2 数据结构(2学时).ppt

《2 数据结构(2学时).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一部分：基本知识第二部分：线性结构第三部分：非线性结构第四部分：线性表的查找和排序一、基本概念1、数据:是描述客观事物并能为计算机加工处理的符号的集合。2、数据元素：是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。3、数据项：是有独立含义的数据最小单位，有时也把数据项称为域、字段等。第一部分：基本知识4、什么是数据结构？数据结构（DataStructure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容：数据的逻辑结构数据的物理结构数据的运算二、数据的逻辑结构：数据的逻辑结构从逻辑上

2、抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。数据的逻辑结构有两大类：线性结构，非线性结构。1、线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。2、非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等。三、数据的物理结构数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。数据的存储结构可用以下四种基本存储方法：1、顺序存储方法—把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由

3、存储单元的邻接关系来体现。2、链式存储方法—不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。3、索引存储方法—在存储结点信息的同时，还建立附加的索引表。4、散列存储方法—根据结点的关键字直接计算出该结点的存储地址。四、数据的运算数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等。五、算法1．算法的性质一个算法就是一种解题的方法，更严格地讲，算法必须满足以下准则：有穷性：一个算法的执行步骤必须是有限的。确定性：算法中的

4、每一个操作步骤的含义必须明确。可行性：算法中的每一个操作步骤都是可以执行的。输入：一个算法一般都要求有一个或多个输入量。输出：一个算法至少产生一个输出量，它是算法对输入量的执行结果。2、算法性能分析：求解同一个问题，可以有多种不同的算法，那么如何衡量一个算法的好坏呢？显然，首先算法应是正确可行的。其次，通常还要考虑如下三方面的问题：（l）执行算法所耗费的时间。（时间复杂度）（2）执行算法所占用的存储空间。（空间复杂度）（3）算法是否易于理解，易于编码，易于调试。第二部分：线性结构一、基本特点：数据元素有限并有序。线性结构的数据元素可排成一个线性队列：a1，a2，a3，…，an其中

5、，a1为起始元素，an为终点元素，ai为索引号为i的数据元素。又称为线性表。二、常见的线性结构（线性表）：顺序表、链表、堆栈、队列、数组、字符串等。1、顺序表(理解特点)2、线性链表(单向链表、双向链表、循环链表)3、堆栈(先进后出)：口袋装大米4、队列(先进先出)：排队买大米1．顺序表当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。顺序表的特点如下：．物理上相邻的元素在逻辑上也相邻。．可随机存取。．

6、存储密度大，空间利用率高。．对顺序表可进行插入、删除等操作，但运算效率低，需要大量的数据元素移位。2．单链表采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。对链表的访问总是从链表的头部开始，根据每个结点中存储的后继结点的地址信息，顺链进行的。每个结点只有一个指针域时，称为单链表。单链表中，插入删除一个数据元素，仅仅需要修改该结

7、点的前一个和后一个结点的指针域，非常简便，但要访问表中的任一元素，都必须从头指针开始，顺链查找，无法随机访问。．优点：插入、删除操作时移动的元素少。．缺点：所有的操作都必须顺链操作，访问不方便。将顺序表与链表作一比较，可以看出：．顺序存储的访问是随机访问，而链式存储的访问是顺链进行的顺序访问。．顺序存储下插入、删除平均移动一半元素，效率不高，而链式存储下插入、删除效率高。．顺序存储空间利用率高，链式存储需额外增加地址指针的存储，增加空间耗费。3．栈与队列栈与队列是两种特殊的线性表