数据结构案例教程（CC++版）第2版 课件全套 陈波 第1-9章 绪论、线性表-排序

2024/9/261数据结构案例教程2024/9/262导学问题1问题中的数据在计算机中如何组织？（1-1）计算某位同学高等数学、英语及计算机导论三门课程的总分。（1-2）已知一个班级20名学生的高等数学成绩，求全班该门课的平均分。（1-3）已知一个班级20名学生的高等数学、英语及计算机导论课程的成绩，计算每位同学的总分以及全班三门课程各自的均分。2024/9/263导学问题1问题中的数据在计算机中如何组织？（1-4）在问题1-3的基础上，列出全班成绩的排名（列出学号、姓名及分数），如表1-1所示。2024/9/264导学问题1问题中的数据在计算机中如何组织？（1-5）假设一个U盘中有3个文件夹，每个文件夹中又有若干文件，如图1-1所示。请设计一种文件信息存储方法，当输入某个文件名称后，显示该文件在U盘中的存储路径，若U盘中无该文件，则显示“文件未找到”。2024/9/265导学问题1问题中的数据在计算机中如何组织？（1-6）某城市中5个地标建筑间有多条道路相通，每条道路长度不同，如图1-2所示。设计一个道路查询系统，能让游客查询从任一个地标建筑到另一个地标建筑之间的最短路径。2024/9/266导学问题1的分析计算机处理的对象由数值发展到非数值数据，而且处理的数据量也越来越大。在程序设计时面对这样的数据，需要解决如何表示这些数据间的结构关系？如何在计算机中存储这些数据？计算机处理的不再只是加减乘除等数值计算，而是排序、信息可视化、求最短路径等较为复杂的非数值计算。在程序设计时，需要解决如何在问题数据上进行非数值计算等操作？以上这些问题正是数据结构这门课程研究的内容。2024/9/267导学问题2编程实现对输入的整数n计算sum=1!+2!+3!+4!+…+n!doublesum(intn){doubles=0;inti,j;doublep;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++) p*=j;s+=p;}returns;}2024/9/268导学问题2的分析可考虑将双重循环，进一步简化为单重循环：doublesum2(intn){doubles=0;inti;doublep=1;for(i=1;i<=n;i++){ p*=i; s+=p;}returns;}为什么用单重循环实现比用双重循环实现有效？2024/9/2691.1知识学习1.1.1数据结构课程的研究内容数据结构就是研究非数值计算问题中的数据以及它们之间的关系和操作算法的学科，具体主要包含3个方面的内容：数据的逻辑结构、数据的存储结构（物理结构）和数据的操作算法。2024/9/26101.1知识学习1.1.2数据的结构相关术语

数据

数据元素

数据对象数据结构的三个要素

数据结构涉及三个要素，分别是数据的逻辑结构、存储结构和操作算法2024/9/26111.1知识学习1.1.3算法与算法分析1.什么是算法2.算法的评价3.算法的描述方法2024/9/2612算法性能分析与度量算法的性能标准算法的事前估计算法的后期测试2024/9/2613算法性能分析与度量算法的性能标准正确性健壮性可读性高效率低存储空间算法的事前估计算法的后期测试2024/9/2614

