《数据结构》课件(完整版).pptx

《《数据结构》课件(完整版).pptx》由会员分享，可在线阅读，更多相关《《数据结构》课件(完整版).pptx（278页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、http:/数据结构v第1章 绪论vvvvvvvv第一章 绪论1.1 数据结构的概念1.2 算法1.1 数据结构的概念v计算机科学的重要研究内容之一就是用计算机进行数据表示和处理。这里面涉及到两个问题：数据的表示和数据的处理。v数据结构研究的主要内容是计算机所处理数据元素间的关系及其操作实现的算法，包括数据的逻辑结构、数据的存储结构以及数据的运算。1.1.1基本概念和术语基本概念和术语v数据数据(Data)是能被计算机识别、存储和加工处理的具有一定结构的符号的总称。v数据项数据项(Data Item)是具有独立意义的不可分割的最小数据单位。v数据元素数据元素(Data Element)是数据被

2、使用时的基本单位，在计算机程序中通常作为一个整体进行处理。v数据对象数据对象(Data object)是性质相同的数据元素的集合，是数据的一个子集。v 数据结构数据结构(Data Structure)由一个数据元素的集合和一系列基本运算组成。1.1.2逻辑结构逻辑结构v数据元素之间的逻辑关系称为数据的逻辑结构。v根据数据元素之间逻辑关系的不同特性，主要有下列三类基本结构。线性结构：结构中的数据元素之间存在一对一的关系。树形结构：结构中的数据元素之间存在一对多的关系。图状结构：结构中的数据元素之间存在多对多的关系。v如下图所示：1.1.3 存储结构存储结构v数据结构在计算机中的表示称为数据的存储

3、结构，也称为物理结构。基本的存储结构有两种：顺序存储结构和链式存储结构。v顺序存储结构是把逻辑上相邻的元素存储在一组连续的存储单元中，其元素之间的逻辑关系由物理位置的相邻关系表示。v链式存储结构将每个数据元素单独存放，称为一个结点，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放下一个结点的存储地址。1.1.4 抽象数据类型抽象数据类型 v抽象数据类型抽象数据类型（Abstract Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。v抽象数据类型可用以下三元组表示：Abstract_Data_Type=(D，R，P)其中：D是数

4、据元素的有限集，R是D上的关系的有限集，P是对D的基本运算集。返回本章目录1.2 算法1.2.1 算法的描述算法的描述v三种方式：非形式化方式。半形式化方式。形式化方式。1.2.2 算法设计的要求算法设计的要求 正确性。高效率。低存储量需求。v算法算法（Algorithm）是对特定问题求解步骤的一种描述。1.2.3 算法分析算法分析v算法的分析主要包括两个方面：算法的时间复杂度分析和空间复杂度分析。v一个算法是由控制结构和问题的基本操作构成的，因此，一个算法的“运行工作量”就可以用该基本操作的重复次数来表示。v一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：

