资源描述：
《数据结构(严蔚敏)课件 第2章 线性表D(应用).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第1次上机内容：单链表的建立、插入与删除基本要求：实现线性表在链式存储结构——单链表中的各种基本操作。1第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分析：要想让an指向an-1,……a2指向a1，一般有
2、两种算法：①替换法：扫描a1……an,将每个ai-1的指针域送入ai+1的指针域。实际上是链栈的概念操作后：（an,…ai+1，ai,ai-1，…,a2,a1）^a1heada2思路：后继变前驱思路：头部变尾部②插入法：扫描a1……an,将每个ai插入到链表首部即可。4p=head->next;//有头结点if(p!=head){q=p->next;p->next=head;p=q};//处理a1while(p!=head)//循环单链表{q=p->next//保存原后继p->next=head->next;head->n
3、ext=p;p=q;}//准备处理下一结点q=head;p=head->next;//有头结点while(p!=head)//循环单链表{r=p->next;p->next=q;//前驱变后继q=p;p=r;}//准备处理下一结点head->next=q;//以an为首替换法的核心语句：插入法的核心语句：ai-1aiqai+1prheada1heada2pq5例4：若某种高级语言没有指针类型，能否实现链式存储和运算？如何实现？答：能！虽然链表通常用动态级联方式存储，但也可以用一片连续空间（一维数组）实现链式存储，这种方式称
4、为静态链表。具体实现方法：定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针。指示域也常称为“游标”6动态链表样式：静态链表样式：指针数据指针数据指针数据指示数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。7静态单链表的类型定义如下：#defineMAXSIZE1000//预分配最大的元素个数（连续空间typedefstruct{ElemTypedata;//数据域intcur;//指示域}componen
5、t,SLinkList[MAXSIZE];//这是一维结构型数组前例1：软考题：L={23，17，47，05，31}若此分量定义为指针型，属于动态链表（题目中是指针）；若此分量定义为整型（通常存放下标），则属于静态链表。Z47Y31V23X17U051001191041081161128前例2：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？——教材P32例题data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur说明1：假设S为SLinkLi
6、st型变量，则S[MAXSIZE]为一个静态链表；S[0].cur则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].cur表示第k+1个结点(即k的直接后继)的位置。i头结点9说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：S[7].cur=S[3].cur；Step2:将QI
7、AN的游标换为新元素LIU的下标：S[3].cur=7Step1:将QIAN的游标值存入LIU的游标中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi头结点LIU67710例6：在双向链表中如何实现插入和删除运算？单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，称为双向链表。其结点的结构为：priordatanexttypedefstructDuLNode{ElemTypedata;//数据
8、域structDuLNode*prior;//前驱指针域structDuLNode*next;//后继指针域}DuLNode,*DuLinkList;双向链表类型的定义如下：11双向链表的插入操作：设p已指向第i元素，请在第i元素前插入元素x①ai-1的后继从ai(指针是p)变为x（指针是s):s->n
