数据结构考试必须要掌握的重点知识

思维导图：

1 线性表的合并（编程题）

1.1 有序表的合并

算法步骤：

1. 创建表长为m+n的空表LC。
2. 指针pc初始化，指向LC的第一个元素。
3. 指针pa和pb初始化，分别指向LA和LB的第一个元素。
4. 当指针pa和pb均为到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中摘取元素值较小的结点插入到LC的最后。
5. 如果pb已到达LB的表尾，依次将LA的剩余元素查到LC的最后。
6. 如果pa已到达LA的表尾，依次将LB的剩余元素查到LC的最后。

算法代码：

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
	LC.length = LA.length+LB.length;  // 新表长度为两表长度之和
	LC.elem = new ElemType[LC.length];  // 为合并后的新表分配空间
	pc = LC.elem;  // 指针pc新表的第一个元素
	pa = LA.elem;  // 指针pa和pb的初值分别指向两个表的第一个元素
	pb = LB.elem;
	pa_last = LA.elem+LA.length-1;  // 指针pa_last 指向LA的最后一个元素
	pb_last = LB.elem+LB.length-1;  // 指针pb_last 指向LB的最后一个元素
	while((pa<=pa_last)&&(pb<=pb_last){  // LA和LB均未达到表尾
		if(*pa<=*pb){
			*pc++ = *pa++;  // 依次摘取两表中值较小的结点插入到LC的最后
		}else{
			*pc++ = *pb++;
		}
	}
	while(pa<=pa_last){  // LB到达表尾
		*pc++ = *pa++;
	}
	while(pb<=pb_last){  // LA到达表尾
		*pc++ = *pb++;
	}
}

1.2 链表的合并

算法步骤:

1. 指针pa和pb初始化，分别指向LA和LB的第一个结点
2. LC的结点取值为LA的头结点
3. 指针pc初始化，指向LC的头结点
4. 当指针pa和pb均未到达相应表尾，则依次比较pa和pb所指向的元素值，从LA或LB中摘取元素值较小的结点插入到LC的最后
5. 将非空表的剩余段插入到pc所指结点后。
6. 释放LB的头结点。

算法代码：

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC){
	pa = LA->next;  pb=LA->next;  // pa和pb的初值分别指向两个表的第一个结点
	LC=LA;  // 用LA的头结点作为LC的头结点
	pc=LC;  // pc的初值指向LC的头结点
	while(pa&&pb){
		if(pa->data<=pb->data){
			pc->next = pa;	// 将pa所指结点链接到pc所指结点之后
			pc=pa;  // pc指向pa
			pa = pa->next;  // pa指向下一结点
		}else{
			pc->next = pb;  // 将pb所指结点链接到pc所指结点之后
			pc = pb;  // pc指向pb
			pb = pb->next;  // pb指向下一结点
		}
	}
	pc->next = pa?pa:pb;  // 将非空表的剩余段插入到pc所示结点之后
	delete LB;  // 释放LB的头结点
}

2 栈和队列

2.1 栈的基本操作

栈：限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又被称为后进先出(Last In First Out)的线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。

栈的删除操作，叫做出栈，有的也叫作弹栈。

2.1.1 入栈、进栈

单栈栈空条件：S->top==-1

单栈栈满条件：S->top==MAXSIZE-1

对于栈的插入，即进栈操作，其实就是做了如下处理：

Status Push(SqStack *S.SElemType e){
    if(S -> top == MAXSIZE -1){ // 栈满
        return ERROR;
    }
    S->top++; // 栈顶指针加一
    S->data[S->top] = e;  // 将新插入元素复制给栈顶空间
    return OK;
}

出栈操作pop，代码如下：

Status Pop(SqStack *S,SElemType *e){
    if(S->top==-1){ // 栈为空
        return ERROR;
    }
    *e = S->data[S->top];  // 将要删除的栈顶元素复制给e
    S->top--;  // 栈顶指针减一
    return OK;
}

2.1.2 共享栈(重要)

栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万—不够用了，就需要用编程手段来扩展数组的容量，非常麻烦。

共享栈就可以很好的解决这个问题。如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第—个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲，我们完全可以用—个数组来存储两个栈，充分利用这个数组占用的内存空间。

设置数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另—个栈为数组的末端，即下标为数组长度n-1处。这样两个栈如果增加元素，就是两端点向中间延伸。

栈空条件：S->top=-1或top[i]=bot[i]

栈满条件：S->top1+1=S->top2

2.1.2.1 共享栈进栈

