数据结构复习内容讲解

1、数据结构细补班材料 1、时间复杂度的计算和一些基本概念 什么是数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为： Data_Structure=（ D, S） D：元素有限集 还分成数值类型和非数值类型 S：关系有限集 数据 （data）所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声 音、图像等信息 ）。 数据元素 （data element）是数据的基本单位，具有完整确定的实际意义（ 又称元素、 结点，顶点、记录等） 。 数据项 （Data item）构成数据元素的项目。是具有独立含义的最小标识单位（又称字 段、域、属性 等）。 逻辑结构 数据元素之

2、间的逻辑关系。 即从逻辑关系上描述数据， 它与数据的存储无关， 是独立于 计算机的。逻辑结构可细分为 4 类： 集合结构： 仅同属一个集合 线性结构 : 一对一（ 1:1） 线性 树 结 构 : 一对多（ 1:n） 非线性 图结构 : 多对多 （m:n） 非线性 物理结构 物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示(或映像) 。它依 赖于计算机。 存储结构可分为 4 大类： 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 数据的运算 数据的运算是在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。 最常用的数据运算有 5 种： 插入、删除、修改、查找、排序 抽

3、象数据类型 抽象数据类型： 由用户定义， 用以表示应用问题的数据模型。 它由基本的数据类型构成， 并包括一组相关的操作。 算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。 算法有 5 个基本特性：有穷性、确定性、可行性、输入和输出 算法评价有 4 个指标：运行时间、占用空间、正确性和简单性 评价指标中的运行时间，就是用时间复杂度来衡量的。 时间复杂度 表现形式： O(f(n) 渐进符号( O)的定义： 当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n) ，则 f(n) = O(g(n) 3n+2=O(n) 3n+3=O(n) 100n+

4、6=O(n) /* 3n+2 4n for n 2 */ /* 3n+3 4n for n 3 */ /* 100n+6 101n for n 10 */ 10n2+4n+2=O(n2) /* 10n2+4n+2 11n2 for n 5 */ 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n 4 */ 常见的时间复杂度， 按数量级递增排列依次为： 常数阶 O(1) 、对数阶 O(log2n) 、线性阶 O(n) 、 线性对数阶 O(nlog2n)、平方阶 O(n2) 、立方阶 O(n3) 、k 次方阶 O(nk) 、指数阶 O(2n) 。 下面我们通过例子加以说明，让大

5、家碰到问题时知道如何去解决。 1 、 设 三 个 函 数 f,g,h 分 别 为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 h(n)=n1.5+5000nlgn 请判断下列关系是否成立： 1) f(n)=O(g(n) 2) g(n)=O(f(n) 3) h(n)=O(n1.5) 4) h(n)=O(nlgn) (1) 成立。题中由于两个函数的最高次项都是n3,因此当 n时，两个函数的比值是 个常数，所以这个关系式是成立的。 ( 2)成立。与上同理。 ( 3)成立。与上同理。 ( 4)不成立。 由于当 n时 n1.5 比 nlgn 递增的快， 所以 h(n)与

