c语言顺序表的简历，合并，归并算法实现解决办法

c语言顺序表的简历，合并，归并算法实现
线性表LA=(3,5,8,11),LB=(2,6,8,9,11,15,20);要求用顺序表实现，给出所用数据类型中每个操作的伪码算法（1），若LA和LB分别表示两个集合A和B，求新集合A=A∪B,（即“并”操作，相同元素不保留）；预测输出
LA=（3，5，8，11，2，6，9，5，20）。
（2）将LA与LB表归并，仍要有序，相同元素要保留，预测输出LC=（2，3，5，6，8，9，11，15，20）。

------解决方案--------------------

C/C++ code


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}linkNode, *linklist;

/*
*功能:初始化链表
*返回值:链表首地址
*/
linklist initList()
{
    linklist head;
    head = (linklist)malloc(sizeof(linkNode));
    if(head == NULL)
        return NULL;
    head->next = NULL;
    return head;
}

/*
*功能:输出链表数据
*参数:链表首地址
*/
void printList(linklist head)
{
    if(head == NULL || head->next == NULL)
        return;
    head = head->next;
    printf("\nlinklist:\n");
    while(head != NULL)
    {
        printf("%d  ", head->data);
        head = head->next;
    }
    printf("\n");

}
/*
*功能:申请空间
*参数:结点(数据)
*返回值:指向结点的指针
*/
linklist makeNode(linkNode nodeData)
{
    linklist newNode;
    newNode = (linklist)malloc(sizeof(linkNode));
    if(newNode == NULL)
        return NULL;
    newNode->data = nodeData.data;
    return newNode;
}


/*
*功能:在链表尾部插入结点
*参数:链表首地址,待插入结点地址
*/
void pushBack(linklist head, linklist insertNode)
{
    if(head == NULL)
        return;
    while(head->next != NULL)
    {
        head = head->next;
    }
    head->next = insertNode;
    insertNode->next = NULL;
}

/*
*功能：合并链表
*参数：两个链表首地址,合并后链表首地址
*/
void mergeLink(linklist La, linklist Lb, linklist Lc)
{
    La = La->next;
    Lb = Lb->next;
    while (La && Lb)
    {
        if (La->data > Lb->data)//将data较小的连接到Lc
        {
            Lc->next = Lb;
            Lb = Lb->next;
        }
        else if(La->data == Lb->data)
        {
            Lc->next = La;
            La = La->next;
            Lb = Lb->next;            
        }
        else
        {
            Lc->next = La;
            La = La->next;            
        }
        Lc = Lc->next;        
    }
    Lc->next = La ? La : Lb;//将La 或 Lb剩下的部分连接到Lc
}

int main()
{
    linklist La, Lb, Lc,insertNode;
    linkNode newNode;
    int dataA[] = {3,5,8,11};
    int dataB[] = {2,6,8,9,11,15,20};
    int i;
    La = initList();
    Lb = initList();
    Lc = initList();
    for(i = 0; i < 4; ++i)
    {
        newNode.data = dataA[i];
        insertNode = makeNode(newNode);        
        pushBack(La, insertNode);
    }
    for(i = 0; i < 7; ++i)
    {
        newNode.data = dataB[i];
        insertNode = makeNode(newNode);        
        pushBack(Lb, insertNode);
    }
    printList(La);
    printList(Lb);
    mergeLink(La, Lb, Lc);
    printList(Lc);
    system("pause");
    return 0;
}

c语言顺序表的简历，合并，归并算法实现解决办法

相关推荐