网络安全综合-????第十一章 程序设计应用

时间：2024-04-13 07:13:01

✨1. 顺序表

顺序表结构体定义
typedef struct{
	int data[maxsize];
	int length;
}SqList;

1.顺序表递增有序，插入元素x，仍递增有序
void insert(SqList &L, int x){
	for(int i=0; i<L.length; i++){
		if(L.data[i] >= x){
			for(int j=L.length; j>i; j--){
				L.data[j] = L.data[j-1];
			}//元素后移
			L.data[i] = x;
			L.length++;
			break;
		}
	}
}

2.用顺序表最后一个元素覆盖整个顺序表中最小元素，并返回该最小元素
int cover(SqList &L){
	int min = 0;
	for(int i=1; i<L.length; i++){
		if(L.data[i] < L.data[min]){
			min = i;
		}
	}//找到到最小元素的数组下标
	int minvalue = L.data[min];
	L.data[min] = L.data[length-1];
	L.length--;
	return minvalue;
}

3.将顺序表中的元素逆置
void reserve(SqList &L){
	int temp;
	for(int i=0; i<L.length/2; i++){
		temp = L.data[i];
		L.data[i] = L.data[length-1-i];
		L.data[length-1-i] = temp;
	}
}

4.删除顺序表中所有值为x的元素（喝前摇一摇，考前看一看）
思想：删除顺序表中所有值为x的元素等价于保留顺序表中所有值不为x的元素
void delete(SqList &L, int x){
	int k = 0;
	for(int i=0; i<L.length; i++){
		if(L.data[i] != x){
			L.data[k] = L.data[i];
			k++;
		}
	}//保留顺序表中所有值不为x的元素
	L.length = k;
}

5.从顺序表中删除给定值在s到t之间（包含s和t）的所有元素
void delete(SqList &L, int s, int t){
	int k = 0;
	for(int i=0; i<L.length; i++){
		if(L.data[i]<s || L.data[i]>t){
			L.data[k] = L.data[i];
			k++;
		}
	}//保留顺序表中所有值在s到t之外（不包含s和t）的元素
	L.length = k;
}

6.从有序表中删除所有值重复的元素（喝前摇一摇，考前看一看）
思想：从有序表中删除所有值重复的元素等价于保留第一个不重复的元素
void delete(SqList &L){
	int i,j;
	for(i=0;j=1; j<L.length; j++){
		if(L.data[i] != L.data[j]){
			i++;
			L.data[i] = L.data[j];
		}
	}//保留第一个不重复的元素
	L.length = i+1;
}

7.两个递增有序表合并成一个递增有序表（喝前摇一摇，考前看一看）
void union(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++];
		}else {
			L3.data[k++] = L2.data[j++];
		}
	}//归并操作
	while(i<L1.length){
		L3.data[k++] = L1.data[i++];
	}
	while(j<L2.length){
		L3.data[k++] = L2.data[j++];
	}
	L3.length = k;
}

8.设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数（喝前摇一摇，考前看一看）
int min(int A[], int n){
	int *B = new int[n+1];
	int i;
	for(i=0; i<n+1; i++){
		B[i] = 0;
	}//将B数组中的值全部默认为0
	for(i=0; i<n+1; i++){
		if(A[i]>0 && A[i]<=n){
			B[A[i]] = A[i];
		}
	}//将B数组的下标与A数组的值对应
	for(i=1; i<n+1; i++){
		if(B[i] == 0){
			break;
		}
	}//找出数组中未出现的最小正整数
	delete[] B;
	return i;	
}

✨2. 链表

链表结构体定义
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;

要想删除一个结点必须要知道这个结点的前驱
1.删除带头结点单链表中所有值为x的结点
void delete(LNode *&L, int x){
	LNode *p = L;
	while(p->next != NULL){//这个地方要注意是p->next != NULL,而不是p != NULL
		if(p->next->data == x){//让p充当pre的角色，pre->next即为p
			LNode *q = p->next;
			p->next = q->next;//等价于p->next = p->next->next
			free(q);
		}else{
			p = p->next;
		}
	}
}

