一、指针与单链表
1、定义：通过使用指针将节点（结点）链接起来成为链表
2、节点（结点）：
1）、数据域：主要用来存储数据，可以基本数据类型，也可以是构造数据类型；
2）、指针域：主要用来当前节点（结点）的下一个节点的地址；
3）、使用命名结构体嵌套定义；
4）、定义结构体
5）、定义结构体指针
定义节点数据的代码如下：
3 #define DataType int 4 5 typedef struct _node{ 6 DataType data; 7 struct _node *next; 8 } Node;
其中第3行代码使用宏定义的方式定义数据类型，也可以使用类型定义数据类型：
3 typedef int DataType； 4 5 typedef struct _node{ 6 DataType data; 7 struct _node *next; 8 } Node;
代码作用是一样一样的。
3、链表：
1）、将一系列节点通过特定的方式链接足层的数据结构；
2）、链表中通常会有一个头节点
3）、链表中通常会有一个尾节点
4）、链表中通常会有一个当前节点；
10 typedef struct _list{ 11 Node *head; 12 Node *tail; 13 Node *current; 14 } List;
链表的定义需要Node节点定义的支持，若不单独定义也可以直接使用节点指针即可。
5）、常见的节点操作；节点操作是根据需要自己把握的事情，通常是完成结构数据的初始化等工作。
6）、对指针使用sizeof运算获取指针长度
4、链表中常见操作：
1）、链表初始化initialList；
2）、链表的头插法addHead；
3）、链表的尾插法addTail；
4）、链表中获取指定数据节点的指针getNode；
5）、链表中删除节点deleteNode；
6）、链表中获取表的长度getLength；
7）、输出链表中的所有数据displayList；
根据以上数据类型的需要和链表中需要的操作可以抽象出链表的抽象数据类型，使用list.h表示：
1 #ifndef list_h 2 #define list_h 3 typedef int DataType; 4 5 typedef struct _node{ 6 DataType data; 7 struct _node *next; 8 } Node; 9 10 typedef struct _list{ 11 Node *head; 12 Node *tail; 13 Node *current; 14 } List; 15 16 void initList(List *); 17 void addHead(List *, DataType); 18 void addTail(List *, DataType); 19 Node *getNode(List *, DataType); 20 void deleNode(List *, DataType); 21 int getLength(List *); 22 void dispList(List *); 23 24 #endif
操作实现的代码如下：
1 #include <stdlib.h> 2 #include <stdio.h> 3 4 #include "list.h" 5 6 //链表初始化 7 void initList(List *list){ 8 list->head = NULL; 9 list->tail = NULL; 10 list->current = NULL; 11 } 12 13 //链表头插法 14 void addHead(List *list, DataType iData){ 15 Node *node = (Node *)malloc(sizeof(Node)); 16 node->data = iData; 17 node->next = NULL; 18 19 if(list->head == NULL){ 20 list->tail = node; 21 }else{ 22 node->next = list->head; 23 } 24 list->head = node; 25 26 return; 27 } 28 29 //链表尾插法 30 void addTail(List *list, DataType iData){ 31 Node *node = (Node *)malloc(sizeof(Node)); 32 node->data = iData; 33 node->next = NULL; 34 35 if(list->head == NULL){ 36 list->head = node; 37 }else{ 38 list->tail->next = node; 39 } 40 list->tail = node; 41 42 return; 43 44 } 45 46 //链表节点获取 47 Node *getNode(List *list, DataType iData){ 48 Node *node = (Node *)malloc(sizeof(Node)); 49 node = list->head; 50 while(node != NULL){ 51 if(node->data == iData){ 52 return node; 53 }else{ 54 node = node->next; 55 } 56 } 57 58 return NULL; 59 } 60 61 //删除链表中的节点 62 void deleNode(List *list, DataType iData){ 63 if(list->head->data == iData){ 64 list->head = list->head->next; 65 } 66 Node *prev = list->head; 67 Node *node = prev->next; 68 while(node != NULL){ 69 if(node->data == iData){ 70 prev->next = prev->next->next; 71 72 return; 73 }else{ 74 prev = prev->next; 75 node = node->next; 76 } 77 } 78 79 return; 80 } 81 82 //链表长度 83 int getLength(List *list){ 84 Node *node = list->head; 85 int i = 0; 86 while(node != NULL){ 87 node = node->next; 88 i++; 89 } 90 91 return i; 92 } 93 94 //链表输出 95 void dispList(List *list){ 96 Node *node = list->head; 97 int i = 0; 98 while(node != NULL){ 99 printf("the %dth node: %d ", i + 1, node->data); 100 node = node->next; 101 i++; 102 } 103 printf("disp finished! "); 104 105 return; 106 }
测试代码如下：
1 #include "list.h" 2 #include <stdlib.h> 3 4 int main(int argc, char **argv) 5 { 6 List *list1 = (List *)malloc(sizeof(List)); 7 printf("the first: "); 8 initList(list1); 9 addHead(list1, 1); 10 addHead(list1, 3); 11 addHead(list1, 5); 12 addHead(list1, 7); 13 addHead(list1, 9); 14 dispList(list1); 15 printf("the second: "); 16 deleNode(list1, 1); 17 dispList(list1); 18 printf("The length: %d ", getLength(list1)); 19 Node *node = getNode(list1, 7); 20 printf("The getNode result: %d ", node->data); 21 22 return 0; 23 }
测试完成功能正常。