数据结构案例教程（CC++版）第2版 课件 第2章 线性表

第2章线性表2024/9/262导学问题1：简易的学生信息管理系统实现一个简易的学生信息管理系统，其中学生信息包括：学号、姓名、性别、年龄、专业等。要求系统能提供建立、查询、删除和增加学生信息等功能。2024/9/263导学问题2：简易的商品信息管理系统实现一个简易的商品信息管理系统，其中商品信息包括：商品代码、品名、单价、库存量等。要求系统能提供建立、查询、删除和增加商品信息等功能。2024/9/264程序设计的实质是对实际问题选择一种合适的数据存储结构，并设计基于此结构上的一批高效的处理算法。因此，首先需要分析实际问题中需要处理的数据对象的特点。问题分析2024/9/265学生信息表问题分析2024/9/266商品信息表问题分析2024/9/267考虑：数据元素之间的关系是什么？——数据如何表示？数据元素如何存储？数据元素如何处理？2024/9/2682.1知识学习2.1.1线性表的概念线性表是具有相同数据类型的n（n≥0）个数据元素组成的有限序列，通常记为L=(a1，a2，…，ai

1，ai，ai+1，…，an)a1a3a4ana22024/9/2692.1知识学习非空线性表的特性有且仅有一个表头结点a1，它没有前驱，而仅有一个后继a2；（2）有且仅有一个表尾结点an，它没有后继，而仅有一个前驱an－1；（3）其余的结点ai（2≤i≤n

1）都有且仅有一个前驱a

i－1和一个后继a

i+1。2.1.1线性表的概念2024/9/26102.1知识学习2.1.2线性表的顺序存储结构及基本操作2.1.2.1顺序结构342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素例：（34,23,67,43）2024/9/2611例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度2024/9/26122.1知识学习2.1.2线性表的顺序存储结构及基本操作2.1.2.1顺序结构数据元素为整型数的顺序表类型描述。constintMAXSIZE=100;//顺序表最大长度typedefstruct{ intdata[MAXSIZE];//存放数据元素的数组 intlength;//顺序表的长度}SeqList;2024/9/2613算法描述：voidInitList_Seq(SeqList&L){L.length=0;}初始化操作——创建空表

datalength02.1.2.2顺序表基本操作的实现2024/9/2614初始化操作——创建长度为n的顺序表2.1.2.2顺序表基本操作的实现顺序表

数组a351224334253512243342算法描述：voidCreatList_Seq(SeqList&L,inta[],intn){if(n>L.MAXSIZE){cout<<"参数超出顺序表容量"<<endl;exit(1);}

L.length=0;

for(inti=0;i<n;i++)

L.data[L.length++]=a[i];}2024/9/2615遍历顺序表2.1.2.2顺序表基本操作的实现voidShow_Seq(SeqList&L){ for(inti=0;i<L.length;i++) cout<<L.data[i]<<""; cout<<endl;}

算法描述：2024/9/2616求顺序表长度2.1.2.2顺序表基本操作的实现intListLength_Seq(SeqList&L){ returnL.length;}算法描述：2024/9/2617按值查找元素：535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系2.1.2.2顺序表基本操作的实现2024/9/2618intLocateElem_Seq(SeqListL,inte){for(inti=0;i<L.length;i++) if(L.data[i]==e) returni+1;

return0;}按值查找算法描述：时间复杂度？2.1.2.2顺序表基本操作的实现2024/9/2619插入操作2.1.2.2顺序表基本操作的实现插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,e

,ai,…,an)ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系2024/9/262033例：（35，12，24，42），在i=2的位置上插入33。表满：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序号）435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件2.1.2.2顺序表基本操作的实现2024/9/26212.1.2.2顺序表基本操作的实现插入操作算法描述①检查顺序表的存储空间是否已到最大值（被占满），若是，则停止插入，并给出“上溢”出错提示；否则，执行第②步。②检查插入位置i是否合法，若不合法，则停止插入，并给出“插入位置非法”出错提示；否则，执行第③步。③从最后一个元素向前直至第i个元素（下标为i

1）为止，将每一个元素均后移一个存储单元，将第i个元素的存储位置空出。④将新元素e写入到第i个元素处，即下标为i

