paixu1.h.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > asd.rar > paixu1.h


#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> &amt;list); 
void LinkInsertSort1(staticlinklist<Type> &amt;list); 
//int ListMerge(staticlinklist<Type> &amt;list,int start1,int start2); 
// int rMergeSort(staticlinklist<Type> &amt;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> &amt;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> &amt;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> &amt;list,int start1,int start2){ 
int k=0,i=start1,j=start2; 
while(i &amt;&amt; 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> &amt;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)); 
}*/