数据结构与算法-教案（367页）.ppt

1、第0章 绪 论 教学目的：1.掌握数据结构的基本概念； 2.掌握抽象数据类型的概念和软件构造方法 3.了解算法的含义，掌握算法时间复杂度的计算 教学重点：1.数据结构的概念 2.抽象数据结构的软件构造方法 3.时间复杂度的计算 教学难点：算法和算法的时间复杂度 作业：1-11-31-11（前三道小题）,一.基本概念 数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述 *数据元素：表示一个事物的一组数据称为一个数据元素 *数据项：构成数据元素的数据称为该数据元素的数据项 抽象数据元素：没有实际含义的数据元素 抽象数据类型：没有确切定义的数据类型叫抽象数据类型

2、，用符号DataType来表示 数据的逻辑结构：即为数据元素之间的相互联系方式可分为线性结构、树结构和图结构,1.1 数据结构的基本概念,二 本门课程的主要内容,数据的存储结构：数据元素在计算机中的存储方式它的基本形式有两种：顺序存储结构，链式存储结构 数据的操作：对一种数据类型的数据进行的某种处理 数据的操作集合：对一种数据类型的数据所有的操作 数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构在讨论这些结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论,三. . 数据元素数据项举例 假设要描述学生的信息，看表1-1学生信息表,表中除第一行标题

3、行外，其他每一行为一个数据元素，每一列为一个数据项,三举 倒,关于数据元素、数据项的描述都可以使用某种高级程序设计语言来描述，本书采用C语言描述如上表学生信息可定义为如下结构体： typedef struct student char number8; char name10; char sex3; int age; student type,用C语言描述,有了上面的定义后，studenttype 就可看做与struct student 含义相同的标识符 1线性结构树结构图结构,结构与标识符,由图可见，线性结构除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素而树

4、结构是除根结点外每个元素只有一个前驱元素，可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素,1.把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置上如下图所示：,2。 顺序存储结构,0 1 2 -2 -1,使用指针把相互直接关联的结点链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上如下图示,3。链式存储结构,数据类型： 指一个类型和定义在这个类型上的操作集合. 例如，当说计算机中的整数数据类型时，就不仅指计算机所能表示的整数数值的集合，而且指能对这个整数类型进

5、行的+、-、*、和求模（）操作 抽象数据类型（Abstract Data Type缩写为ADT）：是指一个逻辑概念上的类型和这个类型上的操作集合 数据类型和抽象数据类型的不同之处在于：数据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不同的抽象数据类型,12 抽象数据类型和软件构造方法,13。算法和算法的时间复杂度（1）,1.3.1算法 算法是描述求解问题方法的操作步骤的集合它主要有三种形式：文字形式伪码形式和程序设计语言形式 例1-1设计一个把存储在数组A中的个抽象数据元素0，1，-1逆

6、置的算法，即要求逆置后的数组中数据元素序列为，1，0，并要求原数组中的数据元素值不能被改变 设计：这是一个算法设计问题该算法要求有一个表示元素个数的输入参数，一个表示原数组的输入参数和一个表示逆置后数组的输出参数, 算法设计如下： void Reverse( int n , DataType a , DataType b ) int i ; for ( i=0 ; in ; i+ ) bi= a n-1- i ; ,算法的时间复杂度（2）,该算法的实现方法如图1-3所示,图1-3例1-1算法实现方法图示,该算法的实现方法,设计一个把存储在数组A中的个抽象数据元素0，1，-1就地逆置的算法，即要

7、求逆置后数组中数据元素序列为，1，0，并要求原数组中的数据元素值被改变 设计：这是另一个算法设计问题该算法要求有一个表示元素个数的输入参数，一个表示原数组的输入参数和一个表示逆置后数组的输出参数由于要求原数组中的数据元素这被改变，所以输出参数必须与输入参数相同，因此，这两个参数应设计为同一个参数，其参数类型设计为输入输出混合型参数,例1-2,算法设计如下： void Reverse (int n , DataType a ) int i , m = n / 2; DataType temp ; for ( i = 0 ; i m ; i + + ) temp = a i ; a i = a n