2.删除单链表中第一个值为x的元素
int delete(LNode *&L, int x){
	LNode *p = L;
	while(p->next != NULL){
		if(p->next->data == x){
			LNode *q = p->next;
			p->next = q->next;
			free(q);
			break;
		}else{
			p = p->next;
		}
	}
}

3.试编写算法将单链表就地逆置
思路：头插法
void reserve(LNode *&L){
	LNode *p = L->next;
	L->next = NULL;
	LNode *r;
	while(p != NULL){
		r = p->next;//记录p的后继，用于p的后移
		p->next = L->next;
		L->next = p;
		p = r;
	}
}

4.试编写在带头结点的单链表L中删除最小值点的高效算法（已知最小值唯一）
void delete(LNode *L){//minp指向最小值的前驱
	LNode *minp = L;
	LNode *p = L->next;
	while(p->next != NULL){
		if(p->next->data < minp->next->data){
			minp = p;
		}
		p = p->next;
	}
	LNode *q = minp->next;
	minp->next = q->next;
	free(q);
}



5.给定一个单链表，按递增排序输出单链表中各结点的数据元素，并释放结点所占空间
void print(LNode *L){
	while(L->next != NULL){
		LNode *minp = L;
		LNode *p = L->next;
		while(p->next != NULL){
			if(p->next->data < minp->next->data){
				minp = p;
			}
			p = p->next;
		}
		cout << minp->next->data << "";
		LNode *q = minp->next;
		minp->next = q->next;
		free(q);
	}
	free(L);
}

6.将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含奇数位置元素，B中含偶数位置元素，且相对位置不变
LinkList create(LNode *&A){
	LNode *B = new LNode;
	B->next = NULL;
	LNode *p = A->next;
	LNode *ra = A, *rb = B;//ra用来操作A，rb用来操作B
	while(p != NULL){
		ra->next = p;
		ra = p;//ra后移
		p = p->next;
		rb->next = p;
		rb = p;//rb后移
		if(p != NULL){//奇数个补一个这个
			p = p->next;
		}
	}
	ra->next = NULL;//偶数个补一个这个
	return B;
}

7.删除递增链表中重复的元素
void delete(LNode *&L){
	LNode *p = L->next;//p指向首结点
	if(p == NULL){
		return;
	}
	LNode *q;
	while(p->next != NULL){
		q = p->next;//q始终保持在p的后一个位置
		if(p->data == q->data){//删除重复元素
			p->next = q->next;
			free(q);
		}else{
			p = p->next;
		}
	}
}

8.两个递增有序的单链表，设计算法将两个链表合并成一个非递减有序的链表（喝前摇一摇，考前看一看）-
ra始终保持在新链表的尾部，方便插入新结点
void union(LNode *&A, LNode *&B){
	LNode *p = A->next;//p指向A的首结点
	LNode *q = B->next;//q指向B的首结点
	A->next = NULL;
	LNode *ra = A;//用来操作合并后的新链表
	while(p != NULL && q != NULL){
		if(p->data < q->data){
			ra->next = p;
			p = p->next;
			ra = ra->next
		}else{
			ra->next = q;
			q = q->next;
			ra = ra->next;
		}
	}//归并操作
	if(p != NULL){
		ra->next = p;
	}
	if(q != NULL){
		ra->next = q;
	}
}

 9.A,B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破坏A，B结点-
LNode *common(LNode *A, LNode *B){
	LNode *p = A->next;//p指向A的首结点
	LNode *q = B->next;//q指向B的首结点
	LNode *C = (LinkList)malloc(sizeof(LNode));
	LNode *r = C;//r用来操作C链表
	LNode *s;//s表示新生成的结点
	while(p!=NULL && q!=NULL){
		if(p->data < q->data){
			p = p->next;
		}else if(q->data < p->data){
			q = q->next;
		}else{
			s = (LNode *)malloc(sizeof(LNode));
			s->data = p->data;
			r->next = s;
			r = s;
			p = p->next;
			q = q->next;
		}
	}
	r->next = NULL;
	return C;
}