算法性能分析与度量算法的性能标准算法的事前估计时间复杂度空间复杂度算法的后期测试2024/9/2615算法性能分析与度量算法的性能标准算法的事前估计时间复杂度空间复杂度存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间2024/9/26161.2知识应用导学问题1-4的数据结构2024/9/26171.2知识应用导学问题1-5的数据结构2024/9/26181.2知识应用导学问题1-6的数据结构2024/9/26191.2知识应用导学问题2的时间复杂度问题2的原始程序是一个双重循环，其中外循环体中的语句p=1;执行次数为n；外循环体中的语句s+=p;执行次数为n；内循环体中语句p*=j;的执行次数为：1+2+3+…+n=n(n+1)/2；因此该程序的基本语句执行次数是n2数量级，时间复杂度T(n)=O(n2)。改进后的程序是一个单重循环，循环体中的语句p*=j;和s+=p;分别执行了n次，因此该程序的基本语句执行次数是n数量级，时间复杂度T(n)=O(n)。2024/9/26201.3知识拓展算法时间复杂度的分析实例算法执行时间的测试2024/9/2621小结数据结构研究实际问题中涉及到的数据的逻辑组织。数据结构研究数据在计算机中如何存储、处理。数据结构研究的核心是数据的各种处理方法和技巧。第2章线性表2024/9/2623导学问题1：简易的学生信息管理系统实现一个简易的学生信息管理系统，其中学生信息包括：学号、姓名、性别、年龄、专业等。要求系统能提供建立、查询、删除和增加学生信息等功能。2024/9/2624导学问题2：简易的商品信息管理系统实现一个简易的商品信息管理系统，其中商品信息包括：商品代码、品名、单价、库存量等。要求系统能提供建立、查询、删除和增加商品信息等功能。2024/9/2625程序设计的实质是对实际问题选择一种合适的数据存储结构，并设计基于此结构上的一批高效的处理算法。因此，首先需要分析实际问题中需要处理的数据对象的特点。问题分析2024/9/2626学生信息表问题分析2024/9/2627商品信息表问题分析2024/9/2628考虑：数据元素之间的关系是什么？——数据如何表示？数据元素如何存储？数据元素如何处理？2024/9/26292.1知识学习2.1.1线性表的概念线性表是具有相同数据类型的n（n≥0）个数据元素组成的有限序列，通常记为L=(a1，a2，…，ai

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

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

i－1和一个后继a

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

datalength02.1.2.2顺序表基本操作的实现2024/9/2635初始化操作——创建长度为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/2636遍历顺序表2.1.2.2顺序表基本操作的实现voidShow_Seq(SeqList&L){ for(inti=0;i<L.length;i++) cout<<L.data[i]<<""; cout<<endl;}

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

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

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

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

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

1的位置。⑤将顺序表长度加1。2024/9/2643插入操作算法描述：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/2644最好情况（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/2645删除操作：删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化2.1.2.2

顺序表基本操作的实现2024/9/2646例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出算法的描述；3.分析时间复杂度。535a1a2a3a401234422412334a51224422.1.2.2顺序表基本操作的实现2024/9/2647删除操作算法描述：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/26482.1.2.3顺序表基本操作的优化（1）增强通用性（2）增强灵活性（3）增强适应性2024/9/26492.1.3线性表的链接存储及基本操作链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间连续不连续零散分布2024/9/26502.1.3.1链式存储结构例：(a1,a2

,a3,a4)的存储示意图存储特点：逻辑次序和物理次序不一定相同。元素之间的逻辑关系用指针表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26510200020803000325…………a10200a20325a30300a4∧结点数据域指针域单链表是由若干结点构成的；单链表的结点只有一个指针域。data：存储数据元素next：存储指向后继结点的地址datanext单链表的结点结构：数据域指针域2.1.3.1链式存储结构2024/9/2652typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext单链表的结点结构：如何申请一个结点？2.1.3.1链式存储结构2024/9/2653s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext单链表的结点结构：……sNode2.1.3.1链式存储结构2024/9/2654s=newNode;datanext……sNode如何引用数据元素？s->data;(*s).data;data如何引用指针域？nexts->next;2.1.3.1链式存储结构2024/9/26550200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。2.1.3.2单链表基本操作的实现2024/9/26560200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？2.1.3.2单链表基本操作的实现2024/9/2657头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。非空表heada1a2an∧空表head∧2.1.3.2单链表基本操作的实现2024/9/26582.1.3.2单链表基本操作的实现voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——创建空的单链表2024/9/26592.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/26602.1.3.2单链表基本操作的实现voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//输出结点数据域 p=p->next; } cout<<endl;}遍历单链表2024/9/26612.1.3.2单链表基本操作的实现intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//计数p=p->next;}returnk;}求单链表长度。2024/9/26622.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/2663插入操作：

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/2664注意分析边界情况——表头、表尾。

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

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

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

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

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

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/2667删除操作接口：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/2668算法描述：q=p->next;p->next=q->next;deleteq;注意分析边界情况——表头、表尾。

pqpq表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在。p->next=NULLheada1ana2∧2.1.3.2单链表基本操作的实现2024/9/2669算法描述——伪代码1.工作指针p初始化；累加器j清零；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在或p不存在后继结点，则抛出位置异常；否则，否则删除结点p的后一个结点。2.1.3.2单链表基本操作的实现2024/9/2670voidListDelete_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/2671将单链表中所有结点的存储空间释放。

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

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

LinkListp=L,q; while(p) { q=p; p=p->next; deleteq; } L=NULL;}2.1.3.2单链表基本操作的实现2024/9/26732.2知识应用2024/9/26742.2知识应用2024/9/2675voidUnion(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/2676voidOrdInsert_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/2677voidInvertLinkedList(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/2678voidMergeLinkList(LinkList&La,LinkList&Lb){LinkListpa=La->next;//pa指向La中当前考察的结点LinkListpb=Lb->next;//pb指向Lb中当前考察的结点LinkListpc=La;//pc指向Lc中当前的表尾结点while(pa!=NULL&&pb!=NULL)

{if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}else

{

pc->next=pb;pc=pb;pb=pb->next;}}if(pa)pc->next=pa;elsepc->next=pb;deleteLb;}2.3

知识拓展——单链表的其他操作合并有序单链表：2024/9/2679顺序表和单链表的比较存储分配方式比较顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。2024/9/2680顺序表和单链表的比较时间性能比较时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。按位查找：顺序表的时间为Ｏ(1)，是随机存取；单链表的时间为Ｏ(n)，是顺序存取。插入和删除：顺序表需移动表长一半的元素，时间为Ｏ(n)；单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。2024/9/2681顺序表和单链表的比较空间性能比较空间性能是指某种存储结构所占用的存储空间的大小。定义结点的存储密度：数据域占用的存储量整个结点占用的存储量存储密度＝2024/9/2682顺序表和单链表的比较空间性能比较结点的存储密度：顺序表中每个结点的存储密度为1（只存储数据元素），没有浪费空间；单链表的每个结点的存储密度<1（包括数据域和指针域），有指针的结构性开销。整体结构：顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。2024/9/2683顺序表和单链表的比较⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。⑵当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。第3章操作受限的线性表：栈和队列导学问题1：数制转换问题【问题描述】

已知十进制数n，试将其转换成对应的八进制数。【分析】以n=1269为例

计算过程中，取余数的顺序正好与计算产生余数的顺序相反的，因此可将每次产生的余数依次保存起来，转换结束后，再按保存的逆序取出余数打印即可。

显然，保存的余数应该具备“后进先出”的特点，可用栈作为数据结构。导学问题2：银行排队问题【问题描述】

请设计一个简单的模拟银行排队系统，要求程序具有三项菜单：1）取号。选择该菜单后，为客户产生一个排队号。2）叫号。选择该菜单后，显示可服务的客户排队号。3）退出系统。【分析】

银行排队问题属于典型的先来先服务，因此需要将产生的排队号存放在具有“先进先出”特性的数据结构中，队列结构可以满足要求。

3.1栈3.1.1知识学习栈：限定仅在表尾进行插入和删除操作的线性表。空栈：不含任何数据元素的栈。允许插入和删除的一端称为栈顶，另一端称为栈底。（a1,a2,……,an）栈顶栈底abc入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图3.1栈栈的操作特性：后进先出abc入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶3.1栈栈的示意图例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：3.1栈例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶情况2：3.1栈出栈序列：b栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？3.1栈如何改造数组实现栈的顺序存储？

012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。

top栈的顺序存储结构及基本操作出栈：top减1进栈：top加1栈空：top=-1

012345678a1topa2topa3top栈满：top=MaxSize-1栈的顺序存储及基本操作constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; inttop;}SeqStack;顺序栈的类型定义voidInitStack(SeqStack&S){S.top=-1;}顺序栈的实现——初始化voidPush(SeqStack&S,ElemTypex){if(S.top==MAXSIZE-1){cout<<"栈已满"<<endl;exit(1);}

S.top++;

S.data[S.top]=x;}顺序栈的实现——入栈ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"栈已空"<<endl;exit(1);}