8、 1 i ; a n 1 i = temp ; 该算法的实现方法如图14所示p20,算法设计,(1) 正确性能 (2) 可读性 (3) 健壮性 (4) 高时间效率 (5) 高空间效率,13.2 算法设计目标,. （1） 事后统计方法 （2） 事前分析方法 事前分析方法主要分析算法的时间效率与算法所处理的数据个数的函数关系 定义1-1T ( n )=O ( f ( n ) )当且仅当存在正常数c和n0对所有的n (n n0)满足T ( n ) c * f ( n ). 即：当算法的时间复杂度T ( n )与数据个数n无关系时，T ( n ) c 1，所以此时算法的时间复杂度T ( n )=O (

9、 1 )；当算法的时间复杂度T ( n )与数据个数n为线性关系时，所以此时算法的时间复杂度T ( n ) = O ( )；依次类推分析一个算法中基本语句执行次数与数据个数的函数关系，就可求出该算法的时间复杂度,13.3算法时间效率的度量,例1-3 设数组和在前边部分已赋值，求如下两个阶矩阵相乘运算算法的时间复杂度 for ( i = 0; i n ; i + + ) for ( j = 0 ; j n ; j + + ) c i j = 0 ;*基本语句1* for ( k = 0 ; k n ; k + + ) c i j = c i j + a i j b k j ; /*基本语句2*/

10、 ,举例说明,下面举例说明算法时间复杂度的分析方法：,解：设基本语句的执行次数为f( n )，有 f( n ) = c1 * n2 + c2 * n3 因T( n ) = f( n ) = c1 * n2 + c2 * n3= c * n3，其中c1,c2,c可为任意常数，所以该算法的时间复杂度为T( n ) = O( n3 ),例1-6,下边算法是在一个有个数据元素的数组中删除第个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度其中，数组下标为0-1 int Delete (int a ,int * n , int i) int j; f ( i= *n ) retur

11、n 0; /*删除位置错误，失败返回*/ ifor ( j = i+1;j *n; j +) aj-1=aj; /*顺次移位填补*/ ( * n )- -; /*数组元素个数减1*/ return ;/*删除成功返回*/ ,解：此算法的时间复杂度随删除数据的位置不同而不同当删除最后一个位置的数组元素时有in1，ji+1n，故不需要移位填补二循环次数为0，当删除第一个位置的数组元素时有i0，ji+11，需移位填补n1次而循环次数为 n1此时算法的时间复杂度应是删除数据位置等概率取值情况下的平均次数 设为删除第个位置上数据元素的概率，则有，设E为删除数组元素的平均次数，则有 E= 1/n 0n-1

12、(n-1-i)= 1/n (n-1)+(n-2)+2+1+0=1*/n 1 n(n-1)/2 =( n 1)/2 因T( n ) = E ( n 1 ) / 2 c * n，其中c为常数，所以该算法的等概率平均时间复杂度为 T(n)=0(n),算法的时间复杂度隋删除数据的位置不同而不同,（） (1) 各种符号均以英语单词命名，所有命名应见名知意 (2) 变量名字母均小写，若单词多于一个时，第二个单词首字母大写 (3) 自定义结构体名常量名和文件名均小写但所有单词的首字母大写可缩写 (4) 函数中的抽象数据类型参数用单字母大写，顺序表SeqList类型的参数L,1.4 算法书写规定,教学目的：1

13、.理解线性表抽象数据类型 2.掌握线性表的顺序表示和实现 3.掌握线性表的链式表示和实 4.掌握静态链表的概念 5.掌握顺序表和单链表的算法设计 教学重点：1.概念的理解 2.线性表的操作 3.算法设计方法 教学难点：线性表的概念，顺序表和链表的操作 作业：2-112-12,第二章 线性表,2.1.1线性表的定义 线性表是一种可以在任意位置进行插入和删除数据元素操作的由n (n0)个相同类型数据元素a0,a1,a2,an-1组成的线性结构 顺序存储结构存储数据元素具体是用数组存储，数据元素编号从0开始,2。1 。1 线性表抽象数据类别,. 线性表的抽象数据类型主要包括两个方面，即数据集合和该数