对于共享栈的push方法，除了要插入元素值参数外，还需要有一个参数判断是栈1还是栈2的栈号参数StackNumber。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
    if(S->top1+1=S->top2){  // 栈满
        return ERROR;
    }
    if(stackNumber==1){ // 栈1元素进栈
        S->data[++S->top1]=e; // 若是栈1则先top1+1后给数组元素赋值
    }else if(stackNumber==2){ // 栈2元素进栈
        S->data[--S->top2]=e;  // 若是栈2则先top2-1后给数组元素赋值
    }
}

2.1.2.2 共享栈出栈

对于共享栈的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

Status Pop(SqDoubleStack *S,SElemType *e.int stackNumber){
    if(stackNumber==1){
        if(S->top1==-1){  // 栈1是空栈
            return ERROR;
        }
        *e = S->data[S->top--];  // 将栈1的栈顶元素出栈
    }else if(stackNumber==2){
        if(S->top2==MAXSIZE){  // 栈2是空栈
            return ERROR;
        }
        *e = S->data[S->top2++] // 将栈2的栈顶元素出栈
    }
}

2.2 表达式求值——中缀表达式转后缀表达式(编程题)

本内容分成两块：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

2.2.1 中缀表达式转后缀表达式

中缀表达式“9＋(3+1)×3＋10÷2”转化为后缀表达式“9 3 1 - 3＊＋10 2 ／ ＋”

方法：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的—部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

思路：

1. 初始化一空栈，用来对符号进出栈使用。

   

2. 第—个字符是数字9，输出9，后面是符号‘‘＋’’ ，进栈。

   

3. 第三个字符是”（ “ ，依然是符号，因其只是左括号，还未配对，故进栈。

   

4. 第四个字符是数字3，输出，总表达式为9 3，接着是“-”，进栈。

   

5. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“）” ，此时，我们需要去匹配此
   前的“（ ”，所以栈顶依次出栈，并输出，直到“（ ”出栈为止。此时左括号上方只有“-’’，因
   此输出“-”。总的输出表达式为9 3 1 -。

   

6. 紧接着是符号”ד，因为此时的栈顶符号为“+”，优先级低于“×”， 因此不输出，“*”进栈。接着是数字3，输出，总的表达式为9 3 1 - 3。

   

7. 之后是符号“＋”，此时当前栈元素“*”，比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”更低的优先级，所以全部出栈），总输出表达式为9 3 1 - 3 * +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“＋”是指中缀表达式中开头的9后面那个‘‘＋” ，而左图中的栈底（也是栈顶）的“＋”是指“9＋（3-1）×3＋”中的最后—个“＋”。

   

8. 紧接着数字10，输出，总表达式变为9 3 1 - 3 * + 10 2。后是符号“÷“，所以“／”进栈。

   

9. 最后一个数字2，输出，总的表达式为9 3 1 - 3 ＊＋10 2。

   

10. 因为巳经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 ＊＋10 2 / +。

    

2.2.2 后缀表达式计算

后缀表达式：9 3 1 - 3＊＋10 2 ／ ＋

1. 初始化空栈，此栈用来对要运算的数字进出使用。

   

2. 后缀表达式前三个都是数字，所以9、3、1进栈，如图所示。

   

3. 接下来是“-”，所以将栈中的1出栈作为减数，3出栈被减数，并运算3-1得到2，再将2进栈，如图所示。

   

4. 接着是数字3进栈，如图所示。

   

5. 后面是“*”，也就意味着栈中的3和2出栈，2与3相乘得到6，并将6进栈。

   

6. 下面是‘‘＋” ，所以栈中6和9出栈，9与6相加，得到15，将15进栈。

   

7. 接着是10与2两数字进栈。

   

8. 接下来是符号‘‘／”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。

   

9. 最后—个是符号“＋”，所以15与5出栈，并相加，得到20，将20进栈 。

   

10. 结果是20出栈，栈变为空。

    

3 串、数组和广义表

3.1 KMP模式匹配算法

3.1.1 算法原理

假设主串S=“abcdefab”，我们要匹配的子串T=”abcdex“，如果用朴素模式匹配算法，前5个字母，两个串完全相等，直到第6个字母，”f“与“x”不等，如图所示。

接下来按照朴素模式匹配算法，应该是按照上图的步骤2、3、4、5、6，即主串S中当$i=2、3、4、5、6$时，首字符与子串T的首字符均不等。

仔细观察就会发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面串“bcdex”中任意一个字符都不相等。也就是说对于步骤1来说前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位字符相等。所以，在上图中，步骤2、3、4、5的判断都是多余的。

