请写出在头指针为La,Lb的两个递减有序的单链表合并为一个递减有序的单链表的算法

发布网友 发布时间：2022-07-21 19:28

我来回答

共1个回答

热心网友 时间：2023-10-31 21:47

#include <stdio.h>
#include <stdlib.h>
 
typedef int Elemtype;
typedef struct node {
    Elemtype data;
    struct node *next;
}NODE,*LinkList,*pNode;
 
LinkList GetNewList() {
    pNode head = (pNode)malloc(sizeof(NODE));
    if(head == NULL) return NULL;
    head->data = 0;
    head->next = NULL;
    return head;
}
 
LinkList merge(LinkList LA,LinkList LB) {
    pNode a,b,c,head;
    a = LA;
    b = LB;
    c = head = GetNewList();
    head->data = LA->data + LB->data;
    while(a->next && b->next) {
        c->next = (pNode)malloc(sizeof(NODE));
        if(c->next == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        if(a->next->data >= b->next->data) {
            c->next->data = a->next->data;
            a = a->next;
        }
        else {
            c->next->data = b->next->data;
            b = b->next;
        }
        c = c->next;
    }
    while(a->next) {
        c->next = (pNode)malloc(sizeof(NODE));
        if(c->next == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        c->next->data = a->next->data;
        a = a->next;
        c = c->next;
    }
    while(b->next) {
        c->next = (pNode)malloc(sizeof(NODE));
        if(c->next == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        c->next->data = b->next->data;
        b = b->next;
        c = c->next;
    }
    c->next = NULL;
    return head;
}
 
LinkList Creat(LinkList head,int a[],int n) {
    int i;
    pNode p = head;
    head->data = n;
    for(i = 0; i < n; ++i) {
        p->next = (pNode)malloc(sizeof(NODE));
        if(p->next == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        p->next->data = a[i];
        p = p->next;
    }
    p->next = NULL;
    return head;
}
 
void Show(LinkList head) {
    pNode p = head->next;
    while(p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
 
int main( ) {
    Elemtypea[] = {98,89,86,80,76,69,68,54,50,29};
    int m = sizeof(a)/sizeof(a[0]);
    Elemtype b[] = {96,85,74,69,68,67,65,60,58};
    int n = sizeof(b)/sizeof(b[0]);
    LinkList LA = GetNewList();
    LA = Creat(LA,a,m);
    LinkList LB = GetNewList();
    LB = Creat(LB,b,n);
    LinkList LC;
    printf("LA: ");
    Show(LA);
    printf("LB: ");
    Show(LB);
    LC = merge(LA,LB);
    printf("LC: ");
    Show(LC);
    return 0;
}