数据结构

这是一篇关于数据结构的思维导图，包括线性表、栈和队列、串、树与二叉树、查找、排序等内容，非常实用，值得收藏。

数据结构8.26

• 1绪论
  • 1.1数据结构的基本概念
    • 1.1.1基本概念和术语
      • 1.数据
        • 是信息的载体，能够输入计算机并被计算机程序识别和处理的符号的集合
      • 2.数据元素
        • 是数据的基本单位，一个数据元素可由多个数据项组成
          • 数据项：构成数据元素的不可分割的最小单位
      • 3.数据对象
        • 具有相同性质的数据元素的集合，是数据的一个子集(如学生信息对象是整体学生信息+课程信息的子集)
      • 4.数据类型
        • 是一个值的集合和定义在此集合上的一组操作的总称(如int型变量，其值集为某区间上的整数(区间大小以来不同机器)，定义其上操作为加减乘除和取模等运算)
          • 1.原子类型
            • 其值不可再分的数据类型
          • 2.结构类型
            • 其值可以分为若干(分量)的数据类型
          • 3.抽象数据结构ADT
            • 指一个数学模型和定义在该模型上的一组操作(仅强调逻辑特性)
              • 图解1-4
    • 1.1.2数据结构和三要素
      • 数据结构
        • 是相互存在特定关系的数据元素的集合
      • 三要素
        • 1.数据的逻辑结构
          • 线性结构
            • 一般线性表
            • 受限线性表
              • 栈、队列
              • 串
            • 线性表推广
              • 数组
          • 非线性结构
            • 集合
            • 树形结构
            • 图状结构
        • 2.数据的存储结构(映像、物理结构)
          • 顺序存储
            • 优点:1.可以实现随机存取2.每个元素占用最少存储空间;缺点:1.只能使用相邻的一整块存储单元，因而容易产生较多外部碎片
          • 链式存储
            • 优点:1.不要求逻辑上相邻的元素物理位置也相邻,因而不会产生碎片现象;缺点:1.指针消耗额外空间2.不能实现随机存取,只能顺序存取
          • 索引存储
            • 存储元素信息的同时，附加建立索引表，索引表中每项称为索引项(key,address);优点:1.检索速度快;缺点:1.附加索引表额外占用存储空间2.增删数据时也要修改索引表，花费较多时间
          • 散列存储
            • 根据元素关键字直接计算出元素的存储地址(Hash存储)优点:1增删查节点操作很快.;缺点:1.若散列函数不好,会产生元素存储单元冲突,解决冲突会增加时空开销
        • 3.数据的运算
          • 运算的定义
            • 针对逻辑结构,指出运算功能
          • 运算的实现
            • 针对存储结构,指出具体操作步骤
  • 1.2算法和算法评价
    • 是对特定问题求解的一种描述，是有限指令序列
      • 时间复杂度
        • 问题规模为n时，运行时间与O(1<log2n<n<nlog2n<n^2<n3<2^n<n!<n^n)成正比
      • 空间复杂度
        • 问题规模为n，除输入和程序之外的额外空间；算法原地工作：算法所需辅助空间为常量，即O(1)
• 2线性表
  • 2.1线性表的定义
    • 具有相同数据类型的n个数据元素的有限序列
  • 2.2线性表的顺序表示
    • 顺序表
      • 插入
        • Bool ListInsert(SqList &L,int i,ElemType e){ If(i < 1 || i > L.length+1) return false; If(L.length >= MaxSize) return false; For(int j = L.length;j>=i;j- -) //L.length在数组下标中为最后一个元素的后一个位置 L.data[j] = L.data[j-1]; L.data[i-1] = e; L.length ++; return true; }
          • 时间复杂度 最好 最坏 平均 O(1) O(n) O(n)
      • 删除
        • Bool ListDelete(SqList &L,int i,ElemType &e){ If( i<1 || i>L.length) return false; e = L.data[i-1]; For(int j = i;j<L.length;j++) L.data[j-1] = L.data[j]; L.length - -; Return true; }
          • O(1) O(n) O(n)
      • 按值查找(顺序查找)
        • Int LocateElem(SqList L,ElemType e){ For(int i=0;i<L.length;i++) If(L.data[i] == e) return i+1; Return 0; }
          • O(1) O(n) O(n)
  • 2.3线性表的链式表示
    • 单链表 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
      • 建立单链表
        • 头插法
          • LinkLIst List_HeadInsert(LinkList &L){ LNode *s;int x; L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; scanf(“%d”,&x); while(x != 9999){ s = （LNode*)malloc(sizeof(LNode)); s->data = x;s->next = L->next; L->next = s; s->data = x; scanf(“%d”,&x); } return L;}
        • 尾插法
          • LinkList List_TailInsert(LinkList &L){ int x; L = (LNode*)malloc(sizeof(LNode)); LNode *s,*r = L; scanf(“%d”,&x); while(x != 9999){ s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; s = r; scanf(“%d”,&x); } r-next = NULL; return L: }
      • 按序号查找节点
        • LNode *GetElem(LinkList L,int i){ int j = 1; LNode *p = L->next; if(i == 0) return L; if(i < 1) return NULL; while(p && j<i){ p = p ->next; j++; } return p; }
      • 按值查找节点表节点
        • LNode *LocateElem(LinkList L,ElemType e){ LNode *p = L->next; while(p != NULL && p->data != e) p = p->next; return p; }
      • 插入节点
        • p = GetElem(L,i-1); s->next = p->next; p->next = s; （i-1为p，在p后插）
          • 时间O(n)
        • s->next = p->next; p->next = s; temp = p->data; p->data = s->data; s->data = temp; (i为p，在p后插并交换data，实现p前插)
          • 时间O(1)
      • 删除节点
        • p = GetElem(L,i-1); q = p->next; p->next = p->next->next; free(q);
          • 时间O(n)
        • q = p->next; p->data = q->data; p->next = p->next->next; free(q);
          • 时间O(1)
      • 求表长
        • 表长不包括头节点
          • O(n)
    • 双链表 typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinkList;
      • 插入节点
        • s->next = p->next; s->next->prior = s; s->prior = p; p->next = s;
          • O(1)
      • 删除节点
        • p->prior->next = p->next; p->next->prior = p->prior; free(p);
          • O(1)
    • 循环链表 明显特征：最后一个结点指针不是NULL。判空条件为头结点是否等于头指针，而不是NULL；即if(L->next == L)
      • 循环单链表
      • 循环双链表
    • 静态链表 借助数组来描述线性表的链式存储结构。 特点：指针是结点的相对地址(数组下标)，又称游标。 和顺序表一样，静态链表也要预先分配一块连续的内存空间。 #define MaxSize 50 typedef struct{ ElemType data; int next; }SLinkList[MaxSize];
• 3栈和队列
  • 栈 卡特兰数:1/n+1(Ｃ2n n)
    • 栈的顺序存储（顺序栈） #define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int top;//栈顶指针 }SqStack;
      • 初始化 void InitStack(SqStack &S){ top = -1; }
      • 判栈空 bool StackEmpty(SqStack S){ if(S.top == -1) return true; else return false; }
      • 进栈 bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) return false; S.data[++S.top] = x;//top初始化为-1的情况 return true; }
      • 出栈 bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) return false; x = S.data[S.top- -]; return true; }
      • 读栈顶元素 bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; return true; }
    • 共享栈：利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间，将两个栈栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸;共享栈可以更有效地利用存储空间，两个栈空间相互调节，只有在整个存储空间被占满时才发生上溢
      • 初始:top0 = -1 top1 = MaxSize;栈满:仅当两个栈定指针相邻 top1 - top0 = 1
    • 链栈 typedef struct Linknode{ ElemType data; struct Linknode *next; }*LinkStack;
  • 队列
    • 队列的顺序存储 #define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front,rear; }SqQueue;
      • 顺序队列
        • 队空条件：Q.front == Q.rear ==0;注意Q.rear == MaxSize不能作为判别队满的条件，可能为假溢出
      • 循环队列 循环队列的出队、入队、判满操作都必有%;判空条件只有Q.rear == Q.front
        • 初始化 void InitQueue(SqQueue &Q){ Q.rear = Q.front = 0; }
        • 判队空 bool isEmpty(SqQueue Q){ if(Q.rear == Q.front) return true; else return false; }
        • 入队 bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear + 1)%MaxSize == Q.front) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1)%MaxSize; return true; }
        • 出队 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; }
    • 队列的链式存储（链队列） typedef struct LNode{ ElemType data; struct LNode* next; }LNode; typedef struct{ LNode *front,*rear; }LinkQueue; 链队列适用于数据元素变动比较大的情形，不存在队列满产生溢出的情况
      • 初始化 void InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkQueue)); //建立头节点 Q.front ->next = NULL; }
      • 判队空 bool IsEmpty(LinkQueue&Q){ if(Q.front == Q.rear) return true;//带有头节点的情况 else return false; }
      • 入队 void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL;//创建新节点，插入到链尾 Q.rear->next = s; Q.rear = s; }
      • 出队 bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.rear == Q.front) return false; LinkNode *p = Q.front->next; x = p->data; Q.front->next = p->next; if(Q.rear == p) Q.rear = Q.front;//原队列只有一个结点 free(p); return true; }
    • 双端队列：允许两端都可以进行入队和出队操作的队列，其元素逻辑结构仍是线性结构；将队列的两端分别称为前端和后端
      • 输入受限的双端队列
        • 允许在一端进行插入和删除，但在另一端只允许删除
      • 输出受限的双端队列
        • 允许在一端进行插入和删除，但在另一端只允许插入
  • 栈和队列的应用
    • 栈在括号匹配中的应用
      • []()([][]())为正确格式；(] [)为错误格式
        • 设置一个空栈，顺序读入括号；若是右括号，则弹栈顶元素检查，若匹配则出栈，反之报错；若是左括号，则压入栈中；算法结束时，检查栈是否为空，为空则匹配，非空则括号序列不匹配
    • 栈在表达式求值中的应用
      • 中缀表达式：依赖运算符的优先级，还要处理括号 后缀表达式：已经考虑了运算符的优先级，没有括号（表达式树的后序遍历） 中缀表达式转化为后缀表达式
        • 处理后缀表达式：顺序扫描表达式的每一项，若为操作数则压栈；若为操作符，则连续从栈中退出两个操作数Y和X，组成X<OP>Y，并将计算结果重新压入栈中
    • 栈在递归中的应用
    • 队列在层次遍历中的应用
      • 根结点入队；若队空(所有结点都处理完毕)，则结束遍历，否则重复下一步操作；队列中第一个根结点出队，并访问之，若有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回上一步
    • 队列在计算机系统中的应用
      • 1.解决主机入外部设备之间速度不匹配的问题； 2.解决由多用户引起的资源竞争问题
        • 1.主机与打印机：设置一个打印数据缓冲区，主机向缓冲区写满后就暂停输出，打印机依次从队列中fcfs取出，打印完后再向主机发送请求
        • 2.CPU资源分配：FCFS
  • 特殊矩阵的压缩存储 解题：根据相应条件，画草图现推，主要理解存储逻辑而不是记公式。
    • 数组 n个相同类型的数据元素构成的有限序列 维界：下标的取值范围 数组是线性表的推广，一位数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推；数组一旦被定义，其维数和维界就不再改变，因此除了初始化和销毁外，数组只会有存取元素和修改元素的操作；二维数组物理存储为映射到一位数组中！
      • 数组的存储结构 行优先；列优先
    • 矩阵的压缩存储 压缩存储：多个值相同的元素只分配一个存储空间，对零元素不分配存储空间 特殊矩阵：具有很多相同矩阵元素或零元素，分布有规律
      • 对称矩阵
        • A[1 n][1 n]存放在B[n(n+1)/2]中 推出一侧公式，另一侧把i j互换
      • 三角矩阵
        • A[1 n][1 n]存放在B[n(n+1)/2 + 1]中 推出一侧公式，另一侧只存放一个数在n(n+1)/2.具体情况具体分析，这个是下标从零开始的
          • 上三角矩阵
          • 下三角矩阵
      • 三对角矩阵
        • k=2i+j-3 当一只一位数组B的下标k时，i=(k+1)/3+1取下界，j=k-2i+3 ！！！不能死记硬背！！！要理解，画出三对角矩阵相应行的草图！！！
    • 稀疏矩阵 矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵。例如一个矩阵100x100，只有少于有100个非零元素
      • 使用三元组（行标、列标、值）或十字链表法
