西安电子科技大学计算机学院数据结构课件 第2章（3）.pptxVIP

第2章线性表2.3 线性表的链式表示和实现1.循环链表循环链表是另一种形式的链式存储结构；可从当前结点出发，访问到任一结点；循环单链表；多重循环链表。

第2章线性表单循环链表设置尾指针rear,比设头指针更好。

第2章线性表练习：有两个带头结点的单循环链表LA、LB，编写一个算法，将两个单循环链表合并为一个单循环链表，其头指针为LA。p=A-next;q=B-next;A-next=q-next;B-next=p;A=B;free(q);

第2章线性表2.双向链表(DoubleLinkedList)类型描述typedefstructDuLNode{ElemTypestructDuLNodestructDuLNodedata;*prior;*next;}DuLNode, *DuLinkList;

第2章线性表双向循环链表p-next-prior=p-prior-next;p

第2章线性表①s-prior=p-prior;②p-prior-next=s;③s-next=p; ④p-prior=s;双向链表的前(后)插操作q①s-next=q-next;③s-prior=q;②q-next-prior=s;④q-next=s;③④②①

第2章线性表双向链表的删除操作①p-prior-next=p-next;②p-next-prior=p-prior;

第2章线性表删除*p的直接后继结点的语句序列q=p-next;p-next=p-next-next;p-next-prior=p;free(q);删除*p的直接前驱结点的语句序列q=p-prior;p-prior=p-prior-prior;p-prior-next=p;free(q);

第2章线性表3.从实际应用出发定义单链表结点类型typedefstructLNode{ElemTypedata;structLNode*next;}*Link,*Position;链表类型typedefstruct{Link head,tail;int len;}LinkList;LinkListL;//创建一个空表L.head=L.tail=newLNode;L.head-next=NULL;L.len=0;

第2章线性表4.顺序表和链表的比较基于空间的考虑存储密度=元素本身所占的存储量/实际分配的存储总量基于时间的考虑顺序表：随机存取结构，O(1)。链表：顺序存取结构，O(n)。基于语言的考虑

第2章线性表2.4 一元多项式的表示及相加用一个线性表P来表示：假设mn，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)，也可以用线性表R来表示：

第2章线性表A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8

第2章线性表A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8多项式相加得到的多项式和

第2章线性表练习1：某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用哪种存储方式最节省时间A单链表C双链表B仅有头指针的单循环链表D仅有尾指针的单循环链表

第2章线性表练习2: 2.38设有一个双向循环链表，每个结点中除有pre,data和next三个域外，还增设一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L,x)的操作后，被访问的结点的频度域freq的值增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以使被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate(L,x)操作的算法。

第2章线性表DuLinkList Locate(DuLinkListL,ElemTypex）typedefstructDuLNode{ElemTypeintstructDuLNodestructDuLNodedata;freq;*prior;*next;}DuLNode, *DuLinkList;5

第2章线性表DuLinkList Locate(DuLinkListL,ElemTypex）{p=L-next;while(p-data!=xp!=L)p=p-next;if(p==L) returnNULL;//没找到p-freq++; s=p-pre;while(s-freqp-freq)s=s-