主頁 >  其他 > 計算機考研資料結構演算法模板

計算機考研資料結構演算法模板

2021-12-22 08:25:35 其他

計算機考研資料結構演算法模板

前言

臨近考研，想給考研黨們分享一些比較通用的演算法模板，讓復習更高效一點，如果備考時間足夠長，備考人應該有大量時間刷大量習題，會有自己總結的演算法模板，筆者文章參考了王道考研系列教材和李春葆版的《新編資料結構習題與決議》，力求在最短的時間里練習一些重要的通用的代碼塊，希望可以幫助到一些朋友們，祝金榜題名！
手打不易，希望能給個三連支持，

本篇博客中有一些優先級低的知識點，已經標注為選看，還有408新增的并查集操作及應用，非統考生可以只關注簡單實作，

順序表部分

1.逆置

用于逆置順序表，在很多場景下可以用到，如反序或者區域反序，一般作為題解的中間步驟，
引數left是區域逆置的起始點，right為區域逆置的終點，全域逆置只需將left置為0，right置為R的長度-1即可

void reverse(int R[], int left, int right){
	int k = left, j = right, tmp;
	while(k < j){
		tmp = R[k];
		R[k] = R[j];
		R[j] = tmp;
	}
}

2. 洗掉某類元素

以下兩個模板本質上思想是一樣的，時間緊的同學可以只練習一個，

此為洗掉某類元素的模板1，在下面注釋中的if陳述句中為不等條件，即想洗掉等于某值的元素，if中要寫為對立條件，即不等，此演算法的原理是將洗掉的條件直接跨過，故步長即為表的最終長度，
在題解中，洗掉某類元素只需修改標注處if陳述句中的條件，

void delAll(SqList &L, ElemType x){
	int i, k = 0;
	for(i = 0; i < L.length; i++){
		if(L.data[i] != x){ //洗掉條件（逆）
			L.data[i] = L.data[i];
			k++;
		}
	}
	L.length = k;
}

此為洗掉某類元素的模板2，在下面的注釋中的if陳述句中為等值條件，即想洗掉等于某值的元素，if中要寫為等值條件，此演算法的原理是將等于某元素的元素數量當作誤差累計步長的誤差，故表的最終長度為表長減去累計的誤差，

void delAll(SqList &L, ElemType x){
	int i = 0, k = 0;
	while(i < L.length){
		if(data[i] == x) k++; //洗掉條件
		else
			L.data[i - k] = L.data[i];
		i++;
	}
	L.length -= k;
}

3. 按某一條件磁區

按某一條件磁區也即給定基準條件，前一部分如何，后一部分如何，

在本演算法中，標注處條件中的條件可按需求變更，本演算法的特點是用i、j向中間夾逼，能夠保證不重不漏，注意前一部分和后一部分滿足的條件應該是對立的，本例中是讓前一部分為負數，后一部分為非負數，類似可以改為前一部分奇數，后一部分偶數…，同時應注意，本演算法僅磁區，并不會保證兩個部分各自有序，

void move(SqList &L){
	ElemType temp;
	int i = 0, j = L.length - 1;
	while(i < j){
		while(i < j && L.data[i] < 0) i++; //while條件中的data[i] < 0為前一部分滿足的條件
		while(i < j && L.data[j] >= 0) j--; //while條件中的data[i] >= 0為后一部分滿足的條件
		if(i < j){
			temp = L.data[i];
			L.data[i] = L.data[j];
			L.data[j] = temp;
		}
	}
}

4. 洗掉相同元素且保持相對次序

