ep6_6.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
- /* 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;
- }