深度解析链表操作
此篇为原创，如需转载，请注明出处：http://blog.****.NET/qq_36759732
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
通过此篇，你将会深入了解到链表的基本操作，便于以后使用链表时更加清楚。大家知道，对于链表的操作，有增，删，改，查等，但它本质上是如何实现的呢，下面我会通过代码实现链表的基本操作。
链表中可以存放各种类型，甚至可以再存放一个链表，为了便于解释，下面操作用存放整型数据元素实现。 编程环境：linux
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4
5 #define OK 1
6 #define ERROR 0
7
8 typedef struct node{
9 int data;
10 struct node *next;
11 }List,*pList;
12
13 pList creat_node(int value){ // 创建结点
14 pList new_node = (pList)malloc(sizeof(List));
15 new_node->data = value;
16 new_node->next = NULL;
17 return new_node;
18 }
19
20 pList insert_node(pList head, pList new_node, int index){ // 插入
21 pList p;
22 List ret; // 可能往头结点插入，创建虚拟节点指向头结点
23 ret.next = head;
24 p = &ret;
25 while(p != NULL && index > 0){
26 p = p->next;
27 index--;
28 }
29 new_node->next = p->next;
30 p->next = new_node;
31
32 if(index == 0){
33 ret.next = new_node;
34 }
35 return ret.next;
36 }
37
38 pList delete_node(pList head, int index){ // 删除
39 pList p,q;
40 List ret;
41 ret.next = head;
42 p = &ret;
43 q = ret.next;
44 while(q && p && index ){
45 p = p->next;
46 index--;
47 }
48 q = p->next;
49 p->next = q->next;
50 free(q);
51 return ret.next;
52 }
53 void search_node(pList head, int value){ //查找
54 pList p = head;
55 int index = 0;
56 while(p != NULL){
57 if(p->data == value) {
58 printf("查找到位置为：%d\n",index);
59 return ;
60 }
61 p = p->next;
62 index++;
63 }
64 printf("未找到\n");
65 return ;
66 }
67
68 void output(pList head){ //输出链表
69 pList p = head;
70 printf("LIST:");
71 while(p){
72 printf("->%d ",p->data);
73 p = p->next;
74 }
75 printf("\n");
76 return ;
77 }
78
79 void clear(pList head){ //清空
80 pList p = head;
81 if(p == NULL) return ;
82 free(p);
83 return ;
84 }
85
86 int main(){
87 printf("/***************************/\n");
88 printf("0代表插入,1代表删除,2代表查找\n");
89 printf("/***************************/\n");
90 printf("\n");
91 pList head = (pList)malloc(sizeof(List));
92 pList p;
93 int opr;
94 for(int i = 0; i < 10; ++i){
95 insert_node(head, creat_node(rand() % 100 + 1), i);
96 }
97 printf("初始化随机链表:\n");
98 output(head);
99 while(scanf("%d",&opr)!=EOF){
100 switch(opr){
101 int value,index;
102 case 0:
103 printf("输入插入值和位置:");
104 scanf("%d%d", &value, &index);
105 insert_node(head, creat_node(value), index);
106 output(head);
107 break;
108 case 1:
109 printf("输入删除位置:");
110 scanf("%d", &index);
111 delete_node(head, index);
112 output(head);
113 break;
114 case 2:
115 printf("输入查找的值:");
116 scanf("%d", &value);
117 search_node(head, value);
118 break;
119 }
120 }
121 clear(head);
122 return 0;
123 }
以上是本人对链表操作的理解，欢迎大家指点与修正。后面我会上传关于树的基本操作，大家敬请期待。