datalist.h

产生随机数据 从文件中读取数据 输出顺序表的数据 直接插入排序 折半插入排序 希尔排序 冒泡排序 快速排序 保存数据

/////////////////////////////////////////////////////////////
//Function:用模板定义数据表类,同时定义数据表类的相关成员函数
//Program:datalist.h
/////////////////////////////////////////////////////////////
#include <cstdlib>//使用随机函数
#include <iostream>
#include <iomanip>
#include <fstream>
#include "quene.h" //使用队列来跟踪执行过程

using namespace std;

const int Pivot_Flag=0;//表示队列中的下一结点的值为枢轴
const int Current_Part=-1;//在队列中用该值表示处理的序列

const int defaultSize=100;//数据表的缺省大小为100

//定义查找表类
template <class Type> class DataList
{
public:
	DataList(int MaxSize=defaultSize);//构造函数
	~DataList();//析构函数
	void Random_data();//产生随机数据
  int Length() const;//计算表长度
	int IsEmpty();//判空
	int IsFull();//判满
	void print() const;//输出数据表的元素
	void print_serial()const;//以序列方式输出
	Type Get(int i);//取出位置i的数据元素
  void swap(Type &,Type &);//交换两个元素值
  
	int SaveToFile();//保存数据
	int ReadFromFile();//读取数据
	
	char IsOrNot();//是否需要演示？
	
	//定义各种排序操作
  void InsertionSort();//直接插入排序
  void BinaryInsertSort();//折半插入排序
  void ShellSort();//希尔排序
  void BubbleSort();//起泡排序
  void QuickSort();//快速排序  
private:
	Type *data;//存放顺序表的动态数组
	int MaxSize;//顺序表的最大可空纳空间
	int CurrentSize;//指示当前元素个数
	
	//定义私有函数
	void Insert(int,char);//第2个参数主要用于判断是否演示？
	void BinaryInsert(int,char);
	void ShellInsert(const int);
	void BubbleExchange(int,int &,int);
	
  void recQuickSort(int,int,Queue<Type>&,char);//第3个参数用于记录处理过程
  int Partition(int,int);
};

template <class Type> 
DataList<Type>::DataList(int sz)
{
//构造函数，通过指定参数sz定义动态数组的大小
	if(sz>0)
	{
		MaxSize=sz;CurrentSize=0;
		data=new Type[MaxSize];
	}
}//end of DataList()

template <class Type>
DataList<Type>::~DataList()
{
	//析构函数的定义
	delete []data;
}//end of ~DataList()

template <class Type>
void DataList<Type>::swap(Type &x,Type &y)
{//完成数据交换
  Type temp=x;
  x=y;
  y=temp;         
}//end of swap()

template <class Type>
int DataList<Type>::Length() const
{
	//返回表中实际存放数据元素的个数
	return CurrentSize;
}//end of Length()

template <class Type>
void DataList<Type>::Random_data()
{//产生随机数以填入数据表中
  int rand_data;CurrentSize=0;
  
  int num;
  cout<<"输入随机数个数(0:表缺省值): ";
  cin>>num;
  if(num>MaxSize)
  {
    cout<<"超越数据表的最大容量,取缺省大小!"<<endl;
    system("PAUSE");
    num=MaxSize;
  }
  if(num==0)
    num=MaxSize;
    srand(1000);
  for(int j=0;j<num;j++)
  {
     rand_data=rand();
		 data[CurrentSize]=rand_data;
		 CurrentSize++;
  }
}//end of Random_data()

template <class Type>
int DataList<Type>::IsFull()
{
	//判定顺序表是否已满
	return CurrentSize==MaxSize;
}//end of IsFull()

template <class Type>
int DataList<Type>::IsEmpty()
{
	//判定顺序表是否为空
	return CurrentSize==0;
}//end of IsEmpty()

template <class Type>
Type DataList<Type>::Get(int i)
{
	//取出位置i的数据元素值
	return i<0||i>(CurrentSize-1)?NULL:data[i];
}//end of Get()

template <class Type>
void DataList<Type>::print_serial() const
{//集合方式输出
  int p;
  cout<<"{";
  for(p=0;p<CurrentSize-1;p++)
    cout<<data[p]<<",";
  cout<<data[p]<<"}"<<endl;
}//end of print_serial()

template <class Type>
void DataList<Type>::print() const
{//列表输出
	for(int j=0;j<CurrentSize;j++)
	        cout<<"第"<<setw(4)<<j+1<<"个: "<<setw(6)<<data[j]<<endl;
}//end of print()

