第三章 栈和队列 Stack and Queue 2007.9

生活中的栈与队列 计算机中的栈与队列 栈与队列的特征 栈：表达式的求值、函数的递归调用 队列：打印机任务处理、CPU的进程处理 LIFO(Last In First Out) FIFO(First In First Out)/FIFS(First In First Service)

栈的定义 栈的特征 栈的基本运算 顺序栈的实现 链式栈的实现 第1节 栈 栈的定义 栈的特征 栈的基本运算 顺序栈的实现 链式栈的实现

1.栈（Stack）的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表。 栈顶(Top)为可进行插入、删除的一端，另一端为栈底 (Bottom)。 空栈：表中没有元素。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶 元素。 栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素 应为栈顶元素。换句话说，栈的修改是按后进先出的原则 进行的。因此，栈称为后进先出表（LIFO）。

3.线性表的基本运算 InitList(L) :初始化,置表L为空 ClearList(L):将表L清空 ListLength(L)： 求表L的长度 Insert(L,i,Item) ： 插入，在给定的线性表L中，将数据Item插 入到第i个结点的位置。表L长度加1。 Delete(L,i) ：删除，在给定的线性表L中，删除第i个元素。 表L的长度减1。 Get(L,i) ：获取表L中第i个结点的值。 Locate(L,x) ：查找定位。若线性表L中存在一个值为x的结 点，则返回该结点的位置，否则返回空。 GetNext（L，Item，p）：取Item的后继结点 GetPrior（ L，Item，p ）：取Item的前驱结点  

顺序表的存储结构 顺序表存储结构的C语言描述 基于顺序表的运算的实现 第2节 线性表的顺序存储—顺序表 顺序表的存储结构 顺序表存储结构的C语言描述 基于顺序表的运算的实现

1.顺序表的存储结构 顺序表：把线性表的结点 按逻辑顺序依次存放在一 组地址连续的存储单元里。 用这种方法存储的线性表 简称顺序表。 a1 a2 an 内存 顺序表：把线性表的结点 按逻辑顺序依次存放在一 组地址连续的存储单元里。 用这种方法存储的线性表 简称顺序表。 由于C语言中的一维数组也 是采用顺序存储表示，故 可以用数组类型来描述顺 序表。 有效结点 备用空间 ListSize -1

2.顺序表存储结构的C语言描述 a1 a2 an 1 n-1 length 内存 数组下标 # define ListSize 100 typedef int DataType; typedef struc{ DataType data[ListSize]; int length; } SequenList; /*声明变量*/ SequenList *sqlist; 备用空间 ListSize -1

一个具体的例子 # define ClassSize 100 typedef struct stu { char* num; char* name; int english; int c_languge; int data_stru; }StuType; typedef struc{ StuType data[ClassSize]; int class_len; } class_list; class_list *soft_1; 学生成绩表 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ：

顺序表的地址关系 假设线性表的每个元素需占用m个存储单元，并 以所占的第一个单元的存储地址作为数据元素的 存储位置。则线性表中第i+1个数据元素的存储位 置LOC( a i+1)和第i个数据元素的存储位置LOC(a I ) 之间满足下列关系： LOC(a i+1)=LOC(a i)+m 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*m

3.基于顺序表的运算的实现 InitList(L) :初始化,置表L为空 ClearList(L):将表L清空 ListLength(L)： 求表L的长度 Insert(L,i,Item) ： 插入，在给定的线性表L中，将 数据Item插入到第i个结点的位置。表L长度加1。 Delete(L,i) ：删除，在给定的线性表L中，删除 第i个元素。表L的长度减1。

Get(L,i) ：获取表L中第i个结点的值。 Locate(L,x) ：查找定位。若线性表L中存在一 个值为x的结点，则返回该结点的位置，否则返 回空。 GetNext（L，Item，p）：取Item的后继结点 GetPrior（ L，Item，p ）：取Item的前驱结点  

