单链表的两种合并操作（C语言）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了单链表的两种合并操作（C语言），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3504字，纯文字阅读大概需要6分钟。

内容图文

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

/**
* 含头节点单链表定义及基本操作 
*/

//基本操作函数用到的状态码 
#define TRUE 1;
#define FALSE 0;
#define OK 1;
#define ERROR 0;

//Status函数返回值类型
typedef int Status; 
//数据元素类型
typedef int ElemType;
//单链表定义
typedef struct Lnode {
    ElemType data;        //数据域
    struct Lnode *next;    //指针域
} Lnode, *LinkList;


//基本操作1：单链表初始化 
Status InitList(LinkList *list) { 
    (*list)=(LinkList)malloc(sizeof(Lnode));
    (*list)->next=NULL;
    return OK;
}

//基本操作11：头插法建立链表，数据保存在ElemType类型的数组中 
Status CreateList_H(LinkList *list,ElemType arrData[],int length) {
    int j;
    for(j=length-1;j>=0;j--){
        //新建结点 
        Lnode *node;
        node=(Lnode*)malloc(sizeof(Lnode));
        node->data=arrData[j];
        node->next=NULL;
        //插入为1号结点 
        node->next=(*list)->next;
        (*list)->next=node;
    }
    return OK;
}

//基本操作13：链表元素遍历输出
Status ListTraverse(LinkList list) {
    Lnode *p;
    p=list;
    int j=0;
    printf("序号：    结点数据：\n");
    while(p->next){
        j++;
        p=p->next;
        printf(" (%d)          %d\n",j,p->data);
    }
    return OK;
}

//有序表合并，顺序表实现。pa,pb分别指向listA,listB首元,pc指向新链表表尾
Status MergeList(LinkList *listA,LinkList *listB) {
    Lnode *pa,*pb,*pc;
    pa=(*listA)->next;
    pb=(*listB)->next;
    pc=*listA;
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        } else {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    //插入剩余表段
    pc->next=pa?pa:pb;
    //释放listB头结点
    free(*listB);
    return OK;
}

//线性表合并，顺序表实现。pa,pb分别指向listA,listB首元
Status UnionList(LinkList *listA,LinkList *listB){
    Lnode *pa,*pb;  //ra将指向listA尾结点
    pa=(*listA);
    pb=(*listB);
    
    while(pb->next){
        ElemType data=pb->next->data;
        while(pa->next&&pa->next->data!=data){
            pa=pa->next;
        }
        if(pa->next&&pa->next->data==data){  //listA中有目标元素
            Lnode *needDelete=pb->next;
            pb->next=needDelete->next;
            free(needDelete);  //释放listB中的该结点
        } else {
            Lnode *needInsert=pb->next;  //pb->next指向当前结点
            //将该结点接入listA尾
            pa->next=needInsert;  //此时pa为listA的尾指针
            pb->next=pb->next->next;
            needInsert->next=NULL;  //listA的 最后结点->next 置空
        }
        pa=(*listA)->next;
    }
    free(*listB);  //释放listB头结点
    return OK;
}

/**
 * 已知线性表:
 * list1=(1,7,8),list2=(2,4,6,8,10,11)
 * 有序表合并:(这里为两个非递减线性表list1,list2;合并为一个非递减线性表,仍作为list1);
 * 则新的:list1=(1,2,4,6,7,8,8,10,11)
 * 线性表合并:(合并结果放入list1，“list1 并= list2”)
 * 则新的:list1=(1,7,8,2,4,6,10,11)
 */

int main(void){
    //定义链表
    LinkList list1,list2,list3,list4;
    
    //链表初始化
    InitList(&list1);
    InitList(&list2);
    InitList(&list3);
    InitList(&list4);
    
    //创建链表
    ElemType waitInserted1[]={1,7,8,};
    ElemType waitInserted2[]={2,4,6,8,10,11,};
    ElemType waitInserted3[]={1,7,8,};
    ElemType waitInserted4[]={2,4,6,8,10,11,};
    int arrLength1=sizeof(waitInserted1)/sizeof(waitInserted1[0]);
    int arrLength2=sizeof(waitInserted2)/sizeof(waitInserted2[0]);
    int arrLength3=sizeof(waitInserted3)/sizeof(waitInserted3[0]);
    int arrLength4=sizeof(waitInserted4)/sizeof(waitInserted4[0]);
    CreateList_H(&list1,waitInserted1,arrLength1);
    CreateList_H(&list2,waitInserted2,arrLength2);
    CreateList_H(&list3,waitInserted3,arrLength3);
    CreateList_H(&list4,waitInserted4,arrLength4);
    
    /*
    printf("\nlist1：\n");
    ListTraverse(list1);
    printf("\nlist2：\n");
    ListTraverse(list2);
    printf("\nlist3：\n");
    ListTraverse(list4);
    printf("\nlist3：\n");
    ListTraverse(list4);
    */
    
    //有序表合并
    MergeList(&list1,&list2);
    printf("\nlist1：(与list2经过有序表合并后)\n");
    ListTraverse(list1);  //遍历测试
    
    //线性表合并
    UnionList(&list3,&list4);
    printf("\nlist3：(与list4经过线性表表合并后)\n");
    ListTraverse(list3);  //遍历测试
    
    printf("\nEND");
    return 0;
}

内容总结

以上是互联网集市为您收集整理的单链表的两种合并操作（C语言）全部内容，希望文章能够帮你解决单链表的两种合并操作（C语言）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端