数据结构案例教程（C语言版） - (EPUB全文下载)

文件大小：0.2 mb。
文件格式：epub 格式。
书籍内容：

数据结构案例教程（C语言版）
第1章　数据结构基础
第2章　线　性　表
第3章　栈和队列
第4章　串
第5章　数组和广义表
第6章　树和二叉树
第7章　图
第8章　查　　找
第9章　排　　序
反侵权盗版声明
第1章　数据结构基础
结构之美无处不在
说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子，还有看不见却也存在的分子、原子。可见一件事物只要存在，就一定会有自己的结构。一幅画的生成，画家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规划、谋篇布局；一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服；还有教育管理系统的结构、通用技术的学科结构、课堂教学结构等。试想一下，管理大量数据是否也需要数据结构呢？
数据结构的基本概念
数据结构和抽象数据类型
算法和算法分析
1.1　数据结构的基本概念
计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制、存储和检索文件、数据库技术等计算机应用，都是对数据进行加工处理的过程。因此，要设计出一个结构好而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。
计算机在发展的初期，其应用范围是数值计算，所处理的数据都是整型、实型、布尔型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。随着计算技术的发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中。与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音、视频等复杂的数据。这些复杂的数据不仅量大，而且具有一定的结构。例如，一幅图像是一个由若干简单数值组成的矩阵，一个图形中的几何坐标可以组成表。此外，语言编译过程中所使用的栈、符号表和语法树，操作系统中用到的队列、磁盘目录树等，都是有结构的数据。数据结构所研究的就是这些有结构的数据，因此，数据结构的知识不论对研制系统软件还是开发应用软件都非常重要，它是学习软件知识和提高软件设计水平的重要基础。
1.1.1　数据结构的研究内容
在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当使用计算机来解决一个具体问题时，一般需要经过如下几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个求解此数学模型的算法，最后编出程序进行调试、测试，得到最终的答案。例如，用计算机进行全球天气预报时，可以求解一组球面坐标系下的二阶椭圆偏微分方程。
随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题显得越来越重要。据统计，当今处理非数值计算问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式来描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。而数据结构主要研究非数值计算问题，下面通过具体实例加以说明。
【例1-1】学生信息检索系统。当系统需要查某个学生的有关情况时，或者想查询某个专业或年级的学生的有关情况时，只要建立相关的数据结构，按照某种算法编写相关的程序，就可以实现计算机自动检索。为此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和若干张分别按姓名、专业、年级顺序排列的索引表，如表1-1～表1-4所示。由这4张表构成的文件便是学生信息检索的数学模型。
表1-1　学生基本信息表
表1-2　姓名索引表
表1-3　专业索引表
表1-4　年级检索表
诸如此类的还有电话号码查询问题，考试成绩查询问题，企业进、销、存管理问题等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系，这类数学模型可称为线性的数据结构。
【例1-2】计算机系统组成结构，如图1-2所示。
计算机系统是由硬件系统和软件系统这两大系统组成，硬件系统由CPU、存储器、输入/输出设备、外设组成，而软件系统由系统软件和应用软件组成。如果把它们视为数据元素，这些元素之间所呈现的是一种层次关系，从上到下按层进行展开，形成“一棵倒立的树”，最上层是“树根”，依层向下展出“节点”和“树叶”。
树结构还有一个单位的组织机构、国家行政区域规划、书籍目录等。在这类问题中，计算机处理的对象是树结构，元素之间是一种一对多的层次关系，这类数学模型称为树的数据结构。
图1-1　计算机系统组成结构图
【例1-3】最短路径问题。从城市A到城市B有多条线路可达，但每条线路的交通成本不同，那么怎样选择一条线路，使得从城市A出发到达城市B所花费的费用最低呢？解决问题的方法是，可以将这类问题抽象为图的最短路径问题。如图1-2所示，图中的顶点代表城市，有向边代表两个城市之间的通路，边上的权值代表两个城市之间的交通费。求解A到B的最低费用，就是要在有向图中，从A点到B点的多条路径中，寻找一条各边权值之和最小的路径，即为该图的最短路径。
图1-2　最短路径问题
图结构还有网络工程图问题、教学计划编排问题、比赛编排问题等，在这类问题中，元素之间是多对多的网状关系，这类数学模型称为图的数据结构。
由以上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
“数据结构”最早是1968年在美国被确定为一门独立的课程的。同年，著名的美国计算机科学家D.E.Knuth教授所著《计算机程序设计技巧》的第一卷《基本算法》，是第一本系统地阐述数据的逻辑结构以及运算的著作。从20世纪60年代末到70年代初出现了大型程序，程序与数据相对独立，结构化程序设计成为程序设计方法学的主要内容，人们越来越感到数据结构的重要性，认为程序设计的实质就是针对所处理问题选择一种好 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。