合并有序的两个线性表

微信扫一扫

028-83195727 , 15928970361
business@forhy.com

合并有序的两个线性表

合并,链式表2016-06-06

【问题描述】:

合并两个有序的线性表，例：两个线性表都是非递减有序序列，线性表1:3->5->8->11->over，线性表2:2->8->10->15->over,合并后的线性表也是递增有序的:2->3->5->8->8->10->11->15.

【问题分析】:

拿到这样一道题如何去分析呢？我们知道对于链式存储的线性表而言每个链式表都有它自己的头指针:用来访问它的后续结点；对于合并后的链式表我们可以为它新开辟自己的头指针也可以借用链式表1或者链式表2的头指针；在实现合并链式表的操作中我考虑到了一下两种情况：

如果传过来的两个链式表中有一个是空链表呢？我们知道线性表都是递增的此时我们只需要返回不为空的那个链表就可以了；

传过来的两个链式表不存在空链表呢？此时最先要考虑的就是如何选取合并之后链表的头指针呢？我们是不是可以通过比较两个链表中第一个节点的数据域的大小让合并之后的链表指向数据域最小的结点呢？当然可以了，我们知道两个链表都是递增的而通过比较两个链表第一个元素的大小就是找到了两个链表中最小的结点了；

接下来要考虑的就是如何比较了，只要两个链表都不为空我们就通过比较他们的数据域找到最小的连接在合并之后的链表上；这种情况有没有可能其中一个链表已经比较结束了而另一个链表还存在元素呢？当然！！！此时就需要在程序的结尾判断，如果有则将该链表的后续结点全部连接到合并之后的结点上; 在这里要提醒大家一句就是如果没有为合并后的链表3开辟空间则不需要释放前两个链表，如果像我一样利用原先的线性表只改变指针指向关系则只序言释放合并后的链表就可以了，我刚开始就将前两个链表都释放了，破坏了系统中的内存堆导致程序失误，真的是小问题坑死人呐；

@空链表

@两个链表都存在元素

一组实例分析如下，图画的不好希望大家多多理解啦！

【代码实现】:

pLinkNode merge_list(pLinkNode plist1,pLinkNode plist2)
{
	pLinkNode plist3=NULL;
	pLinkNode cur=NULL;
	assert(plist1);
	assert(plist2);
	if(NULL == plist1->next)     //传进来的有一个是空链表
	{
		return plist2;
	}
	else if(NULL == plist2->next)
	{
		return plist1;
	}
	if(plist1->next->data <= plist2->next->data)  //使得plist3和开始数据最小的链表公用同一个头指针
	{
		plist3=plist1;
	}
	else 
	{
		plist3=plist2;
	}
	plist1=plist1->next;
	plist2=plist2->next;
	cur=plist3;
	while(plist1 != NULL && plist2 != NULL)   //plist3依然是按照递增的顺序排列
	{
       		if(plist1->data <= plist2->data)
			{
				cur->next=plist1;
				cur=plist1;
				plist1=plist1->next;
			}
			else
			{
				cur->next=plist2;
			    cur=plist2;
			    plist2=plist2->next;
			}
	}
	while(plist1 != NULL)    //链表中比较完成后依然有未比较完的数据,只执行其中的一个while循环
	{
		cur->next=plist1;
		plist1=plist1->next;
	}  
	while(plist2 != NULL)
	{
		cur->next=plist2;
		plist2=plist2->next;
	}
	return plist3;
}

【程序源代码】:

text.c

#include"mergelist.h"

void text1()
{
	pLinkNode ret=NULL;
	LinkNode plist1;
	LinkNode plist2;
	Init_list(&plist1);
	Init_list(&plist2);
	printf("链表1的元素为:");
	Pust_list(&plist1,3);
	Pust_list(&plist1,5);
	Pust_list(&plist1,8);
	Pust_list(&plist1,11);
	Print_list(&plist1);
	printf("链表2的元素为:");
	Pust_list(&plist2,2);
	Pust_list(&plist2,8);
	Pust_list(&plist2,9);
	Pust_list(&plist2,15);
	Print_list(&plist2);
	printf("合并之后链表的元素为:");
	ret=merge_list(&plist1,&plist2);
	Print_list(ret);
	Free_list(ret);
}

