第1章 算法与数据结构(绪论)

《第1章 算法与数据结构(绪论)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法与数据结构教材：《数据结构(C语言版)》。严蔚敏，吴伟民编著。清华大学出版社。参考文献：1《数据结构》。张选平，雷咏梅编，严蔚敏审。机械工业出版社。2《数据结构与算法分析》。CliffordA.Shaffer著，张铭，刘晓丹译。电子工业出版社。3《数据结构习题与解析(C语实言版)》。李春葆。清华大学出版社。4《数据结构与算法》。夏克俭编著。国防工业出版社。第1章绪论目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个

2、问题：信息的表示，信息的处理。信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。编写解决实际问题的程序的一般过程：如何用数据形式描述问题?—即由问题抽象出一个适当的数学模型;问题所涉及的数据量大小及数据之间的关系;如何在计算机中存储数据及体现数据之间的关系?处理问题时需要对数据作何种运算?所编写的程序的性能是否良好?上面所列举的问题基本上由数据结构这门课

3、程来回答。计算机求解问题的一般步骤1.1数据结构及其概念《算法与数据结构》是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。1.1.1数据结构的例子姓名电话号码陈海13612345588李四锋13056112345。。。。。。例1：电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2

4、…n)分别表示某人的名字和电话号码。本问题是一种典型的表格问题。如表1-1，数据与数据成简单的一对一的线性关系。表1-1线性表结构例2：磁盘目录文件系统磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推：本问题是一种典型的树型结构问题，如图1-1，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。图1-1树形结构例3：交通网络图从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。佛山惠州广州中山东莞深圳珠海图1-2网状

5、结构数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…}。1.1.2基本概念和术语数据结构(DataStructure)：是指相互之间具有(存在)一定联系

6、(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例2：设数据逻辑结构B=（K，R）K={k1,k2,…,k9}R={，

7、>，，，，，，，，，}画出这逻辑结构的图示，并确定那些是起点，那些是终点1.1.3数据结构的形式定义图1-3四类基本结构图1.1.4数据结构的存储方式数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示

8、方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结