当我们知道T串中首字符“a”与T中后面的字符均不相等的前提下，T串后面的字符均不相等的前提下，T串的“a”与S串后面的“c”“d”“e”也都可以在步骤1之后就可以确定是不相等的，所以在朴素模式匹配算法中步骤2、3、4、5没有必要，只保留步骤1、6即可，如图所示。

保留步骤6中的判断是因为在步骤1中$T[6]\ne S[6]$，虽然我们已经知道了$T[1]\ne T[6]$，也不能断定$T[1]$一定不等于$S[6]$，因此只需要保留步骤6这一步。

对于在子串中有与首字符相等的字符，也是可以省略一部分不必要的判断步骤，如图所示，省略T串前两位“a”与“b”同S串中的4、5位置字符匹配操作。

在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的，而这种回溯其实是可以省略的，KMP模式匹配算法就是为了让这没必要的回溯不发生。

既然i值不回溯，也就是不可以变小，那要考虑的变化就是j值了，通过观察可以发现，提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不相同。也就是说，j值的变化与主串其实没什么关系，关键取决于T串的结构中是否有重复问题，j值的大小取决于当前字符的串的前后缀的相似度。

在需要查找字符串前，先对要查找的字符串做一个分析，这样可以大大减少我们查找的难度，提高查找的速度。

KMP算法：不回溯，从最长相等前后缀后面一个字符开始比较。

3.1.2 KMP算法字符串的前缀、后缀、最长相等前后缀

前缀：包含第一个字符，但不包含最后一个字符的子串。

后缀：包含最后一个字符，但不包含第一个字符的子串。

最长相等前后缀：前缀和后缀相等的最长子串。

例如字符串“abca”

• 前缀：{a,ab,abc}
• 后缀：{a,ca,bca}
• 最长相等前后缀：a

字符串“ababa”

• 前缀：{a,ba,aba,abab}
• 后缀：{a,ba,aba,baba}
• 最长相等前后缀：aba

3.1.3 next数组

当$S_i$和$T_j$发生失配时，i不回溯，下一趟让j指向最长相等前后缀的后一个位置，用数组将这一位置记录下来，即为next数组。

假设模式串T=“ababaaaba”，如图所示。

1. 当j=1时，第一位默认为0或-1，next[1]=0。

2. 当j=2时，next[2]=1。

3. 当j=3时，next[3]=1。

4. 当j=4时，j由1到j-1的串是“aba”，next[4]=2。

   前缀字符：{a,ab}

   后缀字符：{a,ba}

   最长相等前后缀：{a}

5. 当j=5时，j由1到j-1的串是“abab”，next[5]=3。

   前缀字符：{a,ab,aba}

   后缀字符：{b,ab,bab}

   最长相等前后缀：{ab}

6. 当j=6时，j由1到j-1的串是“ababa”，next[6]=4。

   前缀字符：{a,ab,aba,abab}

   后缀字符：{a,ba,aba,baba}

   最长相等前后缀：{aba}

7. 当j=7时，j由1到j-1的串是“ababaa”，next[7]=2。

   前缀字符：{a,ab,aba,abab,ababa}

   后缀字符：{a,aa,baa,abaa,babaa}

   最长相等前后缀：{a}

8. 当j=8时，j由1到j-1的串是“ababaaa”，next[8]=2。

   前缀字符：{a,ab,aba,abab,ababa,ababaa}

   后缀字符：{a,aa,aaa,baaa,abaaa,babaaa}

   最长相等前后缀：{a}

9. 当j=9时，j由1到j-1的串是“ababaaab”，next[9]=3。

   前缀字符：{a,ab,aba,abab,ababa,ababaa,ababaaa}

   后缀字符：{b,ab,aab,aaab,baaab,abaaab,babaaab}

   最长相等前后缀：{ab}

3.1.4 时间复杂度

$O(n+m)$

3.2 广义表

1. 取表头GetHead(LS)：取出的表头为非空广义表中的第一个元素，它可以是一个单原子，也可以是一个子表。
2. 取表尾GetTail(LS)：**取出的表尾为除去表头之外，由其他元素构成的表。**即表尾一定是一个广义表。

例如：

​ GetHead(B)=e GetTail(B)=()

​ GetHead(D)=A GetTail(D)=(B,C)，

由于B,C是广义表，则可继续分解得到：

​ GetHead(B,C)=B GetTail(B,C)=C

