02 - 선형 구조 1 두 개의 질서 있 는 링크 시퀀스 의 합병 (15 분) (단 방향 링크)
2892 단어 데이터 구조의 PTA
함수 인터페이스 정의:
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
/*
* 。。wrong L1,L2 NULL.. 。。。
* Merge() SB Read Print CE..
*/
#include "iostream"
#include "string"
using namespace std;
struct Node {
int Data;
Node* Next;
};
typedef Node* List;
List Merge(List L1, List L2) {
List p = L1->Next;
List q = L2->Next;
List l = (List)malloc(sizeof(struct Node));
l->Next = NULL;
List rear = l;
while (p != NULL && q != NULL) {
if (p->Data <= q->Data) {
rear->Next = p;
rear = p;
p = p->Next;
}
else {
rear->Next = q;
rear = q;
q = q->Next;
}
}
while (p != NULL) {
rear->Next = p;
rear = p;
p = p->Next;
}
while (q != NULL) {
rear->Next = q;
rear = q;
q = q->Next;
}
L1->Next = NULL;
L2->Next = NULL;
return l;
}
List Read() { //
List p = (List)malloc(sizeof(struct Node));
List rear = p;
p->Next = NULL;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int Data;
scanf("%d", &Data);
List q = (List)malloc(sizeof(struct Node));
q->Next = NULL;
q->Data = Data;
rear->Next = q;
rear = rear->Next;
}
return p;
}
void Print(List l) { //
l = l->Next;
while(l){
cout << l->Data <Next;
}
cout << endl;
}
int main() {
List l1, l2;
List p;
l1 = Read();
l2 = Read();
p = Merge(l1,l2);
Print(p);
return 0;
}