西南民院计算机系.ppt

1、数 据 结 构,西南民院计算机系,北京理工大学现代远程教育,TEL 85572772 Email:,题型 1 选择题 2 填空题 3 解答题 4 算法题,第一章 绪论,第一章 绪 论,计算机的发展 硬件 CPU、内、外存储器等 软件：系统软件、应用软件 应用 科学计算 数据处理 过程控制等 处理数据的能力和种类：数值 字符、字符串 具有多个属性对象 图形 图像 声音,数据结构的研究对象： 非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。 本课程讨论的问题： 应用中常用的几种数据结构，以及如何存储, 如何处理它们。,第一章 绪 论,1 数据：客观对象的符号表示。 例如：课程名，地名

2、，书名都是数据 2 数据结构：带有结构和操作的数据元素集合 结构：数据元素之间的关系； 操作：对数据的加工处理 ；,第一章 绪 论,第一章 绪 论,第一章 绪 论,6 数据的存储结构： 数据结构在计算机内存中的表示。7 顺序存储结构 用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系； 8 链式存储结构 用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。 数据结构基本操作的实现：基本操作在计算机上的实现（方法）,9 数据结构的表示 1 图示表示 2 二元组表示,图示表示：由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的

3、结构关系；,第一章 绪 论,二元组表示 用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。,D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, , ,第一章 绪 论,第一章 绪 论,10 算法的概念 算法是求解问题的操作序列（或操作步骤） 11 时间复杂度T（n） 以求解问题的基本操作（原操作）的执行次数作为算法的时间度量 空间复杂度 用执行算法所需的辅助空间的大小作为算法所需空间的度量,第一章练习题,1 数据结构：带有结构和操作的数据元素集合。 2 常用的数据结构 数据结构的表示 4 数据的逻辑结构 ：数据之间的结构关系，是具体

4、关系的抽象。 数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理； 数据的存储结构：数据结构在计算机内存中的表示 数据结构基本操作的实现：基本操作在计算机上的实现（方法） 顺序存储结构 链式存储结构 10 算法的概念 算法是求解问题的操作序列（或操作步骤）。 11 时间复杂度T（n） 以求解问题的基本操作（原操作）的执行次数作为算法时间的度量,第二章 线性表,常用的数据结构 1） 集合 2） 线性结构 3） 树结构 4） 图结构 5） 其它复杂结构,第二章线性表,对每种数据结构，主要讨论如下两方面的问题 1 数据的逻辑结构，数据结构的基本操作； 2 数据的存储结构，数据结构基本操作的实

