第9章数据结构基础知识.pptVIP

《Web编程技术》 《计算机应用基础》教案 江西财经大学信息管理学院 李钟华 2010年3月——2010年6月 第9章 数据结构基础知识 数据结构基本概念 线性表及其存储结构 栈和队列 树与二叉树 查找技术 排序技术 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。 5.1.1 什么是数据结构 数据结构（Data Structure，DS）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。 数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。它们一般具有某种共同特征。例如，读者在图书馆里借书的记录；学生成绩表中的某个学生的成绩等。 作为某种处理，其中的数据元素一般具有某种共同的特征。例如，{春，夏，秋，冬}这四个数据元素，它们都是季节名，从而构成了季节的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素。 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。 前后件关系是数据元素之间的一个基本关系。但前后件关系所表示的实际意义隨具体对象的不同而不同。 　 5.1.2 数据的逻辑结构 数据是指由有限的符号组成的元素的集合，结构则是元素之间的关系（前驱和后继）的集合。数据元素之间的关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。通常来说，一个数据结构可以表示为一个二元组： DS=（D，S） 　这里D是数据元素的集合，S是定义在D（或其他集合）上的关系的集合，称之为元素的逻辑结构。 根据数据结构中各数据元素之间的前驱与后继关系的复杂程度，逻辑上可以把数据结构分为线性结构和非线性结构。 线性结构又称线性表。 线性结构是一个数据元素的有序(次序)集，其特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。 例如，队列 在现实中的许多事物的关系并非这样简单，如社会组织机构 、城市交通、通讯等，这些事物中的联系都是非线性的 。如果一个数据结构不是线性的，则称为非线性结构。由于非线性结构各数据元素之间的前驱和后继关系比较复杂，因此对非线性结构的存储与处理比线性结构复杂。 所谓非线性结构是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。 5.1.3 数据的存储结构 　 在计算机中进行数据处理时，被处理的每个数据元素都是存放在计算机的存储空间，并且各数据元素在计算机存储空间中的位置关系与他们的逻辑关系不一定相同。 　 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此在数据的存储结构中，不仅要存放各数据元素的内容，还需要存放各数据元素之间的前驱后继关系的信息。 例如，现实生活中不同货物保存在不同仓库中，每个不仅保存货物，还存一张纸条写着下一种货物所在仓库的号码。 ⑴线性结构(指逻辑结构为线性结构) 线性存储结构有顺序、链接、索引和散列4种结构 顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间，缺点是由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。 链接存储结构是将结点所占的存储单元分为两部分，一部分存放结点本身的信息，即数据项。另一部分存放该结点的后继结点所对应的存储单元的地址，即为指针项。优点是不会出现碎片现象，充分利用所有的存储单元，缺点是每个结点占用较多的存储空间。 索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表，会占用较多的存储空间。 散列存储结构是根据结点的值确定它的存储地址，优点是检索、增加和删除结点的操作速度快，缺点是采用不好的散列函数时可能出现结点单元的碰撞，而需要附加时间和空间开销。 ?⑵树型结构树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的倒置树。树结构在客观世界中广泛存在（如各种社会