10.查找单链表中倒数第k个结点，若成功，则输出该结点的data，并返回1，否则返回0-
int find(LNode *L, int k){//采用双指针的思想
	LNode *p = L;//p指向L
	LNode *q = L->next;//q指向L的首结点
	int i = 1;//i表示p和q之间的距离
	while(q != NULL){
		q = q->next;
		i++;
		if(i > k){//如果p和q之间的距离大于k，p也要后移（始终保持p和q之间的距离为k）
			p = p->next;
		}
	}
	if(p == L){//如果p至始至终没有移动过一次，就查到不到第倒数第k个
		return 0;
	}
	cout << p->data << "";
	return 1;
} 

11.判断带头结点的循环双链表是否对称-
bool func(LNode *L){
	LNode *p = L->next;
	LNode *q = L->prior;
	while(p!=q && q->next!=p){
		if(p->data != q->data){
			return false;
		}
		p = p->next;
		q = q->prior;
	}
	return true;
}

12.有两个循环单链表，链表头指针分别为h1,h2，试编写函数将h2链表接到h1之后，要求链接后仍保持循环链表形式（喝前摇一摇，考前看一看）-
void link(LNode *&h1, LNode *&h2){
	LNode *p = h1;
	LNode *q = h2;
	while(p->next != h1){
		p = p->next;
	}
	while(q->next != h2){
		q = q->next;
	}
	q->next = h1;
	p->next = h2;
}

13.设有一个带头结点的循环单链表，其结点值为正整数，设计算法反复找出链表内最小值并不断输出，并将结点从链表中删除，直到链表为空，再删除表头结点
void delete(LNode *L){
	while(L->next != L){
		LNode *p = L;
		LNode *minp = L
		while(p->next != L){
			if(p->next->data < minp->next->data){
				minp = p;
			}
		}
		cout << minp->next->data << "";
		LNode *q = minp->next;
		minp->next = q->next;
		free(q);
	}
	free(L);
}

14.判断单链表是否有环（喝前摇一摇，考前看一看）
int func(LNode *L){
	LNode *fast = L;
	LNode *slow = L;
	while(fast && fast->next){
		slow = slow->next;
		fast = fast->next->next;
		if(slow == fast){
			return 1;
		}
	}
	return 0;
}

✨3. 栈和队列

栈的结构体
typedef struct{
	char data[maxsize];
	int top;
}Stack;

队列的结构体
typedef strcut{
	int data[maxsize];
	int front, rear;
}Queue;

1.S是一个空栈，Q是一个队列，编写算法使得队列中元素逆置（喝前摇一摇，考前看一看）
void reserve(Stack &S, Queue &Q){
	while(Q.front != Q.rear){
		push(S, dequeue(Q));
	}//出队入栈
	while(S.top != -1){
		enqueue(Q, pop(S));
	}//出栈入队
}

2.判断单链表的全部n个字符是否中心对称
bool func(LNode *L){
	Stack S;
	int top = -1;
	LNode *p = L->next;
	while(p != NULL){
		S.data[++S.top] = p->data;
		p = p->next;
	}
	p = L->next;
	while(S.top != -1){
		if(p->data == S.data[S.top--]){
			p = p->next;
		}else{
            return false;
        }
	}
	return true;
}