广义表()和(())不同，前者为空表，长度n=0；后者长度n=1，可继续分解得到其表头，表尾均为空表()。

4 树和二叉树

4.1 二叉树的存储结构

4.1.1 二叉树的顺序存储结构

​ **二叉树的顺序存储结构就是用一维数组存储二叉树的结点存储二叉树中的结点，并且结点的存储位置，**也就是数组的下标要体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

​ 一棵完全二叉树如图所示：

​ 将这棵二叉树存入数组中，相应的下标对应其同样的位置，如图所示。

​ 完全二叉树定义的严格用顺序结构也可以体现出二叉树的结构，对于一般的二叉树，虽然层序编号不能反映逻辑关系，但完全可以按完全二叉树的编号，把不存在的结点设置为“^”即可，如图所示。

​ 但是对于一种极端情况，一棵深度为k的右斜树，只有k个结点，却需要分配$2^k-1$个存储单元，对存储空间有着极大的浪费，如图所示。所以，顺序存储结构一般只用于完全二叉树。

4.1.2 二叉树的链式存储结构

​ **二叉树每个结点最多有两个孩子，所以为它涉及一个数据域和两个指针域，称这样的链表为二叉链表。**结点结构涉及如图所示。

​ 其中，data是数据域；lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

​ 二叉链表的结点结构定义代码如下：

typedef struct BiTNode{  // 结点结构
    TElemType data;   // 结点数据
    struct BiTNode *lchild,*rchild;  // 左右孩子指针
}BiTNode,*BiTree;

​ 结构示意图如图所示：

4.2 根据遍历构造二叉树

建议自己画两棵树试试

两个二叉树遍历的性质：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知前序和后序遍历，是不能确定一棵二叉树的。

4.3 相关算法实现(编程题)

4.3.1 二叉树的遍历

4.3.1.1 前序遍历算法

​ 二叉树的定义是使用递归的方式，实现遍历算法也可以采用递归，二叉树的前序遍历算法如下：

void PreOrderTraverse(BiTree T){
    if(T==NULL){  // 树为空
        return;
    }
    printf("%c",T-data);  // 对数据进行输出操作
    PreOrderTraverse(T->lchild);  // 先序遍历左子树
    PreOrderTraverse(T->rchild);  // 先序遍历右子树
}

4.3.1.2 中序遍历算法

二叉树的中序遍历算法和前序遍历算法仅仅是代码顺序上的差，实现代码如下：

// 初始条件：二叉树T存在
// 操作结果：中序递归遍历T，依次输出值
void InOrderTraverse(BiTree T){
    if(T==null){
        return;
    }
    InOrderTraverse(T->lchild);  // 中序遍历左子树
    printf("%c",T->data);  // 进行输出结点数据的操作
    InOrderTraverse(T->rchild);  // 中序遍历右子树
}

4.3.1.3 后序遍历算法

​ 后序遍历算法与前序、中序遍历算法类似，只是执行步骤有些差异，算法代码如下：

// 初始条件：二叉树T存在
// 操作结果：后续递归遍历T
void PostOrderTraverse(BiTree T){
    if(T==null){
        return;
    }
    PostOrderTraverse(T->lchild);  // 后序遍历左子树
    PostOrderTraverse(T->rchild);  // 后序遍历右子树
    print("%c",T->data);  // 进行结点数据输出操作
}

4.3.2二叉树统计结点个数

4.3.2.1 统计二叉树结点的个数

int NodeCount(BiTree T){
	if(T==null){
        return 0;
    }else{
        return NodeCount(T->lchild)+NodeCount(l->rchild)+1;
    }
}

4.3.2.2 统计二叉树叶节点个数

int NodeCount_Leaf(BiTree T){
    if(T==null){
        return 0;
    }else if(T>lchild==null&&T->rchild==null){
        return 1;
    }else {
        return NodeCount_Leaf(T->lchild)+NodeCount_Leaf(T->rchild);
    }
}

4.3.2.3 统计二叉树度为1的结点个数

int NodeCount_D1( BiTree T){
    if(T==NULL) {
        return 0;
    }
   if(T->lchild==NULL&&T->rchild!=NULL||T->rchild==NULL&&T->lchild!=NULL){   
    	return 1 + NodeCount_D1(T->lchild) + NodeCount_D1(T->rchild);
	}
	return NodeCount_D1(T->lchild)+NodeCount_D1(T->rchild);
}

4.3.2.4 统计二叉树度为2的结点个数