• 4串
  • 串的定义与实现
    • 串的定义：字符串简称串，计算机上非数值处理的对象基本都是字符串数据。 串(String) S；串中任意多个连续的字符串组成的子序列称为该串的子串，相应的包含子串的串称为主串 串的逻辑结构和线性表很相似，区别仅在于其数据对象限定为字符集；线性表操作对象为单个元素，而串的操作对象为子串！
    • 串的存储结构
      • 定长顺序存储 #define MaxLen 255 typedef struct{ char ch[MaxLen]; int length; }SString; 也可以不记录length，使用不计入串长的‘\0’来隐含串长
      • 堆分配存储表示(动态分配) typedef struct{ char *ch; int length; }HString; C语言中，动态分配的空间存放在堆中，malloc() free()来管理，若分配失败则返回NULL
      • 块链存储表示:每个结点称为块，一个块可以存放一个字符，也可以存放多个字符；整个链表称为块链结构 最后一个结点占不满一个块时通常用”#”补上
    • 串的基本操作 最小操作集：串赋值、串比较、求串长、串联接、求子串； 即这些操作不能利用其他串操作实现
      • 串赋值 StrAssign(&T,chars) 把T的值赋值为chars
      • 串比较 StrCompare(S,T) 若S>T,return>0;S=T,return 0;S<T,return<0
      • 求串长 StrLength(S) 返回S元素个数
      • 串联接 Concat(&T,S1,S2) 用T返回由S1 Ｓ2联接而成的新串
      • 求子串 SubString(&Sub,S,pos,len) 用Sub返回S串第pos个字符起，往后len长度的子串
  • 串的模式匹配 子串的定位操作通常称为串的模式匹配，求的是子串（常称模式串）在主串中的位置
    • 简单模式匹配算法
      • int index(SString S,SString T){ int i=1,j=1; while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){ i++;j++; } else{ i = i-j+1 + 1;j = 1; } if(j > T.length) return i - T.length; else return 0; } 最坏时间复杂度O(mn)
    • 改进模式匹配算法—KMP算法 匹配过程中，利用已经获得的匹配信息，使主串指针i不再回溯，而是继续从当前位置向后匹配。 模式向后滑动位数的计算仅与模式本身结构有关！与主串无关 虽然普通模式O(m+n) 但公认的的KMP算法时间复杂度为O(n+m)
      • 相关概念： 前缀：除最后一个字符外，字符串所有头部子串； 后缀：除第一个字符外，字符串的所有尾部子串； 部分匹配值（Partial Match,PM）：字符串的前缀和后缀的最长相等前后缀长度。 例子：’ababa’ 注意！！从主串的第一个字符开始，拆分出所有的子串，然后分别分析前缀后缀和最长相等前后缀的长度 ‘a’ 前缀后缀为空集，最长相等前后缀长度为0 ‘ab’ 前缀‘a’ 后缀‘b’ 最长相等匹配长度为0 ‘aba’ 前缀‘a’ ‘ab’ 后缀‘a’‘ba’ {‘a’ ’ab’} ^ {‘a’ ‘ba’} = ‘a’ ，最长相等前后缀长度为1 ‘abab’ 前缀 ‘a’ ‘ab’ ‘aba’ 后缀 ‘b’ ‘ab’ ‘bab’ ，最长相等前后缀长度为2 ‘ababa’ 前缀’a’ ‘ab’ ‘aba’ ‘abab’ 后缀 ‘a’ ‘ba’ ‘aba’ ‘baba’ ,{ } ^ { } = {‘a’ ‘aba’},最长相等前后缀长度为 3 所以最后字符串的部分匹配值为 00123
      • 使用KMP算法时，先写出模式串（子串）的PM表；当出现子串与主串不匹配时，在PM表中查找子串 最后一位 匹配的元素的PM值，然后让子串向后移动（已匹配字符数 - 最后一个匹配字符的PM值）的距离；某趟发生失配时，若对应部分的部分匹配值为0，那么表明已匹配序列中没有相等的前后缀，此时移动的位数最大（已匹配长度-0），直接移动到此时主串所指位置i进行下一趟比较 Move = (j-1) - PM[j-1];
      • next数组的产生与修改： 为了方便失配时不往前找一个字符，而是直接就去查当前失配字符位置的PM值，所以把PM中所有元素向右移动1位，首位用-1补齐，末位忽略； 叫做next数组，Move = （j-1）- next[j]; 此时j回退到 j = j - Move = next[j] + 1; 再把next全部加1，更新next数组，使得 j = next[j];（此时next数组首位为0） 最终next数组含义：当子串的第j个字符发生失配时，将子串跳到next[j]位置进行下一轮匹配！！！
        • 使用最终next数组的代码： int index_KMP(String T,String S,int next[]){ int i=1,j=1; while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){i++;j++;} else j = next[j]; } if(j > T.length) return i-T.length; else return 0; }
    • KMP算法的进一步优化 例子：当主串‘aaabaaaab’ 模式串‘aaaab’时，匹配到第四个位置失配，若使用上面的next[j]数组，会每次向左移动一个再比较；但会出现Pj = Pnext[j]的情况，造成冗余比较； 解决方法：确保不应该出现 Pj = Pnext[j];如果出现了，再次进行递归，将next[j]修正为next[next[j]]命名为nextval[j]
