资源描述：
《最新数据结构(严蔚敏)课件-第2章-线性表D(应用)教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(严蔚敏)课件-第2章-线性表D(应用)第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例2例1：两个链表的归并（教材P31例）例2：一元多项式的计算(教材P39–43)例3：试用C或类C语言编写一个高效算法，将一循环单链表就地逆置。操作前：（a1,a2,…ai-1，ai,ai+1，…,an）操作后：（an,…ai+1，ai,ai-1，…,a2,a1）3动态链表样式：静态链表样式：指针数据指针数据指针数据指示数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两
2、个分量，属于结构型数组。常用于无指针类型的高级语言中。7静态单链表的类型定义如下：#defineMAXSIZE1000//预分配最大的元素个数（连续空间typedefstruct{ElemTypedata;//数据域intcur;//指示域}component,SLinkList[MAXSIZE];//这是一维结构型数组前例1：软考题：L={23，17，47，05，31}若此分量定义为指针型，属于动态链表（题目中是指针）；若此分量定义为整型（通常存放下标），则属于静态链表。Z47Y31V23X17U051001191041081
3、161128前例2：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？——教材P32例题data0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]为一个静态链表；S[0].cur则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].cur表示第k+1个结点(即k的直接后继)的位置。i头结点9说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就
4、可以了。例如：在线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：S[7].cur=S[3].cur；Step2:将QIAN的游标换为新元素LIU的下标：S[3].cur=7Step1:将QIAN的游标值存入LIU的游标中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi头结点LIU67710例6：在双向链表中如何实现插入和删除运算？单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增
5、加一个指针域，用来存结点的直接前驱，这样的链表，称为双向链表。其结点的结构为：typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//前驱指针域structDuLNode*next;//后继指针域}DuLNode,*DuLinkList;双向链表类型的定义如下：11双向链表的插入操作：设p已指向第i元素，请在第i元素前插入元素x①ai-1的后继从ai(指针是p)变为x（指针是s):s->next=p;p->prior->next=s;②ai的前驱从ai-1(指针是
6、p->prior)变为x(指针是s);s->prior=p->prior;p->prior=s;注意：要修改双向指针！xsai-1aip指针域的变化：12指针域的变化：后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p->next);p->prior->next=p->next;前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p->prior);p->next->prior=p->prior;ai-1ai+1aip双向链表的删除操作：设p指向第i个元素，删除第i个元素注意：要修改双向指针！13本章小结线性结构
7、(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或“1:1”存储结构：顺序、链式运算：修改、插入、删除[查找和排序另述]3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找修改快O(1)缺点：插入、删除慢O(n)改进方案：链表存储结构14循环链表的特点：从任一结点出发均可找到表中其他结点双向链表的特点：可方便找到任一结点的前驱静态链表的特点：不用指针也能实现链式存储和运算4.链式存储特征：逻辑上相邻，物理上未必相邻；优点：插入、删除快O(1)缺点：
8、随机查找修改慢O(n)5.几种特殊链表的特点：15讨论1：顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但