6、nlgn 的比值不是常数， 故不成立。 2、设 n 为正整数，利用大 O记号，将下列程序段的执行时间表示为n 的函数。 (1) i=1; k=0 while(i1 while (x=(y+1)*(y+1) y+; 解答： T(n)=n1/2 ，T(n)=O(n1/2) ，最坏的情况是 y=0 ，那么循环的次数是 n1/2 次，这是一 个按平方根阶递增的函数。 (3) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; 解答： T(n)=O(1) ， 这个程序看起来有点吓人，总共循环运行了 1000 次，但是我们看到 n 没有? 没。这段程序的

7、运行是和 n 无关的，就算它再循环一万年，我们也不管他，只是一个 常数阶的函数。 2、线性结构 逻辑结构： 1. 描述 :线性表是由 n (n=0) 个数据元素 (结点)a1,a2, .,ai, 组.,成an的有限序列。 其 中，数据元素的个数 n 定义为表长。当 n=0 时称为空表，非空的线性表 (n0) 记为： (a1,a2, .,ai, .,an) 注意: 1.数据元素 ai 是一个抽象的符号 2. ai 可取各种数据类型 3. 一般情况下 ,同一线性表中的元素具有相同的数据类型 4. i 是元素的序号 (1=i=n) 2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有

8、一个直接前 趋和一个直接后继 线性表的运算： 线性表的常见基本运算包括： 置空表 SETNULL(L) 建表 CREATLIST(L) 求表长 LENGTH(L) 取结点 GET(L,i) 定位 LOCATE(L,x) 插入 INSERT(L,x,i) 删除 DELETE(L,i) 顺序存储的线性结构(顺序表) 顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。 顺序表：采用顺序存储方法存储的线性表称顺序表。 由 n 个数据元素 a1、 a2、 an 组成的有限序列，称为顺序表 存储地址的计算： 由于顺序表采用的是顺序存储方法，因此表中的任一结点的存储地址可按下式计算： L

9、OC(ai)=LOC(a1)+(i-1)*c 1=i=n 这里： LOC(a1) 为结点 a1 的存储起址， c 为每个结点所占存储单元数。 顺序表是一种随机存取结构 在 c 语言中，顺序表用一维数组描述： typedef int datetype; #define maxsize 1024; typedef struct datatype datamaxsize; int last; sequenlist; 顺序表上的基本运算(实现) SETNULL (L)： (*l).last = -1 LENGTH(L): (*l).last+1 GET(L,i): (*l).datai-1 1. LO

10、CATE(L,x) ,比较至 算法思想 : 将 x 和线性表中的每一个数据元素比较,若相等 ,返回比较结点的序号 表尾,没有等于 x 的节点,则返回 0. int LOCATE(sequenlist *l,datatype x) int i=0; while(i=(*l).last) if(x=(*l).datai) return(i+1); i +; return(0); 最好情况下 : T(n)=1 最坏情况下 : T(n)=n 2. 插入INSERT(L,x,i) 所做工作 : 判断是否可插入 ,从表空间上考虑 判断插入位置是否合法 结点后移 将x 插入第 i 个位置 终端结点下标加 1

11、 3. 删除 DELETE(L,i) 所作工作 : 判断删除位置是否合法 : (i(*L).last+1) 结点前移 for(j=i;jdata=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); if (r!=NULL) r-next=NULL; return head; 优点：链表中结点次序和输入次序相同 缺点：空表和非空表处理不同 开始结点和其余结点的处理不同 简化算法的 解决办法： 引入头结点， 统一空表和非空表、 开始结点和其余结点的处理， 实现 while (ch!= $) s=malloc(sizeof(link

12、list) ; s-data=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); 2.单循环链表的特点： 链表尾结点的 next 域不为空， 而是指向头结点或开始结点。 显然 对单循环链表，从任一结点开始，均可找到其前趋和后继结点。 ,而 引入单循环链表的目的在于方便一些运算的实现。实用中常采用尾指针单循环链表 不是头指针单循环链表。 采用单循环链表实现两个线性表 A 和 B 链成一个线性表的运算 p=ra-next; ra-next=rb-next-next; free（rb-next）; rb-next=p; 双链表的特点

13、：每个结点有两个指针域，分别指向其直接前趋和后继。 为了指示双链表，也须引入一个头指针head，指向其开始结点。 双链表存储结构描述如下： typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist *head; （1）删除运算 （2）插入运算 栈，队列 1 定义：栈（ Stack ）是仅在表的一端进行插入和删除运 算的线性表 栈顶 （top） 为进行插入和删除运算的一端 栈底 （bottom） 为另一端 2 特点 : 最先入栈的元素总是最后出栈，而最后入栈的元素则总是最先出栈，因此，

14、栈又被称为后进先出 （Last In First Out） 的线性表。 3 栈的基本运算包括： （1）置空栈 SETNULL （ S） （2）判栈空 EMPTY （S） :布尔函数 （ 3）入栈 PUSH（S， x） （ 4）出栈 POP（S） （ 5）取栈顶 TOP（ S） 顺序栈 c 语言中通过数组来实现。栈顶指针 top 为 1 定义：顺序栈是采用顺序存储结构的栈， 指示栈顶位置的变量，用数组元素的下标来表示。 2 顺序栈存储结构描述： typedef int datatype; #define maxsize 100; typedef struct datatype datamaxsi

15、ze; int top; seqstack; seqstack *s; 1) 置栈空 setnull(s) seqstack *s; s top=-1; 2) 判栈空 int empty(s) seqstack *s; if(s top=0) return FALSE; else return TRUE; 3) 进栈 seqstack *push(s,x) seqstack *s; datatype x; if(s top=maxsize-1) printf( “overflow ”);return NULL else s top+;s datas top=x; return s; 4) 退栈

