第2章线性表第3节

会计学1第2章线性表第3节循环链表的优点：假设有两个链表，要想将这两个链表连接起来，若是单链表需要找到前一个链表的最后一个结点，时间复杂度为O(n)，而对指向尾结点的单循环链表而言，只需要改变一个指针就可以了，时间复杂度为O（1）合并链表la,lb的基本操作为：(1)la,lb为单链表（带头结点）

p=la->next；

while(p->next!=NULL)p=p->next;p->next=lb->next(合并后以la为头指针）（2）la,lb为指向尾结点的单循环链表（带头结点）

p=la->next;la->next=lb->next->next;lb->next=p;第1页/共20页

2.双向链表（DoublyLinkedList)typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}DuLNode,*DuLinkList;对指向双向链表任一结点的指针d，有下面的关系：d->next->prior=d->prior->next=d即当前结点后继的前趋是自身，当前结点前趋的后继也是自身定义：每个结点中有两个指针域，其一指向直接后继，另一指向直接前趋。

问题：执行前插操作或删除操作时，如何操作？第2页/共20页双向链表的操作特点：“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。双向链表的优点：可以克服单链表的单向性的缺点。查找前驱很方便。第3页/共20页ai-1aies->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;psai-1ai插入第4页/共20页ai-1删除aiai+1p->prior->next=p->next;p->next->prior=p->prior;ai-1第5页/共20页3.双向循环链表空表非空表a1a2…...an第6页/共20页构造一个完整的链表结构//节点结构

typedefstructLnode{Elemtypedata;structLnode*next;}*Link;//链表结构

typedefstruct{Linkhead,tail;intlen;}linklist;第7页/共20页

2.4有序表定义：若线性表中的数据元素之间可以相互比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai>=ai+1或ai<=ai+1.如何在顺序有序表中插入一个元素仍然保持有序第8页/共20页(12,23,34,45,56,67,78,89,98,45)例如:若

e=45,

则

q指向

若e=88,

则q指向表示值为88的元素应插入在该指针所指结点之后。

2.4有序表第9页/共20页1.顺序有序表中插入一个元素仍然保持有序voidOrdInsert(SqList*L,ElemTypex){i=L->length-1;//从最后一个元素起进行查找比较while(i>=0&&x<L->elem[i]){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->length++;}

2.4有序表第10页/共20页2.顺序有序表中删除值相同的多余元素voidpurge(SqList*L)//表必须不是空表{i=0;j=1;//设新的La表为只有一个元素表

while(j<L->length){if(L->elem[i]!=L->elem[j])L->elem[++i]=L->elem[j];j++;}L->length=i+1;}voidpurge(SqList*L)//表可以是空表也可以不是空表{i=-1;j=0;//设新的La表为只有一个元素表

while(j<L->length){if(j==0||L->elem[i]!=L->elem[j])L->elem[++i]=L->elem[j];j++;}L->length=i+1;}

2.4有序表第11页/共20页3.指向尾结点的循环有序链表求并集（带头结点），原两个表不存在la为交集表的头指针voidunion_OL(LinkList&La，LinkList&Lb){pa=La->next->next;pb=Lb->next->next;rc=La->next;while(pa!=La->next&&pb!=Lb->next){if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}elseif(pa->data>pb->data){rc->next=pb;rc=pb;pb=pb->next;}else{rc->next=pa;rc=pa;pa=pa->next;qb=pb;pb=pb->next;deleteqb;}}if(pb==Lb->next)rc->next=pa;else{rc->next=pb;pb=Lb->next;Lb->next=La->next;La=Lb;}deletepb;}

2.4有序表第12页/共20页3.指向尾结点的循环有序链表求并集（带头结点），原两个表不存在la为交集表的头指针（算法改进）voidunion_OL_1(LinkList&La，LinkList&Lb){La->next->data=MAX;Lb->next->data=MAX;pa=La->next->next;pb=Lb->next->next;rc=La->next;while(pa!=La->next||pb!=Lb->next){if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}elseif(pa->data>pb->data){rc->next=pb;rc=pb;pb=pb->next;}else{rc->next=pa;rc=pa;pa=pa->next;qb=pb;pb=pb->next;deleteqb;}}rc->next=La;//封闭链环

deleteLb->next;//释放B表的表头}

2.4有序表第13页/共20页4.有序单链表判断两个集合是否相等boolisequal_OL(LinkListA,LinkListB){pa=A->next;pb=B->next;while(pa&&pb&&pa->data==pb->data){pa=pa->next;pb=pb->next;}if(pa==NULL&&pb==NULL)returnTRUE;elsereturnFALSE;}时间复杂度为O(n)

2.4有序表第14页/共20页基于空间的考虑

在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域，从存储密度来讲，这是不经济的。所谓存储密度(StorageDensity),是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，存储密度越大，存储空间的利用率就越高。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。2.基于查找时间的考虑

顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链找才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。2．5顺序表和链表的综合比较第15页/共20页2.线性表有两种存储结构：顺序表，链表。问题：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？2．5顺序表和链表的综合比较答：（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。

（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O(1)。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

第16页/共20页第17页/共20页本课题目：实验二线性表的链式存储实验实验目的：掌握链表的定义及操作的C++语言实现方法实验重点：链表的操作的C++语言实现方法实验难点：链表的操作的C++语言实现方法实验内容：1建立头文件，包含数据类型定义和基本操作。2建立程序文件利用链表完成基本的删除，插入，查找等各种功能。3上机基本步骤：DEFINE宏定义INCLUDE语句类型定义编写实现各个功能的函数编写调用各个函数的主程序（main函数）2.3线性表的链式表示和实现上机实习第18页/共20页voidListInsert_L(LinkList&L,L