ElemTypex=S.data[S.top];

S.top--; returnx;}顺序栈的实现——出栈ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"栈已空"<<endl;exit(1);}

returnS.data[S.top];}顺序栈的实现——取栈顶元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}顺序栈的实现——判断栈空boolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}顺序栈的实现——判断栈满heada1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈的链式存储及基本操作栈顶栈底链栈：栈的链接存储结构topanan-1a1∧两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底栈的链式存储及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;链栈的类型定义voidInitStack(LinkStack&S){ S=NULL;}链栈的实现——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

S=p;}Sanan-1a1∧xpS链栈的实现——入栈算法描述：ElemTypePop(LinkStack&S){

if(S==NULL)

{cout<<"栈已空";exit(1);}

ElemTypex=S->data;//暂存栈顶元素

LinkStackp=S;

S=S->next;//删除栈顶结点

deletep;

returnx;}Sanan-1a1∧Sp

链栈的实现——出栈ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"栈已空";exit(1);} returnS->data;}链栈的实现——取栈顶元素boolStackEmpty(LinkStack&S){ returnS==NULL;}链栈的实现——判断栈空voidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}链栈的实现——销毁顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。3.1.2知识应用——导学问题1voidconversion(intn){SeqStackS;InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!StackEmpty(S))cout<<Pop(S);cout<<endl;}3.1.3知识拓展——算术表达式求值1、中缀表达式直接求值为实现算符优先算法，可以使用两个工作栈：