int NodeCount_D2(BiTree T){
    if(T==NULL) {
        return 0;
    }else if(T->lchild&&T->rchild){
        return NodeCount_D2(T->lchild)+NodeCount_D2(T->rchild)+1;
    }else{
        return NodeCount_D2(T->lchild)+NodeCount_D2(T->rchild);
    } 
}

4.3.3 二叉树的高度

/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
	int i,j;
	if(!T)
		return 0;
	if(T->lchild)
		i=BiTreeDepth(T->lchild);
	else
		i=0;
	if(T->rchild)
		j=BiTreeDepth(T->rchild);
	else
		j=0;
	return i>j?i+1:j+1;
}

5 图

5.1 最小生成树(编程题)

核心思想、Prim算法和Kruskal算法的区别：归并点和归并边

**构造连通网的最小代价生成树称为最小生成树（Mininum Cost Spanning Tree）。**找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。

5.1.1 普里姆(Prim)算法

我们先构造邻接矩阵，如图所示：

从$v_0$开始，$v_0$旁有两条边, 10与11比, 10更小一些些。所以选$v_0$至$v_1$的边为最小生成树的第—条边，如左下图所示。然后我们看$v_0$和$v_1$两个顶点的其他边，有11、16、12、18，这里面最小的是11，所以$v_0$到$v_5$的边为最小生成树的第二条边，如中下图所示。然后我们看$v_0$、$v_1$和$v_5$三个顶点的其他边，有18、12、16、17、26，这里面最小的是12，所以$v_1$到$v_8$的边为最小生成树的第三条边，如右下图所示。

类似的方法，我们可以得到下面的六张图：

Prim算法实现代码如下：

/* Prim算法生成最小生成树  */
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];		/* 保存相关顶点下标 */
	int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */
	lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */
			/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
	adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */
	for(i = 1; i < G.numVertexes; i++)	/* 循环除下标为0外的全部顶点 */
	{
		lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */
		adjvex[i] = 0;					/* 初始化都为v0的下标 */
	}
	for(i = 1; i < G.numVertexes; i++)
	{
		min = GRAPH_INFINITY;	/* 初始化最小权值为∞， */
						/* 通常设置为不可能的大数字如32767、65535等 */
		j = 1;k = 0;
		while(j < G.numVertexes)	/* 循环全部顶点 */
		{
			if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
			{	
				min = lowcost[j];	/* 则让当前权值成为最小值 */
				k = j;			/* 将当前最小值的下标存入k */
			}
			j++;
		}
		printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
		lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
		for(j = 1; j < G.numVertexes; j++)	/* 循环所有顶点 */
		{
			if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) 
			{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
				lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
				adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */
			}
		}
	}
}

5.1.2 克鲁斯卡尔(Kruskal)算法

普里姆算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。同样的思路’我们也可以直接就以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成，只不过构建时要考虑是否会形成环路而已。

我们将同样的图的邻接矩阵通过程序转化为右下图的边集数组，并旦对它们按权值从小到大排序。

克鲁斯卡尔算法的思想就是站在了上帝视角，先把权值最短的边—个个挑出来。左图找到了权值最短边$v_7$和$v_4$，中下图找到了权值第二短边$v_2$和$v_8$，右下图找到了权值第三短边$v_0$和$v_1$。

我们找到了大量的权值短边后’发现了—个问题。比如当完成到左下图的情况时，我们接下来去找权值最小的边应该是$v_6$和$v_5$，这条边的权值是17，但是这会带来一个结果, $v_6$和$v_5$已经通过中转的顶点$v_0$和$v_1$连通了，它们并不需要继续再关联否则就是重复。而$v_6$和$v_5$两个顶点更应该与顶点$v_3$、$v_7$和$v_4$进行连接。检查了它们的权值，22、21、24、19、26，最终选择了19作为最小的权值边。如右下图，完成最小生成树的构建。

克鲁斯卡尔算法实现代码如下：

/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
	while ( parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}