3.两个栈S1，S2都采用顺序存储，并共享一个存储区[0,...,maxsize-1]。采用栈顶相向，迎面增长的存储方式，设计S1，S2入栈和出栈操作（喝前摇一摇，考前看一看）
bool push(Stack &S, int i, int x){//入栈
	if(i<0 || i>1){
		return false;
	}
	if(s.top[1]-s.top[0] == 1){
		return false;
	}
	if(i == 0){
		S.data[++S.top[0]] = x;
	}else if(i == 1){
		S.data[--S.top[1]] = x;
	}
	return true;
}
bool pop(Stack &S, int i){//出栈
	if(i<0 || i>1){
		return false;
	}
	if(i == 0){
		if(S.top[0] == -1){
			return false;
		}else{
			return S.data[S.top[0]--]
		}
	}else if(i == 1){
		if(S.top[1] == maxsize){
			return false;
		}else{
			S.data[S.top[1]++];
		}
	}
	return true;
}

4.判断一个表达式中括号是否配对（假设只包含圆括号）（喝前摇一摇，考前看一看）
bool func(Stack S, String str){
	int i = 0;
	while(str[i] != '\0'){ //‘\0’是字符串结束标志位
		if(str[i]=='('){
			push(S,'(');
		}
		if(str[i]==')'){
			if(pop(S)!='('){
				return false;
			}
		}
		i++;
	}
	if(S.top == -1){
		return true;
	}else{
		return false;
	}
}

✨4.串和数组

1.KMP算法

void get_next(char ch[], int length, int next[]){//length为串ch的长度
	next[1] = 0;
	int i = 1, j = 0;//i当前主串正在匹配的字符位置，也是next数组的索引
	while(i <= length){
		if(j==0 || ch[i] == ch[j]){
			next[++i] = ++j;
		}else{
			j = next[j];
		}
	}
}
  • 求解next数组前要懂得以下几个概念：
  1. 前缀：包含首位字母但不包含末位字母的字串；
  2. 后缀：包含末位字母但不包含首位字母的字串；
  3. next数组的定义：当主串与模式串的某一位字符不匹配时，模式串要回退的位置；
  4. next[j]：其值 = 第 j 位字符前面 j-1 位字符组成的字串的前后缀重合字符数 + 1。
void kmp(char ch[], char text[]){
	int n = len(ch);
	int m = len(test);
	int *next = new int[n];
	get_next(ch, n, next);
	int i = 0, j = 0;
	while(i < m){
		if(j == n-1 && test[i] == ch[j]){
			cout << "匹配成功！位置为："；
			cout << i-j << endl;
			return;
		}
		if(test[i] != ch[j] ){
			j = next[j];
			if(j != -1){
				continue;
			}
		}
		i++;
		j++;
	}
	cout << "匹配失败" << endl;
}

✨5. 树

树的结构体
typedef struct BTNode{
	char data;
	struct BTNode *lchild, *rchild;
}BTNode, *BiTree;

1.计算二叉树中所有结点个数
void count(BTNode *p, int &n){
	if(p != NULL){
		++n;
		count(p->lchild, n);
		count(p->rchild, n);
		
	}
}

2.计算二叉树中所有叶子结点个数
void count(BTNode *p, int &n){
	if(p != NULL){
		if(!p->lchild && !p->rchild){
			n++;
		}
		count(p->lchild, n);
		count(p->rchild, n);
	}
}

3.计算二叉树中所有双分支的结点个数
void count(BTNode *p, int &n){
	if(p != NULL){
		if(p->lchild && p->rchild){
			n++;
		}
		count(p->lchild, n);
		count(p->rchild, n);
	}
}

4.计算二叉树的深度
int deep(BTNode *p){
	if(p == NULL){
		return 0;
	}
	int left = deep(p->lchild);
	int right = deep(p->rchild);
	if(left > right){
		return left + 1;
	}else{
		return right +1
	}
}