演算法核心思想：插入不排序
憶插入排序思想：將序列劃分為有序區與待檢測區，每次將待檢測區的一個資料插入有序區，并保證有序區有序，有序區逐漸增大，待檢測區慢慢減少，最終使有序區覆寫整張表，從而整體有序，
7 ? o r d e r e d 85936048713 ? u n d e t e c t e d 78 ? o r d e r e d 5936048713 ? u n d e t e c t e d 578 ? o r d e r e d 936048713 ? u n d e t e c t e d 5789 ? o r d e r e d 36048713 ? u n d e t e c t e d 35789 ? o r d e r e d 6048713 ? u n d e t e c t e d . . . \underbrace{7}_{ordered}\quad\underbrace{85936048713}_{undetected}\\ \underbrace{78}_{ordered}\quad\underbrace{5936048713}_{undetected}\\ \underbrace{578}_{ordered}\quad\underbrace{936048713}_{undetected}\\ \underbrace{5789}_{ordered}\quad\underbrace{36048713}_{undetected}\\ \underbrace{35789}_{ordered}\quad\underbrace{6048713}_{undetected}\\ ... ordered 7??undetected 85936048713??ordered 78??undetected 5936048713??ordered 578??undetected 936048713??ordered 5789??undetected 36048713??ordered 35789??undetected 6048713??...
借鑒這種思想，把序列分為無重復區和待檢測區，每次將待檢測區的一個資料插入無重復區，無重復區逐漸增大，待檢測區慢慢減少，最終將序列截斷，使整個表無重復，
7 ? j ? u n i q u e 3 ? i 778 ? u n d e t e c t e d 7 3 ? j ? u n i q u e 7 ? i 78 ? u n d e t e c t e d 7 3 ? j ? u n i q u e 7 7 ? i 8 ? u n d e t e c t e d 7 3 ? j ? u n i q u e 77 8 ? i ? u n d e t e c t e d 73 8 ? j ? u n i q u e 78 73 8 ? j ? u n i q u e \underbrace{\overbrace{7}^{j}}_{unique}\quad\underbrace{\overbrace{3}^{i}778}_{undetected}\\ \underbrace{7\overbrace{3}^{j}}_{unique}\quad\underbrace{\overbrace{7}^{i}78}_{undetected}\\ \underbrace{7\overbrace{3}^{j}}_{unique}\quad7\underbrace{\overbrace{7}^{i}8}_{undetected}\\ \underbrace{7\overbrace{3}^{j}}_{unique}\quad77\underbrace{\overbrace{8}^{i}}_{undetected}\\ \underbrace{73\overbrace{8}^{j}}_{unique}\quad78\\ \underbrace{73\overbrace{8}^{j}}_{unique}\quad unique 7 j??undetected 3 i778??unique 73 j??undetected 7 i78??unique 73 j??7undetected 7 i8??unique 73 j??77undetected 8 i??unique 738 j??78unique 738 j??

void delSame(SqList &L){
	int i, j = 0, k;
	for(i = 1; i < L.length; i++){	//for從下標1開始，第一個元素默認在無重復區中
		k = 0;
		/*
		待檢測元素與無重復區的元素逐一比對，若不同則k增1
		while 中的條件：
			1.k <= j 表示至待檢測元素在與無重復區元素對比
			2.L.data[k] != L.data[i] 表示待檢測元素與當前無重復區中的元素不同
		*/
		while(k <= j && L.data[k] != L.data[i]) k++; 
		if(k > j){ 					//與無重復區的元素比對完畢，無重復
			j++;					//無重復區長度加1
			L.data[j] = L.data[i]; 	//將檢測成功的當前的待檢測元素加入無重復區
		}
	}
	L.length = j + 1;
}

本演算法不涉及排序，故不改變元素的相對次序，只會洗掉冗余元素，本演算法也可用于求交集的思路中，那么本題更改為對兩個表進行操作，

5. 有序順序表的歸并演算法

演算法思路：歸并不排序
借鑒歸并排序的方法，將兩個有序表合并為一個大的有序表，集合類（求交并等）的題目，對于無序的可以用插入不排序的思想，對于有序的可以借鑒歸并不排序的思想，

void Merge(SqList L1, SqList L2, SqList & L3){
	int i = 0, j = 0, k = 0;
	while(i < L1.length && j < L2.length){
		if(L1.data[i] < L2.data[j]){//小者留下
			L3.data[k] = L1.data[i];
			i++;
			k++;
		}
	}
	//下面兩個while是處理剩下的元素，僅會執行一個
	while(i < L1.length){
		L3.data[k] = L1.data[i];
		j++;
		k++;
	}
	while(j < L2.length){
		L3.data[k] = L2.data[j];
		j++;
		k++;
	}
	L3.length = k;
}

