数据结构自编教材.doc

《数据结构自编教材.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录第一章数据结构与算法程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间的关系存放到计算机中，即建立数据的存储结构；最后在所建立的存储结构上实现对数据元素的各种操作，即算法的实现。本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存储结构和算法的有关概念；掌握基本逻辑结构和常用的存储方法，能够选择合适的数据

2、的逻辑结构和存储结构；掌握算法及算法的五个重要特性，能够对算法进行时间复杂度分析，从而选择一个好的算法，为后面的学习打下良好的基础。1.1数据结构的概念1、数据（Data）数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。2、数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。例如：学生的信息，包括：学号、姓名、成绩。一个学生的信息就是一个数据元素。3、数据项（Dataitem）数据项是具有独立

3、含义的最小标识单位。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。4、数据结构（DataStructure）数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：①数据的逻辑结构：数据元素之间的逻辑关系。例如：某个班学生成绩表，包括：学号、姓名和各科成绩，每一个学生的信息都是一个数据元素。数据元素之间有这样的逻辑关系：在一个数据元素的前面最多有一个与其相邻的数据元素（称为直接前驱），在一个数据元素的后面也最多有一个与其相邻的数据元素（称为直接后继）。数据元素之间的这种关系构成了学生成绩表的逻辑结构。

4、数据（逻辑）结构的形式定义：数据结构是一个二元组（D，R），其中D是数据元素的有限集，R是D上关系的有限集。②数据的存储结构：数据元素及数据元素之间的关系在计算机存储器内的表示。③数据的运算：即对数据施加的操作。数据的运算定义在数据的逻辑结构上，只有确定了存储结构，才能具体实现这些运算。数据结构就是研究数据的逻辑结构和存储结构，以及它们之间的相互关系和所定义的算法如何在计算机上实现，它包括数据的逻辑结构、存储结构和数据的运算三个方面。1.2数据的逻辑结构与存储结构1、数据的逻辑结构①线性结构：有且仅有一个开始结点和一个终端结点，且所有结点都最多

5、只有一个直接前驱和一个直接后继。②非线性结构：一个结点可能有多个直接前驱和多个直接后继。2、基本逻辑结构①集合结构：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。②线性结构：数据元素的有序集合。数据元素之间形成一对一的关系。③树型结构：树是层次数据结构，树中数据元素之间存在一对多的关系。④图状结构：图中数据元素之间的关系是多对多的。如果用小圆圈表示结点，用连线表示结点之间的逻辑（邻接）关系，四种基本逻辑结构如图1.1所示：集合结构线性结构图1.1四种基本逻辑结构树型结构网状结构3、存储结构存储结构可用以下四种存储

6、方法得到：①顺序存储方法：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。顺序存储结构通常是借助于程序语言的数组来描述的。②链式存储方法：该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段来表示的。由此得到的存储表示称为链式存储结构。链式存储结构通常是借助于程序语言的指针来描述的。如下图1.2所示：300010301103031032510318……89.54000……90.53050……833020……78NULLhead30

7、00400030503020图1.2链式存储③索引存储方法：除建立结点信息外，还要建立附加的索引表来标识结点的地址。④散列存储方法：根据结点的关键字直接计算出该结点的存储地址。1.3算法及算法分析一、算法及其特性1、算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。2、算法的重要特性①输入：一个算法应该有零个或多个输入。②有穷性：一个算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环。③确定性：算法中的每一条指令必须有确切的含义，不能产生多义性。④可行性：算法中的每一条指令必须是切实可执行的

8、，即原则上可以通过已经实现的基本运算执行有限次来实现。⑤输出：一个算法应该有一个或多个输出，这些输出是同输入有某个特定关系的量。3、算法描述：算法描述