数据结构62777.ppt

数据结构 第一章 算法与数据结构概述 第二章 简单数据结构 第三章 排序 第四章 检索 第五章 树结构 第六章 图结构 第七章 多维数组、稀疏矩阵和广义表 第一章 算法与数据结构概述 1.1?? 数据结构基本概念 1.2?? 数据的逻辑结构 1.3?? 数据的存储结构 1.4?? 数据的运算 1.5?? 算法及表示 1.6?? 算法时间及空间复杂分析 1.1?? 数据结构基本概念数据结构是计算机科学的重要基础，近年来发展成为一个专门学科，经过多年的研究，根据各种实际问题的要求，提出了许多组织数据的方法，构造了不同的数据结构，而且随着处理实际问题的要求，还会提出新的更加复杂的数据结构。数据结构主要研究要问题的求解方法，典型数据结构的算法及程序设计方法。对于每一种数据结构，主要包括3方面的内容：数据之间的逻辑关系，称为数据的逻辑结构；数据在计算机中的存储方式，称为数据的存储结构；数据的运算。讨论这三个问题的主要目的是为了提高数据处理效率。所谓提高数据处理效率体现为：数据处理的速度，尽量节省数据处理过程中所占用计算机存储空间。 1.1?? 数据结构基本概念 下面通过实例来说明数据结构组织对数据处理效率的影响：一、无序表的顺序查找与有序表的二分查找。表1 ：表2：若要在表1 中查找一个元素，由于数据存放的没有规律，只能从第1个数开始顺序进行查找，直到所有的数据找完为止。若要在表2 中查找一个元素，由于数据是从小到大有规律存放，可用二分法进行查找，提高查找效率。这与字典中的内容按顺序编辑方便查找是一样。 1.1?? 数据结构基本概念 二、学生成绩登记表中的数据处理。学生情况登记表在表中查找给定学号的某学生的情况是很方便的，只要给定学号就要立即查到该学生的情况（学号从小到大排列）。若要查找某个分数段的学生情况，只需把以上数据重组得到其它的表格，即可得到所查结果。可见把数据组织成不同的形式，便于做某种运算，从而提高了数据的处理效率。 1.2?? 数据的逻辑结构数据的逻辑结构是对数据间关系的描述，形式上或用一个二元组来表示，即：B=（K，R）K为结点的有穷集合，即K是由有限个结点所构成的集合；R是K上的关系的有穷集合，即R是有限关系所构成的集合，其中关系都是K到K的关系。结点类型是指结点的值的组织方式，即数据的类型。可分为初等类型及组合类型两大类型，只含为一个基本数据类型属于初等类型（整型、实型、字符型、指针类型）；组合类型是由初等类型以某种方式组合而成的。数据结构分为线性数据结构和非线性结构线性结构：数据结构里有且仅有一个终端结点和一个开始结点，所有结点最多只有一个前驱的一个后继。（数组）非线性结构：不满足线性结构的数据。（树、图） 1.2?? 数据的逻辑结构线性结构的表示形式：K={A，B，C，D，E，F}R=A，B,B，C,C，D,D，E,E，F。数据结构里有且仅有一个终端结点和一个开始结点，所有结点最多只有一个前驱的一个后继。非线性结构表示形式：K={k1…k9}R=k1,k2, k1,k3 , k1,k4 , k1,k7 , k1,k8 , k4,k5 , k4,k6 , k8,k9 。 1.3?? 数据的存储结构数据的逻辑结构与数据的存储结构无关，是独立于计算机的，计算机存储器有有限个存储单元，每个单元有惟一的地址，存储单元是连续编址的。建立一个从结点到地址单元的映像，体现结点之间的关系。有4 种基本的存储映像方法：顺序方法：主要用于线性数据结构。把逻辑上相邻的结点存储在物理上相邻的存储单元内，结点之间的关系由存储单元的连接关系来体现。链接方法：每个结点附上指针字段，存储单元内容分为二部分：结点本身与存放后继结点的存储单元地址。索引方法；在线性结构里，结点排成序列k1,k2,…,kn ,每个 ki在序列里都有对应的位置i，这个位置为结点的索引，用结点的 索引号来确定结点的存储地址。散列法：根据结点的值来确定它的存储地址，用散列函数。 1.4?? 数据的运算各种逻辑结构有其相应的运算，每种逻辑结构有一个运算集合。数据的运算是定义在数据的逻辑结构上的，运算的具体实现要在存储结构上进行，常见的运算有检索、插入、删除、更新、排序、遍历。检索：是在数据结构中查找满足条件的结点。插入：是在数据结构中的指定位置增加新的结点。删除：是把指定位置的结点从数据结构中删除。更新：是指改变数据结构中指定结点的一个或多个字段的值。排序：是指保持线性结构的结点序列结点数不变，把结点按某种指定顺序重新排列。遍历：是指按某种方式，访问过数据结构中的每个结点。 1.5?? 算法及表示算法是为解决一个问题采取的方法和步骤，换句话说，算法是为实现某个计算过程而规定的基本动作的执行序列。算法分为数值算法与非数值算法。算法的五个特点：一、有限操作步骤（