ep6_6.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /* 6.6 现有两个已升序排好的数组,将它们合并为一个升序排序的数组(归并),请用函数
  2. 模板实现。该方法可以演变成归并排序。
  3. 算法:两数组合并时,可为每个数组各安排一个指针,从第一个元素开始比较两数组对应元素,
  4. 小的取下来,顺序放入新的数组;取下所指元素的指针后移,再比较,依此类推;直到其中一
  5. 个数组的元素已全部放入新数组,再把另一数组余下的元素全部顺序放入新数组,归并完成。*/
  6. //此处是面向对象的方法
  7. #include<iostream>
  8. #include<string>
  9. using namespace std;
  10. template <typename T,int size>class Orderedlist{
  11. int maxsize;
  12. int last;
  13. T slist[size];
  14. public:
  15. Orderedlist(){last=-1;maxsize=size;}
  16. void BubbleSort();
  17. bool Insert(T & elem,int i);
  18. void print();
  19. void Merge(Orderedlist &,Orderedlist &);
  20. // 无关成员函数省略,缺省的=等不必定义
  21. };//再次指出分号不可少
  22. template <typename T,int size> bool Orderedlist<T,size>::Insert(T & elem ,int i){
  23. if (i<0||i>last+1||last==maxsize-1) return false;
  24. else{
  25. for (int j=last;j>i;j--) slist[j]=slist[j-1];
  26. slist[i]=elem;
  27. last++;
  28. return true;
  29. }
  30. }
  31. template <typename T,int size> void Orderedlist<T,size>::print(){
  32. int i;
  33. for(i=0;i<=last;i++){
  34. cout<<slist[i];
  35. if(i%5==4) cout<<endl;
  36. else cout<<'t';
  37. }
  38. cout<<endl;
  39. }
  40. template <typename T,int size> void Orderedlist<T,size>::BubbleSort(){//升序
  41. bool noswap;
  42. int i,j;
  43. T temp;
  44. for (i=last;i>0;i--){//从上往下冒泡,对比例6.8有何不同?
  45. noswap=true; //未交换标志为真
  46. for(j=0;j<i;j++){
  47. if(slist[j+1]<slist[j]){//关键字比较只用小于号!
  48. temp=slist[j];
  49. slist[j]=slist[j+1];
  50. slist[j+1]=temp;
  51. noswap=false;
  52. }
  53. }
  54. if(noswap) break; //本趟无交换,则终止算法。
  55. }
  56. }
  57. template <typename T,int size> void Orderedlist<T,size>::Merge(Orderedlist & ls1,Orderedlist & ls2){
  58. int i=0,j=0,k=0;
  59. while((i<=ls1.last)&&(j<=ls2.last)){
  60. if(ls1.slist[i]<ls2.slist[j]) {slist[k]=ls1.slist[i];i++;}
  61. else {slist[k]=ls2.slist[j];j++;}
  62. k++;last++;
  63. }
  64. while(i<=ls1.last) {//复制第一个表的剩余元素
  65. slist[k]=ls1.slist[i];i++;
  66. k++;last++;
  67. }
  68. while(j<=ls2.last) {//复制第二个表的剩余元素
  69. slist[k]=ls2.slist[j];j++;
  70. k++;last++;
  71. }
  72. }
  73. int main(){
  74. const int h=15;
  75. int i,h1=8,h2=5;
  76. Orderedlist<string,h> ordlist,ordlist1,ordlist2;
  77. string n[h],m[h];
  78. char sp1[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
  79. "浙江大学","同济大学"};
  80. for(i=0;i<h1;i++)  n[i]=sp1[i];
  81. for(i=0;i<h1;i++)  ordlist1.Insert(n[i],i); //建立顺序表
  82. cout<<"未排序表:"<<endl;
  83. ordlist1.print();
  84. ordlist1.BubbleSort();
  85. cout<<"已排序表:"<<endl;
  86. ordlist1.print();
  87. char sp2[h][10]={"南开大学","吉林大学","中山大学","武汉大学","科技大学"};
  88. for(i=0;i<h2;i++)  m[i]=sp2[i];
  89. for(i=0;i<h2;i++)  ordlist2.Insert(m[i],i); //建立顺序表
  90. cout<<"未排序表:"<<endl;
  91. ordlist2.print();
  92. ordlist2.BubbleSort();
  93. cout<<"已排序表:"<<endl;
  94. ordlist2.print();
  95. ordlist.Merge(ordlist1,ordlist2);
  96. cout<<"归并已排序表:"<<endl;
  97. ordlist.print();
  98. return 0;
  99. }