导图社区 数据结构
- 28
- 0
- 0
- 举报
数据结构
这是一篇关于第1章 概论的思维导图，主要内容包括：1.1 引言，1.2 基本概念和常用术语，1.3 算法的描述和分析，小结，思考与练习。
编辑于2025-03-23 17:13:18- 自考
- 数据结构
- 算法的描述和分析
- 第一章 操作系统概论
这是一篇关于第一章 操作系统概论的思维导图，包含考点1至考点17，系统且全面地覆盖了操作系统概论的核心知识点。从操作系统的定义、特征、观点、功能，到不同类型的操作系统，逻辑清晰，层次分明.
- 数据人主播
这是一篇关于数据人主播的思维导图，主要内容包括：概述，数字人生成方式，语音驱动与口型同步，动作捕捉与交互，场景与直播集成。
- 《马克思主义基本原理概论》
这是一篇关于《马克思主义基本原理概论》的思维导图，主要内容包括：与时俱进是，哲学的基本问题是，空间是物质运动的，实践作为主体有意识、有目的的活动，强调的是实践具有，下列范畴揭示事物联系和发展中确定的和不确定的两种趋势的是，人类社会与自然界有本质区别。。
数据结构
社区模板帮助中心，点此进入>>
- 第一章 操作系统概论
这是一篇关于第一章 操作系统概论的思维导图，包含考点1至考点17，系统且全面地覆盖了操作系统概论的核心知识点。从操作系统的定义、特征、观点、功能，到不同类型的操作系统，逻辑清晰，层次分明.
- 数据人主播
这是一篇关于数据人主播的思维导图，主要内容包括：概述，数字人生成方式，语音驱动与口型同步，动作捕捉与交互，场景与直播集成。
- 《马克思主义基本原理概论》
这是一篇关于《马克思主义基本原理概论》的思维导图，主要内容包括：与时俱进是，哲学的基本问题是，空间是物质运动的，实践作为主体有意识、有目的的活动，强调的是实践具有，下列范畴揭示事物联系和发展中确定的和不确定的两种趋势的是，人类社会与自然界有本质区别。。
- 相似推荐
- 大纲
目录
前言
第1章 概论
1.1 引言
1.2 基本概念和常用术语
1.3 算法的描述和分析
1.3.1算法描述
1.3.2算法分析
小结
思考与练习
第2章 线性表
2.1 线性表的定义和基本运算·
2.1.1线性表的逻辑定义
2.1.2线性表的基本运算
2.2 线性表的顺序存储和基本运算的实现
2.2.1线性表的顺序存储
2.2.22顺序表上基本运算的实现
2.3 线性表的链式存储结构
2.3.11单链表(线性链表)
2.3.2单链表上的基本运算
2.3.3循环链表
2.3.4双向链表
2.4 顺序表和链表的比较
小结…
思考与练习
第3章 栈和队列
3.1栈
3.1.1栈的定义及其运算
3.1.2栈的存储表示和实现见·
3.2栈的应用举例列·
3.2.1圆括号匹配的检验
3.2.2字符串回文的判断
3.2.3数制转换
3.2.4栈与递归
3.3队列
3.3.1队列的定义及其运算·
3.3.2顺序循环队列…
3.3.3链队列
3.4栈和队列的应用实例
3.4.1中缀表达式到后缀表达式的转换
3.4.2后缀表达式的计算
小结·
思考与练习
第4章 多维数组和广义表
4.1多维数组和运算…
4.1.1数组的顺序存储
4.1.2数组运算举例…
4.2矩阵的压缩存储
4.2.1特殊矩阵
4.2.2稀疏矩阵
4.3广义表基础出·
4.3.1 广义表的定义义·
4.3.2 广义表的基本运算
4.3.3 广义表的存储结构
4.3.4 广义表基本运算的实现
小结·
思考与练习1
第5章 树和二叉树
5.1树的基本概念和术语
5.2 二叉树
5.2.1 二叉树的定义和性质
5.2.2 二叉树的存储结构
5.3 二叉树的运算
5.3.1 二叉树的生成
5.3.2 二叉树的遍历
5.3.3二叉树的应用举例
5.4线索二叉树
5.4.1 二叉树的线索化
5.4.2 二叉线索链表上的运算
5.5树和森林
5.5.1 树的存储结构
5.5.2 树、森林与二叉树的转换
5.5.3 树和森林的遍历
5.6哈夫曼树及其应用
5.6.1 最优二叉树(哈夫曼树)
5.6.2 哈夫曼编码
小结
思考与练习
第6章图
6.1 图的定义和基本术语
6.2 图的存储结构
6.2.1邻接矩阵表示法
6.2.2邻接表表示法
6.3图的遍历
6.3.1深度优先搜索遍历
6.3.2广度优先搜索遍历
6.4 图的生成树和最小生成树
6.4.1 图的生成树
6.4.2 最小生成树
6.5 最短路径
6.6 拓扑排序
小结
思考与练习
第7章 排序
7.1 基本概念
7.2 插入排序
7.2.1 直接插入排序…
7.2.2 希尔排序
7.3 交换排序
7.3.1 冒泡排序
7.3.2 快速排序
7.4选择排序
7.4.1 直接选择排序字
7.4.2 堆排序
7.5 归并排序
7.6 分配排序
7.6.1 箱排序
7.6.2 基数排序
7.7 内部排序方法的分析比较交 ·
小结
思考与练习
第8章查找
8.1基本概念
8.2顺序表的查找
8.2.1 顺序查找
8.2.2 二分查找
8.2.3 索引顺序查找
8.2.4 三种查找方法的比较交
8.3树表的查找
8.3.1 二叉排序树
8.3.2 B树
8.3.3 B+树
8.4 散列表查找
8.4.1 散列表的概念
8.4.2 散列函数的构造方法
8.4.3 处理冲突的方法
8.4.4散列表的查找
小结
思考与练习
附录练习题参考答案
参考文献
第1章 概论
1.1 引言
算法+数据结构=程序
著名计算机科学家 N.沃思(N.Wirth)编写的《算法+数据结构=程序》一书明确指出， 在程序设计中，数据结 构与算法同等重要。
1.2 基本概念和常用术语
概念
数据（data）
定义：
数据是对客观事物的符号表示，是信息的载体。它可以是数字、文字、图像、声音等形式。
特点：
数据本身没有意义，只有在特定的上下文中被解释和处理时，才能转化为有用的信息。
例子：
数字“100”可以表示温度、价格、年龄等，具体含义取决于上下文。
数据元素（data element)
定义：
数据元素是数据的基本单位，通常是一个不可分割的、独立的数据单元。它是数据结构中的最小单位。
特点：
数据元素可以是简单的数据类型（如整数、字符），也可以是复杂的数据类型（如结构体、对象）。
例子：
在一个学生信息系统中，学生的“学号”或“姓名”可以是一个数据元素。
数据项（data item)
定义：
数据项是数据元素的组成部分，通常表示数据元素的某个属性或特征。数据项是数据元素的细化。
特点：
数据项可以是数据元素的一部分，也可以是一个独立的数据单元。
例子：
在一个学生的数据元素中，数据项可以包括“学号”、“姓名”、“性别”、“年龄”等。
数据对象(data object）
定义：数据对象是具有相同性质的数据元素的集合。它是对现实世界中某个实体的抽象表示。
特点：数据对象通常包含多个数据元素或数据项，并且这些元素或项之间存在一定的关系。
例子：在一个学生信息系统中，一个“学生”数据对象可以包含“学号”、“姓名”、“性别”、“年龄”等数据项。
1、数据结构包含的内容
（1） 数据元素之间的逻辑（或抽象）关系，也称为数据的逻辑结构
定义：数据元素之间的逻辑（或抽象）关系，与计算机的存储方式无关。
特点：逻辑结构是从问题抽象出来的数学模型，描述数据元素之间的关联方式。
分类：
集合：数据元素之间没有明显的逻辑关系，只是属于同一个集合。
线性结构：数据元素之间存在一对一的线性关系（如数组、链表、队列、栈等）。
树形结构：数据元素之间存在一对多的层次关系（如二叉树、B树、堆等）。
图状结构（网状结构）：数据元素之间存在多对多的任意关系（如有向图、无向图等）。
（2） 数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）
定义：数据元素及其关系在计算机内存中的具体存储方式。
特点：存储结构是逻辑结构在计算机中的实现，依赖于具体的编程语言和硬件环境。
分类：
1||| 顺序存储方法
数据元素存储在连续的存储单元中，逻辑上相邻的元素在物理位置上也相邻。
优点：随机访问效率高，存储密度大。
缺点：插入、删除操作效率低，需要移动大量元素。
例子：数组。
2||| 链接存储方法
数据元素存储在任意的存储单元中，通过指针或引用链接起来。
优点：插入、删除操作效率高，不需要移动元素。
缺点：存储密度较低，访问效率较低。
例子：链表。
3||| 索引存储方法
通过建立索引表来存储数据元素的位置信息，数据元素可以分散存储。
优点：查找效率高，适合大规模数据。
缺点：需要额外的存储空间维护索引表。
例子：数据库索引。
4||| 散列存储方法（哈希存储）
通过哈希函数计算数据元素的存储位置，将数据元素存储在哈希表中。
优点：查找、插入、删除效率高。
缺点：哈希冲突问题，需要处理冲突。
例子：哈希表。
（3） 数据的运算，即对数据元素施加的操作（行为）
定义：对数据元素施加的操作，是数据结构的行为部分。
特点：运算的实现依赖于逻辑结构和存储结构。
常见运算：
查找：在数据结构中查找满足条件的元素。
插入：在数据结构中添加新的元素。
删除：从数据结构中移除指定的元素。
更新：修改数据结构中某个元素的值。
排序：将数据元素按照某种规则重新排列。
遍历：访问数据结构中的每一个元素。
【例1-3】下列关于顺序存储结构与链式存储结构的叙述中，正确的是( )。 A.顺序存储结构的存储空间是连续的， 链式存储结构的存储空间不一定连续 B.顺序存储结构只用于线性结构， 链式存储结构只用于非线性结构 C.顺序存储结构一定比链式存储结构节省存储空间 D.链式存储结构一定比顺序存储结构节省存储空间
（4） 数据类型（Data Type）
定义：
数据类型是一组值的集合以及定义在这些值上的一组操作。
它规定了数据的取值范围、存储方式以及可以进行的操作。
特点：
数据类型是具体的，通常与编程语言直接相关。
它定义了数据的存储空间大小和操作规则。
分类：
基本数据类型（Primitive Data Types）：
由编程语言直接支持的最简单的数据类型。
例如：整数（int）、浮点数（float）、字符（char）、布尔值（bool）等。
#include <stdio.h> int main() { int a = 10; // 整数类型 float b = 3.14; // 浮点数类型 char c = 'A'; // 字符类型 printf("a = %d\n", a); printf("b = %f\n", b); printf("c = %c\n", c); return 0; }
复合数据类型（Composite Data Types）：
由基本数据类型组合而成的复杂数据类型。
例如：数组（array）、结构体（struct）、类（class）等。
#include <stdio.h> // 定义一个结构体类型 struct Student { int id; // 学号 char name[20]; // 姓名 float score; // 成绩 }; int main() { // 声明一个结构体变量 struct Student s1 = {101, "Alice", 95.5}; // 访问结构体成员 printf("ID: %d\n", s1.id); printf("Name: %s\n", s1.name); printf("Score: %.2f\n", s1.score); return 0; }
（5） 抽象数据类型（Abstract Data Type, ADT）
定义：
抽象数据类型是一种数学模型，它定义了一组数据以及对这些数据的操作，但不涉及具体的实现细节。
ADT关注的是“做什么”，而不是“怎么做”。
定义抽象数据类型Triangle，它表示三角形。
ADT Triangle{ //三角形的抽象数据类型定义 数据部分： a,b,c: //表示构成三角形的三条边,实型 操作部分： area(a,b,c) //给定三条边,计算三角形的面积 前提条件：三条边满足构成三角形的条件 perimeter(a,b,c) //给定三条边,计算三角形的周长 输入： a,b,c 输出： 三角形的周长 前提条件： 三条边满足构成三角形的条件 }
特点：
抽象性：ADT隐藏了数据的具体表示和操作的实现细节，只暴露接口。
封装性：数据和操作被封装在一起，用户只能通过接口访问数据。
独立性：ADT的实现可以独立于使用它的程序，便于修改和扩展。
组成：
数据对象：ADT所操作的数据集合。
操作集合：对数据对象可以执行的操作（如插入、删除、查找等）。
例子：
栈（Stack）：
数据对象：一组元素，遵循后进先出（LIFO）原则。
操作集合：push（入栈）、pop（出栈）、isEmpty（判断是否为空）等。
#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 // 定义栈的最大容量 // 定义栈的结构体 typedef struct { int data[MAX_SIZE]; // 存储栈元素的数组 int top; // 栈顶指针 } Stack; // 初始化栈 void initStack(Stack *s) { s->top = -1; // 栈顶指针初始化为-1，表示栈为空 } // 判断栈是否为空 int isEmpty(Stack *s) { return s->top == -1; } // 判断栈是否已满 int isFull(Stack *s) { return s->top == MAX_SIZE - 1; } // 入栈操作 void push(Stack *s, int value) { if (isFull(s)) { printf("Stack is full! Cannot push %d.\n", value); return; } s->data[++(s->top)] = value; // 栈顶指针加1，然后将元素存入栈顶 } // 出栈操作 int pop(Stack *s) { if (isEmpty(s)) { printf("Stack is empty! Cannot pop.\n"); return -1; // 返回-1表示栈为空 } return s->data[(s->top)--]; // 返回栈顶元素，然后栈顶指针减1 } // 获取栈顶元素 int peek(Stack *s) { if (isEmpty(s)) { printf("Stack is empty!\n"); return -1; } return s->data[s->top]; } int main() { Stack s; initStack(&s); // 初始化栈 push(&s, 10); // 入栈 10 push(&s, 20); // 入栈 20 push(&s, 30); // 入栈 30 printf("Top element: %d\n", peek(&s)); // 获取栈顶元素 printf("Popped element: %d\n", pop(&s)); // 出栈 printf("Popped element: %d\n", pop(&s)); // 出栈 printf("Top element: %d\n", peek(&s)); // 获取栈顶元素 return 0; }
队列（Queue）：
数据对象：一组元素，遵循先进先出（FIFO）原则。
操作集合：enqueue（入队）、dequeue（出队）、isEmpty（判断是否为空）等。
列表（List）：
数据对象：一组有序的元素。
操作集合：insert（插入）、delete（删除）、search（查找）等。
1.3 算法的描述和分析
算法(algorithm)
定义1- 1算法是一个由若干确定的 (无二义性的)、 可执行的步骤组成的肯定能够终 止的有序步骤集合。
是解决特定问题的一系列明确步骤或指令。它是计算机科学的核心概念之一，用于描述如何通过有限的步骤完成任务。算法的设计和分析是计算机程序开发的基础。
1.3.1算法描述
1. 输入：
算法必须有零个或多个输入。
输入是算法处理的初始数据。
例如：排序算法的输入可以是一个整数数组。
2. 输出：
算法必须有一个或多个输出。
输出是算法处理后的结果。
例如：排序算法的输出是一个有序的整数数组。
3. 有穷性：
算法必须在有限的步骤内完成，不能无限循环。
例如：一个计算阶乘的算法必须在有限的时间内完成计算。
4. 确定性：
算法的每一步必须有明确的定义，不能有二义性。
例如：算法的每一步操作（如加法、比较）必须是明确的。
5. 可行性：
算法的每一步都必须是可行的，即可以通过基本的操作实现。
例如：算法中的操作必须是计算机能够执行的（如加减乘除、比较等）。
1.3.2算法分析
1||| 执行算法所耗费的时间，即时间复杂性
指执行算法所耗费的时间。
通常用大O表示法 来描述算法的时间复杂度，表示算法运行时间的增长趋势。
例如：
线性查找的时间复杂度是
快速排序的时间复杂度是
2||| 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性
指执行算法所耗费的存储空间，主要是辅助空间（除输入数据外的额外空间）。
空间复杂度也用大O表示法描述。
例如：
冒泡排序的空间复杂度是 O(1)（原地排序，不需要额外空间）。
归并排序的空间复杂度是 O(n)（需要额外的数组来存储中间结果）。
3||| 可读性和可操作性
算法应易于理解、易于编程、易于调试。
可读性高的算法便于团队协作和维护。
可操作性强的算法在实际应用中更容易实现和优化。
例如：
使用清晰的变量名和注释。
模块化设计，将复杂算法分解为多个简单的函数。
4||| 示例：算法的描述和分析
示例1：求两个数的最大公约数（GCD）
算法描述：
输入：两个正整数a和b
输出：a 和 b 的最大公约数
步骤：
1.如果b=0，返回a。 2.否则，计算a mod b， 并将b赋值给a，将a mod b赋值给b。 3.重复步骤1和2，直到b=0。
特性：
有穷性：算法会在有限步骤内结束。 确定性：每一步操作明确。 可行性：基于基本的数学运算。
算法分析：
时间复杂性：O(log min(a，b))(欧几里得算法的复杂度) 空间复杂性：O(1)(只需要常数级别的辅助空间)。 可读性：算法逻辑清晰，易于实现。
示例2：冒泡排序
算法描述：
输入：一个长度为n的数组arr。
输出：按升序排列的数组。
步骤：
1.从第一个元素开始，依次比较相邻的两个元素，如果顺序错误则交换。
2.重复上述过程，直到没有元素需要交换。
特性：
有穷性：算法会在O(n²)步骤内结束。
确定性：每一步操作明确。
可行性：基于比较和交换操作。
算法分析：
时间复杂性：O(n²))((最坏和平均情况))。
空间复杂性：0(1)(原地排序，不需要额外空间)。
可读性：算法逻辑简单，易于理解和实现。
小结
思考与练习
思考题
1.学习数据结构的目的是什么?
学习数据结构的目的是为了高效地组织、存储和管理数据，从而设计出更高效的算法，解决实际问题。数据结构是算法的基础，掌握数据结构可以帮助我们更好地理解问题的本质，优化程序的性能。
2.什么是数据的逻辑结构?什么是数据的物理结构?两者之间有什么联系?
数据的逻辑结构：指数据元素之间的逻辑关系，与数据的存储无关。常见的逻辑结构包括线性结构（如线性表、栈、队列）和非线性结构（如树、图）。
数据的物理结构：指数据在计算机内存中的存储方式，包括顺序存储、链式存储、索引存储和散列存储等。
联系：逻辑结构是抽象的，描述数据之间的关系；物理结构是具体的，描述数据在计算机中的实际存储方式。逻辑结构需要通过物理结构来实现。
3.什么是算法?算法与程序有什么区别?
算法：算法是解决问题的一系列明确步骤，具有输入、输出、有穷性、确定性和可行性。
区别：
算法是抽象的，描述解决问题的思路；程序是具体的，是算法的实现。
算法可以用自然语言、伪代码或流程图描述；程序需要用编程语言编写。
算法不依赖于编程语言；程序依赖于特定的编程语言和环境。
4.如何分析算法的时间复杂度?算法的时间复杂度仅与问题规模相关吗?、
分析时间复杂度：通过计算算法中基本操作的执行次数，用大O符号表示其增长趋势。
是否仅与问题规模相关：时间复杂度主要与问题规模（如输入大小）相关，但也可能受到其他因素影响，如输入数据的分布、算法的具体实现等。
练习题
一、单项选择题
1.在数据结构中，从逻辑上可以把数据结构分为 （)
A.紧凑结构和非紧凑结构
B.线性结构和非线性结构
C.内部结构和外部结构
D.动态结构和静态结构
2.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
3.算法分析的两个主要方面是（）
A.正确性和简明性
B.时间复杂性和空间复杂性
C.可读性和可维护性
D.数据复杂性和程序复杂性
4.线性表若采用链式存储结构存储时，要求内存中可用存储单元地址()
A.不一定连续的
B.部分地址必须是连续的
C.必须是连续的
D.一定是不连续的
5.算法指的是()
A.计算机程序
B.解决问题的计算方法
C.解决问题的有限运算序列
D.排序算法R
二、填空题
6.数据结构一般包括_____和______数据运算三个方面的内容。
答案：逻辑结构、存储结构
解析：
数据结构包括逻辑结构、存储结构和数据运算三个方面。
7.数据的逻辑结构可分为______、______两大类。
答案：线性结构、非线性结构
解析：
数据的逻辑结构分为线性结构（如数组、链表）和非线性结构（如树、图）。
8.数据的存储结构(物理结构)一般可以用_______、_______、______及散列存储等四种存储方法表示。
答案：顺序存储、链式存储、索引存储
解析：
数据的存储结构包括顺序存储、链式存储、索引存储和散列存储。
9.在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑_______及算法应易于理解、易于编程、易于调试等三点。
解、易于编程、易于调试等三点。
答案：时间复杂性和空间复杂性
解析：
在选用算法时，除了正确性外，还需要考虑时间复杂性和空间复杂性，以及算法的可读性和可操作性。
10.设有一批数据元素，为了最快地存取某元素，宜用_______结构存储，为了方便地插入一个元素，宜______用结构存储。
答案：顺序存储、链式存储
解析：
顺序存储支持随机访问，适合快速存取元素。
链式存储支持高效的插入和删除操作。
三、应用题
设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度。
11.
for (i = 1; i <= n; i++) { y = y + i; for (j = 1; j <= 2 * n; j++) { x = x + 1; } }
12.
s = 0; while (n >= (s + 1) * (s + 1)) { s = s + 1; }
13.
x = 1; sum = 0; for (i = 1; i <= n; i++) { x = x * i; sum = sum + x; }
14.
for (i = 1; i <= n; i++) { if (3 * i <= n) { for (j = 3 * i; j <= n; j++) { x++; y = 3 * x + 2; } } }
15
for (i = 1; i <= n; i++) { for (j = 1; j <= i; j++) { x = x + 1; } }
16.
sum = 0; i = 0; while (i <= 100) { sum = sum + i; i++; }
17.
x = 1; s = 0; for (i = 1; i <= n; i++) { ++x; s = s + x; } for (j = 1; j <= n; j++) { for (k = 1; k <= n; k++) { x++; s = s + x; } }
第2章 线性表
2.1 线性表的定义和基本运算
2.1.1线性表的逻辑定义
线性表的逻辑特性：
1. 元素之间是有序的，顺序由其在表中的位置决定。
2. 元素的数量是有限的（可以为空表）。
3. 元素的数据类型相同。
2.1.2线性表的基本运算
1. 初始化：
创建一个空的线性表。
示例：
void InitList(List *L);
2. 插入：
在线性表的指定位置插入一个新元素。
示例：
void InsertList(List *L, int pos, ElemType value);
说明：
pos 是插入位置，value 是插入的元素。
3. 删除：
删除线性表中指定位置的元素。
示例：
void DeleteList(List *L, int pos);
说明：
pos 是删除位置。
4. 查找：
在线性表中查找指定元素的位置。
示例：
int SearchList(List *L, ElemType value);
说明：
返回元素的位置，若未找到则返回 -1。
5. 获取元素：
获取线性表中指定位置的元素。
示例：
ElemType GetElem(List *L, int pos);
说明：
pos 是元素的位置。
6. 修改元素：
修改线性表中指定位置的元素。
示例：
void UpdateList(List *L, int pos, ElemType value);
说明：
pos 是修改位置，value 是新值。
7. 求长度：
返回线性表中元素的个数。
示例：
int LengthList(List *L);
8. 判断是否为空：
判断线性表是否为空。
示例：
int IsEmptyList(List *L);
9. 遍历：
依次访问线性表中的每个元素。
示例：
void TraverseList(List *L);
2.2 线性表的顺序存储和基本运算的实现
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素。顺序存储的线性表也称为 顺序表。顺序表的特点是逻辑上相邻的元素在物理存储上也相邻。
2.2.1线性表的顺序存储
定义：
顺序表是用数组实现的线性表，数组的每个元素存储线性表的一个数据元素。
顺序表的存储结构可以用以下公式表示：
特点：
优点：
随机访问效率高，通过下标可以直接访问元素。
存储密度高，不需要额外的存储空间。
缺点：
插入和删除操作需要移动大量元素，效率较低。
存储空间需要预先分配，可能导致空间浪费或不足。
2.2.2 顺序表上基本运算的实现
1. 插入运算
功能：
在顺序表的指定位置插入一个新元素。
步骤：
1. 检查插入位置是否合法。
2. 检查顺序表是否已满。
3. 将插入位置及其后的元素依次后移。
4. 插入新元素。
5. 更新顺序表长度。
代码实现：
void InsertList(List *L, int pos, ElemType value) { if (pos < 1 || pos > L->length + 1 || L->length == MAX_SIZE) { printf("插入位置无效或顺序表已满！\n"); return; } for (int i = L->length; i >= pos; i--) { L->data[i] = L->data[i - 1]; // 元素后移 } L->data[pos - 1] = value; // 插入元素 L->length++; // 长度加1 }
时间复杂度：
最好情况：O(1)（在表尾插入）。
最坏情况：O(n)（在表头插入）。
平均情况：O(n)。
2. 删除运算
功能：
删除顺序表中指定位置的元素。
步骤：
1. 检查删除位置是否合法。
2. 将删除位置后的元素依次前移。
3. 更新顺序表长度。
代码实现：
void DeleteList(List *L, int pos) { if (pos < 1 || pos > L->length) { printf("删除位置无效！\n"); return; } for (int i = pos; i < L->length; i++) { L->data[i - 1] = L->data[i]; // 元素前移 } L->length--; // 长度减1 }
时间复杂度：
最好情况：O(1)（删除表尾元素）。
最坏情况：O(n)（删除表头元素）。
平均情况：O(n)。
3. 顺序表上的其他运算举例
（1）查找元素
功能：
在顺序表中查找指定元素的位置。
代码实现：
int SearchList(List *L, ElemType value) { for (int i = 0; i < L->length; i++) { if (L->data[i] == value) { return i + 1; // 返回元素位置（从1开始） } } return -1; // 未找到 }
时间复杂度：
最好情况：O(1)（查找第一个元素）。
最坏情况：O(n)（查找最后一个元素或未找到）。
平均情况：O(n)。
（2）获取元素
功能：
获取顺序表中指定位置的元素。
代码实现：
ElemType GetElem(List *L, int pos) { if (pos < 1 || pos > L->length) { printf("位置无效！\n"); return -1; } return L->data[pos - 1]; }
时间复杂度：O(1)（随机访问）。
（3）修改元素
功能：
修改顺序表中指定位置的元素。
代码实现：
void UpdateList(List *L, int pos, ElemType value) { if (pos < 1 || pos > L->length) { printf("位置无效！\n"); return; } L->data[pos - 1] = value; }
时间复杂度：O(1)。
（4）求长度
功能：
返回顺序表的长度。
代码实现：
int LengthList(List *L) { return L->length; }
时间复杂度：
O(1)
（5）判断是否为空
功能：
判断顺序表是否为空。
代码实现：
int IsEmptyList(List *L) { return L->length == 0; }
时间复杂度：
O(1)
（6）遍历顺序表
功能：
依次访问顺序表中的每个元素。
代码实现：
void TraverseList(List *L) { for (int i = 0; i < L->length; i++) { printf("%d ", L->data[i]); } printf("\n"); }
时间复杂度：O(n)。
2.3 线性表的链式存储结构
链式存储结构通过指针将数据元素链接起来，形成一个链表。与顺序表不同，链表中的元素在内存中不必连续存储。链式存储结构包括单链表、循环链表和双向链表等。
2.3.1 单链表(线性链表)
定义：
单链表是由一组结点组成的链式存储结构，每个结点包含两个部分：
数据域：存储数据元素。
指针域：存储指向下一个结点的指针。
最后一个结点的指针域为 NULL，表示链表结束。
特点：
插入和删除操作效率高，不需要移动元素。
不支持随机访问，查找效率较低。
存储空间动态分配，不需要预先分配固定大小的内存。
2.3.2单链表上的基本运算
1. 建立单键表
（1） 头插法建表
方法：
新结点插入到链表的头部。
代码实现：
void CreateList_Head(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(Node)); // 创建头结点 (*L)->next = NULL; // 初始化为空表 for (int i = 0; i < n; i++) { Node *p = (Node *)malloc(sizeof(Node)); // 创建新结点 p->data = i + 1; // 赋值 p->next = (*L)->next; // 新结点指向头结点的下一个结点 (*L)->next = p; // 头结点指向新结点 } }
特点：
生成的链表顺序与输入顺序相反。
（2） 尾插法建表
方法：
新结点插入到链表的尾部。
代码实现：
void CreateList_Tail(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(Node)); // 创建头结点 Node *r = *L; // 尾指针指向头结点 for (int i = 0; i < n; i++) { Node *p = (Node *)malloc(sizeof(Node)); // 创建新结点 p->data = i + 1; // 赋值 r->next = p; // 尾结点的next指向新结点 r = p; // 尾指针指向新结点 } r->next = NULL; // 尾结点的next置为NULL }
特点：
生成的链表顺序与输入顺序相同。
2. 查找运算（带头结点）
（1） 按结点序号查找
功能：
查找链表中第 i 个结点。
代码实现：
Node *GetElem(LinkList L, int i) { int j = 1; Node *p = L->next; // 从第一个结点开始 while (p && j < i) { p = p->next; j++; } return p; // 返回第i个结点，若不存在则返回NULL }
（2） 按结点值查找
功能：
查找链表中值为value的结点。
代码实现：
Node *LocateElem(LinkList L, ElemType value) { Node *p = L->next; // 从第一个结点开始 while (p && p->data != value) { p = p->next; } return p; // 返回找到的结点，若未找到则返回NULL }
3. 插入运算
功能：
在链表的第 i 个位置插入一个新结点。
代码实现：
void InsertList(LinkList L, int i, ElemType value) { Node *p = L; int j = 0; while (p && j < i - 1) { // 找到第i-1个结点 p = p->next; j++; } if (!p || j > i - 1) { printf("插入位置无效！\n"); return; } Node *s = (Node *)malloc(sizeof(Node)); // 创建新结点 s->data = value; s->next = p->next; // 新结点指向第i个结点 p->next = s; // 第i-1个结点指向新结点 }
4. 删除运算
功能：
删除链表的第i 个结点。
代码实现：
void DeleteList(LinkList L, int i) { Node *p = L; int j = 0; while (p->next && j < i - 1) { // 找到第i-1个结点 p = p->next; j++; } if (!p->next || j > i - 1) { printf("删除位置无效！\n"); return; } Node *q = p->next; // q指向第i个结点 p->next = q->next; // 第i-1个结点指向第i+1个结点 free(q); // 释放第i个结点 }
5. 单链表上的运算举例
遍历链表：
void TraverseList(LinkList L) { Node *p = L->next; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); }
2.3.3循环链表
定义：
循环链表是单链表的变种，最后一个结点的指针域指向头结点，形成一个环。
特点：
可以从任意结点开始遍历整个链表。
适用于需要循环访问的场景。
2.3.4双向链表
定义：
双向链表的每个结点包含两个指针域：
前驱指针：指向前一个结点。
后继指针：指向后一个结点。
特点：
支持双向遍历，查找效率更高。
插入和删除操作需要同时修改前驱和后继指针。
2.4 顺序表和链表的比较
1. 时间性能
操作 顺序表 链表 访问元素 O(1)（随机访问，通过下标直接访问） O(n)O(n)（需要从头结点开始遍历） 插入/删除 O(n)O(n)（需要移动大量元素） O(1)O(1)（已知位置时，仅需修改指针） 查找元素 O(n)O(n)（顺序查找） O(n)O(n)（顺序查找） 动态扩容 O(n)O(n)（需要复制数据到新数组） O(1)O(1)（动态分配内存）
顺序表：
访问元素效率高，适合频繁读取的场景。
插入和删除效率低，因为需要移动大量元素。
链表：
插入和删除效率高，适合频繁修改的场景。
访问元素效率低，因为需要从头遍历。
2. 空间性能
性能 顺序表 链表 存储密度 高（只存储数据元素） 低（需要额外空间存储指针） 空间利用率 可能浪费空间（需预先分配固定大小） 动态分配，空间利用率高 内存分配 静态分配（数组）或动态分配（动态数组） 动态分配（每个结点单独分配）
顺序表：
存储密度高，空间利用率可能较低（需预先分配固定大小）。
动态数组可以缓解空间浪费问题，但扩容时可能产生额外开销。
链表：
存储密度低，因为每个结点需要额外空间存储指针。
空间利用率高，内存动态分配，按需使用。
小结…
思考与练习
思考题
1.什么是线性表?线性表的逻辑特征是什么?
定义
当n=0 时，线性表为空表。
逻辑特征：
元素之间是一对一的关系，即除了第一个元素和最后一个元素外，每个元素有且仅有一个直接前驱和一个直接后继。
元素之间的逻辑关系是线性的，因此称为线性表。
2.顺序表的特点是什么?顺序表上插入和删除一个结点的平均移动次数各是多少?
特点：
顺序表是用数组实现的线性表，元素在内存中连续存储。
优点：
随机访问效率高，通过下标可以直接访问元素。
存储密度高，不需要额外的存储空间。
缺点：
插入和删除操作需要移动大量元素，效率较低。
存储空间需要预先分配，可能导致空间浪费或不足。
平均移动次数：
插入：
删除：
3.链表中，头指针、头结点、开始结点各表示什么?有什么区别?
头指针：
指向链表中第一个结点的指针。
如果链表为空，头指针为NULL
头结点：
为了方便操作，在链表的第一个结点之前附加的一个结点。
头结点的数据域通常不存储有效数据，指针域指向开始结点。
开始结点：
链表中第一个存储有效数据的结点。
区别：
头指针是指向链表起始位置的指针。
头结点是为了简化操作而引入的辅助结点。
开始结点是链表中实际存储数据的第一个结点。
4.如何判断一个指针变量是指向单链表、单循环链表、双向循环链表的表尾结点?在单链表中，又是如何访问指针变量p所指结点的直接前趋结点?
判断表尾结点：
单链表：
表尾结点的指针域为 NULL。
单循环链表：
表尾结点的指针域指向头结点（或开始结点）。
双向循环链表：
表尾结点的后继指针指向头结点，头结点的前驱指针指向表尾结点。
访问直接前趋结点：
在单链表中，无法直接访问指针变量 p 所指结点的直接前趋结点，需要从头结点开始遍历，直到某个结点的指针域指向 p 所指结点。
5.理解如何分解或合并两个有序链表。
分解有序链表：
将一个有序链表拆分为两个子链表，通常根据某种条件（如奇偶位置、特定值等）进行拆分。
示例：
void SplitList(LinkList L, LinkList *L1, LinkList *L2) { Node *p = L->next; *L1 = (LinkList)malloc(sizeof(Node)); *L2 = (LinkList)malloc(sizeof(Node)); Node *r1 = *L1, *r2 = *L2; while (p) { if (p->data % 2 == 0) { // 根据条件拆分 r1->next = p; r1 = p; } else { r2->next = p; r2 = p; } p = p->next; } r1->next = NULL; r2->next = NULL; }
合并有序链表：
将两个有序链表合并为一个新的有序链表。
示例：
LinkList MergeList(LinkList L1, LinkList L2) { LinkList L = (LinkList)malloc(sizeof(Node)); Node *r = L; Node *p = L1->next, *q = L2->next; while (p && q) { if (p->data <= q->data) { r->next = p; r = p; p = p->next; } else { r->next = q; r = q; q = q->next; } } r->next = p ? p : q; // 将剩余部分链接到新链表 return L; }
练习题
一、单项选择题
1.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()
A.n-i+1
B.n-i
C.i
D.i-1
解析：
在第i个位置插入元素时，需要将第i个位置及其后的所有元素后移一位。
移动次数为n− i + 1
2.若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是()
A.1020
B.1010
C.1016
D.1024
解析：
第6个元素的存储地址 = 第一个元素的地址 + (6-1) × 每个元素占用的地址单元。
即：1000+5×4=1020。
3.带头结点的单链表(以head为头指针)为空的判断条件是()
A.head!=NULL
B.head->next==head
C.head->next==NULL
D.head==NULL
解析：
带头结点的单链表中，头结点的指针域指向第一个有效结点。
如果链表为空，头结点的指针域为 NULL。
4.在单循环链表中，p指向表中任一结点，判断表不是访问结束的条件是()
A. p!=NULL
B. p!=head
C. p->next!=head
D. p->next!=NULL
解析：
单循环链表的表尾结点的指针域指向头结点。
如果 p->next == head，说明 p 是表尾结点，访问结束。
因此，判断表不是访问结束的条件是 p->next != head。
5.在一个单链表中，已知q指向p所指向结点的前趋结点，若在q、p所指结点之间插入一个s所指向的新结点，则执行的的操作是()
A. q->next=s；s->next=p
B. p->next=s；s->next=q
C.s->next=p->next；p->next=s
D.p->next=s->next； s->next=p
解析：
在q和p之间插入s，需要将q的指针域指向s，s的指针域指向p。
即：q->next = s; s->next = p。
6.在一个单链表中，若删除p指向结点的后继结点，则执行的操作为()
A. q=p->next；p->next=p->next->next； free(q)
B. p=p->next；q=p->next； p=q->next； free(q)
C. q=p->next->next； p=p->next； free(q)
D. p=p->next->next； q=p->next； free(q)
解析：
删除p的后继结点，需要：
用q保存p的后继结点。
将p的指针域指向q的后继结点。
释放q的内存。
即：q = p->next; p->next = p->next->next; free(q)。
二、填空题
7.在一个长度为n的顺序表中删除第i个元素，需要向前移动____个元素。
答案：n−i
解析：
删除第i个元素后，需要将第i+1到第n个元素依次前移一位。
移动次数为 n−i。
8.在顺序表中插入或删除一个元素，需要平均移动____个元素，具体移动的元素个数与____有关。
答案：
具体移动的元素个数与 插入或删除的位置 有关。
解析：
插入或删除操作的平均移动次数为
移动次数取决于插入或删除的位置。
9.顺序表中逻辑上相邻的元素在物理存储位置上____相邻，链表结构中逻辑上相邻的元素在物理位置上___相邻。
答案：
顺序表中逻辑上相邻的元素在物理存储位置上 一定 相邻。
链表结构中逻辑上相邻的元素在物理位置上 不一定 相邻。
解析：
顺序表的元素在内存中连续存储。
链表的元素通过指针链接，物理位置可以不连续。
10.己知顺序表中一个元素的存储位置是x，每个元素占c字节，求其后继元素的存储位置计算公式为_____，而已而已知单链表中某一结点由p指向，求此后继结点存储地址的操作为_____.
答案：
顺序表后继元素的存储位置计算公式为：x+c。
单链表中求后继结点存储地址的操作为：p->next。
解析：
顺序表中元素连续存储，后继元素地址为当前元素地址加上元素大小。
单链表中通过指针域 next 访问后继结点。
11.在用p指针访问单链表时，判断不是访问结束的条件是______;在访问单循环链表时，判断不是访问表结束的条件是_____.
答案：
单链表：p != NULL。
单循环链表：p->next != head。
解析：
单链表的表尾结点指针域为 NULL。
单循环链表的表尾结点指针域指向头结点。
12.已知p指向双向链表的中间某个结点，从给定的操作语句中选择合适的填空。
(1)在p结点后插入s结点的语句序列是意单____.
(2)在p结点前插入s结点的语句序列是____.
(3)删除p结点的直接后继结点的语句序列是____.
(4)删除p结点的直接前趋结点的语句序列是____.
(5)删除p结点的语句序列是_____.
选项
A. p->next=s
B. p->prior=s
C. s->next=p
D. s->prior-p0
E. p->next-p->next->next
F. p->prior-p->prior->prior
G. p->next->prior=s
H. p->prior->next=s
I. s->next=p->next
J. q-p->next
K. q-p->prior
L. free(p)
M. free(q)
N. s->prior-p->prior
O. p->prior->next-p->next
P. p->prior->prior->next=p
Q. p->next->next->prior=p
R. p->next->prior-p->prior
答案：
(1) 在p结点后插入s结点的语句序列是：I, G, A。
s->next = p->next; p->next->prior = s; p->next = s;
(2) 在p结点前插入s结点的语句序列是：N, H, B。
s->prior = p->prior; p->prior->next = s; p->prior = s;
(3) 删除p结点的直接后继结点的语句序列是：J, E, M。
q = p->next; p->next = p->next->next; free(q);
(4) 删除p结点的直接前趋结点的语句序列是：K, F, M。
q = p->prior; p->prior = p->prior->prior; free(q);
(5) 删除p结点的语句序列是：O, R, L。
p->prior->next = p->next; p->next->prior = p->prior; free(p);
13.下面是一个在带头结点的单链表 head 中删除所有数据域值为x的结点的算法，但不完善，请在相应的地方填上适当的语句，使之成为完整的算法。
void DeleX(LinkList head，DataType x) { LinkNode *p,*q,*s; p-head；q-p->next; while(g!=NULL) if(q->data==x){ s=q; q=q->next； free(s);(1) else{ p=q;(2) } }
答案：
(1)
p->next = q;
(2)
q = q->next;
完整算法：
void DeleX(LinkList head, DataType x) { LinkNode *p, *q, *s; p = head; q = p->next; while (q != NULL) { if (q->data == x) { s = q; q = q->next; p->next = q; // (1) 将p的next指向q free(s); } else { p = q; // (2) 移动p到q的位置 q = q->next; // (2) 移动q到下一个结点 } } }
三、算法设计题
14.设有两个顺序表A和B，且都递增有序。试写一算法，从A中删除与B中相同的那些元素(也就是计算A-B)。
算法思路：
使用两个指针 i 和 j 分别遍历顺序表A和B。
比较A[i]和B[j]的值：
如果A[i] < B[j]，说明A[i]不在B中，保留A[i]，i 向后移动。
如果A[i] == B[j]，说明A[i]在B中，删除A[i]。
如果A[i] > B[j]，j 向后移动。
重复上述步骤直到其中一个顺序表遍历完毕。
代码实现：
void SubtractList(int A[], int *lenA, int B[], int lenB) { int i = 0, j = 0, k = 0; while (i < *lenA && j < lenB) { if (A[i] < B[j]) { A[k++] = A[i++]; // 保留A中的元素 } else if (A[i] > B[j]) { j++; // 跳过B中的元素 } else { i++; // 跳过A和B中相同的元素 j++; } } while (i < *lenA) { A[k++] = A[i++]; // 将A中剩余元素复制到结果中 } *lenA = k; // 更新A的长度 }
15.已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。试写一算法，将p所指向的结点与其后继结点位置交换。
算法思路：
找到结点p的后继结点 p_next。
将p的 next 指针指向 p_next 的后继结点。
将 p_next 的 next 指针指向p。
更新p的前驱结点的 next 指针，使其指向 p_next。
代码实现：
void SwapNode(LinkList head, LinkNode *p) { if (p == NULL || p->next == NULL) { return; // p为空或p是尾结点，无法交换 } LinkNode *q = p->next; // q是p的后继结点 LinkNode *pre = head; // pre是p的前驱结点 while (pre->next != p) { pre = pre->next; } // 交换p和q pre->next = q; p->next = q->next; q->next = p; }
16.已知两单链表A和Ｂ分别表示两个集合，其元素值递增有序。试写一算法，求A和Ｂ的交集C，要求C同样以元素值递增的单链表形式存储。
算法思路：
使用两个指针 p 和 q 分别遍历链表A和B。
比较 p 和 q 的值：
如果 p.val < q.val，p 向后移动。
如果 p.val > q.val，q 向后移动。
如果 p.val == q.val，将该值加入到结果链表C中，并同时移动 p 和 q。
重复上述步骤直到其中一个链表遍历完毕。
代码实现：
LinkList IntersectionList(LinkList A, LinkList B) { LinkList C = (LinkList)malloc(sizeof(Node)); // 创建C的头结点 C->next = NULL; LinkNode *r = C; // r指向C的尾结点 LinkNode *p = A->next, *q = B->next; while (p != NULL && q != NULL) { if (p->data < q->data) { p = p->next; // p指向较小的元素，向后移动 } else if (p->data > q->data) { q = q->next; // q指向较小的元素，向后移动 } else { // 找到交集元素，插入到C中 LinkNode *s = (LinkNode *)malloc(sizeof(Node)); s->data = p->data; s->next = NULL; r->next = s; r = s; p = p->next; q = q->next; } } return C; }
17.设有一个带头结点的双向循环链表，head 为链表的头指针。试写一算法，实现在值为x的结点之前插入一个值为y的结点。
算法思路：
遍历链表，找到值为x的结点 target。
创建一个新结点 new_node，值为y。
将 new_node 插入到 target 之前：
new_node.prev = target.prev
new_node.next = target
target.prev.next = new_node
target.prev = new_node
代码实现：
void InsertBeforeX(DLinkList head, int x, int y) { DLinkNode *p = head->next; // p指向第一个结点 while (p != head && p->data != x) { p = p->next; // 查找值为x的结点 } if (p == head) { return; // 未找到值为x的结点 } // 创建新结点 DLinkNode *s = (DLinkNode *)malloc(sizeof(DLinkNode)); s->data = y; // 插入新结点 s->prior = p->prior; s->next = p; p->prior->next = s; p->prior = s; }
第3章 栈和队列
3.1栈
栈（Stack）是一种特殊的线性表，其特点是 后进先出（LIFO, Last In First Out）。栈的所有操作都只能在表的一端进行，这一端称为 栈顶，另一端称为 栈底。
3.1.1栈的定义及其运算
栈定义
栈是一种只允许在表的一端进行插入和删除操作的线性表。
栈顶（Top）：允许插入和删除的一端。
栈底（Bottom）：不允许操作的一端。
运算
1. 判栈空：
判断栈是否为空。
若栈顶指针指向栈底，则栈为空。
2. 置空栈：
将栈清空，栈顶指针指向栈底。
3. 判栈满：
判断栈是否已满（仅适用于顺序栈）。
若栈顶指针达到最大容量，则栈满。
4. 进栈（Push）：
将元素插入栈顶。
5. 退栈（Pop）：
删除栈顶元素并返回其值。
6. 取栈顶元素（GetTop）：
返回栈顶元素的值，但不删除它。
3.1.2栈的存储表示和实现
1. 栈的顺序存储结构
使用数组实现栈的顺序存储结构。
需要定义一个栈顶指针 top，初始值为 -1（表示栈空）。
定义：
#define MAX_SIZE 100 // 栈的最大容量 typedef struct { int data[MAX_SIZE]; // 存储栈元素的数组 int top; // 栈顶指针 } SeqStack;
2. 顺序栈基本运算的实现
初始化栈：
void InitStack(SeqStack *S) { S->top = -1; // 栈顶指针初始化为-1 }
判栈空：
int IsEmpty(SeqStack *S) { return S->top == -1; }
判栈满：
int IsFull(SeqStack *S) { return S->top == MAX_SIZE - 1; }
进栈：
void Push(SeqStack *S, int value) { if (IsFull(S)) { printf("栈已满，无法进栈！\n"); return; } S->data[++(S->top)] = value; // 栈顶指针加1，插入元素 }
退栈：
int Pop(SeqStack *S) { if (IsEmpty(S)) { printf("栈为空，无法退栈！\n"); return -1; } return S->data[(S->top)--]; // 返回栈顶元素，栈顶指针减1 }
取栈顶元素：
int GetTop(SeqStack *S) { if (IsEmpty(S)) { printf("栈为空，无栈顶元素！\n"); return -1; } return S->data[S->top]; // 返回栈顶元素 }
3. 栈的链式存储结构及基本操作
使用链表实现栈的链式存储结构。
链栈的栈顶是链表的头结点。
定义：
typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } LinkStackNode, *LinkStack;
初始化栈：
void InitLinkStack(LinkStack *S) { *S = NULL; // 栈顶指针初始化为NULL }
判栈空：
int IsLinkStackEmpty(LinkStack S) { return S == NULL; }
进栈：
void PushLinkStack(LinkStack *S, int value) { LinkStackNode *p = (LinkStackNode *)malloc(sizeof(LinkStackNode)); p->data = value; p->next = *S; // 新结点指向原栈顶 *S = p; // 栈顶指针指向新结点 }
退栈：
int PopLinkStack(LinkStack *S) { if (IsLinkStackEmpty(*S)) { printf("栈为空，无法退栈！\n"); return -1; } LinkStackNode *p = *S; // p指向栈顶结点 int value = p->data; // 保存栈顶元素的值 *S = p->next; // 栈顶指针指向下一个结点 free(p); // 释放原栈顶结点 return value; }
取栈顶元素：
int GetLinkStackTop(LinkStack S) { if (IsLinkStackEmpty(S)) { printf("栈为空，无栈顶元素！\n"); return -1; } return S->data; // 返回栈顶元素的值 }
3.2栈的应用举例列
3.2.1圆括号匹配的检验
问题描述：
给定一个字符串，判断其中的圆括号是否匹配。
例如：(()()) 是匹配的，(() 是不匹配的。
算法思路：
初始化一个空栈。
遍历字符串中的每个字符：
如果遇到 (，将其压入栈。
如果遇到 )，弹出栈顶元素。如果栈为空，则括号不匹配。
遍历结束后，如果栈为空，则括号匹配；否则不匹配。
代码实现：
#include <stdio.h> #include <stdbool.h> #include <string.h> bool isParenthesesMatch(char *str) { int top = -1; // 栈顶指针 for (int i = 0; i < strlen(str); i++) { if (str[i] == '(') { top++; // 模拟压栈 } else if (str[i] == ')') { if (top == -1) { return false; // 栈为空，不匹配 } top--; // 模拟弹栈 } } return top == -1; // 栈为空则匹配 } int main() { char str[] = "(()())"; if (isParenthesesMatch(str)) { printf("括号匹配！\n"); } else { printf("括号不匹配！\n"); } return 0; }
3.2.2字符串回文的判断
问题描述：
判断一个字符串是否是回文（正读和反读相同）。
例如："abba" 是回文，"abc" 不是回文。
算法思路：
将字符串的前半部分压入栈。
遍历字符串的后半部分，与栈顶元素比较：
如果相等，弹出栈顶元素。
如果不等，则不是回文。
如果栈为空，则是回文。
代码实现：
#include <stdio.h> #include <stdbool.h> #include <string.h> bool isPalindrome(char *str) { int len = strlen(str); int top = -1; // 栈顶指针 char stack[len / 2]; // 栈 for (int i = 0; i < len / 2; i++) { stack[++top] = str[i]; // 压栈 } int start = (len + 1) / 2; // 后半部分起始位置 for (int i = start; i < len; i++) { if (stack[top--] != str[i]) { // 弹栈并比较 return false; } } return true; } int main() { char str[] = "abba"; if (isPalindrome(str)) { printf("是回文！\n"); } else { printf("不是回文！\n"); } return 0; }
3.2.3数制转换
问题描述：
将一个十进制数转换为其他进制（如二进制、八进制、十六进制）。
算法思路：
将十进制数不断除以目标进制，将余数压入栈。
最后将栈中的余数依次弹出，得到转换结果。
代码实现：
#include <stdio.h> void convert(int num, int base) { int stack[100], top = -1; // 栈 while (num > 0) { stack[++top] = num % base; // 压栈 num /= base; } while (top != -1) { printf("%d", stack[top--]); // 弹栈并输出 } printf("\n"); } int main() { int num = 10, base = 2; printf("十进制数 %d 转换为 %d 进制为：", num, base); convert(num, base); return 0; }
3.2.4栈与递归
问题描述：
递归函数的调用过程可以用栈来模拟。
例如：计算阶乘 n!。
算法思路：
将递归函数的参数和返回地址压入栈。
每次递归调用时，从栈中弹出参数并执行。
递归结束时，从栈中弹出返回地址并返回结果。
代码实现：
#include <stdio.h> int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); // 递归调用 } int main() { int n = 5; printf("%d! = %d\n", n, factorial(n)); return 0; }
3.3队列
队列（Queue）是一种特殊的线性表，其特点是 先进先出（FIFO, First In First Out）。队列的所有操作都只能在表的两端进行，插入操作在队尾（Rear），删除操作在队头（Front）。
3.3.1队列的定义及其运算·
1. 队列的定义
队列是一种只允许在表的一端进行插入操作（队尾），在另一端进行删除操作（队头）的线性表。
队头（Front）：允许删除的一端。
队尾（Rear）：允许插入的一端。
2. 队列的运算
初始化队列：
创建一个空队列。
判队列空：
判断队列是否为空。
判队列满：
判断队列是否已满（仅适用于顺序队列）。
入队（Enqueue）：
将元素插入队尾。
出队（Dequeue）：
删除队头元素并返回其值。
取队头元素（GetFront）：
返回队头元素的值，但不删除它。
3.3.2顺序循环队列
顺序队列使用数组实现，但由于普通顺序队列存在“假溢出”问题（即队列未满但无法插入新元素），通常采用 循环队列 来解决。
1. 循环队列的定义
使用数组实现队列，将数组的首尾相连，形成一个环形结构。
需要两个指针：
front：指向队头元素。
rear：指向队尾元素的下一个位置。
队列空：front == rear。
队列满：(rear + 1) % MAX_SIZE == front。
2. 循环队列的实现
定义：
#define MAX_SIZE 100 // 队列的最大容量 typedef struct { int data[MAX_SIZE]; // 存储队列元素的数组 int front; // 队头指针 int rear; // 队尾指针 } SeqQueue;
初始化队列：
void InitQueue(SeqQueue *Q) { Q->front = Q->rear = 0; // 队头和队尾指针初始化为0 }
判队列空：
int IsEmpty(SeqQueue *Q) { return Q->front == Q->rear; }
判队列满：
int IsFull(SeqQueue *Q) { return (Q->rear + 1) % MAX_SIZE == Q->front; }
入队：
void Enqueue(SeqQueue *Q, int value) { if (IsFull(Q)) { printf("队列已满，无法入队！\n"); return; } Q->data[Q->rear] = value; // 插入元素 Q->rear = (Q->rear + 1) % MAX_SIZE; // 队尾指针后移 }
出队：
int Dequeue(SeqQueue *Q) { if (IsEmpty(Q)) { printf("队列为空，无法出队！\n"); return -1; } int value = Q->data[Q->front]; // 保存队头元素 Q->front = (Q->front + 1) % MAX_SIZE; // 队头指针后移 return value; }
取队头元素：
int GetFront(SeqQueue *Q) { if (IsEmpty(Q)) { printf("队列为空，无队头元素！\n"); return -1; } return Q->data[Q->front]; // 返回队头元素 }
3.3.3链队列
链队列使用链表实现，适合元素数量动态变化的场景。
1.链队列的定义
使用链表实现队列，队头指针指向链表的第一个结点，队尾指针指向链表的最后一个结点。
定义：
typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } LinkQueueNode; typedef struct { LinkQueueNode *front; // 队头指针 LinkQueueNode *rear; // 队尾指针 } LinkQueue;
2.链队列的实现
初始化队列：
void InitLinkQueue(LinkQueue *Q) { Q->front = Q->rear = (LinkQueueNode *)malloc(sizeof(LinkQueueNode)); // 创建头结点 Q->front->next = NULL; // 初始化为空队列 }
判队列空：
int IsLinkQueueEmpty(LinkQueue *Q) { return Q->front == Q->rear; }
入队：
void EnLinkQueue(LinkQueue *Q, int value) { LinkQueueNode *p = (LinkQueueNode *)malloc(sizeof(LinkQueueNode)); p->data = value; p->next = NULL; Q->rear->next = p; // 新结点插入队尾 Q->rear = p; // 队尾指针指向新结点 }
出队：
int DeLinkQueue(LinkQueue *Q) { if (IsLinkQueueEmpty(Q)) { printf("队列为空，无法出队！\n"); return -1; } LinkQueueNode *p = Q->front->next; // p指向队头结点 int value = p->data; // 保存队头元素的值 Q->front->next = p->next; // 队头指针指向下一个结点 if (Q->rear == p) { Q->rear = Q->front; // 如果队列只有一个结点，出队后队列为空 } free(p); // 释放队头结点 return value; }
取队头元素
int GetLinkQueueFront(LinkQueue *Q) { if (IsLinkQueueEmpty(Q)) { printf("队列为空，无队头元素！\n"); return -1; } return Q->front->next->data; // 返回队头元素的值 }
3.4栈和队列的应用实例
3.4.1中缀表达式到后缀表达式的转换
1. 问题描述
中缀表达式：运算符位于两个操作数之间，例如 A + B * C。
后缀表达式：运算符位于两个操作数之后，例如 A B C * +。
将中缀表达式转换为后缀表达式，便于计算机计算。
2. 算法思路
初始化一个空栈和一个空输出队列。
从左到右扫描中缀表达式：
如果遇到操作数，直接加入输出队列。
如果遇到左括号 (，压入栈。
如果遇到右括号 )，将栈顶元素弹出并加入输出队列，直到遇到左括号 (。
如果遇到运算符：
将栈中优先级高于或等于当前运算符的运算符弹出并加入输出队列。
将当前运算符压入栈。
扫描结束后，将栈中剩余的运算符依次弹出并加入输出队列。
输出队列中的内容即为后缀表达式。
3. 代码实现
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX_SIZE 100 // 定义栈结构 typedef struct { char data[MAX_SIZE]; int top; } Stack; // 初始化栈 void InitStack(Stack *S) { S->top = -1; } // 判栈空 int IsEmpty(Stack *S) { return S->top == -1; } // 判栈满 int IsFull(Stack *S) { return S->top == MAX_SIZE - 1; } // 进栈 void Push(Stack *S, char value) { if (IsFull(S)) { printf("栈已满，无法进栈！\n"); return; } S->data[++(S->top)] = value; } // 退栈 char Pop(Stack *S) { if (IsEmpty(S)) { printf("栈为空，无法退栈！\n"); return '\0'; } return S->data[(S->top)--]; } // 取栈顶元素 char GetTop(Stack *S) { if (IsEmpty(S)) { printf("栈为空，无栈顶元素！\n"); return '\0'; } return S->data[S->top]; } // 获取运算符优先级 int GetPriority(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; default: return 0; } } // 中缀表达式转后缀表达式 void InfixToPostfix(char *infix, char *postfix) { Stack S; InitStack(&S); int i = 0, j = 0; while (infix[i] != '\0') { if (isalnum(infix[i])) { // 操作数直接加入输出 postfix[j++] = infix[i++]; } else if (infix[i] == '(') { // 左括号压栈 Push(&S, infix[i++]); } else if (infix[i] == ')') { // 右括号弹出栈中元素直到左括号 while (!IsEmpty(&S) && GetTop(&S) != '(') { postfix[j++] = Pop(&S); } Pop(&S); // 弹出左括号 i++; } else { // 运算符 while (!IsEmpty(&S) && GetPriority(GetTop(&S)) >= GetPriority(infix[i])) { postfix[j++] = Pop(&S); } Push(&S, infix[i++]); } } while (!IsEmpty(&S)) { // 弹出栈中剩余运算符 postfix[j++] = Pop(&S); } postfix[j] = '\0'; // 添加字符串结束符 } int main() { char infix[] = "A+B*C-(D/E+F)*G"; char postfix[MAX_SIZE]; InfixToPostfix(infix, postfix); printf("中缀表达式: %s\n", infix); printf("后缀表达式: %s\n", postfix); return 0; }
3.4.2后缀表达式的计算
1. 问题描述
后缀表达式：运算符位于两个操作数之后，例如 A B C * +。
计算后缀表达式的值。
2. 算法思路
初始化一个空栈。
从左到右扫描后缀表达式：
如果遇到操作数，压入栈。
如果遇到运算符，弹出栈顶的两个操作数，进行运算，并将结果压入栈。
扫描结束后，栈中剩余的元素即为计算结果。
3. 代码实现
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX_SIZE 100 // 定义栈结构 typedef struct { int data[MAX_SIZE]; int top; } Stack; // 初始化栈 void InitStack(Stack *S) { S->top = -1; } // 判栈空 int IsEmpty(Stack *S) { return S->top == -1; } // 判栈满 int IsFull(Stack *S) { return S->top == MAX_SIZE - 1; } // 进栈 void Push(Stack *S, int value) { if (IsFull(S)) { printf("栈已满，无法进栈！\n"); return; } S->data[++(S->top)] = value; } // 退栈 int Pop(Stack *S) { if (IsEmpty(S)) { printf("栈为空，无法退栈！\n"); return -1; } return S->data[(S->top)--]; } // 计算后缀表达式 int EvaluatePostfix(char *postfix) { Stack S; InitStack(&S); int i = 0; while (postfix[i] != '\0') { if (isdigit(postfix[i])) { // 操作数压栈 Push(&S, postfix[i] - '0'); } else { // 运算符 int op2 = Pop(&S); int op1 = Pop(&S); switch (postfix[i]) { case '+': Push(&S, op1 + op2); break; case '-': Push(&S, op1 - op2); break; case '*': Push(&S, op1 * op2); break; case '/': Push(&S, op1 / op2); break; } } i++; } return Pop(&S); // 返回计算结果 } int main() { char postfix[] = "23*4+"; int result = EvaluatePostfix(postfix); printf("后缀表达式: %s\n", postfix); printf("计算结果: %d\n", result); return 0; }
小结
思考与练习
思考与练习
思考题
1.栈和队列的特点各是什么?
栈：
特点：后进先出（LIFO, Last In First Out）。
操作：只能在栈顶进行插入（Push）和删除（Pop）操作。
应用：函数调用栈、表达式求值、括号匹配等。
队列：
特点：先进先出（FIFO, First In First Out）。
操作：在队尾插入（Enqueue），在队头删除（Dequeue）。
应用：任务调度、缓冲区管理、广度优先搜索（BFS）等。
2.链栈为什么不设头指针?
链栈：
链栈的栈顶是链表的头结点，栈顶指针直接指向链表的第一个结点。
插入和删除操作都在栈顶进行，因此不需要头指针。
原因：
链栈的操作集中在栈顶，头指针的作用被栈顶指针取代。
链栈的栈顶指针已经足够支持所有操作，头指针是多余的。
3.循环队列的优点是什么?如何判断队空和队满?
优点：
解决普通顺序队列的“假溢出”问题，充分利用数组空间。
入队和出队操作的时间复杂度均为 O(1)。
判断队空和队满：
队空：front == rear。
队满：(rear + 1) % MAX_SIZE == front。
注意：循环队列通常会牺牲一个存储单元来区分队空和队满。
4.一般情况下，链队列的出队操作为什么要删除头结点而不是队头结点?
链队列的结构：
链队列通常包含一个头结点（不存储数据），队头指针指向头结点，队尾指针指向最后一个结点。
出队操作：
出队操作删除的是队头结点的下一个结点（即实际存储数据的第一个结点）。
头结点的作用是简化操作，避免队空时队头指针和队尾指针的特殊处理。
原因：
删除头结点会导致队头指针和队尾指针的混乱，增加操作复杂性。
删除队头结点的下一个结点可以保持队列结构的完整性。
5.设用一个单循环链表来表示一个长度为n的链队列，若只设头指针，则入队操作算法的时间复杂度为何?若只设尾指针呢?
只设头指针：
入队操作需要找到链表的尾结点，时间复杂度为 O(n)。
因为需要从头指针开始遍历整个链表。
只设尾指针：
入队操作直接在尾结点后插入新结点，时间复杂度为 O(1)。
因为尾指针可以直接访问链表的尾结点。
练习题
一、单项选择题
在下列各题的备选答案中选出一个正确答案，并将其代号(A，B，C，D中的一个)填写在题目后面的方括号内。
1.栈的操作原则是()
A.顺序进出
B.后进后出
C.后进先出
D.先进先出
2.(2002年试题)进栈序列为 a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为()
A.4
B.5
C.6
D.7
序列 c, a, b 的分析：
要得到 c 作为第一个出栈元素，必须先将 a, b, c 全部入栈，然后 c 出栈。
此时栈中剩余元素为 a, b，且 b 在栈顶。
接下来如果要出栈 a，必须先出栈 b，因此无法直接出栈 a。
因此，c, a, b 是不可能通过合法的入栈和出栈操作得到的序列。
对于进栈序列 a, b, c，合法的出栈序列有：
a, b, c：
操作：a 入栈 → a 出栈 → b 入栈 → b 出栈 → c 入栈 → c 出栈。
a, c, b：
操作：a 入栈 → a 出栈 → b 入栈 → c 入栈 → c 出栈 → b 出栈。
b, a, c：
操作：a 入栈 → b 入栈 → b 出栈 → a 出栈 → c 入栈 → c 出栈。
b, c, a：
操作：a 入栈 → b 入栈 → b 出栈 → c 入栈 → c 出栈 → a 出栈。
c, b, a：
操作：a 入栈 → b 入栈 → c 入栈 → c 出栈 → b 出栈 → a 出栈。
3. 按字母a，b，c，d，e顺序入栈，则出栈的输出序列不可能是()
A. decba
操作步骤：
1. 入栈 a, b, c, d。
2. 出栈 d。
3. 入栈 e。
4. 出栈 e, c, b, a。
B. dceab
操作步骤：
入栈 a, b, c, d。
出栈 d。
出栈 c。
入栈 e。
出栈 e。
出栈 a, b。
问题：
在出栈 c 后，栈中剩余元素为 a, b。
要出栈 a，必须先出栈 b，因此无法直接出栈 a。
C. abcde
操作步骤：
1. 入栈 a，出栈 a。
2. 入栈 b，出栈 b。
3. 入栈 c，出栈 c。
4. 入栈 d，出栈 d。
5. 入栈 e，出栈 e。
D. edcba
操作步骤：
1. 入栈 a, b, c, d, e。
2. 出栈 e, d, c, b, a。
推广到一般情况
合法的出栈序列
定义：
给定一个进栈序列，如果存在一种入栈和出栈的操作顺序，使得最终得到的出栈序列与给定的序列一致，则称该序列是合法的。
否则，该序列是不合法的。
规则：
1. 元素必须按照进栈顺序依次入栈。
2. 出栈时，只能从栈顶弹出元素。
3. 出栈序列中的元素顺序必须与栈的操作规则一致。
对于长度为 n 的进栈序列，合法的出栈序列的数量为 卡特兰数（Catalan Number），其公式为：
4.判断一个顺序栈st(最多元素为 StackSize)为栈满的条件表达式是()
A. st.top !=StackSize
B. st.top!=0
C.st.top==-1
D. st.top == StackSize-1
5.在向顺序栈中压入元素时()
A.先存入元素，后移动栈顶指针
B.谁先谁后无关紧要
C.先移动栈顶指针，后压入元素
D.同时进行
6.一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是()
A. 9，7，5，3，1
B. 1，3，5，7，9
C. 1，5，9，3，7
D. 9，5，1，7，3
7.判断一个顺序队列sq(最多元素为QueueSize)为空队列的条件表达式是()
A. sq.rear==sq.front
B. sq.rear==0
C. sq.front ==QueueSize
D. sq.rear==QueueSize+1
8.判断一个循环队列cq(最多元素为QueueSize))为满队列的条件表达式是()
A. cq.rear==cq.front
B. cq.rear==QueueSize
C. (cq.rear+1)%QueueSize=cq.front
循环队列满的条件是队尾指针 rear 的下一个位置是队头指针 front，即 (rear + 1) % QueueSize == front。
D.cq.rear%QueueSize+1=cq.front
二、填空题
9.假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为____。
答案：b, c, e, d, a
解析：
操作步骤：
S (a 入栈) → 栈：[a]
S (b 入栈) → 栈：[a, b]
X (b 出栈) → 输出：b → 栈：[a]
S (c 入栈) → 栈：[a, c]
X (c 出栈) → 输出：c → 栈：[a]
S (d 入栈) → 栈：[a, d]
S (e 入栈) → 栈：[a, d, e]
X (e 出栈) → 输出：e → 栈：[a, d]
X (d 出栈) → 输出：d → 栈：[a]
X (a 出栈) → 输出：a → 栈：[]
输出序列：b, c, e, d, a
10. 假设 S.data[maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。能做进栈操作的条件是_____；如要把栈顶元素弹出到x中，需执行下列语句：____.
答案：
能做进栈操作的条件是：top < maxsize - 1。
弹出栈顶元素的语句：x = S.data[top--];
解析：
进栈操作的条件是栈未满，即 top < maxsize - 1。
弹出栈顶元素时，先将栈顶元素赋值给 x，然后将 top 减1。
11.设顺序栈存放在 S.data[maxsize]中，栈底位置是maxsize-1，则栈空条件是____;栈满条件是____.
答案：
栈空条件是：top == maxsize - 1。
栈满条件是：top == -1。
解析：
栈底位置是 maxsize - 1，栈顶指针 top 从 maxsize - 1 开始向下移动。
栈空时，top 指向栈底，即 top == maxsize - 1。
栈满时，top 指向栈顶，即 top == -1。
12.若循环队列用数组 data[m]存储元素值，用front 和 rear 分别作为头尾指针，则当前元素个数为_____.
答案：(rear - front + m) % m
解析：
循环队列的元素个数计算公式为：(rear - front + m) % m。
其中 m 是数组的长度。
13.栈和队列都是____结构；对于栈，只能在____插入和删除元素；对于队列，只能在____插入元素，在____删除元素。
答案：
栈和队列都是 线性 结构。
对于栈，只能在 栈顶 插入和删除元素。
对于队列，只能在 队尾 插入元素，在 队头 删除元素。
解析：
栈是后进先出（LIFO）结构，队列是先进先出（FIFO）结构。
14.从循环队列中删除一个元素时，其操作是先_____，后_____。
答案：
先 取出队头元素，后 移动队头指针。
解析：
删除元素时，先取出队头元素，然后将队头指针 front 后移一位（front = (front + 1) % m）。
三、解答题
15.如果编号为1，2，3的3辆列车进入一个栈式结构的站台，那么可能得到的3辆列车的出站序列有哪些?不可能出现的序列是什么?
可能的出站序列：
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 2, 1
不可能出现的序列：
3, 1, 2
解析：
栈是后进先出（LIFO）结构，编号为3的列车不可能在编号为1的列车之前出站。
16.假设输入栈的元素为a、b、c，在栈Ｓ的输出端得到一个输出序列为a、b、c，试写出在输入端所有可能的输入序列。
可能的输入序列：
a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
解析：
输出序列为 a, b, c，说明 a 是第一个出栈的元素，因此 a 必须是第一个入栈的元素。
可能的输入序列需要满足 a 在 b 和 c 之前入栈。
17.简述下面所给算法的功能(假设栈元素为整数类型)。
(1)
void ex31(SeqStack *S) { int A[80], i, n; n = 0; while (!empty(S)) { A[n] = pop(S); n++; } for (i = 0; i < n; i++) push(S, A[i]); }
功能：
将栈 S 中的元素依次弹出并存入数组 A，然后将数组 A 中的元素依次压回栈 S。
最终栈 S 的元素顺序与原来相同。
总结：
该算法实现了栈的 逆序存储，但最终栈的顺序不变。
(2)
void ex32(SeqStack *S, int c) { SeqStack T; int d; while (!StackEmpty(S)) { d = pop(S); if (d != c) push(T, d); } while (!StackEmpty(T)) { d = pop(T); push(S, d); } }
功能：
从栈 S 中弹出所有元素，将不等于 c 的元素压入临时栈 T。
然后将临时栈 T 中的元素依次压回栈 S。
总结：
该算法删除了栈 S 中所有值为 c 的元素，其余元素的顺序不变。
18.写出下列程序段的输出结果(栈结点数据域为字符型 char)。
SeqStack S; char x, y; x = 'C'; y = 'k'; push(S, x); push(S, 'a'); push(S, y); x = pop(S); push(S, 't'); push(S, x); x = pop(S); push(S, 's'); while (!StackEmpty(S)) { y = pop(S); putchar(y); } putchar(x);
输出结果：
stack
解析：
初始状态：栈 S 为空。
push(S, x)：x = 'C' → 栈：[C]
push(S, 'a') → 栈：[C, a]
push(S, y)：y = 'k' → 栈：[C, a, k]
x = pop(S)：x = 'k' → 栈：[C, a]
push(S, 't') → 栈：[C, a, t]
push(S, x)：x = 'k' → 栈：[C, a, t, k]
x = pop(S)：x = 'k' → 栈：[C, a, t]
push(S, 's') → 栈：[C, a, t, s]
while 循环：
y = pop(S)：y = 's' → 输出 s → 栈：[C, a, t]
y = pop(S)：y = 't' → 输出 t → 栈：[C, a]
y = pop(S)：y = 'a' → 输出 a → 栈：[C]
y = pop(S)：y = 'C' → 输出 C → 栈：[]
putchar(x)：x = 'k' → 输出 k
最终输出：stack
19.在循环队列的顺序存储结构下，分别写出入队(插入元素)、出队(删除元素)时修改队尾、队头指针的操作语句以及求队列长度的公式。
入队操作：
rear = (rear + 1) % m; // 队尾指针后移 data[rear] = value; // 插入元素
出队操作：
front = (front + 1) % m; // 队头指针后移 value = data[front]; // 删除元素
队列长度公式：
length = (rear - front + m) % m;
四、算法设计题
20.利用两个栈S1和S2模拟一个队列，如何用栈的运算来实现队列的插入和删除运算?试写出算法。
21.试设计一个算法，实现输入一字符串并检查字符串中是否含有圆括号，当圆括号匹配时输出括号内的字符串，否则给出出错信息(提示：利用栈记录左括号出现后的字符)。