中国地质大学数据结构课件.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.43M 资料格式：pdf 举报版权申诉

z876518949-6992693-4744300845188573192.pdf-第1页.png

第1页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第2页.png

第2页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第3页.png

第3页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第4页.png

第4页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第5页.png

第5页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第6页.png

第6页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第7页.png

第7页 / 共34页

z876518949-6992693-4744300845188573192.pdf-第8页.png

第8页 / 共34页

文本预览

上堂课要点回顾单链表 – SLNode类型定义 – 基本操作实现Linlist.h 基本操作实现Linlist.h – 链式存储结构的优缺点应用* – 应用*

数据结构课程内容

第第四四次次课课阅读：朱战立第36 44页第323 328页朱战立，第36-44页、第323-328页练习： P j t1 Project1

例2-6 自学 ●● 例例22 77 (P43) ●● 例例22--7 7 (P43) (P43) 线性表的就地排序 (P43) 线性表的就地排序线性表的就地排序线性表的就地排序 ◆ 问题描述： ◆ 问题描述： 8,4,10,7 8,4,10,7 4,10,7 10 7 10,7 7 8 4 8 4,8 , 4,8,10 , 4,7,8,10 则 h d (4 7 8 10) 则 head=(4,7,8,10) 设head是单链表的头指针编写算法将头指针，编写算法将数据元素按照其值递增有序的顺序进行就地排序。地排序。例：head=(8,4,10,7) p p p p p p 辅助空间为O(1)称就地排序辅助空间为O( )称非辅助空间为O(1)称就地排序，辅助空间为O(n)称非就地排序 head e d head head head head head head

思想：通过改变结点间的指针链接关系实现就地排序从“空表”开始依次将元素结点逐个插排序。从“空表”开始，依次将元素结点逐个插入到链表中。具体如下： 1、将head表断开，形成两个表：head空表和p表 2、依次从p表中取出第一个结点（q指针），将q结点 2、依次从p表中取出第个结点（q指针），将q结点移动到head表中合适位置处： 2.1、在head表中根据数据域大小从头指针开始寻找 2.1、在head表中根据数据域大小从头指针开始寻找 q结点的插入位置i（应该找到第i-1个结点才便于删除，因此定义curr指针寻找第i个结点，pre指针始终指向因此定义curr指针寻找第i个结点，pre指针始终指向 curr结点的直接前驱结点）； 2.2、从p表中删除q结点； 2.2、从p表中删除q结点； 2.3、将q结点插在head表pre结点之后（即curr结点之前）；之前）；循环第2步直至p表为空

【单链表就地插入排序算法】 void LinListSort(SLNode *head) //head为带头结点的单链表，就地排序破坏原来的表。 { SLNode *curr,*pre,*p,*q; 为带头结点的单链表就地排序破坏原来的表 //curr和pre：搜索指针 // 表 //p表 //head表置为空表 h d > p=head->next; t head->next=NULL; while (p!=NULL) { curr=head->next; //curr初始化为指向首元结点 //pre始终指向curr结点的直接前驱 pre=head; while( curr!=NULL && curr->data<=p->data) { pre=curr; //curr和pre后移 curr=curr->next; } q=p; p=p->next; q->next=pre->next; pre->next=q; } } //时间复杂度O(n2）

2.3.5 循环单链表（简称循环链表）循环单链表简称循环链表 ◆ 定义：在单链表的尾结点的链域中放入指向头结点的指针，使整个链表形成一个环形个环形。 ◆ 逻辑状态 ◆ 逻辑状态：非空表： head a0 a1 … an-1 空表： head head 空表：满足head==head->next

优点◆ 优点：不增加额外开销却给不少操作带来方便不增加额外开销，却给不少操作带来方便，从循环表中任一结点出发都能访问到表中其它结点中其它结点循环链表的运算与单链表的基本一致，差别仅在于算法中的循环条件，不是p或 p->next是否为空，而是它们是否等于head。 p >next是否为空，而是它们是否等于head。

分享到：

赞收藏

资料库

中国地质大学数据结构课件.pdf

相关推荐

课程资源

热门标签

最新资料