14、据集合上的操作集合 数据集合： 线线性表的数据集合可以表示为a0,a1,a2,an-1或a1,a2,an，每个数据据元素的数据类型为抽象数据元素类型DataType ,2.1.2 线性表抽象数据类型,操作集合.,（1）初始化 ListInitiate( L )：初始化线性表 L. （2）求当前数据元素个数(ListLength( L )：函数返回线性表L的当前数据元素个数 （3） 插入数据元素ListInsert( L, i, x )：在线性表L的第i个数据前插入数据元素x （4） 删除数据元素ListDelete( L, i, x )：删除线性表L的第i个数据元素，所删除的数据元素x由输出参

15、数带回 （5） 取数据元素ListGet ( L, i, x )：取线性表L的第i个数据元素，所取的数据元素x由输出参数带回,2。2线性的顺序表示和实现,线性表的抽象数据类型有两种存储结构：顺序存储结构；链式存储结构 顺序存储结构的线性表称作顺序表 2.2.1 顺序表的存储结构 数组有静态数组和动态数组两种静态数组存储空间的申请和释放由系统自动完成，动态数组存储空间的申请和释放由用户通过调用系统函数完成顺序表一般采用静态数组方法实现数据元素的存储,顺序表的存储结构示意图如下： List 0 1 2 3 4 5 6 MaxSize-1 size=5 为用C语言描述上图所示的顺序表，定义结构体 S

16、eqList如下： typedef struct DataType list MaxSize ; int size ; SeqList;,顺序表的存储结构示意图,（1） 初始化ListInitiate(SeqList * L ) void ListInitiate(SeqList * L) /*初始化顺序表L*/ L-size = 0 ; /*定义初始数据元素个数*/ （2） 求当前数据元素个数(ListLength( L ) int ListLength ( SeqList L ) /*返回顺序表L的当前数据元素个数*/ return L . size; ,2.2.2顺序表操作的实现,（3）

17、 插入数据元素ListInsert( L, i, x ) int ListInsert( SeqList * L, int i, DataType x ) /*在顺序表L的第i（0isize）个位置前插入数据元素 x */ /*插入成功返回1，插入失败返回0*/ int j ; if ( L- size=MaxSize ) printf (“顺序表已满无法插入！n”); return 0; else if ( iL-size ) ,2。2。2顺序表操作实现（2）,插入数据元素（一）,printf (“参数i 不合法！n”) ; return 0; return 0; else /*为插入做准备

18、*/ for ( j = L-size ; ji ; j-) L-list j =L-list j-1 ; L - list i = x ;/*插入x */,L - size +;/*元素个数加1*/ return 1; 插入步骤：首先把存储单元size-1至存储单元i中的数据元素依次后移一个存储单元，然后把数据元素x插入到存储单元i中（注意此操作是前插），最后把数据元素个数加1其过程如下图： list01234567MaxSIZE-1,插入数据元素（二）,list0123456 7 MaxSize-1,（1）（intint ListDelete ( SeqList * L , int i ,

19、DataType *x ) / /*删除顺序表L中位置为i（0isize -1）的数据元素并存放到x中*/ /* /*删除成功返回1，删除失败返回0*/ ) int j ; if ( L- size=0 ) printf (“顺序表已空无法删除！n”); return 0; ,（4） 删除数据元素取数据元素ListDelete( L, i, x),else if ( iL-size ) printf (“参数i 不合法！n”) ; return 0; Else * x = L - list i ; /*保存删除的元素到x中*/ /*依次前移*/ for ( j = i+1 ; j size-1

20、 ; j + ) L-list j-1 = L- list j ; L - size -;/*数据元素个数减1*/ return 1; ) ),删除和取数据元素（二）,（5） 取数据元素ListGet ( L, i, x ) int ListGet ( SeqList L , int i , DataType * x ) /*取顺序表L中第i个数据元素存于x中成功返回1失败返回0*/ if ( i L . size -1 ) printf (“参数i不合法n”); return 0; else x = L . list i ; return 1 ） ） ;,（5）取数据元素,顺序表上的插入和删