6.原地歸并（原地演算法示例）

適用于解決前m個元素有序，后面剩余元素有序，在不借助額外輔助空間的情況下使整張表有序的問題，

void Merge(SqList &A, int m){
	int i = 0, j = m, k;				//j遍歷后半部分的有序表，同時記錄前半部分有序表的長度
	ElemType tmp;
	while(j < A.length && i < j){
		if(j < A.data[j] > A.data[j - 1]){	//整張表已有序
			break;
		} else if(A.data[j] < A.data[i]){	//將A.data[j]插入到前半部分中
			tmp = A.data[j];
			for(k = j - 1; k >= i; k--)		//將A.data[i]及之后的元素后移，給A.data[j]騰地方，i才是A.data[j]應該在的地方
				A.data[k + 1] = A.data[k];
			A.data[i] = tmp;				//將A.data[j]插入A.data[i]處
			i++;
			j++;
		}else{
			i++;
		}
	}	
}

鏈表

1.熟練掌握頭插法、尾插法建表

對于建表演算法，要求建表次序與原來次序相同，則應選擇尾插；如果要求次序相反，則應采用頭插法，
頭插法：

void CreateListFLinkList(LinkList *&L, ElemType a[], int n){
	LinkList *s, int i;
	L = (LinkList *)malloc(sizeof(LinkList));
	L->next = NULL;
	for(i =0; i < n; i++){
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = a[i];
		s>next = L->next;
		L->next = s;
	}
}

尾插法： 尾插一定要記錄尾指標