5.(a-(b+c)*(d/e))存储在二叉树，遍历二叉树求出表达式，遍历二叉树求表达式的值
void getbda(BTNode *p, int &deep){
	if(p != NULL){
		if(p->lchild && p->rchild && deep>1){
			cout << "(";
		}
		deep++;
		getbds(p->lchild);
		cout << p->data << "";
		getbds(p->rchild);
		deep--;
		if(p->lchild && p->rchild && deep>1){
			cout << ")";
		}
	}
}
int getvalue(BTNode *p){
	if(p == NULL){
		return 0;
	} 
	if(p->lchild && p->rchild){
		int left  = getvalue(p->lchild);
		int right = getvalue(p->rchild);
		reutn op(left, right, p->data);//op函数返回left和right进行p->data操作后的值
	}
	if(!p->lchild && !p->rchild){
		return p->data - '0';
	}
}

6.找出二叉树中最大值的点
void getmax(BTNode *p, int &max){
	if(p != NULL){
		if(p->data > max){
			max = p->data;
		}
		getmax(p->lchild, max);
		getmax(p->rchild, max);
	}
}

7.查找二叉树中data域等于key的结点是否存在，若存在，将q指向它，否则q为空
void func(BTNode *p, int key, BTNode *&q){
	if(p != NULL){
		if(p->data == key){
			q = p;
		}
		func(p->lchild, key, q);
		func(p->rchild, key, q);
	}
}

8.输出先序遍历第k个结点的值
void print(BTNode *p, int k, int &n){
	if(p != NULL){
		if(n == k){
			cout << p->data << "";
			return;
		}
		n++;
		print(p->lchild, k, n);
		print(p->rchild, k, n);
	}
} 

9.求二叉树中值为x的层号（喝前摇一摇，考前看一看）
void func(BTNode *p, int x, int &n){
	if(p != NULL){
		if(p->data == x){
			cout << n <<"";
		}
		n++;
		func(p->lchild, x, n);
		func(p->rchild, x, n);
		n--;
	}
}

10.树中元素为x的结点，删除以它为根的子树
void delete(BTNode *&p, int x){
	if(p != NULL){
		if(p->data == x){
			p == NULL;
			return;
		}
		delete(p->lchild, x);
		delete(p->rchild, x);
	}
}

11.利用结点的右孩子指针将一个二叉树的叶子结点从左向右连接成一个单链表（head指向第一个，tail指向最后一个）
void func(BTNode *p, BTNode *&head, BTNode *&tail){
	if(p != NULL){
		if(!p->lchild && !p->rchild){
			if(head == NULL){
				head = p;
				tail = p;
			}else{
				tail->rchild = p;
				tail = p; 
			}
		}
		func(p->lchild, head, tail);
		func(p->rchild, head, tail);
	}
}

-有左入栈，打印输出
-无左出栈，判断出栈点有无右
--有右，入栈
--无右，继续出栈
12.先序非递归遍历二叉树（喝前摇一摇，考前看一看）***
void nonpre(BTNode *p){
	BTNode *stack[maxsize];
	int top = -1;
	while(p ||top!=-1){
		if(p != NULL){
			cout << p->data << "";
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			p = p->rchild;
		}
	}
}//输出入栈

13.中序非递归遍历二叉树（喝前摇一摇，考前看一看）***
void nonmid(BTNode *p){
	BTNode *stack[maxsize];
	int top = -1;
	while(p || top=-1){
		if(p){
			stack[++top] = p;
			p = p->lchild;	
		}else{
			p = stack[top--];
			cout << p->data << "";
			p = p->rchild;
		}
	}
}//出栈输出

14.后序非递归遍历二叉树（喝前摇一摇，考前看一看）***
void nonpost(BTNode *p, BTNode *tag){
	BTNode *stack[maxsize];
	int top = -1;
	tag == NULL;
	while(p || top!=-1){
		if(p){
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top];
			if(p->rchild && p->rchild!=tag){
				p = p->rchild;
			}else{
				p = stack[top--];
				cout << p->data << "";
				tag = p;
				p = NULL;
			}
		}
	}
}

