当前位置：文档之家 › 数据结构(C语言版)朱昌杰

数据结构(C语言版)朱昌杰

  • 格式：pdf
  • 大小：661.74 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构C语言版第2版课后习题答案17888

数据结构C语言版第2版课后习题答案17888

数据结构(C语言版）(第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (14)第4章串、数组和广义表 (27)第5章树和二叉树 (34)第6章图 (44)第7章查找 (56)第8章排序 (67)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素:是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下,数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局(状态）、图中的一个顶点等.数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象:是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2,…}，字母字符数据对象是集合C=｛‘A’，‘B’,…，‘Z’，‘a’，‘b',…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合.换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构.抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合.2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系.答案：例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。

第1章 绪论

第1章 绪论

朱昌杰 肖建于 编著
清华大学出版社
1.4.2 C语言描述算法的注意事项
6.循环语句： while（条件） 循环体语句； do { 循环体语句； }while（条件）； 或者 For（赋初值表达式1；条件表达式2；步长表达式3） 循环体语句； 7.结束语句： return(返回表达式)； break; exit;
朱昌杰 肖建于 编著 清华大学出版社
1.4.2 C语言描述算法的注意事项
2.算法的空间复杂度 如果输入数据所占用空间只取决于问题本身， 则只需要分析除输入和程序之外的额外空间， 否则应同时考虑输入本身所需空间。若额外空 间相对于输入数据量来说是常数，则称此算法 为原地工作，本书第9章讨论的有些排序算法 就属于这一类。若所占空间量依赖于特定的输 入，则除特别指明外，均按最坏情况来分析。
朱昌杰 肖建于 编著 清华大学出版社
1.4.2 C语言描述算法的注意事项
8.函数的定义语句： 函数类型 函数名（类型名 形参1，类型名 形参2，…） { //算法功能说明 函数语句； } 其中函数类型是指函数的返回值的类型，当返回值为整型时，函数类 型可以省略。形参如果是引用参数，则以&打头。
9.函数调用语句： 函数名（实参1，实参2，…）； 因为函数调用是一条语句，所以在括号后要有分号。
朱昌杰 肖建于 编著
清华大学出版社
1.4.2 C语言描述算法的注意事项
10.基本函数： max（表达式1，表达式2，…，表达式n） min（表达式1，表达式2，…，表达式n） abs（表达式） eof（文件变量） eoln（文件变量）
朱昌杰 肖建于 编著
清华大学出版社
1.4.2 C语言描述算法的注意事项
1.1.2 数据的物理结构

数据结构C语言版第2版课后习题答案61248

数据结构C语言版第2版课后习题答案61248

数据结构（C语言版）(第2版）课后习题答案李冬梅2015。

3目录第1章绪论 0第2章线性表 (4)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (55)第8章排序 (66)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象,如一个学生记录，树中棋盘的一个格局(状态)、图中的一个顶点等。

数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。

例如,学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集.例如：整数数据对象是集合N=｛0，±1，±2，…},字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’,…，‘z’｝，学生基本信息表也可是一个数据对象。

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构"的数据元素的集合,“结构"就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构:数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型:由用户定义的，表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称.具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构使用C语言版朱战立丛书版本排序

数据结构使用C语言版朱战立丛书版本排序

{ span = d[m];
//取本次的增量值
for<k = 0; k < span; k++> //共span个小组
{
//组内是直接插入排序,区别是每次不是增1而是增
span
for<i = k; i < n-span; i = i+span>
{ temp = a[i+span];
j = i;
while<j > -1 && temp.key < a[j].key>
优点：实现简单
缺点：每趟只能确定一个元素,表长为n时需要n-1趟
算法如下：
void SelectSort<DataType a[], int n>
{
int i, j, small;
DataType temp;
for<i = 0; i < n-1; i++>
{ small = i;
//设第i个数据元素关键字
(a)初始最大堆 40
32
9
5
10
40 32 9 5 10 50 76 88 (d)交换顶点50后 9
5
76
50
40
5
10
9
32
76 50 40 5 10 9 32 88 (b)交换顶点88后 32
10
9
5
32 10 9 5 40 50 76 88 (e)交换顶点40后
5
9 5 10 32 40 50 76 88
{ a[j+span] = a[j];
j = j-span;
65

新疆大学2019年硕士研究生招生参考书目

新疆大学2019年硕士研究生招生参考书目

考试科目 (716)岩石学 (717)细胞生物学 (718)建筑设计基础（中外建史、 物理与构造） (801)马克思主义哲学著作 (802)马克思主义经典著作选读 (803)综合（世界政治理论与实 践） (804)综合基础（公共管理基础知 识） (805)经济学基础 (806)管理学基础 (807)综合基础（含民法学、刑法 学、民诉、刑诉） (808)民族理论与民族政策 (809)现代汉语 (810)英语文化 (811)综合俄语
考试范围 《微生物学教程》 周德庆编著(第三版)，2011年，高等教育出版社。 《机械设计基础》 杨可帧，高等教育出版社，第五版。 《机械工程材料》 王运炎，机械工业出版社，2012年，第三版。 《电路》 邱关源，高等教育出版社，2006年，第5版。 《自动控制理论》 邹伯敏，机械工业出版社，2004年第2版；《自动控制原理》 胡寿松，科学出版社，2004年第4版；《现代控制理论》 刘豹、唐万生，机械工 业出版社，2007年第3版。 《信号与系统》(第三版)，郑君里编著，高等教育出版社。 《数据结构》(C语言版) 第2版，朱昌杰、肖建于等编著，清华大学出版社。 与“快速建筑设计作图”、建筑物理及建筑构造相关的空间功能组织、场地设计 、工程制图、方案表现和建筑物理及构造工程技术设计规范问题的解答等各类相 关参考资料。 《结构力学》（上、下）杨弗康、李家宝，高等教育出版社，1998年第四版、第 六版；《结构力学》（上、下）李廉锟，高等教育出版社，任意版本；《结构力 学教程》（Ⅰ、Ⅱ）龙驭球，高等教育出版社，任意版本。 《纺织材料学》姚穆，中国纺织出版社，2009年1月第三版。 《旅游学》（第三版），李天元，高等教育出版社，2011年。 《数据结构》(C语言版) 严蔚敏等编著，清华大学出版社；《软件工程导论》 (第5版) 张海藩等编著，清华大学出版社。

数据结构(C语言版本)

数据结构(C语言版本)
同一个逻辑结构可以有不同的内部存储结构；反之，数据的存 储结构一定要映像数据之间的逻辑关系。
数据结构的形式定义：数据结构是一个二元组 data_structure=(D,S)
其中：D是数据元素的有限集，S是D上关系的有限集。
2023/11/3
例1 一种结构 lineority=(K,R） K={k1,k2,kHale Waihona Puke ,k4,k5,k6,k7} R={r}
• 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解
决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于 科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把 这类问题称为数值计算。
• 近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身
运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的 是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远 远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此 相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的 和具有一定结构的信息。
4．存储结构
• 数据在计算机中的存储表示称为数据的存储结构。 • 在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，
可以表示成数组，存放在内存中；也可以表示成文件，存放在磁 盘上，等等。
2023/11/3
5．数据处理
• 数据处理是指对数据进行查找、插入、删除、合并、排序、统计
以及简单计算等的操作过程。在早期，计算机主要用于科学和工 程计算，进入八十年代以后，计算机主要用于数据处理。据有关 统计资料表明，现在计算机用于数据处理的时间比例达到80%以 上，随着时间的推移和计算机应用的进一步普及，计算机用于数 据处理的时间比例必将进一步增大。

数据结构——使用C语言版(朱战立)线性表

数据结构——使用C语言版(朱战立)线性表
结点结构如下图示：
数据域 指针域 或
data next
数据域：存储元 素数值数据
指针域：存储直接后继的存
储位置
第二十一页，编辑于星期三：三点 分。
(2)头指针、头结点和首元结点的区别
示意图如下：
hea d
头指针
a0
a1
头结点
首元结点
…
an ^
第二十二页，编辑于星期三：三点 分。
头指针是指向链表中第一个结点（或为头结点、或为首元结点 ）的指针；
struct Node *next;
} SLNode
（1）初始化ListInitiate(head)
void ListInitiate(SLNode **head)
{ *head = (SLNode *)malloc(sizeof(SLNode));
(*head)->next = NULL;
}
第三十页，编辑于星期三：三点 分。
L->list[j] = L->list[j-1];
L->list[i] = x;
L->size ++;
return 1;
}
}
第八页，编辑于星期三：三点 分。
0
1
2
3
4
5
list
10
11
12
14
15
16
6
7
... MaxSize-1
i=3
size=6
0
1
2
3
4
5
6
7
list
10
11 i=3 12
13
(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域 。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。

2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。

以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。

2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列等；非线性结构包括树、图等。

3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。

以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。

3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。

顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。

4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。

以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。

4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。

5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。

以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。

朱昌杰 C语言程序设计课本习题解答

朱昌杰 C语言程序设计课本习题解答

习题1一．选择题(1) 以下叙述正确的是（）A. 计算机不仅能执行机器语言程序，也可以直接执行其它高级语言编写的程序B. 汇编语言是一种面向机器的低级语言，所以计算机可以直接执行用汇编语言编写的源程序C. 高级语言是与自然语言或数学语言相近的计算机语言，用高级语言编写的源程序计算机都不能直接执行D. 用高级语言编写的源程序只能经过解释程序边解释边执行(2) 以下不正确的概念是（）A. 一个C程序必须包含一个main函数B. 一个C程序可以只有一个语句C. 一个C程序可以由一个或多个函数组成D. 一个C语言函数可以没有任何可执行语句(3) 在C语言程序中（）。

A. main函数必须放在程序最前头B. main函数必须放在程序最后C. main函数必须放在所有函数之前D. main函数可以放在程序任何允许放置函数的位置(4) 以下C语言源程序的书写格式不正确的是（）A. 正确的函数首部，其后必须加上分号B. 分号是语句的一部分C. 一行上可以书写多条语句D. 一个语句可以写在多行之上(5) 以下不正确的叙述是（）A. 一个#include命令只能指定一个被包含文件B. 一个#include命令可以指定多个被包含文件C. 在#include命令中，文件名可以用尖括号或双引号括起来D. 一个C程序中，可以使用多个#include文件包含命令二．填空题(1) 计算机程序设计语言分为语言、语言和语言。

(2) 正确的算法应具有五个重要的特征是：①，②，③，④，⑤。

(3) 算法的表示方法主要有、、、自然语言和语言等。

(4) 程序设计方法主要分为程序设计方法和程序设计方法。

(5) Ｃ语言的函数一般由和两部分组成。

(6) 注释部分从开始，以结束。

(7) 任何C程序的执行都是从函数开始。

(8) 函数体一般包括部分和部分。

(9) 一个C语言程序由若干个函数组成，其中必须有一个函数。

三．编程题(1) 上机运行本章例题，熟悉所用C语言系统（如：Turbo C/C++和Visual C++ 6.0等）的上机方法与步骤。

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案

精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构-使用C语言 朱战立第2章线性表的链式表示

数据结构-使用C语言 朱战立第2章线性表的链式表示

ZHOU
WU
ZHENG
WANG
/\
②
H
ZHAO QIAN SUN LI
ZHOU
WU
ZHENG头结点
头结点不计入 链表长度！
11
例2：线性表具有两种存储方式，即顺序方式和链接方 式。现有一个具有五个元素的线性表L={23，17，47， 05，31}，若它以链接方式存储在下列100～119号地址 空间中，每个结点由数据（占2个字节）和指针（占2 个字节）组成，如下图所示。
2
3.顺序存储
总结
线性表顺序存储结构特点：逻辑关系上相邻的 两个元素在物理存储位臵上也相邻； 优点：可以随机存取表中任一元素，方便快捷 缺点：在插入或删除某一元素时，需要移动大 量元素。 解决问题的思路：改用另一种线性存储方式：
链式存储结构
3
2.3 线性表的链式表示和实现 2.3.1 链表的表示 2.3.2 链表的实现 2.3.3 链表的运算效率分析
21
（3） 单链表的插入
在链表中插入一个元素X 的示意图如下：
p a
b
插 入 X
p
a
b
p->next
s
X
s->next
链表插入的核心语句： Step 1：s->next=p->next; Step 2：p->next=s ；
X 结点的生成方式：
s=(node*)malloc(m); s->data=X ; s->next= ?
22
Status ListInsert_L(LinkList L, int i, ElemType e) {
// L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e p = L; j = 0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于1 s = new LNode; // 生成新结点 s->data = e; s->next = p->next; p->next = s; // 插入 return OK;

数据结构(C语言版)(第2版)(2017年清华大学出版社出版

数据结构(C语言版)(第2版)(2017年清华大学出版社出版
全书共8章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法， 以及C语言编程的要点。第2～8章分别介绍了线性表、栈和队列及其应用、多维数组、特殊矩阵、稀疏矩阵、字 符串和广义表、树与二叉树、图、查找、排序。
成书过程
修订过程
出版工作
该教材是根据教育部《高等学校计算机科学与技术专业公共核心知识体系与课程》编写的数据结构主教材。 该教材的编写得到清华大学2015年精品教材建设项目的资助。
教材目录
（注：目录排版顺序为从左列至右列 ）
教学资源
该教材有配套教材——《数据结构精讲与习题详解（C语言版）（第2版）》。
作者简介
殷人昆，男，清华大学计算机系教授，1985年赴日本国东京理科大学做访问学者，研究方向为软件工程过程 的质量管理和软件产品的质量评价。主要教学工作为计算机系大学本科“数据结构”“软件工程”和研究生“软 件工程设计与技术”“软件项目管理”课程负责人，主持教育部微软精品课程“数据结构”的建设。
该教材的初稿完成于2015年12月，作为另一本教材《数据结构精讲与习题详解（第2版）》的写作参照，相 互补充，首先完成了《数据结构精讲与习题详解（第2版）》，再回过头来第二次修改该教材。
该教材修改部分包括：
2017年5月1日，该教材由清华大学出版社出版。
内容简介
全书共8章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法， 以及C语言编程的要点。第2～8章分别介绍了线性表、栈和队列及其应用、多维数组、特殊矩阵、稀疏矩阵、字 符串和广义表、树与二叉树、图、查找、排序，并做了适当延伸。此外，附录还包含实训作业要求与样例（实训 作业要求和实训作业样例）、词汇索引。
感谢观看
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
#define MAXSIZE 100 typedef struct { Elemtype data[MAXSIZE];
int top; }SqStack;
在顺序栈中，用于指示栈顶的当前位置的 top 是整型，它的实质是栈顶元素在数组 中的下标。栈顶指针 top 直接反映出栈的当前状态：空栈时，栈顶指针 top 为−1；栈满时， 栈顶指针 top 为 MAXSIZE−1；入栈时，栈顶指针 top 加 1；出栈时，栈顶指针 top 减 1。
// top 加 1,栈顶位置上移 //数据 e 存入当前栈顶
（5）出栈 出栈时应首先判断栈是否为空，若栈不为空，则取出栈顶元素，将栈顶指针 top 下
移，再返回栈顶元素。
int Pop(SqStack *s,Elemtype *e) { if(StackEmpty(s)) return ERROR; *e=s->data[s->top]; s->top--; return OK; }
{ Push(ps, N%r); N=N/r;
} while(!StackEmpty(ps))
{ Pop(ps,&x); printf("%d",x);
} }
//定义一个顺序栈 s //余数入栈
算法 3.1
3.2.2 括号匹配的检验
假设在一个算术表达式中，可以包含三种括号：圆括号“(”和“)”，方括号“[” 和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用，例如某一
第3章 栈 和 队 列
47
图 3.3 所示为 MAXSIZE 为 6 的顺序栈中数据元素和栈顶指针 top 的变化情况。其中， 图 3.3(a)表示空栈；图 3.3(b)表示元素 a 进栈，top 指示的是当前栈顶的位置；图 3.3(c)表 示 b、c、d、e、f 依次进栈后栈满的情况；元素 f、e、d 依次出栈后的情况如图 3.3(d)所示， top 为当前栈顶元素 c 的位置；图 3.3(e)表示元素 c、b、a 继续出栈又重新回到空栈状态。
（4）进栈 进栈时应首先判栈满，若栈不满则将栈顶指针 top 上移，存入元素。
int Push(SqStack *s, Elemtype e) {
if(StackFull(s)) return ERROR;
//将元素 e 插入到栈中,作为新栈顶 //栈满
48
数据结构（C 语言版）
s->top++; s->data[s->top]=e; return OK; }
50
Hale Waihona Puke 数据结构（C 语言版）3.2.1 数制转换
数制转换问题是指对于输入的任意一个非负十进制整数 N，打印输出与其等值的 r
进制数。一般利用辗转相除法解决这个问题，以 N=1348，r=8 为例，其转换方法如下：
N
N / 8 (整除)
N % 8 (求余)
1348
168
4
低
168
21
0
21
2
5
2
0
2
高
依次输入表达式每一个字符，若是左括号，将其入栈保存；若是右括号，则出栈左 括号，并检验与其是否匹配。循环执行，直到表达式输入结束。
在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
StackNode *p; if(StackEmpty(top)) return ERROR; *e=top->data; p=top; top=top->next; free(p); retrun OK; }
//栈空
3.2 栈的应用举例
根据栈的运算特点，在很多实际问题中都利用栈作为一个辅助的数据结构来进行求 解，下面通过几个例子进行说明。
第3章 栈 和 队 列
49
2. 链栈的算法实现 链栈的本质是简化的单链表，top 作为栈顶指针始终指向链表首结点。进栈操作就是 在链表表头插入一个新的结点，出栈操作就是删除当前的表头 结点并释放空间。 （1）初始化栈（置空栈）
LinkStack InitStack() //空栈的 top 指针为 NULL { return NULL; }
第3章 栈 和 队 列
本章知识要点： 栈和队列的基本概念 栈和队列的顺序存储结构和链式存储结构 栈和队列的应用
3.1 栈
栈是一种特殊的线性表，它的逻辑结构和存储结构与线性表相同，其特殊性体现在 “运算受限”，即无论往表中插入元素还是删除表中已有元素，都被限制在线性表的一端
进行。一般将表尾作为操作端，如图 3.1 所示。
图 3.3 栈顶指针 top 与栈中数据元素的关系
2. 顺序栈的算法实现 （1）初始化栈（置栈空）
初始化栈主要是分配存储空间，并将栈顶指针置为−1。
int InitStack(SqStack *s) { //创建一个空栈由指针 s 指向 if((s=(SqStack*)malloc(sizeof(SqStack)))==NULL) return ERROR; s->top= -1; return OK; }
StackNode *s; s=(StackNode*)malloc(sizeof(StackNode)); s->data=e; s->next=top; top=s; }
（4）出栈
int Pop(LinkStack top,Elemtype *e) { //若栈不为空将栈顶元素出栈,即为删除表头结点
具体实现如算法 3.2 所示。
typedef char Elemtype
int bracketmatching( )
{
SqStack s;
SqStack *ps=&s;
Elemtype ch;
InitStack(ps);
//若栈不为空,则取栈顶元素 //栈空 //取出数据,top 不变
由于栈的运算特殊性，顺序栈中进栈和出栈操作并不存在移动数据的问题，因而效 率较高。但顺序栈需要预先估计准确的存储空间大小，需要预先分配一个较大空间，这 有可能造成存储空间的浪费。
3.1.3 栈的链式存储结构
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存 储结构。用链式存储结构表示的栈称为“链栈”。
结果为(1348)10=(2504)8。 对其计算过程进行分析可以发现，八进制的各位数实际上就是每次运算所得的余数
值，它们产生的顺序是由低位到高位的，这恰好与输出顺序相反。因此，在转换过程中
每得到一位余数就将其进栈保存，转换完毕后再依次出栈，即可得出结果。
将十进制数 N 转换为 r 进制数，算法思路如下：
（2）判栈空
int StackEmpty(SqStack *s) //判栈为空栈时返回值为真,反之为假 { return(s->top==-1? TRUE:FALSE);}
（3）判栈满
int StackFull(SqStack *s) //判栈为满栈时返回值为真,反之为假 { return(s->top==MAXSIZE-1?TRUE:FALSE);}
（1）当 N≠0，则重复执行①和②：
① 将 N % r 进栈 s；
② N = N/r。
（2）将栈 s 的内容依次出栈，算法结束。
具体实现如算法 3.1 所示。
typedef int Elemtype void conversion(int N, int r) { SqStack s;
SqStack *ps=&s; Elemtype x; InitStack(ps); while(N)
图 3.1 操作仅在表一端进行
3.1.1 栈的定义
栈是限制在表的一端进行插入和删除操作的线性表。能够进行操作的一端是浮动端， 称为栈顶，通常用一个“栈顶指针”指示，它的位置会随着操作而发生变化；与此相对， 表的另一端是固定端，称为栈底。如同线性表可以为空表一样，当栈中没有元素时称为 空栈。往栈中插入元素的操作称为入栈，删除栈中元素的操作称为出栈。如图 3.2 表示 了一个栈。
图 3.2 栈的示意图
根据栈的运算特性，所有操作都只在栈顶进行。如果将数据元素按照 a1, a2, a3, …, an 的顺序依次入栈，则此时 a1 在栈底，an 在栈顶，如图 3.2 所示。当要取出数据时，则必 须按 an, an−1, …, a1 的顺序进行。由此可知，an 作为栈顶元素总是最后入栈的，而最先出 栈；a1 作为栈底元素总是最先入栈的，而最后出栈。栈按照这种后进先出(LIFO，Last In First Out)或者先进后出(FILO，First In Last Out)的原则来组织数据的，因此，它也被称为
1. 链栈的类型定义 链栈通常用一个无头结点的单链表表示，其结点结构与单链表的结点结构相同。
typedef struct node { Elemtype data;
struct node* next; }StackNode,*LinkStack; LinkStack top;
//top 为栈顶指针
由于栈中的主要运算是在栈顶进行插入、删除，对于单链表来说，在表头插入和删 除结点要比在表尾相对简单，因此将单链表表头作为栈顶，则单链表的头指针即为栈顶 指针。通常将链栈表示如图 3.4 所示。
第3章 栈 和 队 列
51
个算术表达式中的括号使用括号情况为“…[…{…}…[…]…]…[…]…(…)…”。括号匹 配的检验主要就是判别给定表达式中所含括号是否正确配对。
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配， 并且每对括号之间可以嵌套，但不能出现交叉情况。根据该规则可知，当前最晚出现的 左括号总是最先与随后出现的右括号进行匹配，这一规律与栈的“后进先出”运算特性 吻合，因此可以利用栈来解决这一问题，算法思路如下：