DS1:头插法建立单链表

头插法从一个空表开始，读取数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。简单来说，就是把新加进的元素放在表头后的第一个位置：

  1. 先让新节点的next指向头节点之后；
  2. 然后让表头的next指向新节点。

比如学校食堂吃饭排了一大队人，你一上来就插到头一个，那么打饭师傅面对的NEXT就是你了，你的下一个就是原来的队头，队头的上一个就是你。

方法一：

#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node{
    datatype data;
    struct node *next;
}listnode;
typedef listnode *linklist;
listnode *p;
linklist createlist(){
      char ch;
      linklist  head;
      listnode  *p;
      head=NULL;/*初始化为空*/
      ch=getchar();/*传入键盘的字符*/
      while (ch!='\n'){
           p=(listnode*)malloc(sizeof(listnode));/*分配空间*/
           p->data=ch;/*数据域赋值*/
           p->next=head;/*指定后继指针*/
           head=p;/*head指针指定到新插入的结点上*/
              ch=getchar();
      }//while
      return (head);
}
main(){
    linklist newlist=createlist();
    do
    {
       printf("%c\n",newlist->data);
       newlist=newlist->next;
    }while(newlist!=NULL);
    printf("\n");
}//main

方法二：

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node * next;
};
//建立只含头结点的空链表
struct node * create_list()
{
    struct node * head = NULL;
    head = (struct node *)malloc(sizeof(struct node));
    if (NULL == head)
    {
        printf("memory out of use\n");
        return NULL;
    }
    head->next = NULL;
    head->data = 0;
    return head;
}
//头插法建立链表
int insert_form_head(struct node * head, int num)
{
    struct node * head_t = head->next;
    struct node * new_node = NULL;
    new_node = (struct node *)malloc(sizeof(struct node));
    if (NULL == new_node)
    {
        printf("memory out of use\n");
        return -1;
    }
    //将新结点插入到链表的最后
    new_node->data = num;
    new_node->next = head_t;
    head->next = new_node;
    return 0;
}
//打印链表
int show_list(struct node * head)
{
    struct node * temp;
    temp = head->next;
    while(temp)
    {
        printf("%d\n",temp->data);
        temp = temp->next;
    }
    return 0;
}
// 按值删除结点，头结点不被删除
int delete_node(struct node *head, int data)
{
    //head_t 保存要删除结点的上一个结点
    struct node * head_t = head;
    struct node * temp = NULL;
    if (head == NULL)
    {
        printf("delete node from empty list!\n");
        return -1;
    }
    //查找删除的结点的前一个结点
    //如果此处查找的是删除的结点，则需要另加一个指针保存删除结点的前一个指针
    while(NULL != head_t->next)
    {
        if (data == head_t->next->data)
            break;
        head_t = head_t->next;
    }
    //如果要删除的结点不存在，直接返回
    if (NULL==head_t->next)
    {
        printf("node not found\n");
        return -1;
    }
    //删除操作
    temp = head_t->next;
    head_t->next = head_t->next->next;
    free(temp);
    return 0;
}
int main(int argc, char* argv[])
{
    struct node * head;
    head = create_list();
    if (NULL == head)
        printf("create_list error\n");    
    insert_form_head(head,123);
    insert_form_head(head,456);
    show_list(head);
    
    printf("delete once!\n");
    delete_node(head,123);
    show_list(head);
    printf("delete second!\n");//以下是调试代码
    delete_node(head,456);
    show_list(head);
    delete_node(head,0);
    show_list(head);
}