(c语言版) 严蔚敏吴伟民编著 精华大学出版社
前言 数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学 科的核心课程,而且已成为其他理工专业的热门选修课。本书是为“数据结 构”课程编写的教材,其内容选取符合教学大纲要求,并兼顾学科的广度和深 度,适用面广。 本书的第1章综述数据、数据结构和抽象数据类型等基本概念;第2章至 笫7章从抽象数据类型的角度,分别讨论线性表、栈、队列、串、数组、广义表、 树和二叉树以及图等基本类型的数据结构及其应用;第8章综合介绍操作系 统和编译程序中涉及的动态存储管理的基本技术;第9章至第11章讨论查找 和排序,除了介绍各种实现方法之外,并着重从时问上进行定性或定量的分析 和比较;第12章介绍常用的文件结构。用过(数据结构》(第二版)的读者容易 看出,本书内容和章节编排与1992年4月出版的《数据结构〉(第二版)基本一 致,但在本书中更突出了抽象数据类型的概念。对每一种数据结构,都分别给 出相应的抽象数据类型规范说明和实现方法 全书中采用类C语言作为数据结构和算法的描述语言,在对数据的存储 结构和算法进行描迷时,尽量考虑C语言的特色,如利用数组的动态分配实现 顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具,但鉴于目 前和近一、两年内,“面向对象程序设计”并非数据结构的先修课程,故本书未 直接采用类和对象等设施,而是从C语言中精选了一个核心子集,并增添 C++语言的引用调用参数传递方式等,构成了一个类C描述语言。它使本 书对各种抽象数据类型的定义和实现简明清晰,既不拘泥于C语言的细节, 又容易转换成能上机执行的C或C+十程序。 从课程性质上讲,数据结构”是一门专业牧术基础课。它的教学要求是 学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适 当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间 分析的技术。另一方面,本课程的学习过程也是复杂程序设计的训练过程,要 求学生编写的程序结构清楚和正确易读,符合软件工程的规范。如果说高级 语言程序设计课程对学生进行了结构化程序设计(程序抽象)的初步训练的 话,那么数据结构课程就要培养他们的数据抽象能力。本书将用规范的数学 语言描述数据结构的定义,以突出其数学特性,同时,通过若干数据结构应用 实例,引导学生学了数据类型的使用,为今后学习面向对象的程序设计作一些
铺垫 本书可作为计算机类专业的本科或专科教材,也可以作为信息类相关专 业的选修教材,讲授学时可为S0至80。教师可根据学时、专业和学生的实际 情况,选讲或不讲目录页中带*的章节,甚至删去第5、8、和12章。本书 文字通俗、简明易懂、便于自学,也可供从辜计算机应用等工作的科技人员参 考。只需掌握程序设计基本技术便可学习本书。若具有离散数学和概率论的 知识,则对书中某些内容更易理解。如果将本书〈数据结构〉(C语言版)和《数 据结构》(第二版)作为关于数据结构及其算法的C和 Pascal程序设计的对照 教材,则有助于快速且深刻地掌握这两种语言 与本书配套的还有《数据结构题集)(C语言版),由清华大学出版社出版。 书中提供配套的习题和实习题,并可作为学习指导手册。 严蔚敏清华大学计算机技术与科学系 吴伟民华南师范大学计算机科学系 1996年7月
目录 第1章绪论…………………… 11什么是数据结构 12基本概念和术语 13抽象数据类型的表示与实现…………………………………………9 14算法和算法分析…… 1.4.1算法…………………………………………… 142算法设计的要求……………………………… 143算法效率的度量 ·,带中垂,非 ………………4 144算法的存储空间需求…………………………………17 第2章线性表……………………………………………………………………18 21线性表的类型定义……………………………………… 22线性表的顺序表示和实现……………………………………………21 23线性表的链式表示和实现…………………………………27 231线性链表 23.2循环链表 233双向链表……… 35 24一元多项式的表示及相加 第3章栈和队列 3.1栈… 311抽象数据类型栈的定义……………………………………44 312栈的表示和实现……………………………45 32栈的应用举例… 3.2.1数制转换………………………………………… 322括号匹配的检验……………………………… 323行编辑程序……… 3.24迷宫求解……… …………50 325表达式求值………………………………………52 33栈与递归的实现………… ·········甲···· 3.4队列 4,.中中中4·中·中·;p,中F中,,中丶甲声;,;·中,·,,中·中非,中中中·;辛4中、,; 58 3.4.1抽象数据类型队列的定义………………………………58 342链队列——队列的链式表示和实现………………………………60 343循环队列——队列的顺序表示和实现………………………63 3.5离散事件模拟…………………………………………………………65 Ⅲ
第4章串 ;··;;中·;中·P;;·:;44:.44;:;1;昏;号号;;4,日;日;;中4、4中、;4 41串类型的定义… ,曲目、甲专 4.2串的表示和实现 专●中··中、:,●;···;,非;专··?+,中.中,q中、加 42.1定长顺序存储表示…… ··,· 42.2堆分配存储表示 …………………………75 423串的块链存储表示……………………… 非,中,甲垂中布专中、垂中非垂 4.3串的模式匹配算法… 7yy 43.1求子串位置的定位函数Inex(s,T,pas)……………79 4.3.2模式匹配的一种改进算法……………………………………80 44串操作应用举例……………………………………………………………84 4.4.1文本编辑…………………… 442建立词索引表……………………………………………85 第5章数组和广义表…………………………………… 90 51数组的定义………………… 52数组的顺序表示和实现……………………………… 53矩阵的压缩存储… 看中带中·,中;;非中·中、;中;t中中·“·中,品中t·+中 5.3.1特殊矩阵 、4、,香“甲;·甲甲甲甲·P·非中、中。中·中垂中昏·4中 532稀疏矩阵……………………………6 54广义表的定义……………………………………………………106 55广义表的存储结构………………… ……109 5.6m元多项式的表示…………………………………………110 5.7广义表的递归算法…………………………………………………112 57.1求广义表的深度 113 57.2复制广义表 114 573.建立广义表的存储结构………………………………115 第6章树和二叉树………………………… 61树的定义和基本术语…………………………………………118 6.2二叉树…………………………………………………………………121 621二叉树的定义………121 622二叉树的性质…………………… 623二又树的存储结构………………………………………126 63遗历二叉树和线索二叉树……………………………………………128 631意历二叉树…… 128 632线索二叉树 韦争垂中·· +中、非;中专由 132 64树和森林…………………………………135 64.1树的存情结构……………………………………135 64.2森林与二叉树的转换………………………………137 64.3树和森林的遍历… 量P《4·t,;·;、中·甲 138 Ⅳ