C语言中数据结构之链表归并排序实例代码

C语言中数据结构之链表归并排序实例代码

问题

设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增排序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

源程序

#include <stdio.h> 
#include<stdlib.h> 
#define N1 6 /*链表La的长度*/  
#define N2 6 /*链表Lb的长度*/ 
struct listnode  
{ 
 int data; 
 struct listnode *next; 
}; 
void createlist(struct listnode * *,int);  
void listinsert(struct listnode * *,struct listnode * *); 
void readlist(struct listnode *); 
int main() 
{ 
  
 struct listnode *ha=NULL,*hb=NULL; 
 printf("请按照升序序列输入以下数字以建立链表La\n"); 
 printf("Please Input %d numbers:",N1); 
 createlist(&ha,N1); 
 printf("请按照升序序列输入以下数字以建立链表Lb\n"); 
 printf("Please Input %d numbers:",N2); 
 createlist(&hb,N2); 
 listinsert(&ha,&hb); 
 readlist(ha); 
 printf("\n");  
} 
 
 
void createlist(struct listnode * *p,int n) 
{ /*尾插法建立链表*/ 
 struct listnode *t,*q; 
 int i; 
 t=(struct listnode *)malloc(sizeof(struct listnode)); 
 scanf("%d",&t->data); 
 *p=t; 
 q=t;  
 for(i=n-1;i>0;i--) 
    { 
 t=(struct listnode *)malloc(sizeof(struct listnode)); 
 scanf("%d",&t->data); 
 q->next=t; 
 q=t; 
  } 
 q->next=NULL; 
} 
 
void listinsert(struct listnode * *a,struct listnode * *b)  
{ /*将两个链表按递增序列排序*/ 
 struct listnode *pa,*pb,*other,*la,*pre; 
 la=(struct listnode *)malloc(sizeof(struct listnode)); 
 la->next=*a; 
 pa=*a;    
 pb=*b; 
 pre=la;   
 while(pa&&pb) 
  { 
 if(pa->data<pb->data) 
   {   
  pre=pre->next; 
  pa=pa->next; 
  } 
 else if (pa->data>pb->data) 
 { 
  other=(struct listnode *)malloc(sizeof(struct listnode)); 
  other->data=pb->data; 
  other->next=pa; 
  pre->next=other; 
  pre=other; 
  pb=pb->next; 
   } 
  
 else 
 { 
  pre=pre->next; 
  pa=pa->next; 
  pb=pb->next; 
  } 
 } 
  
 if(!pa) 
 { 
 while(pb) 
 { 
  other=(struct listnode *)malloc(sizeof(struct listnode)); 
  other->data=pb->data;   
        pre->next=other; 
  pre=pre->next; 
  pb=pb->next; 
 } 
 pre->next=NULL; 
 } 
 *a=la->next; 
 free(la); 
} 
 
void readlist(struct listnode *p) 
{ /*遍历链表并输出最终结果*/ 
 struct listnode *q; 
 q=p; 
 printf("链表的排序结果为:\n"); 
 while(q!=NULL) 
   { 
 printf("%3d",q->data); 
 q=q->next; 
 } 
 printf("\n"); 
}

运行结果

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# 数据结构之链表归并排序 # C语言链表归并排序 # c语言实现的几种常用排序算法 # C语言实现单链表的快速排序算法 # C语言中的结构体快排算法 # 链表 # 升序 # 也有 # 遍历 # 数据结构 # 希望能 # 分别为 # 谢谢大家 # 中不 # 不归 # 无头 # 并到 # 链中 # pre # gt # include # cpp # lt # brush # class

返回目录在线咨询

上一篇：购买域名后，如何将它与WordPress主机绑定？
下一篇：Vim 中 Go 语言语法高亮配置与排查指南

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C语言中数据结构之链表归并排序实例代码

您的项目需求