void CreateListRLinkList(LinkList *&L, ElemType a[], int n){
	LinkList *s, *r, int i;
	L = (LinkList *)malloc(sizeof(LinkList));
	r = L;
	for(i = 0; i < n; i++){
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = NULL;
}

2. 有序單鏈表歸并

順序歸并演算法的鏈表版，無需過多解釋，

void Merge(LinkList *L1, LinkList *L2, LinkList *&L3){
	LinkList *p = L1->next, *q = L2->next, *r, *s;
	L3 = (LinkList *)malloc(sizeof(LinkList));
	r = L3;
	while(p != NULL && q != NULL){
		if(p->data < q->data){
			s = (LinkList *)malloc(sizeof(LinkList));
			s->data = p->data;
			p = p->next;
			r->next = s;
			r = s;
		}else{
			s = (LinkList *)malloc(sizeof(LinkList));
			s->data = q->data;
			q = q->next;
			r->next = s;
			r = s;
		}
	}
	if(q != NULL) p = q;	//無論兩個表剩下誰，統一處理p，減少代碼量
	while(p != NULL){		//處理剩余元素
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = p->data;
		p = p->next;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}

3.原地歸并

在本演算法中，沒有借用第三個表作為輔助空間，而是復用了L1的表頭，將兩個表連接起來，

void Merge(LinkList *L1, LinkList *L2, LinkList *&L3){
	LinkList *p = L1->next, *q = L2->next, *r;
	L3 = L1;
	free(L2);
	r = L3;
	while(p != NULL && q != NULL){
		if(p->data < q->data){
			r->next = p;
			r = p;
			p = p->next;
		}else{
			r->next = q;
			r = q;
			q = q->next;
		}
	}
	if(q != NULL) p = q; //剩余元素直接連接
	r->next = p;
}

4. 王道樹經典遞回法洗掉

此演算法可以當作鏈表洗掉某類元素的模板
此處有個經典錯誤，很多同學會認為這里會斷鏈，實際上在這個if陳述句中的L相當于上一層的L->next，L =L->next之后，對于上一層來說相當于L->next = L->next->next，那么原來的結構就已經發生改變，用p存下的L指的是要洗掉的節點，而原本的鏈表結構已經發生了變化，也就是應該被刪的元素節點已經被摘下來了，它的位置已經被它的下一個節點取代了，因為被刪節點已經不在原本的鏈表中了，那么洗掉它不會影響鏈表，更不會斷鏈，要點：L = L->next是直接操作的原鏈表，直接對鏈表結構發生了改變

void Del_X_3(LinkList &L, ElemType x){
	LNode *p;
	if(L == NULL){
		return;
	}
	if(L.data == x){ 	//洗掉條件
		p = L;
		L = L->next;
		free(p);		//經典一問，會不會斷鏈
		Del_X_3(L, x);
	}else{
		Del_X_3(L->next, x);
	}
}

5. 鏈表題目常用方法

雙指標（野輔聯動）：
用兩個指標，一個基準指標，一個輔助指標，形如：

void xxx(LinkList *&L){
	LNode *pre = L, *p = L->next;
	while(p != NULL){
		//代碼塊
		pre = p;
		p = p->next;
	}
}

基準指標在輔助指標的前面還是后面要按具體題目情況和自己的思路來，兩個指標也并不一定緊挨，while中的條件也是可以按照具體情況需求更改while(p != NULL && [條件])
例：洗掉所有值為x的節點

void Del_X_1(LinkList *&L, ElemType x){
	LNode *pre = L, *p = L->next, *q;
	while(p != NULL){
		if(p->data == x){
			q = p;
			p = p->next;
			pre->next = p;
			free(q);
		}else{
			pre = p;
			p = p->next;
		}
	}
}

如果兩個解決不了怎么辦，那就三個！

三指標（野中輔聯動）：
仍然是一個基準指標，只是輔助多了一個
三個指標，基準指標具體是在中間還是在兩頭，要看題目具體情況發揮，三個指標也不一定要緊挨，可以迎合具體條件，while中的條件也可以靈活按需變通while(p != NULL && [條件])

void xxx(LinkList *&L){
	LNode *prepre = L, *pre = prepre->next, *p;
	while(p != NULL){
		//代碼塊
		prepre = pre;
		pre = p;
	}
}

例：逆置L

void Reverse2(LinkList *&L){
	LinkList *pre = L-next, *p, *post;
	p = pre->next;
	pre->next = NULL;
	while(p != NULL){
		post = p->next;
		p->next = pre;
		pre = p;
		p = post;
	}
	L->next = pre;
}

當然，不嫌麻煩還可以有更多的指標，應該就沒有必要了

二叉樹

二叉樹部分的代碼與線性表相比，其實要簡單，因為樹部分的演算法題，遍歷就是王道，怎么做都是跟遍歷有關，線性表比較靈活，容易結合很多的數學問題，或者原地要求，時間復雜度要求，解法極其靈活，

樹的演算法題，遍歷是王道
首先，要對二叉樹的資料結構定義了然
鏈式：

typedef struct BiNode{
	ElemType data;
	struct BiNode *lchild, *rchild;
}

順序：
T[i] i是資料單元下標

1. 順序二叉樹找公共祖先結點

順序二叉樹掌握一個原則，那就是對于i來說，2i為左孩子2i+1為右孩子

ElemType Comm_Ancestor(SqTree T, int i, int j){
	if(T[i] != '#' && T[j] != '#'){
		while(i != j){
			if(i > j) 	//誰更靠后，誰往上找
				i = i / 2;
			else 
				j = j / 2;
		}
		return T[i];
	}	
}

2. 三序遍歷（遞回）

分別對應根左右、左根右、左右根，是又簡單又重要的模板段，
先序遍歷：

void PreOrder(BiTree T){
	if(T != NULL){
		//代碼塊
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

中序遍歷：

void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);
		//代碼塊
		InOrder(T->rchild);
	}
}

后序遍歷：

void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		//代碼塊
	}
}

3. 層次遍歷

層次遍歷也是一種重要的遍歷演算法，它可以用于與樹高有關的題目中

void LevelOrder(BiTree T){
	queue Q;
	InitQueue(Q);
	BiTree p;
	EnQueue(Q,T);
	while(!IsEmpty(Q)){
		DeQueue(Q,p);
		//代碼段
		if(p->lchild != NULL)
			EnQueue(Q,p->lchild);
		if(p->rchild != NULL)
			EnQueue(Q,p->rchild);
	}
}

判斷當前是否還在某一層內，應該在一次遍歷開始前記錄下本結點的右孩子，那么在遍歷程序中碰到記錄的父節點的右孩子表明到了盡頭，
層次遍歷（佇列符號形應用）：求樹高
本演算法與上面描述的演算法模板本質是一樣的，僅僅是這種符號形屬于使用陣列模擬了佇列的資料結構，使用last標記記錄了每一層的最后一個結點的標號，

