适用于天津财经大学

书籍介绍：
严蔚敏 吴伟民 编著《数据结构》(C语言版)是为“数据结构”课程编写的教材，也可作为学习数据结构及其算法的C程序设计的参考教材。　本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。其内容和章节编排与1992年4月出版的《数据结构》(第二版)基本一致，但在本书中更突出了抽象数据类型的概念。　全书中采用类C语言作为数据结构和算法的描述语言，在对数据的存储结构和算法进行描述时，尽量考虑C语言的特色，如利用数组的动态分配实现顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一二年内，“面向对象程序设计”并非数据结构的先修课程，故本书未直接采用类和对象等设施，而是从C语言中精选了一个核心子集，并增添C++语言的引用调用参数传递方式等，构成了一个类C描述语言。它使本书对各种抽象数据类型的定义和实现简明清晰，既不拘泥于C语言的细节，又容易转换成能上机执行的C或C++程序。　本书概念表述严谨，逻辑推理严密，语言精炼，用词达意。并有配套出版的《数据结构题集》(C语言版)。既便于教学，又便于自学。　本书可作为计算机类专业或信息类相关专业的本科或专科教材，也可供从事计算机工程与应用工作的科技工作者参考。

作者简介　　  
　　严蔚敏，清华大学计算机系教授，长期从事数据结构教学和教材建设，和吴伟民合作编著的《数据结构》曾获“第二届普通高等学校优秀教材全国特等奖”和“1996年度国家科学技术进步奖三等奖”。 吴伟民，广东工业大学计算机学院副教授，硕士生导师。广东省计算机学会图像图形分会秘书长。长期从事数据结构教学和系列教材建设。主要研究领域：数据结构和算法、可视计算、编译和虚拟机技术、智能系统等。和严蔚敏合作编著的《数据结构》曾获“第二届普通高等学校优秀教材全国特等奖”和“1996年度国家科学技术进步奖三等奖”。 

前言
　　“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本书是为“数据结构”课程编写的教材，其内容选取符合教学大纲要求，并兼顾学科的广度和深度，适用面广。 
    本书的第1章综述数据、数据结构和抽象数据类型等基本概念；第2章至第7章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用；第8章综合介绍操作系统和编译程序中涉及的动态存储管理的基本技术；第9章至第11章讨论查找和排序，除了介绍各种实现方法之外，并着重从时间上进行定性或定量的分析和比较；第12章介绍常用的文件结构。用过《数据结构》（第二版）的读者容易看出，本书内容和章节编排与1992年4月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。对每一种数据结构，都分别给出相应的抽象数据类型规范说明和实现方法。 
    全书中采用类C语言作为数据结构和算法的描述语言，在对数据的存储结构和算法进行描述时，尽量考虑C语言的特色，如利用数组的动态分配实现顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一两年内，“面向对象程序设计”并非数据结构的先修课程，故本书未直接采用类和对象等设施，而是从C 语言中精选了一个核心子集，并增添C++语言的引用调用参数传递方式等，构成了一个类C描述语言。它使本书对各种抽象数据类型的定义和实现简明清晰，既不拘泥于C语言的细节， 又容易转换成能上机执行的C或C++程序。 
　　从课程性质上讲，“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。如果说高级语言程序设计课程对学生进行了结构化程序设计（程序抽象）的初步训练的话，那么数据结构课程就要培养他们的数据抽象能力。本书将用规范的数学语言描述数据结构的定义，以突出其数学特性，同时，通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序设计作一些铺垫。 
　　本书可作为计算机类专业的本科或专科教材，也可以作为信息类相关专业的选修教材，讲授学时可为50至80。教师可根据学时、专业和学生的实际情况，选讲或不讲目录页中带**的章节，甚至删去第5、8、11和12章。本书文字通俗，简明易懂，便于自学，也可供从事计算机应用等工作的科技人员参考。只需掌握程序设计基本技术便可学习本书。若具有离散数学和概率论的知识，则对书中某些内容更易理解。如果将本书《数据结构》（C语言版）和《数据结构》（第二版）作为关于数据结构及其算法的C和Pascal 程序设计的对照教材，则有助于快速且深刻地掌握这两种语言。 
　　与本书配套的还有《数据结构题集》(C语言版)，由清华大学出版社出版。书中提供配套的习题和实习题，并可作为学习指导手册。 

