数据结构chapter 2linklist（2） 链表 ppt课件

《数据结构chapter 2linklist（2） 链表 ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上堂课要点回顾单链表类型定义基本操作实现应用*数据结构课程内容第四次课阅读：朱战立，第36-44页、第323-328页练习：Project1●链式存储结构的优缺点◆优点（1）无需事先了解线性表的长度，结点空间动态申请和释放，允许线性表的长度有很大的变化（2）插入删除操作无需大量移动元素，只要修改指针；能够适应经常插入删除元素的情况◆缺点（1）链表的操作算法较复杂（2）指针域需额外占用空间（3）非随机存储结构，需从头指针遍历查找结点●例2-7(P43)线性表的就地排序◆问题描述：设head是单链表的头指

2、针，编写算法将数据元素按照其值递增有序的顺序进行就地排序。例：head=(8,4,10,7)则head=(4,7,8,10)例2-6自学辅助空间为O(1)称就地排序，辅助空间为O(n)称非就地排序8,4,10,7head8,4,10,7headp4,10,78headp10,74,8headp74,8,10headp4,7,8,10headp思想：通过改变结点间的指针链接关系实现就地排序。从“空表”开始，依次将元素结点逐个插入到链表中。具体如下：1、将head表断开，形成两个表：head空表和p表2、

3、依次从p表中取出第一个结点（q指针），将q结点移动到head表中合适位置处：2.1、在head表中根据数据域大小从头指针开始寻找q结点的插入位置i（应该找到第i-1个结点才便于删除，因此定义curr指针寻找第i个结点，pre指针始终指向curr结点的直接前驱结点）；2.2、从p表中删除q结点；2.3、将q结点插在head表pre结点之后（curr结点之前）；循环第2步直至p表为空【单链表就地排序算法】voidLinListSort(SLNode*head)//head为带头结点的单链表，就地排序破

4、坏原来的表。{SLNode*curr,*pre,*p,*q;//curr和pre：搜索指针p=head->next;//p表head->next=NULL;//head表置为空表while(p!=NULL){curr=head->next;//curr初始化为指向首元结点pre=head;//pre始终指向curr结点的直接前驱while(curr!=NULL&&curr->data<=p->data){pre=curr;//curr和pre后移curr=curr->next;}q=p;p=p->ne

5、xt;q->next=pre->next;pre->next=q;}}时间复杂度O(n2）2.3.5循环单链表（简称循环链表）◆定义：在单链表的尾结点的链域中放入指向头结点的指针，使整个链表形成一个环形。◆逻辑状态：heada0a1an-1…head满足head==head->next空表：非空表：◆优点：不增加额外开销开销，却给不少操作带来方便，从循环表中任一结点出发都能访问到表中其它结点循环链表的运算与单链表的基本一致，差别仅在于算法中的循环条件，不是p或p->next是否为空，而是它们是否等于h

6、ead。2.3.6双向链表◆结点结构弥补单链表next域仅指向后继结点，不能有效找到前驱的不足，增加一个指向直接前驱的指针。nextdataprior◆结点描述类型typedefstructNode{DataTypedata;structNode*prior,*next;}DLNode;/*双向链表结点结构*/◆逻辑状态带头结点的双向链表非空表：…a0a1an-1headhead满足head->prior==head->next==head∧∧∧∧空表：◆逻辑状态带头结点的双向循环链表head满足he

7、ad->prior==head->next==head非空表：…a0a1an-1head空表：◆双向链表中结点的一个重要特征显然，ppriornext==pnextprior==pp…CA…B◆插入一个结点的实现xpspprior=s;…ai-1ai…sprior=pprior;ppriornext=s;snext=p;①②③④◆删除一个结点的实现pnextprior=pprior;p…ai+1ai-1…aipproirnext=pnext;①②free(p);几种主要

8、链表比较空表∧head单链表：a0a1∧an-1…head非空表head空表heada0a1an-1…非空表循环单链表：非空表…a0a1an-1head∧∧head∧∧空表非空表：…a0a1an-1head双向链表：双向循环链表：head空表…a0a1an-1head非空表应用场合的选择不宜使用顺序表的场合线性表的最大长度不确定时经常插入删除时不宜使用链表的场合当读操作比插入删除操作频率大时当指针存储开销和整个结点内容所占空间相比，其比例较大时2.4静态