int Btdepth(BiTree T){
	if(!T){
		return 0;
	}
	int front = -1, rear = -1;
	int last = 0, level = 0;
	BiTree Q[MaxSize];
	Q[++rear] = T;
	BiTree p;
	while(front < rear){
		p = Q[++front];
		if(p->lchild)
			Q[++rear] = p->lchild;
		if(p->rchild)
			Q[++rear] = p->rchild;
		if(front == last){
			level++;
			last = rear;
		}
	}
	return level;
}

4. 非遞回的后序遍歷（選看）

建議以下二叉樹部分的代碼，讀者在抓細節難以理解時，可以自頂向下，跳出來看整體，會理解的效果好一些
這一部分演算法用于解決尋找祖先，這是后序遍歷的特點，可以回溯找到所有的祖先結點，非遞回的后序遍歷的要點是區分遍歷順序是回傳根結點時是從左子樹回傳的還是從右子樹回傳的，所以，使用輔助指標r，指向最近訪問過的結點，也可以增加一個標志域，記錄是否已被訪問，
輔助指標型：

void PostOrder(BiTree T){
	stack S;
	BiNode p, r;
	InitStack(S);
	p = T;
	r = NULL;
	while(p || IsEmpty(S)){
		if(p){
			Push(S, p);
			p = p->lchild;
		}else{
			GetTop(S, p);
			if(p->rchild && p->rchild != r){ //若右孩子被訪問過，則p->child == r，就可以輸出根結點了，否則，仍要繼續遍歷右子樹
				p = p->rchild;
				Push(S, p);
				p = p->lchild;
			}else{
				Pop(S, p);
				//visit(p->data) 代碼段
				r = p;
				p = NULL;
			}
		}
	}
}

標志域型：（案例：列印x的所有祖先）：

typedef struct {
	BiTree t;
	int tag;
} Stack;//tag=0表示左孩子被訪問，tag=1表示右孩子被訪問
void Search(BiTree bt, ElemType x){
	Stack s[];
	top = 0;
	while(bt != NULL || top > 0){
		while(bt != NULL && bt->data != x){ //移到最左端，或者還沒到最左端遇到了x
			s[++top].t = bt;
			s[top].tag = 0;					//左孩子訪問標志
			bt = bt->lchild;
		}
		if(bt->data == x){					//若在途中偶遇了x，那么堆疊中結點即為其祖先
			printf("所查結點的所有祖先結點的值為：\n");
			for(int i = 1; i <= top; i++)
				printf("%d",s[i].t->data);
			exit(1);
		}
		while(top != 0 && s[top].tag == 1)	//本結點的右孩子已經訪問，說明本結點的左右子樹均已訪問完成，可以退堆疊
			top--;
		if(top != 0){						//若本結點的右孩子未被訪問，遍歷右子樹
			s[top].tag = 1;
			bt = s[top].t->rchild;
		}
	}
}

5. 線索化二叉樹（選看）

這部分內容不在某些學校的考綱中，所以時間緊張的可以先過，線索化二叉樹是利用了二叉樹中的空指標域，將空指標域（即左孩子為慷訓右孩子為空）連接其前驅或后驅結點，以便于遍歷，故線索話的演算法中處理的是左孩子為空和右孩子為空的結點，將他們的空域分別指向其前驅或后繼，并置ltag或rtag為1.
線索二叉樹的資料結構定義：

typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;
} ThreadNode, *ThreadTree;

通過中序遍歷對二叉樹線索化的遞回演算法：

void InThread(Thread Tree &p, ThreadTree &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 != NULL這個條件是對第一個進行特殊處理的，不做操作，僅僅更新pre指標
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;					//及時更新pre
		InThread(p->rchild, pre);	//遞回，線索化右子樹
	}
}
void CreateInThread(ThreadTree T){
	ThreadTree pre = NULL;
	if(T != NULL){
		InThread(T, pre);
		//下面是處理遍歷的最后一個結點，演算法使然
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}

線索二叉樹的遍歷：

  • 求中序線索二叉樹中中序序列下的第一個結點：
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag == 0) p = p->lchild; //找到最左下的結點
	return p;
}
  • 求中序線索二叉樹中結點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)  代碼段
	}
}

