PTA - 절강대학 교 일부 데이터 구조 문제 분석

이분 찾기
함수 인터페이스 정의:

 Position BinarySearch( List L, ElementType X );

그 중에서 List 구 조 는 다음 과 같다.

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /*                 */
};

L 은 사용자 가 들 어 오 는 선형 표 입 니 다. 그 중에서 Element Type 요 소 는 >, =,
심판 테스트 프로그램 샘플:

#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("%d
", 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 은 사용자 가 들 어 오 는 선형 표 입 니 다. 그 중에서 Element Type 요 소 는 >, =,
심판 테스트 프로그램 샘플:

#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.
");
    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;
} 

관광 계획
입력 형식: 입력 설명: 입력 데이터 의 첫 번 째 줄 은 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);
            temp.cost = c;
            temp.next = b;
            temp.dis = d;
            edge[a].push_back(temp);
            temp.next = 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 %d
",dis[T],cost[T]);
    }
    return 0;
}