第01章_概论22109

《第01章_概论22109》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、李云清杨庆红揭安全高等学校精品课程人民邮电出版社（第2版）数据结构datastru@gmail.com（第2版）什么是数据结构数据类型和抽象数据类型算法和算法分析第一章概述瑞士著名的计算机科学家NicklausWirth在1976年出版了一本书，书名为《算法+数据结构=程序设计》，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组"指令"，首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。　　很多数值计算问题的数学模型通常可用一组线性

2、或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论的数据结构。第一章概述例一、求n个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到1012，那么对32位的计算机来说，就存在一个如何表示的问题。例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。例三、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对n

3、个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？这是一个讨论图的生成树的问题。ABHIGCEDF1812979525631108598672145834（a）城市距离图ABHIGCEDF12979311021834（b）联通各城市最小生成树以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。而信息的表示和组织又直接关系到处理信息

4、的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理综上所述1.1数据结构1.1.1数据结构随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非

5、数值数据。需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处理。例4某电信公司的市话用户信息表格如下图所示：序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王冬5700123瑶湖大道198700004王三5700567瑶湖大道200800005江凡8800129学府大道5035这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单

6、位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。使用计算机处理用户信息表中的数据时，必须弄清楚下面3个问题：1数据的逻辑结构这些数据之间有什么样的内在联系？除最前和最后两个结点之外，表中所有其它的结点都有且仅有一个和它相邻位于它之前的一个结点，也有且仅有一个和它相邻位于它之后的一个结点，这些就是用户信息表的逻辑结构。2数据的存储结构将用户信息表中的所有结点存入计算机时，就必须考虑存储结构，使用C语言进行设计时，常见的方式

7、是用一个结构数组来存储整个用户信息表，每一个数组元素是一个结构，它对应于用户信息表中的一个结点。数据在计算机的存储方式称为存储结构。3数据的运算集合数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。对待处理的数据，只有分析清楚上面3个方面的问题，才能进行有

8、效的处理！数据结构就是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。基于这个二维表格，我们可以在上面执行的操作有：增加一个元素，删除元素，查找元素等。存在的问题：线性查找的效率较低（等概率情况下为n/2）。数组存储时插入一个元素与删除一个元素效率较低。解决办法：改变数据存储结构，在新的存储结构上开发新的算法。找95找35例5、旅游交通网络图实际问题：