数据结构

第一题 链表的合并

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

思路：

• 头插法的合并，头插边逆序，注意最后在某个链表遍历完，遍历另外一个链表的时候注意需要用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;	
}

第二题

已知图中两个顶点，设计一个算法求出顶点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;			//回溯
}

程序设计

第一题 双端队列 贪心

一个长度为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;
} 

第二题 回溯

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;			斜体样式		//回溯还原 }} 
}