目录
第1章绪论1 
1.1什么是数据结构1 
1.2基本概念和术语4 
1.3抽象数据类型的表示与实现9 
1.4算法和算法分析13 
1.4.1算法13 
1.4.2算法设计的要求13 
1.4.3算法效率的度量14 
1.4.4算法的存储空间需求17 
第2章线性表18 
2.1线性表的类型定义18 
2.2线性表的顺序表示和实现21 
2.3线性表的链式表示和实现27 
2.3.1线性链表27 
2.3.2循环链表35 
2.3.3双向链表35 
2.4一元多项式的表示及相加39 
第3章栈和队列44 
3.1栈44 
3.1.1抽象数据类型栈的定义44 
3.1.2栈的表示和实现45 
3.2栈的应用举例48 
321数制转换48 
322括号匹配的检验49 
323行编辑程序49 
324迷宫求解50 
325表达式求值52 
**3.3栈与递归的实现54 
3.4队列58 
3.4.1抽象数据类型队列的定义58 
3.4.2链队列——队列的链式表示和实现60 
3.4.3循环队列——队列的顺序表示和实现63 
**3.5离散事件模拟65 
第4章串70 
4.1串类型的定义70 
4.2串的表示和实现72 
4.2.1定长顺序存储表示73 
4.2.2堆分配存储表示75 
423串的块链存储表示78 
**43串的模式匹配算法79 
4.3.1求子串位置的定位函数Index(S,T,pos)79 
4.3.2模式匹配的一种改进算法80 
4.4串操作应用举例84 
4.4.1文本编辑84 
**4.4.2建立词索引表86 
第5章数组和广义表90 
5.1数组的定义90 
5.2数组的顺序表示和实现91 
5.3矩阵的压缩存储95 
5.3.1特殊矩阵95 
5.3.2稀疏矩阵96 
5.4广义表的定义106 
5.5广义表的存储结构109 
**5.6m元多项式的表示110 
**5.7广义表的递归算法112 
5.7.1求广义表的深度113 
5.7.2复制广义表115 
5.7.3建立广义表的存储结构115 
第6章树和二叉树118 
6.1树的定义和基本术语118 
6.2二叉树121 
6.2.1二叉树的定义121 
6.2.2二叉树的性质123 
6.2.3二叉树的存储结构126 
6.3遍历二叉树和线索二叉树128 
6.3.1遍历二叉树128 
6.3.2线索二叉树132 
6.4树和森林135 
6.4.1树的存储结构135 
6.4.2森林与二叉树的转换137 
6.4.3树和森林的遍历138 
**6.5树与等价问题139 
6.6赫夫曼树及其应用144 
6.6.1最优二叉树(赫夫曼树)144 
6.6.2赫夫曼编码146 
**6.7回溯法与树的遍历149 
**6.8树的计数152 
第7章图156 
7.1图的定义和术语156 
7.2图的存储结构160 
7.2.1数组表示法161 
7.2.2邻接表163 
7.2.3十字链表164 
7.2.4邻接多重表166 
7.3图的遍历167 
7.3.1深度优先搜索167 
7.3.2广度优先搜索169 
7.4图的连通性问题170 
7.4.1无向图的连通分量和生成树170 
**7.4.2有向图的强连通分量172 
7.4.3最小生成树173 
**7.4.4关节点和重连通分量176 
7.5有向无环图及其应用179 
7.5.1拓扑排序180 
7.5.2关键路径183 
7.6最短路径186 
7.6.1从某个源点到其余各顶点的最短路径187 
7.6.2每一对顶点之间的最短路径190 
第8章动态存储管理193 
8.1概述193 
8.2可利用空间表及分配方法195 
8.3边界标识法198 
8.3.1可利用空间表的结构198 
8.3.2分配算法199 
8.3.3回收算法201 
8.4伙伴系统203 
8.4.1可利用空间表的结构203 
8.4.2分配算法204 
8.4.3回收算法205 
**8.5无用单元收集206 
**8.6存储紧缩212 
第9章查找214 
9.1静态查找表216 
9.1.1顺序表的查找216 
9.1.2有序表的查找218 
**9.1.3静态树表的查找222 
9.1.4索引顺序表的查找225 
9.2动态查找表226 
9.2.1二叉排序树和平衡二叉树227 
9.2.2B-树和B+树238 
**9.2.3键树247 
9.3哈希表251 
9.3.1什么是哈希表251 
9.3.2哈希函数的构造方法253 
9.3.3处理冲突的方法256 
9.3.4哈希表的查找及其分析259 
第10章内部排序263 
10.1概述263 
10.2插入排序265 
10.2.1直接插入排序265 
10.2.2其他插入排序266 
10.2.3希尔排序271 
10.3快速排序272 
10.4选择排序277 
10.4.1简单选择排序277 
10.4.2树形选择排序278 
10.4.3堆排序279 
10.5归并排序283 
10.6基数排序284 
10.6.1多关键字的排序284 
10.6.2链式基数排序286 
10.7各种内部排序方法的比较讨论288 
第11章外部排序293 
11.1外存信息的存取293 
11.2外部排序的方法295 
**11.3多路平衡归并的实现297 
**11.4置换选择排序299 
**11.5最佳归并树304 
第12章文件306 
12.1有关文件的基本概念306 
12.2顺序文件308 
12.3索引文件311 
12.4ISAM文件和VSAM文件313 
12.4.1ISAM文件313 
12.4.2VSAM文件316 
12.5直接存取文件(散列文件)317 
12.6多关键字文件319 
12.6.1多重表文件319 
12.6.2倒排文件319 
附录A名词索引322 
附录B函数索引329 

作 者：  严蔚敏、吴伟民 编著 

出版时间： 1997-4第1版