1的位置。⑤将顺序表长度加1。2024/9/2622插入操作算法描述：2.1.2.2顺序表基本操作的实现voidListInsert_Seq(SeqList&L,inti,inte){ if(L.length>=MAXSIZE)

{cout<<"线性表已满"<<endl;exit(1);} if(i<1||i>L.length+1)

{cout<<"i值不合法"<<endl;exit(1);}

for(intj=L.length-1;j>=i-1;j--)

L.data[j+1]=L.data[j];

L.data[i-1]=e;

L.length++;}

2024/9/2623最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n+1次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。插入算法时间性能分析：å+-+=11)=1(niiinpå+-++=11)=1(11niinn2n=O(n)2.1.2.2顺序表基本操作的实现2024/9/2624删除操作：删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化2.1.2.2

顺序表基本操作的实现2024/9/2625例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出算法的描述；3.分析时间复杂度。535a1a2a3a401234422412334a51224422.1.2.2顺序表基本操作的实现2024/9/2626删除操作算法描述：2.1.2.2顺序表基本操作的实现voidListDelete_Seq(SeqList&L,inti,int&e){ if((i<1)||(i>L.length))

{cout<<"i值不合法"<<endl;exit(1);} e=L.data[i-1]; for(intj=i;j<L.length;j++)

L.data[j-1]=L.data[j];

L.length--;}2024/9/26272.1.2.3顺序表基本操作的优化（1）增强通用性（2）增强灵活性（3）增强适应性2024/9/26282.1.3线性表的链接存储及基本操作链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间连续不连续零散分布2024/9/26292.1.3.1链式存储结构例：(a1,a2

,a3,a4)的存储示意图存储特点：逻辑次序和物理次序不一定相同。元素之间的逻辑关系用指针表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26300200020803000325…………a10200a20325a30300a4∧结点数据域指针域单链表是由若干结点构成的；单链表的结点只有一个指针域。data：存储数据元素next：存储指向后继结点的地址datanext单链表的结点结构：数据域指针域2.1.3.1链式存储结构2024/9/2631typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext单链表的结点结构：如何申请一个结点？2.1.3.1链式存储结构2024/9/2632s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext单链表的结点结构：……sNode2.1.3.1链式存储结构2024/9/2633s=newNode;datanext……sNode如何引用数据元素？s->data;(*s).data;data如何引用指针域？nexts->next;2.1.3.1链式存储结构2024/9/26340200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。2.1.3.2单链表基本操作的实现2024/9/26350200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？2.1.3.2单链表基本操作的实现2024/9/2636头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。非空表heada1a2an∧空表head∧2.1.3.2单链表基本操作的实现2024/9/26372.1.3.2单链表基本操作的实现voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——创建空的单链表2024/9/26382.1.3.2单链表基本操作的实现voidCreateList_L(LinkList&L,ElemTypea[],intn){

LinkLists;

L=newNode;L->next=NULL;for(inti=n-1;i>=0;i--)

{s=newNode;s->data=a[i];

s->next=L->next;L->next=s;}}初始化——用数组a中的n个元素创建单链表2024/9/26392.1.3.2单链表基本操作的实现voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//输出结点数据域 p=p->next; } cout<<endl;}遍历单链表2024/9/26402.1.3.2单链表基本操作的实现intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//计数p=p->next;}returnk;}求单链表长度。2024/9/26412.1.3.2单链表基本操作的实现intLocateElem_L(LinkListL,ElemTypee){LinkListp=L->next;

intindex=1;while(p&&p->data!=e)

{p=p->next;

index++;}

if(p)returnindex;

elsereturn0;}按值查找。2024/9/2642插入操作：

voidListInsert_L(LinkListL,inti,ElemTypee)如何实现结点ai-1、e和ai之间逻辑关系的变化？pesheada1ai-1an∧ai算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;2.1.3.2单链表基本操作的实现2024/9/2643注意分析边界情况——表头、表尾。

heada1an∧aipes算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;pxs∧由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。

2.1.3.2单链表基本操作的实现2024/9/2644算法描述——伪代码1.工作指针p初始化；累加器j清零；

