PTA习题：Data Structures and Algorithms (English)1

preview
试读
23页
doc文档
需积分: 0 0 下载量 139 浏览量 更新于2022-08-08 收藏 388KB DOCX 举报
【知识点详解】 在给定的PTA习题中，我们主要关注的是图论中的两个问题：最短路径问题。这两个问题都是关于找到无向图（第一个问题）或有向图（第二个问题）中从源顶点到所有其他顶点的最短路径。以下是相关的知识点： 1. **图数据结构**： - 在这两个问题中，图被表示为邻接表（Adjacency List）的形式。邻接表是一种存储图的方式，它为每个顶点维护一个链表，链表中的节点表示与该顶点相邻的边。 - `LGraph` 和 `MGraph` 是定义图结构的两种类型，分别用于无权图和有权图。`LGraph` 包含顶点数 `Nv`，边数 `Ne`，以及一个 `AdjList` 数组来存储邻接关系。 - `AdjVNode` 结构体表示邻接表中的节点，包含相邻的顶点 `AdjV` 和指向下一个邻接节点的指针 `Next`。 - `AdjList` 是一个数组，每个元素都是一个 `PtrToAdjVNode` 指针，表示顶点的邻接链表。 2. **最短路径算法**： - 第一个问题要求找到无权图的最短路径，这通常可以使用 Bellman-Ford 算法或 BFS（广度优先搜索）解决。由于题目没有提到边的权重，BFS 是一个合适的解决方案，因为它可以找到无权图的最短路径。 - 第二个问题是带权重的最短路径问题，可以使用 Dijkstra 算法或 Bellman-Ford 算法解决。由于题目保证所有权重都是正的，Dijkstra 算法是更高效的选择，它使用贪心策略，每次选择当前未访问顶点中距离源顶点最近的一个进行扩展。 3. **算法实现**： - 在给出的示例程序中，`ShortestDist` 函数是实现最短路径算法的地方。对于无权图，`ShortestDist` 可能会使用 BFS；对于有权图，可能会使用 Dijkstra 算法。 - `ReadG()` 函数负责读取图的输入，但其具体实现细节被省略了。在实际应用中，这个函数可能需要处理输入格式，例如读取顶点数、边数和边的连接关系。 - `main` 函数中，首先读取图 `G`，然后获取源顶点 `S`，调用 `ShortestDist` 计算最短距离，并将结果打印出来。 4. **样例输入和输出**： - 样例输入给出了一个图的顶点数和边数，以及一系列边的连接信息（在问题2中还有边的权重）。在问题1的样例输出中，-1 表示顶点无法从源顶点到达，其余数字表示从源顶点到相应顶点的最短距离。 - 样例输出显示了计算出的最短距离数组，对应于输入图的每个顶点。 5. **编程语言**： - 这些习题使用 C 语言编写，涉及到的基本编程概念包括结构体、指针、数组、函数等。 理解这些知识点是解答这两个PTA习题的关键。对于实际编程时，需要注意正确地实现图数据结构、选择适当的最短路径算法，以及正确处理输入和输出。同时，确保代码的效率和正确性是至关重要的。
6-11 Shortest Path [1] (25 分)
Write a program to find the unweighted shortest distances from any vertex to a given
source vertex in a digraph.
Format of functions:
void ShortestDist( LGraph Graph, int dist[], Vertex S );
where LGraph is defined as the following:
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
The shortest distance from V to the source S is supposed to be stored in dist[V]. If V
cannot be reached from S, store -1 instead.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
LGraph ReadG(); /* details omitted */
void ShortestDist( LGraph Graph, int dist[], Vertex S );
int main()
{
int dist[MaxVertexNum];
Vertex S, V;
LGraph G = ReadG();
scanf("%d", &S);
ShortestDist( G, dist, S );
for ( V=0; V<G->Nv; V++ )
printf("%d ", dist[V]);
return 0;
}
/* Your function will be put here */
Sample Input (for the graph shown in the figure):
7 9
0 1
0 5
0 6
5 3
2 1
2 6
6 4
4 5
6 5
2
Sample Output:
-1 1 0 3 2 2 1
6-12 Shortest Path [2] (25 分)
Write a program to find the weighted shortest distances from any vertex to a given source
vertex in a digraph. It is guaranteed that all the weights are positive.
Format of functions:
void ShortestDist( MGraph Graph, int dist[], Vertex S );
where MGraph is defined as the following:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
The shortest distance from V to the source S is supposed to be stored in dist[V]. If V
cannot be reached from S, store -1 instead.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define INFINITY 1000000
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
MGraph ReadG(); /* details omitted */
void ShortestDist( MGraph Graph, int dist[], Vertex S );
int main()
{
int dist[MaxVertexNum];
Vertex S, V;
MGraph G = ReadG();
scanf("%d", &S);
ShortestDist( G, dist, S );
for ( V=0; V<G->Nv; V++ )
printf("%d ", dist[V]);
return 0;
}
/* Your function will be put here */
Sample Input (for the graph shown in the figure):
7 9
0 1 1
0 5 1
0 6 1
5 3 1
2 1 2
2 6 3
6 4 4
4 5 5
6 5 12
2
Sample Output:
-1 2 0 13 7 12 3
7-1 Maximum Subsequence Sum（25 分）
Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined
to be { Ni, Ni+1, ..., Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous
subsequence which has the largest sum of its elements. For example, given sequence
{ -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum
being 20.
Now you are supposed to find the largest sum, together with the first and the last
numbers of the maximum subsequence.

剩余22页未读，继续阅读

资源推荐
资源评论
CyberNinja
  • 粉丝: 29
  • 资源: 297
上传资源 快速赚钱
voice
center-task 前往需求广场，查看用户热搜

最新资源