• 5树与二叉树
  • 树和森林
    • 概念
      • 树是n(n>0)个结点的有限集，n=0时称为空树；有且仅有一个根结点，其余节点可分为互不相交的有限集，称为子树； 1.树的根结点没有前驱，除根结点外的结点有且只有一个前驱 2.树中所有结点可以有零个或多个后继；树适合表示具有层次结构的数据； 3.术语：1.祖先-子孙(可以跨多层，只要有上下关系就可这样说)；孩子-双亲-兄弟(具有相同双亲节点)； 2.树中一个结点的孩子个数称为该结点的度；树中结点的最大度数为树的度； 3.度>0的结点称为分支结点(非终端结点)；度为0的结点称为叶子结点(终端结点)；分支结点的分支数就是这个分支结点的度； 4.结点的层次从树根开始定义，根结点为第一层；双亲节点在同一层的节点互为堂兄弟； 结点的深度是从根结点开始 自顶向下 逐层累加的 （想象树根向下变深） 结点的高度是从叶结点开始 自底向上 逐层累加的 （从下往上看很高） 树的高度或深度是树中结点的最大层数； 4.有序树和无序树，有序树不可互换 5.路径和路径长度：路径是这两个结点之间所经过的结点序列构成的，路径长度是所经过边的个数！ 6.森林：m棵不相交的树的集合。树只要把根结点删去就成了森林；反之，只要给m棵树加上一个根结点，森林变成了树
    • 性质
      • 性质： 1.树的结点数等于所有结点的度数之和(总分支数)+1(根结点) 2.度为m的树中第i层至多有m^i-1个结点(i>1) 3.高度为h的m叉树至多有(m^i - 1)/(m-1)个结点 4.具有n个结点的m叉树的最小高度为 对logm为底 (n(m-1) + 1)的对数取上界
    • 存储结构
      • 1.顺序存储：双亲表示法：大结构套小结构，小结构为data与parent指针；大结构为多个小结构组成的数组以及结点数。 #define Max_Tree_SIze 100 typedef struct{ ElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[Max_Tree_Size]; int n; }PTree; 该结构利用了每个结点(除根结点)只有唯一双亲的性质，可以很快得到每个结点的双亲节点，但求结点的孩子时需要遍历整个树。
      • 2.孩子表示法中：将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点就有n个链表(叶子结点为的孩子链表为空链表)； 这种方式找子女非常直接，但找双亲需要遍历n个结点中孩子链表指针所指向的n个孩子链表; 类似临界表
      • 3.孩子兄弟表示法：又称为二叉树表示法。 typedef struct CSNode{ ElemType data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; 方便实现树转换为二叉树的操作 左孩子有兄弟
    • 操作：树、森林与二叉树的转换
      • 树与二叉树的转换；树与二叉树都可以用二叉链表表示，物理结构上看相同，只是解释不同；树转换为二叉树的规则：左孩子右兄弟。由于根结点没有兄弟，所以根结点没有右子树；手写转换步骤：1.兄弟节点之间连一条线2.对每个结点只保留他与第一个孩子的连线，以其他孩子的连线全部抹掉3.以树根为轴心，顺时针旋转45度
      • 森林与二叉树的转换 1.先将森林中每棵树转化为二叉树 2.每棵树的根视为兄弟关系，后面的树依次作为前一棵树的右结点 3.以第一棵树的根为轴顺时针旋转45度
      • 二叉树转化为森林： 1.将根结点的右子树依次断开，直到剩一棵没有右子树的根结点 2.将所有断开的二叉树转化为树，就得到了原森林 二叉树转换为树或森林是唯一的
      • 二叉树转化为树 1.将根结点左子树的所有右结点、右右结点、。。。全部作为根的孩子 2.依次调整
    • 遍历
      • 树的遍历
        • 先根遍历 相当于相应二叉树先序遍历
        • 后根遍历 相当于相应二叉树的中序遍历！！！！！
        • 层次遍历
      • 森林的遍历
        • 先序遍历森林 从前到后每个树依次先根遍历
        • 中序遍历森林 从前到后每个树后根遍历(森林说中序遍历是相对对应的二叉树来说的)
    • 树的应用-并查集
      • 并查集是一种简单的集合表示，它支持3种操作 并查集的结构定义： #define SIZE 100 int UFSets[SIZE]; 并查集中一个集合就是一棵树，多个集合组成一个森林
        • 初始化操作(S为并查集),将集合S中每个元素都初始化为只有一个单元素的子集合，S为全集合，为一个森林，存放在双亲表示数组内(此时都为-1) void Initial(int S[]){ for(int i=0;i<size;i++) S[i] = -1; }
        • Find操作，查找集合S中单元素x所在的子集合，返回该子集合的名字 int Find(int S[],int x){ while(S[x]>=0)//循环找x的根 x = S[x];//将x赋为x的根号 return x; }
        • Union操作,把S集合中的子集合root2并入root1,要求root1,root2互不相交,否则不合并 void Union(int S[],int Root1,int Root2){ //要求Root1与Root2是不同的 S[Root2] = Root1; //将Root2连接到另一根Root1下方 } 森林中每棵树的根节点在双亲表示数组中的值是负的，绝对值为根下的节点总数
  • 二叉树
    • 概念：每个结点至多有两颗子树的树，且顺序不可颠倒。二叉树的结点次序不是相对另一结点而言的，二是确定的。(区别于度为2的树)； 几个特殊的二叉树： 1.满二叉树：每层都含有最多的结点 2.完全二叉树：1-n序号与满二叉树中结点完全对应 3.二叉排序树左子树上的所有结点的关键字均小于根结点的关键字，右都大于根 4.平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1 5.线索二叉树
      • 线索二叉树(不熟悉，因而特殊展开) typedef struct TreadNode{ ElemType data; struct TreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; 以结点结构构成二叉链表作为二叉树的存储结构，称为线索链表；指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树
        • 特点与定义： 利用二叉树的空指针来存放前驱或后继指针，从而像遍历链表那样方便地遍历。线索二叉树加快查找节点前驱和后继的速度！ 规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点； (lchild,ltag,data,rtag,rchild) ltag = 0,lchild指左孩子，ltag = 1,lchild指结点前驱 rtag = 0，rchild指右孩子 ，rtag = 1，rchild指结点后继
        • 中序线索二叉树的构造 二叉树的线索化实质就是遍历一次二叉树 void InTread(ThreadTree &p,ThreadTree &pre){ if(p!=NULL){ InThread(p->lchild,pre); if(p->lchild == NULL){ p->lchild = pre; p->ltag = 1; } if(pre!=NULL && pre->next->rchild == NULL){ pre->rchild = p; pre ->rtag = 1; } pre = p; InThread(p->rchild,pre); } } void CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T!=NULL){ InThread(T,pre); pre->rchild = NULL; pre->rtag = 1; } } 可以在二叉树的线索链表上也添加一个头节点，令lchild指二叉树根结点，rchild指二叉树最后一个访问的结点； 另外，二叉树第一个访问结点的lchild与最后一个访问结点的rchild都指向头节点。 就成为了一个双向线索链表，方便从前往后与从后往前对线索二叉树进行遍历
        • 中序线索二叉树的遍历 中序线索二叉树的结点中隐藏了线索二叉树的前驱和后继信息。 1.求中序线索二叉树中中序序列下的第一个结点： ThreadNode *Firstnode(ThreadNode *p){ while(p->ltag == 0) p = p->lchild; return p; }//找最左下结点(不一定为叶子结点) 2.求中序线索二叉树中结点p在中序序列下的后继 ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag == 0) return Firstnode(p->rchild); else return p->rchild; } 3.主函数 void Inorder(ThreadNode *T){ for(ThreadNode *p = Firstnode(T);p!=NULL;p-Nextnode(p)) visit(p); }
        • 先序线索二叉树和后序线索二叉树 只需要变动线索化改造的代码段与调用线索化左右子树递归函数的位置 指NULL的方向可能不同，一个前驱指NULL，一个后继指NULL； 具体前驱后继需要根据遍历顺序具体分析； 特殊：后序线索二叉树上找后继需要知道结点双亲，即需要采用带标志域的三叉链表作为存储结构(三叉链表为三个域，增加了指向父结点的指针)
    • 性质： 1.非空二叉树的叶子结点数等于度为2的结点数+1，即n0 = n2 + 1 2.非空二叉树第k层最多有2^(k-1)个结点 3.高度为h非空二叉树最多有2^h-1个结点 4.完全二叉树: i>1 双亲节点为 对i/2取下界。i偶数，i/2;i奇数，(i-1)/2 2i<=n i左孩子为2i，否则无左孩子 2i+1<=n i右孩子为2i+1，否则无右孩子 5.两个公式： 2^(h-1)-1<n<=2^h-1;2^(h-1) <=n <2^h
    • 存储结构： 1.顺序存储结构： 满二叉树与完全二叉树适合采用顺序存储结构；一般的二叉树需要添加很多空结点(数组中为0)；建议从数组下标1开始存储，符合完全二叉树i的性质 2.链式存储结构： 空间利用率高于顺序存储结构(一般二叉树) typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
    • 操作
      • 遍历
        • DFS 每个结点都访问一次且仅访问一次，时间复杂度与空间复杂度都为O(n)，递归工作栈的深度为树的深度
          • 先序遍历 void PreOrder(BiTree T){ if(T!=NULL){ visit(T); PreOrder(T->lchild); PreOreder(T->rchild); } } 非递归： void PreOrder2(BiTree T){ InitStack(S);BiTree p = T; while(p || !isEmpty(S)){ if(p){ visit(p);Push(S,p); p = p->lchild; } else{ Pop(S,p); p = p->rchild; } } }
          • 中序遍历 void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); visit(T); InOrder(T->rchild); } } 非递归： void InOrder2(BiTree T){ InitStack(S);BiTree p = T; while(p || !isEmpty(S)){//p不空或栈不空 循环 if(p){ //一路向左 Push(S,p); p = p->lchild; } else{ Pop(S,p);visit(p); p = p->rchild; //p向右子树走 } } }
          • 后序遍历 void PostOrder(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
        • BFS
          • 层次遍历 void LevelOrder(BiTree T){ InitQueue(Q); BiTree p = T; Enqueue(Q,p); while(!isEmpty(Q)){ Dequeue(Q,p); visit(p); if(p->lchild != NULL) Enqueue(Q,p->lchild); if(p->rchild != NULL) Enqueue(Q,p->rchild); } }
    • 应用
      • 二叉排序树BST (二叉查找树)
        • BST的查找 BSTNode *BST_Search(BiTree T,ElemType key){ while(T!=NULL&&key!=T->data){ if(key<T.data) T = T->lchild; else T=T->rchild; } return T; }
        • BST的插入：插入的结点一定是一个新添加的叶结点 int BST_Insert(BiTree &T,KeyType k){ if(T==NULL){ T = (BiTree)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->rchild = NULL; return 1; } else if(k==T->key) return 0; else if(k<T->key) return BST_Insert(T->lchild,k); else return BST_Insert(T->rchild,k); }
        • BST的构造 void Creat_BST(BiTree &T,KeyType str[],int n){ T = NULL; int i =0; while(i<n){ BST_Insert(T,str[i]); i++; } }
        • BST的删除
          • 被删除节点是叶子节点，直接删除
          • 被删除的节点z只有一棵左子树或右子树，则让其左子树或右子树代替z的
          • 被删除节点z左右子树都有，则令z的直接后继(或直接前驱)替代z，然后从BST中删去这个直接后继(或直接前驱)，这样就转换到了前两种情况
        • BST查找效率分析
          • BST的查找效率主要取决于树的高度 若BST的左右子树的高度差绝不值不超过1，则这样的二叉排序树叫做平衡二叉树，平均查找长度为O(log2n)； 若BST为单支树，则平均查找长度为O(n)
          • 平均查找长度ASL=∑PiCi (i=1,2,3,…,n)Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。
          • BST与二分查找的比较： 二分查找的判定树唯一，BST的查找不唯一(插入顺序影响树型)； 插入与删除：二分查找的对象是有序顺序表，需要O(n)，BST无需移动节点，只需要修改指针完成，为O(log2n)； 总结：有序表是静态查找表时，适合顺序表存储，用二分查找；有序表是动态查找表，应选择二叉排序树作为逻辑结构。
      • 平衡二叉树
        • 为避免降低二叉排序树性能而设计出来 定义：任意节点的左右字数高度差绝对值不超过1，简称平衡树； 节点左子树与右子树的高度差为该节点的平衡因子，平衡二叉树节点的平衡因子只能为-1 0 1；因此平衡二叉树可以定义为一棵空树
        • 平衡二叉树的插入： 每次调整的对象都是最小不平衡子树，即以插入路径上离插入节点最近的平衡因子的绝对值大于1的节点作为根的子树！ 平衡二叉树的插入过程前半部分与二叉排序树相同，但若插入后造成不平衡，则分为四种情况。(改进BST)； 这里的LL RR LR RL指的是插入的节点相对于最小不平衡子树根节点的位置(某孩子的某子树位置)
          • LL平衡旋转(右单旋转) 结点插入了A的左子树(一定紧挨)的左下方(不一定紧挨)，将第一个L处B节点(最小不平衡子树根节点左孩子)右旋代替A，将A作为B的右孩子，B原先的有孩子作为A的左子树。
          • RR平衡旋转(左单旋转) 结点插入了A的右孩子的右下方，将第一个R处B结点左旋代替A，将A作为B的左子树，B原先的左子树作为A的右子树。 ps:LL,RR模式都是帮助不平衡子树结点A的左/右孩子B“上位”
          • LR平衡旋转(先左后右双旋转) 结点A的左孩子的右子树上插入了结点。 先将A的左孩子B的右子树根节点C左上旋转提升到B的位置，然后把该C结点右上旋转提升到A结点的位置
          • RL平衡旋转(先右后左双旋转) 结点A的右孩子的左子树上插入了结点。 先将结点A的右孩子B的左子树根结点C进行右上旋转提升到B的位置，然后将C进行左上旋转提升到A结点的位置 ps：LR 和RL旋转时，新节点究竟插入C的左子树还是C的右子树不影响旋转过程。 LR,RL模式是帮助不平衡子树左/右孩子B的右/左子树的根节点C“上位”
        • 平衡二叉树的查找 与二叉排序树查找相同； 含有n个结点的平衡二叉树的最大深度为O(log2n)，因此最大查找长度也为O(log2n)； 可以求解给定结点数的平衡二叉树的查找所需的最多比较次数
        • 高度为h的平衡二叉树 最多有2^h - 1个结点； 最少有h(n)个结点，h(n)=h(n-1)+h(n-1)+1,h(0)=0,h(1)=1,h(2)=2c
      • 红黑树
        • 红黑树的概念
        • 红黑树的基本操作
        • 红黑树的性质
        • 红黑树的应用
        • 红黑树性能分析
      • 哈夫曼树和哈夫曼编码
        • 哈夫曼树的定义 树中结点被赋予一个表示某种意义的数值，称为该节点的权； 从树的根到任意结点的路径长度(经过的边数)，与该结点上权值的乘积，称为该节点的带权路径长度； 树中所有叶节点的带权路径长度之和称为该树的带权路径长度，记为WPL(Weighted Path Length of Tree)； 在n个带权叶结点的二叉树中，其中带权路径长度WPL最小的二叉树称为哈夫曼树！也称最优二叉树
        • 哈夫曼树的构造 给定n个权值分别为w1,w2,..,wn的结点， 新建一个根节点，每次挑选权值最小的两个结点组成一个二叉树，将两个结点的权值相加，并视为新建的根节点权值，将原有系列中的这两个根节点删除，新建的带有权值的根节点加入； 重复这个过程，直到无单独结点为止
        • 哈夫曼树的性质 1.每个初始节点最终都成为了叶结点，且权值越小的结点到根节点的路径长度越大 2.构造过程中，共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1 3.每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点
        • 哈夫曼编码
          • 几个相关概念： 固定长度编码：对每个字符用相等长度的二进制表示 可变长度编码：对不同字符用不等长的二进制位表示 可变长度编码比固定长度编码好得多，因为对出现频率高的字符可以赋以短编码，对频率低的编码赋以长编码，从而使字符的平均编码长度减短，起到压缩数据的效果，哈夫曼编码是一种广泛应用且非常有效的数据压缩编码 没有一个编码是前缀的编码，为前缀编码；对其解码：从前往后识别，将其翻译成原码
          • 哈夫曼树从根往下走，一侧赋予0，一侧赋予1(左右谁0谁1皆可，只要始终保持统一)； 哈夫曼树的WPL可视为最终编码得到的二进制编码长度； 哈夫曼树不唯一，WPL必然都是最优的
• 6图
  • 图的基本概念
    • G=(V,E)，顶尖集V，边集E；V(G),表示图G中顶点的有限非空集；E(G)表示图G的顶点之间的关系（边）的集合；|V|表示顶点个数，|E|表示边的条数 线性表可以是空表，树可以是空树，但图不能是空图； 图中的顶点集V必非空，E可以为空
      • 有向图，无向图 有向图：E为有向边(弧)，弧是顶点的有序对，记为<v,w> 无向图：E为无向边(边)，边是顶点的无序对，记为(v,w)
      • 简单图，多重图 简单图： 1.不存在重复边(有向图的两相邻节点间指向彼此的边不算重复边) 2.不存在顶点到自身的边 多重图： 1.两顶点间边数大于1 2.允许顶点通过一条边和自身关联 多重图和简单图的定义是相对的，数据结构中仅讨论简单图
      • 完全图(简单完全图) 对于无向图，|E|取值范围为0-n(n-1)/2， 有n(n-1)/2条边的无向图称为完全图，任两顶点间有边； 对于有向图，|E|的取值范围为0-n(n-1)， 有n(n-1)条弧的有向图称为有向完全图，任两顶点间存在相反弧
      • 子图 G=(V,E),G'=(V',E'); 若V'是V子集，E'是E子集，则称G'为G的子图 若满足V(G')=V(G),则称G'为G的生成子图； 并非V和E的任何子集都能构成G子图，因为E的子集中某些边关联的顶点可能不在这个V的子集中
      • 连通、连通图和连通分量 若从顶点v到顶点w有路径存在，则称v和w是连通的 若G中任意两个顶点都是连通的，则成为连通图，反之为非连通图 无向图中的极大连通子图，称为连通分量。 连通图最少有n-1条边 如果边数小于n-1，则必定为非连通图； 非连通图，最多可以有多少条边？ ：n-1个顶点构成一个完全图（在任意加入一条边构成连通图）的临界状态
        • 极大连通子图：图G中不被其他连通子图包含的连通子图(这里极大不是某种具体量的极大，而是不被包含的关系，其实也就是连通子图中所有顶点和边都存在的意思） 极小连通子图：图G的生成树是一个极小连通子图
      • 强连通图、强连通分量 在有向图中，若一对顶点v到w，w到v间都有路径，则称这两个顶点是强连通的， 若图中任何一对顶点都是强连通的，则称此图为强连通图。 有向图中极大强连通子图称为有向图的强连通分量； 有向图强连通情况下边最少的情况：至少需要n条边，构成一个环路
      • 生成树，生成森林 连通图的生成树是包含图中全部顶点的一个极小连通子图，若定点数为n，则其生成树有n-1条边。若砍去生成树一条边，则会变成非连通子图；若加上一条边，则会形成一个回路。 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
      • 顶点的度、入度和出度 无向图：TD(v),无向图全部顶点的度的和等于边数2倍 有向图：顶点v的度分为入度ID(v)和出度OD(v)，顶点v的度等于入度与出度之和：TD(v)=ID(v)+OD(v),有向图全部顶点的入度等于出度等于边数
      • 边的权和网 每条边都可以标上具有某种含义的数值，称为该边的权值，边上带权值的图称为带权图，也成为网
      • 稠密图、稀疏图 边数很少的图称为稀疏图，反之称为稠密图。 一般当G满足|E|<|V|log|V|时，视G为稀疏图
      • 路径，路径长度和回路 路径：顶点vp到vq间一条路径指顶点序列vp,vi1...vim,vq， 路径上边的数目称为路径长度 第一个顶点和最后一个顶点相同的路径称为回路或环 若一个图有n个顶点，有大于n-1条边，则此图一定有环
      • 简单路径、简单回路 路径序列中，顶点不重复出现的路径称为简单路径； 除第一个顶点和最后一个顶点外，其余顶点不辍那个图出现的回路称为简单回路
      • 距离 从顶点u到顶点v的最短路径若存在，则此路径长度为u到v的距离； u到v根本不存在路径，则记该距离为∞
      • 有向树 一个顶点入度为0，其余顶点出度均为1的有向图，称为有向树
  • 图的存储
    • 邻接矩阵法
      • 指用一个一维数组存储图中顶点关系，用一个二维数组存储图中边的信息(个顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵 整个图G的存储结构： #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; typedef struct{ VertexType Vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵,边表 int vexnum,arcnum; }MGraph;
        • 注意： 1.简单应用中，可直接用二维数组作为图的邻接矩阵 2.无向图中，邻接矩阵是对称矩阵(唯一)，可以压缩存储 3.当邻接矩阵仅表示边是否存在时，ElemType可采用0、1的枚举类型 4.邻接矩阵表示法的空间复杂度为O(n^2),n为顶点数|V|
        • 邻接矩阵表示法特点： 1.无向图第i行(或j列)的非零元素(或非∞)个数表示结点的度TD(v) 有向图第i行和j列的非零元素(或非∞)个数表示节点的出度OD(v)和入度ID(v) 2.用邻接矩阵存储图，很容易确定图中任意两个顶点间是否有边联系；但要确定图中有多少条边，则需要按行列对每个元素进行检测，花费时间代价很大。 3.稠密图适合用邻接矩阵的存储表示 4.设图G的邻接矩阵是A，A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
    • 邻接表法
      • 当一个图为稀疏图时，使用邻接表法节省了大量的空间；图的邻接表法结合了顺序存储和链式存储方法 对图中每个顶点建立一个单链表，第i个单链表中的结点依附于顶点的边vi，这个单链表就是顶点vi的边表(有向图称为出边表)(边表的"边"真是amazing啊)边表的每个节点都表示一条边，只不过自己存储一个顶点号，省略了另一个顶点号(顶点表中的) 边表的头指针和图G的顶点数据信息采用顺序存储(称为顶点表)； #define MaxVertexNum 100 typedef struct ArcNode{//边表节点 int adjvex;//该弧所指向顶点的位置 struct ArcNode *next; //Info Typeinfo； //网的边权值 }ArcNode; typedef struct VNode{ VertexType data;//顶点信息 struct VNode *first;//指向第一条依附该顶点的弧的指针 }VNode，AdjList[MaxVertexNum]; typedef struct{ AdjList vertices;//邻接表 int vexnum,arcnum;//图的顶点数和弧数 }ALGraph
        • 特点： 1.对于无向图，所需存储空间O(|V|+2|E|);(每条边在邻接表中出现了两次) 对于有向图，所需存储空间为O(|V|+|E|); 2.对于稀疏图，采用邻接表能够极大地节省存储空间 3.邻接表中，给定一顶点，很容易找到它所有的边；邻接矩阵中需要扫描一行,O(n) 若要确定给定两顶点间是否存在边，则在邻接矩阵中能够快速找到(有点随机存取的意思)；而邻接矩阵需要在相应的结点对应的边表中查找另一结点，效率较低。 4.在有向图中，求一个顶点的出度只需要计算其相邻邻接表中的节点个数，但求出度则需要遍历全部邻接表；所以可以采用逆邻接表来加快顶点入度的求解。 5.图的邻接表并不唯一，各边结点的连接次序是任意的。
    • 十字链表法
      • 十字链表是有向图的一种链式存储结构，图中的每一条弧都有一个结点。 弧结点有5个域：(tailvex,headvex,hlink,tlink,info) tailvex,headvex分别为边的发出顶点和插入顶点；hlink,tlink分别连接相同发出,插入顶点的边结点 顶点结点有3个域：(data,firstin,firstout) 十字链表并不唯一，但一个十字链表表示确定一个图 十字链表中，既容易找到V的入度，也容易找到V的出度
    • 邻接多重表法
      • 邻接多重表是无向图的一种链式存储结构 边结点(mark,ivex,ilink,jvex,jlink,info) mark为标志域，可以标记这条边是否被搜查过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于ivex的边；jlink指向下一条依附于顶点jvex的边；info为指向和边相关的各种信息的指针域 顶点(data,firstedge)
  • 图的基本操作
    • Adjacent(G,x,y);Neighbors(G,x);InsertVertex(G,x);DeleteVertex(G,x); AddEdge(G,x);RemoveEdge(G,x,y);FirstNeighbor(G,x);NextNeighbor(G,x); Get_edge_value(G,x,y);Set_edge_value(G,x,y,v);
  • 图的遍历 从某顶点出发，对所有的顶点访问一次且仅访问一次，是求解连通性问题，拓扑排序，求关键路径算法问题的基础； 与树不同的是，避免同一个顶点被访问多次，在遍历一个顶点后需记录下来，辅助数组visited[]; 图的遍历有BFS和DFS 采用邻接矩阵，时间复杂度O(n^2);采用邻接表，时间复杂度O(|V|+|E|); BFS\DFS所需空间O(n) (时空复杂度与BFS\DFS的方法选择无关，主要看存储方式)
    • 广度优先搜索 类似于树的层次遍历 逐层访问，所以需要一个辅助队列 bool visited[MAV_VERTEX_NUM]; void BFSTraverse(Graph G){ for(int i=0;i<G.vexnum;i++) visited[i] = FALSE; InitQueue(Q); for(int i=0;i<G.vexnum;i++) if(!visited[i]) BFS(G,i); } void BFS(Graph G,int v){ visit(v); visited[v] = TRUE; Enqueue(Q,v); while(!isEmpty(Q)){ for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) if(!visit[w]){ visit(w); visited[w] = TRUE; Enqueue(Q,w); } } }
      • BFS求解单源最短路径问题 void BFS_MIN_Distance(Graph G,int u){ for(i=0;i<G.vexnum;i++) //d[i]表示从u到i的最短路径 d[i]=∞;//初始化路径长度 visited[u]=TRUE; d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){ DeQueue(Q,u); for(w=FirstNeighbor(G,u);w>=0;w=NextN eighbor(G,u,w)) if(visited[w]){ visited[w]=TRUE; d[w]=d[u]+1;//路径长度+1 EnQueue(Q,w); } } }
      • 广度优先生成树 邻接矩阵存储唯——-其广度优先生成树唯一 邻接表存储不唯一———其广度优先生成树不唯一
    • 深度优先搜索
      • 类似于树的先序遍历 bool visited[MAX_VERTEX_NUM]; void DFSTraverse(Graph G){ for(v=0;v<G.vexnum;v++) visited[v] = FALSE; for(v=0,v<G.vexnum;v++) if(!visited[v]) DFS(G,v); } void DFS(Graph G,int v){ visit(v); visited[v] = TRUE; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) if(!visited[w]){ DFS(G,w); } }
        • 深度优先生成树和生成森林 连通图能够产生深度生成树，非连通图生成森林
    • 图的连通性
      • 图的遍历算法可以用来判断图的连通性。 无向图若连通，从任意顶点出发，仅需遍历一次就能够访问图中的所有顶点； 有向图若连通，若从初始点到图中每个顶点都有路径，则能够访问到图中所有顶点
  • 图的应用
    • 最小生成树 若砍去一条边，则会使生成树变成非连通图； 若增加一条边，则会形成途中一个回路； 最小生成树特殊，要求是生成树集合中边的权值之和最小的生成树； 各边权值不同时，最小生成树唯一；一般情况最小生成树不一定唯一 最小生成树边的权值之和总是唯一的，且是最小的 GENERIC_MST(G){ T=NULL; while T 未形成一棵生成树； do 找到一条最小代价边(u,v)并且加入T后不会产生回路; T=T∪(u,v); }
      • Prim算法(BFS) 类似于Dijkstra,初始时从图中任取一顶点，加入树T，之后选择一个与当前T中顶点集合距离最近的顶点，将该顶点和边加入树T；每次操作后T中的顶点数和边数都增加1；直到图中所有顶点都加入树T，得到T为最小生成树。 T中必有n-1条边 void Prim(G,T){ T=空集； U={W}; while((V-U)!=空集){//若树中不含有全部顶点 设(u,v)是使u∈U与v∈(V-U)，且权值最小的边； T=T∪{(u,v)};//边归入树 U=U∪{v};//顶点归入树 } } Prim算法时间复杂度为O(|V^2|),不依赖|E|,因此适用于求解边稠密的图的最小生成树
      • Kruskal算法 区别于Prim从顶点开始扩展生成最小生成树的算法，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树。 初始时，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未选取过且权值最小的边，若该边依附的顶点落在T的不同连通分量上，则将此边加入T，否则舍弃此边；直到T中所有顶点都在一个连通分量上 void Kruskal(V,T){ T=V;//初始化T，仅含顶点 numS=n;//连通分量数 while(numS>1){//若连通分量数大于1 从E中取出权值最小的边(v,u) if(v和u属于T中不同的连通分量) T=T∪{(v,u)}; numS--; } } } Kruskal算法采用堆存放边的集合，因此每次选择权值最小的边只需要O(log|E|)的时间；每次添加新边类似于求解等价类的过程，可采用并查集的数据结构来描述T，时间复杂度为O(|E|log|E|),所以Kruskal适合于边稀疏而顶点较多的图
    • 最短路径 前面图的BFS遍历求解最短路径是针对无权图的，这里讨论带权路径长度最短的最短路径； 求解最短路径的算法都依赖于一条性质：两点之间的最短路径也包括了路径上其他顶点间的最短路径。
      • Dijkstra算法(BFS) 单源最短路径； Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0放入S，集合S每并入一个新顶点vi，都要修改源点v0到集合V-S中顶点当前的最短路金长度值；不允许边上带有负权值 设置两个辅助数组： dist[]：记录从源点v0到其他各顶点当前的最短路径长度，初态：若v0到vi有弧，则dist[i]为弧的权值；否则设置dist[i]为∞。(dist[]每次只往后探一步-BFS思想) path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点。算法结束时，可以追溯得到源点v0到顶点vi的最短路径。 手动求解时，画一个dict数组，最重要的是每次选定所到顶点后要将此顶点加入集合S，并更新个点路径距离，然后从集合S最后一个顶点开始走下一步 时间复杂度O(|V|^2)
      • Floyd算法 每对顶点间的最短路径 递推产生一个n阶方阵序列：A^-1,A^0,..A^N;其中A^k[i][j]表示顶点i到j的长度，并且以第k个顶点作为中间顶点进行松弛操作 时间复杂度为O(|V|^3)(相当于Dijkstra算法每个顶点运行一次O(|V^2|)*|V|), 不允许有负权值的边，可以作用于有向图\无向图(转化为双边相同的有向图)
    • 有向无环图描述表达式 有向无环图DAG(Directed acycle graph)：一个有向图中不存在环。 是描述含有公共子式的表达式的有效工具。 如一串中缀表达式可以用二叉树表示(根节点存放运算符，子树存放运算数)中有重复出现的子式，利用有向无环图，则可实现对相同子式的共享
    • 拓扑序列 有向无环图顶点组成的序列，每个顶点只出现一次，且若顶点A在序列中排在顶点B的前面，则在图中不存在B到A的路径。也可以理解为：拓扑序列是对有向无环图的顶点的一种排序。 每个AOV网都有一个或多个拓扑排序序列。
      • AOV网(Activity on vertex network) 若用DAG表示一个工程，其顶点表示活动，有向边<Vi,Vj>表示Vi必须先于Vj的一种关系，则将这种图称为顶点表示活动的网络。 对AOV网进行拓扑排序的算法很多，其中一个常用算法： 1.从AOV网中选择一个没有前驱的顶点并输出 2.从网中删除该顶点和所有以它为起点的有向边 3.重复1.2步骤直到AOV网为空or当前网中不再存在无前驱的顶点为止(说明图中必有环) 由于输出每个顶点还要删除它起始的边，所以拓扑排序的时间复杂度为O(|V|+|E|) 另外，使用DFS也可以实现拓扑排序(挨个从入度为0出度非0的顶点出发，只要出现回溯就失败，直到一笔画完成) 逆拓扑排序 从出度为0的顶点入手 AOV网采用邻接矩阵存储，若为三角矩阵，则必有拓扑序列，反之不一定
        • bool TopologicalSort(Graph G){ InitStack(S); for(int i=0;i<G.vexnum;i++) if(indegree[i]==0) Push(S,i);//将所有入度为0的顶点进栈 int count=0; while(!isEmpty(S)){ Pop(S,i); print[count++]=i;//输出顶点 for(p=G.vertices[i].firstarc;p;p=p->nextarc){ //将所有i指向的顶点的入度减1，将入度减为0的顶点压栈 v = p->adjvex; if(!(--indegree[v])) Push(S,v); } if(count<G.vexnum) return false; else return true; }
    • 关键路径
      • AOE网(Activity on edge network) 以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间) AOE网的两个性质： 1.只有在某顶点所代表事件发生后,从该顶点出发的各有向边所代表的活动才能开始 2.只有在某顶点的入边所代表的活动都完成后，该顶点的事件才能发生。 AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，代表整个工程的开始；AOE网也仅有一个出度为0的顶点，称为结束顶点(汇点)，代表整个工程的结束。 AOE网中的某些活动是可以并行进行的，但所有路径上的所有活动都已完成才能结束，因此从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动(找到了关键活动就等于找到了关键路径)。 完成整个工程的最短时间就是关键路径的长度。
        • 寻找关键活动 1.事件vk的最早发生时间ve(k) 它使指从源点v1到顶点vk的最长路径长度，事件vk的最早发生时间最顶了所有从vk开始的活动能够开工的最早时间。设vk为vj的任意后继 if(ve[j]+Weight(vj,vk) > ve(k)) 则ve[k]=ve[j]+Weight(vj,vk) "紧张操作" 计算ve()值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算 2.事件vk的最迟发生时间vl(k) 是指在不推迟整个工程完成的前提下，k能够发生的最迟时间vl(k) 计算vl()值时，按从后往前的顺序进行，可以在逆拓扑序列基础上计算 3.活动ai最早开始的时间e(i) 4.活动ai最迟开始时间l(i) 5.一个活动ai最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i) 它是指该活动完成时间的时间余量，说白了就是ai可以拖延多久。若d(i)=0则i为关键活动 网中的关键路径并不唯一，且对于有几条关键路径的网，值提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快包含在所有关键路径上的关键互动才能达到缩短工期的目的
          • 求解的vl(k)的理解：ve(k)是从源点到汇点最勤奋的走法；vl(k)是从汇点到源点走，选出距离汇点最近的走法(也就是正着走最懒的走法，能拖就拖)
• 7查找
  • 查找的基本概念
    • 查找：在数据集合中寻找满足某种条件的数据元素的过程 查找表(查找结构)：用于查找的数据集合；对查找表常用的操作有四种 1.查询某个特定的数据元素是否在查找表中 2.检索满足条件的某个特定的数据元素 3.在查找表中插入一个数据元素 4.从查找表中删除某个数据元素 静态查找表：只涉及上述一二两个步骤的查找表，无需动态修改查找表(顺序查找，折半查找，散列查找等)；动态查找表(二叉排序树的查找，散列查找等) 关键字：数据元素中唯一标识该元素的某个数据项的值 平均查找长度：查找过程中，一次查找的长度是指需要比较的关键字次数，平均查找长度则是所有查找过程中进行关键字比较次数的平均值
      • 练习求查找成功与失败时的ASL
  • 顺序查找和折半查找
    • 顺序查找 又称线性查找，对顺序表和链表都适用。优点：对数据元素存储没有要求，对有序性也没有要求；缺点：n较大时，效率低
      • 一般线性表的顺序查找 typedef struct{//查找表的数据结构 ElemType *elem;//元素存储空间基址 int TableLen;//表的长度 }SSTable; int Search_Seq(SSTable ST,ElemType key){ ST.elem[0] = key;//哨兵 for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找 return i; } 上述算法中，将ST.elem[0]称为哨兵，目的是使得Search_Seq内部循环不必判断数组是否会越界，因为满足i==0时循环一定会跳出。引入哨兵可以避免很多不必要的判断语句，从而提高程序效率
      • 有序表的顺序查找 若在查找之前就已经知道表时关键字有序的，那么比较失败后就不用再比较到表的另一端就能返回查找失败，从而降低查找失败的平均查找长度 可以用判定树来描述有序线性表的查找过程，圆形节点表示有序线性表中存在的元素；矩形结点为失败节点(自己虚构的空结点)；若有n个结点，则相应地有n+1个查找失败的结点 查找失败的平均查找长度(ASL)为(1+2+..+n+n)/(n+1);查找到每一个'失败节点'的概率为1/n+1
        • 顺序查找的无序与有序的差别仅在于查找失败时的区别
      • ASL成功=(n+1)/2
    • 折半查找(二分查找) 仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列 时间为O(log2n)
      • int Binary_Search(SeqList L,ElemType key){ int low=0,high=L.TableLen-1,mid; while(low<=high){ mid = (low+high)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]<key){ low = mid+1; // mid = (low+high)/2; } else{ high = mid-1; // mid = (low+high)/2; } } return -1; }
    • 分块查找(索引顺序查找) 它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适用于快速查找； 分块查找的基本思想：将查找表分为若干子块。块内元素可以无序，但块之间是有序的(第一组中最大关键字小于第二块中所有关键字，以此类推)；再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址；索引表按关键字有序排列。 分块查找的过程：1.在索引表中确定待查记录所在的块(顺序或折半查找)2.块内顺序查找 分块查找平均查找长度：索引查找和块内查找的平均长度之和
  • B树和B+树
    • B树(多路平衡查找树) (BST改进版) B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示 一棵m阶B树或为空树，或满足以下特性： 1.树中每个节点至多有m棵子树，即至多含有m-1个关键字 2.若根节点不是终端结点，则至少有两棵子树 3.除根节点外的所有非叶结点至少有m/2取上界棵子树，即至少含有m/2取上界-1个关键字 4.所有非叶结点结构如下(n,P0,K1,P1,K2,P2,...,Kn,Pn) Ki为关键字，且满足K1<K2<..<Kn;Pi为指向子树根节点的指针，Pi指针指向的子树中所有结点都大于Ki，小于Ki+1；n为节点中关键字的个数 5.所有叶结点出现在同一层次上，并且不带信息，实际上不存在，指向这些节点的指针为空
      • B树的高度 B树中大部分操作所需磁盘存取次数与B树高度成正比 树中每结点最多有m棵子树，m-1个关键字，关键字个数应满足n≤m^h-1； 第h+1层至少有2(m/2取上界)^(h-1)个结点，h+1层为不含任何信息的叶结点； 对于关键字个数为n的B树，叶结点查找不成功的结点为n+1，由此n+1>=2(m/2取上界)^(h-1)，即h≤log(m/2取上界)((n+1)/2 + 1)
      • B树的查找 1.B树中找结点 2.结点内找关键字 1.的查找操作在磁盘中进行，2.的查找操作在内存中进行； 找到目标结点后，将其读入内存，然后再结点内采用顺序查找法或折半查找法
      • B树的插入 不能找到位置后直接插入，会破坏B树定义中的要求 1.定位：查找到最底层中的非叶节点(查到叶结点，取上一层非叶节点) 2.插入：每个非失败结点关键字个数都在区间[m/2取上界-1,m-1]内，可以直接插入； 当插入后的结点关键字个数大于m-1时，对结点进行分裂。 分裂的方法：从中间位置m/2取上界将关键字分为两部分，左边部分包含在原结点中，右边部分放在新结点中；中间位置(m/2取上界)的结点插入原结点的父级节点；以此类推
      • B树的删除 当被删除关键字k不在终端结点(最底层非叶结点)时，可以用k的前驱(后继)k'来代替k，然后在相应的结点中删除k'，转换成了关键字在终端结点中的情形； 当被删关键字在终端结点(最底层非叶节点)时，有三种情况： 1.直接删除关键字：关键字个数 ≥ m/2取上界-1 2.兄弟够借：关键字个数=m/2取上界-1，其左右(相邻)兄弟关键字个数大于等于m/2取上界，则其兄弟，父，其自身，使用父子换位法，达到平衡 3.兄弟不够借：被删除的关键字个数=m/2取上界-1，此时其左右(相邻)兄弟的结点也都＝m/2取上界+1，则将关键字删除后与左(右)兄弟结点以及双亲结点中的关键字进行合并，双亲结点的关键字个数减一，双亲为根节点的关键字可以直接减少到0(删除根节点)，新结点称为根。
      • B树相关性质 要拿捏好关键字个数与子树个数的关系：关键字个数比子树个数少1 除根节点外所有非终端节点至少有m/2取上界棵子树(m/2取上界-1个关键字) 结点中关键字从左到右递增有序. 即m/2取上界-1≤n≤m-1，即[m/2取上界-1，m-1]
    • B+树
      • B+树是应数据库所需而出现的一种B树的变形树 一棵m阶B+树满足如下条件： 1.每个分支节点最多有m棵子树 2.非叶根结点至少有两棵子树 3.节点的子树个数与关键字个数相等 4.所有叶结点包含全部关键字及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互连接起来。
      • 与B树的主要差异： 1.B+树具有n个关键字的结点有n棵子树，每个关键字对应一棵子树；B树中n个关键字结点含有n-1棵子树。 2.B+树中每个结点关键字个数n的范围为[m/2取上界,m](相对于B树中结点关键字个数n上下限加1)；根节点B+：[1，m]，B：[1,m-1] 3.B+树中，叶子结点包含信息(全部关键字)，非叶结点仅起索引作用 4.B+树每次查找，无论成功与否，都是一条从根结点到叶结点的路径
  • 散列表
    • 散列表的基本概念
      • 由于之前的线性表和树的查找中，记录在表中的位置与记录的关键字之间不存在确定关系。因此，在这些表中查找记录时需要对一系列的关键字进行比较，这种查找方法是建立在比较之上的，查找的效率取决于比较的次数。 散列函数：将查找表中的关键字映射成该关键字对应的地址的函数Hash(key)=Addr，即将关键字自身的特性利用起来，尽可能少的利用‘‘比较‘查找。 散列函数可能会把多个不同关键字映射到同一地址，称为‘冲突‘，这些发生碰撞的不同关键字称为同义词。一方面设计的好的散列函数会尽量减少冲突；另一方面，冲突不可避免，要设计处理冲突的方法。 散列表：根据关键字而直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。 理想情况下，对散列表进行查找的时间复杂度为O(1)，即与元素个数无关
    • 散列函数的构造方法
      • 1.散列函数的定义域必须包含全部的存储关键字，而值域依赖于散列表的大小或地址范围、 2.散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生 3.散列函数应尽量简单，能在较短时间内计算出任意关键字对应的散列
        • 1.直接定址法 直接取关键字的某个线性函数值为散列地址。 H( key)＝key或H(key)＝ax key+b 符合关键字分布基本连续的情况；若关键字分布不连续，空位较多，则会造成存储空间的浪费
    • 冲突处理方法
    • 散列查找及性能分析
• 8排序
  • 排序基本概念
    • 算法的稳定性：待排序表中有两个元素Ri和Rj，其对应关键字相同keyi=keyj，若使用某一排序算法后，Ri与Rj相对位置不变，则此排序算法稳定，否则不稳定；稳定性并不能反映算法的优劣，只是对算法性质的描述。 根据排序过程中，数据元素是否完全在内存中，可将排序算法分为两类： 1.内部排序：排序期间，元素全部存放在内存中排序 2.外部排序：排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动。 一般情况下，内部排序都需要比较与移动，但并非所有内部排序都需要比较，如基数排序
  • 插入排序 每次将一个待排序的记录按关键字大小插入前面已拍好的子序列
    • 直接插入排序
      • 有序序列L[1..i-1]L(i)无序序列L[i+1…n] void InsertSort(ELemType A[],int n){ int i,j; for(i=2;i<=n;i++){//将后面n-1个数插入到前面 if(A[i]<A[i-1]){ A[0] = A[i];//复制为哨兵，A[0]不存放任何元素 for(j=i-1;A[0]<A[j];j--){//从后往前找待插入位置 A[j+1] = A[j]; A[j+1] = A[0]; } } 空间复杂度O(1),空间复杂度O(n^2) 最好情况：表中元素已经有序 时间O(n) 最坏情况：表中元素顺序相反 时间O(n^2) 由于每次比较都是从后往前，所以是稳定的 适用于顺序表、链表(可以从前往后查找指定元素位置) 适用于基本有序、数据量不大的排序表
    • 折半插入排序
      • void InsertSort(ElemType A[],int n){ int i,j,low,high,mid; for(i=2;i<=n;i++){ A[0] =A[i]; low=1;high=i-1; while(low<=high){ mid = (low+high)/2; if(A[mid]>A[0])high=mid-1; else low=mid+1; } for(j=i-1;j>=high+1;j--) A[j+1] = A[j]; A[high+1]=A[0]; } } 时间复杂度O(n^2) 比较次数与待排序表的初始状态无关，仅取决于表中元素个数n； 移动次数与待排序表初始状态有关
    • 希尔排序
      • 先将排序表分割成若干子表(把相隔相同增量的记录组成一个子表di+1=di/2，并且最后一个增量等于1)，对各个子表分别进行直接插入排序，当整个表中的元素已经基本有序时，对全体记录进行一次直接插入排序。 void ShellSort(ELemType A[],int n){ //A[0]是暂存单元，不是哨兵,j<=0时，到达插入位置 for(dk=n/2;dk>=1;dk/=2)//步长变化 for(i=di+1;i<=n;i++) if(A[i]<A[i-dk]){//需将A[i]插入有序增量子表 A[0]=A[j];//暂存在A[0] for(j=i-dk;j>0&&A[0]<A[j];j-=dk) A[j+dk]=A[j]; } } 时间复杂度尚无确切定论，认为O(n^2) 为不稳定排序 适用于顺序表
  • 交换排序 根据关键字的比较结果来对换这两个记录在序列中的位置
    • 冒泡排序
      • 从后往前(从前往后)两两比较相邻元素的值，若为逆序则交换它们。关键字像气泡一般逐渐漂浮到水面 void BubbleSort(ELemType A[],int n){ for(int i=0;i<n-1;i++){//n-1趟 flag = false; for(j=n-1;j>i;j--) if(A[j-1]>A[j]){//若为逆序 swap(A[j-1],A[j]); flag = true; } if(flag==false)//冒泡排序结束的标志:一次交换也没有 return; } } 空间O(1),时间O(n^2) 稳定性：元素相等时不会交换，稳定 冒泡排序产生的序列是全局有序的，不等同于插入排序的局部有序
    • 快速排序 基于分治思想
      • 在待排序表中任取一个元素作为pivot(通常取首元素)，通过一趟排序将带排序序列划分为独立的两部分L[1..k-1] L(k) L[k+1,...n]，使得前一半皆小于pivot，后一半皆大于pivot，pivot放在了最终位置L(k)上，这个过程称为一趟快速排序(一趟划分) void QuickSort(ELemType A[],int low,int high){ if(low<high){//递归跳出的条件 int pivotpos = Partition(A,low,high);//划分 QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos+1,high); } } 快速排序算法的性能与关键自于划分操作，划分操作有很多版本，这里以首部元素作为pivot枢轴进行划分 int Partition(ElemType A[],int low,int high){ ElemType pivot=A[low]; while(low<high){//循环跳出条件 while(low<high && A[high]>=pivot) --high; A[low]=A[high]; whilie(low<high && A[low]<=pivot) ++low; A[high] = A[low]; } A[low] = pivot; return low; } 空间：需要递归工作栈,最好O(log2n),平均O(log2n)(尽可能对半劈开,像完全二叉树), 最坏O(n)(划分的两个区域元素个数为n-1与0，需要n-1次递归调用，需要栈深度为O(n))。 时间：快排运行时间与划分是否对称有关，最坏情况也是一半n-1个一半0个，最大限度的不对称性发生在每层递归上，即对应于初始有序序列(顺序or逆序)，为O(n^2) 稳定性：不稳定，会将相同元素调换到不同部分，改变相对位置 注意：快排中并不产生有序子序列，只是每趟会将pivot元素放到最终位置上 提高效率：1.选取尽量能将序列中分的枢轴元素2.随机选取枢轴元素 最理想的划分：两个字问题都小于n/2，时间为O(nlog2n),且快速排序平均情况下与最佳情况的运行时间很接近。 快速排序是所有内部排序算法中平均性能最优的排序算法。
  • 选择排序 每一趟选取原始序列中关键字最小元素作为有序子序列的第i个元素，直到n-1趟
    • 简单选择排序
      • void SelectSort(ElemType A[],int n){ for(i=0;i<n-1;i++)//一共进行n-1趟 min=i;//记录最小元素位置 for(j=i+1;j<n;j++) if(A[j]<A[min]) min = j; if(min!=i) swap(A[i],A[min]); } } 空间O(1),时间O(n^2) 稳定性：可能会导致含有相同元素关键字的相对位置发生改变，不稳定。
    • 堆排序
      • 堆是一棵树的数组对象，可将一维数组看成一棵完全二叉树，满足性质 1.L(i)>=L(2i)且L(i)>=L(2i+1)或2.L(i)<=L(2i)且L(i)<=L(2i+1) (1<=i<=n/2取下界); 满足1.的视为大根堆(大顶堆)，满足2.的视为小根堆(小顶堆)。 堆排序：首先将数组中n个元素建成初始堆；输出堆顶元素后，将堆底元素送入堆顶，此时根节点已不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质。再输出塔顶元素，如此重复，直到堆中仅剩一个元素为止。 堆排序算法： void HeapSort(ElemType A[],int len){ BuildMaxHeap(A,len); for(i=len;i>1;i--){ Swap(A[i],A[1]);//输出堆顶元素，和堆底元素交换 HeadAdjust(A,1,i-1);//把剩余i-1个元素整理成堆 } } 堆排序适合关键字较多的情况(上亿量级) 例子：一亿个数中选出前100个最大值，首先使用一个100的数组，读取前100个数，构建成小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆。数据读取完毕后，堆中的100个数即为所求。 空间效率O(1),时间效率O(nlog2n) 不稳定
        • 1.如何使无序序列构造成初始堆 对第(n/2取下界)个结点为根的子树进行筛选(若为大根堆，则比较根结点关键字与其左右子树关键字大小，若不符合大根堆规则则交换)，使该子树成为堆。之后向前依次对各结点(n/2取下界-1,1)为根的子树进行筛选。 看作完全二叉树时，从下往上逐步调整根节点(根节点与子结点交换关键字)；数组中为从右往左调整根节点(交换关键字) void BuildMaxHeap(ElemType A[],int len){ for(int i=len/2;i>0;i--)//从i=n/2到1，反复调整堆 HeadAdjust(A,i,len); } void HeadAdjust(ElemType A[],int k,int len){ //HeadAdjust将元素k为根的子树进行调整 A[0]=A[k]; for(i=2*k;i<=len;i*=2){//沿key较大的子节点向下筛选 if(i<len && A[i]<A[i+1]) i++;//取key较大的子节点的下标 if(A[0]>=A[i]) break;//筛选结束 else{ A[k] = A[i];//将A[i]调整到双亲结点上 k=i;//修改k值以便继续向下筛选 } } A[k]=A[0]; } 调整时间与树高有关，O(h),时间复杂度O(n),可以在线性时间内将一个无序数组建堆
        • 2.输出堆顶元素后，如何将剩余元素调整成新的堆 输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。 从上到下筛选(交换根节点关键字与子树关键字)
        • 堆的插入 插入尾部，从下向上调整
  • 归并排序和基数排序
    • 归并排序 归并的含义是将两个或两个以上的有序表组合成一个新的有序表
      • 假设待排序表含有n个记录，则可将其视为n个有序的子表，每个子表长度为1，然后两两归并，得到n/2取上界个长度为2或1的有序表；继续两两归并，直到合并成一个长度为n的有序表，此种方法称为2路归并排序 ElemType *B=(ElemType*)malloc((n+1)*sizeof(ElemType));//辅助数组B void Merge(ElemType A[],int low,int mid,int high){ //表A[low..mid]A[mid+1..high]各自有序，将他们合并成一个有序表 for(int k=low;k<=high;k++) B[k]=A[k]; for(i=low;j=mid+1;k=i,i<=mid&&j<=high;k++){ if(B[i]<=B[j]) A[k]=B[i++]; else A[k]=B[j++]; } while(i<=mid) A[k++]=B[i++]; while(j<=high) A[k++]=B[j++]; } void MergeSort(ELemType A[],int low,int high){ if(low<high){ int mid=(low+high)/2; MergeSort(A,low,mid); MergeSort(A,mid+1,high); Merge(A,low,mid,high); } } 空间效率：辅助空间n个单元，空间复杂度O(n) 时间效率：每趟归并O(n),需进行log2n取上界趟归并，算法时间复杂度为O(nlog2n) 稳定性：Merge()操作不会改变相同关键字记录相对次序，稳定
        • 一般而言，对N个元素进行k路归并，排序的趟数m满足k^m=N，从而m=logkN,又因m为整数，所以m=logkN取上界
    • 基数排序 借助多关键字排序的思想对单逻辑关键字进行排序
      • 基于关键字的各位大小排序。每个结点aj的关键字由d元组组成，kd-1j为主位关键字，kj0为次位关键字。为实现多关键字排序，通常有两种方法： 1.最高位优先(MSD)，按关键字权重递减依次逐层划分若干更小的子序列，最后所有子序列依次连接成一个有序序列。 2.最低位优先(LSD),按关键字权重递增依次排序，形成一个有序序列。 操作： 1.分配：把Q0...Qr-1队列置空，然后依据每个结点相应位，使之加入相应队列 2.收集：把Q0..Qr-1各队列结点依次首尾相接，得到新的节点序列，从而组成新线性表 例子：排序1000以下序列，先确定基数r(可以看作r进制),1000的基数为10，所以在排序过程中需要借助10个链队列。1000以下数字为三位，所以需要进行3趟“分配”和“收集”操作；将所有最低位子关键字(个位)相等的记录分配到一个队列，然后进行“收集”操作。 空间效率：一趟排序需要的辅助存储空间为r(r个队列：r个队头指针，r个队尾指针)，O(r) 时间效率：d趟分配和收集，一趟分配需要O(n),一趟收集需要O(r),时间复杂度O(d(n+r)),与序列初始状态无关。 稳定性：基数排序本身就要求，按位排序必须是稳定的，所以稳定！
  • 各种内部排序算法的比较及应用
    • 内部排序算法的比较
    • 内部排序算法的应用
      • 1.若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。 2.若文件初始状态已按关键字基本有序，用直接插入或冒泡排序为宜 3.若n较大，则使用O(nlog2n)的排序方法：快速排序，堆排序或归并排序。 快速排序被认为是目前基于比较的内部排序中最好的方法，当待排序的关键字随机分布时，快速排序平均时间最短，堆排序所需辅助空间少于快速排序，并且不会出现快速排序的最坏情况。但两种排序都不稳定。若要求使用稳定的O(nlog2n)算法，则使用归并排序，但不提倡从单个记录起两两归并，通常可以将它们和直接插入排序结合使用：先利用直接插入排序求得较长有序子文件，然后两两归并。直接插入排序是稳定的，改进后的归并排序也是稳定的 4.在基于比较的排序方法中，每次比较两个关键字大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较的判定过程，由此可证明：当文件n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog2n)时间。 5.若n很大，记录的关键字位数较少且可以分解，采用基数排序较好 6.当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构
  • 外部排序
    • 外部排序算法的基本概念
      • 在内存中进行的排序叫内部排序。而在许多应用中，需要对大文件进行排序，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，排序过程中需要多次进行内存外存之间交换。这种排序称为外部排序
    • 外部排序方法
      • 外部排序过程过程中时间代价主要考虑访问磁盘的次数，即IO次数 外部排序通常采用归并排序法： 1.根据内存缓冲区大小，将外存上文件分成长度为l的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串； 2.对这些归并段进行逐趟归并，使归并段逐渐由小到大，直到得到整个有序文件为止 一趟归并，指的是将当前同等层级的所有段全部归并一便 外部排序总时间=内部排序所需时间+外部信息读写时间+内部归并所需的时间 外存信息读写时间远大于内部排序和内部归并时间，外存信息读写是以“磁盘块”为单位的，一趟归并需要进行总记录数/一个磁盘块的记录数次读与写，所以总共需要进行读写次数：2*总记录数/一个磁盘块的记录数 * n(趟数) + 总记录数/一个磁盘块的记录数(内部排序还需要进行一次全部的读写) 对r个初始归并段，做k路平衡归并，树(倒立的k叉树)的高度=logkr取上界=归并趟数S 可见，增大归并路数k，或减少初始归并段个数r，都能减少归并趟数S，进而减少磁盘I/O次数，提高外部排序速度
    • 多路平衡归并与败者树
      • 增大归并路数k能减少归并趟数S，但会使内部归并时间增加。内部归并时，k个元素选择最小关键字需要比较k-1次，需要比较n-1个关键字，每趟归并n个元素需要做(n-1)(k-1)次比较，S趟归并总共需要比较次数为 S(n-1)(k-1)=log2r取上界(n-1)(k-1)/log2k取上界，式中(k-1)/log2k取上界随k增长而增长。因此不能使用普通的内部归并排序算法。
        • 为使内部归并不受k增大的影响，引入了败者树，败者树是树形排序的一种变体，可视为一棵完全二叉树。k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录，内部节点用来记录左右节点的“失败者”，而让胜者继续往上比较，一直到根节点。根节点为胜者。 S(n-1)log2k取上界=log2k取上界(n-1)log2k取上界=(n-1)log2r取上界 使用败者树后，内部归并排序比较次序与k无关了，但归并路数k受内存空间的制约，可能会在一定的空间下减少缓冲区的容量。k值过大，虽归并趟数会减少，但IO次数仍会增加。 ps:与胜者树比较，胜者树重构时需要与兄弟节点比较，再更改双亲结点；败者树重构时只需要一路向上走双亲结点比较就可以了。
    • 置换-选择排序(生成初始归并段)
      • 为减小r,r=n/l取上界，所以要想办法产生更长的初始归并段l。 设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO与WA初始为空，WA可容纳w个记录。置换-选择算法步骤如下 1.从FI中输入w个记录到工作区WA 2.从WA中选出关键字最小值的记录，记为MINIMAX 3.将MINIMAX记录到FO 4.若FI不空，则从FI输出下一个记录到WA 5.从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录 6.重复3-5步，直至WA中选不出新的MINIMAX为止，得到一个初始归并段，输出一个归并段的结束标志到FO中去 7.重复2-6步，直至WA空，得到全部初始归并段 WA中选择MINIMAX记录过程需用败者树来实现
    • 最佳归并树
      • 文件经过置换-选择排序后，得到的是长度不等的初始归并段。如何组织长度不等的初始归并段的归并顺序，使IO次数最少？ 画出相应的归并树，树的带权路径长度WPL为递归过程中的总读取记录数。 将哈夫曼树的思想推广到k叉树的情形，在归并树中，让记录数少的初始归并段最先归并，让记录数多的初始归并段最晚归并，就可以建立总IO次数最少的最佳归并树。 构建最佳归并树方法：若初始归并段并不足以构成一棵严格k叉树时，需添加长度为0的“虚段”。如何判定添加虚段的数目？ 严格k叉树有n0=(k-1)nk+1。 若(n0-1)%(k-1)=0，则正好可以构造k叉归并书，内节点有nk个 若(n0-1)%(k-1)=u!=0，则再加上k-u-1个空归并段，就可以建立归并树
• AOV网与AOE网都是DAG，两者的边与顶点代表的意义不同， AOV网中边无权值，仅代表顶点之间的前后关系；AOE网中的边有权值，表示完成该活动的开销
• Dijkstra与Prim的区别：Prim的最小生成树中所有边之和一定是最小的，只有相邻节点的权值；Dijkstra的MST(单元点最短路径树)中两点间距离并不一定比原始图AB短，因为加入了到源点的距离；两者区别就在松弛操作上。 另外Prim只能用于无向图，Dijkstra可以有\无向图(无向图转化为有向图，ij双边)
• 邻接矩阵的遍历是唯一的，邻接表的遍历是不唯一的
• 无向图中讨论连通性，有向图中讨论强连通性