前几天朋友说三天可以过完一科，最开始不信，现在相信了。
线性表部分
- 顺序表的建立、删除和插入节点
//2021.09.18
//表结构
typedef struct sqlist
{
ElemType elem_array[MAX_SIZE] ;
int length ;
} SqList ;
//初始化
int Init_SqList( SqList *L )
{
L->elem_array=(int*)malloc(100*sizeof(int)) ;//数组的大小为100，不够可以用realloc再分配
if ( !L -> elem_array )
return -1 ;
else {
L->length= 0 ;
return 1 ;
}
}
//插入节点
int Insert_SqList(Sqlist *L，int i ，ElemType e)//数组可直接用下标进行操作，故不必用返回值再赋值一次
{
int j ;
if ( i<1||i>L->length)
return -1 ;
if (L->length>=MAX_SIZE)
{
printf(“线性表溢出!\n”);
return -1 ;
}
for ( j=L->length–1; j>=i-1; --j )
L->Elem_array[j+1]=L->Elem_array[j];
/* i-1位置以后的所有结点后移 */
L->Elem_array[i-1]=e; /* 在i-1位置插入结点 */
L->length++ ;
return OK ;
}
//删除节点，直接覆盖就行
int Delete_SqList(Sqlist *L，int i)
{
int k ;
int x ;//返回被删除的值
if (L->length==0)
{
printf(“线性表L为空!\n”);
return -1000;//假设表中值绝对值小于1000
}
else if ( i<1||i>L->length )
{
printf(“要删除的数据元素不存在!\n”) ;
return -1000 ; }
else { x=L->Elem_array[i-1] ; /*保存结点的值*/
for ( k=i ; k<L->length ; k++)
L->Elem_array[k-1]=L->Elem_array[k];
/* i位置以后的所有结点前移 */
L->length--;
return (x);
}
}
- 链表的建立（头插法、尾插法）、插入、删除节点
//20210920
//节点结构
typedef struct Lnode
{
int data; /*数据域，保存结点的值 */
struct Lnode *next; /*指针域*/
}LNode;
//头插法建表
LNode *CreateListHead(LNode *L,ElemType a[],int n){
LNode *s;
L=(LNode *)malloc(sizeof(LNode));//创建头结点,其data位为空
L->next=NULL; //将头结点next域置空
for(int i=0;i<n;i++){ //循环建立数据结点
//创建数据结点*s
s=(LNode *)malloc(sizeof(LNode));
//将每个新结点s插入到头结点之后
s->data=a[i];
s->next=L->next;
L->next=s;
}
return L;//要将操作过的指针作为参数返回
//C++中可以将指针作为引用传入，可直接修改数值，所以不用再作为返回值重新赋值
//但C语言必须返回
};
//尾插法建表
LNode *CreateListTail(LNode *L,ElemType a[],int n){
LNode *s,*r;
L=(LNode *)malloc(sizeof(LNode));//创建头结点
L->next = NULL; //将头结点next域置空
r=L;//r始终指向尾结点，开始时头结点和尾结点是同一个
for(int i=0;i<n;i++){
s=(LNode *)malloc(sizeof(LNode));//创建数据结点
s->data=a[i];//数据域
r->next=s;//将s插入到r后
r=s;//使r指向尾结点
}
r->next=NULL;//尾指针指针域置空
//若要在循环内将s->next每次都置空，则要多次进行无意义的赋值，大可不必
return L;
};
//插入节点
void insertLNode(LNode *L,int n,int data)
{
LNode *s=L;
int j=0;
LNode *p=(LNode *)malloc(sizeof(LNode));
p->data=data;
while((j<n-1)&&(s!=NULL)&&(s->next!=NULL))
//确保s->next不为空，避免s=NULL的赋值。
//在最后一次判断中s->next!=NULL没意义，因为j=n-1了
{
s=s->next;
j++;
}//循环结束后，s指向了第n-1个节点
if(j!=n-1)//循环提前退出，即节点数小于n-1
printf("插入位置不合适,%d\n",j);
else
{
p->next=s->next;
s->next=p;
}
}
//删除指定位置节点
void deleteLNode(LNode *L,int n)
{
LNode *s=L;
LNode *p=L->next;
int j=0;
while((j<n-1)&&(s!=NULL)&&(p!=NULL))
{
s=p;
p=p->next;
j++;
}
if(j!=n-1)//节点数小于n-1
printf("删除位置不合适,%d\n",j);
else
{
s->next=p->next;
free(p);
}
}
/*之前写过*/
//链表的合并
//链表的倒叙
//链表一元多项式和相加
栈和队列
//代码之前写过，没啥东西
树
- 二叉树
//存储
数组存储，根节点下标为1，左子树下标为2*i,右子树下标为2*i+1，子树为空则空出数组中的位置
typedef struct BTNode//二叉链表存储
{
int data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
typedef struct BTNode_3//三叉链表存储
{
int data ;
struct BTNode_3 *Lchild , *Rchild , *parent ;
}BTNode_3 ;
/******************************
遍历：
分为递归和非递归
也可分为先序、中序、后序、层序
也可分为深度优先（先、中、后序）和广度优先遍历（层序）
*****************************/
//先序遍历
void PreorderTraverse(BTNode *T)//递归写法
{
if (T!=NULL)
{
visit(T->data) ; /* 访问根结点的数据域，具体操作看visit的定义 */
PreorderTraverse(T->Lchild) ;
PreorderTraverse(T->Rchild) ;
}
}
Void preOrder(BiTree T)//非递归写法
//BiTree是结构体指针，定义出的是指针变量
{
InitStack(S);//初始化栈
BiTree p = T;
while(p || !IsEmpty(S)){//判断条件是 或
if(p){//一路向左下
visit(p);
Push(S,p);//入栈
p = p->lchild;
}else{
//一般要连续执行多次，先弹出子树，直到p->rchild不为空
p = Pop(S);//出栈
p = p->rchild;
}
}
}
//中序遍历
void InorderTraverse(BTNode *T)//递归写法
{
if (T!=NULL)
{
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 访问根结点 */
InorderTraverse(T->Rchild) ;
}
}
Void InOrder(Bitree T)//非递归写法
{
InintStack(S);
Bitree p = T;
while( p || !IsEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
}else{
//左子树是在弹出时访问的
p = pop(S);
visit(p);
p=p->rchild;
}
}
}
//后序遍历
void PostorderTraverse(BTNode *T)
{
if (T!=NULL)
{
PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 访问根结点 */
}
}
Void PostOrder(BiTree T)
{
InitStack(S);
BiTree p = T;
BiTree r = NULL;//用于标记右子树有没有被访问
while(p||！IsEmpty(S)){
if(p){
push(S,p);
p = p->lchild;
}
else{
p = GetTop(S);
if(p->rchild&&p->rchild!=r)//当右子树存在且没有被访问
{
p=p->rchild;
}
else
{
pop(S,p);
visit(p->data);
r=p;
p=NULL;
}
}
}
}
//层序遍历
#define MAX_NODE 50
void LevelorderTraverse( BTNode *T)
{
BTNode *Queue[MAX_NODE] ,*p=T ;
int front=0 , rear=0 ;
if (p!=NULL)
{
Queue[++rear]=p; /* 根结点入队 */
while (front<rear)
{
p=Queue[++front];//出队操做，容易造成假溢出
//+在前，先算加法
visit( p->data );
if (p->Lchild!=NULL)
Queue[++rear]=p->Lchild; /* 左结点入队 */
if (p->Rchild!=NULL)
Queue[++rear]= p->Rchild; /* 左结点入队 */
}
}
}
//层序遍历的递归算法不做要求
- 线索二叉树的构建和访问
//N个节点，则有2N个指针域，N-1个指针域用于存放边，N+1个空闲指针域可用于对二叉树进行线索化
//左前驱，右后继
typedef struct BiThrNode
{
int data;
struct BiTreeNode *Lchild , *Rchild ;
int Ltag , Rtag ;//value=1表示指向线索，value=0表示指向子树
}BiThrNode ;
//线索化二叉树
//主要分为先序、中序
//先序和中序，只是在遍历的visit(p->data)处加了线索化的操作
//递归先序线索化二叉树
void PreThread(ThreadTree p,ThreadTree pre)
{
if(p){
if(p->lchild == NULL){//左子树为空，建立前驱线索
p->lchild=pre;
p->Ltag=1;
}
if(pre!=NULL && pre->rchild==NULL){
pre->rchild=p;//建立前驱结点的后继线索
pre->Rtag=1;
}
pre=p;//标记当前结点成为刚刚访问过的结点
if(p->Ltag != 1)
//以1 2 3 NULL 4 5 6为例，在1和2处如果不判断会出现死循环
//PreThread(1,2)->PreThread(1,2)(此时不会再线索化，只会pre=p,然后再下一次)->PreThread(1,2)
//如果不判断ltag，则会死循环，
PreThread(p->lchild,pre);//递归，线索化左子树
if(p->Rtag != 1)
PreThread(p->rchild, pre);//递归，线索化右子树
}
}
//递归中序线索化二叉树
Void inThread(ThreadTree *p,ThreadTree *pre)//pre为直接前驱
{
if(p!=NULL){
//递归，线索化左子树
//不会出现死循环，故无需判断
inThread(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;
//递归，线索化右子树
inThread(p->rchild,pre);
}
}
//线索二叉树的遍历
//先序遍历先序线索二叉树
void preorder_Thread_bt(BiThrNode *T)
{
BiThrNode *p=T ;
while (p!=NULL)
{
visit(p->data) ;
if (p->Ltag==0)
p=p->Lchild;
else
p=p->Rchild;
//若有右子树，则跳转到右子树
//若没有左子树，也没有右子树，则跳转到直接后继
}
}
//中序遍历中序线索二叉树
ThreadNode *FirstNode(ThreadNode *p){//访问的节点，必然是左子树的最深层左子树
//有左子树返回左子树，否则返回自己
while(p->ltag==0)
p = p->lchild;
return p;
}
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag==0)
//右子树存在，则返回其右子树的最深层左子树
return Firstnode(p->rchild);
else
//右子树不存在，返回直接后继
return p->rchild;
}
Void Inorder(ThreadNode *T){
for(ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p))
visit(p);
}
- 树
//存储结构
//双亲表示法
typedef struct PTNode
{
int data ;
int parent ;
}PTNode ;
typedef struct
{
PTNode Nodes[MAX_SIZE] ;//用PTNode 数组存储
int root; /* 根结点位置 */
int num ; /* 结点数 */
}Ptree ;
//复合链表结构
typedef struct listnode
{ i
nt childno ; /* 孩子结点编号 */
struct listno *next ;
}CTNode; /* 表结点结构 */
typedef struct
{
ElemType data ;
CTNode *firstchild ;//叶子节点的孩子节点是NULL
}HNode; /* 头结点结构 */
typedef struct
{
HNode nodes[MAX_NODE] ;//头节点数组，每一个数据元素都是头节点
int root; /* 根结点位置 */
int num ; /* 结点数 */
}CLinkList; /* 复合链表结构 */
//孩子兄弟表示法（二叉树表示，左孩子，右兄弟）
typedef struct CSnode
{ int data ;
struct CSnode *firstchild, *nextsibing ;
}CSNode;
//树的遍历（先序、后序）
树的 先序遍历等同于将树转化为二叉树后的 先序遍历
树的 后序遍历等同于将树转化为二叉树后的 中序遍历
- 哈夫曼树（节点定义、生成算法、哈夫曼编码算法）
//WPL 树的带权路径长度
//代码不要求
typedef struct
{
int Weight ; /* 权值域 */
int Parent , Lchild , Rchild ;
} HTNode ;
//生成算法，看看过程就行
void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m)
/* 创建一棵叶子结点数为n的Huffman树 */
{
unsigned int w ; int k , j ;
for (k=1 ; k<m ; k++)
{ if (k<=n)
{ printf(“\n Please Input Weight : w=?”);
scanf(“%d”, &w) ;HT[k].weight=w ;
} /* 输入时，所有叶子结点都有权值 */
else HT[k].weight=0; /* 非叶子结点没有权值 */
HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;
} /* 初始化向量HT */
for (k=n+1; k<m ; k++)//从N+1开始是非叶子节点
{
unsigned w1=32767 , w2=w1 ;
/* w1 , w2分别保存权值最小的两个权值 */
int p1=0 , p2=0 ;
/* p1 , p2保存两个最小权值的下标 */
for (j=1 ; j<=k-1 ; j++)//找集合中权值最小的两个节点
{
if (HT[k].Parent==0) /* 尚未合并 ，相当于排除掉已经合并过的节点*/
{
if (HT[j].Weight<w1)
{
w2=w1 ;
p2=p1 ;
w1=HT[j].Weight ;
p1=j ;
}
else if (HT[j].Weight<w2)
{
w2=HT[j].Weight ;
p2=j ;
}
} /* 找到权值最小的两个值及其下标 */
}
HT[k].Lchild=p1 ; HT[k].Rchild=p2 ;
HT[k].weight=w1+w2 ;
HT[p1].Parent=k ; HT[p2].Parent=k ;
}
}
//编码过程，看看就行
void Huff_coding(unsigned n , HTNode HT[] , unsigned m)
/* m应为n+1,编码的最大长度n加1 */
{
int k , sp ,fp ;//当前叶子下标，当前编码下标，当前父节点下标
char *cd , *HC[m] ;
cd=(char *)malloc(m*sizeof(char)) ;
/* 动态分配求编码的工作空间 */
cd[n]=‘\0’ /* 编码的结束标志 */
for (k=1 ; k<n+1 ; k++)
{ /* 逐个求字符的编码 */
for ( ; fp!=0 ;p=fp , fp=HT[p].parent)
/* 从叶子结点到根逆向求编码 */
if (HT[fp].lchild==p) cd[--sp]=‘0’ ;
else cd[--sp]=‘1’ ;
HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;
/* 为第k个字符分配保存编码的空间 */
strcpy(HC[k] , &cd[sp]) ;//这里很有趣，讲一下。
}
free(cd) ;
}
- 二叉排序树
天勤查找章节
KMP
讲解：https://zhuanlan.zhihu.com/p/83334559 dp数组，和原算法有出入
// 暴力匹配（伪码）
//pat为模式串，txt为主串
int search(String pat, String txt) {
int M = pat.length;
int N = txt.length;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (pat[j] != txt[i+j])
break;
}
// pat 全都匹配了
if (j == M) return i;//看j是否走完
}
// txt 中不存在 pat 子串
return -1;
}
//首先得到next数组，其值与最大公共前后缀有关
//pat串从下标0处开始存储
//主串指针永不回退
void getNext()
{
// next[j]的值比next[j-1]最多只能增长1
// k表示确定本次next数组值，所需要比较的字母的下标
// 每次给next[j]赋值时，pat[j-1]是需要比较的字母之一
int j, k;//k表示数组值，j表示数组下标
j = 0; k = -1; nxt[0] = -1;
while(j < patlen)
if(k == -1 || pat[j] == pat[k])
nxt[++j] = ++k;
else
k = nxt[k];//回退
}
/*
返回模式串pat在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{
int i = 0, j = 0;
getNext();//得到pat串的next数组
while(i < slen && j < patlen)
{
if(j == -1 || S[i] == pat[j])
{
i++; j++;
}
else
j = nxt[j];
}
if(j == patlen)
return i - patlen;
else
return -1;
}
/*
返回模式串在主串S中出现的次数
*/
int KMP_Count()
{
int ans = 0;
int i, j = 0;
if(slen == 1 && patlen == 1)
{
if(S[0] == pat[0])
return 1;
else
return 0;
}
getNext();
for(i = 0; i < slen; i++)
{
while(j > 0 && S[i] != pat[j])
j = nxt[j];
if(S[i] == pat[j])
j++;
if(j == patlen)
{
ans++;
j = nxt[j];//回退j再进行下一次的比较
}
}
return ans;
}
查找
//平均查找长度：所有查找中进行关键字比较的平均次数
//顺序查找
int Search(int arr[],int n,int data)
{
for(int i=0;i<n;i++)
{
if(arr[i]==data)
return i;
}
return -1;
}
//折半查找
//arr数组必须是有序的
int BinarySearch(int arr[],int n,int x)
{
int low=0;
int high=n-1;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(arr[mid]==x)
return mid;
else if(arr[mid]>x)
mid=high-1;
else
low=mid+1;
}
return -1;
}
//分块查找
//又称索引查找
//无代码，块间有序，块内无序
- 二叉排序树
/*
左子树的所有值都小于等于根的值
右子树的所有值都大于等于根的值
左右子树也符合上述两个条件
*/
typedef struct BTNode
{
int key;//存放的数值
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
//二叉排序树的查找
BTNode* BSTSearch(BTNode *bt,int key)
{
if(bt==NULL)
return NULL;
else
{
if(bt->key==key)
return bt;
else if(key < bt->key)
return BSTSearch(bt->lchild,key);
else
return BSTSearch(bt->rchild,key);
}
}
//插入key到二叉排序树中
int BSTInsert(BTNode *bt,int key)
{
if(bt==NULL)//插入为根节点
{
bt=(BTNode*)malloc(sizeof(BTNode));
bt->lchild=bt->rchild=NULL;
bt->key=key;
return 1;
}
else
{
if(key == bt->key)
return 0;//默认无相同元素，所以不插入
else if(key < bt->key)
return BSTInsert(bt->lchild,key);
else
return BSTInsert(bt->rchild,key);
}
}
//删除节点
/*
(1)p结点是叶子结点：直接删除
(2)p结点无左子树或无右子树：直接删除p后将p的子树连上p的父节点
(3)p结点既有左子树又有右子树：在p的左子树中，一直往右找，也就是找p的【左子树中的最大值】，替换
掉p点，然后接上p的左右子树
*/
- 平衡二叉树
如何调整
- B树
如何调整
- 散列表
不写代码
图
- 有向图中的概念
- 图的存储
//邻接矩阵
#define MaxSize 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
VertexType Vex[MaxSize]; //存储顶点信息，如A、B、C、D
EdgeType Edge[MaxSize][MaxSize]; //存储图的边或边的权值
int vexNum,arcNum; //点的个数和边的个数
}MGraph;
//邻接表
#define MaxSize 100
typedef char VertexType;
typedef int EdgeType;
typedef struct ArcNode{//边类型
int adjvex;//边指向的节点
struct ArcNode *next;
int info; //边的权值
}ArcNode;
typedef struct//点类型
{
VertexType data;
ArcNode *firstarc;//下一条边
}VNode;
typedef struct//图类型
{
VNode adjlist[MaxSize];
int vexNum,arcNum; //点的个数和边的个数
}AGraph;
//具体实例如下图
十字链表
有箭头的一边表示 弧头
顶点节点：数据域、第一个入度节点、第一个出度节点
弧节点： 弧尾、弧头、相同弧头节点、相同弧尾节点、权值
邻接多重表
Mark为标志位，表示该边有没有被访问过
- 图的遍历
深搜和广搜与存储结构基本没有关系
邻接表广搜
while(!QueueEmpty(&Q))
{ //队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->adjlist[i].firstedge; //取vi的边表头指针
while§
{ //依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex])
{ //若vj未访问过
Visit(p->adjvex); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex); //访问过的vj人队
}
p=p->next; //找vi的下一邻接点
}
}邻接矩阵深搜
for (int i=1;i<=n;i++) if (!visited[i])
dfs(i);
//广搜-----邻接矩阵
int visit[MaxSize];//全局变量，开始都为0
void BFS(AGraph *G,int v) //从v点开始广搜图
{
InitQueue(Q); //初始化队列
visit[v]=1;//修改标志位
Visit(v);
Enqueue(Q,v);
while(!isEmpty(Q))
{
DeQueue(Q,v);//队首点弹出
for(int i=1;i<=VexNum;i++)
{
if(G.Edge[v][i]==1&&!visit[i])//如果v点到i点存在边 且i点未访问过
{
Visit(i);
visit[i]=1;
Enqueue(Q,i);
}
}
}
}
//有可能不是连通图，因此要BFS每一个连通分量
void BFSGraph(AGraph *G)
{
for(int i=1;i<=G.VexNum;i++)
visit[i]=0;
for(int i=1;i<=G.VexNum;i++)
{
if(!visit[i])
BFS(G,i);
}
}
//深搜-----邻接表
int visit[MaxSize];
void DFS(AGraph *G,int v)
{
ArcNode *p
visit[v]=1;
Visit(v);
p=G->adjlist[v].firstarc; //从v的第一条边开始
while(p!=NULL)
{
if(visit[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
- 最小生成树（连通但不存在回路的图）
仅存在于无向图中
//加点法----Prim算法/普里姆算法
const int INF=1e9+7;
const int MAXN=110;
bool vis[MAXN]; //标记顶点是否加入最小生成树
int lowc[MAXN]; //存每个点加入最小生成树的最小花费
//点是 从0 到n-1
int Prim(int Graph[][MAXN],int n)
{
int ans=0;
memset(vis,false,sizeof(vis)); //初始化数组，全部初始化为false
vis[0]=true; //第0个点首先加入
for(int i=1;i<n;i++)
lowc[i]=Graph[0][i]; //初始化每个点加入最小生成树的花费为 从该点到0的距离
for(int i=1;i<n;i++)//循环n-1次，每次添加一个点到生成树中
{
int minc=INF; //初始化最小花费为 无穷大
int p=−1; //定义要加入最小生成树的顶点
for(int j=0;j<n;j++)
if(!vis[j]&&minc>lowc[j]) //在所有未加入最小生成树的顶点中，找到距离最小生成树花费最小的点
{
minc=lowc[j];
p=j;
}
if(minc==INF)
return −1;//原图不连通
ans+=minc; //答案加上 加入p点的花费
vis[p]=true; //更改标记
for(int j=0;j<n;j++)
if(!vis[j]&&lowc[j]>Graph[p][j]) //对于剩下所有没有加入最小生成树的点，更新加入最小生成树的花费
lowc[j]=Graph[p][j];
}
return ans;
}
//加边法----Kruskal算法/克鲁斯卡尔算法
//默认图是连通的
int n,m; //n个点，m条边
int pre[MAX]; //每个点所在连通图的标志点
struct edge //边
{
int from,to; //边的左右连接的两个点
int len; //边的权值或长度
};
edge arr[MAX]; //边数组
bool cmp(edge a,edge b) //比较函数，按照边长从小到大排序
{
return a.len<b.len;
}
int Find(int x) //并查集查找函数，用了路径压缩
{
if(pre[x]==x) return x;
return pre[x]=Find(pre[x]);//直到找到pre[x]=x为止，也就是所有生成树的父节点
//实现了路径压缩
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>arr[i].from>>arr[i].to>>arr[i].len;
sort(arr,arr+m,cmp);
for(int i=1;i<=n;i++) //初始化，每个点都是单独的连通图
pre[i]=i;
int pFrom,pTo;
int ans=0;
for(int i=0;i<m;i++)
{
pFrom=Find(arr[i].from); //查找左边的点所在连通图的标志点
pTo=Find(arr[i].to); //查找右边的点所在的连通图的标志点
if(pFrom!=pTo) //当前边所连接的两个点不在同一个连通图
{
ans+=arr[i].len;
pre[pFrom]=pTo; //把左边的点所在的连通图加入右边
}
}
cout<<ans<<endl;
return 0;
}
- 最短路
//Floyd算法------暴力算法
//总共有n个顶点，graph是原图 dis是记录最短路的结果
//假设原来存放了最短路的结果
void Floyd(int n,int graph[][],int dis[][])
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
//Dijkstra算法
int n; //n个点
int m; //m条边
int G[MaxSize][MaxSize]; //矩阵存图
int MinDis[MaxSize]; //出发点到其他点的最短距离
bool vis[MaxSize]; //标记当前节点是否已经最近无法更新
void Init() //初始化
{
for(int i=1;i<=n;i++)
{
vis[i]=0;
for(int j=1;j<=n;j++)
G[i][j]=MaxInt;//全部是最大值
}
}
void djs(int index) //index表示出发点
{
vis[index]=1;
for(int i=1;i<=n;i++)
MinDis[i]=G[index][i];
int time=0; //更新的次数
while(time<n)
{
int node;
int MinNum=MaxInt;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&MinDis[i]<MinNum)
{
MinNum=MinDis[i];
node=i;//下一个出发的节点
}
}
vis[node]=1;
for(int i=1;i<n;i++)
{
if(!vis[i]&&MinDis[i]>MinDis[node]+G[node][i])
{
MinDis[i]=MinDis[node]+G[node][i];
}
}
time++;
}
}
int main()
{
scanf("%d%d",&n,&m);
Init();
int x,y,dis;
for(int i=0;i<m;i++)//输入边
{
scanf("%d%d%d",&x,&y,&dis);
G[x][y]=G[y][x]=dis;
}
djs(1);//求1点到其它点的最短路径
for(int i=2;i<=n;i++)
cout<<MinDis[i]<<endl;
return 0;
}
- 拓扑排序（AOV网）
//退出条件：删除完全部节点，或出现环
//如何判断环？ 通过count计数
//要事先建立一个indegree[]数组，统计所有顶点的入度
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;//先赋值到print数组，后自增
for(p=G.vertice[i].firstarc;p;p=p->nextarc){
v=p->adjvex;
if(!(--indegree[v]))//如果删掉i节点后，v的入度为0
Push(S,v);
}
}
if(count<G.vexNum)//栈为空，遇到环了
return false;
else
return true;
}
- 关键路径（AOE网）
不要求代码
关键路径执行完后，图中所有时间全都执行完了
AOE网：
1.只有某顶点所代表的事件发生后，从该顶点出发的各条边的活动才能开始。
2.只有所有指向该顶点的边的活动都结束，该顶点的事件才开始。
3.只存在一个入度为0的顶点，称为源点，一个出度为0的顶点，称为汇点。
沿着汇点，【逆序找最大值】形成的路径就是关键路径
求出事件的最早开始时间VE 和最晚开始时间VL
求出活动的最早开始时间E 和最晚开始时间L
L-E=0的活动即为关键活动
关键活动连接而成的路径即为关键路径（没有时间余量的活动）
排序
不需要写代码：希尔排序、基数排序、外排序
需要代码：直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、计数排序
计数排序和基数排序都称作桶排序，但二者思想不同
/*
直接插入排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
*/
void straight_insert_sort(Sqlist *L)//升序排列
{
int i, j ;
for (i=2; i<=L->length; i++)//下标0处用作哨兵
{
L->R[0]=L->R[i]; /* 设置哨兵 */
j=i-1;
/*
while循环作用：
第i个元素和前面的逐一比较，然后位移
最终j+1就是要插入的位置
*/
while( L->R[0].key < L->R[j].key )//查找插入位置，若最终没找到，会停在哨兵前面
{
L->R[j+1]=L->R[j];
j--;
} /* 查找插入位置 */
L->R[j+1]=L->R[0]; /* 插入到相应位置 */
}
}
//降序排列：
//只需将while循环的条件改为 vL->R[0].key > L->R[j].key
/*
折半插入排序
时间复杂度：O(N^2) 减少了比较次数，但未减少移动次数
空间复杂度：O(1)
稳定性：稳定
*/
void Binary_insert_sort(Sqlist *L)//升序排列
{
int i, j, low, high, mid ;
for (i=2; i<=L->length; i++)
{
L->R[0]=L->R[i]; /* 设置哨兵 */
low=1 ;
high=i-1 ;
while (low<=high)
{
if ( L->R[0].key < L->R[mid].key)
high=mid-1 ;
else
low=mid+1 ;
} /* 查找插入位置 */
for (j=i-1; j>=high+1; j--)//移动，空出待插入位置
L->R[j+1]=L->R[j];
L->R[high+1]=L->R[0]; /* 插入到相应位置 */
}
}
//降序：将while循环中if判断条件改成【大于号】即可
/*
冒泡排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定的
*/
void Bubble_Sort(Sqlist *L)
{
int j ,k ;
for (j=0; j<L->length; j++) /* 共有n-1趟排序 */
{
for (k=1; k<=L->length-j; k++) /* 一趟排序 */
//k<length-j
if (LT(L->R[k+1].key, L->R[k].key ) )
{
L->R[0]=L->R[k] ;
L->R[k]=L->R[k+1] ;
L->R[k+1]=L->R[0] ;
}
}
}
//LT中为【小于号】是升序，【大于号】为降序
/*
快速排序
时间复杂度：O( nlog2(N) ) //一趟快排为O(N)，因为三个循环加起来只有N次；共有log2(N)次一趟快排
空间复杂度：O( log2(N) ) //递归需要堆栈辅助，最深可以深入到log2(N)层，然后开始弹出
稳定性：不稳定
*/
int quick_one_pass(Sqlist *L , int low, int high)//一趟快速排序
{
int i=low, j=high ;
L->R[0]=L->R[i] ; /* R[0]作为临时单元和哨兵 */
do
//以升序为例，将大于R[i] 的值放在其右侧，小于R[i]的值放在其左侧
//利用双指针进行双向查找
{
while (LQ(L->R[0].key, L->R[j].key)&&(j>i))
j-- ;
if (j>i)
{ L->R[i]=L->R[j] ; i++; }
//此时R[i]的值被保存到R[0]，R[i]可视为空,故直接赋值
while (LQ(L->R[i].key, L->R[0].key)&&(j>i))
i++ ;
if (j>i)
{ L->R[j]=L->R[i] ; j--; }
//此时R[j]的值已经被保存到了【前一步】的R[i]，故也可直接赋值
} while(i!=j) ; /* i=j时退出扫描 */
L->R[i]=L->R[0] ;
Return i ;//返回值为分界点
}
void quick_Sort(Sqlist *L , int low, int high)//递归实现快排
{
int k ;
if (low<high)
{
k=quick_one_pass(L, low, high);
quick_Sort(L, low, k-1);
quick_Sort(L, k+1, high);
} /* 序列分为两部分后分别对每个子序列排序 */
}
/*
简单选择排序/直接选择排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
*/
//以升序为例，降序每次选择最小值即可
/*
不稳定原因：
以{80，80(重)，70}为例，排序后，结果为{70,80(重),80}，两个80交换了顺序
*/
void simple_selection_sort(Sqlist *L)
{
int m, n , k;
//k为要和R[0]交换的位置
for (m=1; m<L->length; m++)
{
k=m ;
for (n=m+1; n<=L->length; n++)
if ( LT(L->R[n].key, L->R[k].key) )
k=n ;
if (k!=m) /* 记录交换 */
{ L->R[0]=L->R[m]; L->R[m]=L->R[k];
L->R[k]=L->R[0];
}
}
}
/*
计数排序
时间复杂度：O(N)
空间复杂度：O(N)
稳定性：不稳定
*/
//用计数的原理，只能对正整数进行排序，且有较多的空间冗余
void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE; //保证max比数组中任何一个数都小
//将max变为数组中的最大值
for (int i = 0; i < arr.length; i++) {//将max和arr[i]中的较大值赋值给max
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
//将数组中的元素依次放入对应的桶
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0; //指向原数组，用于往数组中放入桶中的数据
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) { //将每一个桶中的数据全部取出
arr[i++] = j;
}
}
}
/*
归并排序
时间复杂度：O( nlog2(N) )
空间复杂度：O(N)
稳定性：稳定
*/
void MergeSort_UptoDown(int *num, int start, int end)
/* 将序列对半拆分直到序列长度为1*/
{
int mid = start + (end - start) / 2;
if (start >= end)
{
return;
}
MergeSort_UptoDown(num, start, mid);
MergeSort_UptoDown(num, mid + 1, end);
//递归到最底层后开始合并，此时start=mid; mid+1=end
Merge(num, start, mid, end);
}
void Merge(int *num, int start, int mid, int end)
{
int *temp = (int *)malloc((end-start+1) * sizeof(int)); //申请空间来存放两个有序区归并后的临时区域
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end)
{
if (num[i] <= num[j])
{
temp[k++] = num[i++];
}
else
{
temp[k++] = num[j++];
}
}
while (i <= mid)//如果i还有剩余
{
temp[k++] = num[i++];
}
while (j <= end)
{
temp[k++] = num[j++];
}
//将临时区域中排序后的元素，整合到原数组中
for (i = 0; i < k; i++)
{
num[start + i] = temp[i];
}
free(temp);
}
/*
堆排序
时间复杂度：O( nlog2(N) )
空间复杂度：O(1)
稳定性：不稳定
*/
//堆：完全二叉树、父节点的关键字 > 子节点的关键字
//heap堆 heapify堆调整
//从倒数第二层开始做heapify，就能把二叉树变成堆
//从最后一个节点的parent节点开始，倒着做heapify，即可将一个混乱的树构建成堆
//从最后一个节点开始，与根节点交换、脱离堆、然后再heapify调整堆，经过n-1次调整，就能实现堆排序
//参考灯神的代码
int tree[]={10,4,5,6,7,8};//注意，从0开始计数，显然第i个节点父母的坐标为(i-1)/2，左孩子下标为2*i+1，右孩子下标为2*i+2
void swap(int tree[],int i,int j)
{
int temp=tree[i];
tree[i]=tree[j];
tree[j]=temp;
}
void heapify(int tree[],int n,int i)
{
if(i >= n)//递归的出口
return ;
int c1=2*i+1;
int c2=2*i+2;
int max=i;//随便给一个最大值
if(c1<n && tree[c1]>tree[max])
max=c1;
if(c2<n && tree[c2]>tree[max])
max=c2;
if(max != i)//找到最大值，需要做交换
{
swap(tree,max,i);
heapify(tree,n,max);//对交换之后的堆再做调整
}
}
void build_heap(int tree[],int n)
{
int last_node=n-1;//最后一个节点
int parent=(last_node-1)/2;
int i;
for(i=parent;i>=0;i--)
{
heapify(tree,n,i);//从最后一个节点的父节点开始，
}
}
void heap_sort(int tree[],int n)
{
build_heap(tree,n);
int i;
for(i=n-1;i>=0;i--)
//实现最后一个节点和根节点交换，砍断，然后堆调整
{
swap(tree,i,0);
heapify(tree,i,0);//通过i的递减，控制了每次堆调整时【堆的大小】，模拟了【砍断】的效果
}
}
堆的表示(用数组)
代码尝试
sizeof
//关于sizeof在外函数和main中的用法
void Fun(int arr[])
{
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
arr[i]=1;
}
int main()
{
int arry[8]={0};
Fun(arry);
for(int i=0;i<sizeof(arry)/sizeof(int);i++)
printf("%d\n",arry[i]);
return 0;
}
/*输出：
1
1
0
0
0
0
0
0
*/
//在Fun函数中传入的是地址，不必再除int的大小
arry[++q]=1;
//究竟会赋值给谁
int q=1;
arry[q++]=1; //结果：q=2;arry[1]=1;
int q=1;
arry[++q]=1; //结果，q=2;arry[2]=1;
int q=1;
arry[q++]=q; //结果，q=2;arry[1]=2;
int q=1;
arry[++q]=q; //结果，q=2;arry[2]=2;