《计算机软件技术基础》2012版-2数据结构

1、计算机软件技术基础（合肥工业大学朱家诚）226第2章常用数据结构及其运算2.1概述2.1.1 什么是数据结构数据结构是计算机应用方面的基础课程之一。要想有效地使用计算机，仅掌握计算机语言而缺乏数据结构和算法的有关知识是难以应付众多复杂的应用课题的。数据结构是研究非数据运算程序设计问题，也就是数据处理问题。即对数据集合中的各元素以各种方式进行运算，数据之间的关系、如何组织数据和如何高效地处理这些数据。2.1.2 有关数据结构的基本概念和术语1数据（data）数据是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。2数据元素(data element)数据元素是数据集合中的一个个体，

2、是数据的基本单位。数据元素不一定是单个的数字或字符，它本身也可能是若干个数据项的集合。3数据对象具有相同性质的数据元素的集合称为数据对象。4数据结构是指同一数据对象中各数据元素间存在的关系S = ( D , R )数据结构S是一个二元组，其中D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。5逻辑结构与物理结构逻辑结构是数据元素及其关系的数学特性数据结构。物理结构是逻辑结构在计算机中的映象存储结构。6数据类型是指程序设计语言中允许的变量的类型。数据类型可分为基本数据类型和结构数据类型。7数据结构与算法算法是解决某一特定类型问题的有限运算序列，算法的实现必须借助程序设计语言中提

3、供的数据类型及其运算。一个算法的效率往往与数据的表示形式有关，因此，数据结构的选择对数据处理的效率起着至关重要的作用。数据结构算法程序2.1.3 算法分析技术初步1时间复杂度常见的时间复杂度：这里用频度和时间复杂度这两个概念进行估算。常见的时间复杂度有：常量型、多项式型、对数型和指数型2空间复杂度空间复杂度是指在算法中所需的辅助空间单元。它们与问题尺寸n之间的关系。当与尺寸n无关时，空间复杂度：。时间与空间是一对矛盾，要节约空间往往就要消耗较多的时间。2.2线性表在数据处理中，大量数据均以表格形式出现，称为线性表，它是一种最简单也是最常见的数据结构。2.2.1 线性表定义和运算（1）一维向量：

4、（2）多维向量：（3）一般的表示形式为：（4）结构特点：数据元素之间的关系是线性关系。线性表的定义和运算结构特点是数据元素之间是线性关系，即在线性表中必存在唯一的一个“第一个”元素，必存在唯一的“最后一个”元素。 （5）有序表：存储方式：向量和链表主要运算：插入、删除、查找和排序。2.2.2顺序存储线性表（1）存储结构（2）基本运算：插入、删除、查找、排序等。（3）时间分析：平均移动次数。从上述分析可以看出，无论是插入或删除一个元素，平均需要移动表中一半元素，这在表长n较大时是相当可观的。2.2.3线性链表（1）链式存储结构（2）链表的基本运算：插入和删除插入、删除、查找、排序等。（3）链表的

5、其它形式：循环链表；双向链表。2.2.4 向量与链表的比较（1）线性表的长度是否固定；（2）线性表的主要操作是什么；（3）采用的算法语言2.3栈与队栈与队是两种特殊的线性表，它们的运算规则较一般线性表有更多的约束和限制，因此又称为限定性数据结构。（1）栈的结构和运算（2）队的结构和运算2.3.1栈的结构与运算（1）栈的定义（2）栈的结构：顺序栈和链栈（3）栈的应用（表达式求值）详细解释“表达式求值”过程。进一步说明数据结构算法的重要性。2.3.2 队的结构与运算（1）队的定义（2）队的结构：顺序队和链队（3）队的应用：多任务管理问题（缓冲区设计）。2.4数组数组已广泛应用于各种高级语言中，是我

6、们比较熟悉的一种数据结构。（1）数组的定义维数（2）数组的顺序存储结构按行优先、按列优先、特殊矩阵的存放方式。（3）数组的链式存储结构单链表、十字链表结构。2.5树与二叉树（1）树的定义（2）树的存储结构（3）二叉树定义：二叉树是n个结点的有限集合，它或为空树，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。（4）二叉树的基本性质（结点数与层深度等性质）（5）特殊形式的二叉树満二叉树：（如何对结点进行编号）完全二叉树：编号相同则称为完全二叉树。平衡二叉树（6）一般树转换为二叉树由于二叉树具有一些特点（二叉链表等），所以要研究从一般树到二叉树、二叉树到一般树的转换。为了转换需对

7、结点进行排序。一般树转换为二叉树的方法为：（7）二叉树的遍历（8）二叉树的应用深度优先、广度优先2.6图（1）图的定义图分为无向图和有向图。若图中每一条边附有一个对应的数，则称为网，这些数称为权，它可以表示两顶点之间的距离或花费的代价。（2）有关图的基本术语l 子图l 度、入度和出度（顶点相连的边数目）l 路经和回路（从一顶点到另一顶点间的顶点序列）l 连通图和连通分量（3）图的存储结构邻接矩阵邻接表（4）运算（遍历）深优先广优先（5）图的应用2.7 查找2.7.1查找的基本概念查找是数据处理中最基本的操作之一，当查找所的数据量很大时，查找方法的效率直接影响到数据处理的速度，而查找方法又与数据

8、结构有关。关键字：在数据处理中，被查找的元素通常是以记录形式出现，即每一个数据元素由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字，此外称为次关键字。本节介绍的查找方法主要按主关键字查找，记录的集合称为表格或文件。定义：给定一个值K，在含有n个记录的文件中进行查找，寻找一个关键字值等于K的记录，如找到则输出该记录，否则查找不成功的信息。查找的方法线性查找、对分查找、分块查找、二叉排序树查找。2.7.2 线性查找线性查找又称为顺序查找，是一种最简单的查找方法。线性查找的改进：将K值加入表中，放在最后，这样，在查找过程中，不需对是否查完进行判断了。提高了查找效率。2.7.3 对分查找如果记录在文件中是按关键字有序排列的，则在进行查找时可以不必逐个比较，而采用较快的方法，如：对分法。2.7.4 分块查找2.7.5 二叉排序树查找线性表查找中，对分法效率较高，但需排序，且不能用链表作为存储结构。2.8排序2.8.1 排序的基本概念将原序列排成一个按关键字有序的序列。排序的