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");
}

运行结果

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

(0)

相关推荐

  • 数据结构之归并排序的实例详解

    归并排序 基本思想         归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列:即先使每个子序 列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表:将这些有序序列 再次归并,得到n/4个长度为4的有序序列:如此反复进行下去,最后得到一个长度为n的有序序列.所以呢,我们总结一下归并排序 其实就只有两步:

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • 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的

  • 列举java语言中反射的常用方法及实例代码

    Java反射机制 一.什么是反射机制  简单的来说,反射机制指的是程序在运行时能够获取自身的信息.在java中,只要给定类的名字,     那么就可以通过反射机制来获得类的所有信息. 二.哪里用到反射机制  有些时候,我们用过一些知识,但是并不知道它的专业术语是什么,在刚刚学jdbc时用过一行代码,     Class.forName("com.mysql.jdbc.Driver.class").newInstance();但是那时候只知道那行代码是生成     驱动对象实例,并不知道

  • 数据结构 C语言实现循环单链表的实例

    数据结构 C语言实现循环单链表的实例 实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环

  • C语言中数据结构之链式基数排序

    C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int ElemType; #define MAX_NUM_OF_KEY 8 //关

  • python数据结构之链表的实例讲解

    在程序中,经常需要将⼀组(通常是同为某个类型的)数据元素作为整体 管理和使⽤,需要创建这种元素组,⽤变量记录它们,传进传出函数等. ⼀组数据中包含的元素个数可能发⽣变化(可以增加或删除元素). 对于这种需求,最简单的解决⽅案便是将这样⼀组元素看成⼀个序列,⽤ 元素在序列⾥的位置和顺序,表示实际应⽤中的某种有意义的信息,或者 表示数据之间的某种关系. 这样的⼀组序列元素的组织形式,我们可以将其抽象为线性表.⼀个线性 表是某类元素的⼀个集合,还记录着元素之间的⼀种顺序关系.线性表是 最基本的数据结构

  • C++语言数据结构 串的基本操作实例代码

    C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================

  • C语言中枚举与指针的实例详解

     C语言中枚举与指针的实例详解 总结一下, 定义枚举,用typedef enum关键字, 比如 typedef enum{Red,Green,Blue} Color3; 枚举到数值的转换,如果没有指定代表数值就是从0开始算, 比如 Color3 c=Red; printf("%d",c);会显示0, 除非指定 如typedef enum{Red=3,Green=5,Blue=10} Color3; 关于类型指针的定义, 定义的时候在变量名左边加*代表此变量只是一个空指针而已, 若需要赋

  • C语言中实现itoa函数的实例

    C语言中实现itoa函数的实例 一.原型: char *itoa( int value, char *string,int radix); 二.函数说明: value:欲转换的数据. string:目标字符串的地址. radix:转换后的进制数,可以是10进制.16进制等. 三.函数简单实现: #include <iostream> #include <string> using namespace std; char* My_itoa(int value,char str[],i

  • Java语言中的自定义类加载器实例解析

    本文研究的主要是Java语言中的自定义类加载器实例解析的相关内容,具体如下. 自己写的类加载器 需要注意的是:如果想要对这个实例进行测试的话,首先需要在c盘建立一个c://myjava的目录.然后将相应的java文件放在这个目录中.并将产生的.clas文件放在c://myjava/com/lg.test目录下,否则是找不到的.这是要注意的.. class FileClassLoader : package com.lg.test; import java.io.ByteArrayOutputSt

  • R语言中字符串的拼接操作实例讲解

    在R语言中 paste 是一个很有用的字符串处理函数,可以连接不同类型的变量及常量. 函数paste的一般使用格式为: paste(..., sep = " ", collapse = NULL) 其 中-表示一个或多个R可以被转化为字符型的对象:参数sep表示分隔符,默认为空格:参数collapse可选,如果不指定值,那么函数paste的返回值是自变量之间通过sep指定的分隔符连接后得到的一个字符型向量:如果为其指定了特定的值,那么自变量连接后的字符型向量会再被连接成一个字符串,之间

随机推荐