自然归并(链表).cpp

this package contains two .c files.One file implements the merge of two int arrays.The other one imp

#include<stdio.h>
#include<malloc.h>
#define N 20

typedef struct chain										// 结点结构
{
	int info;
	struct chain* next;
} node;

typedef node* nodepointer;

void init_array( nodepointer* pp )							// 初始化 断层
{
	int xx;
	for( xx=0;xx<N;xx++ )
	{
		pp[ xx ] = NULL;
	}
}

node* creat_chain( int* arrayx,int array_lengthx )		   // 创建一个链表
{
	node* headx,*pre,*p;
	headx = (node*)malloc( sizeof(node) );
	headx->next = NULL;
	pre = headx;
	int i;
	for( i=0;i<array_lengthx;i++ )
	{
		p = (node*)malloc( sizeof(node) );
		p->info = arrayx[ i ];
		p->next = pre->next;

		pre->next = p;

		pre = pre->next;
	}
	printf( "creat chain succesfully !\n\n" );
	return headx->next;
}

void print_chain( node* headx )							// 打印链表........
{
	printf( "\n\nprint_chain 开始\n" );
	node* pre;
	pre = headx;
	while( pre )
	{
		printf( "pre: %d   %d-->\n",pre,pre->info );
		pre = pre->next;
	}
	printf( "\t\t.NULL.\n\n" );
}

int count_chain( node* headx )						// 统计链表结点个数
{
	node* pre;
	int cnt = 0;
	pre = headx;

	while( pre )
	{
		cnt ++;
		pre = pre->next;
	}
	return cnt;
}

int find_defaltage( node* headx,nodepointer* def )				// 扫描断层的结点位置，结果保存至 defaltage 数组
{																	// 并按自然排序分段.....
	int cnt=1;
	node* pre = headx;
	int nodepointer_indicator = 1;
	pre = headx;

	def[0] = headx;
	while( pre->next )
	{
		if( pre->info > pre->next->info )
		{
			cnt ++;
			def[nodepointer_indicator++] = pre->next;					// 记入 nodepointer 数组	
			pre->next = NULL;											// 断链
			pre = def[ nodepointer_indicator-1 ];
		}
		else
		{
			pre = pre->next;										// 游标移动
		}
	}

	return cnt;
}

void print_defaltage( nodepointer* defaltage )				// 打印断层
{
	printf( "打印断层位置: \n" );
	int i=0;
	while( defaltage[ i ] )
	{
		printf( "%d-->\n",defaltage[i++] );
	}
}

node* combine( node* lowhead,node* highhead )                           //  合并两个升序链表....
{
	node* output,*out_pre,*low_pre,*high_pre,*p;
	output = (node*)malloc( sizeof(node) );
	output->next = NULL;
	out_pre = output;	

	low_pre = lowhead;
	high_pre = highhead;

	while( low_pre && high_pre )
	{		
		if( low_pre->info < high_pre->info )
		{
			p = (node*)malloc( sizeof(node) );
			p->info = low_pre->info;
			p->next = out_pre->next;

			out_pre->next = p;

			out_pre = out_pre->next;
			low_pre = low_pre->next;
		}
		else
		{
			p = (node*)malloc( sizeof(node) );
			p->info = high_pre->info;
			p->next = out_pre->next;

			out_pre->next = p;

			out_pre = out_pre->next;
			high_pre = high_pre->next;
		}
	}

	if( low_pre )
	{
		out_pre->next = low_pre;
	}
	else if( high_pre )
	{
		out_pre->next = high_pre;
	}	
	return output->next;
}

node* merge_sort( int low,int high,nodepointer* defalt )
{
	if( low == high )
	{	
		return defalt[low];
	}

	node* head,*lowhead,*highhead;

	int mid = (low+high) / 2;

	lowhead = merge_sort(   low, mid,defalt );
	highhead = merge_sort( mid+1,high,defalt );

	head = combine( lowhead,highhead );

	return head;
}

int main()
{
	int links=0;
	node* head;
	int array[] = { 1,24,3,7,45,89,85,74,67,35,68,29,294,71,65,188,40,88,82,51,254,38,60,84,73,52,34,79,75,756 };

	nodepointer* defaltage = new nodepointer[ N ];			//  断层位置
	init_array( defaltage );								//  初始化为 NULL

	head = creat_chain( array,sizeof(array) / sizeof(int) ); // 建立一链表..

	print_chain( head );									// 打印链表结点

	links = find_defaltage( head,defaltage );						// 扫描断层

	printf( "有 %d 个升序链表\n\n",links );

	print_defaltage( defaltage );							// 打印断层	

	int add;
	printf( "\n打印升序链表:  \n" );
	for( add=0;add<N;add++ )
	{
		node* tmp = defaltage[add];

		if( tmp  )
		{
			while( tmp )
			{
				printf( "%d-->",tmp->info );
				tmp = tmp->next;
			}
			printf( "\n" );
		}
		else
			break;
	}
	printf( "\n\n\n" );

	node* headxx = merge_sort( 0,links-1,defaltage );                      // 返回最后合并好的链表 表头

	print_chain( headxx );

	printf( "\n\n" );
	return 0;
}