清华大学10课件

第11章链表及其应用1本章主要内容链表的基本概念链表的基本操作方法循环链表双向链表链表的应用2清华大学黄维通设计制作11.1链表的基本概念3清华大学黄维通设计制作structstu{intnum;floatvalue;数据域

charname[20];…structstu*next;指针域};链表的存储结构在内存空间上由两个域组成5清华大学黄维通设计制作6清华大学黄维通设计制作线性表的顺序表示和实现用一组地址连续的存储单元依次存储线性表的数据元素。通常用数组来描述。特点：逻辑上相邻的两个元素，在物理上也具有相邻的存储位置。可以随机存取任何一个元素。插入和删除时需要移动大量元素空间不能充分得到利用表的容量难以扩充7清华大学黄维通设计制作

从以上讨论可知，线性表顺序存储结构的特点是逻辑关系相邻的两个元素，其物理位置也相邻，因此可以随机存取表中任意元素，它的存储位置可以用一个简单、直观的表达式来表示，但删除、修改时，需移动大量的元素。而链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但也失去了顺序表可随机存储的优点。9清华大学黄维通设计制作定义：线性表是n个数据元素的有限序列。线性表的基本操作判断线性表是否为空构造一个空线性表将一个线性表重置为空表求线性表的元素个数求线性表的第i个元素的值在线性表中查找第一个满足指定条件的元素求指定元素的前驱，即为ai前面的元素ai-1求指定元素的后继在线性表的第i个元素之前插入一个新元素删除线性表的第i个元素遍历线性表销毁一个线性表线性表的定义和基本操作10清华大学黄维通设计制作11.1.2动态内存分配在栈上创建：保存函数内的局部变量，函数结束时自动地释放掉內存分配方式从静态存储区域分配：在程序编译时分配，在程序的整个运行期间都存在。比如全局变量和静态变量从堆上分配：即动态内存分配，用malloc向系统申请一连续的内存空间，不再需要时，用free函数释放11清华大学黄维通设计制作11.2.1链表的建立使第一个结点的next指针指向第二个结点cursorcursor13清华大学黄维通设计制作如何使第二个结点的next指针指向第三个结点呢？cursorcursor14清华大学黄维通设计制作【例】创建一个包含表头结点和10个结点的链表，假设这个链表表征学生的数据，包含学生的学号、考试成绩。#include"stdlib.h"#include"stdio.h“#defineLENsizeof(structstu)structstu{intnum;floatscore;structstu*next;};15清华大学黄维通设计制作tempnode->score=20.5*i+10;cursor->next=tempnode; //将结点连接到链表上cursor=cursor->next; //移到下一个结点printf("num=%d,score=%f\n",tempnode->num,tempnode->score);}printf("\n");return(mylist);}

17清华大学黄维通设计制作调用create()函数的主函数及链表输出函数print(structstu*list){structstu*cursor;cursor=list;if(list!=NULL)

do{cursor=cursor->next;//依次遍历链表

printf("%d%f\n",cursor->num,cursor->score);}while(cursor->next!=NULL);}voidmain(){intn; //链表结点数structstu*my_list;scanf("%d",&n); //输入链表结点数my_list=create(n); //返回所创建的链表print(my_list);}18清华大学黄维通设计制作对链表结点的访问，必须从头结点开始，依次遍历链表，直到找到该结点(如果所要找的数据在链表的尾结点上，则需要遍历整个链表才能找到)。而数组可以通过下标快速定位元素的存储位置。下面给出找第n个结点的算法。11.2.2链表结点的访问

19清华大学黄维通设计制作【例】链表的连接。structstu*link(structstu*list1,structstu*list2){structstu*cursor;cursor=list1;

while(cursor->next!=NULL)cursor=cursor->next; //找到第一个链表的最后一个结点cursor->next=list2->next; //将两个链表连接起来return(list1);}11.2.3同结构链表的连接

21清华大学黄维通设计制作11.2.4链表结点的插入

第一种情况：在头结点之前插入22清华大学黄维通设计制作第二种情况：在链表的中间位置插入结点

23清华大学黄维通设计制作【例】无表头结点的链表中结点的插入structstu*insert_node(structstu*list,structstu*newnode){structstu*cursor;cursor=list;if(cursor==NULL||cursor->num>newnode->num)//链表为空，或新结点的num值在链表结点中是最小的，则插入到第一个结点的位置。{newnode->next=cursor;list=newnode;}25清华大学黄维通设计制作else//插入表中和表尾的情况同时处理{while(cursor->next&&cursor->next->num<newnode->num)

//若cursor不为尾结点，且下一结点的num值仍小于newnode的num值，继续向后移动光标cursor=cursor->next;newnode->next=cursor->next;cursor->next=newnode; //将newnode插入到cursor与cursor->next之间}returnlist;}26清华大学黄维通设计制作【例】删除带无表头结点的链表结点算法structstu*delete_node_withhead(structstu*list,intvalue){structstu*cursor;cursor=list;if(cursor->num==value){list=cursor->next;free(cursor);}

else//删除头结点{while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;//若cursor->next为有效结点且不是要删除//的结点，则cursor指针向后移动。

if(cursor->next)cursor->next=cursor->next->next;}return(list);}29清华大学黄维通设计制作【例】删除不带有表头结点的链表结点算法structstu*delete_node_withouthead(structstu*list,intvalue){structstu*cursor;cursor=list;

while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;if(cursor->next)//若cursor->next为有效结点且该结点不//是要删除的结点，cursor指针向后移动cursor->next=cursor->next->next;return(list);}30清华大学黄维通设计制作【例】链表存储空间的释放。voidfree_list(structstu*list){structstu*tempnode;while(list){ tempnode=list; list=list->next; free(tempnode);}}11.2.6释放链表存储空间

31清华大学黄维通设计制作11.3循环链表

带表头的空循环链表带表头的非空的循环链表32清华大学黄维通设计制作structstu_dual{intnum;floatscore;structstu_dual*next;//指向后继结点的指针structstu_dual*previous;//指向前驱结点的指针}11.4双向链表

双链表的结构定义双向循环链表33清华大学黄维通设计制作对链表结点的操作，要先确定结点位置，然后才进行操作，此外，由于链表需要额外的空间开销，这将影响性能11.5链表的应用

【例】合并两个有序链表的并从大到小顺序输出排序后的结果#include"stdlib.h"#include"stdio.h"structstu{intnum;structstu*next;};34清华大学黄维通设计制作structstu*Merge(structstu*list1,structstu*list2){structstu*cursor1=list1; //指向list1structstu*cursor2=list2; //指向list2structstu*tmp; //保存插入前cursor2的位置

while(cursor1!=NULL&&cursor2!=NULL){if(cursor2->num<=cursor1->num){tmp=cursor2;cursor2=cursor2->next;tmp->next=cursor1; //插入tmplist1=tmp;cursor1=tmp;}35清华大学黄维通设计制作elseif(cursor2->num>cursor1->num&&cursor1->next==NULL){cursor1->next=cursor2;break;}elseif(cursor2->num>cursor1->num&&

cursor2->num<=cursor1->next->num){tmp=cursor2; //cursor2位于cursor1之后后移cursor2cursor2=cursor2->next;tmp->next=cursor1->next;//插入cursor2cursor1->next=tmp;}else cursor1=cursor1->next;}list1=list1->next; return(list