21、除是顺序表中时间复杂度最高的成员函数在顺序表中插入一个数据元素时，最坏情况是pos0，需移动size个数据元素；最好情况是possize，需移动0个数据元素设pi是在第i个存储位置上插入一个数据元素的概率，设顺序表中的数据元素个数为n，当在顺序表的任何位置上插入数据元素的概率相等时，有pi1/（n+1），则向顺序表插入一个数据元素需移动的数据元素的平均次数为： Eis = 0 npi(n-i) = 0n (n-i) = n/2 删除操作的时间复杂度计算见教材33 顺序表中其余操作都与数据元素个数n无关，在顺序表中插入和删除一个数据元素的时间复杂度为 O(n)，其余操作的时间复杂度为 O(1),

22、2。2。3顺序表操作的分析,2。2。4顺序表应用举例,请同学们自己分析例题算法,2。3 线性表的链式表示和实现,指针：指向物理存储单元地址的变量 结点：由数据元素域和一个或若干个指针域组成的一个结构体 链表：链式存储结构的线性表 链表主要有单链表、单循环链表和双向循环链表三种,单链表是构成链表的结点只有一个指向直接后继结点的指针域 1. 单链表的表示方法 定义单链表结点的结构体如下： typedef struct Node DataType data; struct Node * next; SLNode;,2。3。1单链表的存储结构（1）,其中，data域用来存放数据元素， next域用来存