5、现,第二章线性表,线性数据结构： 除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念 一 线性表的逻辑结构 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念,线性表的基本操作 1 初始化操作 InitList( /线性表存储空间基址 int length; /当前线性表长度 int listsize; /当前分配的存储空间大小 SqList;,顺序表图示,设 A =（a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放 A,2

6、.2 线性表的顺序存储和实现,顺序表保存了哪些信息?,2.2 线性表的顺序存储和实现,顺序表保存了哪些信息？ *线性表中的数据元素；*线性表中数据元素的顺序关系； *表中元素个数（简化算法） *当前分配的存储空间 顺序表如何保存这些信息？ 3 顺序表存储特点 元素存储在一组连续的内存单元中； 通过元素存储顺序元素之的逻辑顺序；,二 顺序表的基本操作算法1 初始化算法 InitList_Sq( SqList Struct Lnode *next;LNode, *LinkList;,data next,2 线性链表的结点类型定义 及指向结点的指针类型定义,2. 3. 1 线性链表,2. 3. 1

7、线性链表,3 线性链表存储特点 1）用一组任意的存储单元存储线性表中的数据元素； 2） 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；,二 线性链表基本操作算法 1 初始化操作算法 InitList_L (LinkList /栈底指针SElemType *top /栈顶指针int stacksize; /当前分配的栈空间大小 /(以sizeof(SElemType)为单位）SqStack;,3.1 栈,2 顺序栈的类型定义,3.1 栈,顺序栈的图示,栈操作算法 1）进栈操作算法：在栈顶插入元素 Push(SqStack 队空间基址 int front; /队头指针 int rea

8、r; /队尾指针 SqQueue;,34 队列,34 队列,2 队列操作算法 入队操作：在队尾插入元素； 出队操作：在队头删除元素；,第三章练习题,队列是限定仅能在表尾一端插入，表头一端删除操作的线性表； 2 表尾称为队头，表头称为队尾 3 队头、队尾元素的位置分别由队头指针和队尾指针指示； 4 队列具有先进先出的特点 5 入队操作要修改队尾指针，出队操作要修改队头指针；,第四章 串,4. 1 串的基本概念,一、串的概念1 什么是串 串是由零个或多个字符组成的有限序列， 一般记作 s = a1,a2, a3, . an,4. 1 串的基本概念,2 串的基本操作（了解） 串的逻辑结构与线性表一样

9、，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。 串连接操作 Concat( /指向存放串值的存储空间基址 int length; / 整型域：存放串长 Hstring;,第四章练习题,从逻辑结构上看串是线性数据结构； S=ababcabcac, S1=abc， S2=isastring Concat(Hstring Value(T, cur_e); Assign(T, cur_e, value); Paret(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); InsertChild(,6.1 树的有关概

10、念,2树的应用1）树可表示具有分枝结构关系的对象,例1家族族谱,6.1 树的有关概念,2）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。,6.1 树的有关概念,3）一些应用问题的求解过程可用树结构的来描述,例5 求A=1,2,3 的幂集,6.1 树的有关概念,树的基本术语（了解） 树的结点 孩子结点 双亲结点 兄弟结点 结点层 树的高度 结点的度 树的度 叶子结点 分枝结点 森林,6.2 二 叉 树,一 二叉树的概念 1 二叉树的定义 二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二

11、叉树。,6.2 二 叉 树,二叉树的五种基本形态,6.2 二 叉 树,2 基本操作：（了解） InitBiTree(,6.2 二 叉 树,Root(T); Value(T,e); Assign(T, ,6.2 二 叉 树,InsertChild(T, p, LR, c); DeleteChild(T, p, LP); PreOrderTraverse(T, Visit( ); InOrderTraverse(T, Visit( ); PostOrderTraverse(T, Visit( ); LevelOrderTraverse(T, Visit( );,6.2 二 叉 树,3 二叉树性质（

12、了解）,6.2 二 叉 树,三 二叉树存贮结构 1 二叉树的顺序结构,6.2 二 叉 树,2 二叉链表 二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域,6.2 二 叉 树,3 三叉链表 三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域,6.2 二 叉 树,静态二叉链表（了解）,6.3 二叉树的遍历,遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 1 二叉树的遍历方法 先序遍历 DLR 中序遍历 LDR 后序遍历 LRD,6.3 二叉树的遍历,先序遍历（DLR） 若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；

13、,例 先序遍历序列： -,+,a,*,b,-,c,d,/,e,f,6.3 二叉树的遍历,中序遍历（LDR） 若二叉树非空（1）中序遍历左子树（2）访问根结点 （3）中序遍历右子树,例 中序遍历序列： a,+,b,*,c,-,d,-,e,/,f,6.3 二叉树的遍历,后序遍历（LRD） 若二叉树非空（1）后序遍历左子树（2）后序遍历右子树 （3）访问根结点,例 后序遍历序列： a,b,c,d,-,*,+,e,f,/,-,6.4 遍历的应用,例1 求二叉树的叶子结点个数输入：二叉树的二叉链表结果：二叉树的叶子结点个数,基本思想：在二叉树遍历的过程中，统计叶子结点的个数,6.5 线索二叉树,1线索二

14、叉树 加上结点前趋后继信息（结索）的二叉树称为线索二叉树,中序序列：D,B,H,E,A,F,C,G,6.5 线索二叉树,2 线索链表,线索二叉树的存储结构，利用二叉链表的空指针域保存结点的前趋后继结点的指针,6.6 树和森林,一树的存贮结构（了解） 了解树的存贮方法 1 双亲表示法 双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。,6.6 树和森林,2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。 方法I ：多重链表（类似二叉链表） 3 孩子兄弟表示法 该方法用二叉链表作为树的存贮结构通过保存每个结点的第一个结点和它的紧邻的右兄

15、弟的位置，表示树中结点之间的结构关系。,6.6 树和森林,树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。 树与二叉树转换方法,树 根 结点X的第一个孩子 结点X紧邻的右兄弟,二叉树 根 结点X的左孩子 结点X的右孩子,6.6 树和森林,6.6 树和森林,三 树的遍历 先根遍历 先访问根，然后依次先根遍历根每一颗子树。例 先根遍历序列 A B C D E 后根遍历 依次后根遍历根的每一颗子树，然后访问根。后根遍历序列 B D C E A,6.7 哈夫曼树及应用,1 哈夫曼树 带权路径最短的二叉树 2 哈夫曼编码,第六章练习题,1 二叉树的顺序结构:

16、通过二叉树结点的相对位置，表示结点之间结构关系 2二叉链表：通过保存每个结点的左、右孩子结点的存储位置，表示结点之间的结构关系。 3 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、后序遍历 LRD,第六章练习题,5设p是指向二叉链表某结点的指针，请写出将左孩子结点数据赋值给变量e的主要操作语句：q=p-lchild;.e=q-data; 6 加上结点前趋后继信息的二叉树称为线索二叉树 7 在线索链表中左右指针域或指向孩子结点或指向前趋后继结点 8 列举与树的两种存储结构,7.1 图的基本概念,一 图的概念 1 图的逻

17、辑结构 是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；,7.1 图的基本概念,无向图：在图G中，若所有边是无向边，则称G为无向图有向图：在图G中，若所有边是有向边，则称G为有向图混和图：在图G中，即有无向边也有有向边，则称G为混合图,7.1 图的基本概念,2 图的基本操作（了解） CreateGraph(,7.1 图的基本概念,FirstAdjVex(G,v); NextAdjVex(G,v,w); InsertVex(,7.1 图的基本概念,二 图的应用举例（了解） 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有

18、向边、无向边表示； 例4 各种流程图,7.1 图的基本概念,三 图的基本术语（了解） 1） 邻接点及关联边 2） 顶点的度、入度、出度 3） 路径、回路 4） 连通图 5） 子图,7.2 图的存储结构,一 数组表示法,图的邻接矩阵,数组表示法是图的一种顺序存储结构,7.2 图的存储结构,数组表示法 顶点的存储：通常按顶点的编号顺序将顶点数据存储在一维数组中;顶点间关系的存储：用二维数组存储图的邻接矩阵；,7.2 图的存储结构,存储顶点的 一维数组,存储邻接矩阵的 二维数组,7.2 图的存储结构,无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）判断两顶点v、u是否为邻

19、接点：只需判二维数组对应分量是否为1；3）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；4）设存储顶点的一维数组大小为m(m图的顶点数n), G占用存储空间：m+m2； G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；,7.2 图的存储结构,邻接表 邻接表是图的链式存储结构1 无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用线性链表存储,7.2 图的存储结构,例,7.2 图的存储结构,无向图的邻接表的特点 （1）在G邻接表中，同一条边对应两个结点；（2）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点； （

20、3）在G中增减边：要在两个单链表插入、删除结点； （4）G占用存储空间：m+2*e G占用存储空间与G的顶点数有关，与G的边数有关；适用于边稀疏的图；,7.2 图的存储结构,2 有向图的邻接表和逆邻接表 1）有向图的邻接表 类似于无向图的邻接表，所不同的是： 以同一顶点为起点的弧：用线性链表存储 例：,7.2 图的存储结构,2）有向图的逆邻接表 类似于无向图的邻接表，所不同的是： 以同一顶点为终点的弧：用线性链表存储 例：,7.3 图的遍历,图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。,1 深度优先遍历（连通图的遍历）从图中某顶点v出发：1）访问顶点v；2）从v的未被

21、访问的邻接点出发对图进行深度优先遍历；,7.3 图的遍历,例 图G中，以V1起点的的深度优先序列： (1) V1,V2,V4,V5,V8,V3,V6,V7 (2) V1,V3,V6,V7,V2,V4,V8,V5,由于没为有规定访问邻接点的顺序，深度优先序列不是唯一的,7.3 图的遍历,2 广义优先遍历（按层遍历） 从图中某顶点v出发： 1）访问出发点v ； 2）然后访问v的所有未被访问的邻接点w1 ,w2 , wk ； 3）然后依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；,7.3 图的遍历,例 图G中，以V1起点的的广度优先序列：

22、 V1,V2,V3,V4,V8,V5,V6,V7, V1,V3,V2, V6,V7,V4,V5,V8,由于没为有规定访问邻接点的顺序，深度优先序列不是唯一的,7.3 图的遍历,3 非连通图的遍历（了解） 深度优先序列：V1,V2,V3,V4,V5,V6 广度优先序列：V1,V2,V4,V3,V5,V6,7.4 有向无环图的应用,应用中，可用有向图来表示工程的流程 AOV网( activity on vertex net ） AOE网( activity on edge net,7.4 有向无环图的应用,AOV网( activity on vertex net ) 用顶点表示活动，边表示活动的顺

23、序的有向图称为AOV网 例1 某工程可分为7个子工程， 工程流程可用如下AOV网表示：,7.4 有向无环图的应用,4 AOE网( activity on edge net ) 用边表示活动，顶点表示事件的有向图称为AOE网,事件发生表示以该事件为起点的话动可以开始，以该事件为终点的话动已经。,7.4 有向无环图的应用,2 拓扑排序 拓扑序列：有向图D的一个顶点序列称作一个拓扑序列，如果该序列中任两顶点v 、u ，若在D中v是u前趋，则在序列中v也是u前趋。拓扑排序: 就是将有向图中顶点排成拓扑序列,7.4 有向无环图的应用,拓扑排序方法： 1）从有向图选一无前趋的顶点V，输出；2）从有向图中删

24、除V及以V为尾的孤；3）重复1）、2）、直接全部输出全部顶点或有向图中不存在无前趋顶点例；,拓扑序列： V1 V2 V3 V4 V5 V6 V7 V2 V1 V5 V4 V3 V7 V6,第七章练习题,1 图的逻辑结构：图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继； 3 数组表示法用邻接矩阵表示结点间的邻接关系 4 邻接表是图的链式存储结构 5 邻接表用顶点关联边的线性链表表示结点间的邻接关系；,9.1 概 述,本章讨论数据结构：查找表 一 查找表的概念 1 查找表：由同一类型数据元素（或记录）构成的集合。,2 查找表基本操作 构造查找表 Create(平均查找长度=log2（n+1） * 要求查找表中的记录按关键字有序； * 查找表中的记录要用顺序表存储；,9.3 动态查找表,1 二叉排序树 2 二叉排序树插入 3 二叉排序树的查找,9.3 动态查找表,关键字序列：45,53,12,3,100,37,24,61,90,78,9.4 哈希表,上两节介绍的查找表的查找方法,共同特点： 通过比较查找，即通过将记录关键字值与给定值比较，来进行查找。 查找算法的时间效率取决于查找过程中所进行的比较次数。,9.4 哈希表,1 哈希函数 用来定义记录的关键字与记录存储位置的对应关系的函数 2 哈希表：将记录按哈希函数或解决冲