15.层次遍历（喝前摇一摇，考前看一看）
void level(BTNode *p){
	BTNode *queue[maxsize];
	int front = 0;
	int rear = 0;
	if(p != NULL){
		queue[rear++] = p;
		while(front != rear){
			p = queue[front++];
			cout << p->data << "";
			if(p->lchild){
				queue[rear++] = p->lchild;
			}
			if(p->rchild){
				queue[rear++] = p->rchild;
			}
		}
	}
}//入队输出

16.判断二叉树是否为完全二叉树（喝前摇一摇，考前看一看）***
bool func(BTNode *p){
	BTNode *que[maxsize];
	int front = 0;
	int rear = 0;
	if(p == NULL){
		return true;
	}
	que[rear++] = p;
	while(front != rear){
		p = que[front++];
		if(p != NULL){
			que[rear++] = p->lchild;
			que[rear++] = p->rchild;
		}else{
			while(front != rear){//如果结点为空，判断剩余队列里面有没有非空的元素，若有证明不是完全二叉树
				p = que[front++];
				if(p != NULL){
					return false;
				}
			}
		}
	}
	return true;
}

17.计算二叉树的带权路径长度（叶子结点）（喝前摇一摇，考前看一看）***
int func(BTNode *p, int deep){
	if(p == NULL){
		return 0;
	}
	if(!p->lchild && !p->rchild){
		return deep*(p->data-'0');
	}
	int A = func(p->lchild, deep+1);
	int B = func(p->rchild, deep+1);
	return A + B;
}

✨6. 图

图的结构体之邻接表
typedef struct ArcNode{
	int adjvex; //边所指向结点的位置
	struct ArcNode *nextarc;
}ArcNode, *Node; //边结点结构体
typedef struct{
	int data;
	ArcNode *firstarc;
}VNode; //顶点结构体
typedef struct{
	VNode adjlist[maxsize];
	int numvex, numedg;
}AGraph;
图的结构体之邻接矩阵
typedef struct{
	int verticle[maxsize];
	int edge[maxsize][maxsize];
	int numvex, numedg;
}MGraph;

1.头插法建立图（邻接表结构体）
AGraph *func(int v, int e){
	AGraph *G = new AGraph;
	G->numvex = v;
	G->numedg = e;
	for(int i=0; i<G->numver; i++){
		G->adjlist[i].firstarc = NULL;
	}//初始化顶点表
	for(int i=0; i<G->numedg; i++){
		int v1, v2;
		cin >> v1;
		cin >> v2;
		ArcNode *p = new ArcNode;
		p->adjvex = v1;
		p->nextarc = G->adjlist[v2].firstarc;
		G->adjlist[v2].firstarc = p;
		ArcNode *q = new ArcNode;
		q->adjvex = v2;
		q->nextarc = G->adjlist[v1].firstarc;
		G->adjlist[v1].firstarc = q;
	}//向顶点表中插入双向边
	return G;
}

EL路径：度为奇数的顶点个数为不大于2的偶数
2.判断无向图中是否存在EL路径
int isExistEL(MGraph G){
	int degree;
	int count = 0;//为奇数的顶点个数
	for(int i=0; i<G.numVertices; i++){
		degree = 0;//顶点的度
		for(int j=0; j<G.numVertives; j++){
			if(G.Edge[i][j] != 0){
				degree++;
			}
		}
		if(degree%2 != 0){
			count++;
		}
	}
	if(count==0 || count==2){
		return 1;
	}else{
		return 0;
	}
}

3.树的层次遍历
void level(BTNode *p){
	BTNode *que[maxsize];
	int front = 0;
	int rear = 0;
	if(p != NULL){
		que[rear++] = p;
		while(front != rear){
			p = que[front++];
			cout << p->data << "";
			if(p->lchild != NULL){
				que[rear++] = p->lchild;
			}
			if(p->rchild != NULL){
				que[rear++] = p->rchild;
			}
		}
	}
}
4.图的广度优先遍历（喝前摇一摇，考前看一看）***
void BFS(AGraph *G, int v, int visit[]){
	for(int i=0; i<G->numver; i++){
		visit[i] = 0;
	}
	int que[maxsize];
	int front = 0;
	int rear = 0;
	cout << v <<"";
	visit[v] = 1;
	que[rear++] = v;
	ArcNode *p;
	while(front != rear){
		v = que[front++];//记录这一层的第一个结点并将其出队
		p = G->adjlist[v].firstarc;//记录这一层第一个结点的第一个邻接点
		while(p != NULL){//遍历这一层的所有结点
			if(visit[p->adjvex] == 0){
				cout << p->adjvex << "";
				visit[p->adjvex] = 1;
				que[rear++] = p->adjvex;
			}
			p = p->nextarc;
		}
	}
}