template <class Type>
int DataList<Type>::SaveToFile()
{//根据自定义文件名保存数据表的数据
  char *s1=new char[12];//接收文件名
  cout<<"输入数据文件名： ";
  cin>>s1;
  ofstream outp(s1);
	int i;
	for(i=0;i<CurrentSize-1;i++)
		outp<<data[i]<<",";
	outp<<data[i];//最后一条记录单独写，以免行数多1
  return 0;
}//end of SaveToFile()

template <class Type>
int DataList<Type>::ReadFromFile()
{//根据自定义文件名为数据表读取数据
  char *s1=new char[12];//接收数据来源文件名
  cout<<"输入数据文件名： ";
  cin>>s1;
  ifstream infile;
	infile.open(s1);

  int num;
  int error_flag=1;
  while(error_flag)
  {
          cout<<"读取数据个数(0:表示全部)： ";
          cin>>num;
          if(num==0)
          {
            num=MaxSize;
            error_flag=0;
          }
          if(num>0)
            error_flag=0;
          if(num<0)
            cout<<"非法数据!"<<endl;
  }
  
	int j=0;	
  while(j<num&&!IsFull())
	{
		infile>>data[j];
		infile.ignore(1);
		j++;
		CurrentSize=j;
	}

	cout<<"实际读取了"<<CurrentSize<<"个数据!"<<endl;
	system("PAUSE");
	return 0;
}//end of ReadFromFile()

template <class Type>
char DataList<Type>::IsOrNot()
{//询问
  char IsNeed;
  cout<<"是否需要演示排序过程(Y/N?):";
  cin>>IsNeed;
  return IsNeed;
}//end of IsOrNot()

template <class Type>
void DataList<Type>::QuickSort()
{//快速排序
  char isNeed=IsOrNot();
  cout<<"    原始数据序列: ";
  print_serial();

  Queue<int> q;
  recQuickSort(0,Length()-1,q,isNeed);
  while(!(q.IsEmpty()))
  {
    int t=q.DeQueue();
    if(t==0)
    {
      cout<<endl;
      cout<<"枢轴元素为:"<<q.DeQueue()<<endl;
    }
    else if(t==-1)
    {cout<<endl;
      cout<<"当前处理的子序列为:";
      if(q.GetFront()==-1)
      cout<<"Empty!"<<endl;
    }
    else cout<<t<<"  ";
  }
  cout<<endl;
  cout<<"排序后的数据序列: ";
  print_serial();
  system("PAUSE");
}//end of QuickSort()

template <class Type>
void DataList<Type>::recQuickSort(int left,int right,Queue<Type> &q,char isNeed)
{//快速排序递归主程序
  int pivotpos;
  static int part_num=0;
    
  if(left<right)
  {
    pivotpos=Partition(left,right);
    if(isNeed=='y'||isNeed=='Y')
    {
      q.EnQueue(Pivot_Flag);
      q.EnQueue(data[pivotpos]);
      q.EnQueue(Current_Part);    
      for(int i=left;i<=pivotpos-1;i++)
        q.EnQueue(data[i]);
    } 
    recQuickSort(left,pivotpos-1,q,isNeed);
    if(isNeed=='y'||isNeed=='Y')
    {
      q.EnQueue(Current_Part);
      for(int i=pivotpos+1;i<=right;i++)
        q.EnQueue(data[i]);;
    }
    recQuickSort(pivotpos+1,right,q,isNeed); 
  }            
}//end of recQuickSort()

template <class Type>
int DataList<Type>::Partition(int low,int high)
{//一次划分处理
  int pivotpos=low;int pivot=data[low];
  for(int i=low+1;i<=high;i++)
    if(data[i]<pivot && ++pivotpos!=i)
    swap(data[pivotpos],data[i]);
  swap(data[low],data[pivotpos]);
//  cout<<"pivotpos="<<pivotpos<<endl;
  return pivotpos;
}//end of Partition()

template <class Type>
void DataList<Type>::BubbleSort()
{//起泡排序
  int pass=1;
  int exchange=1;
  char IsNeed=IsOrNot();

  cout<<"    原始数据序列: ";
  print_serial();


  while(pass<CurrentSize&&exchange)
  {
    if(IsNeed=='y'||IsNeed=='Y')
    cout<<"*******第"<<pass<<"趟起泡：***********"<<endl;                                     
    BubbleExchange(pass,exchange,IsNeed);
    pass++;
  }
  cout<<"排序后的数据序列: ";
  print_serial();
  system("PAUSE");  
}//end of BubbleSort()

template <class Type>
void DataList<Type>::BubbleExchange(int i,int& exchange,int IsNeed)
{
  exchange=0;
  for(int j=CurrentSize-1;j>=i;j--)
  {
    if(data[j-1]>data[j])
    {
      swap(data[j-1],data[j]);
      if(IsNeed=='Y'||IsNeed=='y')
        cout<<"交换的数据元素是: "<<data[j-1]<<"<-->"<<data[j]<<endl;
      exchange=1;
    }
  }
  if(exchange==0)
    cout<<"本次起泡过程无数据交换!"<<endl;
  cout<<endl;
}//end of BubbleExchange()

