好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

《数据结构》考前冲刺大纲讲义总结(考研资料).pdf

48页
  • 卖家[上传人]:汽***
  • 文档编号:575332031
  • 上传时间:2024-08-18
  • 文档格式:PDF
  • 文档大小:8.35MB
  • / 48 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 《 数据结构》考前冲刺大纲讲义总结绪论1 . 1 数据结构的基本概念1 . 1 . 1 基本概念和术语1 . 数据2 . 数据元素: 可由若干数据项组成, 数据项是不可分割的最小单位3 . 数据对象: 具有相同性质的数据元素的集合4 . 数据类型: 是一个值的集合和定义在此集合上一组操作的总称5 . 抽象数据类型( ADT ) : 包括数据对象、数据关系和基本操作集6 . 数据结构: 逻辑结构、存储结构和数据的运算1 . 1 . 2 数据结构的三要素1 . 逻辑结构: 分为线性和非线性结构2 . 存储结构( 物理结构) : 包括顺序、链式、索引和散列存储3 . 数据的运算: 运算的定义和实现1 . 2 算法和算法评价1 . 2 . 1算法的基本概念1 . 五个重要特性: 有穷、确定、可行、输入和输出2 . 好的算法目标: 正确性、可读性、健壮性、高效率与低存储量1 . 2 . 2 算法效率的度量1 . 时间复杂度: T ( 〃 ) = O ( / ( 〃 ) ) , 通常指最坏情况下时间复杂度2 . 空间复杂度: 原地工作指算法所需的辅助空间是常量第 2章线性表2 . 1线性表的定义及基本操作2 . 1 . 1线性表的定义1 . 线性表是具有n 个相同类型数据元素的有限序列, n 为表长, n = 0是空表2 . 1 . 2线性表的基本操作1 . I n i t L i s t ( & L )2 . L e n g t h ( L )3 . L o c a t e El e m ( L , e )i-1 - 4 . G e t El e m ( L , i )5 . L i s t i n s e r t ( & L , i , e )6 . L i s t De l e t e ( & L , i , & e )7 . Em p t y ( L )8 . De s t r o y L i s t ( & L )2 . 2线性表的顺序表示2 . 2 . 1顺序表的定义1 .元素逻辑位置与物理位置相同, 线性表的顺序从1开始2 .线性表的顺序存储类型( 1 ) 一位数组静态分配id efin e MaxSize 50typedef s tru c t{ElemType data[M axSize];in t length;}SqList;( 2 )动态分配#define In itS iz e 100typedef s tr u c t(ElemType *data;in t M axSize,length;} S eqL ist;〃定义线性表的最大长度〃顺序表的元素〃顺序表的当前长度〃顺序表的类型定义〃表长度的初始定义« 指示动态 分 曝 组 的 殿/ / 毅组蔚晟大容凝居 前个数〃动态分配数组顺序表的类型定义C 的初始动态分配语句 L . d a t a = ( El e m T y p e * ) m a l l o c ( s i z e o f ( El e m T y p e )* I n i t S i z e ) ;3. 顺序表特点: 随机访问, 存储密度高, 插入和删除需要移动大量元素2 . 2 . 2顺序表上基本操作的实现( 1 )插入: 在第i个位置插入e ( 1 < / < Llength + 1 ) , i不合法则返回f a l s e ;否则, 将第i个元素及其后所有元素右移一个位置; 插入e ,表长加1 ,返回t r u e ( 从后往前依次后移一个)b o o l L i s t i n s e r t ( S q L i s t & LZ i n t i , El e m T y p e e ) {/ / 本算法实现将元素e插入到顺序表L中第i f < i < l | | i > L . l e n g t h + l )r e t u r n f a l s e ;i f ( L . l e n g t h > = M a x S i z e )r e t u r n f a l s e ;f o r ( i n t j = L . length;j- - )L . d a t a [ j ] = L , d a t a , L i ,- 1 ] , < „L . d a t a f i - 1 1 » e ;L . l e n g t h + + ;r e t u r n t r u e ;}个位置/ / 判 断i的范围是否有效〃当前存储空间已满,不能插入〃 将 第i个元惠及之后的元素后移〃 在位置i会放入e/ / 线性表长度加1平均移动n / 2个元素, 则时间复杂度为0( n )2- 2 - ( 2 ) 删除: 删除第i 个元素, 成功返回t r u e , 并将元素用e 返回, 否则返回f a l s e ( 从前往后依次前移一个)bool ListDelete(SqList &L,int i,int &e){〃本算法实现删除顺序表L 中第i 个位置的元素if (iL. length) 〃判断i 的范围是否有效return false;e-L.data[i-l]; 〃将被删除的元素赋值给efor (int j=»i; jK 5 — n i B - rVTA—图 2 - 5 头插法建立单链表3- 3 - L i n k L i s t C r e a t L i s t l ( L i n k L i s t &L ) (/ / 从表尾到表头逆向建立单链表L ,每次均在头结点之后插入元素L N o d e * s ; i n t x ;L - ( L i n k L i s t ) m a l l o c ( s i z e o f ( L N o d e ) ) ;L - > n e x t - N U L L ;s c a n f (/z%d/z, &x ) ;w h i l e ( x ! - 9 9 9 9 1 (s = ( L N o d e * } m a l l o c ( s i z e o f ( L N o d e ) ) ;s - > d a t a - x ;s - > n e x t = L - > n e x t ;L - > n e x t - s ;scanf& x);)r e t u r n L ;〃创建头结点〃初始为空链表〃输入结点的值〃 输 入9 9 9 9表示结束〃创建新结点〃将新结点插入表中,L为头指针//W h i l e 结束时间复杂度0(n)2 . 采用尾插法建立单链表: 需增加一个尾指针, 使其始终指向尾结点每次将s所指结点描在末端1图2-6尾插法建立单链表LinkList CreatList2(LinkList &L) {//从表头到表尾正向建立单链表L,每次均在表尾插入元素int x; //设元素类型为整型L=(LinkList)malloc(sizeof(LNode));LNode *s,*r=L; 〃r 为表尾指针scanf (Z/%d^z &x) ; //输入结点的值while (x!=9999) { 〃输入 9999 表示结束s=(LNode *)malloc(sizecf(LNode));s->data=x;r->next=s;r»s; /〃 指向新的表尾结点scanf("%d",&x);)r->next=NULL; 〃尾结点指针置空return L;)3 . 按序号查找结点值: 从第一个结点出发, 顺 next往下查找, 0(n)L N o d e * G e t E l e m ( L i n k L i s t L , i n t i ) (〃本算法取出单链表,( 带头结点) 中第i个位置的结点指针i n t j - 1 ;L N o d e * p - L - > n e x t ;i f ( i - 0 )r e t u r n L ;i f ( i < Dr e t u r n N U L L ;w h i l e ( p 4 &j < i ) (p »p - > n e x t ;*+;)r e t u r n p ;〃计数 , 初 始 为1/ / 头结点指价赋给P〃 若i等于0 ,则返回头结点〃 若i无效,则返回N U L L/ / 从第1个结点开始找,查找第i个结点〃返回第i个结点的指针,如果i大于表长,P - N U L L ,直接返回P即可4 . 按值查找元素:0(n)〃本算法查找单链表L( 带头结点)中数据域值等于e的结点指针,否则返回N U L L〃 从 第1个结点开始查找d a t a域为e的结点〃找到后返回该结点指针, 否则返回N U L LL N o d e * L o c a t e E l e m ( L i n k L i s t L,E l e m T y p e e ) (L N o d e * p = L - > n e x t ;w h i l e ( p ! « N U L L s &p - > d a t a I - e )p - p - > n e x t ;r e t u r n p ;5 . 插入结点: 插入到第i 个位置, 先检查插入位置合法性, 然后找到第i-1 个4- 4 - 结点, 在其后插入p = G e t E l e m ( L . i - l ) ;s - > n e x t = p - > n e x t ;p - > n e x t = s ;( 1 ) 时间复杂度为0 ( n ) , 若在给定序号后插入时间复杂度为0 ( 1 )( 2 ) 扩展: 对某一结点进行前插操作: 仍将* s 插入到* p 后面, 然后将p - > d a t a与 s - > d a t a 换位置6 . 删除结点操作: 先检查位置合法性, 找到i - l 个位置, 即被删除结点的前驱结点位置p = G e t E l e m ( L , i - l ) ;q = p - > n e x t ;p - > n e x t = q - > n e x t ;f r e e ( q ) ;2 . 3. 3 双链表两个指针p r i o r ( 指针前驱) 和n e x t ( 指向后继)t y p e d e f s t r u c t D N o d e {E l e m T y p e d a t a ;s t r u c t D N o d e * p r i o r , * n e x t ;} D N o d e * D L i n k L i s t ;L双链表的插入p斗 I : I - - - - - - - - - *③ ! - - -| x | 评 - - - - - !①图2 - 1 0双链表描入结点过程① s - > n e x t = p - > n e x t ; 〃将结点*s插入到结点*p之后② p - > n e x t - > p r i o r5= s ;③ s - > p r i o r = p ;④ p - > n e x t = s ;2 . 双链表的删除5- 5 - 图2 - 1 1双链表删除结点过程p->next=q->next; //图 2-10 中步骤①q->next->prior=p; //图 2-10 中步骤②free(q); //释放结点空间2. 3. 4循环链表1 .循环单链表: 表中最后一个元素不是指向NULL,而是指向头结点; 判断是否为空是头结点是否等于头指针; 若操作经常在表头和表尾进行, 可设置尾指针,这样效率为0(1)2 .循环双链表: 空表时头结点的p rio r和n ex t都是L3 .静态链表: 指针是数组下标8 1 2 -1 4静态链表存储示意图第3章 栈和队列3. 1栈3 .1 .1 栈的基本概念1 .栈的定义: 只允许在一端进行插入和删除操作的线性表. 栈顶( 允许插入和删除的一端) 、栈底、空栈, 后进先出2 .栈的基本操作(1) InitStack(&S)(2) StackEmpty(S)(3) Push(&S, x)(4) Pop (&S, &x)(5) GetTop(S, &.x)(6) ClearStack(&S)3. 1 .2栈的顺序存储结构6- 6 - 1 . 顺序栈的实现: 用一维数组存放自栈底到栈顶的数据元素, 同时附设一个指针( t o p) 指示当前栈顶位置#define MaxSize 50typedef struct{Elemtype data(MaxSizeJ;int top;} SqStack;〃定义栈中元素的最大个数〃存放栈中元素〃栈顶指针( 1 ) 栈顶指针s . t o p初始为T , 栈顶元素S. d at a[ S. t o p]⑵进栈: 栈不满, 栈顶指针先加1 , 再送值到栈顶元素( 3 ) 出栈: 栈非空, 先取栈顶元素值, 再讲栈顶指针减1( 4 ) 栈空: S. t o p= = - l, 栈满 S. t o p= = M ax Siz e - l, 栈长 S. t o p+ 1(a)空枝 (b)l个元素 (c)5个元素top -2 . 顺序栈的基本运算(d)2个元素( 1 ) 初始化void InitStack(&S){s.top=-l;}( 2 ) 判栈空bool StackEmpty(S){if(s.top==-l)return true;elsereturn false;}〃初始化栈顶指针〃 栈空//不空( 3 ) 进栈bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-l)return false;S.data[++S.top]=x;return true;)〃栈满,报错〃指针先加1, 再入栈( 4 ) 出栈bool Pop(SqStack iS,ElemTypeif(S.top==-l)return false;x=S.data[S.top- ];return true;&X) {//栈空,报错〃先出栈,指针再减1( 5 ) 读栈顶元素7- 7 - bool GetTop(SqStack S,ElemTypeif (S. t o p - 1)return false;x=S,data[S.top];return true;)3 . 共享栈: 栈满t o pl- t o p= l&x) {/ / 栈空,报错//X记录栈顶元素3 . 1 . 3 栈的链式存储结构所有操作都是在单链表表头进行, 第一个插入的结点在尾结点, 之后依次往前插入, 生成表头注: n 个不同的元素入栈, 有 占 0 个出栈序列3 . 2 队列3 . 2 . 1队列的定义1 . 队列的定义: 只允许在表的一端插入在另一端删除, 入队和出队, 先进先出2 . 队列常见的基本操作( 1 ) I nit Q u e u e ( & Q )( 2 ) Q u e u e Empt y( Q )( 3 ) EnQ u e u e ( & Q , x )( 4 ) De Q u e u e ( & Q , & x )( 5 ) G e t H e ad ( Q , & x )3 . 2 . 2 队列的顺序存储结构L队列的顺序存储: 附设两个指针fr o nt 和 r e ar 分别指示队头元素和队尾元素的下一个位置♦define MaxSize 50 〃定义队列中元素的最大个数typedef struct(ElemType data [MaxSize]; 〃存放队列元素int front, rear; 〃队头指针和队尾指针} SqQueue;初始状态( 队空) : Q . fr o nt = = Q . r e ar = = 0进队操作( 队不满) : 先送值到队尾, 再将队尾指针加1出队操作( 队不空) : 先取队头值, 再讲队头指针加18- 8 - 2 . 循环队列( 1 ) 初始时: Q . fr o nt = Q . r e ar = O( 2 ) 队首指针进 1 : Q . fr o nt = ( Q . fr o nt + l) % M ax Siz e( 3 ) 队尾指针进 1 : Q . r e ar = ( Q . r e ar + l) % M ax Siz e( 4 ) 队列长度: ( Q . r e ar + M ax Siz e - Q . fr o nt ) % M ax Siz e队空条件: Q . fr o nt = = Q . r e arQ.front Q.front(dl) d« c、f、g入队 (0 ) d、e、f入队为了区分队满还是队空: 牺牲一个单元, 队头指针在队尾指针的下一个位置作为队满标志; 队满条件为( Q . r e ar + l) % M ax Siz e = = Q . fr o nt3 . 循环队列的操作( 1 ) 初始化void InitQueue(aQ){Q.rear«Q.front=0; //初始化队首、队尾指针)( 2 ) 判断空bool isEmpty(Q){if (Q.rear==Q. front) return true; //队空条件else return false;}:( 3 ) 入队bool EnQueue(SqQueue &QZElemType:x){if ((Q.rear+1) %MaxSize==Q. front) return false; 〃队满Q.data[Q,rear]=x;Q. rear=- (Q. rear+1) %MaxSize; 〃队尾指针加 1 取模return true;|( 4 ) 出队bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear==Q.front) return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;}3 . 2 . 3 队列的链式存储结构//队空,报错〃队头指针加1 取模1 . 队列的链式存储: 是一个同时带有队头指针和队尾指针的单链表, 头指针9- 9 - 指向队头结点, 尾指针指向队尾结点t ype d e f s t r u c t {ElemType data;s tru c t LinkNode *next;JLinkNode;typedef s tr u c t{LinkNode * fro n tz * re a r;.}LinkQueue;//链式队列结点〃链式队列//队列的队头和队尾指针当Q . fr o nt = = Q . r e ar = = N UL L时 链 队 列 为空, 通常将链队列设id - -个 头结点2. 链队列的基本操作( 1 )初始化void InitQueue(LinkQueue &Q){Q. front«Q.rear= (LinkNode*)malloc (sizeof (LinkNode) ) ”/建立头结点Q . f ront->next=NULL; 〃初始为空)( 2 )判断空void EnQueue (LinkQueue &Q/EleniType x) {s=(LinkNode *)m alloc(sizeof(LinkN ode));s->data=x; s->next==NULL; //创建新结点,插入到链尾Q.rear-> next= s;Q .rear=s;}⑶ 入 队bool IsEmpty(LinkQueue Q){if(Q.front==Q.rear) return true;else return false;( 4 )出队bool DeQueue(LinkQueue &Q,ElemType &x){if (Q. front==Q.rear) return false; //空队p-Q.front->next;x=p->data;Q .front->next=p->next;if(Q.rear==p)Q.rear=Q. front; //若原队列中只有一个结点,删除后变空free(p);3 . 2 . 4双端队列两 端 均 允 许 进 队 和 出 队 的 队 列 : 重 点 是 受 限 制 的 双 端 队 列 , 即进队只有一端出队有两端或相反3 . 3栈和队列的应用3 . 3 . 1栈在括号匹配中的应用10- 10 - 3 . 3 . 2栈在表达式求值中的应用: 中缀表达式与后缀表达式相互转换1 .中缀表达式A + B x ( C- D) - E/F转化为后缀表达式为A B CD- x + EF /-2 .操作: 如果该项是操作数, 则将其压入栈中; 如果该项是操作符, 则连续从栈中弹出操作数Y和X,做Y< o p> X操作, 并将其重新压入栈3 . 3 . 3栈在递归中的应用: 效率并不高3 . 3 . 4队列在层次遍历中的应用表3 - 2层次遍历二又树的过程序说明队内队外1A 入A2A tb,B C入BCA3B 出,D 入CDAB4C 出 . E F入DEFABC5DIB. G 入EFGABCD6E 出,H I入FGHIABCDE7F 出GHIABCDEF8GHI出ABCDEFGH13 . 3 . 5队列在计算机系统中的应用: 缓冲区队列3 . 4特殊矩阵的压缩存储3 . 4 . 1数组的定义3 . 4 . 2数组的存储结构对于多维数组, 可以分为按行优先存储和按列优先存储, 但都是按顺序存放在一个连续的空间中3 . 4 . 3矩阵的压缩存储压缩存储: 为多个值相同的元素只分配一个存储空间, 对0不分配存储空间特殊矩阵: 具有许多相同元素或0元素, 分布有一定规律的矩阵( 对称矩阵、上下三角矩阵、对角矩阵)1 .对称矩阵:n阶方阵中, 按主对角线对称, 只存放主对角线和下三角元素( 或上三角元素, 又或按行或者按列存储)( 共n ( n + l )/ 2 )2 .三角矩阵: 上或下三角矩阵, 其另外一角都为同一常数, 存储完对角线和下三角元素后, 紧接着存储上三角元素一次( 共n ( n + l )/ 2 + l )3 .三对角矩阵: 所有元素集中在三条主对角线上, 其余均为0 ; ( i , j )元素在数组中的下标为k = 2 i + j - 3 ,反之, 若元素在数组中第k个位置, 则/ = 1 (左 + l ) / 3 + l _ J / = Z : — 2 i + 3 i 取下限3 . 4 . 4稀疏矩阵11-11 - 元素的个数远大于非0 元素的个数, 此时需要一个三元数组, 同时存放非0元素的行、列和值第 4 章 树与二叉树4. 1 树的基本概念4 .1 .1 树的定义: 只有一个根结点, 其他结点称为根结点的子树1 . 树的根结点没有前驱结点, 除根结点外所有结点只有一个前驱结点, 所有结点可以有0 或多个后继结点; n 个结点的树有n T 个边4. 1. 2 基本术语( 1)根往下走过的路径直到尾结点K,前面所有结点都是K的祖先结点, K是前面所有结点的子孙结点, 路径上最接近K的结点叫K的双亲结点, K是其孩子结点, 有相同双亲结点的叫兄弟结点( 2)树中一个结点的子结点( 直接孩子结点) 个数叫称为该结点的度, 树中结点最大的度叫树的度( 3)度大于0 的叫分支结点, 又叫非终端结点, 度为0 的叫叶子结点( 终端结点)( 4)结点的层次, 深度是从根结点开始自顶向下逐渐累加; 高度是从叶子结点自底向上累加; 树的高度( 深度) 是树中结点最大的层数( 5)路径和路径长度: 路径长度是所经过边的个数( 6)森林: 是m>=0棵互不相交树的集合4. 1 .3 树的性质( 1)树中结点数等于所有结点度数加1( 2)度为m的树中第i 层上至多有加 一 个结点( 3)高度为h 的m叉树至多有( 川_i) /( ,"-1) 个结点( 4)具有n 个结点的m叉树最小高度为「 log,”( 〃⑺- 1) + 1) ]注意: 设树中度为i 的结点个数为M ( 1) 总结点数:N = N0 + N\ + N2 + ...+ Nm ⑵总分支数: V = 1XN1 + 2XN2 + .. +加xNm ( 3)N = M + i4. 2 二叉树的概念4. 2. 1 二叉树的定义及主要特性12- 12 - 1 . 二叉树的定义: 不存在度大于2的结点, 左右顺序不能颠倒( 1 )二叉树与度为2的树的区别: 度为2的树至少有3个结点, 而二叉树可以为空; 二叉树有左右子树之分, 不能颠倒2 . 几个特殊的二叉树( 1 )满二叉树: 所有层都含最多个结点; 对于满二叉树, 对于编号为i 的结点, 若有双亲, 则 其 双 亲 为 若 有 左 孩 子 为 万 , 右孩子为2 1 + 1( 2 )完全二叉树: 每个结点的编号都与满二叉树一一对应; ①若三] 〃 / 2 」 则结点i 为分支结点, 否则为叶子结点②叶子结点只可能在层次最大的两层上出现③如果有度为1 的结点, 则只能有1 个, 且该结点只有左孩子没有右孩子④按层序编号后, 一旦出现某结点( 编号为i ) 为叶子结点或只有左孩子, 则编号大于i的结点均为叶子结点⑤若n 为奇数, 则每个结点都有左孩子和右孩子; 若为偶数,则编号最大的只有左孩子, 无右孩子( 3)二叉排序树: 左子树上所有结点关键字小于根结点, 右子树上所有关键字大于根结点, 左子树和右子树又是一个二叉排序树( 4 )平衡二叉树: 树上任意结点的左子树和右子树深度之差不超过13 . 二叉树的性质( 1 )非空二叉树叶子结点数等于度为2的结点数+ 1 , 即NO N2 + 1( 2 )非空二叉树第k 层上至多有2 一结点( 3)高度为H的二叉树至多有2 " - 1 个结点( 4 )当 i > l时, 结点i 的双亲编号为上/2 」 , 即当n 为偶数, 双亲编号为i /2 , 它是双亲的左孩子; i 为奇数, 双亲编号为( i T ) /2 , 它是双亲结点的右孩子( 5 ) 2 i < = N, 结点的左孩子编号为2 i , 否则无左孩子( 6 ) 2 i + l< = N, 结点i 的右孩子编号为2 i + l, 否则无右孩子⑺ 结点i 所在层次为] log2 , 」 + l13- 13 - ( 8 )具有N个结点的完全二叉树高度为|_log2N」 +l4. 2. 2二叉树的存储结构1 . 顺序存储结构: 按编号顺序存放, 完全二叉树和满二叉树比较合适; 要从数组下标为1开始存储2 .链式存储结构I ch i ldd a t ar ch i ld( 1 )二叉树链式存储结构表示typedef struct BiTNode{ElemType data; 〃数据域struct BiTNode *lchild, *rchild; I 〃左、右孩子指针)BiTNode,*BiTree;在含有n个结点的二叉链表中含有n+1个空链域4 . 3二叉树的遍历与线索二叉树4. 3. 1二叉树的遍历1 .先序遍历(NLR根左右)void PreOrder(BiTree T) {if(T!=NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}} . . . . .2 .中序遍历(LNR左根右)〃访问根结点〃递归遍历左子树〃递归遍历右子树void InOrder(BiTree T){if(T!=NULL){InOrder (T->lchild); 〃递归遍历左子树visit (T); 〃访问根结点InOrder (T->rchild); 〃递归遍历右子树)3 . 后序遍历(LRN左右根)void PostOrder(BiTree:T){if(T!=NULL){PostOrder (T->lchild); 〃递归遍历左子树PostOrder (T->rchild); 〃递归遍历右子树visit (T) ; //访问根结点:}}时间与空间复杂度都是0(n)4 .递归算法与非递归算法的转换( 借助栈)中序遍历: 先扫描根结点的所有左结点并将它们一一进栈, 然后出栈一个结14- 14 - 点*p ( p没有左孩子结点或者左孩子结点被访问过), 则访问他; 然后扫描右孩子结点, 将其进栈, 再扫描右孩子结点所有左结点并一一进栈, 直到栈空void In0rder2(BiTree T) {Ini t St ack (S);BiTree p = T;while(p|| lisEnpty(S)) {if(p) {Push(S. p);p = p->lchild;Jelse {Pop(S. p);visit(p);p = p->rchild;)))5 .层次遍历: 先将二叉树根结点入队, 然后出队访问该结点, 若它由左子树,将左子树入队, 若有右子树将右子树入队. 然后出队, 对出队结点进行访问, 如此反复void LevelOrder(BiTree T) IInnitQueue(Q);BiTree p;EnQueue(Q, T);whiledisEinpty(Q)) {DeQueue(Q, p);v isit(p );if(p->lchildl=NULL) {EnQueue(Q, p->lchi1d),)if(p->rchildl=NULL) {.EnQueue(Q, p->rchild);))6 .由遍历序列构造二叉树: 先序序列和中序序列可以唯一确定一棵二叉树,先序遍历中第一个结点必定是根结点, 中序遍历中根结点必然将序列分为两个子序列; 同理, 二叉树后序序列和中序序列也能唯一确定一个二叉树; 注意, 如果知道二叉树先序序列和后序序列, 不能唯一确定一个二叉树例如,求先序序列(ABCDEFGHI)和中序序列(B d止DGHFD所确定的二叉树。

      首先, 由先序序列可疯A,为二叉树的根结点. 中序序列中A之前的B C为左子树的中序序列,EDGHF1为右子树的中序序列. 然后由先序序列可知B是左子树的根结点,D是右子树的根结点•依此类推,就能将剩下的结点继续分解下去,最后得到的二叉树如图4-8 (c ).4 . 3. 2线索二叉树1. 基本概念: 利用二叉树中大量空链域( N个结点中有N+ 1个空指针)存放直接前驱或后继的指针; 线索化时规定, 若无左子树, 令Ic h i l d指向其前驱结点,若无右子树,r c h i l d指向其后继结点15-15 - lugIchilddatarchildrtagHa .J Ichild域指示结点的左孩子l a 8[l Ichild域指示结点的前驱JO rchild域指示结点的右孩子jl rchild域指示结点的后继线索二叉树存储结构为:t y p e d e f s t r u c t T h r e a d N o d e (E l e m T y p e d a t a ;s t r u c t T h r e a d N o d e *1 c h i 1 i i +r c h i Id ;i n t It a g , r t a g ,//S右线索标志} T h r e a d N o d e , *T h r e a d T r e e ;这叫线索链表,其中指向其前驱和后继的指针叫线索,线索二叉树2.线索二叉树的构造:遍历一次二叉树,遍历过程中,检查当前结点左右指针域是否为空,若为空,将他们改为指向前驱或后继的线索( 标识t a g有孩子则为0,无则为1 )图4 - 1 0 中序线索二叉树及其二叉链表示注:有时为方便,在二叉树线索链表上添加一个头结点,并令其Ic h i l d域指针指向二叉树根结点,其r c h i l d指向中序遍历的最后一个结点;反之,令二叉树第一个结点的Ic h i l d和最后一个结点的r c h i l d指向头结点,变成一个双向循环链表注:先序序列为n个顺序的树,不同二叉树个数为,4 . 4树森林4. 4. 1树的存储结构1 .双亲表示法:一组连续空间存储每个结点,每个结点增设一个伪指针,指示其双亲在数组中位置( 例下图:根结点为下标0,尾指针为-1 ) ;适合求双亲结点,16-16 - 不适合求孩子结点图4 -1 3 树的双亲表示法2 . 孩子表示法:将每个结点的孩子结点用单链表连接起来;适合查找孩子结点,不适合双亲结点图 4 4 4 树的孩子表示法和孩子兄弟表示法3 . 孩子兄弟表示法: 以二叉链表作为树的存储结构,包括结点值、指向结点第一个孩子结点和指向结点下一个兄弟结点的指针,方便实现树转化为二叉树,易于查找结点的孩子( 上图)4 . 4 . 2 树、森林和二叉树的转换1 . 树转化为二叉树规则:每个结点左指针指向它第一个孩子结点,右指针指向它在树中的相邻兄弟结点, 表 示 为 “ 左孩子右兄弟”, 由于根没有右兄弟, 所以树转化为二叉树没有右子树图4 -1 5 树转换为二叉树2 . 森林转化为二叉树:先将森林中每一棵树转化为二叉树,再将第一棵树的根作为转化为二叉树的根,第一棵树的左子树作为转化后二叉树根的左子树,第17- 17 - 二棵树作为转化后二叉树的右子树,第三棵树作为转化后二叉树根的右子树的右子树, 依次类推3.二叉树转化为森林:二叉树根及其左子树为第一棵树的二叉树形式,二叉树根的右子树又可以看做是一个由除第一棵树外的森林转化后的二叉树,应用同样的方法,直到最后产生一棵没有右子树的二叉树为止,就得到了原森林注 :(1 )树转化为二叉树:在兄弟结点间加一条线;对每一个结点, 只保留它与第一个子结点的连线,与其他子结点的连线全部抹掉; 以树轴为轴心, 顺时针旋转45°(2)森林转化为二叉树:将每棵树根相连,将森林中每棵树转化为相应的二叉树 ; 以第一棵树根轴心顺时针旋转45°4. 4. 3树和森林的遍历1 .树的遍历(1 )先根遍历: 与相应的二叉树的先序遍历相同(2)后根遍历:与相应的二叉树的中序遍历相同(3)层次遍历:与二叉树一样2 .森林的遍历(1 )先序遍历森林:访问森林每一棵树根结点;先序遍历第一棵树中根结点子树森林;先序遍历除去第一棵树之后剩余的树构成的森林(2)中序遍历森林: 中序遍历森林中第一棵树的根结点的子树森林;访问第一棵树根结点; 中序遍历除去第一棵树之后剩余的树构成的森林4. 5树与二叉树的应用4. 5. 1二叉排序树1 .定义:简称B S T ,也称二叉查找树;左子树值全部小于根结点值,右子树值全部大于根结点值,左右子树本身也是二叉排序树,所以二叉排序树中序遍历可以得到一个递增序列18- 18 - 2 .二叉排序树查找:从根结点开始,沿某一条分支逐层向下进行比较的过程,将给定值与根结点进行比较,若相等, 则查找成功;若根结点关键字大于关键字,在根结点左子树中查找, 否则在右子树中查找, 是一个递归的过程3 . 二叉排序树的插入: 若关键字k 小于根结点关键字, 则插入左子树中, 相反插入右子树中; 一定插入了叶结点中SI4-2I向二叉排序树中插入结点4 . 二叉排序树的构造: 按二叉排序树性质进行构造5 . 二叉排序树的删除: 将单个元素删除, 其他因为此删除的链再重新组合, 确保性质不变( 1 )若删除是叶结点, 则直接删除( 2 )若结点z只有一棵左子树或右子树, 则让z 的子树成为z 父结点的子树, 替代z 位置( 3)若结点z 有左右两棵子树, 则令z 的直接后继( 或直接前驱) 代替z , 然后从二叉排序树中删除这个直接后继( 或直接前驱)6 . 二叉排序树的查找效率分析( 1 ) 对于高度为H的二又排序树, 其插入和删除操作的运行时间都是0 ( n ) .19- 19 - 但在最坏的情况下, 构造二叉排序树的输入序列是有序的, 则会形成一个倾斜的单支树, 此时二叉排序树的性能显变坏, 树的高度也增加为元素个数N,如下图所示 :在等概率情况下, 图 4-23 (a)的查找成功的平均查找长度为ASL=(l+2X 2+3X 4+4X 3)/10=2. 9而 图 4-23 (b)的查找成功的平均查找长度为由上可知, 二叉排序树查找算法的平均查找长度, 主要取决于树的高度, 即与二叉树的形态有关. 如果二叉排序树是一个只有右( 左)孩子的单支树( 类似于有序的单键表), 其平均查找长度和单链表相同, 为0 (n ).如果二义排序树的左、右子树的高度之差的绝对值不超过1,这样的二叉排序树称为平衡二叉树. 它的平均查找长度达到O(log2 n)(2)二叉排序树与二分查找: 从查找过程看, 二叉排序树与二分查找相似. 就平均时间性能而言, 二叉排序树上的查找和二分查找差不多. 但二分查找的判定树唯一, 而二叉排序树不唯一, 相同的关键字其插入顺序不同可能生成不同的二叉排序树, 如上图所示;就维护表的有序性而言, 二叉排序树无须移动结点, 只需修改指针即可完成插入和删除操作, 平均执行时间为0(1嗝〃). 二分查找的对象是有序顺序表, 若有插入和删除结点的操作, 所花的代价是0 (n ).当有序表是静态查找表时, 宜用顺序表作为其存储结构, 而采用二分查找实现其查找操作;若有序表是动态查找表, 则应选择二又排序树作为其逻辑结构4. 5. 2 平衡二叉树1 . 定义: 要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树, 简称平衡树(AVL树)20- 20 - (a)平衡二叉树(b)不平衡的二叉树图4 - 2 4 平衡二叉树和不平衡的二叉树2 . 平衡二叉树的插入: 每当二叉排序树插入( 或删除)一个结点时, 查看是否导致不平衡, 若是则找到插入路径上离插入结点最近平衡因子绝对值大于1 的结点A , 以A为根的子树进行调整达到平衡插入27、16. 75. 382后的一又I t序树图4 - 2 5 最小不平衡子树示意( 1 )L L 平衡旋转( 右单旋转): 由于在结点A的左孩子( L )的左子树( L )上播入了新结点, A的平衡因子由1 增至2 , 导致以A为根的子树失去平衡, 需要一次向右的旋转操作. 将A的左孩子B向右上旋转代替A成为根结点, 将A结点向右下旋转成为B的右子树的根结点, 而B的原右子树则作为A结点的左子树( 2 ) RR 平衡旋转( 左单旋转) : 由于在结点A的右孩子( R ) 的右子树( R ) 上插入了新结点, A的平衡因子由T 减至- 2 , 导致以A为根的子树失去平衡, 需要一次向左的旋转操作. 将A的右孩子B 向左上旋转代替A成为根结点, 将A结点向左下旋转成为B 的左子树的根结点, 而B 的原左子树则作为A结点的右子树21- 21 - BL BRH H( a) 插入结点前( b) 插入结点导致不平衡图4-27 RR平衡旋转⑹ R R 旋转( 左单旋转)( 3 ) L R 平衡旋转( 先左后右双旋转) : 由于在A的左孩子( L ) 的右子树( R ) 上插入新结点, A的平衡因子由1增至2 , 导致以A 为根的子树失去平衡, 需要进行两次旋转操作, 先左旋转后右旋转. 先将A 结点的左孩子B 的右子树的根结点C向左上旋转提升到B 结点的位置, 然后把该C结点向右上旋转提升到A结点的位置图428 LR平衡旋转( 4 ) R L 平衡旋转( 先右后左双旋转) : 由于在A的右孩子( R ) 的左子树( L ) 上插入新结点, A的平衡因子由- 1减至- 2 , 导致以A为根的子树失去平衡, 需要进行两次旋转操作, 先右旋转左旋转. 先将A结点的右孩子B 的左子树的根结点C向右上旋转提升到B 结点的位置, 然后把该C结点向左上旋转提升到A结点的位置H H-I⑥插入结点前 ( b) 插入结点导致不平衡 ( c) RL旋转( 双旋转)图4-29 RL平衡旋转3 . 平衡二叉树的查找: 假设以表示深度为h 的平衡树中含有的最少结点数. 显然N 0 = 0 , N l = l , N 2 = 2 , 并且有+ N 〃 _ 2 + 1, 所有非叶结点平衡因子均为 1, 则结点数最少. 可以证明, 含有n 个结点平衡二叉树的最大深度为l o g2 % 因22- 22 - 此, 平衡二叉树的平均查找长度为O ( l o g2 〃 )图4 -3 0 结点个数n 最少的平宿二叉树4 . 5 . 3哈夫曼树( Huffma n ) 树和哈夫曼编码1 . 哈夫曼树的定义: 树中结点被赋予值( 权) , 从树根结点到任意结点的路径长度( 经过的边数) 与该点上权值的乘积称为该结点的带权路径长度. 树中所有叶结点的带权路径长度之和称为该树的带权路径长度, 记为叱乙= 为吗" 式中, w i/=1是第i 个叶结点所带的权值; l i 是该叶结点到根结点的路径长度. 在含有N个带权叶子结点的二又树中, 其中带权路径长度( W P L ) 最小的二叉树称为哈夫曼树, 也称为最优二叉树:例如, 下图甲的3 棵二叉树, 都有4个叶子结点a 、b 、c 、d , 分别带权7、5 、2 、4 、它们的带权路径长度分别为18 4 -3 1具有不同带权长度的二叉树(a) WPL=7x2+5x2+2*2+4*2=36(b) WPL=7x3+5x3+2* 1+4x2=46(c) WPL=7x 1+5x2+2*3+4x3=35其 中 图4-31 ( c )中 树的WPL最 小 - 可 以 验 证 ,它恰为哈夫曼树。

      2 . 哈夫曼树的构造:( 1) 将这N 个结点分别作为N棵仅含一个结点的二叉树, 构成森林F( 2 ) 构造一个新结点, 并从F中选取两棵根结点权值最小的树作为新结点的左、右子树, 并且将新结点的权值置为左、右子树上根结点的权值之和( 3 ) 从 F中删除刚才选出的两棵树, 同时将新得到的树加入F中( 4 ) 重复步骤( 2 ) 和( 3 ) , 直至F中只剩下一棵树为止3 . 哈夫曼树特点:23- 23 - (1)每个初始结点最终都成为叶结点, 并且权值越小的结点到根结点的路径长度越大(2)构造过程中共新建了 N-1个结点( 双分支结点) , 因此哈夫曼树中结点总数 为 2N-1(3)每次构造都选择2 棵树作为新结点的孩子, 因此哈夫曼树中不存在度为1 的结点例如, 权值{ 7} , 5, 2, 4} 的哈夫受树的构造过程如图所示图4 -3 2哈夫曼树的构造过程4 .哈夫曼编码: 可变长度编码比固定长度编码好得多, 其特点是对频率高的字符赋以短编码, 而对频率较低的字符则赋以较长一些的编码, 从而可以使字符平均编码长度减短, 起到压缩数据的效果. 如果没有一个编码是另一个编码的前缀, 则称这样的编码为前缀编码. 如0, 101和 100是前缀编码. 对前缀编码的解码也是很简单的, 因为没有一个码是其他码的前缀. 所以, 可以识别出第一个编码, 将它翻译为原码, 再对余下的编码文件重复同样的解码操作. 如00101100可被唯一地分析为0、0、101和 100由哈夫曼树得到哈夫曼编码是很自然的过程, 首先, 将每个出现的字符当做一个独立的结点,其权值为它出现的频度( 或次数) , 构造出对应的哈夫曼树. 显然, 所有字符结点都出现在叶结点中. 我们可以将字符的编码解释为从根至该字符的路径上边标记的序列, 其中边标记为0 表 示 “ 转向左孩子”, 标 记 为 1 表 示 “ 转向右孩子”.下图所示为一个由哈夫曼树构造哈夫曼编码示例, 矩形方块表示字符及其出现的次数24- 24 - 图4 -3 3 由哈夫曼树构造哈夫曼编码这棵哈夫曼树的WPL为WPL=lx45+34 13+12+16)+4x(5+9)=224第 5 章 图5 . 1 图的基本概念5 . 1 . 1图的定义: 图G是顶点集V和边集E 组成, 记为G = ( V , E ) , 其中V ( G ) 表示图G中顶点有限非空集, E ( G ) 表示图G中顶点之间关系( 边) 的集合, 图中顶点个数也叫图的阶, 图不可以是空, 边集可以为空1 . 有向图: E是有向边( 也叫弧) 的有限集合, G是有向图, 有向边记为< v , w > ,顶点v 到顶点w2 . 无向图: ( v , w )3 . 简单图: 不存在重复边, 不存在顶点到自身的边4 . 完全图: 无向图中任意两个顶点之间都存在边称为无向完全图, n 个顶点无向完全图有〃 ( , - 1 ) / 2 条边; 有向图中, 任意两定点间存在方向相反的两条边, 称为有向完全图, n 个 顶 点 有 条 边5 . 子图: 两个图, 图V I 的顶点是图V 2 的子集, 边也是V 2 的子集, 则V I 是 V 2的子图, 但也可能不是图, 即V I 不一定是V 2 子图6 . 连通、连通图和连通分量: 无向图中, 顶点v 到w 有路径存在, 则v 和w是连通的, 任意两个顶点间都存在路径则是连通图; 无向图中极大连通子图称为连通分量, 若有n 个顶点, 并且小于n - 1 条边, 则必为非连通图; 边最少( n - 1 条) 即构成一个树7 . 强连通图、强连通分量: 有向图中, 从顶点v 到w 和从w到v都有路径, 则称两顶点是强连通的, 任意一对顶点都是强连通的则是强连通图; 边最少即构成有向环8 . 生成树: 连通图生成树是包含全部顶点的一个极小连通子图, 顶点为n 个 ,生成树有n - 1 条边25- 25 - 9 . 顶点的度、入度和出度: 度是以该顶点为一个端点的边的数目; 对于无向图, 顶点度是依附于该顶点边的条数, 全部顶点的度之和等于边数的两倍; 有向图入度是以顶点v 为终点的有向边的数目, 出度是以顶点v 为起点的有向边的数目, 顶点度等于出度和入度之和, 有向图全部顶点的入度之和和出度之和相等且等于边数10 . 边的权和网: 每条边可以标上有意义的数值, 称为边的权值, 图称为带权图( 网)11 . 路径、路径长度和回路: 一个顶点到另一顶点全部路径过程, 路过边数称为路径长度, 第一个顶点和最后一个顶点相同的叫回路; 一个图有n 个顶点, 并且有大于n-1条边, 此图一定有环12 . 距离: 从顶点v 到w最短路径若存在, 则叫距离13 . 简单路径: 顶点不重复出现; 除第一个和最后一个顶点外,其余顶点不重复出现的回路叫简单回路 :14 . 有向树: 一个顶点入度为0,其余入度全为1,则称此有向 '图为有向树5. 2 图的存储及基本操作5. 2. 1 邻接矩阵法( 顺序存储)1 . 定义: 用一个一维数组存储顶点, 一个二维数组存储边的信息( 各顶点之间邻接关系) , n 个顶点是nxn的矩阵, 若( 匕电) e E ,则A[i][j] = l , 否则等于0;对于带权图, 则邻接矩阵中对应项存放着该边对应的权值, 若顶点v i和 v j不相连, 则用oo来表示这两个顶点之间不存在边2 . 注意①无向图的邻接矩阵是对称矩阵, 对规模特大的邻接矩阵可采用压缩存储②邻接矩阵表示法的空间复杂的为0( n「 2) , 其中n 为图的定点数3 . 图的邻接矩阵存储表示法具有以下特点:①无向图的邻接矩阵一定是一个对称矩阵( 并且唯一) , 因此, 在实际存储邻接矩阵时只需存储上( 或下) 三角矩阵的元素即可②对于无向图, 邻接矩阵的第i 行( 或第i 歹 ij) 非零元素( 或非无穷元素) 的个26-26 - 数正好是第i个顶点的度T D ( v i)③对于有向凰邻接矩阵的第i行( 或第i歹U )非零元素( 或非无穷元素) 的个数正好是第i个顶点的出度O D ( v i) (或入度I D ( v i) ) ,第i行 和 第i列和是有向图 第i结点的度④用邻接矩阵存储图, 很容易确定图中任意两个顶点时间是否有边相连. 但是, 要确定图中有多少边, 则必须按行、按列对每个元素进行检测, 所花费的时间代价很大. 这是用邻接矩阵存储图的局限性⑤稠密图适合使用邻接矩阵的存储表示5 . 2 . 2邻接表法1 .定义: 对图G中每个顶点建立一个单链表, 第i个单链表结点表示依附于顶 点v i的边( 有向图是以顶点v i为尾的弧)(■) flHtW (b)"“词G伤 / 搂 跳 .2 . 邻接表特点( 1 )如果G为无向图, 则所需存数空间为0 ( | V | + 2 | E | ) ,若为有向图, 则需O ( | V + | E | )( 2 )邻接表中给定一顶点, 能够很容易找到所有邻边, 而邻接矩阵中需要扫描一行, 时间为0 ( n ) ;但是若要确定两个顶点间是否存在边, 则在邻接矩阵里可以立即查找, 而在邻接表需要对相应结点的边表里查找另一结点, 效率较低( 3 )有向图邻接表中, 求一个给定顶点的出度只需计算其邻接表结点个数,但要求入度, 需遍历整表, 也可用逆邻接表5 . 3图的遍历从图中某一顶点出发, 按照某种方式沿着图中边对图中所有顶点访问有且仅有一次5 . 3 . 1广度优先搜索( B F S )27- 27 - 1 . 定义: 首先由顶点V 出发, 访问V中各个未被访问的邻接结点, 然后再依次访问邻接结点的未被访问过的邻接结点; 是一种分层查找方式, 每向前走一步, 访问一批结点, 不是递归; 为了实现逐层访问, 必须借助一个辅助队列( 例题见下图) ; 图的广度优先搜索与二叉树的层序遍历完全一致2 . 算法性能分析: 需要一个辅助队列, 最坏情况下, 空间复杂度为0 (|V |); 邻接表时间复杂度为0 (山 | + 但| ), 邻接矩阵时间复杂度为0 (|丫 | 2)3 . 广度优先生成树: 广度遍历中, 得到一颗遍历树, 称为广度优先生成树; 一给定图的邻接矩阵存储是唯一的, 故其广度优先生成树也是唯一, 但邻接表存储不唯一, 故广度优先生成树不唯一5. 3. 2 深度优先搜索(DFS)1 . 定义: 类似于树的先序遍历, 尽量进行深层遍历; 从一个顶点出发, 挨个访问其邻边未被访问过的顶点, 一直访问到不能继续进行的时候退回到原来的顶点, 退回路中挨个查找其邻边未被访问过的顶点, 并访问之, 一直退回到原点2 . 算法性能分析: 需要一个递归工作栈, 空间复杂度为0 (|V |),邻接矩阵存储, 时间复杂度为0 ( IV12), 邻接表存储, 时间复杂度为O(|V| + |E|)3 . 深度优先生成树和森林: 对连通图调用DFS生成树, 否则生成森林5. 3 . 3 图的遍历与图的连通性1 . 图的遍历算法可以判断图的连通性; 对于无向图, 若是连通, 则从一点出发, 仅需一次遍历就能访问图中所有结点, 若是非连通, 则一次只能访问连通分量; 对于28- 28 - 有向凰若从一个结点到每个结点都有路径, 则能够访问到图中所有结点, 否则不能5 . 4 图的应用5 . 4 . 1最小生成树( M S T )1 . 概念: 一个连通图的生成树是图的极小连通子图; 对于一个带权无向凰生成树不同, 每棵树的权( 权值之和)也可能不同, 最小生成树是权值最小的树2 . 最小生成树性质( 1 )最小生成树树形不唯一; 图中各权值互不相等时, G的最小生成树唯一; 若无向图连通图边比顶点少1 , 即G 本身就是一棵树, G的最小生成树就是本身( 2 )虽然最小生成树不唯一, 但最小生成树边的权值之和唯一且最小( 3 )最小生成树边数为顶点数减13 . 普里姆( P r i m )算法( 1 )概念: 算法从一个顶点开始, 在此顶点对应的结点中寻找最小权值的结点连接, 如此往复, 直至满了为止, 此时树必有n - 1 条边图5-20 Prim算法构造最小牛. 成树的过程( 2 )时间复杂度: 0 ( | V | 2 ), 不依赖于| E | , 适用于求解稠密图的最小生成树4 . 克鲁斯卡尔( K r u s k a l )算法( 1 )按权值递增序列选择合适的边来构造最小生成树, 开始时, 每个顶点构成一棵独立的树, T 此时为仅含V各结点的森林, 按G的边的权值递增顺序选择一条边, 若这条边加入不构成回路, 则将其加入, 否则舍弃, 直到含有n - 1 条边; 构造时按网中权值由小到大的顺序, 不断选取当前未被选取的边集中权值最小的边,选取n - 1 条边29- 29 - ( 2 )时间复杂度: 采用堆存放边的集合, 0 ( I E l o g | E | ), 适用于边稀疏而顶点较多的图5 . 4 . 2 最短路径1 . 概念:对于带权图, 路径上权值之和最小的叫最短路径;带权有向图G 的最短路径问题, 一般分为两类, 一类是单源最短路径, 即求某一顶点到其他各顶点的最短路径, 通过Di j k s t r a 算法, 二是求每一对顶点间的最短路径, 用Flo y d 算法2 . Di j k s t r a 算法求单源最短路径( 1 ) 概念:从某一顶点出发, 求到另一顶点的最小路径( 带权值) , 可以从一顶点出发挨个搜寻, 每一趟都需要得到最短的路径, 求的是一顶点到所有其他顶点的路径每墙得到的最短路径为:第1趟:I T ,路径距离为5第2趟:L 5 - 4 ,路都巨离为7第3趟:1 - 5 - 2 ,路 筋g离为8第4趟:1- 5 - 2 - 3 ,路径距离为9表5- 1从v i到各终点的d i”值和最短路径的求解过程图5-22 应用Dijkstra算法图顶点第1-第2招第3越第4趟210V |— Vj8V1— Vj-*v28V1-*¥S-*V23814V |-13V|— V $ -V 4 -V j9V L V L V 2 — Vj487yi-*vs~*V 455Vl -丫5集合S{b 5}{I, 5, 4)(1. 5, 4, 2)(1. 5, 4, 2, 3)( 2 ) 时间复杂度:邻接矩阵为0 ( | V 『) , 邻接表为O ( | V F) , 若要找出所有结点之间最短距离, 则时间复杂度为O d V F)( 3 ) 注意:若有负权值, 此算法不适用30-30 - 3 . Flo y d 算法求各顶点间最短路经过⑴产生一个n 阶方阵卬公用[ 力( k 从- 1 开始到n- 1 ) 表示从顶点vi 到 vj 路径长度, k 表示绕行第k 个顶点运算步骤;初始时, vi 和 vj 之间存在边, 则以此边权值作为最短路径, 若不存在边则以无穷作为权值; 以后逐步加入顶点k 作为中间顶点, 若增加中间结点得到的路径比原路径减少了, 则以此新路径代替原来路径0 6 13­10 0 45 8 0 .(b)G的邻接矩阵表5-2 Floyd算法的执行过程图5 -2 4带权有向图G及其邻接矩阵distdist⑼dist©VoV,V jV0Viv:VoViViVovtv2Vo0613061306100610Vj100410041004904VJ5co0511051105110( 2 ) 时间复杂度:0 ( | V | 3 )( 3 ) 注意: 允许带负权值的边, 但不允许包含带负权值的边组成的回路, 也适用于带权无向图5 . 4 . 3拓扑排序1 . 有向无环图:有向图中不存在环, 称为DA G图2 . A 0 V 网:用DA G图表示一个工程, 顶点表示活动, 有向边〈 v, w > 表示v 必须先于w , 称为A 0 V 网3 . 拓扑排序( 1 ) 一个有向无环图顶点组成的序列满足下列条件①每个顶点出现仅出现一次②若顶点A 排在B前面, 则不存在从B 到 A的路径( 2 ) 对一个DA G图进行拓扑排序①从DA G中选择一个没有前驱的顶点并输出②从图中删除该顶点和所有以它为起点的有向边③重复( 1 ) ( 2 ) 直到DA G图为空或者图中不存在无前驱顶点为止, 而后一种情31- 31 - 况说明有向图必存在环图5 .2 5仃向无环图的拓扑排序过程于是,得到拓扑排序后的结果为{ 1, 2, 4, 3, 5,( 3 ) 时间复杂度:O ( | V | + | E| )( 4 ) 用拓扑排序算法处理DA G图时, 注意:①一个顶点有多个直接后继, 拓扑排序不唯一;但若各个顶点已经排在一个线性有序序列中, 每个顶点有唯一前驱后继关系, 则结果唯一②对于一般的图, 若它的邻接矩阵是三角矩阵, 则存在拓扑序列5 . 4 . 4关键路径1 . A O E 网( 1 ) 概念:带权有向图中以顶点表示事件, 有向边表示活动, 边上权值表示完成的开销, 称为A O E网, 边上的权值表示活动的持续时间( 2 ) A 0 E 网性质: ( 1 ) 只有某顶点表示的事件发生后, 从该顶点出发的有向边所表示的活动才能开始( 2 ) 只有在进入某一顶点各有向边所代表的活动都已经结束时, 该顶点所代表的事件才能发生( 3) A O E 网中只有一个源点( 入度为0 ) 表示工程开始, 也只有一个汇点( 出度为 0 ) 表示工程结束( 4) 只有路径上所有活动都完成了, 整个工程才结束, 从源点到汇点的最大路径长度的路径称为关键路径, 关键路径上的活动叫关键活动( e( i ) = l ( i ) )( 5) 最短时间就是关键路径长度, 也就是关键路径上各活动花费开销之和2 . 参量定义( 1 )事件V k最早发生时间V e ( k) : 从V ( 源点) 到V k最长路径长度( 从前往后计算)32- 32 - ( 2 ) 事件V k最迟发生时间V I ( k) : 指在不推迟整个工程完成前提下, 保证它所指向的事件v i 在 V e( i ) 时刻能够快速发生时, 该事件迟早必须发生的时间( 从最后向前计算)( 3) 活动a i 最早发生的时间e( i ) : 指该活动起点所表示的事件最早发生的时间( 4) 活动a i 最迟发生的时间l ( i ) : 指该活动终点所表示的事件最迟发生时间与该活动所需时间之差( 5) 一个活动最迟开始时间l ( i ) 与最早开始时间e( i ) 差额d ( i ) = l ( i ) -e( i ) : 指活动完成时间余量, 是在不增减整个完成整个工程所需时间情况下, 活动a i 可以拖延的时间, 如果一个活动时间余量是0 , 该活动必须如期完成, 当 l ( i )= e( i ) 表示活动a i 是关键活动7 . 求关键路径步骤( 1 ) 求 A 0 E 网中所有事件最早发生时间v e( )( 2 ) 求 A 0 E 网中所有事件最迟发生时间v l ( )( 3) 求A 0 E 网中所有活动最早开始时间e( )( 4) 求A 0 E 网中所有活动最迟开始时间1 ( )( 5) 求 A 0 E 网中所有活动的差额d ( ) , 找出所有d ( ) = 0 的活动构成关键路径注: ( 1 ) 可以判断有向图是否有环: 深度优先遍历、拓扑排序、关键路径( 2 ) 不存在拓扑排序的有向图, 必存在回路( 3) 只有关键路径上所有活动时间同时减少, 才能缩短工期第 6章查找6 . 1查找的基本概念1 . 基本概念33- 33 - ( 1 ) 分为查找成功和查找失败( 2 ) 静态查找表: 无需动态修改查找表( 顺序查找、折半查找、散列查找) ; 动态查找表: 需要动态修改和删除的查找表( 二叉排序树查找、散列查找)( 3) 平均查找长度: 一次查找长度是需要比较的关键字的次数6 . 2顺序查找和折半查找6 . 2 . 1顺序查找1 . 概念: 主要用于线性表中查找, 分为无序线性表和有序线性表查找2 . 一般线性表顺序查找( 1 ) 从线性表一端开始逐个关键字是否满足要求, 若满足则查找成功, 若查找到末尾还未查找到则失败, 其中引入哨兵作用是不必判断数组是否越界, 因为当 i = = 0 时, 循环一定会跳出typedef struct ( 〃查找表的数据结构ElemType *elem; 7/元素存储空间基址,蟒时按实际长度分配,0 号单元留空int TableLen; 〃表的长度ISSTable;int Search_Seq(SSTable ST,ElemType key){〃在顺序表ST中顺序查找关健字为key的元素。

      若找到则返回该元素在表中的位置ST.elem[O]=key; / / “ 哨兵”f?r.CizST- TableLen;ST.elem,[i 11 «key; - i)〃从后往前找return i; 〃若表中不存在关键字为key的元素,将查找到i 为 0 时退出for循环} • ............. •一( 2) Z SL成功= (n+l )/2, 不成功= n+l ; 当n 较大时, 平均查找长度较大, 效率低; 优点是对元素存储无要求; 对线性的链表只能顺序查找3 .有序表的顺序查找(1)概念: 查找失败时可以不用再比较到表的另一端就能返回查找失败的信息, 可以用如下判定树表示查找 序 列 (10,20,30,40> 5 0 , 6 0 , )查找25 25X 0婢义 8 查找‘ °| (-°°,10) I S25>201 (10,20) [ S25001 (2030) [ 40=40| (M40)I (4 )「'| (50.60) |一 | (60,°°) |(2) NSL成功= (n+l )/2, 4 s■或必6 . 2. 2 折半查找1 .概念: 又叫二分查找, 仅适用于按关键字排列有序的顺序表34- 34 - 2.算法int Binary_Search(SeqList L,EiemType key)(〃在有序表L斗查找关键字为key的元素,若存在则返回其位置,不存在则返回7int low«0,high=L.TableLen-1,nid;while(low<»high){mid= (low+high) /2; 〃取中间位置if(L.elem[mid]»*key)return mid; 〃查找成功则返回所在位置else if (L.elem[mid]>key)high=mid-l; 〃从前半部分继续查找elselow=mid+l ; 〃从后半部分维续查找) :return -1;)例题: 已知 11 个元素有序表{ 7 , 10, 13, 16 , 19 , 29 , 32, 33, 37 , 4 1, 4 3} ,查找 11和32,可以用如下二叉树表示查找过程; 树最下面都是方形, 表示查找不成功的情况; 查找成功的查找长度为从根结点到目的结点的路径上的结点数, 而不成功的情况为从根结点到对应失败结点的父结点路径上结点数; 若有序序列有n个结点, 判定树有n个圆形非叶子结点和n+1个方形叶结点, 是为二叉排序树图& 2 描述折半查找过程的判定树查找成功:A SL = (l x l +2x 2+3x 4 +4 x 4 )/l l = 3,查找不成功 A SL = (3x 4 +4 x 8 )/12= 11/33.效率: 查找成功平均长度为Z SL = l o g 2(〃 + l )- l ,元素个数为n的树高(也即查找不成功的查找长度)为力= 「1。

      8 2(〃 + 1)] (往上进), 时间复杂度为8 2〃 )6 . 2. 3分块查找1 .概念: 将查找表分为若干个子表, 块内可以无序, 块间有序, 即第一个块关键字小于第二个块中所有记录的关键字, 依次类推, 再建立一个索引表, 索引表中每个元素含有各块最大关键字和各块的第一个元素的地址, 索引表按关键字有序排列2 .查找过程: 第一步在索引表确定待查记录所在块, 可以顺序可以折半, 第二步快内顺序查找35一 35 一 例如,关键码集合为{88, 24 , 72 , 61, 21, 6, 32, 11, 8 , 31, 22 , 83 , 78 , 5 4 } ,按照关键码值为24、54、78、8 8 ,分为四个块和索引表,如图6・ 3所示.图6 - 3分块宜找示意图3.查找长度: 长度为n 表均匀分为b 块, 每块s 个记录,NSL = 四+ 匕 L生 *1, 若s = &,则平均查找长度取最小& + 1,若对索2 2 2s引表采用折半查找, 则NSL = 「 l o g 2( 〃 + l ) [ + 皆^6 . 3 B 树和B +树6 . 3. 1 B 树及其基本操作1.概念: 又称多路平衡查找树, B 树中所有结点孩子结点数的最大值称为B树的阶, 用m 表示, 一棵m 阶B 树或为空树, 或有如下特征:( 1)树中每个结点至多m 个子树( 至多m T个关键字)( 2)若根结点不是终端结点, 则至少有两棵子树( 3)除根结点外所有非叶子结点至少有加/21棵子树( 至少有「 加/21- 1个关键字)( 4 )所有叶结点都出现在同一层上, 并且不带任何信息|18 33 I| 10 I I 回 |20 '21.1 |- 2 1 [ 1.31 J |45 可 |5。

      52)f i a o 6 b i n □ □ □ □ bi d b b □图 & 5 3 阶B树示意图2 . B 树的高度( 磁盘存取次数, 不包括最后一层不带任何信息的叶结点所在层)( 1)n 个关键字, m 阶 B 树, 高度为 l o g , , , (M + 1) [m/2 > 12 )兄弟够借: 若被删除关键字所在结点删除前关键字个数= 「 加/2 11,且与此结点相连的左( 右) 兄 弟 结 点 关 键 字 个 数 需 要 调 整 左 右 兄 弟 结 点 以 及双亲结点, 以达到平衡3)兄弟不够借: 若被删除关键字所在结点删除前关键字个数= 「 加/2 ] -1,且与此结点相连的左( 右) 兄 弟 结 点 关 键 字 个 数 则 将 关 键 字 删 除 后 与 左( 右) 兄弟结点及双亲结点中关键字进行合并注意: 在合并的过程中, 双亲结点中的关键字个数会减少. 若其双亲结点是根结点并且关键字个数减少至0(根结点关键字个数为1时, 有2棵子树) , 则直接将根结点删除, 合并后的新结点成为根; 若双亲结点不是根结点, 且关键字个数减少到「 用/2 1-2 ,又要与它自己的兄弟结点进行调整或合并操作, 并重复上述步骤,1)每个分支结点最多有m棵子树( 子结点)2 )非叶根结点至少有两棵子树, 其他每个分支结点至少有,/2 1棵子树3)结点的子树个数与关键字个数相4 )所有叶结点包含全部关键字及指向相应记录的指针, 而且叶结点中将关键字按大小顺序38- 38 - 排列. 并且相邻叶结点按大小顺序相互链接起来5) 所有分支结点( 可看成是索引的索引) 中仅包含它的各个子结点( 即下一级的索引块)中关键字的最大值及指向其子结点的指针2. m阶的B+树与m阶的B树的主要差异在于:1) 在 B+树中, 具有n 个关键字的结点只含有n 棵子树, 即每个关键字对应一棵子树; 而在B树中, 具有n 个关键字的结点含有( n+1) 棵子树2) 在 B+树中, 每个结点( 非根内部结点) 关键字个数n 的范围是pn/2~|WnWm( 根结点:1 WnWm) , 在 B树中, 每个结点( 非根内部结点) 关键字个数n 的范围是「 加/ 2]-1 WnWmT ( 根结点: 1 WnWmT)3) 在 B+树中, 叶结点包含信息, 所有非叶结点仅起到索引作用, 非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针, 不含有该关键字对应记录的存储地址4) 在 B+树中, 叶结点包含了全部关键字, 即在非叶结点中出现的关键字也会出现在叶结点中; 而在B树中, 叶结点包含的关键字和其他结点包含的关键字是不重复的如下图所示为一棵4 阶B+树的示例. 从图中可以看此分支结点的某个关键字是其子树中最大关键字的副本. 通常在B+树中有两个头指针: 一个指向根结点, 另一个指向关键字最小的叶结点. 因此, 可以对B+树进行两种查找运算: 一种是从最小关键字开始的顺序查找, 另一种是从根结点开始, 进行多路查找6. 4 散列表6. 4 .1 散列表基本概念39- 39 - 1 . 概念: 之前的算法建立在“ 比较”基础上, 效率取决于比较次数( 1 )散列函数: 将关键字映射成该关键字对应地址的函数, 记为H a s h ( k e y )= A d d r , 散列函数会把两个不同的关键字映射到同一地址, 称 为 “ 冲突”, 发生碰撞的不同关键字称为同义词; 应尽量减少冲突, 设计好的处理冲突的方法( 2 )散列表: 建立了关键字和存储地址之间直接映射关系6 . 4 . 2 散列函数的构造方法1 )函数定义域必须包括全部需要存储的关键字2 )散列函数计算出的地址能够等概率、均匀分布在整个地址空间, 减少冲突3 )散列函数尽量简单, 较短时间内能计算出任意关键字的地址1 . 直接定址法: 散列函数为“ ( 的) = a x* e y + 〃 ; 不会产生冲突, 适合关键字分布基本连续的情况, 若分布不连续, 则空位较多, 造成空间浪费2 . 除留余数法: 假定表长为m , 取一个不大于m 但最接近或等于m的质数p ,散列函数为/ / ( 左 " ) = « e y % p ( 需要选取好P )3 . 数字分析法: 适合与关键字已知的集合4 . 平方取中法: 取关键字平方值中间几位作为散列地址, 适用于关键字每一位取值都不够均匀或均小于散列地址所需位数5 . 折叠法: 适用于关键字位数很多, 而且关键字每一位数字分布大致均匀6 . 4 . 3 处理冲突的方法为产生冲突的关键字寻找下一个“ 空”的H a s h 地址, 用H i 表示冲突后第i次探索的散列地址1 . 开放定址法:乩 = ( H ( key) + di) ° /om , m 表示表长, d i 表示增量( 1 )线性探索法:d i = l 开始, 每次递增1 , 向后查找空位, 直到找到一个空位或查遍全表; 缺点:可能使第i 个散列地址同义词存在第i +1 个, 造成大量相邻的散列地址聚集, 大大降低了查找效率( 2 )平方探测法: 4 = 1 2 , _ 匕2 2 , _ 2 2 . . , 心加 / 2 , m = 4 k +3 , 又称二次探测法; 可以避免堆积问题, 缺点是不能探测到表的全部单元, 但至少可以探测到一半( 3 )再散列法:使用两个散列函数进行散列注意:不能随便删除表中元素, 因为若删除元素将会截断其他具有相同散列40- 40 - 地址的元素的查找地址, 所以要想删除一个元素, 给它做一个标记, 进行逻辑删除, 但副作用是表面上看起来散列表很满, 实际上有许多位置没有利用2 . 拉链法( 1 )为避免非同义词发生冲突, 可以把所有同义词存储在一个线性链表中,这个线性链表由散列地址唯一标识, 拉链法适用于经常进行插入和删除的情况例如, 关键字序列为{ 19,14,23,01,68,20,84,27,55,11,】 0 ,79),散列函数 H(key尸key%13,用拉链法处理冲突,建立的表如图6 /2 所示。

      o T2 13 二■% 168 卜 ]4 A6 2 按大小进行排序7 二"20下 |8 ~9巳, 10 二川】0 | 23 -12 [T6 . 4 . 4散列查找及性能分析1 . 散列查找( 1 )初始化:根据散列函数计算出散列地址, a d d r = H a s h ( k e y )( 2 )检测表中a d d r 位置上是否有记录, 没有记录则失败; 若有记录比较它与 k e y 值, 若相等返回成功标志, 不然执行下面( 3 )( 3 )用给定的处理冲突的方法计算“ 下一散列地址”, 并把a d d r 置为此地此转入⑵例如, 关键字序列{ 19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}按散列函数 H(key)=key%13和线性探测处理冲突构造所得的散列表L如图6-13所示0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15140168275519208479231110图 &1 3用线性探测法得到的散列表L给定值84的查找过程为:首先求得散列地址H(84)=6,因L[6]不空且L [6#84,则找第一次冲突处理后的地址H,=(6+1) % 16=7,而L⑺不 空 且L⑺邦4 ,则找第二次冲突处理后的地址氏= (6+2)%16=8, L[8]不空且L[8]=84,查找成功,返回记录在表中的序号8。

      给 定 值3 8的查找过程为:先求散列地址H(38)=12, L[12]不空且L[12]^38,则找下一地址H1=(12+l)% 16=13,由于L[13]是空记录,故表中不存在关键字为38的记录2 . 散列查找效率: 取决于散列函数、处理冲突方法和装填因子3 . 装填因子:八表中记录数n , 平均查找长度依赖于装填因子;a越大, 装填记散列表长度m录越满, 冲突可能性越大, 散列表查找成功与a有关, 与表长无关第 7 章排序7 . 1 排序的基本概念41- 41 - 7 . 1 . 1排序的定义1 . 定义: 按关键字递增或递减2 . 算法的稳定性: 排序中两个元素相等, 排序后位置不发生变化说明算法稳定, 主要是对算法性质的描述, 不能衡量算法优劣3 . 内部算法通常进行: 比较+ 移动, 基数排序不是基于比较的7 . 2插入排序基本思想是每次将一个待排序的记录, 按其关键字大小插入到前面已经排好序的子序列中, 直到全部记录插入完成, 每次插入便又多一个元素排好相对顺序7 . 2 . 1直接插入排序1 . 将第i 个元素插入到前面己经排序好的iT 的元素中, 步骤为:( 1 ) 查找出L ( i ) 在 L [ L . i - 1 ] 中位置k( 2 ) 将 L [ k . . i - l ] 中所有元素全部后移一位( 3 ) 将 L ⑴复制到L ( k )void InsertSort (ElemType n)•int i,j;for(i=2;i<=n;i++) 〃依次将A[2]〜插入到前面己排序序列if (A[i).keyA[0] .key) high=m id-l; 〃查找左半子表e ls e low=mid+l; 〃查找右半子表A [j+ l]= A [j];A[high+1]=A[O];〃统一后移元素,空出插入位置〃插入操作1 )2 . 效率: 减少了元素比较的次数, 约为。

      ( 〃 1 氏 〃 ) , 该比较次数与待排序初始状态无关, 仅取决于n ;移动次数没有改变, 依赖于待排序初始状态, 时间复杂度为0 ( 吟3 . 稳定性: 算法稳定7 . 2 . 3希尔排序1 . 定义: 先将待排序表分为若干个相同长度的子表( 最后一个可不计) , 分别进行直接插入排序, 当基本有序时, 再对整体做一次直接插入排序, 步骤:( 1 ) 取一个步长&, 分为4 组, 所有距离为& 倍数的放在一组( 2 ) 各组中进行插入排序( 3 ) 然后取步长小, 重复上述, 直到取到步长为1 , 即所有记录已放在同一组中, 再进行直接插入排序( 4 ) 一般的, 取4 = 〃 / 2 , dM =[d./2],并且最后一个为1void S h ellS o rt (ElemType A [],in t n ) {〃对顺序表作希尔插入排序,本算法和直接插入排序相比,作了以下修改:〃:I . 前后记录位置的增量是d k ,不是1〃2 .r[0 1 只是暂存单元,不是哨兵,当j<=时,插入位置已到fo r (dk=n/2;dk>™ l;dk=dk/2) 〃步长变化fo r(i^ d k + l; i<=n;++i)i f (ACi 1 .key O & & A [O ].k e y < A [j].k e y ;j-= d k )A [j+dk]=A [j]; 〃记录后移,查找插入的位置A [j+dk]-A [0]; 〃插入} //if)2 . 效率: 空间为0 ( 1 ) , 时间效率最坏情况下0 ( 1 )3 . 稳定性: 相同关键字会被划分为不同子表中, 所以为不稳定算法4 . 适用性: 仅适用于顺序表43- 43 - 7 . 3 交换排序根据序列中两元素关键字比较结果对换两元素7 . 3 . 1冒泡排序1 . 定义: 从后往前两两比较相邻元素值, 若为逆序则交换它们, 结果将最小的元素排到第一个位置, 每趟排序将需要排序的最小( 或最大) 的元素放到序列的最终位置void BubbleSort(ElemType A[]z int n)(〃用冒泡排序法将序列A 中的元素按从小到大排列for (i»0; ii; j — ) 〃一趟冒泡过程if(A(j-ll.key>A[j].key)( 〃若为逆序swap (A[ j-1] ,A[j]); 〃交换flag*true;-)if(flag==false)return ; 〃本趟遍历后没有发生交换,说明表己经有序}} ­2 . 效率: 空间复杂度0 ( 1 ) , 时间复杂度: 最好时, 基本有序, 第一趟比较n - 1次, 移动0 次, 所以最好为0 ( n ) ;当初始为逆序时, 需要进行n - 1 趟排序, 第i趟进行n - i次比较, 而且每次比较都需要移动元素3 次来交换, 最坏时间复杂度为0 ( 〃) , 平均也为0 ( r ? )3 . 稳定性: 稳定7 . 3 . 2 快速排序1 . 定义: 通常取第一个P iv o t 元素作为基准, 通过一趟排序将其分为两部分L [ l . . . k T ] 与 L [ k +1 . . n ] 其中 L [ l . . . k T ] 中元素都小于等于 p iv o t , 而 L [ k +1 . . n ] 中元素都大于等于p iv o t , 则p iv o t 放在其最终位置k 上, 而后分别递归对两个子表重复上述过程, 直至每部分只有一个元素或为空;具体实现为: 将表从后往前扫与基准元素对比, 比其小的第一个元素相互对换, 而后从前往后扫, 比其大的第一个元素与其相互对换, 依次重复直到完全定位2 . 空间效率: 需要一个递归工作栈, 最好为「 b g 2 ( 〃 + l ) ] , 最坏为0 ( n ) , 平均为O ( l o g2 n)3 . 时间效率: 运行时间与划分是否对称有关, 若两个区域基本有序或逆序( 即一边元素为n - 1 , 一边为0 个) , 最坏时间复杂度为M r ? ) , 可以尽量选取一个将数44- 44 - 据中分的元素;最好情况下, 均分时, 时间复杂度为O ( 〃l o g 2 ” ); 快速排序是平均性能最优的排序算法4. 稳定性: 不稳定5. 性质: 每趟排序后将一个元素放到最终位置上7 . 4选择排序第i趟在后面n - i+1个元素中选取关键字最小的元素作为有序子序列第i个元素, 直到n - 1趟7 . 4 . 1简单选择排序1 . 定义: 第i趟从L [ i. . n ]中选取最小元素与L ( i )对换, 每一趟排序可以确定一个元素的最终位置void SelectSort(ElemType A(] ,int n){〃对表A 作简单选择排序, A □从0 开始存放元素for(i=0;i

      氏 〃 )6 . 堆的插入:先将元素插入末尾, 再将这个结点向上进行调整, 时间复杂度为7 . 效率:空间复杂度0 ( 1 ) , 时间效率:建堆0 ( n ) , 之后有n - 1 次向下调整, 故最好最坏平均时间复杂度为O ( ” I o g / )8 . 稳定性:不稳定7 . 5 归并排序和基数排序7. 5. 1归并排序46- 46 - 1 . 定义:将表看做n 个有序的子表, 每个子表长度为1 , 然后两两合并, 称为2- 路归并排序2. 用法:设两段有序表Al l o w . . m i d ] 和 A[ m i d + L . h i g h ] 存放在顺序表相邻位置上, 先将他们复制到辅助数组B中, 每次从B中两个段取出一个记录进行比较, 将较小者放入A 中, 数组B中一段下表超出其对应表长时, 将另一段剩余直接复制到A 中; 基于分治的思想:将含有n 个元素的待排序表分为各含n / 2个元素的子表, 采用2- 路归并排序算法对两个子表递归进行排序, 合并两个已排序的子表初始关键字一越归并后二趟归并后三趟归并后图74 2- 路归并排序示例4 . 效率:空间复杂度0 ( n ) , 时间效率:每趟归并时间复杂度为0 ( n ) , 共需进行「 b g 2〃1 趟, 所以时间复杂度为0 ( “ |喝 〃 )5 . 稳定性:稳定6 . 注意:文件太大时, 内存放不下, 最好放在外存进行排序, 而外部排序通常采用归并排序7 . 5 . 2 基数排序1 . 定义:基于关键字各位大小进行排序, 并非基于比较2 . 空间复杂度为:0 ( r ) , r 为 r 个队列3 . 时间效率:基数排序进行d 趟分配和收集, 一趟分配需要0 ( n ) , 一趟收集需要0 ( r ) , 则时间复杂度为0 ( d ( n + r ) ) , 与序列初始状态无关4 . 稳定性:稳定7 . 6 各种内部算法的比较及应用7 . 6 . 1 各种内部算法比较时间复杂度空间复 是否稳算法种类最好 平均最坏杂度 定直接插入排0 ( n ) 0 ( n2)0 ( n2)0 ( 1 ) 是序47- 47 - 冒泡排序0 ( n )0 ( n2)0 ( n2)0 ( 1 )是序简单选择排0 ( n2)0 ( n2)0 ( n2)0 ( 1 )否希尔排序无法确定0 ( 1 )否快速排序0(〃 log, n。

      " log”0 ( n2)O(log2 n)否堆排序O(n log2 nO(n log,)O(n log2 n0 ( 1 )否序2- 路归并排O(n log2 nO(n log,)O(n log2 n0 ( n )是基数排序r ) )O ( d ( n +r ) )O ( d ( n +r ) )O ( d ( n +0 ( r )是7 . 6 . 2内部排序算法应用1. 小结( 1 )若n较小, 可以采用直接插入排序或简单选择排序( 2 )文件初始状态已按关键字基本有序, 采用直接插入或冒泡( 3 )若n较大, 采用快速排序、堆排序、归并排序; 当待排序关键字是随机分布时, 快速排序平均时间最短, 堆排序辅助空间少于快速排序, 但这两种情况都是不稳定的, 若要求稳定, 则采用归并排序( 4 )排序趟数与初始状态无关:直接插入排序、简单选择排序、基数排序48- 48 - 。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.