wangxu.h

数据结构的C++程序

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
void BubbleSort(int array[],int count)  //起泡排序
{
	int temp,i,j,keycompare(0),keymove(0);
	
	for(i=2;i<=count;i++)
	{
		for(j=1;j<count;j++)
		{
			if(array[j]>array[j+1])
			{
				temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
				keymove+=3;
			}
			keycompare+=1;
		}
	}
	cout<<"经过起泡法排序的数组为:"<<endl;
	for(i=1;i<=count;i++)
	{
		cout<<setw(8)<<array[i];
	}
	cout<<endl;
	cout<<"起泡排序的关键字比较次数为"<<keycompare<<"，移动次数为"<<keymove<<endl;
}

void InsertSort(int array[],int count)  //直接插入排序
{
	int i,j,keycompare(0),keymove(0);
	for(i=2;i<=count;i++)
	{
		if(array[i]<array[i-1])
		{
			array[0]=array[i];    //复制为哨兵
			array[i]=array[i-1];  
			keymove+=2; 
			for(j=i-2;array[0]<array[j];j--,keycompare+=1)
			{
				array[j+1]=array[j];   //记录后移
				keymove+=1; 
			}
			array[j+1]=array[0];  //插入到正确位置 
			keymove+=1;
		}
		keycompare+=1;
	}
    cout<<"经过直接插入排序的数组为:"<<endl;
	for(i=1;i<=count;i++)
	{
		cout<<setw(8)<<array[i];
	}
	cout<<endl;
	cout<<"直接插入排序法的关键字比较次数为"<<keycompare<<"，移动次数为"<<keymove<<endl;
}

void SelectSort(int array[],int count)  //简单选择排序
{
	int i,j,min,temp,keycompare(0),keymove(0);
	for(i=1;i<=count-1;i++)   //选择第i小的记录，并交换到位
	{
		array[0]=array[i];
		keymove+=1;
		for(j=i;j<=count;j++,keycompare++)   //从array[i]到array[count]选择关键字最小的记录
		{
			
			if(array[0]<array[j])
				continue;
			else 
			{
				array[0]=array[j];
				min=j;
				keymove+=1;
			}
		}
		if(i!=min)    //与第i个记录交换
		{
			temp=array[i];
			array[i]=array[min];
			array[min]=temp;
			keymove+=3;
		}
	}
	cout<<"经过简单选择排序的数组为:"<<endl;
	for(i=1;i<=count;i++)
	{
		cout<<setw(8)<<array[i];
	}
	cout<<endl;
	cout<<"简单选择排序法的关键字比较次数为"<<keycompare<<"，移动次数为"<<keymove<<endl;
}

void QuickSort(int array[],int low,int high)  //快速排序
{
	int i=low,j=high;
	array[0]=array[low];
	while (i<j)    //从表的两端交替向中间扫描
	{
		while(i<j&&array[0]<=array[j])
		{
			j--;
			
		}
		if(i<j)
		{
			array[i]=array[j];
			i++;
			
		}
		while(i<j&&array[i]<array[0]) 
		{
			i++;
			
		}
		if(i<j)
		{
			array[j]=array[i];
			j--;
			
		}
	}
	array[i]=array[0];
	if(low<i) QuickSort(array,low,i-1);
	if(i<high) QuickSort(array,j+1,high);
	
}

void QuickSortPrint(int array[],int count)
{
	cout<<"经过快速排序的数组为:"<<endl;
	for(int i=1;i<=count;i++)
	{
		cout<<setw(8)<<array[i];
	}
	cout<<endl;
	
}	

void ShellSort(int array[],int count)   //希尔排序
{
	int i,j,keycompare(0),keymove(0);
	int k=count/2;
    while (k>0)
	{
		for(j=k;j<=count;j++)
		{
			array[0]=array[j];
			keymove+=1;
			i=j-k;
			keycompare+=1;
			while((i>=0)&&(array[i]>array[0]))
			{
				array[i+k]=array[i];
				keymove+=1;
				i=i-k;
				

			}
			array[i+k]=array[0];
			keymove+=1;
		}
		k=k/2;
	}
	
	cout<<"经过希尔排序的数组为:"<<endl;
	for(i=1;i<=count;i++)
	{
		cout<<setw(8)<<array[i];
	}
	cout<<endl;
	cout<<"希尔排序法的关键字比较次数为"<<keycompare<<"，移动次数为"<<keymove<<endl;
}
//筛选法调整堆
void Sift(int r[], int k, int m)
{
  
	int i;
	int j;
	int temp;
	i=k; 
	j=2*i+1;                            //置i为要筛的结点，j为i的左孩子
  while (j<=m)                          //筛选还没有进行到叶子
  {
      if (j<m && r[j]<r[j+1]) 
		  j++;                          //比较i的左右孩子，j为较大者
      if (r[i]>r[j]) break;             //根结点已经大于左右孩子中的较大者
      else 
	  {
           temp=r[i];
	       r[i]=r[j];
		   r[j]=temp;                   //将根结点与结点j交换
           i=j;
		   j=2*i+1;                     //被筛结点位于原来结点j的位置
	 }
  }
}
//堆排序
void HeapSort(int r[ ], int count)
{
   
  int i;
  int temp;
  for (i=count/2; i>=0; i--)                //初始建堆，从最后一个非终端结点至根结点
     Sift(r, i, count) ;     
   for (i=count-1; i>0; i--)                //重复执行移走堆顶及重建堆的操作
   {
	   temp=r[i];
	   r[i]=r[0];
	   r[0]=temp;
      Sift(r, 0, i-1);
   }
   
cout<<"经过dui排序的数组为:"<<endl;
	for(i=1;i<=count;i++)
	{
		cout<<setw(8)<<r[i];
	}
	cout<<endl;
}