template <class Type>
void DataList<Type>::ShellSort()
{//希尔排序
  char IsNeed=IsOrNot();

  cout<<"    原始数据序列: ";
  print_serial();
  
  int gap=CurrentSize/2;
  while(gap)
  {
  //输出子序列
    if(IsNeed=='y'||IsNeed=='Y')
    {
      cout<<"当前gap="<<gap<<endl;
      cout<<"应有"<<gap<<"个子序列,各子序列如下:"<<endl;
      for(int i=0;i<gap;i++)
      {
        int j=i;
        cout<<"第"<<i+1<<"个子序列为:";
        while(j<CurrentSize)
        {
          cout<<data[j]<<"  ";
          j+=gap;
        }
        cout<<endl;        
      }
      system("PAUSE");
    }
    ShellInsert(gap);
    //gap=gap==2?1:(int)(gap/2);          
    gap=(int)(gap/2);
  }
  cout<<"排序后的数据序列: ";
  print_serial();
  system("PAUSE");  
}//end of ShellSort()

template <class Type>
void DataList<Type>::ShellInsert(const int gap)
{//各子序列使用直接插入排序
  for(int i=gap;i<CurrentSize;i++)
  {
    int temp=data[i];
    int j=i;
    while(j>=gap&&temp<data[j-gap])
    {
      data[j]=data[j-gap];
      j-=gap;
    }
    data[j]=temp;
  }
}//end of ShellInsert()

template <class Type>
void DataList<Type>::BinaryInsertSort()
{//折半插入排序
  char IsNeed=IsOrNot();
  
  cout<<"    原始数据序列: ";
  print_serial();

  for(int i=1;i<CurrentSize;i++)         
  {
       if(IsNeed=='y'||IsNeed=='Y')  
         cout<<"第"<<i<<"趟:";
       BinaryInsert(i,IsNeed);
       if(IsNeed=='y'||IsNeed=='Y')  cout<<endl;
  }
  cout<<"排序后的数据序列: ";
  print_serial();

//  print();
  system("PAUSE");  
}//end of BinaryInsertSort()

template <class Type>
void DataList<Type>::BinaryInsert(int i,char IsNeed)
{
  int left=0,right=i-1;int temp=data[i];
  while(left<=right)       
  {
    int mid=(left+right)/2;
    if(IsNeed=='y'||IsNeed=='Y')
      cout<<"当前元素为"<<data[i]<<"("<<i<<"号)与"
          <<data[mid]<<"(第"<<mid<<"号)元素进行比较(left="<<left
          <<",right="<<right<<",mid="<<mid<<")"<<endl;
    if(temp<data[mid])
    {
      right=mid-1;
    }
    else
      left=mid+1;                         
  }
  for(int k=i-1;k>=left;k--)
    data[k+1]=data[k];
  data[left]=temp;
  if(IsNeed=='y'||IsNeed=='Y')  
  if(i!=left)
    cout<<"元素"<<temp<<"插入到"<<left<<"号单元"<<endl;
  else
    cout<<"元素"<<temp<<"位置不动"<<endl;  
}//end of BinaryInsert()

template <class Type>
void DataList<Type>::InsertionSort()
{//直接插入排序
  char IsNeed=IsOrNot();
  
  cout<<"    原始数据序列: ";
  print_serial();

  for(int i=1;i<CurrentSize;i++)         
  {
       if(IsNeed=='y'||IsNeed=='Y')  
         cout<<"第"<<i<<"趟:";
          Insert(i,IsNeed);
  }
  cout<<"排序后的数据序列: ";
  print_serial();

//  print();
  system("PAUSE");
}//end of InsertionSort()

template <class Type>
void DataList<Type>::Insert(int i,char IsNeed)
{//直接插入排序的过程
  int temp=data[i];int j=i;
//  cout<<"temp="<<temp<<endl;
  
  while(j>0&&temp<data[j-1])
  {
    data[j]=data[j-1];
  if(IsNeed=='y'||IsNeed=='Y')  
    cout<<"第"<<j-1<<"元素后移"<<"; ";
//    cout<<"data["<<j<<"]="<<data[j]<<endl;
//    cout<<"data["<<j-1<<"]="<<data[j-1]<<endl;    
    j--;                          
  }
  data[j]=temp;
  if(IsNeed=='y'||IsNeed=='Y')  
  if(i!=j)
    cout<<"元素"<<temp<<"插入到"<<j<<"号单元"<<endl;
  else
    cout<<"元素"<<temp<<"位置不动"<<endl;  
}//end of Insert()