16、 datatype pop(s) seqstack *s; if (empty(s) printf( “underflow ”);return NULL; else s top-; return(s datas top+1); 5) 取栈顶 datatype top(s) seqstack *s; if (empty(s) printf(“ staisc k empty ” ); return NULL; else return(s datas top); 为了充分利用向量存储空间， 多个栈共用一段存储空间。 缺点：使栈运算的实现更复杂。 那么这个合用的顺序栈的代码如何实现。 链栈 1 定义：

17、采用链式存储结构的栈称为链栈。链栈实际上是操作受限的单链表，其插入和 删除操作均在表头进行。 2 链栈的存储结构描述如下： typedef int datatype; typedef struct node datatype data; struct node *next; linkstack; linkstack *top; 1) 进栈 PUSHLSTACK(top,x) Linkstack *PUSHLSTACK(top,x) linkstack *top; datatype x; linkstack *p; p=malloc(sizeof(linkstack); p-data=x; p-

18、next=top; return p; 2) 退栈 PUSHLSTACK(top,x) Linkstack *POPLSTACK(top,datap) linkstack *top; datatype *datap; linkstack *p; ); return NULL; if(top=NULL) printf( “ underflow else *datap=top-data; p=top; top=top-next; free(p); return top; 队列 1 定义：队列 （queue） 是一端进行删除另一端进行插入的线性表。允许插入的一端称为 队尾 （rear） ，允许删除的

19、一端称为队头 （front） 。 2 特点： 先入队 （ 即插入队尾）的元素必将被先删除 （即出队）。因此，队列是一种先进 先出 （First In First Out） 的线性表。 3 队列的基本运算： 1）SETNULL （ Q）置队空 2）EMPTY （Q ）判队空 3）FRONT （Q）取队头元素 ,队中元素保持不变 4）ENQUEUE （Q,x） 将元素 x 入队 5）DEQUEUE （ Q）出队 ,函数返回原队头元素 顺序队列 1 定义：采用顺序存储结构的队列称为顺序队列， c 语言中通过数组来实现。 规定： front 总是指向当前队头元素的前一个位置 rear 指向当前队尾元素

20、的位置 2 顺序队列存储结构描述如下： typedef struct datatype datamaxsize; int front,rear; sequeue; sequeue *sq; 4 顺序队列基本运算 初始时， sq rear=sq front=-1, 在不考虑溢出的情况下，入队和出队的运算如下： ?入队： ?出队： sq rear+; sq datasq rear=x; sq front+; ?队空： sq rear=sq front ?队满： sq rear sq front=maxsize ?下溢： 队空时，若要进行出队操作时发生 ?上溢： 队满时，进行入队操作时出现。 ?“假

21、上溢 ”： 当 sq-rear=maxsize-1 但队列并不满 时进行入队操作 这种情况(即 sq-rear=maxsize-1)下若要进行入队运算 ,sq rear 的值将超出下标范围， 故不能进行这种运算，但此时整个队列空间并没用完。 解决“假上溢”的方法： 采用循环队列：即 sq-data0 接在 sq-datamaxsize-1 之后 循环队列 基本运算 1) 置队空 setnull (sq) sequeue *sq; sq front=sq rear=maxsize-1; 在循环向量中 maxsize-1 是位置 0 的前一个位置 2) 判队空 empty(sq) sequeue

22、*sq; return(TRUE); “ queue is empty. ” ); if (sq rear=sq front) else return(FALSE); 3) 取队头元素 datatype front (sq) sequeue *sq; if empty(sq) printf( return( 特定值 ); else return(sq data(sq front+1)%maxsize); 4) 入队 int enqueue (sq,x) sequeue *sq; datatype x; if (sq front=(sq rear+1)%maxsize) printf(“ que

23、ue is full.” );return (NULL); else sq rear=(sq rear+1) % maxsize; sq datasq rear=x;return (TRUE); 5) 出队 datatype dequeue(sq) sequeue *sq; if empty(sq) printf( “ queue is empty. ” ); return( 特定值 ); else sq front=(sq front+1) % maxsize; return(sq datasq front); 链队列 1 定义：采用链式存储结构的队列称为链队列 2 链队列存储结构描述 ty