5、T(n)=O(f(n)vT(n)称做算法的渐近时间复杂度，简称时间复杂度时间复杂度（Time Complexity）。v算法的时间复杂度常见的有：v常量阶O(1)、线性阶O(n)、平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。v不同数量级时间复杂度的性状如下图所示。【例1】起泡排序的算法描述如下，分析其时间复杂度。v void bubble-sort(int a，int n)v v int i,j,change,temp;v for(i=n-1;change=1;i1&change;-i)v v change=0;vvfor(j=0;jaj+1)v temp=

6、aj;v aj=aj+1;v aj+1=temp;v change=1;v v /bubble-sort解：解：在上述起泡排序算法中，问题的基本操作是“交换序列中相邻两个元素”，初始序列的状态不同，该基本操作的重复次数也有很大不同：最好情况：当初始序列为自小至大有序时，基本操作的重复次数为0，时间复杂度为O(1)；最坏情况：当初始序列为自大至小有序时，基本操作的重复次数为：1+2+3+n-1=n(n-1)/2 时间复杂度为:O(n2)平均情况：假设初始序列可能出现的排列情况（共n!种）的概率相等，则时间复杂度为O(n2)。通常，时间复杂度的评价指标可以分为以下三种：v最好时间复杂度：在最好情况

7、下执行一个算法所需要的时间。v最坏时间复杂度：在最坏情况下执行一个算法所需要的时间。v平均时间复杂度：在平均情况下执行一个算法所需要的时间。v算法的空间复杂度空间复杂度（Space Complexity）是指执行算法过程中所使用的额外存储空间的开销。不包括算法程序代码和所处理的数据本身所占用的空间部分。通常，额外空间与问题的规模有关，类似于算法的时间复杂度，算法的空间复杂度记作：S(n)=O(f(n)其中n为问题的规模(或大小)。v数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括数据的逻辑结构、数据的存储结构以及数据的运算。v数据元素之间的逻辑关系称为数据的逻辑结构。主要

8、有线性结构、树形结构和图状结构。v数据结构在计算机中的表示称为数据的存储结构。基本的存储结构有顺序存储结构和链式存储结构两种。v算法是对特定问题求解步骤的一种描述。算法的设计既要保证正确性，同时也必须考虑算法的效率和对存储量的需求。1.简述下列术语：数据、数据元素、数据对象、数据结构。2.什么叫数据的逻辑结构？主要有哪几种？3.什么叫数据的存储结构？基本的存储结构有哪几种？4.试述顺序存储结构和链式存储结构的区别。5.算法的时间复杂度和空间复杂度分别是什么？6.试写一算法，将3个整数a、b和c按从小到大的次序输出。结束第二章 线性表2.1 线性表的抽象数据类型 2.2 线性表的顺序存储结构 2

9、.3 线性表的链式存储结构 2.1 线性表的抽象数据类型v一个线性表线性表(Linear List)是由n(n0)个数据元素(结点)组成的有限序列。v数据元素可以是一个字符、一个数或一个记录，也可以是更复杂的信息。v 线性表一：26个英文字母组成的字母表（A，B，C，Z）。表中的数据元素是单个字母字符。v线性表二：某学生五门课的成绩列表（76，87，88，80，92）。表中的数据元素是整数。v线性表三：某班级学生信息表（如下表所示）。表中的数据元素是一个记录，包括姓名、学号、性别和年龄4个数据项。线性表中的元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属同一数据对象。v 一个线

10、性表可记为：（a1,a2,ai-1,ai,ai+1,an），n 0 其中，n为表的长度，当n=0时，称为空表。称i为ai在线性表中的位序。v表中ai-1领先于ai，称ai-1是ai的直接前驱，ai+1是ai的直接后继。v线性表的抽象数据类型定义（参见教材）返回本章目录2.2 线性表的顺序存储结构 v线性表的顺序存储是指在内存中用地址连续的一块存储空间依次存放线性表的数据元素，用这种存储形式存储的线性表称其为顺序表顺序表。v假设每个数据元素占d个存储单元，且将ai的存储地址表示为Loc(ai)，则有如下关系：Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是线性表的第一个数据元素a

11、1的存储地址，通常称作线性表的基地址。v顺序表的存储结构如下图所示，其中b为线性表的基地址。2.2.1 顺序表的类型定义顺序表的类型定义#define MAXSIZE 100 /顺序表的容量 typedef struct ElemType dataMAXSIZE;/存放顺序表的元素 int len;/顺序表的实际长度 SqList;MAXSIZE为顺序表的容量，表示线性表实际可能达到的最大长度。len表示顺序表当前的长度。2.2.2 线性表基本运算在顺序表上的实现线性表基本运算在顺序表上的实现vC语言中数组的下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.data

12、i-1。1.初始化线性表运算初始化线性表运算void InitList(SqList&sq)sq.len=0;2.求线性表长度运算求线性表长度运算int ListLength(SqList sq)return(sq.len);3.求线性表中第求线性表中第i个元素运算个元素运算ElemType GetElem(SqList sq,int i)if(isq.len)/i 值不合法 return 0;else return(sq.datai-1);4.按值查找运算按值查找运算int LocateElem(SqList sq,ElemType e)int i=0;while(i=sq.len)retu

13、rn 0;else return i+1;5.插入元素运算插入元素运算int ListInsert(SqList&sq,int i,ElemType e)int j;if(isq.len+1)return 0;/i 值不合法 for(j=sq.len;j=i;j-)/插入位置及之后的元素右移 sq.dataj=sq.dataj-1;sq.datai-1=e;/插入e sq.len+;/表长增1 return 1;6.删除元素运算删除元素运算 int ListDelete(SqList&sq,int i)int j;if(isq.len)return 0;/i 值不合法 for(j=i;jsq.

14、len;j+)/被删除元素之后的元素左移 sq.dataj-1=sq.dataj;sq.len-;/表长减1 return 1;2.2.3 顺序实现的算法分析顺序实现的算法分析1.插入插入v假设pi是在第i个位置插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为：pi=1/(n+1)插入算法的平均时间复杂度为O(n)。2.删除删除v假设qi是在第i个位置删除一个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为：qi=1/n删除算法的平均时间复杂度为O(n)。2.2.4 顺序表的应用举例顺序表的应用举例v【例1】编写一算法，从顺序表中删除自第

15、i个元素开始的k个元素。v算法思路：为保持顺序表的逻辑特性，需将i+k n位置的所有元素依次前移k个位置。算法如下：int deleteK(Sqlist&sq,int i,int k)if(i1|ksq.len)return 0;for(j=i+k-1;j=sq.len-1;j+)sq.dataj-k=sq.dataj;sq.len-=k;return 1;/deleteK【例2】巳知有两个按元素值递增有序的顺序表La和Lb，设计一个算法将表La和表Lb的全部元素归并为一个按元素值递增有序的顺序表Lc。v算法思路：用i扫描顺序表La，用j扫描顺序表Lb。当表La和表Lb都未扫描完时，比较两者的

16、当前元素，将较小者插入表Lc的表尾，若两者的当前元素相等，则将这两个元素依次插入表Lc的表尾。最后，将尚为扫描完的顺序表的余下部分元素依次插入表Lc的表尾。算法如下：v void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)int i=0,j=0,k=0;while(i La.len&jLb.len)/表La和表Lb都未扫描完时 if(La.datai Lb.data j)Lc.data k=Lb.data j;j+;k+;else Lc.data k=La.data i;i+;k+;Lc.data k=Lb.data j;j+;k+;while(iL

17、a.len)Lc.data k=La.data i;i+;k+;while(jnext=NULL;（2 2）求线性表长度）求线性表长度 int ListLength(LinkList h)int i=1;LNode*p=h-next;while(p-next!=NULL)/当p指向最后一个数据结点时，循环停止 p=p-next;i+;/指针p沿着next域移动一次，i值增1 return i;（3）求线性表中第）求线性表中第i个元素个元素 LNode*GetElem(LinkList h,int i)int j=1;LNode*p=h-next;if(i ListLength(h)return

18、 NULL;/i值不合法 while(jnext;j+;return p;/返回第i个结点的指针 本算法的时间复杂度为O(n)。（4）按值查找）按值查找 LNode*LocateElem(LinkList h,ElemType e)LNode*p=h-next;while(p!=NULL&p-data!=e)/从第1个结点开始，查找data域为e的结点 p=p-next;return p;（5）插入结点）插入结点 int ListInsert(LinkList&h,ElemType e,int i)int j=0;LNode*p=h,*s;if(i ListLength(h)+1)return

19、 0;/i值不合法 while(jnext;j+;/从头结点开始，查找第i-1个结点 s=(LNode*)malloc(sizeof(LNode);/创建新结点 s-data=e;s-next=p-next;p-next=s;/插入链表中 return 1;（6）删除结点）删除结点 int ListDelete(LinkList&h,int i)int j=0;LNode*p=h,*q;if(i ListLength(h)return 0;/i值不合法 while(jnext;j+;/从头结点开始，查找第i-1个结点 q=p-next;/删除并释放结点 p-next=q-next;free(q

20、);return 1;（7）输出元素值）输出元素值 void ListOutput(LinkList h)LNode *p=h-next;while (p!=NULL)printf(“%5d”,p-data);/输出结点的data域 p=p-next;2.建立单链表建立单链表 （1）头插法建表头插法建表 算法思路：从一个空表开始，读取数据，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，如此重复，直到读入结束标志为止。v算法如下：void CreateListF(LinkList&h,ElemType a,int n)LNode*s;int i;h=(LNo

21、de*)malloc(sizeof(LNode);/创建头结点 h-next=NULL;for(i=0;idata=ai;s-next=h-next;/将新结点插入到头结点之后 h-next=s;/CreateListF（2)尾插法建表尾插法建表 算法思路：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。算法如下：void CreateListR(LinkList&h,ElemType a,int n)LNode *s,*r;int i;h=(LNode*)malloc(sizeof(LNode);/创建头结点 r=h;/r始终指向尾结点，开始时指向头结

22、点 for(i=0;idata=ai;r-next=s;r=s;/将新结点插入到尾结点之后 r-next=NULL;/将尾结点的next域置为空 /CreateListR头插法建表和尾插法建表算法的时间复杂度都是O(n)。3.单链表的应用举例单链表的应用举例【例1】设ha和hb分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的空间。表中允许有重复的数据。v算法思路：设立3个指针pa、pb和pc，其中pa和pb分别指向ha和hb表中当前待比较插入的结点，而pc指向hc表中当前最后一个结点。比较pa-dat

23、a和pb-data,将较小者插入hc的表尾，即链到pc所指结点之后。若pa-data和pb-data相等，则将两个结点均链到pc所指结点之后。如此反复，直到有一个表的元素已归并完（pa或pb为空）为止，再将另一个表的剩余段链接到pc所指结点之后。v具体算法：void MergeList_L(LinkList&ha,LinkList&hb,LinkList&hc)LNode*pa,*pb,*pc;pa=ha-next;pb=hb-next;hc=pc=ha;/用ha的头结点作为hc的头结点，pc始终指向hc的表尾结点 while(pa&pb)if(pa-datadata)pc-next=pa;p

24、c=pa;pa=pa-next;else if(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next;else pc-next=pa;pc=pa;pa=pa-next;pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;/插入剩余段free(hb);/释放hb的头结点/MergeList_Lv本算法的基本操作是结点数据的比较和结点的链入，在最坏情况下，对每个结点均需进行上述操作，因此，若表ha和表hb的长度分别是m和n，则本算法的时间复杂度为O(m+n)。【例2】设计算法，根据输入的学生人数和成绩建立一个单链表，并累计其中成

25、绩不及格的人数。要求给出完整的程序。v解题思路：先定义单链表结点的类型，并根据题意将ElemType设为int型；然后设计一个算法create，用于输入学生人数和成绩，并建立相应的单链表；设计一个算法count，用于计算不及格人数；最后在主函数中调用实现上述两个算法的函数。v完整的程序参见教材 2.3.2 单循环链表单循环链表v循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。v 单循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是它们是否等于头指针。例如，求线性表的长度运算在单循环链表上的实现算法如下：int ListLengt

26、h(LinkList h)int i=1;LNode*p=h-next;while(p-next!=h)/当p指向最后一个数据结点时，循环停止 p=p-next;i+;/指针p沿着next域移动一次，i值增1 return i;/ListLength(a)双向链表的结点结构 (b)空的双向循环链表(c)非空的双向循环链表2.3.3 双向链表双向链表在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。1.删除删除 int ListDelete_DuL(DuLinkList&Dh,int i)int j=0;DuLNode*p=Dh,*q;if(i ListLength_DuL(D

27、h)return 0;/i值不合法 while(jnext;j+;/从头结点开始，查找第i个结点 p-prior-next=p-next;/删除并释放结点 p-next-prior=p-prior;free(p);return 1;/ListDelete_DuL2.插入插入 int ListInsert_DuL(DuLinkList&Dh,ElemType e,int i)int j=0;LNode*p=Dh,*s;if(i ListLength_DuL(Dh)+1)return 0;/i值不合法 while(jnext;j+;/从头结点开始，查找第i个结点 s=(DuLNode*)mallo

28、c(sizeof(DuLNode);/创建新结点 s-data=e;s-prior=p-prior;p-prior-next=s;/插入链表中 s-next=p;p-prior=s;return 1;/ListInsert_DuLv线性表是一种典型的线性结构。线性表中的元素可以是各种各样的，但同一线性表中的元素必具有相同的特性。v顺序表是以“物理位置相邻”来表示线性表中数据元素之间的逻辑关系的，通常用数组来描述。v链表是通过每个结点的链域将线性表的各个结点按其逻辑次序链接在一起的。v单循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。双向链表的结点中有两个分别指向直接后继

29、和指向直接前驱的指针域，在双向链表中寻查结点的前驱和后继都很方便。1.对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的元素的平均个数为多少？2.设线性表A采用顺序存储且元素按值递增有序排列。试编一算法，将x插入到线性表的适当位置上，并保持线性表的有序性。分析算法的时间复杂度。3.设线性表A采用链式存储且元素按值递增有序排列。试编一算法，将x插入到线性表的适当位置上，并保持线性表的有序性。分析算法的时间复杂度。4.已知La是带头结点的单链表，编写一算法，从表La中删除自第i个元素起，共len个元素。5.分别画

30、出顺序表、单链表、双链表和单循环链表的结构图。结束第三章 栈3.1 栈的抽象数据类型 3.2 栈的顺序存储结构 3.3 栈的链式存储结构3.4 栈与递归的实现 3.1 栈的抽象数据类型v栈栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称允许进行插入、删除的一端为栈顶栈顶(Top)，另一端为栈底栈底(Bottom)。v栈的修改原则：后进先出（LIFO）v栈的抽象数据类型定义（参见教材）返回本章目录3.2 栈的顺序存储结构 v栈的顺序存储结构简称为顺序栈。顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时用一个变量top记录栈顶的位置，通常称此变量为栈顶指针。

31、3.2.1 顺序栈的类型定义顺序栈的类型定义#defineStackSize100/顺序栈的初始分配空间typedefstructElemTypedataStackSize;/保存栈中元素inttop;/栈顶指针SqStack;其中，StackSize是指顺序栈的初始分配空间，是栈的最大容量。数组data用于存储栈中元素，top为栈顶指针。v由于C语言中数组的下标约定从0开始，因此，用top=-1表示栈空。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。3.2.2 栈基本运算在顺序栈上的实现栈基本运算在顺序栈上的实现1.初始化栈运算初始化栈运算 void InitSta

32、ck(SqStack st)st.top=-1;2.进栈运算进栈运算 int Push(SqStack&st,ElemType e)if(st.top=StackSize-1)return 0;else st.top+;st.datast.top=e;return 1;3.出栈运算出栈运算 int Pop(SqStack&st,ElemType&e)if(st.top=-1)return 0;else e=st.datast.top;st.top-;return 1;4.取栈顶元素运算取栈顶元素运算 int GetTop(SqStack st,ElemType&e)if(st.top=-1)r

33、eturn 0;else e=st.datast.top;return 1;5.判断栈空运算判断栈空运算 int StackEmpty(SqStack st)if (st.top=-1)return 1;else return 0;3.2.3 顺序栈的应用举例顺序栈的应用举例【例1】设计一个算法，判断一个表达式中括号是否匹配。若匹配，则返回1；否则返回0。算法思路：算法思路：扫描表达式，当遇到左括号时，将其进栈，遇到右括号时，判断栈顶是否为相匹配的左括号。若不是，则退出扫描过程，返回0；否则栈顶元素出栈，直到扫描完整个表达式时，若栈为空，则返回1。具体算法参见教材【例2】编写一个算法，将非负的

34、十进制整数转换为其他进制的数输出，10及其以上的数字从A开始的字母表示。并给出完整的程序。v解题思路：先定义顺序栈的类型，并根据题意将ElemType设为char型；然后设计一个算法trans来完成数制的转换；最后在主函数中调用实现转换算法的函数。v算法trans的思路：先用“除基取余”法求得从低位到高位的值，同时采用顺序栈暂时存放每次得到的数，当商为0时，再从栈顶到栈底输出从高位到低位的数字。v完整的程序参见教材返回本章目录3.3 栈的链式存储结构v栈的链式存储结构称为链栈，它是运算是受限的单链表，即插入和删除操作仅限制在表头位置上进行。3.3.1链栈的类型定义链栈的类型定义 typedef

35、 struct stnode ElemType data;struct stnode *next;StNode,*LinkStack;3.3.2 栈基本运算在链栈上的实现栈基本运算在链栈上的实现1.初始化栈运算初始化栈运算 void InitStack(LinkStack&ls)ls=NULL;2.进栈运算进栈运算 void Push(LinkStack&ls,ElemType x)StNode*p;p=(StNode*)malloc(sizeof(StNode);p-data=x;p-next=ls;ls=p;3.出栈运算出栈运算 int Pop(LinkStack&ls,ElemType&

36、x)StNode*p;if(ls=NULL)return 0;else p=ls;x=p-data;ls=p-next;free(p);return 1;4.取栈顶元素运算取栈顶元素运算 int GetTop(LinkStack ls,ElemType&x)if(ls=NULL)return 0;else x=ls-data;return 1;5.判断栈空运算判断栈空运算 int StackEmpty(LinkStack ls)if(ls=NULL)return 1;else return 0;v3.3.3 链栈的应用举例链栈的应用举例v【例3】回文指的是一个字符串从前面读和从后面读都一样，编

37、写一个算法判断一个字符串是否为回文。并给出完整的程序。v解题思路：先定义链栈的类型，并根据题意将ElemType设为char型；然后设计一个算法huiwei来完成判断；最后在主函数中调用实现判断算法的函数。v算法huiwei的思路：先将字符串从头到尾的各个字符依次放入一个链栈中；然后依次取栈顶到栈底的各个字符与字符串从头到尾的各个字符比较，如果两者不同，则表明该字符串不是回文，若相同，则继续比较；如果直到比较完毕相互之间都相匹配，则表明该字符串是回文。v完整的程序参见教材 返回本章目录3.4 栈与递归的实现v栈的一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接

38、地调用自己的函数，称做递归函数。【例4】阶乘函数。1 若n=0 Fact(n)=n*Fact(n-1)若n0以求3！为例，完整的程序如下：#include stdio.hvoid main()int result,n;n=3;result=fact(n);printf(“3!=%dn”,result);intfact(intn)1intf;2if(n=0)/递归终止条件3f=1;4else5f=n*fact(n-1);6returnf;v递归是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”

39、都可以直接解决，此时递归终止，逐层返回。v计算fac(3)的过程如 下：v递归调用的特点是：主调函数和被调函数是同一个函数，因此，在一个递归函数的运行过程中，一个和每次调用相关的重要概念是递归函数运行的“层次”。v为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实际参数、所有的局部变量以及上一层的返回地址。v每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录。v栈是一种操作受限的线性表，即只允许在表尾进行插入和删除操作。栈的结构特点是后进先出，在许多软件系

40、统中都会用到这种结构。v栈也有顺序存储结构和链式存储结构。栈的顺序存储结构称为顺序栈，主要通过改变栈顶指针来实现各种操作；栈的链式存储结构称为链栈，其各种操作的实现类似于单链表。1.栈有什么特点？什么情况下用到栈？2.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是哪个？（1）ABCD（2）BDCBA（3）ACDB（4）DABC3.若元素进栈顺序为1234，为了得到1342的出栈顺序，试给出相应的操作序列。4.链栈中为何不设头结点？5.写一个算法，借助于栈将一个单链表逆置。结束第四章 队列4.1 队列的抽象数据类型 4.2 队列的顺序存储结构 4.3 队列的链式存储结构

41、4.1 队列的抽象数据类型v队列队列(Queue)是限制在表的一端进行插入，而在表的另一端进行删除的线性表，通常称允许进行插入的一端为队尾队尾(Rear)，允许进行删除的一端为对头对头(Front)。v队列的修改原则：先进先出（FIFO）v队列的抽象数据类型定义（参见教材）返回本章目录4.2 队列的顺序存储结构 v在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放自队头到队尾的数据元素之外，还需附设两个变量front和rear分别指示队头元素和队尾元素的位置，这两个变量分别称为“队头指针”和“队尾指针”。v通常约定：初始化队列时，令front=rear=0，每当有新元素入队列时，队尾

42、指针增1；每当删除队头元素时，队头指针增1。因此，在非空队列中，队头指针始终指向队头元素的当前位置，而队尾指针始终指向队尾元素当前位置的下一个位置。v“假溢出”现象：队列的实际可用空间未占满，但不能再进行入队列操作了。v解决假溢出的方法之一：将队列的数据区看成首尾相接的循环结构，形成一个环形的空间，称之为循环队列。4.2.1 循环队列的类型定义循环队列的类型定义#define QueueSize 100 /循环队列的初始分配空间 typedef struct ElemType dataQueueSize;/保存队列中元素 int front;/队头指针 int rear;/队尾指针 SqQue

43、ue;v其中，QueueSize是指循环队列的初始分配空间，是循环队列的最大容量。数组data用于存储队列中的元素，front和rear分别为“队头指针”和“队尾指针”。v在循环队列Q中：队头指针增1：Q.front=(Q.front+1)%QueueSize 队尾指针增1：Q.rear=(Q.rear+1)%QueueSize4.2.2 队列基本运算在循环队列上的实现队列基本运算在循环队列上的实现1.初始化队列运算初始化队列运算 void InitQueue(SqQueue&qu)qu.rear=qu.front=0;2.入队列运算入队列运算 int EnQueue(SqQueue&qu,E

44、lemType e)if(qu.rear+1)%QueueSize=qu.front)return 0;qu.dataqu.rear=e;qu.rear=(qu.rear+1)%QueueSize;return 1;3.出队列运算出队列运算 int DeQueue(SqQueue&qu,ElemType&e)if(qu.rear=qu.front)return 0;e=qu.dataqu.front;qu.front=(qu.front+1)%QueueSize;return 1;4.取队头元素运算取队头元素运算 int GetHead(SqQueue qu,ElemType&e)if(qu.

45、rear=qu.front)return 0;e=qu.dataqu.front;return 1;5.判断队列空运算判断队列空运算 int QueueEmpty(SqQueue qu)if(qu.rear=qu.front)return 0;else return 1;4.2.3 循环队列的应用举例循环队列的应用举例【例1】设从键盘输入一整数序列a1,a2,an，试编程实现：当ai0时，ai进队；当ainext=NULL;2.入队列运算入队列运算 void EnQueue(LinkQueue&lq,ElemType e)p=(QueuePtr)malloc(sizeof(QNode);p-d

46、ata=e;p-next=NULL;lq.rear-next=p;lq.rear=p;3.出队列运算出队列运算 int DeQueue(LinkQueue&lq,ElemType&e)if(lq.rear=lq.front)return 0;p=lq.front-next;e=p-data;lq.front-next=p-next;if(lq.rear=p)lq.rear=lq.front;free(p);return 1;4.取队头元素运算取队头元素运算 int GetHead(LinkQueue&lq,ElemType&e)if(lq.rear=lq.front)return 0;p=lq

47、.front-next;e=p-data;return 1;5.判断队列空运算判断队列空运算 int QueueEmpty(LinkQueue lq)if(lq.rear=lq.front)return 0;else return 1;4.3.3 链队列的应用举例链队列的应用举例【例2】编写一个程序，反映病人到医院看病、排队看医生的情况。在病人排队过程中，主要发生两件事：（1）病人到达诊室，将病历交给护士，排队候诊；（2）护士从排好队的病历中取出下一位病人的病历，该病人进入诊室就诊。要求程序采用菜单方式，其选项及功能说明如下：（1）排队：输入排队病人的病历号，加入到病人排队队列中；（2）就诊：

48、病人排队队列中最前面的病人就诊，并将其从队列中删除；（3）查看排队：从队首到队尾列出所有的排队病人的病历号；（4）下班：退出运行。v解题思路：先定义链队列的类型，并根据题意将ElemType设为char型；在程序中根据功能要求进行插入、删除和输出操作，并使用switch语句实现菜单的选择。v完整的程序参见教材。v队列也是一种操作受限的线性表。它只允许在表尾进行插入而在表头进行删除操作。队列的结构特点是先进先出，在许多实际问题的解决中和系统软件的设计中，都会用到队列。v队列也有顺序存储结构和链式存储结构。为了解决假溢出的问题，通常将队列的顺序存储结构数据区看成首尾相接的循环结构，形成一个环形的空

49、间，称之为循环队列。队列的链式存储结构称为链队列，是一个同时带有首指针和尾指针的单链表，其各种操作的实现也类似于单链表。1.循环队列有什么优点？如何判断它的空和满？2.对于一个具有Qsize个单元的循环队列，写出求队列中元素个数的公式。3.假设以一维数组sqm存储循环队列的元素，同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的入队列和出队列的算法。4.假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向队尾元素结点（注意不设头指针），试写出相应的初始化、入队列和出队列的算法。结束第五章 数组和稀疏矩阵5

50、.1数组的概念与表示 5.2 稀疏矩阵 5.1数组的概念与表示 v数组可以看作线性表的推广，或者说是线性表的嵌套。5.1.1 数组的概念数组的概念v数组是有序排列的相同类型的数据元素的集合。v数组具有如下两个特征：（1）数组中的元素是有序的。数组中的元素可以用数组名和下标指定，下标指出了该元素在数组中的顺序。（2）数组的元素是相同类型的。数组中存储的所有元素必须是同一种数据类型，而不能是多种数据类型的混合。v对数组的操作一般只有两类：（1）获得特定位置的元素值；（2）修改特定位置的元素值。v数组的抽象数据类型（参见教材）5.1.2 数组的顺序表示数组的顺序表示对于多维数组，数组元素在一维结构的