/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
	int i, j, n, m;
	int k = 0;
	int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
	
	Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */

	/* 用来构建边集数组并排序********************* */
	for ( i = 0; i < G.numVertexes-1; i++)
	{
		for (j = i + 1; j < G.numVertexes; j++)
		{
			if (G.arc[i][j]<GRAPH_INFINITY)
			{
				edges[k].begin = i;
				edges[k].end = j;
				edges[k].weight = G.arc[i][j];
				k++;
			}
		}
	}
	sort(edges, &G);
	/* ******************************************* */


	for (i = 0; i < G.numVertexes; i++)
		parent[i] = 0;	/* 初始化数组值为0 */

	printf("打印最小生成树：\n");
	for (i = 0; i < G.numEdges; i++)	/* 循环每一条边 */
	{
		n = Find(parent,edges[i].begin);
		m = Find(parent,edges[i].end);
		if (n != m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
		{
			parent[n] = m;	/* 将此边的结尾顶点放入下标为起点的parent中。 */
							/* 表示此顶点已经在生成树集合中 */
			printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
}

6 查找

6.1 顺序查找

顺序查找的算法实现如下：

/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if (a[i]==key)
			return i;
	}
	return 0;
}

这种算法在每次循环时都需要对i是否越界，即是否小于等于n作判断。优化此算法可以设置一个哨兵，可以解决不需要每次让i与n作比较。

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
	int i;
	a[0]=key;
	i=n;
	while(a[i]!=key)
	{
		i--;
	}
	return i;
}

此时代码是从尾部开始查找, 由于a[0]=key，也就是说，如果在a[j]中有key则返回值，查找成功。否则—定在最终的a[0]处等于key，此时返回的是0，即说明a[1]-a[n]中没有关键字key，查找失败。

6.2 折半查找（编程）

折半查找（Binary Search）技术，又称为二分查找。

它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续童找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

折半查找算法代码如下：

/* 折半查找 */
int Binary_Search(int *a,int n,int key)
{
	int low,high,mid;
	low=1;	/* 定义最低下标为记录首位 */
	high=n;	/* 定义最高下标为记录末位 */
	while(low<=high)
	{
		mid=(low+high)/2;	/* 折半 */
		if (key<a[mid])		/* 若查找值比中值小 */
			high=mid-1;		/* 最高下标调整到中位下标小一位 */
		else if (key>a[mid])/* 若查找值比中值大 */
			low=mid+1;		/* 最低下标调整到中位下标大一位 */
		else
		{
			return mid;		/* 若相等则说明mid即为查找到的位置 */
		}
		
	}
	return 0;
}

算法执行流程如下：

1. 假设我们传入的参数 a = { 0 , 1 , 16 , 24 , 35 , 47 , 59 , 62 , 73 , 88 , 99 } a=\{0,1,16,24,35,47,59,62,73,88,99\} a={0,1,16,24,35,47,59,62,73,88,99}，我们要查找的数值为62，初始化n=10，key=62，第3-5行，此时low=1，high=10，如图所示。

   

2. 第6-15行循环，进行查找。

3. 第8行，mid计算出得5，由于a[5]=47<key，所以执行第12行，low=5+1=6，如图所示。

   

4. 再次循环，mid=(6+10)/2=8，此时a[8]=73>key，所以执行第10行，high=8-1=7，如图所示。

   

5. 再次循环，mid=(6+7)/2=6，此时a[6]=59<key，所以执行第12行，low=6+1=7，如图所示。

   

6. 再次循环，mid=(7+7)/2=7，a[7]=62=key，查找成功，返回7。

折半查找时间复杂度：$O(lo{g}_{2}n)$

6.3 哈希查找

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系$f$，使得每个关键字key对应一个存储位置$f(key)$。

存储位置=f(关键字)

对应关系$f$称为散列函数，又称为哈希（Hash）函数。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。散列技术既是一种存储方法，也是一种查找方法。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这些情况为冲突，这些发生碰撞的不同关键字称为同义词。

6.3.1 散列函数构造方法

6.3.1.1 直接定址法

对于下图所示的0-100岁的人口数字统计表，对年龄这个关键字就可以直接用年龄的数字作为地址，此时f(key)=key。

如果我们要统计的是1980年后出生年份的人口数，如下图所示，我们对出生年份这个关键字可以用年份减去1980来作为地址。此时f(key)=key-1980。

直接去关键字的某个线性函数值为散列地址，散列函数为：

$$f(key)=a\times key+b(a、b为常数)$$

直接定址法的散列函数的优点是简单、均匀，也不会产生冲突，但是需要提前知道关键字的分布情况，适合查找表较小且连续的情况。

6.3.1.2 除留余数法

除留余数法是最常用的构造散列函数的方法，假设散列表表长为m，取一个不大于m但最接近或等于m的质数p，散列函数为：

$$f(key)=keymodp(p\le m)$$

假设我们有12个记录的关键字构造散列表时，就用了$f(key)=keymod12$的方法，比如$29mod12=5$，所以它存储在下标为5的位置。

根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。

6.3.2 处理散列冲突的方法