int main()
{
	text1();
	system("pause");
	return 0;
}

mergelist.h

#ifndef __MERGELIST_H__
#define __MERGELIST_H__

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

typedef int DateType;

typedef struct LinkNode
{
	DateType data;
	struct LinkNode *next;
}LinkNode,*pLinkNode;

void Init_list(pLinkNode plist);
void Pust_list(pLinkNode plist,DateType x);    //尾插
pLinkNode merge_list(pLinkNode plist1,pLinkNode plist2);  //合并两个有序链表
void Print_list(pLinkNode plist);
void Free_list(pLinkNode plist);

#endif //__MERGELIST_H__

mergelist.c

#include"mergelist.h"

void Init_list(pLinkNode plist)
{
	assert(plist);
	plist->next=NULL;
}

pLinkNode Create_Node(DateType x)
{
	pLinkNode newNode=(pLinkNode)malloc(sizeof(LinkNode));
	if(NULL == newNode)
	{
		printf("out of memory\n");
		exit(EXIT_FAILURE);
	}
	newNode->data=x;
	newNode->next=NULL;
	return newNode;
}

void Pust_list(pLinkNode plist,DateType x)
{
	pLinkNode cur=plist->next;
	pLinkNode newNode=NULL;
	assert(plist);
	newNode=Create_Node(x);
	if(NULL == plist->next)  //空链表时
	{
		plist->next=newNode;
	}
	else
	{
		while(cur->next != NULL)
		{
			cur=cur->next;
		}
		cur->next=newNode;
	}
}

pLinkNode merge_list(pLinkNode plist1,pLinkNode plist2)
{
	pLinkNode plist3=NULL;
	pLinkNode cur=NULL;
	assert(plist1);
	assert(plist2);
	if(NULL == plist1->next)     //传进来的有一个是空链表
	{
		return plist2;
	}
	else if(NULL == plist2->next)
	{
		return plist1;
	}
	if(plist1->next->data <= plist2->next->data)  //使得plist3和开始数据最小的链表公用同一个头指针
	{
		plist3=plist1;
	}
	else 
	{
		plist3=plist2;
	}
	plist1=plist1->next;
	plist2=plist2->next;
	cur=plist3;
	while(plist1 != NULL && plist2 != NULL)   //plist3依然是按照递增的顺序排列
	{
       		if(plist1->data <= plist2->data)
			{
				cur->next=plist1;
				cur=plist1;
				plist1=plist1->next;
			}
			else
			{
				cur->next=plist2;
			    cur=plist2;
			    plist2=plist2->next;
			}
	}
	while(plist1 != NULL)    //链表中比较完成后依然有未比较完的数据,只执行其中的一个while循环
	{
		cur->next=plist1;
		plist1=plist1->next;
	}  
	while(plist2 != NULL)
	{
		cur->next=plist2;
		plist2=plist2->next;
	}
	return plist3;
}

void Print_list(pLinkNode plist)
{
	pLinkNode cur=plist->next;
	assert(plist);
	while(cur != NULL)
	{
		printf("%d->",cur->data);
		cur=cur->next;
	}
	printf("over\n");
}
       
void Free_list(pLinkNode plist)
{
	pLinkNode cur=plist->next;
	pLinkNode tmp=NULL;
	if(NULL == plist->next)  //空链表
	{
		return ;
	}
	else if(NULL == plist->next->next) //只有一个结点
	{
		free(plist->next);
		plist->next=NULL;
	}
	else
	{
		while(cur != NULL)
		{
			tmp=cur;
			cur=cur->next;
			free(tmp);
			tmp=NULL;
		}
	}
	plist=NULL;
}