PTA ——浙江大学部分数据结构题目解析

PTA ——浙江大学部分数据结构题目解析

二分查找

函数接口定义：

 Position BinarySearch( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );int main()
{List L;ElementType X;Position P;L = ReadInput();scanf("%d", &X);P = BinarySearch( L, X );printf("%dn", P);return 0;
}/* 你的代码将被嵌在这里 */

输入输出样例

输入样例1：5
12 31 55 89 101
31输出样例1：2输入样例2：3
26 78 233
31输出样例2：0

解析

Position BinarySearch (List L ,ElementType X){int low=1,mid=1;int high=L->Last;while(low<=high){mid=(low+high)/2;if(X==L->Data[mid])return mid;else if (X<L->Data[mid])high=mid-1;else low=mid+1;}return NotFound;
} 

有序数组的插入

函数接口定义：

bool Insert( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置，以保持结果依然有序（注意：元素从下标0开始存储）。但如果X已经在Data[]中了，就不要插入，返回失败的标记false；如果插入成功，则返回true。另外，因为Data[]中最多只能存MAXSIZE个元素，所以如果插入新元素之前已经满了，也不要插入，而是返回失败的标记false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
bool Insert( List L, ElementType X );int main()
{List L;ElementType X;L = ReadInput();scanf("%d", &X);if ( Insert( L, X ) == false )printf("Insertion failed.n");PrintList( L );return 0;
}/* 你的代码将被嵌在这里 */

输入输出样例

输入样例1：5
35 12 8 7 3
10输出样例1：35 12 10 8 7 3
Last = 5输入样例2：6
35 12 10 8 7 3
8输出样例2：Insertion failed.
35 12 10 8 7 3
Last = 5

解析

bool Insert (List L ,ElementType X){if (L->Last+1==MAXSIZE)return false;for(int i=0;i<=L->Last;i++){if(L->Data[i]==X)return false;else if(L->Data[i]<X){for(int j=L->Last;j>=i;j--){L->Data[j+1]=L->Data[j]; }L->Data[i]=X;L->Last=L->Last+1;break;}else if(i==L->Last&&L->Data[i]>X){L->Data[L->Last+1]=X;L->Last=L->Last+1;break;}}return true;
} 

旅游规划

输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40

解析(C语言版）

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;struct E
{int next;int cost;int dis;
};
vector<E> edge[501];
bool mark[501];
int dis[501];
int cost[501];int main()
{int n,m,S,T;  int i,j;E temp;int newP;while( scanf("%d%d%d%d",&n,&m,&S,&T)!=EOF){if( n==0 && m==0) break;for( i=0; i<=n; i++){edge[i].clear();   dis[i] = -1;mark[i] = false;cost[i] = 0;}while( m--){int a,b,d,c;scanf("%d%d%d%d",&a,&b,&d,&c);st =  = b;temp.dis = d;edge[a].push_back(temp); = a;edge[b].push_back(temp);  /}dis[S] = 0;mark[S] = 1;newP = S;  for( i=1; i<n; i++){for( j=0; j<edge[newP].size(); j++){int next = edge[newP][j].next;int c = edge[newP][j].cost;int d = edge[newP][j].dis;if( mark[next]==true) continue;if( dis[next]==-1 || dis[next]>dis[newP]+d|| ((dis[next]==dis[newP]+d) &&(cost[next]>cost[newP]+c))){dis[next] = dis[newP]+d;cost[next] = cost[newP]+c;}}int minx = 66666666;for( j=0; j<=n; j++){if( mark[j]==true) continue;if( dis[j]==-1) continue;if( dis[j]<minx){minx = dis[j];newP = j;}}mark[newP] = true;}printf("%d %dn",dis[T],cost[T]);}return 0;
}