链表

安哥网络

链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

特点线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。
根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。
对于非线性的链表，可以参见相关的IT论坛数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn），和平衡二叉树一样。
其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。
由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

基本操作（pascal语言）

建立
第一行读入n，表示n个数
第二行包括n个数
以链表的形式存储输出这些数

1. programproject1;
   
2. type
   
3. point=^node;
   
4. node=record
   
5. data:longint;
   
6. next:point;
   
7. end;
   
8. var
   
9. i,n,e:longint;
   
10. p,q,head,last:point;
    
11. 
    
12. begin
    
13. write('Inputthenumbercount:');
    
14. readln(n);
    
15. i:=1;
    
16. new(head);
    
17. read(e);
    
18. head^.data:=e;
    
19. head^.next:=nil;
    
20. last:=head;
    
21. q:=head;
    
22. whilei<ndo
    
23. begin
    
24. inc(i);
    
25. read(e);
    
26. new(p);
    
27. q^.next:=p;
    
28. p^.data:=e;
    
29. p^.next:=nil;
    
30. last:=p;
    
31. q:=last
    
32. end;
    
33. //建立链表
    
34. q:=head;
    
35. whileq^.next<>nildo
    
36. begin
    
37. write(q^.data,'');
    
38. q:=q^.next;
    
39. end;
    
40. write(q^.data);
    
41. //输出
    
42. readln;
    
43. readln
    
44. end.

复制代码

删除
在以z为头的链表中搜索第一个n，如果找到则删去，返回值为1，否则返回0

1. functiondelete(n:longint;varz:point):longint;
   
2. var
   
3. t,s:point;
   
4. 
   
5. begin
   
6. t:=z;
   
7. while(t^.next<>nil)and(t^.data<>n)do
   
8. begin
   
9. s:=t;
   
10. t:=t^.next;
    
11. end;
    
12. ift^.data<>nthenexit(0);
    
13. s^.next:=t^.next;
    
14. dispose(t);
    
15. exit⑴
    
16. end;

复制代码

查找
类似于删除，只需要找到不删即可
插入
插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度

1. functioninsert(w,nn:longint;varzz:point):longint;
   
2. vard:longint;v,vp,vs:point;
   
3. 
   
4. begin
   
5. v:=zz;
   
6. ford:=1towdo
   
7. ifv^.next=nil
   
8. thenexit(d)
   
9. else
   
10. begin
    
11. vp:=v;
    
12. v:=v^.next;
    
13. end;
    
14. 
    
15. new(vs);
    
16. vs^.data:=nn;
    
17. vp^.next:=vs;
    
18. vs^.next:=v;
    
19. exit(0)
    
20. end;

复制代码

链表函数

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<iostream.h>
   
4. 
   
5. usingnamespacestd;
   
6. 
   
7. structNode
   
8. {
   
9. intdata;//数据域
   
10. structNode*next;//指针域
    
11. };
    
12. 
    
13. /*
    
14. Create
    
15. *函数功能：创建链表.
    
16. *输入：各节点的data
    
17. *返回值：指针head
    
18. */
    
19. Node*Create()
    
20. {
    
21. intn=0;
    
22. Node*head,*p1,*p2;
    
23. p1=p2=newNode;
    
24. cin>>p1->data;
    
25. head=NULL;
    
26. while(p1->data!=0)
    
27. {
    
28. if(n==0)
    
29. {
    
30. head=p1;
    
31. }
    
32. else
    
33. p2->next=p1;
    
34. p2=p1;
    
35. p1=newNode;
    
36. cin>>p1->data;
    
37. n++;
    
38. }
    
39. p2->next=NULL;
    
40. returnhead;
    
41. }
    
42. 
    
43. /*
    
44. insert
    
45. *函数功能：在链表中插入元素.
    
46. *输入：head链表头指针，p新元素插入位置，x新元素中的数据域内容
    
47. *返回值：无
    
48. */
    
49. voidinsert(Node*head,intp,intx)
    
