ep6_7_0.cpp

这里有大量的c语言习题呢！真的是题海哦

/* 6.17  希尔排序（shell sort），又称缩小增量排序（diminishing increment sort）。
其思想如下：
设线性表L长度为n，取增量gap=n/2，即以L[0]和L[gap]为一组，L[1]和L[gap+1]为一组，
L[2]和L[gap+2]为一组，……，L[n-gap]和L[n]为一组，分别进行插入排序。再取
gap=gap/2，则分组成为L[0]，L[gap]，L[2gap]，……为一组，L[1]，L[gap+1]，L[2gap+1]，
……为一组，等等，分别进行插入排序。直到gap=1，这时分组成为整个表，并只有一个组，
再插入排序，完成全部任务。参见下图：

初始	20	26	49	21	15	6	
1	    20	-	-	21			分组1，gap=3
		    26	-	-	15		分组2
			    49	-	-	6	分组3
	    20	15	6	21	26	49	结果

2	    20	15	6	21	26	49	gap=1
	    6	15	20	21	26	49	结果

全部采用函数模板，包括希尔插入子程序。分组直接用增量控制在原线性表中进行插入排序。*/

//此处不是纯面向对象的方法

#include<iostream>
#include<string>
using namespace std;

template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	T slist[size];
public:
	int getlast(){return last;}
	T getslist(int k){return slist[k];}
	void putslist(T t,int k){slist[k]=t;}
	Orderedlist(){last=-1;maxsize=size;}
	bool Insert(T & elem,int i);
	void print();
	// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
template <typename T,int size> bool Orderedlist<T,size>::Insert(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];		
		if(i%5==4) cout<<endl;
		else cout<<'\t';
	}
	cout<<endl;
}
template <typename T,int size> void Shellsort(Orderedlist<T,size> & list){//非成员函数，仅以表模板类为参数
	int gap=(list.getlast()+1)/2;
	while(gap){
		Shellinsert(list,gap);//一趟排序
		gap/=2;
	}
}//int size必须保留
template <typename T,int size> void Shellinsert(Orderedlist<T,size> & list,const int gap){
	int i,j;
	T temp;
	//注意每一趟排序包含若干子序列，其中第一个子序列第一个元素是0号，第二个元素是gap号，
	//插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。
	for(i=gap;i<=list.getlast();i++){//从第一个子序列开始直接插入排序，但不是完成一个子序列，
		//再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步，等等，穿插完成。
		//直接插入排序总是从后逐个向前，找到第一个比待插元素大的，则插在前面。
		temp=list.getslist(i);//待插元素放temp中
		j=i;
		while(j>=gap&&temp<list.getslist(j-gap)){//升序
			list.putslist(list.getslist(j-gap),j);//找的元素，只要比temp大，就后移，空出位置
			j-=gap;
		}
		list.putslist(temp,j);//将temp插入正确的空位
	}
}

int main(){
	const int h=8;
	int i;
	Orderedlist<string,h> ordlist;
	string n[h];
	char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
	"浙江大学","同济大学"};	
	for(i=0;i<h;i++)  n[i]=sp[i];
	for(i=0;i<h;i++)  ordlist.Insert(n[i],i); //建立顺序表
	cout<<"未排序表："<<endl;
	ordlist.print();
	Shellsort(ordlist);
	cout<<"已排序表："<<endl;
	ordlist.print();
	return 0;
}
/*本题希尔排序是独立的函数，而线性类模板作为形参，也是一种常见的用法。*/