這篇文章主要介紹了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++程序設計有所幫助。