50. {
    
51. Node*tmp=head;//for循环是为了防止插入位置超出了链表长度
    
52. for(inti=0;i<p;i++)
    
53. {
    
54. if(tmp==NULL)
    
55. return;
    
56. if(i<p-1）
    
57. tmp=tmp->next;
    
58. }
    
59. Node*tmp2=newNode;
    
60. tmp2->data=x;
    
61. tmp2->next=tmp->next;
    
62. tmp->next=tmp2;
    
63. }
    
64. 
    
65. /*
    
66. del
    
67. *函数功能：删除链表中的元素
    
68. *输入：head链表头指针，p被删除元素位置
    
69. *返回值：被删除元素中的数据域.如果删除失败返回-1
    
70. */
    
71. intdel(Node*head,intp)
    
72. {
    
73. Node*tmp=head;
    
74. for(inti=0;i<p;i++)
    
75. {
    
76. if(tmp==NULL)
    
77. return-1;
    
78. if(i<p-1）
    
79. tmp=tmp->next;
    
80. }
    
81. intret=tmp->next->data;
    
82. tmp->next=tmp->next->next;
    
83. returnret;
    
84. }
    
85. 
    
86. voidprint(Node*head)
    
87. {
    
88. for(Node*tmp=head;tmp!=NULL;tmp=tmp->next)
    
89. printf("%d",tmp->data);
    
90. printf("\n");
    
91. }
    
92. 
    
93. intmain()
    
94. {
    
95. Node*head;
    
96. head=newNode;
    
97. head->data=-1;
    
98. head->next=NULL;
    
99. return0;
    
100. }
     
101. 例子
     
102. #include<iostream>
     
103. #defineNULL0
     
104. structstudent
     
105. {
     
106. longnum;
     
107. structstudent*next;
     
108. };
     
109. intmain()
     
110. {
     
111. inti,n;
     
112. student*p=(structstudent*)malloc(sizeof(structstudent));
     
113. student*q=p;
     
114. printf("输入几个值");
     
115. scanf("%d",&n);
     
116. for(i=1;i<=n;i++)
     
117. {
     
118. scanf("%d",&(q->num));
     
119. q->next=(structstudent*)malloc(sizeof(structstudent));
     
120. q=q->next;
     
121. }
     
122. printf("值第几个");
     
123. intrank;
     
124. scanf("%d%d",&(q->num),&rank);
     
125. student*w=p;
     
126. for(i=1;i<rank-1;i++)
     
127. {
     
128. w=w->next;
     
129. }
     
130. q->next=w->next;
     
131. w->next=q;
     
132. for(i=1;i<=n+1;i++)
     
133. {
     
134. printf("%d",p->num);
     
135. p=p->next;
     
136. }
     
137. return0;
     
138. }//指针后移麻烦链表形式循环链表

复制代码

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
应用举例概述
约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。例如：n = 9,k = 1,m = 5
参考代码

1. #include<stdio.h>
   
2. #include<malloc.h>
   
3. #defineN41
   
4. #defineM5
   
5. typedefstructnode*link;
   
6. structnode
   
7. {
   
8. intitem;
   
9. linknext;
   
10. };
    
11. linkNODE(intitem,linknext)
    
12. {
    
13. linkt=malloc(sizeof*t);
    
14. t->item=item;
    
15. t->next=next;
    
16. returnt;
    
17. }
    
18. intmain(void)
    
19. {
    
20. inti;
    
21. linkt=NODE（1,NULL);
    
22. t->next=t;
    
23. for(i=2;i<=N;i++)
    
24. t=t->next=NODE(i,t->next);
    
25. while(t!=t->next)
    
26. {
    
27. for(i=1;i<M;i++)
    
28. t=t->next;
    
29. t->next=t->next->next;
    
30. }
    
31. printf("%d\n",t->item);
    
32. return0;
    
33. }

复制代码

IT论坛相关结语与个人总结
C语言是学习数据结构的很好的学习工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！
链表的提出主要在于顺序存储中的插入和删除的时间复杂度是线性时间的，而链表的操作则可以是常数时间的复杂度。对于链表的插入与删除操作，个人做了一点总结，适用于各种链表如下：
插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。按照这个顺序处理可以完成任何链表的插入操作。
删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。
按照此顺序可以处理任何链表的删除操作。
如果不存在其中的某个节点略过即可。
上面的总结，大家可以看到一个现象，就是插入的顺序和删除的顺序恰好是相反的，很有意思！
操作
-----悉尼大学工程学院张志刚（Stone Cold）作品

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<conio.h>
   
4. typedefstructSlist
   
5. {
   
6. intdata;
   
7. structSlist*next;
   
8. }
   
9. SLIST;
   
10. SLIST*InitList_Sq()/*初始化函数*/
    
11. {
    
12. inta;
    
13. SLIST*h,*s,*r;
    
14. h=(SLIST*)malloc(sizeof(SLIST));/*建立头指针，头指针不可以更改！！！*/
    
15. r=h;
    
16. if(!h)
    
17. {
    
18. printf("分配失败");
    
19. exit(0);
    
20. }
    
21. scanf("%d",&a);
    
22. for(;a!=-1;)
    
23. {
    
24. s=(SLIST*)malloc(sizeof(SLIST));/*每次都开辟一个结点空间并赋值*/
    
25. s->data=a;
    
26. r->next=s;
    
27. r=s;
    
28. scanf("%d",&a);
    
29. }
    
30. r->next='\0';
    
31. returnh;
    
32. }
    
33. voidprint_list(SLIST*finder)/*打印函数*/
    
34. {
    
35. while(finder!='\0')
    
36. {
    
37. printf("->%d",finder->data);
    
38. finder=finder->next;
    
39. }
    
40. printf("->end\n");
    
41. }
    
42. intDeleteNode(SLIST*killer)//删除节点函数
    
43. {
    
44. inti,j=0;
    
45. SLIST*p,*q;
    
46. intx;
    
47. p=killer;
    
48. q=killer->next;
    
49. printf("请输入您要删除的节点序号：");
    
50. scanf("%d",&i);
    
51. while((p->next!='\0')&&(j<i-1））
    
52. {
    
53. p=p->next;
    
54. j++;
    
55. q=p->next;
    
56. }
    
57. if(p->next=='\0'||j>i-1）
    
58. {
    
59. printf("\nerror");
    
60. return-1;
    
61. }
    
62. else
    
63. {
    
64. p->next=q->next;
    
65. x=q->data;
    
66. free(q);
    
67. returnx;
    
68. }
    
69. }
    
70. voidInsert_Node(SLIST*jumper)//插入函数，本算法为前插结点法
    
71. {
    
72. intt,e,j=0;
    
73. SLIST*p,*q;
    
74. p=jumper;
    
75. printf("请输入要插入位置的序号：");
    
76. scanf("%d",&t);
    
77. printf("请输入要插入的元素：");
    
78. scanf("%d",&e);
    
79. while(p->next!='\0'&&j<t-1）
    
80. {
    
81. j++;
    
82. p=p->next;
    
83. }
    
84. if(p=='\0'||j>t-1）
    
85. printf("插入的目的位置不存在");
    
86. else
    
87. {
    
88. q=(SLIST*)malloc(sizeof(SLIST));
    
89. q->data=e;
    
90. q->next=p->next;
    
91. p->next=q;
    
92. }
    
93. }
    
94. voidLocate_List(SLIST*reader)//查找值为e的元素
    
95. {
    
96. inte,i=0;
    
97. SLIST*p;
    
98. p=reader;
    
99. printf("请输入要查找的元素：");
    
100. scanf("%d",&e);
     
101. while(p->next!='\0'&&p->data!=e)
     
102. {
     
103. i++;
     
104. p=p->next;
     
105. }
     
106. if(p->data==e)
     
107. printf("此元素在%d号位置\n",i);
     
108. else
     
109. printf("无此元素！");
     
110. }
     
111. voidmain()
     
112. {
     
113. inti,k,y;
     
114. SLIST*head;
     
115. printf("\n1.建立线性表");
     
116. printf("\n2.在i位置插入元素e");
     
117. printf("\n3.删除第i个元素，返回其值");
     
118. printf("\n4.查找值为e的元素");
     
119. printf("\n5.结束程序运行");
     
120. printf("\n===================================================");
     
121. printf("请输入您的选择：");
     
122. scanf("%d",&k);
     
123. switch(k)
     
124. {
     
125. case1:
     
126. {
     
127. head=InitList_Sq();
     
128. print_list(head->next);
     
129. }break;
     
130. case2:
     
131. {
     
132. head=InitList_Sq();
     
133. print_list(head->next);
     
134. Insert_Node(head);
     
135. print_list(head->next);
     
136. }
     
137. break;
     
138. case3:
     
139. {
     
140. head=InitList_Sq();
     
141. print_list(head->next);
     
142. y=DeleteNode(head);
     
143. print_list(head->next);
     
144. if(y!=-1）
     
145. printf("被删除元素为：%d",y);
     
146. }break;//头结点不算，从有数据的开始算第一个
     
147. case4:
     
148. {
     
149. head=InitList_Sq();
     
150. print_list(head->next);
     
151. Locate_List(head);
     
152. }break;
     
153. }
     
154. }

复制代码

本程序可在微软VC++下编译通过并且运行
使用方法简介：运行程序后，先打数字1，然后回车，这样就可以先创建一个新的链表，比如你要创建一个
4->5->6->7这样一个链表，你就输入数字4回车，输入5回车，输入6回车，输入7回车，最后输入-1回车，这个-1就是告诉程序到此为止的标志
假如你要使用插入的功能位置插入，就输入3，回车，程序会问你插入的数值是什么，比如你要插入999，然后回车，999就被插进去了

http://baike.baidu.com/link?url= ... ODOSNIt4B-xjTk29nj_
链表