数据结构c语言版 附试题及答案

数据结构c语言版是一本pdf中文版的高清电子书，作者严蔚敏，吴伟民。全书总共分为12章节，第1章综述数据、数据结构和抽像数据类型等基本概念；第2章至第7章从抽像数据类型的角度，分别讨论线性表，栈，队列，串，数组，广义表，树和二叉树以及图等基本类型的数据结构及其应用；第8章综合介绍操作系统和编译程序中涉及的动态存储管理的基本技术；第9章到第11章讨论查找和排序，除了介绍各种实现方法之外，并着重从时间上进行定性或定量的分析和比较；第12章介绍常用的文件结构。另外软件包中还附带了数据结构试题及答案，以方便各位读者学习和参考。

<

目录节选：

第1章 绪论

1.1 什么是数据结构

1.2 基本概念和术语

1.3 抽象数据类型的表现与实现

1.4 算法和算法分析

第2章 线性表

2.1 线性表的类型定义

2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现

2.4 一元多项式的表示及相加

第3章 栈和队列

3.1 栈

3.2 栈的应有和举例

3.3 栈与递归的实现

3.4 队列

3.5 离散事件模拟

第4章 串

4.1 串类型的定义

4.2 串的表示和实现

4.3 串的模式匹配算法

4.4 串操作应用举例

……

章节内容

第1章绪 论

自1946 年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使得它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是“数据结构”这门学科形成和发展的背景。

1.1 什么是数据结构

一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而更多的非数值计算问题无法用数学方程加以描述。下面请看 3个例子。

例1-1 图书馆的书目检索系统自动化问题。当你想借阅一本参考书不知道书库中是否有的时候；或者，当你想找某一方面的参考书而不知图书馆内有哪些这方面的书时，你都需要到图书馆去查阅图书目录卡片。在图书馆内有各种名目的卡片：有按书名编排的，有按作者编排的，还有按分类编排的，等等。若利用计算机实现自动检索，则计算机处理的对象便是这些目录卡片上的书目信息。列在一张卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等若干项组成，每一本书都有惟一的一个登录号，但不同的书目之间可能有相同的书名，或者有相同的作者名，或者有相同的分类号。由此，在书目自动检索系统中可以建立一张按登录号顺序排列的书目文件和 3张分别按书名、作者名和分类号顺序排列的索引表，如图 1.1 所示。由这4张表构成的文件便是书目自动检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定书名）对书目文件进行查询。诸如此类的还有查号系统自动化、仓库账目管理等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。

例 1-2 计算机和人对弈问题。计算机之所以能和人对是因为有人将对弈的策略事先已存人计算机。由于对弈的过程是在一定规则下随机进行的，所以，为使计算机能灵活对弈就必须对对弈过程中所有可能发生的情况以及相应的对策都考虑周全，并且，一个“好”的棋手在对弈时不仅要看棋盘当时的状态还应能预测棋局发展的趋势，甚至最后结局。因此，在对弈问题中，计算机操作的对象是对弈过程中可能出现的棋盘状态一一称为格局。例如图1.2（a）所示为井字棋的一个格局，而格局之间的关系是由比赛规则决定的。通常，这个关系不是线性的，因为从一个棋盘格局可以派生出几个格局，例如从图1.2（a）所示的格局可以派生出 5个格局如图1.2（b）所示而从每一个新的格局又可派生出 4 个可能出现的格局。因此，若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一倒长的“树”。“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对的过程就是从树根沿树权到某个叶子的过。“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。

例 1-3 多路口交通灯的管问题。通常在十路口只设红绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的大流通

……