怎样把两个有序的顺序表合并后还是有序的?

Question

怎样把两个有序的顺序表合并后还是有序的?

Answer 1

// 下面的程序代码用于集合的交、并运算,请仔细阅读.

#include <iostream>

#include <iomanip>

#include <time.h>

using namespace std;

typedef struct link {

\x09short num;

\x09struct link *next;

}AGG;

AGG *CreateList(int n) { // 创建结点数为n的链表,返回链表头

\x09AGG *head,*p,*q;

\x09head = p = new AGG;

\x09head->num = 0;

\x09for(short i = 0;i < n;i++) {

\x09\x09q = new AGG;

\x09\x09q->num = (unsigned)rand() % n + n/2;

\x09\x09p->next = q;

\x09\x09p = q;

\x09}

\x09p->next = head;

\x09return head;

}

void RiseSort(AGG *head) { // 上升排序

\x09AGG *p,*s,*pt; 

\x09p = head;

\x09s = p->next;

\x09while(p->next != head) {

\x09\x09while(s->next != head) {

\x09\x09\x09if(p->next->num > s->next->num) {

\x09\x09\x09\x09pt = p->next;

\x09\x09\x09\x09p->next = s->next;

\x09\x09\x09\x09s->next = p->next->next;

\x09\x09\x09\x09p->next->next = pt;

\x09\x09\x09}

\x09\x09\x09else s = s->next;

\x09\x09}

\x09\x09p = p->next;

\x09\x09s = p->next;

\x09}

}

void Simplification(AGG *head) { // 去除相同的集合元素

\x09AGG *p,*q,*s;

\x09p = head->next;

\x09q = p->next;

\x09while(q != head) {

\x09\x09if(p->num == q->num) {

\x09\x09\x09p->next = q->next;

\x09\x09\x09s = q;

\x09\x09\x09q = q->next;

\x09\x09\x09delete s;

\x09\x09}

\x09\x09else {

\x09\x09\x09p = p->next;

\x09\x09\x09q = q->next;

\x09\x09}

\x09}

}

AGG *CreateAgg(int n) {

\x09AGG *head;

\x09head = CreateList(n);

\x09RiseSort(head);;

\x09Simplification(head);

\x09return head;

}

void InsertNode(AGG *head,short num) {

\x09AGG *t,*p = head;

\x09while(p->next != head) {

\x09\x09if(p->next->num == num) return; 

\x09\x09if(p->next->num < num) p = p->next;

\x09\x09else {

\x09\x09\x09t = new AGG[1];

\x09\x09\x09t->num = num;

\x09\x09\x09t->next = p->next;

\x09\x09\x09p->next = t;

\x09\x09\x09return;

\x09\x09}

\x09}

\x09t = new AGG[1];

\x09t->num = num;

\x09p->next = t; 

\x09t->next = head;     // 插入在链表尾的处理

}

AGG *MergeAgg(AGG *A,AGG *B) {  // A∪B

\x09AGG *head,*pa,*pb,*pc,*qc;

\x09head = pc = new AGG;

\x09pa = A->next;

\x09while(pa != A) {

\x09\x09qc = new AGG[1];

\x09\x09qc->num = pa->num;

\x09\x09pc->next = qc;

\x09\x09pc = qc;

\x09\x09pa = pa->next;

\x09}

\x09pc->next = head;

\x09pb = B->next;

\x09while(pb != B) {

\x09\x09InsertNode(head,pb->num);

\x09\x09pb = pb->next;

\x09}

\x09return head;

}

AGG *MutualAgg(AGG *A,AGG *B) {  // A∩B

\x09AGG *C,*pa,*pb,*pc,*qc;

\x09C = pc = new AGG;

\x09pc->num = 0;

\x09pa = A->next;

\x09pb = B;

\x09while(pa != A) {

\x09\x09pb = B->next;

\x09\x09while(pb != B) {

\x09\x09\x09if(pb->num == pa->num) {

\x09\x09\x09\x09qc = new AGG;

\x09\x09\x09\x09qc->num = pb->num;

\x09\x09\x09\x09pc->next = qc;

\x09\x09\x09\x09pc = qc;

\x09\x09\x09}

\x09\x09\x09pb = pb->next;

\x09\x09}

\x09\x09pa = pa->next;

\x09}

\x09pc->next = C;

\x09return C;

}

void PrintList(AGG *head) {

\x09AGG *p = head->next;

\x09short counter = 0;

\x09while(p != head) {

\x09\x09if(counter%10 == 0) cout << endl;

\x09\x09cout<<setw(5)<< p->num;

\x09\x09counter++;

\x09\x09p = p->next;

\x09}

\x09cout << endl;

}

void freeheap(AGG *head) {

\x09AGG *p,*q;

\x09p = head;

\x09q = p->next;

\x09while(q != head) {

\x09\x09p = q;

\x09\x09q = p->next;

\x09\x09delete p;

\x09}

\x09free(head);

}

int main() {

\x09AGG *A,*B,*C,*D;

\x09srand(time(NULL));

\x09A = CreateAgg(50);

\x09cout << "集合A的元素有:";

\x09PrintList(A);

\x09B = CreateAgg(50);

\x09cout << endl << endl << "集合B的元素有:";

\x09PrintList(B);

\x09C = MutualAgg(A,B);

\x09cout << endl << endl << "C = A∩B:" << endl;

\x09PrintList(C);

\x09cout << endl << endl << "D = A∪B : " << endl;

\x09D = MergeAgg(A,B);

\x09PrintList(D);

\x09freeheap(A);

\x09freeheap(B);

\x09freeheap(C);

\x09freeheap(D);

\x09printf("\n\n");

\x09return 0;

}