剣指OFFERの合併秩序チェーンテーブル(九度OJ 1519)


タイトルの説明:


2つの単調に増加したチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.(hint:チェーンテーブルは必ず使用してください.)
 
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各試験例について、入力される第1の動作の2つの整数nおよびm(0<=n<=1000、0<=m<=1000):nは、入力される第1のチェーンテーブルの要素の個数を表し、mは、入力される第2のチェーンテーブルの要素の個数を表す.次の行は、チェーンテーブル1の要素を表すn個の数t(1<=t<=1000000)を含む.次の行には、m個の要素、s(1<=t<=1000000)が含まれます.
 
出力:
各テストケースに対応し、結果があれば対応するチェーンテーブルを出力します.そうでなければNULLを出力します.
 
サンプル入力:
5 2

1 3 5 7 9

2 4

0 0

 
サンプル出力:
1 2 3 4 5 7 9

NULL

 

問題解決の考え方:


まず2つの秩序あるチェーンテーブルが与えられると、p 1はチェーンテーブル1、p 2はチェーンテーブル2、p 3は連結後のチェーンテーブル3を指す3つのポインタを用いることが考えられる.では、チェーンテーブル1と2を順次走査し、小さい要素をp 3の後ろに置くたびに、p 3はチェーンテーブル3の尾を指す.最後によく考えなければならない問題:
1両方のチェーンテーブルが空の場合
if(n1 == 0 && n2 == 0)

            printf("NULL
");

 
2いずれかのチェーンテーブルが空の場合
    if(head1->next == NULL){

        res->next = head2->next;

        return ;

    }

    if(head2->next == NULL){

        res->next = head1->next;

        return ;

    }

 
3チェーンテーブルを事前にスキャンした場合
        Node *p1;

    Node *p2;

    Node *p3 = res;

    while(head1->next != NULL && head2->next != NULL){

        p1 = head1->next;

        p2 = head2->next;

        if(p1->number < p2->number){

            head1->next = p1->next;

            p1->next = p3->next;

            p3->next = p1;

            p3 = p3->next;

        }else{

            head2->next = p2->next;

            p2->next = p3->next;

            p3->next = p2;

            p3 = p3->next;

        }

    }

    if(head1->next == NULL)

        p3->next = head2->next;

    if(head2->next == NULL)

        p3->next = head1->next;    

 
この3つの問題を解決すると、チェーンテーブルのソートが完了します.

コード:

#include <stdio.h>

#include <stdlib.h>

typedef struct node{

    int number;

    struct node * next;

}Node;

void mergeList(Node *res,Node *head1,Node *head2);

int main(){

    int n1,n2;

    int i;

    int temp;

    while(scanf("%d %d",&n1,&n2)!=EOF && n1>=0 && n1<=1000 && n2>=0 && n2<=1000){

        Node *head1 = (Node *)malloc(sizeof(Node));

        Node *head2 = (Node *)malloc(sizeof(Node));

        head1->next = NULL;

        head2->next = NULL;

        Node *tail1 = head1;

        Node *tail2 = head2;

        for(i=0;i<n1;i++){

            scanf("%d",&temp);

            Node *p = (Node *)malloc(sizeof(Node));

            p->next = tail1->next;

            tail1->next = p;

            p->number = temp;

            tail1 = tail1->next;

        }

        for(i=0;i<n2;i++){

            scanf("%d",&temp);

            Node *p = (Node *)malloc(sizeof(Node));

            p->next = tail2->next;

            tail2->next = p;

            p->number = temp;

            tail2 = tail2->next;

        }

        Node *res = (Node *)malloc(sizeof(Node));

        mergeList(res,head1,head2);

        if(n1 == 0 && n2 == 0)

            printf("NULL
"); else{ Node *p = res->next; printf("%d",p->number); p = p->next; while(p != NULL){ printf(" %d",p->number); p = p->next; } printf("
"); } } return 0; } void mergeList(Node *res,Node *head1,Node *head2){ if(head1->next == NULL){ res->next = head2->next; return ; } if(head2->next == NULL){ res->next = head1->next; return ; } Node *p1; Node *p2; Node *p3 = res; while(head1->next != NULL && head2->next != NULL){ p1 = head1->next; p2 = head2->next; if(p1->number < p2->number){ head1->next = p1->next; p1->next = p3->next; p3->next = p1; p3 = p3->next; }else{ head2->next = p2->next; p2->next = p3->next; p3->next = p2; p3 = p3->next; } } if(head1->next == NULL) p3->next = head2->next; if(head2->next == NULL) p3->next = head1->next; return ; } /************************************************************** Problem: 1519 User: xhalo Language: C Result: Accepted Time:250 ms Memory:4212 kb ****************************************************************/