ep6_6.cpp

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

/* 6.6 现有两个已升序排好的数组，将它们合并为一个升序排序的数组（归并），请用函数
模板实现。该方法可以演变成归并排序。
算法：两数组合并时，可为每个数组各安排一个指针，从第一个元素开始比较两数组对应元素，
小的取下来，顺序放入新的数组；取下所指元素的指针后移，再比较，依此类推；直到其中一
个数组的元素已全部放入新数组，再把另一数组余下的元素全部顺序放入新数组，归并完成。*/
//此处是面向对象的方法

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

template <typename T,int size>class Orderedlist{
	int maxsize;
	int last;
	T slist[size];
public:
	Orderedlist(){last=-1;maxsize=size;}
	void BubbleSort();
	bool Insert(T & elem,int i);
	void print();
	void Merge(Orderedlist &,Orderedlist &);
	// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
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 Orderedlist<T,size>::BubbleSort(){//升序
	bool noswap;
	int i,j;
	T temp;
	for (i=last;i>0;i--){//从上往下冒泡，对比例6.8有何不同？
		noswap=true;	//未交换标志为真
		for(j=0;j<i;j++){
			if(slist[j+1]<slist[j]){//关键字比较只用小于号！
				temp=slist[j];
				slist[j]=slist[j+1];
				slist[j+1]=temp;
				noswap=false;
			}			
		}
		if(noswap) break;	//本趟无交换，则终止算法。
	}
}

template <typename T,int size> void Orderedlist<T,size>::Merge(Orderedlist & ls1,Orderedlist & ls2){
	int i=0,j=0,k=0;
	
	while((i<=ls1.last)&&(j<=ls2.last)){
		if(ls1.slist[i]<ls2.slist[j]) {slist[k]=ls1.slist[i];i++;}
		else {slist[k]=ls2.slist[j];j++;}
		k++;last++;
	}
	while(i<=ls1.last) {//复制第一个表的剩余元素
		slist[k]=ls1.slist[i];i++;
		k++;last++;
	}
	while(j<=ls2.last) {//复制第二个表的剩余元素
		slist[k]=ls2.slist[j];j++;
		k++;last++;
	}
}
int main(){
	const int h=15;
	int i,h1=8,h2=5;
	Orderedlist<string,h> ordlist,ordlist1,ordlist2;
	string n[h],m[h];
	char sp1[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
	"浙江大学","同济大学"};	
	for(i=0;i<h1;i++)  n[i]=sp1[i];
	for(i=0;i<h1;i++)  ordlist1.Insert(n[i],i); //建立顺序表
	cout<<"未排序表："<<endl;
	ordlist1.print();
	ordlist1.BubbleSort();
	cout<<"已排序表："<<endl;
	ordlist1.print();
	char sp2[h][10]={"南开大学","吉林大学","中山大学","武汉大学","科技大学"};
	for(i=0;i<h2;i++)  m[i]=sp2[i];
	for(i=0;i<h2;i++)  ordlist2.Insert(m[i],i); //建立顺序表
	cout<<"未排序表："<<endl;
	ordlist2.print();
	ordlist2.BubbleSort();
	cout<<"已排序表："<<endl;
	ordlist2.print();
	ordlist.Merge(ordlist1,ordlist2);
	cout<<"归并已排序表："<<endl;
	ordlist.print();
	return 0;
}