圖

2021 408真題中首次出現了圖的演算法題，并且，是遍歷鄰接矩陣的演算法題，所以鄰接矩陣和鄰接表的資料結構定義最好還是需要知曉的，圖的演算法使用DFS與BFS對于考研要求基本足夠，
鄰接矩陣：

typedef struct{
	VertexType Vex[MaxVertexNum];				//頂點表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//鄰接矩陣，邊表
	int vexnum, arcnum;							//圖的當前頂點數和弧數
} MGraph;

鄰接表：

typedef struct ArcNode{							//邊表結點
	int adjvex;									//該弧指向的頂點的位置
	struct ArcNode *next;						//指向下一潭訓的指標
	InfoType info;								//權值
}ArcNode;
typedef strcut VNode{							//頂點表結點
	VertexType data;							//頂點資訊
	ArcNode *first;								//指向第一條依附該頂點的弧的指標
}VNode, AdjList[MaxVertexNum];
typedef struct{									//鄰接表
	AdjList vertices;							//圖的頂點數和弧數
	int vexnum, arcnum;
}ALGraph;

1. 深度優先遍歷

Traverse中的回圈是為了，避免整個圖中有多個連通分量而導致遍歷不全的情況，

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);
}

2. 廣度優先遍歷

BFS需要借助佇列實作，與二叉樹的層次遍歷路子差不多，事實上DFS需要借助堆疊，但函式嵌套的遞回本身就在堆疊中作業，

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){
	for(i = 0; i < G.vexnum; i++)
		visited[i] = FASLE;
	InitQueue(Q);
	for(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)){
		DeQueue(Q, v);
		for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
			if(!visited[w]){
				visit(w);
				visited[w] = TRUE;
				EnQueue(Q, w);
			}
		}
	}
}

排序

1. 插入排序

直接插入排序：

//0相當于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int j;
        for(j=i-1;a[0]<a[j];j--){
            a[j+1] = a[j];
        }
        a[j+1] = a[0];
    }
}

折半插入排序：

//0相當于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int low = 1,high = i-1;
        while(low<=high){
            int mid = low+high>>1;
            if(a[mid]>a[0]) high = mid-1;
            else low = mid+1;
        }
        for(int j=i-1;j>=low;j--){
            a[j+1] = a[j];
        }
        a[low] = a[0];
    }
}

2. 冒泡排序

//冒泡排序，元素下標從1開始，從后往前冒泡
void BubbleSort1(int a[],int n){
    for(int i=1;i<n;i++){
        bool flag = false;
        for(int j=n;j>i;j--){
            if(a[j-1]>a[j]){
                swap(a[j-1],a[j]);
                flag = true;
            }
        }
        if(!flag) return ;
    }
}
 
//冒泡排序，元素下標從1開始，從前往后冒泡
void BubbleSort2(int a[],int n){
    for(int j=n;j>1;j--){
        bool flag = false;
        for(int i=1;i<j;i++){
            if(a[i]>a[i+1]){
                swap(a[i],a[i+1]);
                flag = true;
            }
        }
        if(!flag) return;
    }
}

3. 快速排序

int Partition(int a[],int low,int high){
    int 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;
}
 
//快速排序
void QuickSort(int a[],int low,int high){
    if(low<high){
        int pivotpos = Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
}

4. 簡單選擇排序

//下標從1開始
void SelectSort(int a[],int n){
    for(int i=1;i<=n;i++){
        int tmp=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[tmp]){
                tmp=j;
            }
        }
        swap(a[tmp],a[i]);
    }
 
}

查找

1.折半查找

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)
			high = mid - 1;
		else
			low = mid + 1;
	}
	return -1;
}

并查集（選看）

此部分為408考研新大綱中的新增內容，統考生應重點關注

1. 簡單并查集的實作

