18 软专

数据结构

第一题 链表的合并

单链表形式存储的线性表，每个表均按元素值递增次序进行排序，编写算法，将两个单链表合并为一个递减次序的单链表 ，要求不能额外增加存储空间

思路：

• 头插法的合并，头插边逆序，注意最后在某个链表遍历完，遍历另外一个链表的时候注意需要用while头插，直到为空

代码：

typedef struct node{
	int data;
	struct node *next;
}*list; 

list mergelist(list head1, list head2){		//假设不带头结点 
	struct node *newhead,*p1,*p2,*next;		//newhead保存合并的单链表，p1为head1的工作指针，p2为head2的工作指针 
	p1 = head1; p2 = head2;
	
	if(p1->data > p2->data){				//保存较小的节点 
		newhead = p2;
		p2 = p2->next;
	}
	else{
		newhead = p1;
		p1 = p1->next;
	} 
	newhead->next = NULL;
	while(p1 != NULL && p2 != NULL){
		if(p1->data > p2->data){		//将较小的节点头插入newhead中 
			next = p2->next;
			p2->next = newhead;
			newhead = p2;
			p2 = next;
		}
		else{
			next = p1->next;
			p1->next = newhead;
			newhead = p1;
			p1 = next;
		} 
	}
	
	while(p1){							//p1还有节点，继续插入 
		next = p1->next;
		p1->next = newhead;
		newhead = p1;
		p1 = next;
	}
	while(p2){							//p2还有节点，继续插入 
		next = p2->next;
		p2->next = newhead;
		newhead = p2;
		p2 = next;
	} 
	
	p1 = newhead;
	while(p1!=NULL){
		printf("%d ",p1->data);
		p1 = p1->next;
	}
	return newhead;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

第二题

已知图中两个顶点，设计一个算法求出顶点i到顶点j的所有简单路径

思路：

• dfs+回溯，在图dfs基础上修改，注意回溯的位置是在遍历完该条边所有领接边之后再回溯，而不是立马遍历一条边就回溯，不然找不到完整的路径，同时visited,path数组也是在dfs遍历的时候就标记

代码：

typedef struct ArcNode{		//边结点 
	int adjvex;
	struct ArcNode *next; 
}ArcNode; 
 
typedef struct VNode{		//顶点节点 
	int data;
	struct ArcNode *firstarc; 
}VNode;

typedef struct AGraph{		//领接表 
	VNode adjlist[maxsize];
	int vexnum, edgenum;
}AGraph;

//思路：深度优先遍历回溯
int visited[maxsize] = {0};
int path[maxsize] = {0};

void dfsfindall(AGraph *G, int i, int j, int count){		//count统计路径长度 
	path[count++] = i; 
	visited[i] = 1;
	if(i == j){
		for(int k = 0; k < count; k++){
			printf("经过了节点%d ",path[k]);
		}
		printf("\n"); 
	}
	ArcNode *p = G->adjlist[i].firstarc;
	while(p!=NULL){
		if(visited[p->adjvex] == 0){
			dfsfindall(G,p->adjvex,j,count);
		} 
		p = p->next;
	}
	visited[i] = 0;			//回溯
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

程序设计

第一题 双端队列 贪心

一个长度为n的非负整型双向队列的加权和定义如下：
(1)依次从队列头或者队列尾取一个数，共取n次
(2)第i次取出的数乘以系数i，得到加权数
(3)将n个加权数求和，即为该队列的加权和
编写函数，计算给定一个长度为n的非负整型双向队列的“加权和"的最大值
双向队列用一维数组或链表表示

思路：

• 贪心的思路，在队头或者队尾中取较小的元素

代码：

//贪心思路：比较队头和队尾元素大小，将小的先出队 
int summary(int A[], int n){
	int i=0, j = n-1,sum=0,count = 1;
	while(i <= j){
		if(A[i] < A[j]){
			sum += A[i]*count;
			i++;
		}
		else{
			sum += A[j]*count;
			j--;
		}
		count++;
	} 
	printf("最大加权和为%d",sum);
	return sum;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二题 回溯

N*N的矩阵a表示有向图的领接表，其中
d[i,j] = 1 节点i到节点j有边
d[i,j] = 0 节点i到节点j无边
编写函数，给定节点i和步长k，计算节点i经k步能到达的所有节点

思路：

• dfs回溯（三大步骤）
• 1、确定函数的中的参数
• 2、确定函数的终止条件
• 3、确定单层递归的具体表达式（回溯在这里实现）

代码：

int visited[N] = {0};		//判断是否访问过 
int isout[N] = {0};			//判断是否输出 

void dfsfindallnode(int a[N][N], int i, int k){
	if(k == 0){				//函数的终止条件 
		if(isout[i] == 0){
			printf("可以到达节点%d\n",i); 
			isout[i] = 1;
			return;			//结束当前层递归 
		}
	}
	for(int j = 0;  j < N; j++){
		if(a[i][j] == 1 && visited[j]==0){//如果可以到达这个点的话 
			visited[j]=1;
			dfsfindallnode(a,j,k-1);
			visited[j]=0;				//回溯还原 
		}
	} 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19