📢博客主页：https://blog.csdn.net/dxt19980308
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由肩匣与橘编写，首发于CSDN🙉
📢生活依旧是美好而又温柔的，你也是✨
目录
🔴线性表
1.1 顺序表
1.1.1 顺序表定义
1.1.2 顺序表基本操作
1.2 单链表
1.2.1 单链表节点定义
1.2.2 单链表基本操作
1.3 双链表
1.3.1 双链表节点定义
1.3.2 双链表基本操作
1.4 静态链表
🟠栈和队列
2.1 栈
2.1.1 顺序栈
2.1.2 链式栈
2.2 队列
2.2.1 顺序队列
2.2.2 链式队列
2.3 应用
🟡串
3.1 串的定义与实现
3.2 串的模式匹配
🟢树与二叉树
4.1 二叉树
4.1.1二叉树的概念
4.1.2二叉树的操作
4.2 线索二叉树
4.2.1 线索二叉树的概念
4.2.2线索二叉树的操作
4.3 树和森林
4.3.1 树的存储结构
4.4 树的应用
4.4.1 并查集
4.4.2 二叉查找树
🔵图
5.1 图的存储结构
5.1.1 邻接矩阵法
5.1.2 邻接表法
5.1.3 十字链表法
5.1.4 临界多重表法
5.2 图的遍历
5.2.1 广度优先遍历BFS
5.2.2 深度优先遍历DFS
5.3 图的应用
5.3.1最小生成树
5.3.2 拓扑排序
🟣查找
6.1 顺序查找和折半查找
6.1.1 顺序查找
6.1.2 折半查找
🟤排序
7.1 插入排序
7.1.1 直接插入排序
7.1.2 折半插入排序
7.1.3 希尔排序
7.2 交换排序
7.2.1 冒泡排序
7.2.2 快速排序
7.3 选择排序
7.3.1 简单选择排序
7.3.2 堆排序
7.4 归并排序
🔴线性表
1.1 顺序表
1.1.1 顺序表定义
静态定义
#define Maxsize 50
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;动态定义
#define InitSize 100
typedef struct {
ElemType *data; //指示动态分配数组的指针
int MaxSize, length; //数组的最大容量和当前个数
} SeqList;1.1.2 顺序表基本操作
插入
bool ListInsert(SqList &L,int i,ElemType e){
//本算法实现将元素e插入到顺序表L中第i个位置
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
return false;
for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e
L.length++; //线性表长度加1
return true;
}删除
bool ListDelete(SqList &L,int i,ElemType &e){
//本算法实现删除顺序表L中第i个位置的元素
if(i<1||i>L.length) //判断i的范围是否有效
return false;
e=L.data[i-1]; //将被删除的元素赋值给e
for(int j=i;j < L.length;j++)//将第i个位置之后的元素前移
L.data[j-1]=L.data[j];
L.length--; //线性表长度减1
return true;
}按值查找
int LocateElem(SqList L,ElemType e){
//实现查找顺序表中值为e的元素
int i;
for(i=0;i < L.length;i++)
if(L.data[i]==e)
return i+1; //返回其位序i+1
return 0; //退出循环，说明查找失败
}1.2 单链表
1.2.1 单链表节点定义
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;1.2.2 单链表基本操作
头插法
LinkList CreateList1(LinkList &L){
//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始化为空链表
while(scanf(" d",&x) != EOF){ //循环输入
s=(LNode*)malloc(sizeof(LNode));//创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中，L为头指针
scanf(" d",&x);
}//while结束
return L;
}尾插法
LinkList CreatList2(LinkList &L) {
//从表头到表尾正向建立单链表L，每次均在表尾插入元素
int x; //设元素类型为整型
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L; //r为表尾指针
while(scanf(" d",&x) != EOF) { //循环输入
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf(" d",&x);
}
r->next = NULL; //尾结点指针置空
return L
} 按序号索值
LNode *GetElem(LinkList L,int i){
//本算法取出单链表L(带头结点)中第i个位置的结点指针
int j=1; //计数，初始化为1
LNode *p=L->next; //头结点指针赋给P
if(i==0)
return L; //若i等于0.则返回头结点
if(i<1)
return NULL; //若i无效，则返回NULL
while(p&&j<i){ //从第1个结点开始找，查找第i个结点
p=p->next;
j++;
}
return p; //返回第i个结点的指针，如果i大于表长，p= NULL,直接返回p即可
}按值查找结点
LNode *LocateElem(LinkList L,ElemType e){
//本算法查找单链表L(带头结点)中数据域值等于e的结点指针，否 则返回NULL
LNode *p=L->next;
while(p!=NULL&&p->data!=e)//从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
}插入节点操作 (两种)
前插
p=GetElem(L,i-1); //查找插入位置的前驱结点
s->next=p->next;
p->next=s; 后插
//将*s结点插入到*p之前的主要代码片段
s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;删除节点操作
//删除所给节点后一节点
p=GetElem(L,i-1); //查找删除位置的前驱结点
q=p->next; //令q指向被删除结点
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
//删除所给节点
q=p->next; //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间1.3 双链表
1.3.1 双链表节点定义
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;1.3.2 双链表基本操作
插入
s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p; p->next=s;删除
p->next=q->next;
q->next->prior=p;
free(q);1.4 静态链表
#define MaxSize 50 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];🟠栈和队列
2.1 栈
2.1.1 顺序栈
顺序栈的存储类型定义:
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack;顺序栈的基本运算
(1)初始化
void InitStack(&S){
//初始化栈
s.top=-1; //初始化栈顶指针
}
(2)判断空
bool StackEmpty(S){
//判断栈是否为空
if (S.top == -1) //栈空
return true;
else //不空
return false;
}
(3)进栈
bool Push(SqStack &S, ElemType x) {
//进栈操作
if (S.top == MaxSize - 1) //栈满，报错
return false;
S.data[++S.top] = x; //指针先加1，再入栈
return true;
}
bool Pop(SqStack &S, ElemType &x) {
//出栈操作
if (S.top == -1) //栈空，报错
return false;
x = S.data[S.top--]; //先出栈，指针再减1
return true;
}
bool GetTop(SqStack S, ElemType &x) {
//获取栈顶元素
if (S.top == -1) //栈空，报错
return false;
x = S.data[S.top]; //x记录栈顶元素
return true;
}
2.1.2 链式栈
链式栈的存储定义：
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack;2.2 队列
2.2.1 顺序队列
顺序队列的定义
#define MaxSize 50 //定义队列中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //存放队列元素
int front, rear; //队头指针和队尾指针
} SqQueue;循环队列的操作
(1)初始化
void InitQueue(SqQueue &Q) {
//初始化循环队列
Q.rear = Q.front = 0; //初始化队首、队尾指针
}
(2)判空
bool isEmpty(SqQueue Q) {
//判断循环队列是否为空
if(Q.rear==Q.front) return true; //队空条件
else return false;
}
(3)入队
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; //队尾指针加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; //队头指针加1取模
return true;
}2.2.2 链式队列
链式队列的存储
typedef struct{ //链式队列结点
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear; //队列的对头和队尾指针
} LinkQueue;链式队列的基本操作
(1)初始化
void InitQueue(LinkQueue &Q) {
//初始化链式队列
Q.front = Q.rear = (LinkNode *)malloc(sizeof( LinkNode));//建立头结点
Q.front->next = NULL; //初始为空
}
(2)判断空
bool IsEmpty(LinkQueue Q) {
if(Q.front==Q.rear)
return true;
else
return false;
}
(3)入队
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;
}
(4)出队
bool DeQueue(LinkQueue &Q, ElemType &x) {
//链式队列出队操作
if (Q.front == Q.rear)
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;
}2.3 应用
栈在递归中的作用 (斐波那契)
int Fib(n){//斐波那契数列实现
if(n==0)
return 0;//边界条件
else if(n==1)
return 1;//边界条件
else
return Fib(n-1)+Fib(n-2);//递归表达式
}🟡串
3.1 串的定义与实现
定长顺序存储表示
#define MAXLEN 255 typedef struct{
char ch[MAXLEN];//每个分量分配一个字符
int length;//串的实际长度
}SString;堆分配存储表示
typedef struct{
char *ch//按串长度分配存储区 ch指向串的基地址
int length;//串的长度
}HString;3.2 串的模式匹配
简单的模式匹配
int Index(SString S,SString T){
int i=1;j=1; while(i<=S[0]&&j<=T[0]){
if (S[i]==T[j]){
++i;++j; //继续比较后继字符
}
else{
i=i-j+2;j=1; //指针后退重新开始匹配
}
}if(j>T[0])
return i-T[0];
else
return 0;
}KMP
void get_next(char T[],int next[]){
i=1;
next[1]=0; j=0;
while(i<=T[0]){ //T[0]用于保存字符串的长度
if(j==0||T[i]==T[j]){
++i;++j;next[i]=j;
}
else
j=next[j];
}
}
int KMP(char S[],char T[],int next[],int pos){
i=pos;
j=1;
while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){
++i;
++j;
}
else
j=next[j];
} if(j>T[0])
return i-T[0]; else
return 0;
}🟢树与二叉树
4.1 二叉树
4.1.1二叉树的概念
typedef struct BiTNode { //链式二叉树定义
ElemType data; //数据域
struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;4.1.2二叉树的操作
二叉树的遍历 (递归)
1.先序遍历
void PreOrder(BiTree T) {
if (T != NULL) {
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树PreOrder(T->rchild); //递归遍历右子树
}
}
2.中序遍历
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
3.后序遍历
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树visit(T); //访问根结点
}
}二叉树的遍历 (非递归)
void InOrder2(BiTree T) {
//二叉树中序遍历的非递归算法，需要借助一个栈
InitStack(S); BiTree p = T; //初始化栈；p是遍历指针
while (p||!IsEmpty(S)) { //栈不空或p不空时循环
if (p) { //一路向西~不对一路向左(
Push(S,p); //当前节点入栈
p = p->lchild;//左子树不空便继续往左走
}
else { //退栈，访问根结点，遍历右子树
Pop(S,p); visit(p); //退栈，访问根结点
p = p->rchild; //再向右子树走
}
}
}二叉树的层次遍历
void LevelOrder(BiTree T) {
//层次遍历
InitQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根结点入队
while (!IsEmpty(Q)) { //队列不空循环
DeQueue(Q,p); //队头元素出队
visit(p); //访问当前p所指向结点
if (p->lchild!=NULL)
EnQueue(Q,p->lchild);//左子树不空，则入队列
if (p->rchild!=NULL)
EnQueue(Q,p->rchild);//右子树不空，则入队列
}
}4.2 线索二叉树
4.2.1 线索二叉树的概念
线索二叉树节点定义
typedef struct ThreadNode {
// 线 索 二 叉 树 定 义 ElemType data; //数据元素
struct ThreadNode *lchild, *rchild; //左、右孩子指针
int ltag, rtag; //左、右线索标志
} ThreadNode, *ThreadTree;4.2.2线索二叉树的操作
线索二叉树的构造
void InTread(ThreadTree &p,ThreadTree &pre) {
//中序遍历对二叉树线索化的递归算法
if (p!=NULL) {
InTread(p->lchild, pre); //递归，线索化左子树
if (p->lchild == NULL) { //左子树为空建立前驱线索
p->lchild = pre;
p->ltag = 1;
}
if (pre!=NULL && pre->rchild == NULL) {
pre->rchild = p; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = p; //标记当前结点成为刚刚访问过的结点
InTread(p->rchild, pre); //递归，线索化右子树
}//if{p!=NULL}
}
通过中序遍历建立中序线索二叉树线的主过程算法
void CreateInThread(ThreadTree T) {
//中序遍历建立中序线索二叉树
ThreadTree pre = NULL;
if (T!=NULL) { //非空二叉树，线索化
InTread(T, pre); //线索化二叉树
pre->rchild = NULL; //处理遍历的最后一个结点
pre->rtag = 1;
}
}线索二叉树的遍历
(1)求中序线索二叉树中序序列下的第一个结点
ThreadNode *Firstnode(ThreadTree p) {
//求中序线索二叉树中序序列下的第一个结点
while (p->ltag == 0)
p = p->lchild; //最左下结点(不一定是叶结点)
return p;
}
(2)求中序线索二叉树中结点p在中序序列下的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
//求中序线索二叉树中结点p在中序序列下的后继结点
if (p->rtag == 0)
return Firstnode(p->rchild);
else
return p->rchild; //rtag==1直接返回后继线索
}
(1-1)求中序线索二叉树中序序列下的最后一个结点
ThreadNode *Lastnode(ThreadTree p) {
//求中序线索二叉树中序序列下的最后一个结点
while (p->rtag == 0)
p = p->rchild;
return p;
}
(2-1)求中序线索二叉树中结点p在中序序列下的前驱结点
ThreadNode *Prenode(ThreadNode *p) {
//求中序线索二叉树中结点p在中序序列下的前驱结点
if (p->ltag == 0)
return Lastnode(p->lchild);
else
return p->lchild;
}
(3)不带头结点的中序线索二叉树的中序遍历
void InOrder(ThreadTree T) {
//不带头结点的中序线索二叉树的中序遍历
for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
visit(p);
}4.3 树和森林
4.3.1 树的存储结构
双亲表示法
#define MAX_TREE_SIZE 100 //树中最多结点数、
typedef struct { //树的结点定义
ElemType data; //数据元素
int parent; //双亲位置域
} PTNode;
typedef struct{ //树的类型定义
PTNode nodes[MAX_TREE_SIZE];//双亲表示
int n; //结点数
}PTree;孩子兄弟表示法
typedef struct CSNode{
ElemType data; //数据域
struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;4.4 树的应用
4.4.1 并查集
并查集结构定义
#define SIZE 100
int UFSets[SIZE]； //集合元素数组(双亲指针数组)并查集初始化
void Initial(int S[]) {
for (int i = 0; i < MaxSize; i++) //每个自成单元素集合
S[i] = -1;
}Find 操作
int Find(int S[], int x) {
while (S[x] >= 0) //循环寻找x的根
x = S[x];
return x; //根的S[]小于0
}Union 操作
void Union(int S[], int Root1, int Root2) {
//Root1与Root2不同并且表示子集合的名字
S[Root2] = Root1; //将根Root2连接到另一根Root1下面
}4.4.2 二叉查找树
二叉查找树非递归查找
BSTNode *BST_Search(BiTree T, ElemType key, BiTNode *&p) {
//查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL
p = NULL;//p指向被查找结点的双亲结点，用于插入删除操作
while (T != NULL && key != T->data) { p = T;
if (key < T->data)
T = T->lchild;
else
T = T->rchild;
}
return T;
}二叉查找树插入
int BST_Insert(BiTree &T, KeyType k) {
//在二叉排序树T中插入一个关键字为k的结点
if (T == NULL) { //原树为空，新插入的记录为根结点
T = (BiTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1; //返回1，表示成功
}
else if (k == T->key) //树中存在相同关键字的结点
return 0;
else if (k < T->key) //插入到T的左子树中
return BST_Insert(T->lchild, k); else //插入到T的右子树中
return BST_Insert(T->rchild, k);
}二叉排序树构造
void Creat_BST(BiTree &T, KeyType str[], int n) {
//用关键字数组str[]建立一个二叉排序树
T = NULL; //初始时bt为空树
int i = 0;
while (i < n){ //依次将每个元素插入
BST_Insert(T, str[i]);
i++;
}
}🔵图
5.1 图的存储结构
5.1.1 邻接矩阵法
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;5.1.2 邻接表法
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode { //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
//InfoType info; //网的边权值
} ArcNode;
typedef struct VNode { //顶点表结点
VertexType data; //顶点信息
ArcNode *first; //指向第一条依附该结点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct { //图的邻接表存储结构定义
AdjList vertices; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} ALGraph;5.1.3 十字链表法
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{ //边表结点
int tailvex, headvex; //该弧的头尾结点
struct ArcNode2 *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点
//InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstin, *firstout; //指向第一条入弧和出弧
} VNode; typedef struct {
VNode xlist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} GLGraph;5.1.4 临界多重表法
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode { //边表结点
bool mark; //访问标记
int ivex, jvex; //分别指向该弧的两个结点
struct ArcNode3 *ilink, *jlink; //分别指向两个顶点的下一条边
//InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode { //顶点表结点
VertexType data; //顶点信息
ArcNode *firstedge; //指向第一条依附该顶点的边
}VNode;
typedef struct {
VNode adjmulist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} AMLGraph;5.2 图的遍历
5.2.1 广度优先遍历BFS
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){
//对图G进行广度优先遍历，设访问函数为visit()
for(i=0;i<G.vexnum,++i)
visited[i]=false; //访问标记数组初始化
InitQueue(Q); //初始化辅助队列Q
for (int i = 0; i < G.vexnum; ++i)//从0号顶点遍历
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G,i); //Vi未访问过，从Vi开始BFS
}
void BFS(Graph G,int v){
//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
visit(v); //访问初始顶点v
visited[v]=true; //对v做已访问标记
EnQueue(Q,v); //顶点v入队列
while(!IsEmpty(Q)){
DeQueue(Q,v); //顶点v出队列
for (w=FirstNeighbor(G,v); w>=0;w=NextNeighbor(G,v,w))
{ //检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w]=true; //对w做已访问标记
EnQueue(Q,w); //顶点w入队列
}//if
}
}//while
}BFS 算法求解单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for (int i = 0; i < G.vexnum; ++i)
d[i]=∞； //初始化路径长度
visited[u]=true;d[u]=0;
EnQueue(Q,u);
while(!IsEmpty(Q)){ //BFS算法主过程
DeQueue(Q,u); //队头元素u出队
for (w=FirstNeighbor(G,u); w>=0;w=NextNeighbor(G,u,w))
{
if(!visited[w]){ //w为u的尚未访问的邻接顶点
visited[w]=true; //设已访问标记
d[w]=d[u]+1; // 路 径 长 度 加 1
EnQueue(Q,w); //顶点w入队
}//if
}
}//while
}5.2.2 深度优先遍历DFS
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历
for(v=0;v<G.vexnum,++v)
visited[v]=false; //初始化已访问标记数据
for (v = 0; v < G.vexnum; ++v) //本代码中是从v=0开始遍历
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){
//从顶点v出发，采用递归思想，深度优先遍历图G
visit(v); //访问顶点v
visited[v]=true; //设已访问标记
for (w=FirstNeighbor(G,v); w>=0;w=NextNeighbor(G,v,w))
{
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G,w);
}//if
}
}5.3 图的应用
5.3.1最小生成树
GENERIC_MST(G){ T=NULL;
while T 未形成一颗生成树；
do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
T=T (u,v);
}Prim 算法
void Prim(G,T){
T= ; //初始化空树
U={w}; //添加任一顶点w
while((V-U)!= ){ //若树中不含全部顶点
设(u,v)是使u U与v (V-U)，且权值最小的边；
T=T {(u,v)}; //边归入树
U=U {v}; //顶点归入树
}
}Krustal 算法
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--; //连通分量数减1
}
}
}5.3.2 拓扑排序
bool TopologicalSort(Graph G){
//如果G存在拓扑序列，返回true；否则返回false，这时G中存在环
InitStack(S); //初始化栈，存储入度为0的顶点
for (int i = 0; i < G.vexnum; ++i)
{
if(indegree[i]==0)
Push(S,i); //将所有入度为0的顶点进栈
}
int count=0; //计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点
Pop(S,i); //栈顶元素出栈
print[count++]=i; // 输 出 顶 点 i
for(p=G.vertices[i].firstarc;p=p->nextarc){
//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
v=p->adjvex;
if(!(--indegree[v])) Push(S,v); //入度为0，则入栈
}//for
}//while
if(count < G.vexnum)
return false; //排序失败，有向图中有回路
else
return true; //拓扑排序成功
}邻接矩阵存储结构的 NextNeighbor 函数
int NextNeighbor(MGraph& G,int x,int y){
if(x!=-1&&y!=-1){
for (int col=y+1;col < G.vexnum;col++)
{
if(G.Edge[x][col] > 0&&G.Edge[x][col] < maxWeight)
return col; //maxWeight代表∞
}
}
return -1;
}邻接表做存储结构
int NextNeighbor(ALGraph& G,int x,int y){ if(x!=-1){ //顶点x存在
ArcNode *p=G.vertices[x].first; //对应边链表第一个边结点
while(p!=NULL&&p->data!=y) //寻找邻接顶点Y p=p->next;
if(p!=NULL&&p->next!=NULL)
return p->next->data; //返回下一个邻接顶点
}
return -1;
}🟣查找
6.1 顺序查找和折半查找
6.1.1 顺序查找
typedef struct{ //查找表的数据结构
ElemType *elem; //元素存储空间基址，建表时按实际长度分配，0号单元留空
int TableLen; //表的长度
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
//在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元 素在表中的位置
ST.elem[0]=key; //“哨兵”
for (i=ST.TableLen;ST.elem[i]!=key; --i){ //从后往前找
}
return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}6.1.2 折半查找
int Binary_Search(SeqList L, ElemType key) {
//在有序表L中查找关键字为key的元素，若存在则分会其位置，不 存在返回-1
int low = 0, high = L.length - 1, mid; while (low <= high) {
mid = (low + high) / 2; //取中间位置
if (L.elem[mid] == key)
return mid; //查找成功则返回所在位置else if(L.elem[mid] > key)
high = mid - 1; //从前半部分继续查找
else
low = mid + 1; //从后半部分继续查找
}
return -1;
}🟤排序
7.1 插入排序
7.1.1 直接插入排序
void InsertSort(ElemType A[], int n) {
//直接插入排序int i, j;
for (i = 2; i <= n; i++) //依次将A[2]～A[n]插入到前面已排好的序列
if (A[i].key < A[i - 1].key) { //若A[i]的关键码小于其前驱，需将A[i]插入有序表
A[0] = A[i]; //复制为哨兵，A[0]不存放元素
for (j = i - 1; A[0].key < A[j].key; --j) //从后往前查找待插入位置
A[j+1] = A[j]; //向后挪位
A[j + 1] = A[0]; //复制到插入位置
}
}7.1.2 折半插入排序
void InsertSort(ElemType A[], int n) {
//折半插入排序
int i, j, low, high, mid;
for (i = 2; i <= n; i++) { //依次将A[2]～A[n]插入到前面已排序序列
A[0] = A[i]; //将A[i]暂存到A[0]
low = 1; high = i - 1; //设置折半查找的范围
while (low <= high) { //折半查找（默认递增有序）
mid = (low + high) / 2; //取中间点
if (A[mid].key > A[0].key) 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]; //插入操作
}
}7.1.3 希尔排序
void ShellSort(ElemType A[], int n) {
//希尔排序，对顺序表做希尔插入排序，比直接插入排序有如下修 改
//1.前后记录的增量是dk，不是1
//2.A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
int i, j, dk; //dk:步长
for (dk = n / 2; dk >= 1; dk = dk / 2) //步长变化
for (i = dk + 1; i <= n; ++i)
if (A[i].key < A[i - dk].key) { //需将A[i]插入有序增量子表
A[0] = A[i]; //暂存在A[0]
for (j = i - dk; j > 0 && A[0].key < A[j
].key; j -= dk)
A[j + dk] = A[j]; //记录后移，查找插入的位置
A[j + dk] = A[j]; //插入
}//if
}7.2 交换排序
7.2.1 冒泡排序
void BubbleSort(ElemType A[], int n) {
//用冒泡排序法将序列A中的元素按从小到大排列
bool flag;
for (int i = 0; i < n - 1; i++) {
flag = false; //表示本趟冒泡是否发生交换的标志
for (int j = n - 1; j > i; j--) //一趟冒泡过程
if (A[j - 1].key > A[j].key) { //若为逆序
swap(A[j - 1], A[j]); //交换
flag = true;
}
if (flag == true)
return; //本趟遍历后没有发生交换说明表已经有序
}
}7.2.2 快速排序
void QuickSort(ElemType A[], int low, int high) {
//快速排序
if (low < high) { //递归跳出的条件
//Partition()就是划分操作，将表A[low...high]划分为满 足上述条件的两个子表
int pivotpos = Partition(A, low, high); //划分
QuickSort(A, low, pivotpos - 1); //依次对两个子表进行递归排序
QuickSort(A, pivotpos + 1, high);
}
}
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]; //将比枢轴值小的元素移动到左端
while (low < high && A[low] <= pivot)
++low;
A[high] = A[low]; //将比枢轴值大的元素移动到右端
}
A[low] = pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴元素的位置
}7.3 选择排序
7.3.1 简单选择排序
void SelectSort(ElemType A[], int n) {
//对表A进行简单的选择排序，A[]从0开始存放元素
for (int i = 0; i < n - 1; i++) { //一共进行n-1趟
int min = i; //记录最小元素位置
for (int j = i + 1; j < n; j++) //在A[1...n-1]中选择最小的元素
if (A[j] < A[min]) min = j; //更新最小元素的位置
if (min != i) swap(A[i], A[min]); //与第i个位置互换
}
}7.3.2 堆排序
建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
//建立大根堆
for (int i = len / 2; i > 0; i--) //从i=[n/2]～1，反复调整堆
AdjustDown(A, i, len);
}
void AdjustDown(ElemType A[], int k, int len) {
//函数AdjustDown将元素k向下进行调整
A[0] = A[k]; //A[0]暂存
for (int 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值，以便继续向下筛选
}
}//for
A[k] = A[0]; //被筛选结点的值放入最终位置
}
堆排序算法
void HeapSort(ElemType A[], int len) {
//堆排序
BuildMaxHeap(A, len); //建立初始堆
for (int i = len; i > 1; i--) { //n-1趟的交换和建堆过程
swap(A[i], A[1]); //输出堆顶的元素（和堆底元素交换）
AdjustDown(A, 1, i - 1); //整理，把剩余的i-1个元素整理成堆
}
}
向上调整堆的算法
void AdjustUp(ElemType A[], int k) {
//参数k为向上调整的结点，也为堆的元素个数A[0] = A[k];
int i = k / 2; //若结点值大于双亲结点,则将双亲结点下调，并继续向上比较
while (i > 0 && A[i] < A[0]) { //循环退出条件A[k] = A[i]; //双亲结点下调
k = i;
i = k / 2; //继续向上比较
}//while
A[k] = A[0]; //复制到最终位置
}7.4 归并排序
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));//辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
//表A的两端A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
for(int k=low;k<=high;k++)
B[k]=A[k]; //将A中所有元素复制到B中
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]) //比较B的左右两段中的元素
A[k]=B[i++]; //将较小值复制到A中
else
A[k]=B[j++];
}//for
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); //归并
}//if
}文章出处登录后可见！
已经登录？立即刷新