#define SIZE 10000
//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
		S[i]=-1;
}
//Find“查"操作，找x所屬集合(回傳x所屬根結點)
int Find(int S[],int x){
	while(S[x]>=0) 			// 回圈尋找x的根
		x=S[x];
	return x;				//根的S[]小于0
}
//Union“并"操作，將兩個集合合并為一個
void Union(int S[],int Rootl,int Root2 ) {
	//要求Root1與Root2是不同的集合
	if (Root1==Root2) return; 
	//將根Root2連接到另-根Root1下面
	S[Root2]=Root1 ;
}

2. 優化后的并查集

下面是優化后的并查集實作，Union操作采用”小樹并入大樹"的優化策略，Find操作采用“壓縮路徑”的優化策略

#define SIZE 10000
//初始化并查集
void Initial(int S[]){
	for(int i = 0; i < SIZE; i++)
	S[i]=-1;
}
//Find“查" 操作優化，先找到根節點，再進行"壓縮路徑”
int Find(int S[], int x){
	int root = X;
	while(S[root] >= 0) root = S[root]; //回圈找到根
	while(x!=root){ //壓縮路徑
	int t = S[x];	// t指向x的父節點
	S[x]=root; 		//x直接掛到根節點下
	x=t;
	return root;	//回傳根節點編號
}
//Union "“并" 操作，小樹合并到大樹
void Union(int S[], int Root1, int Root2) {
	if(Root1==Root2) return ;
	if(S[Root2]>S[Root1]) { //Root2結 點數更少
		S[Root1] += S[Root2]; //累加結點總數
		S[Root2] = Root1; //小樹合并到大樹
	} else {
	S[Root2] += S[Root1]; //累加結點總數
	S[Root1] = Root2;
	}
}

3. 求無向圖中的連通分量

例：二維陣列int g[5][5]表示無向圖G的鄰接矩陣，使用并查集的基本操作，求無向圖G中有幾個連通分量

//用并查集判斷一個圖有幾個連通分量(圖用鄰接矩陣表示)
int ComponentCount(int g[5][5]){
	//g[5][5]是二維陣串列示的鄰接矩陣
	int S[5]; //定義、 初始化并查集
	for (int i=0;i<5;i++) S[i]=-1;
	//遍歷各條邊(無向圖，遍歷上三角部分即可)
	for (int i=0;i<5;i++)
		for (int j=i+1;j<5;j++)
			if (g[i][j]>0){ //結點i、j之間有邊
				int iRoot=Find(S,i); //通過并 查集找到i所屬集合
				int jRoot=Find(S,j); //通過并查集找到j所屬集合
				if (iRoot!=jRoot) //i、 j并入同一集合
				Union(S,iRoot, jRoot);
			}
	//統計有幾個連通分量
	int count=0;
	for (int i=0;i<5;i++)
		if(S[i]<0) count++;
	return count;
}

4. 判斷無向圖是否有環

例：二維陣列int g[5][5]表示無向圖G的鄰接矩陣，使用并查集的基本操作，判斷無向圖G中是否有環

//用并查集判斷一個圖是否有環(圖用鄰接矩陣表示)
int hasAcyclic(int g[5][5]){//g[5][5]是二維陣串列示的鄰接矩陣
	int S[5]; 人//定義、初始化并查集
	for (int i=0;i<5;i++) S[i]=-1;//遍歷各條邊(無向圖，遍歷上三角部分即可)
	for (int i=0;i<5; i++)
		for (int j=i+1;j<5;j++)
			if (g[i][j]>0){ //結點i、j之間有邊
				int iRoot=Find(S,i); //通過并查集找到i所屬集合
				int jRoot=Find(S,j); //通過并查集找到j所屬集合
				if(iRoot !=jRoot) //i、j不在同一個集合，Union 
					Union(S,iRoot， jRoot);
				else //i、j原本就在同一個集合，即原本就連通
				return 1; //在一個連通子圖中， 但凡再多-條邊，必有環
			}
	return 0;//圖中沒有環
}

創作不易，謝邀三連，感謝支持！
CSDN：Moresweet貓甜

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/389162.html

標籤：其他

上一篇：藍橋杯通用動圖講解《演算法和資料結構》

下一篇：位元組面試：SYN 包在什么場景下會被丟棄？

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