开放地址法

线性探测法

开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

公式是：

$$f_i(key)=(f(key)+d_i)MODm(d_i=1,2,3,\cdot \cdot \cdot ,m-1)$$

一个简单的案例，我们的关键字集合为 { 12 , 67 , 56 , 16 , 25 , 37 , 22 , 29 , 15 , 47 , 48 , 34 } \{12,67,56,16,25,37,22,29,15,47,48,34\} {12,67,56,16,25,37,22,29,15,47,48,34}，表长为12.我们用散列函数$f(key)=keymod12$。

当计算前5个数 { 12 , 67 , 56 , 16 , 25 } \{12,67,56,16,25\} {12,67,56,16,25}，都是没有冲突的散列地址，直接存入，如下图所示。

计算key=37时，发现$f(37)=1$，此时就与25所在的位置冲突，于是再次进行计算$f(37)=(f(37)+1)mod12=2$，于是将37存入下标为2的位置，如图所示。

到了key=48，我们计算得到$f(48)=0$，与12所在的0位置冲突了，继续计算$f(48)=(f(48)+1)mod12=1$，与25所在的位置冲突，于是一直到$f(48=(f(48)+6))\mathrm{mod}12=6$，才有空位，如图所示。

这种解决冲突的开放定址法称为线性探测法。

二次探测

当$d_i=0^2,1^2,(-1{)}^2,2^2,(-2{)}^2\cdot \cdot \cdot \cdot K^2,(-k{)}^2$时，称为二次探测法。增加平方运算的目的是为了不让关键字都聚集在某一块区域。

公式如下：

$$f_i(key)=(f(key)+d_i)MODm(d_i=1^2,(-1{)}^2,2^2,(-2{)}^2\cdot \cdot \cdot \cdot K^2,(-k{)}^2,k\le m/2)$$

伪随机探测

在冲突时，对于位移量 $d_i$采用随机函数计算得到，我们称为随机探测法。

7 排序

7.1 冒泡排序

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，指导没有反序的记录为止。

冒泡排序算法：,

void BubbliSort(SqList *L){
    int i,j;
    Status flag= TRUE;
    for (i=1;i<L->length && flag;i++){  // 如果flag发生数据交换，则退出循环
		flag = FALSE;
        for(j=L->length-1;j>=i;j--){  // j从后往前循环
            if(L->r[j]>L->r[j+1]){  // 若前者大于后者
                swap(L,j,j+1); // 交换L->r[j]与L->r[j+1]的值
        		flag = TRUE;  // 如果有数据交换，则flag为TRUE
            }
    }
}
    
/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp; 
}

算法步骤：