23、放指向下一个结点的指针 单链表有带头结点结构和不结点结构两种指向单链表的指针称作头指针，头指针所指的不存放数据元素的第一个结点称为头结点存放第一个数据元素的结点称为第一个数据元素结点符号表示空指针，空指针是一个特殊标识，用来标识链的结束空指针在算法描述中用NULL表示 在链式存储结构中，数据元素的逻辑次序是通过链中的指针链接实现的,2。3。1（2）,(1）带头单链表每个元素的存贮区分为两大部分： head p data next,带头和不带头结点单链表的比较,a0,a n-1 ,X ,上图是在带头结点单链表第一个数据元素前插入结点前的图示,上图是在带头结点单链表第一个数据元素前插入结点后的图示

24、也可参考下图：,head p,s,带头和不带头结点单链表的比较（2）,p,P-next=q;,q-next=p-next;,Head p next,上图是删除带头结点单链表第一个数据元素结点的示意图,22）不带头结点的单链表插入删除数据元素结点的示意图如下： 在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针s，其插入过程如下： head,a0,a1,an-1,x ,插入删除数据元素结点的示意图,在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针s，其插入过程如下： head 插入前的示意图 s head s a0 上图是在不带头结点的单链表第一个数

25、据元素前插入结点后的示意图,不带头结点的单链表插入删除数据元素示意图,在不带头结点的单链表其它数据元素前插入结点的示意图如下： head data next p,a0,ai-1,ai,an-1 ,X,s,插入结点的示意图,类似地，删除不带头结点的单链表第一个数据元素结点时，头指针head的值将改变为head - next，即指针head等于原head - next的值 head data next,a0,a1,an-1 ,删除不带头结点示意,删除不带头结点的单链表其它数据元素结点时的示意图如下：,head data next p,单链表是由一个个结点链接构成的，单链表中每个结点的结构体定义如下

26、： typedef struct Node ,DataType data; struct Node *next; SLNode; 在带头结点的单链存储结构下，线性表抽象数据类型的操作集合中各个操作的具体实现方法如下： （1） 初始化ListInitiate( SLNode * * head ) void ListInitiate( SLNode * * head )/*初始化*/ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if( * head =(SLNode *)malloc (sizeof ( SLNode )=NULL )exit (1) ( * head )

27、- next = NULL; ,int ListLength( SLNode * head ) SLNode * p = head;/*指向头结点*/ int size = 0;/* size初始为0*/ while ( p - next ! = NULL)/*循环计数*/ p = p - next ; size +; return size; ,（2） 求当前数据元素个数ListLength( SLNode * head ),求当前数据元数个数,head p size=0,a0,a1,an-1 ,head p size=n,a0,a1,an-1 ,接上面,（1）（,（3） 插入ListIns

28、ert( SLNode * head , int i , DataType x ) int ListInsert( SLNode * head , int i , DataType x ) /*在带头结点的单链表head 的第i(0isize)个结点前*/ /*插入一个存放数据元素x的结点插入成功时返回1，失败返回0*/ SLNode * p, * q ; int j ; while ( p - next != NULL ,插入存放数据元素的结点（1）,if ( j != i-1 ) printf ( “插入位置参数错!”); return 0 ; /*生成新结点由指针q指示*/ if ( q

29、 =(SLNode *)malloc (sizeof(SLNode)=NULL) exit (1) q - data = x ; q - next = p - next ;/*插入步骤1*/p - next = q ;/*插入步骤2*/ return 1 ; ,插入存放数据元素的结点（2）,（4） 删除取数据元素 ListDelete( SLNode * head , int i , DataType x ) int ListDelete ( SLNode * head , int i , DataType x ) /*删除带头结点的单链表head的第i（0isize-1）个结点*/ /*被删

30、除结点的数据元素域值由x带回删除成功时返回1，失败返回0*/ SLNode * p , * s ; int j ; p = head ; j = -1;,删除取数据元素（1）,while ( p - next != NULL ,删除取数据元素（2）,（5） 取数据元素ListGet( SLNode * head , int i , DataType x ) int ListGet( SLNode * head , int i , DataType x ) SLNode * p ; int j ; p = head ; j = -1 ; while ( p - next != NULL ,取数据

31、元素,（6） 撤销单链表Destroy( SLNode * * head ) void Destroy( SLNode * * head ) SLNode * p , * p1 ; p = * head ; while ( p != NULL ) p1 = p ; p = p - next ; free ( p1 ); head = NULL ; ,撤销单链表,当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为： Eis = 0n pi (n-i) = 1/(n+1)0n (n-i) = n/2 删除单链表的一个数据元素时比较数据元素的平均次数

32、为： Edl =0n-1 qi(n-i) =1/ n0n-1 (n-i) =(n-1)/2 单链表数据元素个数操作的时间复杂度为T（n）=O（n） 单链表的主要优点是不需要预先确定数据元素的最大个数，插入和删除操作时不需要移动数据元素；主要缺点是每个结点中要有一个指针域，因此，空间单元利用效率不高此外，单链表操作的算法较复杂,2。3。3单链表操作的效率分析,本章结束时，再行分析,2。3。4单链表应用举例,循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环 带头结点的循环链表的操作与带头单链表的操作相似，差别在

33、于： 1. 在初始化函数中，把语句 (*head) - next = NULL改为(*head) - next = head 2. 在其它函数中，循环判断条件p - next != NULL和p - next -next !=NULL中的NULL改为头指针head ,2。3。5循环单链表,1.双向链表的存储结构 双向链表是每个结点除后继指针域外还有一个前驱指针域 这里讨论的是带头结点的双向循环链表在双向链表中，每个结点包括三个域，分别是data域next域prior域 双向链表结点的结构体定义如下： prior data next typedef struct Node DataType da

34、ta ; struct Node * next ; struct Node * prior ; DLNode ; 双向循环链表的后继指针和前驱指针各自构成自己的单循环链表，见图48 2-17 双向链表有利于频繁查找当前结点的后继结点和当前结点的前驱结点,2。3。6双向链表,3.双向链表的操作实例,设指针指向双向链表中的第i个结点，则p - next指向第i+1个结点，p - next - prior 仍指向第i个结点，即p - next - prior = p；同样地，p - prior指向第i-1个结点，p - prior - next仍指向第i个结点，即p - prior - next =

35、 p p,head 双向链表的指针关系空链表,双向链表的操作实现如下： (1)初始化 void ListInitiate ( DLNode * * head ) if ( * head = (DLNode *)malloc( sizeof (DLNode) = NULL)exit (0) ; ( * head ) - prior = * head ;/*构成前驱指针循环链*/ ( * head ) - next = * head ;/*构成后继指针循环链*/ ,操作实现如下,/*在带头结点的双向循环链表的第i个结点前*/ /*插入一个存放数据元素x的结点插入成功返回1，失败返回0*/ int

36、ListInsert ( DLNode * head , int i , DataType x ) DLNode * p , * s ; int j ; p = head - next ; j = 0 ; while ( p != head ,(2)插入数据元素（1）,if ( s = (DLNode *)malloc(sizeof(DLNode) = NULL) exit (0) ; s - data = x ; s - prior = p - prior ;/*插入步骤1*/ p - prior - next = s ;/*插入步骤2*/ s - next = p ;/*插入步骤3*/ p

37、 - prior = s ;/*插入步骤4*/ return 1 ; ,(2)插入数据单元（2）,循环双向链表的插入过程如下： head p,插入过程,s,int ListDelete ( DLNode * head ,int i , DataType * x ) /* 删除带头结点双向循环链表head的第i(0isize-1)个结点*/ /*被删除结点的数据元素域值由x带回，删除成功时返回1，失败返回0*/ DLNode * p ; int j ; p = head - next ; j = 0 ; while ( p - next != head ,（3）删除数据无数（1）,（3）删除数据

38、元素（2）,if ( j != i ) printf (“删除位置参数出错！”) ; return 0 ; p - prior - next = p - next ;/*删除步骤1*/ p - next - prior = p - prior ;/*删除步骤2*/ * x = p - data; free ( p ) ; return 1 ; ,void Destroy ( DLNode * * head ) DLNode * p , * p1 ; int i , n = ListLength ( * head ) ; p = * head ; for ( i = 0 ; i next ; f

39、ree ( p1 ); head = NULL ; ,（4）撤销内存空间Destroy ( DLNode * * head ),2。4静态链表 2。5算法设计举例（1）,2.5.1 顺序表算法设计举例 例2-4构造一个顺序表的删除算法，把顺序表L中数据元素删除 算法思想；此删除问题可通过一个循环比较过程来实现 算法设计如下： int ListDataDelete ( SeqList * L , DataType x ) int i , j ;,for ( i = 0 ; i size ; i +)/*寻找元素x*/ if ( x = L - list i ) break ; if ( i =

40、L - size ) return 0 ;/*未寻找到元素x*/ else/*寻找到元素*/ for ( j = i ; j size ; j + )/*元素依次前移*/ L - listj = L - listj+1 ; L - size - ;/*元素个数减1*/ return 1 ; ,算法设计举例（2）,例2-5 设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置，要求插入后保持单链表数据元素的递增有序 算法思想；从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比

41、较；否则，就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾,2。5。2单链表算法设计举例,void LinListInsert ( SLNode * head , DataType x ) SLNode * curr , * pre , * q ; /*循环初始化*/ curr = head - next ; /*curr指向第一个设计元素结点*/ pre = head ; /*pre指向头结点*/ /*循环定位插入位置*/ while ( curr != NULL 学生分析剩余的例题,算法设计如下,教学

42、目的：1.掌握堆栈的基本概念 2.了解堆栈抽象数据类型 3.熟练掌握堆栈的表示和实现 4.掌握队列的基本概念 5.掌握顺序循环队列的表示和实现 6.掌握链式队列的存储结构和操作的实现 教学重点：1.堆栈的表示和实现 2.队列的实现 教学难点：堆栈的实现,第三章堆栈和队列,3.1.1堆栈的基本概念 堆栈 是一种特殊的线性表其数据元素以及数据元素间的逻辑关系和线性表完全相同，差别在于线性表允许在任意位置插入和删除，而堆栈只允许在栈顶进行操作堆栈也称作后进先出表它可完成比较复杂的数据元素特定序列的转换任务,3。1堆栈,数据集合：堆栈的数据集合可以表示为a0,a1,an-1每个数据元素的数据类型为Da

43、taType. 操作集合： 1.初始化StackInitiate(S)：初始化堆栈S 2.非空否StackNotEmpty(S)：堆栈S非空否若堆栈非空，则函数返回1；否则，返回0 3.入栈StackPush(S,x)：在堆栈的当前栈顶插入数据元素x 4.出栈StackPop(S,d)：把堆栈S的当前栈顶数据元素删除并由参数d带回 5.取栈顶数据元素StackTop(S,d)：取堆栈S的当前栈顶数据元素并由参数d带回 以上3.4.5均为成功返回1；否则，返回0,3。1。2堆栈抽象数类型,3。1。2 堆栈抽象数据类型,1. 1. 顺序堆栈的存储结构 顺序堆栈的存储结构示意图如下： Stack 栈

44、底 栈顶 0 1 2 3 4 5 MaxStackSize-1 top 用C语言定义上述顺序堆栈结构体SeqStack如下： typedef struct DataType stack MaxStackSize ; int top ; SeqStack ;,a 0 a1 a2 a3 a4,3。1。3堆栈的顺序表示和实现,; .(1) 初始化StackInitiate(S) void StackInitiate ( SeqStack * S )/*初始化顺序堆栈S*/ S - top = 0 ;/*定义初始栈顶下标值*/ （2） 非空否StackNotEmpty(S) int StackNotE

45、mpty ( SeqStack S ) /*判断顺序堆栈S非空否，非空返回1，否则返回0*/ if ( S.top = 0) return 0 ; else return 1 ; ,2。顺序堆栈的操作实现（1）,int StackPush ( SeqStack * S ,DataType x ) /*把数据元素值x压入顺序堆栈S，入栈成功返回1，否则返回0*/ if ( S - top = MaxStackSize ) printf (“堆栈已满无法插入！n”) ; return 0 ; else S - stack S - top = x ; S - top + ; return 1 ; ,

46、(3) 入栈StackPush ( SeqStack * Sz ,DataType x ),操作实现（2）,int StackPop(SeqStack * S , DataType * d ) /*弹出顺序堆栈S的栈顶数据元素值到参数d，出栈成功返回1，否则返回0*/ if ( S - top top - ; * d = S - stack S - top ; return 1 ; ,操作实现（3）,（4） 出栈StackPop(SeqStack * S , DataType * d ),StackTop(SeqStack S ,DataType * d ) int StackTop(SeqS

47、tack S ,DataType * d)/*取顺序堆栈S的当前栈顶数据元素值到参数d，成功返回1，否则返回0*/ if ( S.top = 0 ) printf (“堆栈已空！n”) ; return 0 ; else * d = S.stack S.top-1 ; return 1 ; ,（5）取顶数据元素,设上述顺序堆栈的结构体定义和操作的实现函数存放在文 件 SS中，设计如下测试主函数进行测试： include /*该文件包含printf()函数*/ include /*该文件包含exit()函数*/ define MaxStackSize 100 /*定义MaxStackSize为

48、100*/ typedef int DataType ; /*定义DataType为int数据类型*/ include “SeqStack.h” void main ( void ) SeqStack myStack ; int i , x ;,3。顺序堆栈的测试（1）,StackInitiate( ,3。顺序堆栈的测试（2）,else printf (“当前栈顶数据元素为：%dn”, x ) ; printf (“依次出栈的数据元素序列如下：n”) ; while ( StackNotEmpty ( myStack ) StackPop ( /*显示数据元素*/ 程序运行输出结果如下： 当前

49、栈顶数据元素为：10 依次出栈的数据元素序列如下： 10987654321,3。顺序堆栈的测试（3）,1.链式堆栈的存储结构,与线性链表类似，链式栈也需要一个描述结点，它作为整个栈的代表。链式栈中的存贮栈元素的结点的结构与线性链表相同。,3。1。4堆栈的链式表示和实现（1）,堆栈有两端，插入元素和输出元素的一端为栈顶，另一端为栈底链式堆栈都设计成把靠近头指针的一端定义为栈顶如上图所示： 链式堆栈结点的结构体定义如下： typedef struct snode DataType data ; struct snode * next ; ,3.1.4堆栈的链式表示和实现（2）,链式堆栈的插入和删除

50、操作都是在链表的表头进行的若把链式堆栈设计成带头结点的结构，则入栈和出栈操作改变的只是头指针所指头结点的域的值，而不是头指针的值，因此，头指针参数可设计成结点的指针类型，故此头指针参数必须设计成结点的双重指针（即指针的指针）类型 带头结点链式堆栈操作的实现如下： （1） 初始化StackInitiate ( LSNode * head ) void StackInitiate ( LSNode * head ) /*初始化带头结点链式堆栈*/ if(*head=(LSNode *)malloc(sizeof(LSNode)=NULL)exit(1); (*head) - next = NULL

51、 ; ,3。链式堆栈的操作的实现,（2） 非空否StackNotEmpty(LSNode * head) int StackNotEmpty(LSNode * head) /*判断堆栈是否非空，非空返回1，否则返回0*/ if (head - next = NULL ) return 0 ; return 1 ; ,3。链式堆栈的操作的实现（2）,（3）入栈StackPush( LSNode * head , DataType x ) /*把数据元素x插入链式堆栈的栈顶head作为新的栈顶*/ int StackPush( LSNode * head , DataType x ) LSNode

52、 * p ; if (p = ( LSNode *)malloc(sizeof(LSNode) = NULL ) printf(“内存空间不足无法插入！n”); return 0 ; p - data = x ; p - next = head - next ; /*新结点链入栈顶*/ head - next = p ; /*新结点成为新的栈顶*/ return 1 ; ,3。链式堆栈的操作的实现（3）,(4) 出栈StackPop (LSNode * head ,DataType * d ) int StackPop (LSNode * head ,DataType * d ) /*出栈并把

53、栈顶元素由参数d带回*/ LSNode * p = head - next ; if ( p = NULL ) printf(“堆栈已空出错!”) ; return 0 ; head - next = p - next ; /*删除原栈顶结点*/ * d = p - data ; /*原栈顶结点元素赋予d*/ free ( p ) ; /*释放原栈顶结点内存空间*/ return 1 ; ,3。链式堆栈的操作的实现（4）,(5 取栈顶数据元素StackTop(LSNode * head , DataType * d ) int StackTop(LSNode * head , DataType

54、 * d ) /*取栈顶元素并把栈顶元素由参数d带回*/ LSNode * p = head - next ; if ( p = NULL ) printf(“堆栈已空出错!”) ; return 0 ; d = p - data ; return 1 ; ,3。链式堆栈的操作的实现（5）,(5) 撤销动态申请空间Destroy( LSNode * head ) void Destroy( LSNode * head ) LSNode * p , * p1 ; p = head ; while( p != NULL ) p1 = p ; p = p - next ; free ( p1 );

55、与单链表的操作集合相同，链式堆栈也要增加一个撤销动态申请空间的操作,3。链式堆栈的操作的实现（6）,3。3队列,3.3.1队列的基本概念 队列是一种特殊的线性表它允许在其一端进行插入操作，在其另一端进行删除操作 队列中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头插入称为入队列，删除称为出队列当队列中没有数据元素时称为空队列因队尾插入，队头删除，它也称作先进先出表，即FIFO（First In First Out）的结构 插入与删除分别称为入队与出队。,数据集合： 队列的数据集合可以表示为a0,a1,an-1，每个数 据元素的数据类型为DataType 操作集合： （1） 初始

56、化QueueInitiate(Q)：初始化队列Q. （2） 非空否QueueNotEmpty(Q)：队列Q非空否 若队列非空，函数返回1，否则，函数返回0 （3） 入队列QueueAppend( Q ,x ):在队列Q的队尾插入数据元素x如入队列成功，返回1；否则，返回0 （4） 出队列QueueDelete ( Q ,d )：把队列Q的队头数据元素删除并由参数d带回如出队列成功，返回1；失败，则返回0 （5） 取队头数据元素QueueGet ( Q , d )：取队头数据元素并由参数d带回如取到数据元素返回1；否则，返回0,.,3。3。2队列抽象数据类型,1. 顺序队列的存储结构见73图3-

57、7 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针以分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后尾指针将加。出队时，删去所指的元素，然后头指针将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 顺序队列的动态示意图见73图3-7,3。3。3 顺序队列,因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。见教材上的例子 ,2.顺序队列的“假溢出”问题,. 1。顺序循环队列的基本原理 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过