单向链表的C语言实现

用C语言的指针实现了单向链表中的几项基本操作：新建链表，置空链表，插入节点（由于在尾部加入新节点尤为常用，故单独用一个函数实现），删除节点。为了以上操作更便捷，另分别写了返回尾节点和某特定节点的函数。

为了统一插入及删除节点的操作，使其不因节点位置不同而受到影响（主要是插入或删除头节点），我在真正的表头（我称之为true_head）前加入一空节点作为表头。

另外，在特定位置插入、删除节点时必须确保此位置是有效的。想法是：在表头中储存链表的长度，在特定位置插入、删除时，将此位置与长度比较大小，如果位置大于长度，则报错；如果位置小于长度，则执行操作并更新表头中的长度信息。长度信息的更新：新建时置为1，置空时重置为0，插入成功则加1，删除成功则减1。

用结构体定义：

1 typedef struct Node{
2     int i;
3     struct Node *next;
4 }Node;

新建链表：这是唯一一个需要返回头指针的函数。

 1 Node *MakeList(void)//创建带有空表头节点的列表并返回表头，其中表头储存的是链表的长度
 2 {
 3     Node *head = (Node *)malloc(sizeof(Node));
 4     Node *true_head = (Node *)malloc(sizeof(Node));
 5     printf("Please type in the element of the head node:");
 6     scanf("%d", &true_head->i);
 7     head->next = true_head;
 8     true_head->next = NULL;
 9     head->i = 1;
10     return head;
11 }

置空链表：

1 void MakeNull(Node *head)
2 {
3     head->next = NULL;
4     head->i = 0;
5 }

插入节点：

 1 void Insert(Node *head, int i)//在特定位置插入节点
 2 {
 3     if(i > (head->i + 1))//注意：在i或者i+1位置都没有问题，在i+1位置相当于Append
 4     {
 5         printf("Insertion failed because i is too big!\n");
 6     }
 7     else
 8     {
 9         Node *temp = (Node *)malloc(sizeof(Node));
10         printf("Please type in the element of the new node:");
11         scanf("%d", &temp->i);
12         Node *pre = GetNode(head, i-1);
13         Node *aft = pre->next;//刚开始以为要把在表尾的插入单独拿出来讨论，但后来发现此时aft不就是NULL了嘛♪(´▽｀ )
14         temp->next = aft;
15         pre->next = temp;
16         head->i++;
17     }

 1 void Append(Node *head)//在链表尾部附加节点
 2 {
 3     Node *temp = (Node *)malloc(sizeof(Node));
 4     printf("Please type in the element of the new node:");
 5     scanf("%d", &temp->i);
 6     Node *pre = GetTail(head);
 7     pre->next = temp;
 8     temp->next = NULL;
 9     head->i++;
10 }

删除节点：

 1 void Remove(Node *head, int i)//删除特定节点
 2 {
 3     if(i > head->i)
 4     {
 5         printf("Removal failed because i is too big!\n");
 6     }
 7     else
 8     {
 9         Node *pre = GetNode(head, i-1);//同插入，尾节点也不需要拿出来
10         Node *temp = pre->next;
11         pre->next = temp->next;
12         head->i--;
13     }
14 }

其他的：

 1 Node *GetNode(Node *head, int i)//传入节点位置，并返回此节点
 2 {
 3     if(i > head->i)
 4     {
 5         printf("Failed to get node i because i is too big!\n");
 6         return NULL;
 7     }
 8     else
 9     {
10         Node *temp = head;
11         int k;
12         for(k = 0; k < i; k++)
13         {
14             temp = temp->next;
15         }
16         return temp;
17     }
18 }
19 
20 Node *GetTail(Node *head)//返回链表尾节点，便于在链表尾插入新节点
21 {
22     Node *temp = head;
23     while(NULL != temp->next)
24     {
25         temp = temp->next;
26     }
27     return temp;
28 }
29 
30 void PrintList(Node *head)//按从表头到表尾的顺序打印链表
31 {
32     Node *temp = head->next;//从真表头开始打印
33     if(NULL == temp)
34     {
35         printf("There is no element in the list!\n");
36     }
37     else
38     {
39         int k;
40         for(k = 0; k < head->i; k++)
41         {
42             printf("%d\n", temp->i);
43             temp = temp->next;
44         }
45     }
46 }

问题们：

由于指针掌握不好，对于一些操作有些不知所以然；增加一个指针指向尾节点，就可以把GetTail替换掉，但是在进行插入删除操作时可能会增加额外的工作；希望增加通过元素返回节点位置的操作。