1）运算符OPTR栈,用以寄存运算符；2）操作数OPND栈,用以寄存操作数或运算结果。算法步骤：参见教材3.1.3知识拓展——算术表达式求值2、利用后缀表达式求值

将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发生变化，同时需要去掉圆括号。因此设置一个栈OPTR用以存放操作符。。算法步骤：参见教材3.1.3知识拓展——栈和递归求阶乘的递归算法intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}3.1.3知识拓展——栈和递归递归函数的内部执行过程⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。3.1.3知识拓展——栈和递归哪些问题可以用递归解决大问题可以分解为小问题可以确定递归到何时终止3.2队列3.2.1知识学习队列的基本概念

队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。队尾队头a1a2a3入队出队队列的操作特性：先进先出constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; intrear;}SeqQueue;队列的顺序存储及基本操作（循环队列）（1）循环队列的初始化voidInitQueue(SeqQueue&Q){Q.front=Q.rear=0;}（2）循环队列的入队操作voidEnQueue(SeqQueue&Q,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {cout<<"队列已满"<<endl;exit(1);}Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x;

}队列的顺序存储及基本操作（循环队列）（3）循环队列的出队操作ElemTypeDeQueue(SeqQueue&Q){if(Q.front==Q.rear) {cout<<"队列已空"<<endl;exit(1);} Q.front=(Q.front+1)%MAXSIZE; ElemTypex=Q.data[Q.front];returnx;}队列的顺序存储及基本操作（循环队列）（4）判断循环队列是否为空的操作boolQueueEmpty(SeqQueue&Q){ returnQ.front==Q.rear;}（5）判断循环队列是否为满的操作boolQueueFull(SeqQueue&Q){ return(Q.rear+1)%MAXSIZE==Q.front;}队列的顺序存储及基本操作（循环队列）链队列：队列的链接存储结构队头指针即为链表的头指针heada1a2an∧如何改造单链表实现队列的链接存储？rearfront队列的链式存储及基本操作（链队列）非空链队列fronta1a2an∧rear空链队列front∧rear队列的链式存储及基本操作（链队列）typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstruct{ Node*front; Node*rear;}LinkQueue;队列的链式存储及基本操作（链队列）voidInitQueue(LinkQueue&Q){Q.front=Q.rear=newNode; Q.front->next=NULL;}front∧rear链队列的操作——初始化xpfronta1an∧rearrearfrontxp∧∧rearrear算法描述：p->next=NULL;rear->next=p;rear=p;有了头结点两种情况下的处理是一致的。链队列的操作——入队∧voidEnQueue(LinkQueue&Q,ElemTypex){

Node*p=newNode;//产生新结点p p->data=x; p->next=NULL; Q.rear->next=p;//将结点p插入到队尾 Q.rear=p; }链队列的操作——入队fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;链队列的操作——出队fronta1a2an∧rearp考虑边界情况：队列中只有一个元素？fronta1p∧rear∧rear仅1个元素的队列判断：if(rear==p)rear=front;如何判断边界情况？链队列的操作——出队ElemTypeDeQueue(LinkQueue&Q){

if(Q.front==Q.rear)

{cout<<"队列已空"<<endl;exit(1);} Node*p=Q.front->next; ElemTypex=p->data; Q.front->next=p->next; if(Q.rear==p)

Q.rear=Q.front;

deletep; returnx; }链队列的操作——出队boolQueueEmpty(LinkQueue&Q){ returnQ.front==Q.rear;}链队列的操作——判断队空voidDestroyListQueue(LinkQueue&Q){while(Q.front) { Q.rear=Q.front->next; deleteQ.front; Q.front=Q.rear; }}链队列的操作——销毁

