中原工学院数据结构复习重点,考点

1、单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。(掌握单链表的增删改查算法),用C语言描述的单链表结点如下：,Typedef char ElemType; typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;,b,c,d,a,i=0,i=1,i=2,i=3,head,头结点,a,d,c,采用尾插法建立单链表的过程,4.插入元素操作,分析：在线性表中“插入”一个元素时，使元素之间的关系改变为和。由此，算法的基本思想就是，首先找到第i-1个结 点，然后修改相应指针。,5.删除元素操作,分析：和插

2、入类似，由于删除元素ai改变了元素之间的逻辑关系，使ai1不再是ai的后继，而是ai1的后继：首先找到第 i-1 个结点，然后修改相应指针。,例、在含有尾指针的循环链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。（循环链表）,LinkList connect(LinkList ra，linklist rb) /ra、rb为两个表的尾指针 LinkList p=ra-next; ra-next=(rb-next)-next delete rb-next; rb-next=p; return rb; ,通常称top为栈顶指针,base为栈底指针。

3、 顺序栈的类型定义如下： typedef char SElemType; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,void conversion( ) InitStack(s); cinn; while(n) push(S,n%2); n=n/2; while(! StackEmpty(S) Pop(s,e); coute; ,使用堆栈实现十进制与二进制的转换,3.4.2 链队列 1.链队列的定义 队列的链式存储结构简称为链队列，它是限制 仅在表头删除和表尾插入的单链表。显然仅有单链 表的头

4、指针不便于在表尾做插入操作，为此再增加 一个尾指针，指向链表的最后一个结点。,链队列的类型LinkQueue定义为如下： struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue;,(3)入队 Stutas EnQueue(LinkQueue ,(4)出队 Status DeQueue(LinkQueue ,循环队列的类型定义。 #define MAXQSIZE 100 typedef char QElemTy

5、pe; typedef Struct QElemType *base; int front; int rear; SqQueue;,如何判断队列“空”还是“满”。 解决此问题的方法至少有三种： 设标志位(上次的更新动作)：0-创建/删除，1-插入 引入队列长度 少用一个元素空间约定：当Q.front=(Q.rear+1)%MAXQSIZE时队满,练习题 1、设一个栈的入栈序列是ABCD，则借助一个栈所得的出栈序列不可能是（ ）。 A.ABCD B.DCBA C.ACDB D.DABC,2、设top为链栈(无头结点)的栈顶指针，则空栈的条件是（ ）。 A.n=0 B.top-next=0 C.t

6、op=NULL D.top-next=NULL,3、设栈的输入序列是1，2，.，n，若输出序列的第一个元素是n，则第i个输出元素是（ ）。 A.n-i+1 B. i C. n-i D. 前面都不正确,4、队列的工作方式是（ ）。 A.可在队尾删除 B. 可在队头插入 C. 先进先出 D. 先进后出,5、循环队列Q为空的条件是（ ）。 A. MAXQSIZE=0 B. Q.front=Q.rear C. Q.front=Q.rear-1 D. Q.front =(Q.rear + 1) % MAXQSIZE,6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当

7、从队列中删除一个元素，再插入两个元素后， rear和front的值分别为（ ）。 A.1和5 B. 2和4 C.4和2 D.5和1,7、指出下列程序段的功能是什么？ (1) void demo1(SqStack s) int i; int arr64; int n=0; while (!StackEmpty(s) arrn+=pop(s); for(i=0;in;i+) push(s,arri); ,(2) void demo2(SqStack s,int m) SqStack t; int i; initstack(t); while(! StackEmpty(s) if(i=pop(s)!

8、=m) push(t,i); while(! StackEmpty(t) i=pop(t); push(s,i); ,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G， M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟 结点A是结点F，G的祖先,树的基本概念;,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。二叉树的5种基本形态：,例：若一个完全二叉树有145

9、0个结点，则度为1的结点个数为 ，度为2的结点个数为 ， 叶子结点的个数为 ，有 个结点有左孩子，有 个结点有右孩子；该树的高度为 。 (性质3、性质4以及完全二叉树的特征),答案：1 724 725 725 724 11,练 习,2.二叉链表 存储二叉树经常用二叉链表法,按先序遍历,其先序序列为： -+a*b-cd/ef 按中序遍历,其中序序列为： a+b*c-d-e/f 按后序遍历,其后序序列为： abcd-*+ef/-,例1统计二叉树中叶子结点的个数.,void CountLeaf (BiTree T, int ,例：已知 先序序列 ABHFDECKG 和 中序序列 HBDFAEKCG

10、, 构造二叉树过程如下：,6.4.1树的存储结构 1.双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。,6.4树与森林,2.孩子表示法： (1)多重链表法（两种） (2)孩子链表法 将每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，n个结点有n个孩子链表，n个头指针组成线性表。,d为树的度,同构,degree,child1,childd,.,d为结点的度,不同构,data,A,B,C,D,E,F,G,C,E,F,G,0,4,5,6,3,1,2,6,孩子链表法示例,结点结构,data,nextSibling,3.孩子兄弟表示法,除信息

11、域外，再增加两个分别指向该结点的第一个孩子和下一个兄弟结点的指针,firstChild,树 二叉树 方法： 树中所有相邻兄弟间加一连线； 对树中的每个结点，只保留其与第一个孩子间的连线，删去它与其他孩子间连线； 以树根为轴心，将整棵树顺时针旋转45度，使之结构层次分明。,6.4.2 森林与二叉树的转换,树的遍历示例,先根遍历：ABEHIJCDFGK 后根遍历：HIJEBCFKGDA,森林的遍历示例,先序遍历森林：ABCDEFGHIKJ 中序遍历森林：BCEDAGFKIJH,已知a,b,c,d,e,f,g,h出现的频率分别为：0.05,0.29, 0.07,08,0.14,0.23,0.03,0

12、.11,构造赫夫曼树并编码。并计算WPL,练 习,例 w=5, 29, 7, 8, 14, 23, 3, 11,7.2 图的存储结构,（1）邻接矩阵表示顶点间相联关系的矩阵 定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,带权的无向图的邻接矩阵,邻接表,逆邻接表,深度优先搜索过程,6,7,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,I,H,1,2,3,4,5,8,9,1,2,3,4,5,6,7,8,9,前进 回退,深度优先生成树,广度优先搜索过程,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7

13、,8,9,1,2,3,4,5,6,7,8,9,广度优先生成树,I,构造最小生成树方法,方法一：普里姆(Prim)算法 加顶点法，时间复杂度O(n2) 从某顶点开始，找其相邻边中权值最小的边所连另一个顶点，再找与这两个顶点相邻边中权值最小的边所连第三个顶点，重复操作，扩展到所有顶点。,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图 (a) (b),5,0,4,6,1,3,2,10,(c) (d) (e) (f),5,0,4,6,1,3,2,10,22,12,5,0,4,6,1,2,1

14、0,25,14,22,16,12,3,25,22,12,5,0 28,0 10,0,5,1,2,3,4,6,0 28,5 25,4,0,5,4,1,2,3,6,0 28,4 22,4 24,3,0,5,4,3,1,2,6,0 28,3 12,3 18,2,0,5,4,3,2,1,6,2 16,3 18,1,1 14,6,6,0,5,4,3,2,1,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图,12,5,0,6,1,3,2,4,克鲁斯卡尔(Kruskal)算法,AOV网络及其邻接表表示（拓扑排序）,C0,C1,C2,C3,C4,C5,C0 C1 C2 C3 C

15、4 C5 ,0 1 2 3 4 5,indegree data firstarc,1 3 0 1 0 3,1,adjvex nextarc,3 ,5 ,1,5 ,0,1,5 ,3. 关键路径,问题提出 把工程计划表示为有向图，用顶点表示事件(Event) ，弧表示活动(Activity) ，边上权值表示活动持续时间 Duration) ； 每个事件表示在它之前的活动已完成，在它之后的活动可以开始.,例： 设一个工程有11项活动，9个事件 事件 V1表示整个工程开始 事件 V9表示整个工程结束 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？,AOE网,最短路径问

16、题,问题解法 单源最短路径问题 Dijkstra算法 按路径长度递增的次序产生最短路径 所有顶点之间的最短路径 Floyd算法,0,1,2,3,4,10,60,100,20,50,30,10,终点 v1 v2 v3 v4 vj S i=1 10 30 100 i=2 i=3 i=4,1 0,1, 60, 30, 100,3 0,1,3, 50, 90,2 0,1,3,2, 60,4 0,1,3,2,4,0,1,2,3,4,10,20,30,10,50,60,10,30,学习提要,查找方法,比较式查找法,计算式查找法,基于树的查找法（动态）,基于线性表的查找法（静态）,分块（或索引顺序）查找法,

17、折半（或二分）查找法,顺序查找法,对存储结构和关键字排列方式没有特殊要求,只适合顺序存储的有序表,另建一个索引表，分块有序，块间可用折半查找，块内顺序查找,二叉排序树,平衡二叉树（AVL）,B_树,B+树,哈希法/散列法/杂凑法,在记录存储位置与关键字之间建立确定的关系哈希函数,左子树上所有节点的值小于根节点的值 ，右子树上所有节点的值均大于根节点的值,左、右子树深度之差的绝对值不超过1的二叉排序树,一种平衡的多路查找树，m叉树,B_树的变型树，关键字信息全部在叶子结点中，其它结点是其索引,二叉排序（查找）树创建举例：,例 10， 18， 3， 8， 12， 2， 7， 3,10,中序遍历二叉

18、排序树可得到一个关键字的有序序列,4 . 二叉排序树的删除,要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针 f-lchild=NULL 或 f-rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p p只有右子树，用p的右孩子代替p p左、右子树均非空 查找p的中序遍历直接前驱（或直接后继），替代p,原则：删除后保持所有节点的中序遍历顺序不变,8,4,12,6,5,7,10,14,11,16,13,练习,依次删除13、12、4、8,平衡二叉树：平衡因子BF (Balance Factor),每个结点附加一个数字, 给出该结点左子树的高度减

19、去右子树的高度所得的高度差,这个数字即为结点的平衡因子balance 。 AVL树任一结点平衡因子只能取 -1, 0, 1, 如果一个结点的平衡因子的绝对值大于1,则这棵二叉搜索树就失去了平衡, 不再是AVL树。 如果一棵二叉搜索树是高度平衡的, 且有 n 个结点，其高度可保持在O(logn),平均搜索长度也可保持在O(logn)。,左右双旋转,右左双旋转,如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。,例，输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。, 16, 3, 7, 11, 9, 26

20、, 18, 14, 15 ,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等,填充哈希表，并计算查找成功时的ASL,(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m,H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5,H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，

21、H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9,ASL=(1*6+2+3*3+4+9)/12=2.5,14,1,68,27,55,19,20,84,79,23,11,10,H(19)=6,H(14)=1,H(23)=10,H(1)=1 冲突，H1=(1+1) MOD16=2,H(68)=3,H(20)=7,H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8,H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3

22、=(1+3)MOD16=4,H(11)=11,H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12,(2) 用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79),本章小结,查找的基本概念 静态查找表（基于线性表的查找法） 顺序查找、二分查找、分块查找 动态查找表（基于树的查找法） 二叉排序树、二叉平衡树、 B_ 树、B+ 树 哈希表（计算式查找法） 构造哈希函数的方法 直接定址、数字分析、平方取中、折叠、除留余数、随机数 处理冲突的方法 开放定址、再

23、哈希、链地址、建立一个公共溢出区,按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序 按排序所需工作量 简单的排序方法：T(n)=O(n) 先进的排序方法：T(n)=O(nlogn) 基数排序：T(n)=O(d.n),4、排序分类,例1,49 38 65 97 76 13 27 49,i=2 38 (38 49) 65 97 76 13 27 49,i=3 38 (38 49 65) 97 76 13 27 49,i=4 38 (38 49 65 97) 76 13 27 49,i=5 76 (38 49 65 76 97) 13 27 49,i=6 13 (13 38 49 65 76 97) 27 49,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97) 49,76,65,49,38,27,直接插入排序举例,i=8 (13 27 38 49 49 65 76 97),49,38