C语言,求一段归并很有序线性表的完整代码,原有的两个线性表的元素要手动输入。

2026年09月27日 12:39
有1个网友回答
网友(1):

#include 
#include 
  
typedef int DataType;
  
typedef struct list {
    DataType data;
    struct list *next;
}*LinkList,*pNode;
  
LinkList GetEmptyList() {
    LinkList head = (pNode)malloc(sizeof(struct list));
    head->data = 0;
    head->next = 0;
    return head;
}
 

// 将data插入到增序表head中,用来创建链表
void InsertNode(LinkList head, DataType data) {
    pNode p,q = (pNode)malloc(sizeof(struct list));
    int flag = 1;
    q->data = data;
    for(p = head; p->next && flag; p = p->next) {
if(p->next->data == data) {
printf("域值%d已经存在,本次插入作废!\n",data);
free(q);
return;
}
        if(p->next->data > data) {
            q->next = p->next;
            p->next = q;
            flag = 0;
        }
    }
    if(flag) {
        p->next = q;
        q->next = NULL;
    }
}
 
LinkList CopyList(LinkList head) {
    pNode p,q;
    LinkList headcpy = q = GetEmptyList();
    for(p = head->next; p; p = p->next) {
        q->next = (pNode)malloc(sizeof(struct list));
        q->next->data = p->data;
        q = q->next;
    }
    q->next = NULL;
    return headcpy;
}
  
// 合并 heada 和 headb 到 headc 
LinkList MergeList(LinkList heada, LinkList headb) {
    pNode p,q,t;
    int flag;
    LinkList headc = CopyList(heada);
    for(p = headb->next; p; p = p->next) {
        t = (pNode)malloc(sizeof(struct list));
        t->data = p->data;
        flag = 1;
        for(q = headc; q->next && flag; q = q->next) {
    if(p->data == q->next->data) flag = 0;
            else if(p->data < q->next->data) {
                t->next = q->next;
                q->next = t;
                flag = 0;
            }
        }
        if(flag) {
            q->next = t;
            t->next = NULL;
        }
    }
    return headc;
}
 
// 在表中查找data,找到返回结点的地址,否则返回NULL
pNode Find(LinkList head,DataType data) {
    pNode p = head->next;
    while(p) {
        if(p->data == data) return p;
        p = p->next;
    }
    return NULL;
}
 
int GetLength(LinkList head) {
    int len = 0;
    pNode p = head->next;
    while(p) {
        ++len;
        p = p->next;
    }
    return len;
}
  
void ShowList(LinkList head) {
    pNode p;
    for(p = head->next; p; p = p->next)
        printf("%d ",p->data);
    printf("\n");
}
  
int main() {
    LinkList ListA,ListB,ListC;
    DataType t;
  
    printf("创建ListA:\n");
    ListA = GetEmptyList();
    printf("输入一个整数('q' to quit):\n");
    while(scanf("%d",&t) == 1) {
        InsertNode(ListA,t);
        printf("输入一个整数('q' to quit):\n");
    }
    ShowList(ListA);
    printf("ListA的长度:%d\n",GetLength(ListA));
  
    fflush(stdin); // 'q'退出后,键盘输入缓冲区中有残留数据
      
    printf("创建ListB:\n");
    ListB = GetEmptyList();
    printf("输入一个整数('q' to quit):\n");
    while(scanf("%d",&t) == 1) {
        InsertNode(ListB,t);
        printf("输入一个整数('q' to quit):\n");
    }
    ShowList(ListB);
    printf("ListB的长度:%d\n",GetLength(ListB));
  
    printf("ListC = ListA ∪ ListB:\n");
    ListC = MergeList(ListA,ListB);
    ShowList(ListC);
    printf("ListC的长度:%d\n",GetLength(ListC));
    return 0;
}