开始学习数据结构这个大坑了啊。。。赶紧记一记各种数据结构的写法。
以下是单链表的C语言实现，只有一些最基本的功能。
我这个链表有一个表头（头节点），储存了该链表的长度。但是这个不是必须的，数据结构没有一个确定的答案，只要合适自己就行。
头节点储存链表的长度，指针指向第一个节点。
LinkedList.h
该文件定义了链表，并声明了一些操作链表的函数
1 #ifndef _LINKEDLIST_H_ 2 #define _LINKEDLIST_H_ 3 4 #include<stdlib.h> 5 #include<stdio.h> 6 7 typedef int DataType; 8 9 struct node 10 { 11 DataType data; 12 struct node *next; 13 }; 14 typedef struct node NODE; 15 typedef NODE *HEAD; 16 17 //初始化链表，创建一个头节点，值为该链表长度 18 void InitList(NODE **L); 19 20 //头插法创建整表 21 void CreateListHead(NODE **L); 22 23 //尾插法创建整表 24 void CreateListTail(NODE **L); 25 26 //销毁链表 27 void DestroyList(NODE **L); 28 //销毁节点及以后的节点 29 void DestroyNode(NODE *N); 30 31 //获取位置i的数据 32 void GetElem(NODE L,DataType i, DataType *num); 33 34 //获取数据num的位置 35 int LocateElem(NODE L, DataType num); 36 37 //获取数据cur之前的一个数据 38 int PriorElem(NODE L, DataType cur_e, DataType *pre_e); 39 40 //获取数据cur之后的一个数据 41 int NextElem(NODE L, DataType cur_e, DataType *next_e); 42 43 //在位置i插入元素num 44 void ListInsert(NODE *L, DataType i, DataType num); 45 46 //在位置i删除元素，并将其值给num 47 void ListDelete(NODE *L, DataType i, DataType *num); 48 49 //打印整表 50 void ListTraverse(NODE L); 51 52 #endif
LinkedList.c
在该文件中我们具体的定义每个函数的功能。
首先我们将头文件包含进来
#include"LinkedList.h"
然后从上往下依次定义函数。
第一个是初始化链表的函数，作用是新建一个头节点，并将传入的指针指向该头节点。
1 void InitList(NODE **L) 2 { 3 *L = (NODE*)malloc(sizeof(NODE)); 4 (*L)->data = 0; 5 (*L)->next = NULL; 6 }
注意该函数的形参有两个**，需要传入的实参为指向指针的指针。
比如我们在main函数中，
HEAD head;
这个head是指向NODE的指针（因为我在头文件中typedef NODE *HEAD），那么传入它的时候就要写成
InitList(&head);
函数接收的值即指向该指针的指针。
为什么这么做呢？
因为我们要创建链表，而一开始head指针是空的，我们需要修改它的值让他指向新创建的头节点。
我们都知道要修改某个数据的值，只能向函数传入指向该数据的指针；而我们要修改这个head指针的值，那就要传入指向他的指针。
对于这个链表来说，如果我们想修改头指针的值（通常发生在创建链表和销毁链表的时候），那么相应的函数就要接受指向头指针的指针。
比如下面的头插法和尾插法创建链表，以及链表的销毁。
头插法创建链表
特性是输入的数据与最后生成的链表顺序相反
1 void CreateListHead(NODE **L) 2 { 3 InitList(L); 4 int num; 5 NODE *temp; 6 while (scanf("%d", &num) && num != 999) 7 { 8 temp = (NODE*)malloc(sizeof(NODE)); 9 temp->data = num; 10 //新建的节点指向头节点后的一个节点 11 temp->next = (*L)->next; 12 //头节点指向新建的节点，插队成功 13 (*L)->next = temp; 14 (*L)->data++; 15 } 16 }
尾插法创建链表
特性与头插法相反，输入的数据与生成的链表顺序相同，但代价是使用的时候需要多维护一个不断指向尾部的指针。
1 void CreateListTail(NODE **L) 2 { 3 InitList(L); 4 int num; 5 NODE *temp; 6 //指向尾部 7 NODE *tail_pointer; 8 //刚开始头节点为链表的尾部 9 tail_pointer = *L; 10 while (scanf("%d", &num) && num != 999) 11 { 12 temp = (NODE*)malloc(sizeof(NODE)); 13 //尾部的下一个指向新建的节点 14 tail_pointer->next = temp; 15 temp->data = num; 16 temp->next = NULL; 17 18 //新建的节点变成尾部 19 tail_pointer = temp; 20 (*L)->data++; 21 } 22 }
链表的销毁
注意只需在main函数中调用DestroyList即可，DestroyNode函数不需要人为调用。
1 void DestroyNode(NODE *N) 2 { 3 NODE *temp = NULL; 4 if (N != NULL) 5 { 6 temp = N; 7 N = N->next; 8 free(temp); 9 temp = NULL; 10 11 DestroyNode(N); 12 } 13 } 14 15 void DestroyList(NODE **L) 16 { 17 DestroyNode(*L); 18 *L = NULL; 19 }
使用了递归？（又是你？）
说实话我不知道这个DeleteList能不能正常工作，dubug半天也看不出过了这个函数之后到底起没起作用。。。。但是按照代码分析似乎好像也许是可以工作的。
按照递归从头开始删除每一个节点。递归真是个神奇的东西。
剩下的函数定义都直接贴出来了，都是比较简单的东西，对照头文件看看就可以了。
1 void GetElem(NODE L, DataType i, DataType *num) 2 { 3 HEAD temp; 4 int lop; 5 6 temp = &L; 7 temp = temp->next; 8 for (lop = 0; lop < i; lop++) 9 { 10 temp = temp->next; 11 } 12 13 *num = temp->data; 14 temp = NULL; 15 } 16 17 int LocateElem(NODE L, DataType num) 18 { 19 HEAD temp; 20 int lop; 21 22 temp = &L;
24 temp = temp->next; 25 26 for (lop = 0; lop < L.data; lop++) 27 { 28 if (num == temp->data) 29 { 30 return lop + 1; 31 } 32 else 33 { 34 temp = temp->next; 35 } 36 } 37 38 return 0; 39 } 40 41 int PriorElem(NODE L, DataType cur_e, DataType * pre_e) 42 { 43 int lop; 44 NODE *target,*cursor; 45 target = &L; 46 cursor = &L; 47 cursor = cursor->next; 48 for (lop = 0; lop < L.data ; lop++) 49 { 50 if (cursor->data == cur_e) 51 { 52 if (lop == 0) 53 { 54 return 0; 55 } 56 *pre_e = target->data; 57 return 1; 58 } 59 else 60 { 61 cursor = cursor->next; 62 target = target->next; 63 } 64 } 65 return -1; 66 } 67 68 int NextElem(NODE L, DataType cur_e, DataType * next_e) 69 { 70 int lop; 71 NODE *cursor; 72 cursor = &L; 73 cursor = cursor->next; 74 75 for (lop = 0; lop < L.data ; lop++) 76 { 77 if (cursor->data == cur_e) 78 { 79 if (lop == L.data - 1) 80 { 81 return 0; 82 } 83 *next_e = cursor->next->data; 84 return 1; 85 } 86 cursor = cursor->next; 87 } 88 return -1; 89 } 90 91 void ListInsert(NODE *L, DataType i, DataType num) 92 { 93 HEAD temp; 94 NODE *temp_node; 95 int lop; 96 97 temp = L; 98 99 for (lop = 0; lop < i; lop++) 100 { 101 temp = temp->next; 102 } 103 temp_node = (NODE*)malloc(sizeof(NODE)); 104 temp_node->data = num; 105 temp_node->next = NULL; 106 107 if (lop != L->data) 108 { 109 temp_node->next = temp->next; 110 } 111 else 112 { 113 temp_node->next = NULL; 114 } 115 temp->next = temp_node; 116 117 temp = L; 118 temp->data++; 119 temp = NULL; 120 temp_node = NULL; 121 } 122 123 void ListDelete(NODE *L, DataType i, DataType *num) 124 { 125 HEAD temp; 126 NODE *temp_delete; 127 int lop; 128 129 temp = L; 130 131 for (lop = 0; lop < i; lop++) 132 { 133 temp = temp->next; 134 } 135 temp_delete = temp->next; 136 *num = temp_delete->data; 137 temp->next = temp->next->next; 138 139 free(temp_delete); 140 141 temp = L; 142 temp->data--; 143 temp = NULL; 144 temp_delete = NULL; 145 } 146 147 void ListTraverse(NODE L) 148 { 149 HEAD temp; 150 temp = &L; 151 int timer= 0; 152 printf("The Length Of This List Is: %d ", temp->data); 153 printf("The Member(s) Are: "); 154 while (temp->next!= NULL) 155 { 156 temp = temp->next; 157 printf("%d) %d ", timer++, temp->data); 158 } 159 printf(" ============================ "); 160 }
最后可以写一个main函数测试一下该链表。所有的函数都可以试试。我只调用了几个函数。
1 #include"LinkedList.h" 2 3 int main() 4 { 5 HEAD head = NULL; 6 int a = -1; 7 8 //输入999终止创建,以下方法任选一个 9 10 //CreateListHead(&head); 11 CreateListTail(&head); 12 13 ListTraverse(*head); 14 15 if (PriorElem(*head, 1, &a) == 1) 16 { 17 printf("前驱元素 %d ", a); 18 } 19 20 if (NextElem(*head, 4, &a) == 1) 21 { 22 printf("后继元素 %d ", a); 23 } 24 DestroyList(&head); 25 return 0; 26 }
前驱后继元素那里的值可以自己更换，我用的是1和4