兰州市城乡建设局网站s104项目,常州有哪些做阿里巴巴网站的,网站建设数据库建设,深圳网络推广哪家6-1 递增的整数序列链表的插入
本题要求实现一个函数#xff0c;在递增的整数序列链表#xff08;带头结点#xff09;中插入一个新整数#xff0c;并保持该序列的有序性。
答案#xff1a; 语言选C(gcc)
List Insert(List L, ElementType X) {List tmp (List) mal…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-DataX) {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[MaxVertexNum1] {};int size 0;q[size] S;Visited[S] true;while (size ! 0) {int tmp q[0];for (int i 1; i size1; 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, vectorint, greaterint Q;int N, x, a, b, ans 0;cinN;for(int i 0;i N;i){cinx;Q.push(x);}for(int i 0;i N-1;i){a Q.top();Q.pop();b Q.top();Q.pop();Q.push(ab);ans ab;}coutansendl;return 0;
}7-3 公路村村通
现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N≤1000和候选道路数目M≤3N随后的M行对应M条道路每行给出3个正整数分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见城镇从1到N编号。
语言选c
//Prim算法
#includeiostream
#includestdio.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 N1;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 N1;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;
}