银行排队其实就是队列的操作，取号对应的是入队操作，叫号对应的是出队操作。为了完成导学问题2，可首先创建一个队列，有客户选择“取号”功能时，产生一个排队序号，并将该序号加入队列中；当服务员选择“叫号”功能时，从队列头部取出一个排队序号即可。3.2.2知识应用——导学问题2的实现3.2.3知识拓展打印任务队列管理步骤如下：①创建队列并设置需打印任务的位置flag，初始化打印时间time；②依次将队头任务e出队，重置需打印任务位置flag，并将e与队列的最高优先级别max进行比较：

若e<max，则将任务e移至队尾，移动的任务为需要打印的任务，则重置需打印任务的位置flag；

若e>=max，打印时间time增1（表示该任务完成打印），若e为需要打印的任务，则执行步骤3）；③显示打印时间time。第4章元素受限的线性表：串导学问题——微信中的安全提醒微信（WeChat）是腾讯公司于2011年推出的一个为智能终端提供即时通讯服务的免费应用程序，人们通过微信可以进行便捷的交流。然而，微信中的诈骗信息也让人们深受其害。为了提醒微信用户免受欺骗，新版微信设置了安全提示功能，当与微信好友聊天中提及帐号、密码、财物等敏感信息时，微信会立即弹出安全提示，提醒大家注意，如图所示。请编写程序，模拟简单的微信安全提示功能。4.1知识学习4.1.1串的基本概念串：由零个或多个任意字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：""。非空串通常记为：

S=“a1a2…an”

其中：S是串名，双引号是定界符，双引号引起来的部分是串值，ai（1≤i≤n）是一个任意字符。4.1

知识学习4.1.1串的基本概念两个串相等：如果两个串的长度相等且对应字符都相等。子串：串中任意连续的字符组成的子序列称为该串。主串：包含子串的串。子串的第一个字符在主串中的序号称为子串的位置。4.1.2串的存储结构（1）用一个变量来表示串的长度。4.1知识学习如何表示串的长度？1.串的顺序存储结构（2）在串尾存储一个不会在串中出现的特殊字符作为串的终结符

。

4.1知识学习如何表示串的长度？4.1.2串的存储结构1.串的顺序存储结构（3）用数组的0号单元存放串的长度，串值从1号单元开始存放。

4.1知识学习如何表示串的长度？4.1.2串的存储结构1.串的顺序存储结构（1）非压缩形式（2）圧缩形式4.1知识学习4.1.2串的存储结构1.串的链式存储结构4.1知识学习串的基本操作算法串的复制strcpy(字符数组名1,字符数组名2)功能：把字符数组2中的字符串，连同字符串结束符'\0'，赋值到字符数组1中。串的连接strcat(字符数组名1,字符数组名2)功能：把字符数组2中的字符串连接到字符数组1中字符串的后面，并去掉字符数组1中的字符串后的字符串标志'\0'。串的比较strcmp(字符数组名1,字符数组名2)功能：将两个字符串从左至右逐个字符按照ASCII码值进行比较，直到出现不相等的字符或遇到‘\0’为止。如果所有字符都相等，则这两个字符串相等。如果出现了不相等的字符，以第一个不相等字符的比较结果为准。4.1知识学习串的简单模式匹配模式匹配：给定两个串s="s0s1