1. 设待排序的记录存在在数组r[1····n]中，首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序(L->r[j]>L->r[j+1])，则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直到第n-1个记录和第n个记录的关键字进行过比较为止，上述过程称为冒泡排序的第一个趟，其结果是使得关键字最大的记录被安置到最后一个记录的位置上。
2. 然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。
3. 重复上述比较和交换过程，第i趟是从L-r[1]到L->r[L->length-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这L->length-i+1个记录中关键字最大的记录被交换到第L->length-i+1的位置上。指导在某一趟排序过程中没有进行过交换记录的操作，说明序列已全部达到排序要求，则完成排序。

若待排序记录的关键字序列为{49,38,65,97,76,13,27,49}，请给出用冒泡排序法进行排序的过程。

时间复杂度：$\frac{n(n-1)}{2}$，总的时间复杂度$O(n^2)$

7.2 快速排序（重点掌握）

快速排序的基本思想是：:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另—部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序算法的实现：

/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{ 
	int pivotkey;

	pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
	while(low<high) /*  从表的两端交替地向中间扫描 */
	{ 
		 while(low<high&&L->r[high]>=pivotkey)
			high--;
		 swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
		 while(low<high&&L->r[low]<=pivotkey)
			low++;
		 swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
	}
	return low; /* 返回枢轴所在位置 */
}

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{ 
	int pivot;
	if(low<high)
	{
			pivot=Partition(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
			QSort(L,low,pivot-1);		/*  对低子表递归排序 */
			QSort(L,pivot+1,high);		/*  对高子表递归排序 */
	}
}

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{ 
	QSort(L,1,L->length);
}

Partiotion()函数要做的，就是先选取一个当中的一个关键字，想尽办法将它放到一个位置，使得左边的值都比它小，右边的值比它大，称这样的关键字称为枢轴(pivot)。

快速排序算法执行流程：

假设我们要排序的序列为{50,10,90,30,70,40,80,60,20}，执行流程如下：

1. 程序开始执行，此时low=1，high=L->length=9。第4行，我们将L.row[low]=L.r[1]=50赋值给枢轴变量pivotkey，如图所示。

   

2. 第5-13行为while循环，目前low=1<high=9，执行内部语句。

3. 第7行，L.r[high]=L.r[9]=20不大于pivitkey=50，因此不执行第8行。

4. 第9行，交换L.r[low]与L.r[high]的值，使得L.r[1]=20，L.r[9]=50，如图所示。

   

5. 第10行，当L.r[low]=L.r[1]=20, pivotkey＝50，L.r[low]＜pivotkey，因此第11行，low++,此时low＝2。继续循环，L.r[2]=10<50，low++，此时low＝3。L.r[3]=90＞50，退出循环。

6. 第12行，交换L.r[low]＝L.r[3]与L.r[high]＝L.r[9]的值，使得L.r[3]＝50，L.r[9]＝90。此对相当于将一个比50大的值90交换到了50的右边。注意此时low已经指向了3，如下图所示。

   

7. 继续第5行,因为low＝3＜high＝9，执行循环体。

8. 第7行吗，当L.r[high]＝L.r[9]＝90， pivotkey＝50，L.r[high]＞pivotkey，因此第8行，high-，此时high=8。继续循环，L.r[8]＝60＞50, high-，此时high＝7。L.r[7]＝80>50，high-，此时high＝6。L.r[6]＝40＜50，退出循环。

9. 第9行，交换L.r[low]＝L.r[3]＝50与L.r[high]＝L.r[6]＝40的值，使得L.r[3]＝40,L.r[6]＝50,如下图所示。

   

10. 第10行，当L.r[low]＝L.r[3]＝40， pivotkey＝50, L.r［low]＜pivotkey，因此第11行, low++，此时low＝4。继续循环L.r[4]＝30＜50，low++，此时low＝5。L.r[5]＝70＞50，退出循环。

11. 12行，交换L.r[low]＝L.r[5]＝70与L.r[high]＝L.r[6]＝50的值，使得L.r[5]＝50，L.r[6]＝70，如图所示。

    

12. 再次循环。因low＝5＜high＝6，执行循环体后， low＝hlgh＝5，退出循环，如下图所示。

    

13. 最后第14行，返回low的值5。函数执行完成。接下来就是递归调用QSort(L,1,5-1)和QSort(L,5+1,9)，分别进行同样的Partiotion操作，直到顺序全部正确为止。

Partiotion函数的作用就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。

[high]＝L.r[9]的值，使得L.r[3]＝50，L.r[9]＝90。此对相当于将一个比50大的值90交换到了50的右边。注意此时low已经指向了3，如下图所示。

[外链图片转存中…(img-F5Ur0aiH-1663829427239)]

7. 继续第5行,因为low＝3＜high＝9，执行循环体。

8. 第7行吗，当L.r[high]＝L.r[9]＝90， pivotkey＝50，L.r[high]＞pivotkey，因此第8行，high-，此时high=8。继续循环，L.r[8]＝60＞50, high-，此时high＝7。L.r[7]＝80>50，high-，此时high＝6。L.r[6]＝40＜50，退出循环。

9. 第9行，交换L.r[low]＝L.r[3]＝50与L.r[high]＝L.r[6]＝40的值，使得L.r[3]＝40,L.r[6]＝50,如下图所示。

   [外链图片转存中…(img-r3GlwwiQ-1663829427240)]

10. 第10行，当L.r[low]＝L.r[3]＝40， pivotkey＝50, L.r［low]＜pivotkey，因此第11行, low++，此时low＝4。继续循环L.r[4]＝30＜50，low++，此时low＝5。L.r[5]＝70＞50，退出循环。

11. 12行，交换L.r[low]＝L.r[5]＝70与L.r[high]＝L.r[6]＝50的值，使得L.r[5]＝50，L.r[6]＝70，如图所示。

    [外链图片转存中…(img-54siJvwi-1663829427241)]

12. 再次循环。因low＝5＜high＝6，执行循环体后， low＝hlgh＝5，退出循环，如下图所示。

    [外链图片转存中…(img-5vkUWbgn-1663829427242)]

13. 最后第14行，返回low的值5。函数执行完成。接下来就是递归调用QSort(L,1,5-1)和QSort(L,5+1,9)，分别进行同样的Partiotion操作，直到顺序全部正确为止。

Partiotion函数的作用就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。