24、pedef struct linklist *front,*rear; linkqueue; linkqueue *q; 为了运算实现的方便， 在队头结点前引入一个头结点。初始时 （即队空） 链队 的头、尾指针均指向头结点。 链队列上的几种 基本运算 1）建空队 CREATEMPTYQUEUE(q) linkqueue *q; q-front=malloc(sizeof(linklist); q-front-next=NULL; q-rear=q-front; 2) 判队空 Int EMPTY(q) linkqueue *q if(q-front= =q-rear) return(TRUE);

25、 else return(FALSE); 3) 取队头结点数据 datatype FRONT(q) linkqueue *q if(EMPTY(q) print( “ queue is empty re”tu)r;n NULL; else return(q-front-next-data); 4) 入队 ENQUEUE (q,x) linkqueue *q; datatype x; q-rear-next =malloc(sizeof(linklist); q-rear=q-rear-next; q-rear-data=x; q-rear-next=NULL; 5) 出队 队列长度大于 1 时

26、，只需修改头结点的指针域，尾指针不变。 S=q-front-next; q-front-next=s-next; free(s); 队列长度等于 1 时，不但修改头结点的指针域，还需尾指针。 解决方法： 出队时只修改头指针， 删除头结点， 使链队列上的队头结点成为新的链表的 头结点，队列上的第 2 个结点成为队头结点。即物理上删除头结点，逻辑上删除对头结点。 即使当前队列长度为 1，也不用修改尾指针。 Datatype DEQUEUE(q) linkqueue *q; if(EMPTY(q) print( “ queue is empty retu”rn) ;N ULL; else s=q-f

27、ront; q-front=q-front-next; free(s); return(q-front-data); 树的基本概念 1、树的定义：树 (Tree)是 n(n0) 个结点的有限集合 T， 它满足如下条件： (1) 有且仅有一个称为根 (Root) 的结点。 (2) 其余结点可分为 m(m=0) 个互不相交的有限集合 , T1,T2, ,Tm其, 中每个集合又是一棵树，并称其 为 根 的 子 树 ( Subtree ) 。 这 是 一 个 递 归 定 义 有时 n=0 也称为空树。 树的表示方法 2) 嵌套集合法 3) 广义表形式 ( A(B, C(E,F), D(G) ) 4）凹

28、入表示法 基本术语 1）结点的度 （Degree） ：为该结点的子树的个数。 2）树的度：为该树中结点的最大度数。 3）终端结点 （叶子 ）：度为零的结点。 4）非终端结点 （分支结点 ）：度不为零的结点。 5）内部结点：除根结点之外的分支结点。 6）孩子 （child） ：结点的子树之根 双亲（ parent）: 该结点称为孩子的双亲 兄弟 （sibling）: 同一双亲的孩子 堂兄弟（ cousin）: 双亲不同但其双亲处于同一层的结点 7）路径（Path）：若树中存在一个结点序列 k1,k2, ,kj,使得 ki是ki+1 的双亲（1=i=0) 棵互不相交的树的集合称为森林。 逻辑特征

29、树中任一个结点都可以有零个或多个后继结点， 但最多只能有一个前趋结点。 有序树中 兄弟结点之间从左至右有次序之分。 逻辑运算 1.setnull(T) : 置 T 为空树。 2. root(T) 或 root(x) :求树 T 或结点 x 所在树的根结点。 3. parent(T,x) : 求 T 中 x 结点的双亲，若 x 为根或 x 不在树中， 结果为空。 4. child(T,x,i) : 求 T 中 x 结点从左至右第 i 个孩子，若 x 为叶 子或 x 不在树中，结果为空。 叉树 二叉树的定义： 二叉树 (Binary Tree)是 n(n=0)个结点的有限集， 它或者是空集 (n=

30、0) 或者由一个根结点 和两棵互不相交的，分别称为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定义。 二叉树的五种基本形态 二叉树中子树是有左右之分的， 即使只有一棵子树，或为左子树， 或为右子树，这一点 与度为 2 的有序树不同。 二叉树的性质 性质 1：二叉树第 i 层上的结点数目最多为 2i-1 (i=1) 该性质可用数学归纳法证明。 性质 2：深度为 k 的二叉树至多有 2k-1 个结点 (k=1) 性质 3：任意二叉树中，若叶结点的个数为n0,度为 2 的结点数为 n2，则 n0=n2+1。 性质 4：具有 n 个结点的完全二叉树的深度为 log2

