paixu1.h

数据结构程序设计21

#include<fstream.h>
template <class Type> class staticlinklist;              //数据表的前视声明
template <class Type> class Element1{               //数据表元素类的定义
friend class staticlinklist<Type>;
private:
		Type key;                                  //关键码
		int link;
public:
	   Type getKey(){return key;}                   //取当前结点的关键码
	   void setKey(const Type x) {key=x;}           //将当前结点的关键码修改为x
       int getLink(){return link;}                  //取当前结点的链结指针
      void setLink(const int l){link=l;}           //取当前结点的链接指针置为l
};

template<class Type> class staticlinklist{             //静态链表的类定义
//friend  void shuchu1(int x,staticlinklist<int> list) ;
//friend int suiji1(staticlinklist <int> list);
//friend int jiaohu1(staticlinklist <int> list);
//friend void paixu(int x,staticlinklist<int> list);
//friend void memu2(int x,staticlinklist<int> list);

friend void memu(int x,datalist <int> list);
friend void memu1(datalist <int> list);
public:
      staticlinklist(int MaxSz=DefaultSize):MaxSize(MaxSz),CurrentSize(0)
      {Vector=new Element1<Type> [MaxSz];}
	  void LinkInsertSort(staticlinklist<Type> &list);
	  void LinkInsertSort1(staticlinklist<Type> &list);
	  //int ListMerge(staticlinklist<Type> &list,int start1,int start2);
	 // int rMergeSort(staticlinklist<Type> &list,const int left,const int right);
	  void print();

private:
       Element1<Type> *Vector;                       //存储待排序元素向量
       int MaxSize,CurrentSize;                     //向量中最大元素个数和当前元素个数
};

template<class Type> 
void staticlinklist<Type>::print()                    //输出函数
{
	int j=Vector[0].getLink();
	cout<<"结果为：";
	while(j)
	{
		if(j==0) break;
		cout<<Vector[j].getKey()<<" ";
		j=Vector[j].getLink();
	}
    cout<<endl;
}



//插入排序的链表插入
template<class Type> void staticlinklist<Type>::LinkInsertSort(staticlinklist<Type> &list){
ofstream out("链表插入.txt");
int MaxNum=100000000;
list.Vector[0].setKey(MaxNum);list.Vector[0].setLink(1);
list.Vector[1].setLink(0);                //初始化,形成只有头结点的循环链表
for(int i=2;i<=list.CurrentSize;i++){      //向有序链表中插入一个结点,共n-1趟
  int current=list.Vector[0].getLink();     //current是链表检测指针
  int pre=0;                                 //pre指向current的前驱
  while(list.Vector[current].getKey()<=list.Vector[i].getKey())   //循链找插入位置
   {pre=current;current=list.Vector[current].getLink();}             //pre跟上,current循链检测下一个结点
   list.Vector[i].setLink(current);list.Vector[pre].setLink(i);          //结点i链入pre与current之间
   	cout<<"i="<<i<<"时 ";
    out<<"i="<<i<<"时 ";
   	int j=Vector[0].getLink();
	while(j)
	{
		if(j==0) break;
		cout<<Vector[j].getKey()<<" ";
		out<<Vector[j].getKey()<<" ";
		j=Vector[j].getLink();
	}
   cout<<endl;
   out<<endl;
 }
   
}




//插入排序的链表插入
template<class Type> void staticlinklist<Type>::LinkInsertSort1(staticlinklist<Type> &list){
int MaxNum=100000000;
list.Vector[0].setKey(MaxNum);list.Vector[0].setLink(1);
list.Vector[1].setLink(0);                //初始化,形成只有头结点的循环链表
for(int i=2;i<=list.CurrentSize;i++){      //向有序链表中插入一个结点,共n-1趟
  int current=list.Vector[0].getLink();     //current是链表检测指针
  int pre=0;                                 //pre指向current的前驱
  while(list.Vector[current].getKey()<=list.Vector[i].getKey())   //循链找插入位置
   {pre=current;current=list.Vector[current].getLink();}             //pre跟上,current循链检测下一个结点
   list.Vector[i].setLink(current);list.Vector[pre].setLink(i);          //结点i链入pre与current之间
   
 }
}

/*
//递归的表归并排序
template<class Type> int staticlinklist<Type>::ListMerge(staticlinklist<Type> &list,int start1,int start2){
   int k=0,i=start1,j=start2;
   while(i && j)
     if(list.Vector[i].getKey()<=list.Vector[j].getKey())
      {list.Vector[k].setLink(i);k=i;i=list.Vector[i].getLink();}
     else
      {list.Vector[k].setLink(j);k=j;j=list.Vector[j].getLink();}
     if(! i) list.Vector[k].setLink(j);
      else list.Vector[k].setLink(i);
     return list.Vector[0].getLink();
}



template<class Type> int staticlinklist<Type>::rMergeSort(staticlinklist<Type> &list,const int left,const int right){
    if(left>=right) return left;
    int middle=(left+right)/2;
    return ListMerge(list,rMergeSort(list,left,middle),rMergeSort(list,middle+1,right));
}*/