5.利用BFS求无向图的最短路径
void BFSMin(AGraph *G, int v, int visit[], int d[]){
	for(int i=0; i<G->numver; i++){
		visit[i] = 0;
	}//初始化visit数组
	for(int i=0; i<G->numver; i++){
		d[i] = INT_MAX;
	}//初始化d数组
	int que[maxsiz];
	int front = 0;
	int rear = 0;
	visit[v] = 1;
	d[v] = 0;
	que[rear++] = v;
	ArcNode *p;
	while(front != rear){
		v = que[front++];
		p = G->adjlist[v].firstarc;
		while(p != NULL){
			if(visit[p->adjvex] == 0){
				d[p->adjvex] = d[v]+1;
				visit[p->adjvex] = 1;
				que[rear++] = p->adjvex;
			}
			p = p->nextarc;
		}
	}
}

6.图的深度优先遍历（喝前摇一摇，考前看一看）***
void init(AGraph *G, int visit[]){
	for(int i=0; i<G->numver; i++){
		visit[i] = 0;
	}
}
void DFS(AGraph *G; int v; int visit[]){
	cout << v << "";
	visit[v] = 1;
	ArcNode *p = G->adjlist[v].firstarc;
	while(p != NULL){
		if(visit[p->adjvex] == 0){
			DFS(G, p->adjvex, visit);
		}
		p = p->nextarc;
	}
}
void main(AGraph *G, int v, int visit[]){
	init(G, visit);
	DFS(G, v, visit);
}

7.判断图中i和j结点之间是否有路径
void ispath(AGraph *G, int visit[], int i, int j){
	for(int i=0; i<G->numver; i++){
		visit[i] = 0;
	}
	DFS(G, i, visit);
	if(visit[j] == 1){//从i结点开始走一次DFS算法，看visit数组中j位置是否被修改
		return true;
	}else{
		return false;
	}
}

8.求无向图的连通分量个数
int count(AGraph *G, int v, int visit[]){
	for(int i=0; i<G->numver; i++){
		visit[i] = 0;
	}
	int count = 0;
	for(int i=0; i<G->numver; i++){
		if(visit[v] == 0){
			DFS(G, v, visit);
			count++;
		}
	}
	return count;
}

9.邻接表转化成邻接矩阵
void invert(AGraph *G1, MGraph G2){
	G2.numver = G1->numver;
	G2.numedg = G1->numedg;
	ArcNode *p;
	for(int i=0; i<G1->numver; i++){
		G2.vertices[i] = G1->adjlist[i];
		p = G1->adjlist[i].firstarc;
		while(p != NULL){
			G2.edge[i][p->adjvex] = 1;
			p = p->nextarc;
		}
	}
}

10.邻接矩阵变成邻接表(头插法)
void invert(MGraph G1, AGraph *G2){
	G2->numver = G1.numver;
	G2->numedg = G1.numedg;
	ArcNode *p;
	for(int i=0; i<G1.numver; i++){
		G2->adjlist[i]->firstarc = NULL;
	}//初始化邻接表
	for(int i=0; i<G1.numver; i++){
		for(int j=0; j<G1.numver; j++){
			if(G1.edge[i][j] != 0){
				p = new ArcNode;
				p->adjvex = j;
				p->nextarc = G2->adjlist[i].firstarc;
				G2->adjlist[i].firstarc = p;
			}
		}
	}//遍历邻接矩阵生成邻接表
}

