服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言中数据结构之链表归并排序实例代码

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

2021-05-13 12:21将进酒-杯莫停 C/C++

这篇文章主要介绍了C语言中数据结构之链表归并排序实例代码的相关资料,需要的朋友可以参考下

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

问题

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

源程序

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#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语言中数据结构之链表归并排序实例代码

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

原文链接:http://blog.csdn.net/johnwcheung/article/details/50815932

延伸 · 阅读

精彩推荐