ex6_18.cpp

纯粹是学习专用～

#include<iostream.h>

template <typename T>struct Node{
	T  key;
	// 其他域省略
};//再次指出分号不可少
template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	Node<T> slist[size];
public:
	Orderedlist(){last=-1;maxsize=size;}
	void BubbleSort();
	bool Insert(Node<T> & elem,int i);
	void print();
	// 无关成员函数省略
};//再次指出分号不可少
template <typename T,int size> bool Orderedlist<T,size>::Insert(Node<T> & elem ,int i){
	if (i<0||i>last+1||last==maxsize-1) return false;
	else{
		for (int j=last;j>i;j--) slist[j]=slist[j-1];
		slist[i]=elem;
		last++;
		return true;
	}
}
template <typename T,int size> void Orderedlist<T,size>::print(){
	int i;
	for(i=0;i<=last;i++){
		cout<<slist[i].key<<'\t';
		if(i%8==7) cout<<endl;
	}
	cout<<endl;
}
template <typename T,int size> void Orderedlist<T,size>::BubbleSort(){
	bool noswap;
	int i,j;
	Node<T> temp;
	for (i=0;i<last;i++){//最多做n-1趟
		noswap=true;	//未交换标志为真
		for(j=last;j>i;j--){//从下往上冒泡
			if(slist[j].key<slist[j-1].key){
				temp=slist[j];
				slist[j]=slist[j-1];
				slist[j-1]=temp;
				noswap=false;
			}			
		}
		if(noswap) break;	//本趟无交换，则终止算法。
	}
}

void main(){
	const int h=19;
	int i,k=47;
	Orderedlist<int,100> ordlist;
	int a[h]={53,7,67,5,41,3,61,59,13,47,23,19,37,29,31,2,17,43,11};
	Node<int> n[h];
	for(i=0;i<h;i++)  n[i].key=a[i];
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
	cout<<"未排序表："<<endl;
	ordlist.print();
	ordlist.BubbleSort();
	cout<<"已排序表："<<endl;
	ordlist.print();
}