1、资源环境学院 游涟数数 据据 结结 构构数据结构数据结构（使用（使用C语言、第语言、第3版）版） 朱战立朱战立 西安交通大学出版社西安交通大学出版社数据结构数据结构 （C语言版）语言版） 严蔚敏等严蔚敏等 清华大学出版社清华大学出版社 数据结构数据结构 有关内容有关内容预备知识、绪论预备知识、绪论树和二叉树树和二叉树图图非线性结构非线性结构应用应用查找查找排序排序线性结构线性结构线性表线性表堆栈与队列堆栈与队列数据结构数据结构预备知识预备知识 C语言中的有关内容语言中的有关内容 课程性质课程性质 是计算机专业和计算机技术应用相关专业的基础课。是计算机专业和计算机技术应用相关专业的基础课。 与程
2、序设计语言的关系与程序设计语言的关系 以程序设计语言为工具，描述数据结构的基本内容和以程序设计语言为工具，描述数据结构的基本内容和常用操作算法。常用操作算法。数据结构数据结构程序结构程序结构一一般般结结构构形形式式函数函数1函数函数2 ：函数函数n主函数主函数函函数数系统函数（库函数）系统函数（库函数）用户自定义函数用户自定义函数数据结构数据结构 指针、指针变量、变量的指针指针、指针变量、变量的指针 指针不仅能指向基本类型（指针不仅能指向基本类型（如如 int *p1 ;），还可），还可以有数组的指针、指向指针的指针（如以有数组的指针、指向指针的指针（如 int * *p2 ;）、）、结构体类
3、型的指针等。结构体类型的指针等。指针类型指针类型数据结构数据结构定义结构体类型：定义结构体类型： struct ; 结构体类型结构体类型定义结构体类型变量：定义结构体类型变量： struct student char Name20 ; int Age ; float Score ; ; struct student Student1 , *p ;数据结构数据结构 struct student char Name20 ; int Age ; float Score ; Student1 , *p ; 对结构体成员的访问方式：对结构体成员的访问方式： p = &Student1 ; ： 几种访问方
4、式几种访问方式 Student1 . Age (*p) . Age p Age数据结构数据结构函数函数 一般形式：一般形式： 数据类型数据类型 函数名（数据类型函数名（数据类型 参数参数1 , ） 函数体函数体 返回值、参数返回值、参数数据结构数据结构返回值返回值函数名函数名return语句语句返回值类型返回值类型参数参数输入型（值传递）输入型（值传递）输出型（地址传递）输出型（地址传递）数据结构数据结构自定义语句自定义语句功能：定义同名数据类型名功能：定义同名数据类型名 typedef ; typedef struct Node int data ; struct Node *next ;
5、SLNode ; SLNode *p1 , *p2 ; typedef float DataType ; DataType x1 ; 等同于等同于 float x1 ;数据结构数据结构动态内存分配动态内存分配分配内存分配内存静态分配静态分配动态分配动态分配在在编制编制程序时程序时确定占用内存确定占用内存单元的大小单元的大小在在运行运行程序时程序时确定占用内存确定占用内存单元的大小单元的大小数据结构数据结构常用的动态分配和释放函数：常用的动态分配和释放函数：void * malloc ( size ) void free ( void * p ) SLNode * q ; q = ( SLNod
6、e * ) malloc ( sizeof ( SLNode ) ) ; free ( q ) ;数据结构数据结构第一章第一章 绪论绪论 随着各学科的发展，计算机的处理对象将不断出新，随着各学科的发展，计算机的处理对象将不断出新，针对每种应用领域新的处理对象，我们面临：针对每种应用领域新的处理对象，我们面临： 数据结构要解决的问题数据结构要解决的问题 （在此基础上）如何有效地（在此基础上）如何有效地实现实现处理对象之间的处理对象之间的 运算运算关系。关系。 如何有效地如何有效地组织组织具有某种关系的数据在计算机中的具有某种关系的数据在计算机中的存储存储方法方法物理（存储）结构物理（存储）结构；
7、 如何如何选择选择合适的数据合适的数据表示表示逻辑结构逻辑结构；数据结构数据结构1.1 数据结构的基本概念数据结构的基本概念 计算机的算法与数据结构密切相关计算机的算法与数据结构密切相关每个算法都依每个算法都依赖于具体的数据结构；数据结构直接影响着算法的选择和赖于具体的数据结构；数据结构直接影响着算法的选择和效率。效率。 对不同的数据组织形式，需要选择不同的算法；对对不同的数据组织形式，需要选择不同的算法；对不同的数据组织形式，运算的定义也不同。不同的数据组织形式，运算的定义也不同。通讯录之例：通讯录之例： 姓名随意排列；姓名随意排列；姓名按字母顺序排列；姓名按字母顺序排列；姓名按类排列。姓名
8、按类排列。 数据结构在程序设计中起着怎样的作用数据结构在程序设计中起着怎样的作用数据结构数据结构数据、数据元素、数据项、抽象数据元素、抽象数据元素类型数据、数据元素、数据项、抽象数据元素、抽象数据元素类型、数据的逻辑结构、数据的存储结构、数据的操作、数据的操作集合数据的逻辑结构、数据的存储结构、数据的操作、数据的操作集合 数据元素之间的关系（数据元素之间的关系（R）线性关系线性关系 数据元素之间的关系是一一对应的关系。数据元素之间的关系是一一对应的关系。非线性关系非线性关系 数据元素之间的关系是一对多或多对多的关系。数据元素之间的关系是一对多或多对多的关系。 基本术语基本术语数据结构数据结构
9、线性结构线性结构 数据元素之间为线性关系的结构。数据元素之间为线性关系的结构。 非线性结构非线性结构 数据元素之间为非线性关系的结构。数据元素之间为非线性关系的结构。 数据结构（逻辑结构）数据结构（逻辑结构） 顺序存储结构顺序存储结构 非顺序存储结构非顺序存储结构（链式存储结构）（链式存储结构） 存储结构（物理结构）存储结构（物理结构）数据结构数据结构1.3 算法和算法的时间复杂度算法和算法的时间复杂度描述求解问题方法描述求解问题方法的操作步骤的集合的操作步骤的集合输入性输入性输出性输出性有限性有限性确定性确定性可执行性可执行性 算法算法数据结构数据结构 算法设计目标算法设计目标正确性、正确性
10、、 可读性、可读性、 健壮性健壮性高效率（高效率（时间复杂度时间复杂度）、低存储量需求（）、低存储量需求（空间复杂度空间复杂度） 算法时间效率的度量算法时间效率的度量 度量一个算法应脱离具体的计算机和程序设计语言，度量一个算法应脱离具体的计算机和程序设计语言，仅考虑算法本身的效率高低。仅考虑算法本身的效率高低。 算法效率是问题规模的函数算法效率是问题规模的函数数据结构数据结构算法的时间效率算法的时间效率（算法的时间复杂度）（算法的时间复杂度） 是算法所处理的数据个数是算法所处理的数据个数n的函数的函数 用大用大O 符号来表示符号来表示数量级数量级的概念，若算法中基本操作的概念，若算法中基本操作
11、重复执行的频率重复执行的频率T( n ) 是问题规模是问题规模 n 的某个函数的某个函数f ( n ) ， 记作：记作： T( n ) = O ( f ( n ) ) 表示随表示随 n 增大，算法执行时间的增长率与增大，算法执行时间的增长率与f ( n )同级。同级。如如T( n ) = O( n2 )，表示随表示随 n 增大，算法执行时间的增长增大，算法执行时间的增长率与率与 n2 成正比。成正比。数据结构数据结构第二章第二章 线性表线性表 线性表是最简单、最常用的一种数据结构，线性表是最简单、最常用的一种数据结构，比较适合于描述具有自然顺序的数据。线性结构比较适合于描述具有自然顺序的数据。
12、线性结构的基本特点是除第一个和最后一个数据元素外每的基本特点是除第一个和最后一个数据元素外每个数据元素个数据元素只有一个前驱数据元素和一个后继数只有一个前驱数据元素和一个后继数据元素据元素。 本章本章重点重点为线性表的顺序存储结构、链式存为线性表的顺序存储结构、链式存储结构以及相关操作。储结构以及相关操作。数据结构数据结构2.1 线性表抽象数据类型线性表抽象数据类型 线性表的定义线性表的定义同一线性表中各元素类型相同，元素为有限个；同一线性表中各元素类型相同，元素为有限个；元素之间相对位置是线性关系。元素之间相对位置是线性关系。特特点点 是一种可以在任意位置进行插入和删除数据元素操是一种可以在
13、任意位置进行插入和删除数据元素操作的、由作的、由n（n0）个相同类型数据元素个相同类型数据元素a0 , a1 , , an-1组成的线性结构。组成的线性结构。 n 长度长度 不含元素的表为空表不含元素的表为空表 ai 序号为序号为i 的数据元素（抽象数据元素）的数据元素（抽象数据元素）数据结构数据结构 线性表抽象数据类型线性表抽象数据类型数据集合数据集合 表示为：表示为：a0 , a1 , , an-1，每个数据元素的数据类型，每个数据元素的数据类型为抽象数据元素类型。为抽象数据元素类型。数据集合数据集合操作集合操作集合操作集合操作集合 数据集合上可进行的操作，如：初始化、求元素个数据集合上可
14、进行的操作，如：初始化、求元素个数、插入、删除、取元素等。数、插入、删除、取元素等。（具体实现要结合存储结构）（具体实现要结合存储结构）数据结构数据结构2.2 线性表的顺序表示和实现线性表的顺序表示和实现 用一组用一组地址连续地址连续的存储单元的存储单元依次依次存储线性表中各元素存储线性表中各元素的存储结构称为线性表的顺序存储结构，简称顺序表。的存储结构称为线性表的顺序存储结构，简称顺序表。 顺序表的存储结构顺序表的存储结构a0a2a3a4a5a6 a1 0123456MaxSize -1listsize = 7 逻辑上相邻的数据元素，其物理次序也是相邻逻辑上相邻的数据元素，其物理次序也是相邻
15、的。元素间逻辑上的前后关系体现在数据元素存储的。元素间逻辑上的前后关系体现在数据元素存储单元的前后位置关系上。单元的前后位置关系上。特特点点数据结构数据结构用用C语言中的语言中的一维数组一维数组表示顺序表的存储结构表示顺序表的存储结构: : 以结构体的方式定义：以结构体的方式定义： typedef struct DataType list MaxSize ; int size ; SeqList ;最大元素个数最大元素个数当前存储的当前存储的元素个数元素个数顺序表结构体名顺序表结构体名数据结构数据结构 顺序表操作的实现顺序表操作的实现 void ListInitiate ( SeqList *
16、 L ) L size = 0 ; 初始化初始化 int ListLength ( SeqList L ) return L . size ; 求当前元素个数求当前元素个数数据结构数据结构 在顺序表在顺序表L 的第的第 i ( 0 i size )个位置前插入新数据元素个位置前插入新数据元素x： 后移元素，空出后移元素，空出 i 位；位； 插入元素插入元素 x ，线性表长度加，线性表长度加1。0size-1ia0aiasize-1插入数据元素插入数据元素数据结构数据结构 int ListInsert ( SeqList * L , int i , DataType x ) int j ; if
17、 ( L size = MaxSize ) printf ( 表已满表已满! ! n ) ; return 0 ; else if ( i L size ) printf ( i 值不合法值不合法! ! n ) ; return 0 ; else for( j = L size ; j i ; j - - ) L list j = L list j - 1 ; L list i = x ; L size + + ; return 1 ; 数据结构数据结构 删除删除顺序表顺序表L 中第中第i ( 0 i size - 1 ) 个数据元素并存放到个数据元素并存放到 x 中：中： 前移元素，压盖前移
18、元素，压盖 i 位；位； 线性表长度减线性表长度减1。删除数据元素删除数据元素0size-1ia0aiasize-1数据结构数据结构 int ListDelete( SeqList * L , int i , DataType * x ) int j ; if ( L size = 0 ) printf (表已空表已空! ! n ) ; return 0 ; else if ( i L size - 1 ) printf ( i 值不合法值不合法! ! n ) ; return 0 ; else * x = L list i ; for( j = i + 1； j size - 1 ; j +
19、 + ) L list j - 1 = L list j ; L size - - ; return 1 ; 数据结构数据结构取数据元素取数据元素 int ListGet ( SeqList L , int i , DataType * x ) if ( i L . size - 1 ) printf ( i 值不合法值不合法! ! n ) ; return 0 ; else * x = L . list i ; return 1 ; 数据结构数据结构 特点特点 是随机存取的结构；空间利用率高。是随机存取的结构；空间利用率高。 数据元素最大个数需预先确定；插入和删除数据元素最大个数需预先确定；
20、插入和删除操作时需要移动大量数据，不适合要频繁进行插入和操作时需要移动大量数据，不适合要频繁进行插入和删除操作的问题。删除操作的问题。数据结构数据结构 应用举例应用举例例例2-1 假设对顺序表操作的实现模块放在文件假设对顺序表操作的实现模块放在文件SeqList.h中，现要求利用它们建立一个线性表，先输入数据元素中，现要求利用它们建立一个线性表，先输入数据元素1， 2，10 ，再删除元素，再删除元素5 ，最后依次显示当前线性表中，最后依次显示当前线性表中的数据元素的数据元素。分析：分析：定义线性表最大元素个数定义线性表最大元素个数MaxSize；定义；定义DataType为为int； 调用调用
21、SeqList.h中顺序表的插入、删除、取元素等函数。中顺序表的插入、删除、取元素等函数。数据结构数据结构 # include # define MaxSize 100 typedef int DataType ; # include SeqList . h void main ( void ) SeqList myList ; int i , x ; ListInitiate ( & myList ) ;数据结构数据结构 for ( i = 0 ; i 10 ; i + + ) if ( ListInsert ( & myList , i , i + 1 ) = 0 ) printf ( 错
22、误！错误！ n ) ; return ; if ( ListDelete ( & myList , 4 , &x ) = 0 ) printf ( 错误！错误！ n ) ; return ; for ( i = 0 ; i data p next p = p next ;自学自学 带头结点单链表与不带头结点单链表的区别、比较带头结点单链表与不带头结点单链表的区别、比较数据结构数据结构初始化初始化 void ListInitiate ( SLNode * * head ) if ( ( * head = ( SLNode * ) malloc ( sizeof ( SLNode ) ) ) =
23、NULL ) exit ( 1 ) ; ( * head ) next = NULL ; head 单链表的操作实现单链表的操作实现（以带头结点单链表为例）（以带头结点单链表为例）数据结构数据结构 int ListLength ( SLNode * head ) SLNode * p = head ; int size = 0 ; while ( p next != NULL ) p = p next ; size + + ; return size ; 求当前元素个数求当前元素个数数据结构数据结构插入插入p ai-1ai q x q next = p next ; p next = q ;a
24、i-1ai x数据结构数据结构 int ListInsert ( SLNode *head , int i , DataType x ) SLNode *p , *q ; int j ; p = head ; j = 0 ; while( p next != NULL & j next ; j + + ; if ( j != i - 1 ) printf(插入位置错！插入位置错！ n ) ; return 0 ; if ( q = ( SLNode * ) malloc( sizeof( SLNode ) = = NULL ) return 0 ; q data = x ; q next =
25、p next ; p next = q ; return 1 ; 数据结构数据结构删除删除p ai-1ai ai+1ais ai-1 ai+1 p next = p next next ; 或或 p next = s next ; s = p next ;数据结构数据结构 int ListDelete ( SLNode * head , int i , DataType * x ) SLNode *p , * s ; int j ; p = head ; j = 0 ; while( p next != NULL & p next next != NULL & j next ; j + + ;
26、 if ( j != i - 1 ) printf( 删除位置错！删除位置错！n ) ; return 0 ; s = p next ; * x = s data ; p next = p next next ; free ( s ) ; return 1 ; 数据结构数据结构 int ListGet ( SLNode * head , int i , DataType * x ) SLNode * p ; int j ; p = head ; j = 0 ; while( p next != NULL & j next ; j + + ; if ( j != i ) printf( 位置错！
27、位置错！n ) ; return 0 ; * x =p data ; return 1 ; 取元素取元素数据结构数据结构 void Destroy ( SLNode * * head ) SLNode * p , * p1 ; p = * head ; while( p != NULL ) p1 = p ; p = p next ; free ( p1 ) ; * head = NULL ; 撤消单链表撤消单链表数据结构数据结构 应用举例应用举例例例2-3 使用单链表完成：建立一个使用单链表完成：建立一个线性表，先输入数线性表，先输入数据元素据元素1，2，10，再删除元素，再删除元素5，最后依
28、次显示当前，最后依次显示当前线性表中的数据元素线性表中的数据元素。分析：分析：定义定义DataType为为int；将；将对单链表操作的实现模块对单链表操作的实现模块放在文件放在文件LinList . h中，通过调用函数完成操作；撤消动中，通过调用函数完成操作；撤消动态申请的内存空间。态申请的内存空间。数据结构数据结构 /必要的头文件必要的头文件 typedef int DataType ; # include LinList . h void main ( void ) SLNode * head ; int i , x ; ListInitiate ( & head ) ; for ( i
29、= 1 ; i = 10 ; i + + ) if ( ListInsert ( head , i , i ) = = 0 ) printf ( 错误！错误！ n ) ; return ; 数据结构数据结构 if ( ListDelete ( head , 5 , &x ) = = 0 ) printf ( 错误！错误！ n ) ; return ; for ( i = 1 ; i next prior = = p prior next aip ai ai -1 ai+1图示图示数据结构数据结构p ai ai-1 xs s prior = p prior ; p prior next = s
30、; s next = p ; p prior = s ;p ai ai-1 xs插入元素插入元素数据结构数据结构 p prior next = p next ;p ai ai-1 ai+1 p next prior = p prior ;删除元素删除元素 ai-1 ai+1 ai数据结构数据结构 结点空间是动态申请和动态释放；结点空间是动态申请和动态释放； 数据元素的逻辑次序由结点的指针域指示，插入数据元素的逻辑次序由结点的指针域指示，插入与删除操作不需移动数据元素；与删除操作不需移动数据元素； 结点的指针域需额外占用存储空间；结点的指针域需额外占用存储空间； 是一种非随机存储结构。是一种非随
31、机存储结构。 链式存储结构的特点链式存储结构的特点数据结构数据结构2.4 静态链表静态链表静态单链表静态单链表（最常用的）（最常用的） 链表中的一个结点是链表中的一个结点是数组的一个元素，每个元数组的一个元素，每个元素包含一个素包含一个数据域数据域和一个和一个指示器域指示器域（也称指针），（也称指针），指示器指示了后继结点在指示器指示了后继结点在数组中的相应位置。数组中的相应位置。在顺序表基础在顺序表基础上实现的链表上实现的链表 typedef struct DataType data ; int next ; STLNode ; STLNode StList MaxSize ;数据结构数据结
32、构01234:MaxSize-1A1B2C3D4E-1 : data next01234:MaxSize-1A2E-1B4D1C3 : data next图示图示数据结构数据结构01234:MaxSize-1A2E-1B4D1C3 : data next(a) 初始状态初始状态012345MaxSize-1data nextA2E5B4D1C3 : F-1:(b) 插入插入F后后012345MaxSize-1data nextA2E5B4D1C1 : F-1:(c) 删除删除D后后数据结构数据结构2.5 算法设计举例算法设计举例 顺序表算法设计举例顺序表算法设计举例 例例2-4 设计设计删除顺
33、序表删除顺序表L中数据元素中数据元素x的算法。的算法。 int ListDataDelete ( SeqList * L , DataType x ) int i , j ; for ( i = 0 ; i size ; i + + ) if ( x = = L list i ) break ; if ( i = = L size ) return 0 ; else for ( j = i ; j size ; j + ) L list j = L list j + 1 ; L size - - ; return 1 ; 数据结构数据结构 例例2-5 设计算法，将设计算法，将顺序表顺序表L中所
34、有值相同的数据元中所有值相同的数据元素素x全部全部删除。删除。 int ListMoreDataDelete ( SeqList * L , DataType x ) int i , j , tag = 0 ; for ( i = 0 ; i size ; i + + ) if ( x = = L list i ) for ( j = i ; j size ; j + ) L list j = L list j + 1 ; L size - - ; i - - ; tag = 1 ; return tag ; 数据结构数据结构 单链表算法设计举例单链表算法设计举例例例2-6 设带头结点单链表的
35、头指针为设带头结点单链表的头指针为head，其中的数，其中的数据元素递增有序，编写算法将据元素递增有序，编写算法将数据元素数据元素x插入到该单链表插入到该单链表适当位置上，插入后保持单链表数据元素的递增有序适当位置上，插入后保持单链表数据元素的递增有序。 an a1 a2 head curr = head next ;curr pre = head ;pre数据结构数据结构 an a1 a2 headcurrpre循环执行，条件：循环执行，条件：curr != NULL & curr data next ; an a1 a2 headcurrprecurrpre ai-1 ai 循环结束循环结
36、束 xq插入结点插入结点数据结构数据结构 void LinListInsert ( SLNode * head , DataType x ) SLNode * curr , * pre , * q ; curr = head next ; pre = head ; while ( curr ! = NULL & curr data next ; if ( ( q = ( SLNode * ) malloc ( size ( SLNode ) ) ) = = NULL ) exit ( 1 ) ; q data = x ; q next = pre next ; pre next = q ; 数
37、据结构数据结构例例2-7 设带头结点单链表的头指针为设带头结点单链表的头指针为head，编写算法，编写算法将单链表中的将单链表中的数据元素按数据元素按递增有序进行就地排序。递增有序进行就地排序。 void LinListSort ( SLNode * head ) SLNode * curr , * pre , * p , * q ; p = head next ; head next = NULL ; / 将单链表置空将单链表置空 while ( p != NULL ) curr = head next ; pre = head ; / 在在pre之后插入结点之后插入结点数据结构数据结构 w
38、hile ( curr != NULL & curr data data) pre = curr ; curr = curr next ; / 循环结束，循环结束，p所指结点应插在所指结点应插在pre之后之后 q = p ; p = p next ; / q指欲插结点，指欲插结点，p后移后移 q next = pre next ; pre next = q ; / 将将q指结点插在指结点插在pre之后之后 数据结构数据结构 补充例补充例 以单链表存储结构实现线性表以单链表存储结构实现线性表( a1 , a2 , , an )的就地逆置。的就地逆置。原单链表原单链表 an a1 a2 head结
39、果单链表结果单链表 a1 an an-1 head数据结构数据结构(a) 初始化初始化 an a1 a2 head p = head next ;p an a1 a2 head head next = NULL ;p an a1 a2 head 数据结构数据结构(b)链入链入a1p an a1 a2 head q = p ; p = p next ;q p an a1 a2 head q next = head next ; head next = q ;q p an a1 a2 head 数据结构数据结构q p an a1 a2 head (c)链入链入a2q = p ; p = p nex
40、t ;q p a3 an head a1 a2 q p a3 an head a2 a1 q next = head next ; head next = q ;数据结构数据结构 重复上述过程直到重复上述过程直到 p = = NULL 为止为止 解决方法解决方法 全局变量法全局变量法 参数法参数法 单链表带头结点单链表带头结点 单链表不带头结点单链表不带头结点(d)链入链入an后后q a1 an an-1 head数据结构数据结构 void SLConverse1( SLNode * head ) SLNode *p , *q ; p = head next ; head next = NUL
41、L ; while ( p != NULL ) q = p ; p = p next ; q next = head next ; head next = q ; 参数法参数法1 设设head为带头结点的单链表的头指针为带头结点的单链表的头指针数据结构数据结构 void SLConverse2( SLNode * * head ) SLNode *p , *q ; p =( *head ) ; ( *head ) = NULL ; while ( p != NULL ) q = p ; p = p next ; q next = ( *head ) ; ( *head ) = q ; 参数法参
42、数法2 设设head为不带头结点的单链表的头指针为不带头结点的单链表的头指针数据结构数据结构第三章第三章 堆栈与队列堆栈与队列 堆栈与队列是两种堆栈与队列是两种特殊的线性表特殊的线性表，其上的插，其上的插入、删除操作受到某种特殊限制。堆栈与队列也入、删除操作受到某种特殊限制。堆栈与队列也称为操作受限的线性表。它们在各种类型的软件称为操作受限的线性表。它们在各种类型的软件系统中应用十分广泛，它们可以用来完成数据序系统中应用十分广泛，它们可以用来完成数据序列的特定变换。列的特定变换。数据结构数据结构3.1 堆堆 栈栈 堆栈的基本概念堆栈的基本概念 堆栈堆栈(Stack)是一种特殊的线性表，是一种是
43、一种特殊的线性表，是一种只允许在表只允许在表的一端的一端进行插入或删除操作的线性表。进行插入或删除操作的线性表。几个概念几个概念 栈顶栈顶( top )、栈底、栈底( bottom )、顶元、顶元、 底元、栈顶指针、空栈、进栈、出栈底元、栈顶指针、空栈、进栈、出栈abctopbottom特点特点 先进后出（或后进先出）先进后出（或后进先出）数据结构数据结构进栈顺序进栈顺序 A、B、C、D 出栈顺序出栈顺序 D、C、B、AAABCDAB进栈、出栈示意图进栈、出栈示意图数据结构数据结构 堆栈抽象数据类型堆栈抽象数据类型数据集合数据集合 表示为：表示为：a0 , a1 , , an-1，每个数据元素
44、的数据类型，每个数据元素的数据类型为抽象数据元素类型为抽象数据元素类型DataType。操作集合操作集合 数据集合上可进行的操作，如：初始化、非空否、入数据集合上可进行的操作，如：初始化、非空否、入栈、出栈、取栈顶数据元素等。栈、出栈、取栈顶数据元素等。（具体实现要结合存储结构）（具体实现要结合存储结构）数据结构数据结构 堆栈的顺序表示和实现堆栈的顺序表示和实现（简称顺序堆栈）（简称顺序堆栈）顺序堆栈的存储结构顺序堆栈的存储结构 利用一维数组定义顺序栈，用指示器利用一维数组定义顺序栈，用指示器top指示当指示当前栈顶位置。前栈顶位置。 typedef struct DataType stack
45、 MaxStackSize ; int top ; SeqStack ;数据结构数据结构顺序堆栈的操作实现顺序堆栈的操作实现 void StackInitiate ( SeqStack * S ) S top = 0 ; 初始化初始化非空否非空否 int StackNotEmpty ( SeqStack S ) if ( S . top top = MaxStackSize ) printf ( 堆栈已满！堆栈已满！n ) ; return 0 ; else S stack S top = x ; S top + + ; return 1 ; 入栈入栈数据结构数据结构 int StackPop
46、 ( SeqStack * S , DataType * d ) if ( S top top - - ; * d = S stack S top ; return 1 ; 出栈出栈数据结构数据结构 int StackTop ( SeqStack S , DataType * d ) if ( S . top next = = NULL ) return 0 ; else return 1 ; 非空否非空否数据结构数据结构 p next = h next ; h next = p ; a0 an-1 an-2 h an-1 an-2 a0 h x p 入栈入栈数据结构数据结构 int Stac
47、kPush ( LSNode * head , DataType x ) LSNode * p ; if ( p = ( LSNode * ) malloc( sizeof( LSNode ) = = NULL ) printf ( 内存空间不足！内存空间不足！n ) ; return 0 ; p data = x ; p next = head next ; head next = p ; return 1 ; 数据结构数据结构 a0 an-1 an-2 h an-1 a0 an-2 h p p = h next ; h next = p next ;出栈出栈数据结构数据结构 int Sta
48、ckPop ( LSNode * head , DataType * d ) LSNode * p = head next ; if ( p = = NULL ) printf ( 堆栈已空！堆栈已空！ n ) ; return 0 ; head next = p next ; * d = p data ; free ( p ) ; return 1 ; 数据结构数据结构取栈顶元素取栈顶元素 int StackTop ( LSNode * head , DataType * d ) LSNode * p = head next ; if ( p = = NULL ) printf ( 堆栈已空
49、！堆栈已空！ n ) ; return 0 ; * d = p data ; return 1 ; 数据结构数据结构 void Destroy ( LSNode * * head ) LSNode * p , * p1 ; p = * head ; while( p != NULL ) p1 = p ; p = p next ; free ( p1 ) ; * head = NULL ; 撤消动态申请空间撤消动态申请空间数据结构数据结构3.2 堆栈的应用堆栈的应用 应用堆栈对表达式计算进行控制应用堆栈对表达式计算进行控制 借助堆栈变换表达式的表示序列，以便机器正确理借助堆栈变换表达式的表示序列
50、，以便机器正确理解。解。设置一个返回地址栈设置一个返回地址栈rstmaina1a2a3a1a2a3r:s:t: 应用堆栈对过程的调用及返回进行处理应用堆栈对过程的调用及返回进行处理数据结构数据结构3.3 队队 列列 队列的基本概念队列的基本概念 队列队列( (Queue) )也也是一种特殊的线性表，是一种只允许在是一种特殊的线性表，是一种只允许在表的表的一端一端进行进行插入插入操作，而在表的操作，而在表的另一端另一端进行进行删除删除操作的线操作的线性表。性表。几个概念几个概念队头队头（Front）、队尾、队尾（Rear）、队头指针、队头指针、队尾指针、空队、入队列、出队列队尾指针、空队、入队列
