データ構造の授業後の練習問題(練習二)練習問題の2.5つの順序付きチェーンの連結(15分)
4613 ワード
本題は一つの関数を実現して、二つのチェーンが表しているインクリメントされた整数系列を一つのインクリメントされていない整数系列にマージします.
関数インターフェースの定義:
審判試験手順の例:
関数インターフェースの定義:
List Merge( List L1, List L2 );
Listの構造定義は以下の通りである.typedef struct Node *PtrToNode; struct Node { ElementType Data; /* */ PtrToNode Next; /* */ }; typedef PtrToNode List; /* */ L1およびL2は、所与の率先ノードの単一のチェーンテーブルであり、そのノードに格納されたデータは、インクリメント順序である.関数Mergeは、L1およびL2を非逓減整数シーケンスにマージする.元のシーケンスの結点を直接使用して、帰結後の先頭結点のチェーンポインタを返します.審判試験手順の例:
#include
#include typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* */ void Print( List L ); /* ； NULL */ List Merge( List L1, List L2 ); int main() { List L1, L2, L; L1 = Read(); L2 = Read(); L = Merge(L1, L2); Print(L); Print(L1); Print(L2); return 0; } /* */ 3
1 3 5
5
2 4 6 8 10
1 2 3 4 5 6 8 10 NULL NULL
List Merge(List L1,List L2){
List p1=L1,p2=L2;
L1=L1->Next;L2=L2->Next;
List res=(List)malloc(sizeof(List));
List tmp=res;
while(L1!=NULL&&L2!=NULL){
if((L1->Data)Data)){
tmp->Next=L1;
L1=L1->Next;
tmp=tmp->Next;
}else{
tmp->Next=L2;
L2=L2->Next;
tmp=tmp->Next;
}
}
if(L1!=NULL) tmp->Next=L1;
if(L2!=NULL) tmp->Next=L2;
p1->Next=NULL;
p2->Next=NULL;
return res;
}