C++归并算法实例

这篇文章主要介绍了C++归并算法,实例分析了C++实现基于归并算法合并线性表的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了C++归并算法。分享给大家供大家参考。具体如下：

1. /*  
2. 归并算法：把两个或两个以上的线性表合并在一起，形成一个新的线性表 
3. 函数模版的基本使用 
4. 程序意图：将两个相同类型的线性表元素排好序，然后将他们组合成一个排好的线性表  
5. */ 
6. #include <iostream> 
7. using namespace std; 
8. const int n = 5; //5个元素  
9. //输出数据元素 
10. template <class T1> 
11. void OutPut(T1 out[(2*n)]) 
12. {  
13. for (int i=0; i<(2*n); i++) 
14. {  
15. cout<<out[i]<<" "; 
16. } 
17. cout<<endl; 
18. }  
19. //输入数据元素  
20. template <class T2> 
21. void InPut(T2 in[n]) 
22. { 
23. cout<<"请输入5个数据元素："; 
24. for (int i=0; i<n; i++) 
25. {  
26. cin>>in[i]; 
27. cout<<" ";  
28. } 
29. cout<<endl; 
30. } 
31. //模版函数 输入线性表元素并将其排序 
32. template <class T3>  
33. void MySort(T3 a[2*n]) 
34. { 
35. int temp; //交换数据临时变量  
36. //冒泡锚序  
37. for (int i=0; i<2*n-1; i++) 
38. { 
39. for (int j=0; j<2*n-1-i; j++) 
40. { 
41. if (a[j]>a[j+1])  
42. { 
43. temp = a[j]; 
44. a[j] = a[j+1]; 
45. a[j+1] = temp;  
46. } 
47. } 
48. } 
49. } 
50. //模版函数 归并  
51. template <class T>  
52. void MergeList(T La[n], T Lb[n], T Lc[(2*n)])  
53. { 
54. int i = 0; //作为La的下标  
55. int j = 0; //Lb下标 
56. int k = 0; //Lc下标  
57. //将La Lb组合成在一起  
58. while (i<n && j<n) 
59. { 
60. if (La[i] < Lb[j]) 
61. { 
62. Lc[k] = La[i]; 
63. k++; 
64. Lc[k] = Lb[j]; 
65. } 
66. else 
67. { 
68. if (La[i] == Lb[j]) 
69. { 
70. Lc[k] = La[i]; 
71. k++; 
72. Lc[k] = Lb[j]; 
73. } 
74. else 
75. { 
76. Lc[k] = Lb[j]; 
77. k++; 
78. Lc[k] = La[i]; 
79. } 
80. } 
81. //各下标往下移动  
82. i++; 
83. j++; 
84. k++; 
85. }  
86. //如果La中的数据没有取完，及La比Lb长，则将La剩下的元素插入Lc中 这里是进行扩展  
87. while (i<=n) 
88. { 
89. Lc[k++] = La[i++]; 
90. }  
91. //如果Lb中的数据没有取完，及Lb比La长，则将Lb剩下的元素插入Lc中 
92. while (j<=n) 
93. { 
94. Lc[k++] = Lb[j++]; 
95. }  
96. //对组合好的元素进行排序  
97. MySort(Lc);  
98. } 
99. int main() 
100. { 
101. int a1[n],a2[n], a[(2*n)]; 
102. double b1[n], b2[n],b[(2*n)]; 
103. char m1[n], m2[n], m[(2*n)]; 
104. //输入数据 归并输出  
105. /*InPut(a1); 
106. InPut(a2);  
107. MergeList(a1,a2,a); 
108. OutPut(a); */ 
109. InPut(m1); 
110. InPut(m2);  
111. MergeList(m1,m2,m); 
112. OutPut(m);  
113. system("pause"); 
114. return 0; 
115. }  

希望本文所述对大家的C++程序设计有所帮助。