PTApt——2023年软件设计综合实践

6-1 递增的整数序列链表的插入

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

答案：语言选C(gcc)

List Insert(List L, ElementType X) {List tmp = (List) malloc(sizeof(List));tmp->Data = X;List ptr = L;// 这样的写法头节点不存储，为0while (ptr->Next && ptr->Next->Data<X) {ptr = ptr->Next;}tmp->Next = ptr->Next;ptr->Next = tmp;return L;
}

6-2 另类循环队列

如果用一个循环数组表示队列，并且只设队列头指针Front，不设尾指针Rear，而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。

答案：语言选C(gcc)

bool AddQ(Queue Q, ElementType X) {if (Q->Count == Q->MaxSize) {printf("Queue Full\n");return false;}Q->Data[(++Q->Count + Q->Front) % Q->MaxSize] = X;return true;
}ElementType DeleteQ(Queue Q) {if (Q->Count == 0) {printf("Queue Empty\n");return ERROR;}Q->Front = (Q->Front + 1) % Q->MaxSize;Q->Count--;return Q->Data[Q->Front];
}

6-3 另类堆栈

在栈的顺序存储实现中，另有一种方法是将Top定义为栈顶的上一个位置。请编写程序实现这种定义下堆栈的入栈、出栈操作。如何判断堆栈为空或者满？

答案：语言选C(gcc)

bool Push(Stack S, ElementType X) {if (S->Top == S->MaxSize) {printf("Stack Full\n");return false;}S->Data[S->Top] = X;S->Top++;return true;
}//Stack Empty
//3 is out
//4 is out
//Stack Full
//0 1 2 5
ElementType Pop(Stack S) {if (S->Top == 0) {printf("Stack Empty\n");return ERROR;}return S->Data[--(S->Top)];
}

6-4 二叉树的遍历

在一棵树T中两个结点u和v的最近公共祖先(LCA)，是树中以u和v为其后代的深度最大的那个结点。现给定某二叉搜索树(BST)中任意两个结点，要求你找出它们的最近公共祖先。

void InorderTraversal(BinTree BT) {if (BT == NULL)return;InorderTraversal(BT->Left);printf(" %c", BT->Data);InorderTraversal(BT->Right);
}void PreorderTraversal(BinTree BT) {if (BT == NULL)return;printf(" %c", BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);
}void PostorderTraversal(BinTree BT) {if (BT == NULL)return;PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c", BT->Data);
}void LevelorderTraversal(BinTree BT) {BinTree a[1000] = {};int size = 0;a[0] = BT;size++;while (size != 0) {BinTree tmp = a[0];for (int i = 1; i < size + 1; i++) {a[i - 1] = a[i];}size--;if (tmp == NULL)continue;else {printf(" %c", tmp->Data);a[size++] = tmp->Left;a[size++] = tmp->Right;}}}

6-6 邻接矩阵存储图的深度优先遍历

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) {//    printV(Visited, Visit);if (Visited[V] == true) {return;} else {Visited[V] = true;Visit(V);for (int i = 0; i < Graph->Nv; i++) {if (i == V)continue;if (Graph->G[V][i] == INFINITY)continue;if (Graph->G[V][i] == 1 && Visited[i] != 1)DFS(Graph, i, Visit);}}}

6-7 邻接表存储图的广度优先遍历

void BFS(LGraph Graph, Vertex S, void (*Visit)(Vertex)) {int q[MaxVertexNum+1] = {};int size = 0;q[size++] = S;Visited[S] = true;while (size != 0) {int tmp = q[0];for (int i = 1; i < size+1; i++) {q[i - 1] = q[i];}size--;Visit(tmp);for (PtrToAdjVNode itr = Graph->G[tmp].FirstEdge; itr != NULL; itr = itr->Next) {if (!Visited[itr->AdjV]) {q[size++] = itr->AdjV;Visited[itr->AdjV] = true;}}}
}

7-1 城市间紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

语言选c++

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int dis[510], weight[510], e[510][510], num[510], w[510], pre[510];
bool visit[510];
const int inf = 99999999;
void printPath(int v) {if(v == c1) {printf("%d", v);return ;}printPath(pre[v]);printf(" %d", v);
}
int main() {scanf("%d%d%d%d", &n, &m, &c1, &c2);for(int i = 0; i < n; i++)scanf("%d", &weight[i]);fill(e[0], e[0] + 510 * 510, inf);fill(dis, dis + 510, inf);int a, b, c;for(int i = 0; i < m; i++) {scanf("%d%d%d", &a, &b, &c);e[a][b] = c;e[b][a] = c;}dis[c1] = 0;w[c1] = weight[c1];num[c1] = 1;for(int i = 0; i < n; i++) {int u = -1, minn = inf;for(int j = 0; j < n; j++) {if(visit[j] == false && dis[j] < minn) {u = j;minn = dis[j];}}if(u == -1) break;visit[u] = true;for(int v = 0; v < n; v++) {if(visit[v] == false && e[u][v] != inf) {if(dis[u] + e[u][v] < dis[v]) {dis[v] = dis[u] + e[u][v];num[v] = num[u];w[v] = w[u] + weight[v];pre[v] = u;} else if(dis[u] + e[u][v] == dis[v]) {num[v] = num[v] + num[u];if(w[u] + weight[v] > w[v]) {w[v] = w[u] + weight[v];pre[v] = u;}}}}}printf("%d %d\n", num[c2], w[c2]);printPath(c2);return 0;
}

7-2 修理牧场

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

语言选c++

#include <iostream>
#include <queue> 
using namespace std;int main()
{priority_queue< int, vector<int>, greater<int> > Q;int N, x, a, b, ans = 0;cin>>N;for(int i = 0;i < N;i++){cin>>x;Q.push(x);}for(int i = 0;i < N-1;i++){a = Q.top();Q.pop();b = Q.top();Q.pop();Q.push(a+b);ans += a+b;}cout<<ans<<endl;return 0;
}

7-3 公路村村通

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

语言选c++

//Prim算法
#include<iostream>
#include<stdio.h>
#define MAXVEX 1005
#define MAXEDGE 3005
#define IFINITY 65535using namespace std;
int G[MAXVEX][MAXVEX];
int N,M;//城镇数目和候选道路数目
int Prim()
{int NumVexes = 0;//初始化加入的节点数int MinLength = 0;int lowcost[MAXVEX];int start = 1;//从城镇1开始for(int i = 1;i < MAXVEX;i++)lowcost[i] = G[start][i];lowcost[start] = 0;NumVexes = 1;int min_cost;int k;for(int i = 1;i < N;i++){min_cost = IFINITY;for(int j = 1;j < N+1;j++){if(lowcost[j] != 0 && lowcost[j] < min_cost){k = j;min_cost = lowcost[j];}}if(min_cost != IFINITY){NumVexes++;MinLength += min_cost;lowcost[k] = 0;for(int j = 1;j < N+1;j++){if(lowcost[j] != 0 && G[k][j] < lowcost[j]){lowcost[j] = G[k][j];}}}}if(NumVexes == N)return MinLength;elsereturn -1;}int main()
{cin >> N >> M;int b,e,w;for(int i = 0;i < MAXVEX;i++){for(int j = 0;j < MAXVEX;j++){G[i][j] = G[j][i] = IFINITY;}}for(int i = 0;i < M;i++){cin >> b >> e >> w;G[b][e] = G[e][b] = w;}printf("%d",Prim());return 0;
}