PTApt——2023年软件设计综合实践_7(数据结构)

news/2024/2/29 4:21:53

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中两个结点uv的最近公共祖先(LCA),是树中以uv为其后代的深度最大的那个结点。现给定某二叉搜索树(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;
}


https://www.xjx100.cn/news/3118873.html

相关文章

flink源码分析之功能组件(四)-slotpool组件II

简介 本系列是flink源码分析的第二个系列&#xff0c;上一个《flink源码分析之集群与资源》分析集群与资源&#xff0c;本系列分析功能组件&#xff0c;kubeclient&#xff0c;rpc&#xff0c;心跳&#xff0c;高可用&#xff0c;slotpool&#xff0c;rest&#xff0c;metrics&…

FastApi接收不到Apifox发送的from-data字符串_解决方法

接收不到Apifox发送的from-data字符串_解决方法 问题描述解决方法弯路总结弯路描述纵观全局小结 问题描述 这里写了一个接口&#xff0c;功能是上传文件&#xff0c;接口参数是file文件和一个id字符串 gpt_router.post("/uploadfiles") async def create_upload_fi…

Web安全漏洞分析-XSS(中)

随着互联网的迅猛发展&#xff0c;Web应用的普及程度也愈发广泛。然而&#xff0c;随之而来的是各种安全威胁的不断涌现&#xff0c;其中最为常见而危险的之一就是跨站脚本攻击&#xff08;Cross-Site Scripting&#xff0c;简称XSS&#xff09;。XSS攻击一直以来都是Web安全领…

编程零基础算法 | 四、循环和选择结构——1572. 矩阵对角线元素的和

一、题目链接 1572. 矩阵对角线元素的和 二、题目简介 给你两个整数&#xff0c;n 和 start 。 数组 nums 定义为&#xff1a;nums[i] start 2*i&#xff08;下标从 0 开始&#xff09;且 n nums.length 。 请返回 nums 中所有元素按位异或&#xff08;XOR&#xff09;后…

vueRouter常用属性

vueRouter常用属性 basemodehashhistoryhistory模式下可能会遇到的问题及解决方案 routesprops配置(最佳方案) scrollBehavior base 基本的路由请求的路径 如果整个单页应用服务在 /app/ 下&#xff0c;然后 base 就应该设为 “/app/”,所有的请求都会在url之后加上/app/ new …

通过Python Flask快速构建应用程序

通过Python Flask快速构建应用程序 当你想要快速创建一个简单且轻量级的 Web 应用程序时&#xff0c;Python 的 Flask 框架是一个非常好的选择。Flask 提供了许多有用的功能和扩展&#xff0c;可以帮助你快速搭建一个可靠的 Web 应用程序。本文将向你介绍如何快速入门并开始使…

OpenCvSharpSlim画中文

github地址&#xff1a;https://github.com/AvenSun/OpenCvSharpSlim Slim Build of OpenCvSharp OpenCvSharpSlim This project provides the slim build of OpenCvSharp native library . Currently therere binary packages for OpenCvSharp 2.4.10, 3.4.20 ,4.8.0 and 4…

【物联网与大数据应用】Hadoop数据处理

Hadoop是目前最成熟的大数据处理技术。Hadoop利用分而治之的思想为大数据提供了一整套解决方案&#xff0c;如分布式文件系统HDFS、分布式计算框架MapReduce、NoSQL数据库HBase、数据仓库工具Hive等。 Hadoop的两个核心解决了数据存储问题&#xff08;HDFS分布式文件系统&#…