31、n +1( log2(n+1) ) 性质 5：如果对一棵有 n 个结点的完全二叉树的结点按层次编号(即自上而下，自左至 右) ，则对任一结点 i(1=i1, 则其 双 亲 是 编 号 为 i/2 的结点。 (2) 如果 2*in,则结点 i 无左孩子；否则其左孩子是编号为 2*i 的结点。 (3) 如果 2*i+1n, 则结点 i 无右孩子；否则其右孩子是编号为 2*i+1 的结点。 (4) 若 i为奇数且不为 1,则结点 i 的左兄弟的编号是 i-1;否则,结点 i 无左兄弟。 (5) 若 i为偶数且小于 n,则结点 i的右兄弟的编号是 i+1;否则,结 点i 无右兄弟。 二叉树的存储 顺序

32、存储结构 对于完全二叉树可以采用顺序存储结构 (即一维数组 )进行存储，编号为 i 的结点存放在 第 i 个数组元素所分配的存储单元中， 完全二叉树结点之间的逻辑关系通过数组元素的下标 体现。 对于非完全二叉树，通过补设一些“虚结点” ，使得二叉树的结点的编号与完全二叉树 相同，再进行顺序存储。每个“虚结点”都将占据一个数组元素存储单元。 结论：非完全二叉树采用顺序存储结构会造成存储空间的浪费。 链式存储结构 二叉树除了可以采用顺序存储结构实现存储外,还可以采用链式存储结构进行存储 ,与采 用顺序存储结构相比 ,采用链式存储结构实现二叉树的存储显得更自然. 结点的存储描述 typedef st

33、ruct node datatype data; struct node *lchild,*rchild; bitree; bitree *root; 所有类型为 node 的结点，再加上一个指向根结点的头指针root ，就构成了二叉树的存 储结构，称为二叉链表。 一个二叉链表由头指针唯一确定。若二叉树为空，则 root=NULL 。 在 n 个结点的二叉树中一共有 2n 个指针域， n+1 个为空， n-1 个非空。 二叉树的遍历 二叉树的遍历指的是沿某条搜索路径访问二叉树， 对二叉树中的每个结点访问一次且仅 一次。这里的“访问”实际上指的是对结点进行某种操作。 (以下 “访问”特指打印该结

34、点信息 ) 非空的二叉树可以分成三部份： 根结点， 左子树和右子树。因此， 对二叉树的遍历可以 分成三个子问题：访问根结点，遍历左子树，遍历右子树。若分别以D，L， R 表示上述三 个子问题，则对二叉树存在六种遍历次序： DLR ， LDR ，LRD ，DRL ，RDL ，RLD 。后三种 与前三种对称，因此仅需讨论前三种。 按照根结点在遍历过程中被访问的先后次序，DLR 、LDR 和 LRD 分别被称为前序、中 序和后序遍历。 前序遍历二叉树 . 遍历过程： 若二叉树非空， 则先访问根结点， 再前序遍历左子树， 最后前序遍历右子树。 ?算法描述： preorder (t ) bitree *

35、t; if (t) printf( “t%c ”,t data); preorder(t lchild); preorder(t rchild); 中序遍历二叉树 ? 算法描述： inorder (t) bitree *t; if (t) inorder(t lchild); printf( “t%c ” ,t-data); inorder(t rchild); 后序遍历二叉树 ? 算法描述： postorder (t ) bitree *t; lchild); rchild); t%c ” ,t-data); if (t) postorder(t postorder(t printf( 三个

36、算法具有相同的搜索路径 : 该路线从根结点出发 , 逆时针沿二叉树外缘移动 , 对每个结点均途径三次 . 若访 问结点均是在第一次经过结点时进行的 ,则是前序遍历 , 若访问结点均是在第二 次（或第三次）经过结点时进行的 ,则是中序遍历 （或后序遍历 ）. 考虑： 1、遍历的第一个结点和最后一个结点的特征 ? 2、前序序列、中序序列、后序序列，已知任意两者可以确定第三者吗 3、遍历算法中对每个结点进行一次访问操作，访问操作可以是多种形式及多个 操作。得到求解许多问题的算法。 4、二叉树的遍历只有这六种方法吗 ? 线索二叉树的基本概念 什么是线索二叉树？ 线索二叉树如何创建？ 线索二叉树建立以后

37、，有什么用？ 树和森林 树或森林与二叉树之间存在一一对应的关系。 任何一棵树或一个森林可唯一地对 应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。 树: 是 n(n=0)个结点的有限集合，且满足两个条件有且仅有一个特定 的称为根的结点； 其余结点又可分为 m(m=0)个互不相交的有限集合 T1,T2.Tm, 其中每个集合又都是一棵树，并称其为根的子树 森林：是 m(m=0)棵互不相交的树的集合。 二叉树：是 n(n=0) 个结点的有限集合。它或是空或者是由一个根结点及两棵互 不相交的分别称做根的左右子树的二叉树组成。 树和森林间的转换关系： 删去树的根就得到一个森林。 将

38、森林中所有的树加上一个共同的根就得到一棵树 树(或森林中的树 ) 中的每个结点最多只有一个最左边的孩子和一个右邻的兄 弟。这是将树 ( 或森林 )转换成二叉树所用到的关系。 将树转换成二叉树的步骤为： (1) 将所有兄弟结点用边连接起来。 (2) 对每个结点，除了保留与其长子的边外，去掉该结点与其它孩子的边。 森林转换成二叉树的步骤： (1) 将森林中的每棵树转换成二叉树。 (2) 将每个二叉树的根结点看成兄弟用边连起来。 注意：树 (或森林) 转换得到的二叉树，结点之间的关系与一般二叉树中结点之 间的关系不同。 树的储存 双亲链表表示法 每个结点最多只有一个双亲， 因此对每个结点引入一个指针

39、， 使其指向该结点的 双亲。 孩子链表表示法 不可采用多重链表。 较好的方法是：用一个结构数组储存树中的每个结点及指向该结点所属孩子的单 链表的指针， 另对每个结点的孩子结点用一个单链表， 储存各结点在结构数组中 的序号，该方法已知某结点找父结点困难。 孩子兄弟链表表示法 在存储结点信息的同时 , 附加两个分别指向该结点最左孩子和右邻兄弟的指针 域。该方法实际上是用二叉链表实现树的储存。 哈夫曼树及其应用 树的路径长度：从树根到树中每一结点的路径长度之和。 结点数相同的二叉树中， 完全二叉树的路径长度最短。 对树中的结点赋予一个有某种意义的值 (实数 ), 该值称为结点的权。 结点的带权路径长

40、度：结点到树根之间的路径长度与结点的权值之积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 最优二叉树(哈夫曼树) ：在权为 w1,w2,wn 的 n个叶结点的所有二叉树中， WPL最小的二叉树称为最优二叉树或哈夫曼树。 给定 4 个叶结点 a,b,c,d,分别带权 7,5,2,4,我们来构造 3 棵二叉树 哈夫曼算法思想 (1) 根据给定的 n 个权值 w1,w2, ,wn 构造 n 棵二叉树的森林 F=T1,T2, ,Tn ，其中每棵二叉树 Ti 中仅有一个权值为 Wi 的根结点，其左 右子树为空。 (2) 在 F 中任选出两棵根结点权值最小的二叉树作为左右子树构造一棵新二 叉

41、树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。 (3) 在 F 中删除这两棵二叉树并将新得到的二叉树加入到 F 中。 (4) 重复(2) 和(3) , 直到 F只含一棵二叉树为止，这棵二叉树便是哈夫曼树。 哈夫曼编码 1)等长编码： 每个字符均用长度相等的二进制位串表示。如 ASCII 码。 2)非等长编码： 每个字符不是采用等长的二进制串表示，而是根据字符使用的 频度，对使用频度高的字符采用较短的二进制串表示， 对使用频度低的字符采用 较长的二进制串表示，从而达到缩短报文总长的目的。 不等长编码带来的问题：在不等长编码情况下，例 00 表示 E，01 表示 T， 0001 表

42、示 W，收到的编码是 0001，那么这组编码是 W还是 ET呢？ 无法区分，原因是 E 的编码和 W的编码开始部分(前缀)相同。 若对字符集进行不等长编码， 则要求这种不等长编码必须是前缀码， 即任一字符 的编码不能是其它字符编码的前缀。 图 图 G 由两个集合 V 和 E 组成，记为 G=(V,E), 其中 V 为顶点的有穷非空集合， E 为 V 中 顶点偶对(即边)的集合。图G的顶点集和边集分别记为 V(G)和 E(G)。E(G)可以是空集， 若 E(G) 为空，则图 G 只有顶点而没有边。 有向图 :图 G 中的每一条边都是有方向的。 V(G)=v0,v1,v2,v3,v4 E(G)=,

43、 无向图 : 图中的每一条边都是无方向的。 V(G)=v0,v1,v2,v3,v4 E(G)= (v0,v1),(v0,v2),(v0,v3),(v1,v2),(v1,v4),(v3,v4) 简单图：一条边不重复出现在图中且不存在顶点到其自身的边。 数据结构只研究简单图。 其顶点数 n 和边数 e 满足下列关系 : 若 G 为无向图0 e n(n-1) /2 无向完全图 若 G 为有向图0 e n(n-1 ) 有向完全图 若 (vi,vj) 是一条无向边，则称顶点 vi 和 vj 互为邻结点 (Adjacent) ， (vi,vj) 与顶点 vi 和 vj 相关联 (Incident) 。若

44、是一条有向边， 则称顶点 vi 邻接到 vj, 顶点 vj 邻 接于 vi, 与顶点 vi 和 vj 相关联。 度、入度和出度的概念： 无向图中顶点 v的度为关联于该顶点的边的数目，记为 D(v) 有向图中把以顶点 v 为 终点的边的数目称为 v 的入度，记为 ID(v) 把以顶点 v 为始点的边的数目称为 v 的出度 ,记为 OD(v) 顶点的度定义为入度与出度之和，即 D(v)=ID(v)+OD(v) 。 子图的概念 :设G=(V,E)是一个图，若 V是 V 的子集， E是 E的子集且 E中的边所关联 的顶点均在 V中，则 G=(V,E) 也是一个图，并称其为 G 的子图。 路径：若存在一

45、个顶点序列 vp , vi1 , vi2 , 无向图 G 中，使得 (vp , vi1) , (vi1 , vi2) , 到 vq 存在一条路径。 有向图 G 中，若 , , 到 vq 存在一条路径。 , vin , vq: , (vi均n ,属 v于q) E(G) ，则称顶点 vp . , 于 E(G) , 则从顶点 vp 路径长度：路径长度为该路径上边的数目。 简单路径： 除起点和终点外， 其余顶点均不相同的路径称为简单路径。 起点和终点相同 的简单路径称为简单回路。 有向图的根 有向图中，若存在一个顶点 v，从该顶点到图中其它各顶点都存在路径，则称该有向图 为有根图， v 称为图的根。

46、无向图 G 中，若任意两个顶点间存在路径 (即连通的 ),则称 G 为连通图 . 无向图 G 的极大连通子图称为 G 的连通分量 . 有向图 G 中，任意两个不同的顶点 vi 和 vj ，都存在从 vi 到 vj 以及 vj 到 vi 的 路径，则称 G 为 强连通图。 有向图 G 的极大强连通子图称为 G 的 强连通分量。 强连通图只有一个强连通分量 非强连通图有多个强连通分量 若将图中的每一条边赋上一个权值，则称该图为带权图。带权图又称为网络。 图的存储 图的存储涉及到两方面：顶点内容的存储和边(逻辑关系 )的存储。图的存储所采用的两 种常用方法为：邻接矩阵和邻接表。 邻接矩阵和邻接表的比

47、较 1、一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。因为邻接表表示中，各 边表结点的链接次序取决于建立邻接表的算法及边的输入次序。 2、 中结点个数等于一行（或一列）中非零元素个数 3、n 个顶点 e 条边的图 建立 无向图： 邻接矩阵 O（n2） 有向图： O（n2） 4、 求顶点 vi 的度： 邻接矩阵 无向图：第 i 行（列）上非零元素个数 有向图：出度：第 i 行上非零元素个数 入度：第 i 列上非零元素个数 在邻接表（或逆邻接表）表示中，每个边表对应于邻接矩阵 行（或一列）,边表 邻接表 O（n+2e） O（n+e） 邻接表 第 i 个边表中结点数 第 i 个边表上的结点数

48、需遍历整个表 5、 判断（ Vi ，Vj ）或 Vi ， Vj 是否是图的一条边 邻接矩阵：判矩阵中第 i 行 第 j 列的那个元素是否为零 邻接表中：扫描第 i 个边表 O（n） 6、 求边数 邻接矩阵：检测整个矩阵O（ n2） 邻接表： 计算边表结点个数之和 O（ e+n） 对 n 个顶点的图，若 e 接近于 n*（n-1）（ 有向图 ） 或 e 接近于 n*（n-1）/2（ 无向图 ）则称该图为 稠密图 对 n 个顶点的图，若 en*（n-1）（ 有向图 ） 或 en*（n-1）/2（ 无向图 ）则称该图为稀疏图 图的遍历： 深度优先搜索遍历 .DFS 基本思想 从图 G中任一顶点 vi

49、 出发，先访问顶点 vi，并将其访问标 志置为 true，然后依次从 vi 出发搜索 vi 的没有被访问过的邻接顶点 , 以该顶点为新的出发 点，继续进行深度优先搜索。重复上述过程，直到所有顶点都被访问为止。 上述遍历的思想是一种递归的思想 , 在算法的具体实现过程中，可采用递归程序方法。 对图进行深度优先搜索得到的顶点序列称为深度优先搜索序列，简称为 DFS 序列 DFS 序列不唯一 ,它与遍历算法，图的存储结构以及初始出发点有关。 广度优先搜索遍历 BFS 基本思想 从图 G 中任一顶点 vi 开始，首先访问顶点 vi ，接着依次访问 vi 的所有邻接点 w0,w1, ,wt，然后再依次访

50、问 w0,w1, ,wt 邻接的所有未被访问过的顶点，依次类推， 直到图中所有和 vi 有路径相通的顶点都被访问过为止。 对图进行广度优先搜索得到的顶点序列称为广度优先搜索序列，简称为 BFS 序列。 BFS 序列 不唯一,与算法、图的存储结构以及初始出发点有关 定义：具有 n个顶点的无向连通图 G，其生成树为包含有 n个顶点和 n-1 条边的无向连 通子图，或生成树是连通图 G 的一个极小连通子图。 特点： a.无向连通图的生成树通常是不唯一的 b.生成树满足连通性且边数最小 生成树：连通图 G 的一个极小连通子图，如果是含有 G 的所有的顶点的树，则称该子 图为生成树 特点： 1.无向连通

51、图的生成树通常是不唯一的 2. 生成树满足连通性且边数最小 求无向连通图的生成树： 方法是：对图进行 dfs 或 bfs 遍历，在遍历的过程中，每当从被访问过的顶点 vi 搜索到 未被访问的相邻的顶点 vj 并对其进行访问时，将边 （vi,vj） 记录下来。除初始顶点外，对其余 n-1 个顶点的访问一共要经过 G 中的 n-1 条边。因此，记录下来的边的数目为n-1，这 n-1 条边将 G 中的 n个顶点连接成 G 的极小连通子图，从而构成了图的一棵生成树。 说明： （1）此定义不仅适用于无向图也适用于有向图 （ 2）若 G 是强连通图，则其生成树为包含强连通图所有顶点的有根子图。强连通图的

52、生成树通常也是不唯一的，遍历的出发顶点不一样，生成树的根也不一样。 （3）若 G 是有根 （设根为 v）的有向图，其生成树是以 v为根的生成树。 （ 4）对于非连通的有向图（有根图除外） ，只能得到其生成森林 按深度优先搜索得到的生成树称为深度优先生成树 按广度优先搜索得到的生成树称为广度优先生成树 求最小生成树的方法： prim 与 kruskal 算法。 求最短路径的方法： 单源最短路径问题： dijkstra 算法。 查找 （1）查找的过程是怎样的？ 给定一个值 K ，在含有 n 个记录的文件中进行搜索，寻找一个关键字值等于 K 的 记录，如找到则输出该记录，否则输出查找不成功的信息。

53、（ 2）对查找表常用的操作有哪些？ 查询某个 “特定的 ”数据元素是否在表中； 查询某个 “特定的 ”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 （ 3） 有哪些查找方法？ 查找方法取决于表中数据的排列方式 ; 针对静态查找表和动态查找表的查找方法也有所不同。 （ 4）如何评估查找方法的优劣？ 明确：查找的过程就是将给定的 K 值与文件中各记录的关键字项进行比较的过程。所 以用比较次数的平均值来评估算法的优劣。 称为平均查找长度 （ ASL ：average search length）。 顺序查找（ Linear search，又称线性查找 ） 顺序查找：即用逐一比较的办法顺序查找关