数据结构总复习ppt课件.ppt

数 据 结 构,西南民院计算机系,TEL 13618097826Emailliu-li-,题型1 选择题 2 填空题 3 解答题 4 算法题,第一章 绪论,第一章 绪 论,计算机的发展硬件 CPU、内、外存储器等软件：系统软件、应用软件应用 科学计算 数据处理 过程控制等处理数据的能力和种类：数值 字符、字符串 具有多个属性对象 图形 图像 声音,数据结构的研究对象：非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。本课程讨论的问题：应用中常用的几种数据结构，以及如何存储,如何处理它们。,第一章 绪 论,1 数据：客观对象的符号表示。例如：课程名，地名，书名都是数据2 数据结构：带有结构和操作的数据元素集合 结构：数据元素之间的关系；操作：对数据的加工处理；,第一章 绪 论,第一章 绪 论,第一章 绪 论,6 数据的存储结构：数据结构在计算机内存中的表示。7 顺序存储结构 用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；8 链式存储结构 用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。数据结构基本操作的实现：基本操作在计算机上的实现（方法）,9 数据结构的表示 1 图示表示 2 二元组表示,图示表示：由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；,第一章 绪 论,二元组表示 用一个二元组（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 数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：也叫基本运算：是指对数据结构的加工处理；数据的存储结构：数据结构在计算机内存中的表示数据结构基本操作的实现：基本操作在计算机上的实现（方法）顺序存储结构链式存储结构10 算法的概念 算法是求解问题的操作序列（或操作步骤）。11 时间复杂度T（n）以求解问题的基本操作（原操作）的执行次数作为算法时间的度量,第二章 线性表,常用的数据结构 1）集合 2）线性结构 3）树结构 4）图结构 5）其它复杂结构,第二章线性表,对每种数据结构，主要讨论如下两方面的问题1 数据的逻辑结构，数据结构的基本操作；2 数据的存储结构，数据结构基本操作的实现,第二章线性表,线性数据结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念 一 线性表的逻辑结构在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。,2.1 线性表的概念,线性表的基本操作1 初始化操作 InitList(&L)2 销毁操作DetroyList(&L)3 置空操作ClearList(&L)4 判空操作ListEmpty(L)5 求表长操作 ListLength(L)6 取元素操作：GetElem(L,i,&e)7 查找操作 LocateElem(L,e,compare()8 插入操作 ListInsert(&L,i,e)9 删除操作 ListDelete(&L,i,&e)10 遍历操作 ListTraverse(&L,visit(),2.1 线性表的概念,2.2 线性表的顺序存储和实现,一 线性表的顺序存储结构顺序表1 顺序表用一组连续的内存单元依次存放线性表的数据元素。,2 顺序表的类型定义typedef struct ElemType*elem;/线性表存储空间基址 int length;/当前线性表长度 int listsize;/当前分配的存储空间大小SqList;,顺序表图示,设 A=（a1,a2,a3,.an）是一线性表，L是SqList 类型的结构变量，用于存放 A,2.2 线性表的顺序存储和实现,顺序表保存了哪些信息?,2.2 线性表的顺序存储和实现,顺序表保存了哪些信息？*线性表中的数据元素；*线性表中数据元素的顺序关系；*表中元素个数（简化算法）*当前分配的存储空间 顺序表如何保存这些信息？3 顺序表存储特点元素存储在一组连续的内存单元中；通过元素存储顺序元素之的逻辑顺序；,二 顺序表的基本操作算法1 初始化算法 InitList_Sq(SqList&L)2 插入操作算法 ListInsert_Sq(SqList&L,int i,ElemType e)3 删除操作算法 ListDelete_Sq(SqList&L,inti,ElemType&e),2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,5 顺序表主要操作特点1）可随机存取顺序表的元素(用L.elemi-1或L.elem+(i-1)可直接定位元素的存储地址)2）插入删除操作通过移动元素实现,23 线性表的链式存储结构和实现,线性表的链式存储结构 用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了相关元素的存储位置。,2.3.1 线性链表一 线性链表的概念1 线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。,23 线性表的链式存储结构和实现,typedef struct Lnode ElemType data;Struct Lnode*next;LNode,*LinkList;,data next,2 线性链表的结点类型定义 及指向结点的指针类型定义,2.3.1 线性链表,2.3.1 线性链表,3 线性链表存储特点1）用一组任意的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；,二 线性链表基本操作算法1 初始化操作算法InitList_L(LinkList&L)2 插入操作算法ListInsert_L(LinkList&L,inti,ElemType e)3 删除操作算法ListInsert_L(LinkList&L,inti,ElemType&e),2.3.1 线性链表,2.3.1 线性链表,5 线性链表操作主要特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；,循环链表 循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点,2.3.2 循环链表,双向链表,双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,2.3.3 双向链表,线性表的其他操作的实现1)通过调用基本操作算法2)直接实现,线性表的其他操作的实现,第二章练习题,；,线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。顺序表存储特点：1）元素存储在一组连续的内存单元中2）通过元素的存储顺序反映线性表中数据元素之的逻辑顺序；顺序表操作特点：1）可随机存取顺序表的元素；2）顺序表的插入删除操作要通过移动元素实现,第二章练习题,线性链表存储特点1）用任意一组的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；线性链表操作特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；顺序表的插入、删除操作平均要移动表的一半元素,第二章练习题,顺序表能随机存取元素的原因是：顺序表能通过L.elemi-1或L.elem+(i-1)直接定位元素的存储地址。线性链表不能随机存取元素的原因是：需从线性链表的头指针开始，顺着链指针定位元素的存储地址对于经常要存取元素的应用，线性表应采用顺序存储结构10 对于经常要插入删除元素的应用，线性表应采用链式存储结构,第三章 栈和队列,栈是限定仅能在表尾进行插入删除操作的线性表。,栈的特点后进先出,3.1 栈,一.栈的概念1 栈的定义,3.1 栈,2 栈的基本操作 1）初始化操作InitStack(&S)2）销毁栈操作DestroyStack(&S)3）置空栈操作ClearStack(&S)4）取栈顶元素操作GetTop(S,&e)5）进栈操作Push(&S,e)6）退栈操作Pop(&S,&e）7）判空操作StackEmpty(S),3.1 栈,二 栈的顺序存储和实现1 栈的顺序存储结构 1）用一组连续的内存单元依次存放自栈底到栈顶的数据元素；2）栈顶元素的位置由栈顶指针指示；,typedef structSElemType*base;/栈底指针SElemType*top/栈顶指针int stacksize;/当前分配的栈空间大小/(以sizeof(SElemType)为单位）SqStack;,3.1 栈,2 顺序栈的类型定义,3.1 栈,顺序栈的图示,栈操作算法1）进栈操作算法：在栈顶插入元素 Push(SqStack&S,SElemType e)2）出栈操作算法：在栈顶插入元素 Pop(SqStack&S,SElemType&e)4 栈操作主要特点进栈、出栈操作要修改栈顶指针,3.1 栈,3.1 栈,栈的链式存储和实现 栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头指针,S,四 栈的应用举例例2 表达式求值算符优先算法：掌握利用操作数栈OPND，运算符栈OPTR，对表达式求值的方法,3.2 栈,第三章练习题,栈是限定仅能在表尾一端进行插入、删除操作的线性表；2 表尾称为栈顶，表头称为栈底；3 栈的具有后进先出的特点；4 栈顶元素的位置由一个栈顶指针指示；5 进栈、出栈操作要修改栈顶指针；6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为：abc,acb,bac,bca,cba,一 队列的概念 队列的定义,队列是限定仅能在表头删除，表尾插入的线性表。,队列的特点先进先出,34 队列,2 队列的基本操作1）初始化操作InitQueue(&Q)2）销毁操作DestroyQueue(&Q)3）置空操作ClearQueue(&Q)4）判空操作QueueEmpty(Q)5）取队头元素操作GetHead(Q,&e)6）入队操作EnQueue(&Q,e)7）出队操作DeQueue(&Q,&e),34 队列,二 循环队列队列的顺序存储和实现循环队列队列的顺序存贮结构（1）在队列的顺序存贮结构中用一组连续存储单元依次存储队列的数据元素（2）队头、队尾元素的位置分别由队头指针和队尾指针指示；（3）将顺序队列设想为首尾相连的环状空间,34 队列,2 循环队列的类型定义,#define MAXSIZE 100/最大队列长度typedef struct QElemType*base;队空间基址 int front;/队头指针 int rear;/队尾指针SqQueue;,34 队列,34 队列,2 队列操作算法入队操作：在队尾插入元素；出队操作：在队头删除元素；,第三章练习题,队列是限定仅能在表尾一端插入，表头一端删除操作的线性表；2 表尾称为队头，表头称为队尾 3 队头、队尾元素的位置分别由队头指针和队尾指针指示；4 队列具有先进先出的特点5 入队操作要修改队尾指针，出队操作要修改队头指针；,第四章 串,4.1 串的基本概念,一、串的概念1 什么是串 串是由零个或多个字符组成的有限序列，一般记作 s=a1,a2,a3,.an,4.1 串的基本概念,2 串的基本操作（了解）串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。串连接操作 Concat(&T,S1,S2)求子串操作SubString(&Sub,S,pos,len)求子串位置操作Index(S,T,pos)串插入操作 StrInsert(&S,pos,T)串删除操作 StrDelete(&S,pos,len),4.2 串存储和实现,一、串的存储（了解）1 定长顺序存储结构 定长顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：#define MAXSTRLEN 255Typedef unsigned char SStringMAXSTRLEN+1,4.2 串存储和实现,2、堆分配存储堆分配存储类似于线性表的顺序存储结构 堆分配存储的类型说明Typedef struct char*ch;/指向存放串值的存储空间基址 int length;/整型域：存放串长Hstring;,第四章练习题,从逻辑结构上看串是线性数据结构；S=ababcabcac,S1=abc，S2=isastringConcat(Hstring&T,Hstring S1,Hstring S2)T=abcisastring 3 请列举两个线性表所没有的串操作:求子串,求子串位置，,第五章 数组和广义表,51 数 组,1 数组的逻辑结构 n 维数组中的每个元素都受n个线性关系的约束，以二维数组为例：二维数组中的每个元素都受两个线性关系的约束,51 数 组,2 数组的基本操作（了解）初始化操作 InitArray(&A,n,bound1,boundn)功能：参数合法，构造数组A，并返回OK；销毁操作 DestroyArray(&A)功能：销毁数组A；3 读元素操作 Value(A,&e,index1,indexn)功能：若指定下标不越界，读指定下标的元素，用e返回，并返回OK；写元素操作 Assign(A,e,index1,indexn)功能：若指定下标不越界，将e赋值给A指定的下标元素，并返回OK；,51 数 组,3 数组的顺序存贮结构(以二维数组为例)两种方式：以行为主序的方式，以列序为主序的方式4 数组元素存储地址的计算,第五章练习题,1 从逻辑结构来看，二维数组中的每个元素都受两个线性关系的约束在行关系中 aij直接前趋是 aij-1，aij直接后继是 aij+1；在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j；二维数组的两种顺序存贮结构为：）以行为主序的方式，）以列序为主序的方式。数组元素存储地址的计算,52 矩阵的压缩存储,矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间一 特殊矩阵1 什么是特殊矩阵 值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵2 特殊矩阵压缩存储 特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系；,52 矩阵的压缩存储,二 稀疏矩阵 1 什么是稀疏矩阵 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。2 稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）稀疏矩阵的压缩存储只存非零元，对每一非零元，除了要保存非零元素的值外，还要保存非零元素在矩阵中的位置；,52 矩阵的压缩存储,3 稀疏矩阵的（非零元）三元组表 A=(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)4 三元组顺序表 用顺序表存储三元组表，非零元三元组以行为主序存储,第五章练习题,1 矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间；2 特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系；3(含零元的)稀疏矩阵的压缩存储只存非零元，对每一非零元，除了要保存零元素的值外，还要保存零元素在矩阵中的位置；4 给出稀疏矩阵，写出对应的（非零元）三元组表 A=(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),53 广义表,1 什么是广义表广义表是数据元素的有限序列。记作：LS=(1,2,n)。其中i其可以是单个元素，也可以是广义表。2 广义表的基本操作求表头求表尾表头：广义表的第一个元素表尾：除第一个元素外，起它元素组成的表,53 广义表,广义表的存储结构（了解）广义表通常采用链式存储结构。链表中有两种的结点：一种是表结点，用以表示广义表；一种是原子结点，用以表示原子；,第五章练习题,广义表是数据元素的有限序列。其元素可以是单个元素，也可以是广义表。2表头：广义表的第一个元素表尾：除第一个元素外，其它元素组成的表,第六章 树和二叉树,6.1 树的有关概念,一 树的概念1 树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；,6.1 树的有关概念,2 树的基本操作（了解）1）InitTree(,6.1 树的有关概念,Root(T);Value(T,cur_e);Assign(T,cur_e,value);Paret(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);InsertChild(,6.1 树的有关概念,2树的应用1）树可表示具有分枝结构关系的对象,例1家族族谱,6.1 树的有关概念,2）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。,6.1 树的有关概念,3）一些应用问题的求解过程可用树结构的来描述,例5 求A=1,2,3 的幂集,6.1 树的有关概念,树的基本术语（了解）树的结点 孩子结点 双亲结点 兄弟结点结点层 树的高度 结点的度 树的度 叶子结点 分枝结点 森林,6.2 二 叉 树,一 二叉树的概念1 二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。,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 二叉树性质（了解）,6.2 二 叉 树,三 二叉树存贮结构1 二叉树的顺序结构,6.2 二 叉 树,2 二叉链表 二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域,6.2 二 叉 树,3 三叉链表 三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域,6.2 二 叉 树,静态二叉链表（了解）,6.3 二叉树的遍历,遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。1 二叉树的遍历方法 先序遍历 DLR 中序遍历 LDR 后序遍历 LRD,6.3 二叉树的遍历,先序遍历（DLR）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；,例 先序遍历序列：-,+,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线索二叉树加上结点前趋后继信息（结索）的二叉树称为线索二叉树,中序序列：D,B,H,E,A,F,C,G,6.5 线索二叉树,2 线索链表,线索二叉树的存储结构，利用二叉链表的空指针域保存结点的前趋后继结点的指针,6.6 树和森林,一树的存贮结构（了解）了解树的存贮方法1 双亲表示法 双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。,6.6 树和森林,2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。方法I：多重链表（类似二叉链表）3 孩子兄弟表示法 该方法用二叉链表作为树的存贮结构通过保存每个结点的第一个结点和它的紧邻的右兄弟的位置，表示树中结点之间的结构关系。,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 二叉树的顺序结构:通过二叉树结点的相对位置，表示结点之间结构关系2二叉链表：通过保存每个结点的左、右孩子结点的存储位置，表示结点之间的结构关系。3 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。4二叉树的遍历方法:先序遍历 DLR、中序遍历LDR、后序遍历 LRD,第六章练习题,5设p是指向二叉链表某结点的指针，请写出将左孩子结点数据赋值给变量e的主要操作语句：q=p-lchild;.e=q-data;6 加上结点前趋后继信息的二叉树称为线索二叉树7 在线索链表中左右指针域或指向孩子结点或指向前趋后继结点8 列举与树的两种存储结构,7.1 图的基本概念,一 图的概念1 图的逻辑结构是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；,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 交通图（公路、铁路）顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；例4 各种流程图,7.1 图的基本概念,三 图的基本术语（了解）1）邻接点及关联边2）顶点的度、入度、出度3）路径、回路4）连通图5）子图,7.2 图的存储结构,一 数组表示法,图的邻接矩阵,数组表示法是图的一种顺序存储结构,7.2 图的存储结构,数组表示法顶点的存储：通常按顶点的编号顺序将顶点数据存储在一维数组中;顶点间关系的存储：用二维数组存储图的邻接矩阵；,7.2 图的存储结构,存储顶点的一维数组,存储邻接矩阵的二维数组,7.2 图的存储结构,无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为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对应线性链表中有无对应的结点；（3）在G中增减边：要在两个单链表插入、删除结点；（4）G占用存储空间：m+2*eG占用存储空间与G的顶点数有关，与G的边数有关；适用于边稀疏的图；,7.2 图的存储结构,2 有向图的邻接表和逆邻接表1）有向图的邻接表 类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储例：,7.2 图的存储结构,2）有向图的逆邻接表 类似于无向图的邻接表，所不同的是：以同一顶点为终点的弧：用线性链表存储例：,7.3 图的遍历,图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。,1 深度优先遍历（连通图的遍历）从图中某顶点v出发：1）访问顶点v；2）从v的未被访问的邻接点出发对图进行深度优先遍历；,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起点的的广度优先序列：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)用顶点表示活动，边表示活动的顺序的有向图称为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）从有向图中删除V及以V为尾的孤；3）重复1）、2）、直接全部输出全部顶点或有向图中不存在无前趋顶点例；,拓扑序列：V1 V2 V3 V4 V5 V6 V7V2 V1 V5 V4 V3 V7 V6,第七章练习题,1 图的逻辑结构：图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；3 数组表示法用邻接矩阵表示结点间的邻接关系4 邻接表是图的链式存储结构5 邻接表用顶点关联边的线性链表表示结点间的邻接关系；,9.1 概 述,本章讨论数据结构：查找表一 查找表的概念1 查找表：由同一类型数据元素（或记录）构成的集合。,2 查找表基本操作构造查找表 Create(&ST,n)2 销毁查找表 Destroy(&ST)3 各种查找操作,9.1 概 述,二 查找的分类及查找的概念（了解）,学号 姓名 专业 年龄 01 王洪 计算机 17 02 孙文 计算机 18 03 谢军 计算机 18 04 李辉 计算机 20 05 沈祥福 计算机 25,9.1 概 述,9.1 概 述,三 查找表的组织方法和查找方法静态查找表 顺序表及查找 有序表及查找动态查找表 二叉排序树哈希表 哈希表及查找,9.1 概 述,平均查找长度（了解）（设查找不成功的可能性很小，可忽略不计）查找方法的平均查找长度=在查找过程中，与给定值比较的关键字个数的数学期望值,9.2 静态查找表,1 顺序表及查找（线性表及查找）查找表组织：将查找表中的记录按线性表的形式来组织 L1=(45,53,12,3,37,24,100,61,90,78)顺序查找法 1）基本思想：从表的最后一个记录（或第一个记录）开始，依次将记录的关键字与给定值比较，若相等：查找成功，否则，继续查找。,9.2 静态查找表,2）说明：优点1）算法简单2）对于查找表的存储结构没有特别的要求缺点 效率不高，平均查找长度=（n+1）/2,9.2 静态查找表,有序表及查找1 有序表：查找表中的记录按关键字有序序2 二分查找法1）基本步骤：将查找范围中间位置的记录关键字与给定值比较：继续在前半个表中查找=：查找成功，返回记录位置：继续在后半个表中查找,1 2 3 4 5 6 7 8 9 10 L2=(3,12,24,37,45,53,61,78,90,100)K=24,9.2 静态查找表,2）说明：*效率比顺序查找高;平均查找长度=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 哈希表：将记录按哈希函数或解决冲突的方法确定的位置存放，所构成的表称为哈希表,例 1949-2000年某地区人口统计表哈希函数 H（KEY）=KEY-1948,9.4 哈希表,哈希函数 H（KEY）=KEY-1948,3 冲突：不同的关键字由哈希函数确定的记录的存储位置相同4 解决冲突的方法：开放地址法，链地址法5 哈希表的查找方法：对于给定值，由哈希函数直接定位记录的存储位置,第九章练习题,1 查找表的逻辑结构：查找表中的记录除同属一个集合外，没有其他关系2 顺序查找法的优点简单、对查找表及存储结构没有什么特殊的要求。3 二分查找法的优点查找效率高4二分查找法要求查找表中的记录按关键字有序5 用二叉排序树组织查找表的优点是既可能有较高的查找效率又可能有较高插入删除效率,第九章练习题,6 哈希表：将记录按哈希函数或解决冲突的方法确定的位置存放，所构成的表称为哈希表7何为冲突：不同的关键字由哈希函数确定的记录的存储位置相同8 列举两种解决冲突的方法：开放地址法、链地址法,10.1 概 述,1 排序定义 设R1 R2 R3 Rn 是n个记录，k1,k2,k3 kn为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。,10.1 概 述,2 分类（了解）按记录的存放位置分类有 内排序：待排记录放在内存 外排序：待排记录放在外存按排序原则分类（内排序）插入排序 交换排序 选择排序 归并排序 基数排序,10.1 概 述,稳性排序：在任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。例 设 49,38,65,97,76,13,27,49 是待排序列排序后:13,27,38,49,49,65,76,97 稳定排序后:13,27,38,49,49,65,76,97不稳定,第十章练习题,1 下面几种排序方法的基本思想 插入，交换、选择，归并2 能写出直接插入、快速排序一趟排序过程,