✨7. 排序

1.直接插入排序之顺序存储
void insertSort(int A[], int n){
	int i, j, temp;
	for(i=2; i<=n; i++){//因为A[0]做哨兵不存储元素且默认第一个元素有序，所以第一个无序的元素是i=2，无序元素后移的条件变为i<=n
		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];//j指向无序元素最终位置的前一个位置
	}
}

2.直接插入排序之链式存储(喝前摇一摇，考前看一看)***
void linkSort(LNode *&L){
	LNode *p = L->next;//p指向首结点
	LNode *r = p->next;//r记录p的后继结点
	p->next = NULL;//将头指针和头结点与后续元素分开，头指针和头结点为有序序列，后续元素为无序序列
	p = r;//p后移
	while(p != NULL){
		r = p->next;//r记录p的后继结点
		LNode *pre = L;//pre初始指向头结点
		while(pre->next != NULL && pre->next->data < p->data){//在有序序列中找到第一个比无序元素大的前驱结点，让pre指向它
			pre = pre->next;
		}
		p->next = pre->next;//将无序元素插入到有序序列对应位置上
		pre->next = p;
		p = r;//p后移
	}
}

3.折半插入排序(喝前摇一摇，考前看一看)
折半查找条件是: low <= high
快速排序条件是: low < high
归并排序条件是：low < high
void binSearch(int A[], int &low, int &high, int key){
	int mid;
	while(low <= high){
		mid = (low+high)/2;
		if(key < mid){
			high = mid - 1;
		}else if(key >= mid){
			low = mid + 1;
		}
	}
}
void binSort(int A[], int n){
	int low, high;
	for(int i=2; i<=n; i++){
		A[0] = A[i];//A[0]做为临时变量
		low=1, high=i-1;
		binSearch(A, low, high, A[0]);//找到low指针变化后的位置
		for(int j=i-1; j>=low; j--){//这个low也可以写成high+1，后移元素的范围为[low,i-1]
			A[j+1] = A[j];
		}
		A[low] = A[0];//这个low也可以写成high+1
	}
}

4.快速排序（喝前摇一摇，考前看一看）
int part(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 = part(A, low, high);
		quickSort(A,low, pivotpos-1);
		quickSort(A,pivotpos+1,high);
	}
}

5.选择排序
void selectSort(int A[], int n){
	int min;
	for(int i=0; i<n; i++){
		min = i;
		for(int j=i+1; j<n; j++){
			if(A[j] < A[i]){
				min = j;
			}
		}
		swap(A[i], A[min]);
	}
}

6.归并排序（喝前摇一摇，考前看一看）
void func(int A[], int low, int mid, int high){
	int *B = new int[high-low+1];//先把A中的复制到B中，B中划分的两个递增，比较完往A里面放
	int i = low;
	int j = mid+1;
	for(int k=low; k<=high; k++){
		B[k] = A[k];
	}//把A数组中的元素复制到B数组	
	int k = i;
	for(; i<=mid&&j<=high; k++){//归并操作（谁小谁往A里面放）
		if(B[i] <= B[j]){
			A[k] = B[i++];
		}else{
			A[k] = B[j++];
		}
	}
	while(j <= high){//另没走完的数组全部放入A中
		A[k++] = B[j++];
	}
	while(i <= mid){//另没走完的数组全部放入A中
		A[k++] = B[i++];
	}
	delete B[];//动态创建的B数组是存放在堆里面的，需要手动释放B数组才可以
}
void mergeSort(int A[], int low, int high){//初值：low=0, high=n-1
	if(low < high){
		int mid = (low+high)/2;
		mergeSort(A, low, mid);//mergeSort为一种排序方式
		mergeSort(A, mid+1, high);
		func(A, low, mid, high);//两个递增合并为一个大的递增
	}
}

相关文章