…sn-1"和t="t0t1

…tm-1"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。4.1知识学习BF模式匹配基本思想：从主串s中下标为0的字符开始，与模式串t中下标为0的字符比较，若相同，则继续逐个比较s和t中的后续字符；若不同，从主串s中下标为1的字符开始，与模式串t中下标为0的字符比较。以此类推，重复上述过程，若t中字符全部比完，则说明匹配成功；否则匹配失败。例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=2，j=2失败；i回溯到1，j回溯到0ijijij第

1趟abcac

4.1知识学习——BF模式匹配算法ababcabcacbabi=2，j=2失败；i回溯到1，j回溯到0ji第

1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbabi=1，j=0失败i回溯到2，j回溯到0第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbabi=1，j=0失败i回溯到2，j回溯到0第

2趟ijabcac

例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=6，j=4失败i回溯到3，j回溯到0第

3趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=6，j=4失败i回溯到3，j回溯到0第

3趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=3，j=0失败i回溯到4，j回溯到0第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=3，j=0失败i回溯到4，j回溯到0第

4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=4，j=0失败i回溯到5，j回溯到0第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=4，j=0失败i回溯到5，j回溯到0第

5趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法ababcabcacbababcac

i=10，j=5，T中全部字符都比较完毕，匹配成功。第

6趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.1知识学习——BF模式匹配算法4.1知识学习——BF模式匹配算法回溯位置j的确定，j=0回溯位置i的确定

i=i-j+1新i原i原j122210364430540intBF(char*s,char*t){ i=0;j=0; n=strlen(s);m=strlen(t); while(i<n&&j<m) { if(s[i]==t[j]) {i++;j++;} else {i=i-j+1;j=0; } } if(j>=m)returni-j;//匹配成功，返回

子串在

主串中首次出现的下标位置 elsereturn-1;//匹配不成功，返回-1}4.1知识学习——BF模式匹配算法4.1知识学习——BF模式匹配算法设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况：最好情况：每趟不成功的匹配都发生在第一对字符比较时：例如：s="aaaaabcd"t="bcd"设匹配成功发生在si处，则在前i趟比较中，匹配均不成功。每趟不成功的匹配都发生在第一对字符比较时，因此前面i趟匹配中共比较了i次，第i+1趟成功的匹配共比较了m次，所以总共比较了i+m次，所有匹配成功的可能共有n－m+1种，设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n－m+1)，平均比较的次数是因此最好情况下的时间复杂度是O(n+m)。4.1知识学习——BF模式匹配算法设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况：最坏情况：不成功的匹配都发生在串t的最后一个字符。例如：s="aaaaab"t="aaab“设匹配成功发生在si处，则在前面i趟匹配中共比较了i*m次，第i+1趟成功的匹配共比较了m次，所以总共比较了(i+1)*m次，因此平均比较的次数是：一般情况下，m<<n，因此最坏情况下的时间复杂度是O(nm)。4.2知识应用intmain(){chars[MaxSize],t[]="转账";intflag;

cout<<"请输入聊天信息：\n";cin>>s;flag=BF(s,t);if(flag!=-1)cout<<"***安全提示：如果聊天中提及财产，请一定先核实好友身份！***\n";

return0;}4.3知识拓展——KMP模式匹配算法为什么BF算法时间性能低？在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？i=2，j=2失败；

s1=t1;t0≠t1∴t0≠s1ababcabcacbabij第

1趟abcac

ababcabcacbab第

2趟abcac

4.3知识拓展——KMP模式匹配算法i=2，j=2失败；

s1=t1;t0≠t1∴t0≠s1ababcabcacbabij第

1趟abcac

ababcabcacbababcac

第

3趟4.3知识拓展——KMP模式匹配算法ababcabcacbababcac

第

3趟iji=6，j=4失败s3=t1;t0≠t1∴t0≠s3ababcabcacbababcac

第

4趟4.3知识拓展——KMP模式匹配算法ababcabcacbaba