4.顺序表插入算法的时间复杂度分析 Void InsertList(Sequenlist *sqlist，int i, DataType Item) { int j; if (i<1 || i>sqlist.length+1){ printf(“Position error”); return 0 ; } if( sqlist.length >= ListSize ) { printf(“overflow”); return 0; for( j=sqlist.length-1; j>=i-1; j-- )sqlist.data[ j+1]=sqlist.data[ j ]; sqlist.data[ i-1]=x; sqlist.length++;

顺序表插入算法的时间复杂度分析 时间主要耗费在： for( j=sqlist.length-1; j>=i-1; j-- ) sqlist.data[ j+1]=sqlist.data[ j ]; 所需移动结点的次数不仅依赖于表的长度，而且还 与插入位置有关。 最好：当i=n时，结点不需要后移，其时间复杂度O （1）； 最坏：当i=0时，结点后移语句将循环执行n次，需 移动表中所有结点，其时间复杂度O（n）

平均复杂度：由于插入可能在表中任何位置上进行，因 此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点， 令Eis(n)表示移动结点的期望值（即移动的平均次数）， 则在第i个位置上插入一个结点的移动次数为n-I+1。故 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点 的机会是均等的，则在等概率插入的情况下，

也就是说，在顺序表上做插入运算，平均要移动表 上一半结点。当表长 n较大时，算法的效率相当低。 虽然Eis(n)中n的的系数较小，但就数量级而言，它 仍然是线性阶的。因此算法的平均时间复杂度为 O(n)。 问题：请你分析一下删除算法的时间复杂度。

5.顺序表存储结构特点 基本特点：逻辑上相邻的元素，物理上也是相邻 的。 优点 可以直接实现元素的定位，或者说可以随机存取其中的 任意元素 因为数据在存储结构中是连续存储的，任意元素的存储地址可 由公式直接算出。 高级程序设计语言提供的数组类型可以直接定义顺序存 储结构的线性表，使程序实现十分方便。

顺序存储结构的不方便之处： 数据元素最大个数需预先确定，使得高级语言编译系统需 预先分配相应的存储空间。 插入与删除运算的效率很低。 为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需 移动大量数据。 顺序存储结构的线性表的存储空间不便于扩充。 当一个线性表分配顺序存储空间后，如果线性表的存储空间已满， 但还需要插入新的元素，则会发生“上溢”错误，会导致运算的失 败或中断。

2.2 单链表 Link List

复习：关于指针的概念 即 指针 地址 指针 与 指针所指的变量 指针相关的函数 malloc free

1.单链表的存储结构 线性表的逻辑结构 单链表的结点结构 数据域 指针域 单链表的逻辑结构 单链表的存储结构 head 110 135 ……… …… Data_2 200 ……. Data_1 110 …. Data_n Null 135 数据域 指针域 110 135 单链表的逻辑结构 head Data_1 Data_2 … Data_n ^ 165 单链表的存储结构 200

一个具体的例子 head NULL 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ： head A07001 王萍 90 85 95 A07002 马玲 80 85 90 A07003 张兰 95 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 NULL

一个具体的例子 头指针 head : 165 110 135 165 200 ……… …… A07002 马玲… 200 ……. 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ： 头指针 head : 165 ……… …… A07002 马玲… 200 ……. A07001 王萍… 110 …. A070046 … Null 135 110 135 165 200

2.单链表存储结构的C语言描述 head 顺序表的描述 # define ListSize 100 typedef int DataType; typedef struc{ DataType data[ListSize]; int length; } SequenList; /*声明变量*/ SequenList *sqlist; typedef int DataType; typedef struc node{ DataType data; struc node *next; } LinkList; /*声明变量*/ LinkList *head; head Data_1 Data_2 … Data_n ^

一个具体的例子 # define ClassSize 100 typedef struct stu typedef struct stu { char* num; char* name; int english; int c_languge; int data_stru; }StuType; typedef struc node{ StuType data; struc node *next ; } class_list; class_list *soft_1_head; # define ClassSize 100 typedef struct stu { char* num; char* name; int english; int c_languge; int data_stru; }StuType; typedef struc{ StuType data[ClassSize]; int class_len; } class_list; class_list *soft_1; 学生成绩表 学号 姓名 大学英语 C语言 数据结构 … A07001 王萍 90 85 95 A07002 马玲 80 A07003 张兰 91 99 A07004 李建 70 84 86 A07005 黄勇 82 76 78 : ：

基于单链表的运算的实现 InitList(L) :初始化,置表L为空 ClearList(L):将表L清空 ListLength(L)： 求表L的长度 Insert(L,i,Item) ： 插入，在给定的线性表L中，将 数据Item插入到第i个结点的位置。表L长度加1。 Delete(L,i) ：删除，在给定的线性表L中，删除 第i个元素。表L的长度减1。

Get(L,i) ：获取表L中第i个结点的值。 Locate(L,x) ：查找定位。若线性表L中存在一 个值为x的结点，则返回该结点的位置，否则返 回空。 GetNext（L，Item，p）：取Item的后继结点 GetPrior（ L，Item，p ）：取Item的前驱结点  

单链表算法的时间复杂度 O（1） O（n） InitList(L) ClearList(L) Insert(L,i,Item) ListLength(L) Delete(L,i) Get(L,i) GetNext(L，Item，p) Locate(L,x) GetPrior( L，Item，p) O（1） O（n）

void build( int n ) { linklist void build( int n ) { linklist *q; char ch; int i; printf("\n input %2d data: \t",n); head=(struct link *)malloc(sizeof(struct link)); q=head; scanf("%d",&q->data); for(i=2;i<=n;i++){ q->next=(struct link *)malloc(sizeof(struct link)); q=q->next; } q->next=NULL; 单链表的建立

单链表存储结构特点 不能随机存取，查找速度慢 基本特点：逻辑上相邻的元素，物理上不一定相 邻的。 优缺点 是一种动态结构，整个存储空间为多个链 表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢

2.3 其他形式的链表

2.3.1 循环链表 循环链表的逻辑结构 单链表的逻辑结构 循环链表的空表 循环链表是表中最后一个结点的指针指向头结点， 使链表构成环状。 特点：从表中任一结点出发均可找到表中其他结点， 提高查找效率。 单链表的逻辑结构 循环链表的逻辑结构 Data_1 Data_2 Data_n ^ … Data_1 Data_2 Data_n … head 循环链表的空表

循环链表的操作 循环链表的操作与单链表基本一致,循环条件不同 单链表: p->next==NULL 循环链表: p->next==head

void build( int n ) { linklist void build( int n ) { linklist *q; char ch; int i; printf("\n input %2d data: \t",n); head=(struct link *)malloc(sizeof(struct link)); q=head; scanf("%d",&q->data); for(i=2;i<=n;i++){ q->next=(struct link *)malloc(sizeof(struct link)); q=q->next; } q->next=head; 循环链表的建立

讨论：如何将两个链表合并？ 利用单链表如何实现？P47 EX4 Data_1 Data_2 Data_n ^ … Data_1 Data_2 ha Data_1 Data_2 Data_m ^ … hb

利用循环链表如何实现？ 表头指针与表尾指针的使用 … Data_1 Data_n Data_2 … Data_1 Data_m Data_2 ha ra Data_1 Data_2 Data_m … hb rb

2.3.2 双向循环链表 双向链表的结点结构 prior data next 双向循环链表的逻辑结构 双向循环链表的空表 head 双向循环链表的空表 head 特点：方便查找任一结点的后继和前驱。

双向循环链表的C语言描述 prior data next typedef int DataType; typedef struc Dnode{ DataType data; struc Dnode *prior, next; } DoubleLinkList; /*声明变量*/ DoubleLinkList *head; prior data next

双向循环链表中的插入与删除 void dinsertbefor(dlistnode *p， datatype x) { dlistnode *q=malloc(sizeof(dlistnode)); q—>data=x; q—>prior=p—>prior; q—>next=p; p—>prior—>next=q; p—>prior=q; } void ddeletenode(dlistnode *p) { p–>prior–>next=p–>next; p–>next–>prior=p–>prior; free(p); } 与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。