merge.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

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

void Merge(int R[],int low,int mid,int high)
//将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]
{
	int *R1;
	int i=low,j=mid+1,k=0;  //k是R1的下标，i,j分别为第1,2段的下标
	R1=(int *)malloc((high-low+1)*sizeof(int));  //R1为辅助数组

	while(i<=mid&&j<=high) //在第1段和第2段均未扫描完时循环
		if(R[i]<=R[j])    
		{
			R1[k]=R[i];	
			i++; k++;
		}
		else            
		{
			R1[k]=R[j];	
			j++; k++;
		}

	while(i<=mid)   //将第1段余下部分复制到R1
	{
		R1[k]=R[i];	
		i++; k++;
	}
	while(j<=high)  //将第2段余下部分复制到R1
	{
		R1[k]=R[j];
		j++; k++;
	}

	for(k=0,i=low; i<=high; k++,i++)  //将R1复制回R中
		R[i]=R1[k];
}

void MergePass(int R[],int length,int n)  //实现一趟归并
{
	int i;
	for(i=0; i+2*length-1<n; i=i+2*length)  //归并length长的两相邻子表
		Merge(R,i,i+length-1,i+2*length-1);

	if(i+length-1<n)  //余下两个子表，后者长度小于length
		Merge(R,i,i+length-1,n-1);  //归并这两个子表
}

void MergeSort(int R[],int n)  //二路归并排序算法
{
	int length,k,i=1;   //i用于累计归并的趟数
	for(length=1;length<n;length=2*length)
	{
		MergePass(R,length,n);
		printf("  第%d趟归并:\n",i++);   //输出每一趟的排序结果
		for(k=0;k<n;k++)
			printf("%4d",R[k]);
		printf("\n");
	}
}

void main()
{
	int k,n=10;
	int a[]={18,2,20,34,12,32,6,16,7,14};

	printf("\n");
    printf("对数组中元素进行归并排序 ");
	printf("\n");

	printf("  初始关键字为:\n");
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
    printf("\n");

	MergeSort(a,n);

	printf("  最后结果为:\n");
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
	printf("\n");

	system("PAUSE");
}