2.查找第i-1个结点并使工作指针p指向该结点；3.若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，

3.1生成一个元素值为e的新结点s；

3.2将新结点s插入到结点p之后；2.1.3.2单链表基本操作的实现2024/9/2645

voidListInsert_L(LinkListL,inti,ElemTypee){ LinkListp=L,s; intj=0; while(p&&j<i-1){ p=p->next; j++; }

算法描述

if(!p){cout<<"插入位置非法";exit(1);}else{

s=newNode; s->data=e;

s->next=p->next;

p->next=s; }}，基本语句？时间复杂度？2.1.3.2单链表基本操作的实现2024/9/2646删除操作接口：voidListDelete_L(LinkListL,inti);p如何实现结点ai-1和ai之间逻辑关系的变化？heada1ai-1ai+1ai算法描述：q=p->next;p->next=q->next;deleteq;q2.1.3.2单链表基本操作的实现2024/9/2647算法描述：q=p->next;p->next=q->next;deleteq;注意分析边界情况——表头、表尾。

pqpq表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在。p->next=NULLheada1ana2∧2.1.3.2单链表基本操作的实现2024/9/2648算法描述——伪代码1.工作指针p初始化；累加器j清零；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在或p不存在后继结点，则抛出位置异常；否则，否则删除结点p的后一个结点。2.1.3.2单链表基本操作的实现2024/9/2649voidListDelete_L(LinkListL,inti){ LinkListp=L,q; intj=0; while(p&&j<i-1){ p=p->next; j++;}算法描述

if(!p||!p->next){cout<<"删除位置非法";exit(1);}

else

{

q=p->next;

p->next=q->next;

deleteq;

}}2.1.3.2单链表基本操作的实现2024/9/2650将单链表中所有结点的存储空间释放。

单链表的销毁操作：heada1a2an∧aipq算法描述：q=p;p=p->next;deleteq;p注意：保证链表未处理的部分不断开

2.1.3.2单链表基本操作的实现2024/9/2651voidDestroyList_L(LinkList&L){

LinkListp=L,q; while(p) { q=p; p=p->next; deleteq; } L=NULL;}2.1.3.2单链表基本操作的实现2024/9/26522.2知识应用2024/9/26532.2知识应用2024/9/2654voidUnion(SeqList&La,SeqList&Lb){intLa_len=ListLength_Seq(La);//求线性表La的长度ElemTypee;

while(Lb.length!=0)//Lb表的元素尚未处理完

{

ListDelete_Seq(Lb,1,e);//从Lb中删除第一个数据元素赋给e

if(!LocateElem_Seq(La,e))//若La中不存在值和e相等的元素，ListInsert_Seq(La,++La_len,e);//则将它插入到La的最后

}}2.3知识拓展——顺序表的其他操作求集合的并集：2024/9/2655voidOrdInsert_Seq(SeqList&L,ElemTypex){

if(L.length>=MAXSIZE){cout<<"线性表已满"<<endl;exit(1);}

inti=0;while(L.data[i]<=x&&i<L.length)//查找插入位置i

i++;

for(intj=L.length-1;j>=i;j--)//元素后移

L.data[j+1]=L.data[j];

L.data[i]=x;//插入元素x

L.length++;//表长增1}2.3知识拓展——顺序表的其他操作有序表的插入：2024/9/2656voidInvertLinkedList(LinkList&L)//逆置头指针L所指链表{LinkLists,p=L->next;

L->next=NULL;//设逆置后的链表的初态为空表while(p){//p为待逆置链表的头指针s=p;p=p->next;//从p所指链表中删除第一个结点(s结点)s->next=L->next;L->next=s;//将s结点插入到逆置表的表头}}2.3

知识拓展——单链表的其他操作单链表的逆置：2024/9/2657voidMergeLinkList(LinkList&La,LinkList&Lb){LinkListpa=La->next;//pa指向La中当前考察的结点LinkListpb=Lb->next;//pb指向Lb中当前考察的结点LinkListpc=La;//pc指向Lc中当前的表尾结点while(pa!=NULL&&pb!=NULL)

{if