演算法分析作業：
1. 使用快速排序和冒泡排序進行陣列排序
2. 使用蠻力法進行字串匹配
3. 實作大整數乘法
4. 實作回圈賽制安排表
5. 運用減一演算法，生成一個n個元素集合的冪集
6. 使用插人排序對序列2,6,1,4,5,3,2進行排序
7. 實作俄式乘法
8. 實作AVL樹
9. 實作2-3樹
10. 貪心演算法實作活動安排
11. 貪心演算法實作背包問題
1. 使用快速排序和冒泡排序進行陣列排序
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-01 08:54:13 4 * @LastEditTime: 2020-04-01 10:12:08 5 * @LastEditors: bpf 6 * @Description: 使用快速和冒泡排序陣列 7 * @FilePath: \Learn in the Internet\Code\Algorithms\sortArray.cpp 8 */ 9 #include <stdio.h> 10 11 void Print(int a[], int n) 12 { 13 for(int i=0; i<n; i++) 14 printf("%d ", a[i]); 15 } 16 17 void Switch(int *a, int *b) 18 { 19 int tmp = 0; 20 tmp = *a; 21 *a = *b; 22 *b = tmp; 23 } 24 25 void QuickSort(int a[], int n) 26 { 27 int min = 0, tmp = 0; 28 for(int i=0; i<n-1; i++) 29 { 30 min = i; 31 for(int j=i+1; j<n; j++) 32 if(a[min] > a[j]) 33 min = j; 34 35 if(min != i) 36 Switch(a+min, a+i); 37 } 38 } 39 40 void BubbleSort(int a[], int n) 41 { 42 int tmp = 0; 43 for(int i=0; i<=n-2; i++) 44 for(int j=0; j<=n-2-i; j++) 45 if(a[j] > a[j+1]) 46 Switch(a+j, a+j+1); 47 } 48 49 int main() 50 { 51 int a [7] = {2, 6, 1, 4, 5, 3, 2}; 52 int Length = 7; 53 printf("原陣列："); 54 Print(a, Length); 55 printf("\n快速排序法："); 56 QuickSort(a, Length); 57 Print(a, Length); 58 printf("\n冒泡排序法："); 59 BubbleSort(a, Length); 60 Print(a, Length); 61 return 0; 62 } 63 64 /****** 快速排序 65 1. 獲得源陣列a 66 2. 輸出源陣列a 67 3. min = 0, 表示默認第一個元素為最小 68 4. i = 0, j = i+1 69 5. 第i輪排序, 從第j個元素開始, 與第min個元素比較 70 如果a[min] > a[j], 則 min = j 71 如果a[min] < a[j], 則跳過 72 6. j++ 直到 j == n 73 7. i++ 74 8. 回圈執行第5、6、7步，直到i == n-2 75 9. 輸出排序后陣列a 76 77 ******* 冒泡排序 78 1. 獲得源陣列a 79 2. 輸出源陣列a 80 3. i = 0, j = 0 81 4. 第i輪排序, 從第j個元素開始, 與第j+1個元素比較 82 如果a[j] > a[j+1], 則交換兩個數 83 如果a[j] < a[j+1], 則跳過 84 5. j++ 直到 j == n-2-i 85 6. i++ 86 7. 回圈執行第4、5、6步，直到i == n-2 87 8. 輸出排序后陣列a 88 */
2. 使用蠻力法進行字串匹配
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-01 09:21:35 4 * @LastEditTime: 2020-04-01 09:47:06 5 * @LastEditors: bpf 6 * @Description: 使用蠻力法進行字串匹配 7 * @FilePath: \Learn in the Internet\Code\Algorithms\catchString.cpp 8 */ 9 #include <stdio.h> 10 11 int catStr(char s[], char cmp[]) 12 { 13 int i = 0, j = 0; 14 for(i=0; s[i]!='\0'; i++) 15 { 16 for(j=0; cmp[j]!='\0'; j++) 17 { 18 if(s[i] !=cmp [j]) 19 break; 20 else 21 i++; 22 } 23 if(cmp[j] == '\0') 24 return true; 25 } 26 return false; 27 } 28 29 int main() 30 { 31 char s[100] = "I like apples and pears."; 32 char cmp[16] = {"\0"}; 33 printf("源字串：%s\n", s); 34 printf("請輸入匹配的字串:"); 35 scanf("%s", cmp); 36 if(catStr(s, cmp)) 37 printf("Yes"); 38 else 39 printf("No"); 40 } 41 42 /* 字串匹配 43 1. 獲得源字串s 44 2. 輸入匹配的字串cmp 45 3. i = 0, j = 0 46 4. 判斷字串s與字串cmp的第i個字符 47 如果不同則移到字串s的下一個字符, 即i++ 48 如果相同則再匹配cmp的第二個字符, 即j++ 49 5. 重復第4步, 直到匹配完字串s 50 6. 輸出結果 51 */
第1、2部分的 執行結果：
3. 實作大整數乘法
1 /* 2 * @Author: bpf 3 * @Description: 大整數乘法，此處數字使用十進制 4 * @FilePath: \Learn in the Internet\Code\Algorithms\MutiplyLarge.cpp 5 */ 6 7 #include <stdio.h> 8 #include <math.h> 9 10 /** 獲取整數符號 */ 11 int sign(int x) { 12 if(x > 0) 13 return 1; 14 else if(x == 0) 15 return 0; 16 else 17 return -1; 18 } 19 20 /** 大整數乘法運算 */ 21 long int Mutiply(int x, int y, int n) { 22 int s = sign(x) * sign(y); // 符號 23 x = abs(x); // 取絕對值 24 y = abs(y); // 取絕對值 25 26 if(n == 1) { 27 if(x!=0 && y!=0) 28 return s*x*y; 29 else 30 return 0; 31 } 32 else { 33 int a = x / pow(10, n/2); // a為x的左半邊 34 int b = x % int(pow(10, n/2)); // b為x的右半邊 35 int c = y / pow(10, n/2); // c為y的左半邊 36 int d = y % int(pow(10, n/2)); // d為y的右半邊 37 38 int m1 = Mutiply(a, c, n/2); 39 int m2 = Mutiply(a-b, d-c, n/2); 40 int m3 = Mutiply(b, d, n/2); 41 s = s * (m1*pow(10, n) + (m1+m2+m3)*pow(10, n/2) + m3); 42 // printf("a=%d, b=%d, c=%d, d=%d, m1=%d, m2=%d, m3=%d, s=%d\n", a,b,c,d,m1,m2,m3,s); 43 44 return s; 45 } 46 } 47 48 int main() { 49 int x = 3141, y = 5327, n = 4; 50 printf("%d*%d = %d", x, y, Mutiply(x, y, n)); 51 }
4. 實作回圈賽制安排表
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-15 11:03:14 4 * @LastEditTime: 2020-04-15 11:53:04 5 * @Description: 回圈賽安排 6 * @FilePath: \Learn in the Internet\Code\Algorithms\Arrangment.cpp 7 */ 8 #include <stdio.h> 9 #define N 8 10 11 /** 輸出陣列 */ 12 void printArray(int n, int a[][N]) { 13 for(int i=0; i<n; i++) { 14 for(int j=0; j<n; j++) { 15 printf("%2d ", a[i][j]); 16 } 17 printf("\n"); 18 } 19 } 20 21 void merger(int n, int a[][N]) { 22 int m = n/2; 23 for(int i=0; i<m; i++) { 24 for(int j=0; j<m; j++) { 25 a[i][j+m] = a[i][j] + m; 26 a[i+m][j] = a[i][j+m]; 27 a[i+m][j+m] = a[i][j]; 28 } 29 } 30 } 31 32 void arrangment(int n, int a[][N]) { 33 if(n == 1) { 34 a[0][0] = 1; 35 return; 36 } 37 arrangment(n/2, a); 38 merger(n, a); 39 } 40 41 int main() { 42 int a[N][N] = {0}; 43 arrangment(N, a); 44 printf("N == %d:\n", N); 45 printArray(N, a); 46 }
第3、4部分的 執行結果：
5. 運用減一演算法，生成一個n個元素集合的冪集
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-29 09:51:30 4 * @LastEditTime: 2020-04-29 11:27:21 5 * @Description: 集合的冪集, 使用0、1表示第i個元素是否存在, 如下所示 6 * 000: 空集 | 001: a1 | 010: a2 | 110: a1,a2 7 * @FilePath: \Learn in the Internet\Code\Algorithms\SonSet.cpp 8 */ 9 #include <stdio.h> 10 #include <string.h> 11 12 void SonSet(int n) { 13 short bit[1000][n]; 14 memset(bit, 0, sizeof(bit)); // 值置為0 15 int sum = 1, count = 1; // sum計算第i輪生成的子集個數,count計算總個數 16 for(int i=n-1; i>=0; i--) { 17 for(int j=0; j<sum; j++) 18 { 19 for(int k=0; k<n; k++) 20 bit[sum+j][k] = bit[0+j][k]; // 賦值前sum個給后sum個 21 bit[sum+j][i] = 1; 22 count++; 23 } 24 sum *= 2; 25 } 26 27 for(int i=0; i<count; i++) { // 輸出冪集 28 for(int j=0; j<n; j++) { 29 printf("%d", bit[i][j]); 30 } 31 printf("\n"); 32 } 33 } 34 35 int main() { 36 int n = 0; 37 printf("請輸入集合的元素個數n: "); 38 scanf("%d", &n); 39 printf("集合的子集如下：\n"); 40 SonSet(n); 41 42 return 0; 43 }
6. 使用插人排序對序列2,6,1,4,5,3,2進行排序
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-29 09:21:09 4 * @LastEditTime: 2020-04-29 11:29:33 5 * @Description: 插入排序 6 * @FilePath: \Learn in the Internet\Code\Algorithms\InsertSort.cpp 7 */ 8 #include <stdio.h> 9 // 插入排序 10 void InsertSort(int a[], int n) { 11 int t = 0, j = 0; 12 for(int i=1; i<n; i++) { 13 t = a[i]; 14 for(j = i-1; j>=0 && a[j]>t; j--) { 15 a[j+1] = a[j]; 16 } 17 a[j+1] = t; 18 } 19 } 20 //輸出序列 21 void printArray(int a[], int n) { 22 for(int i=0; i<n; i++) { 23 printf("%d ", a[i]); 24 } 25 printf("\n"); 26 } 27 28 int main() { 29 int a[7] = {2, 6, 1, 4, 5, 3, 2}; 30 printf("排序前："); 31 printArray(a, 7); 32 InsertSort(a, 7); 33 printf("排序后："); 34 printArray(a, 7); 35 36 return 0; 37 }
7. 實作俄式乘法
1 /* 2 * @Author: bpf 3 * @Date: 2020-04-29 11:10:48 4 * @LastEditTime: 2020-04-29 11:30:57 5 * @Description: 俄氏乘法 6 * @FilePath: \Learn in the Internet\Code\Algorithms\EMutiply.cpp 7 */ 8 #include <stdio.h> 9 10 int EMutiply(int m, int n) { 11 int sum = 0; 12 while (m != 0) 13 { 14 if(m%2 != 0) { 15 sum += n; 16 m--; 17 } 18 else 19 { 20 m /= 2; 21 n *= 2; 22 } 23 } 24 25 return sum; 26 } 27 28 int main() { 29 int m, n; 30 printf("請輸入兩個整數(空格隔開)："); 31 sacnf("%d %d", &m, &n); 32 printf("%d x %d = %d\n", EMutiply(m, n)); 33 }
第6、7部分的執行結果：
8. 實作AVL樹
1 /* 2 * @Author: bpf 3 * @Date: 2020-05-13 08:37:26 4 * @LastEditTime: 2020-05-13 14:15:00 5 * @Description: 演算法實作AVL樹 6 * @FilePath: \Learn in the Internet\Code\Algorithms\avlTree.cpp 7 */ 8 9 #include <stdio.h> 10 #include <malloc.h> 11 typedef int KeyType; // 關鍵字型別 12 typedef char InfoType; // 資料型別 13 typedef struct note 14 { 15 KeyType key; // 關鍵字 16 InfoType data; // 資料域 17 int bf; // 平衡因子 18 struct note *lchild; 19 struct note *rchild; 20 } BSTNode; 21 22 // 輸出AVL樹 23 void dispBSTree(BSTNode *b) 24 { 25 if (b != NULL) 26 { 27 printf("%d[%d]", b->key, b->bf); 28 if (b->lchild != NULL || b->rchild != NULL) 29 { 30 printf("("); 31 dispBSTree(b->lchild); 32 if (b->rchild != NULL) 33 printf(", "); 34 dispBSTree(b->rchild); 35 printf(")"); 36 } 37 } 38 } 39 40 // 插入元素時處理左子樹 41 void leftProcess(BSTNode *&p, int &taller) 42 { 43 BSTNode *p1, *p2; 44 if (p->bf == 0) 45 { // 原左右子樹等高，現左子樹高右子樹1 46 p->bf = 1; 47 taller = 1; 48 } 49 else if (p->bf == -1) 50 { // 原左子樹低右子樹1，現左右子樹登高 51 p->bf = 0; 52 taller = 0; 53 } 54 else 55 { 56 p1 = p->lchild; 57 if (p1->bf == 1) 58 { // 新結點插入在結點b的左孩子的左子樹上,要作LL調整 59 p->lchild = p1->rchild; 60 p1->rchild = p; 61 p->bf = p1->bf = 0; 62 p = p1; 63 } 64 else if (p1->bf == -1) 65 { // 新結點插入在結點b的左孩子的右子樹上,要作LR調整 66 p2 = p1->rchild; 67 p1->rchild = p2->lchild; 68 p2->lchild = p1; 69 p->lchild = p2->rchild; 70 p2->rchild = p; 71 if (p2->bf == 0) // 新結點插在p2處作為葉子結點的情況 72 p->bf = p1->bf = 0; 73 else if (p2->bf == 1) 74 { // 新結點插在p2的左子樹上的情況 75 p1->bf = 0; 76 p->bf = -1; 77 } 78 else 79 { // 新結點插在p2的右子樹上的情況 80 p1->bf = 1; 81 p->bf = 0; 82 } 83 p = p2; 84 p->bf = 0; // 仍將p指向新的根結??,并置其bf值為0 85 } 86 taller = 0; 87 } 88 } 89 90 // 插入元素時處理右子樹 91 void rightProcess(BSTNode *&p, int &taller) 92 { 93 BSTNode *p1, *p2; 94 if (p->bf == 0) 95 { // 原左右子樹等高，現左子樹低右子樹1 96 p->bf = -1; 97 taller = 1; 98 } 99 else if (p->bf == 1) 100 { // 原左子樹高右子樹1，現左右子樹等高 101 p->bf = 0; 102 taller = 0; 103 } 104 else 105 { 106 p1 = p->rchild; 107 if (p1->bf == -1) 108 { // 新結點插入在結點b的右孩子的右子樹上,要作RR調整 109 p->rchild = p1->lchild; 110 p1->lchild = p; 111 p->bf = p1->bf = 0; 112 p = p1; 113 } 114 else if (p1->bf == 1) 115 { // 新結點插入在結點b的右孩子的左子樹上,要作RL調整 116 p2 = p1->lchild; 117 p1->lchild = p2->rchild; 118 p2->rchild = p1; 119 p->rchild = p2->lchild; 120 p2->lchild = p; 121 if (p2->bf == 0) //新結點插在p2處作為葉子結點的情況 122 p->bf = p1->bf = 0; 123 else if (p2->bf == -1) 124 { //新結點插在p2的右子樹上的情況 125 p1->bf = 0; 126 p->bf = 1; 127 } 128 else 129 { //新結點插在p2的左子樹上的情況 130 p1->bf = -1; 131 p->bf = 0; 132 } 133 p = p2; 134 p->bf = 0; //仍將p指向新的根結??,并置其bf值為0 135 } 136 taller = 0; 137 } 138 } 139 140 // 插入元素 141 int insertElement(BSTNode *&b, KeyType e, int &taller) 142 { 143 if (b == NULL) 144 { 145 b = (BSTNode *)malloc(sizeof(BSTNode)); 146 b->key = e; 147 b->lchild = b->rchild = NULL; 148 b->bf = 0; 149 taller = 1; 150 } 151 else 152 { 153 if (e == b->key) 154 { //樹中已存在和e有相同關鍵字的結點則不再插入 155 taller = 0; 156 return 0; 157 } 158 if (e < b->key) 159 { 160 if ((insertElement(b->lchild, e, taller)) == 0) 161 return 0; 162 if (taller == 1) //已插入到結點b的左子樹中且左子樹長高 163 leftProcess(b, taller); 164 } 165 else 166 { 167 if ((insertElement(b->rchild, e, taller)) == 0) 168 return 0; 169 if (taller == 1) //已插入到b的右子樹且右子樹長高 170 rightProcess(b, taller); 171 } 172 } 173 return 1; 174 } 175 176 // 洗掉元素時處理左子樹 177 void leftProcessDelete(BSTNode *&p, int &taller) //在洗掉結點時進行左側處理 178 { 179 BSTNode *p1, *p2; 180 if (p->bf == 1) 181 { 182 p->bf = 0; 183 taller = 1; 184 } 185 else if (p->bf == 0) 186 { 187 p->bf = -1; 188 taller = 0; 189 } 190 else 191 { 192 p1 = p->rchild; 193 if (p1->bf == 0) 194 { //需作RR調整 195 p->rchild = p1->lchild; 196 p1->lchild = p; 197 p1->bf = 1; 198 p->bf = -1; 199 p = p1; 200 taller = 0; 201 } 202 else if (p1->bf == -1) 203 { //需作RL調整 204 p->rchild = p1->lchild; 205 p1->lchild = p; 206 p->bf = p1->bf = 0; 207 p = p1; 208 taller = 1; 209 } 210 else 211 { //需作RL調整 212 p2 = p1->lchild; 213 p1->lchild = p2->rchild; 214 p2->rchild = p1; 215 p->rchild = p2->lchild; 216 p2->lchild = p; 217 if (p2->bf == 0) 218 { 219 p->bf = 0; 220 p1->bf = 0; 221 } 222 else if (p2->bf == -1) 223 { 224 p->bf = 1; 225 p1->bf = 0; 226 } 227 else 228 { 229 p->bf = 0; 230 p1->bf = -1; 231 } 232 p2->bf = 0; 233 p = p2; 234 taller = 1; 235 } 236 } 237 } 238 239 // 洗掉元素時處理右子樹 240 void rightProcessDelete(BSTNode *&p, int &taller) //在洗掉結點時進行右側處理 241 { 242 BSTNode *p1, *p2; 243 if (p->bf == -1) 244 { 245 p->bf = 0; 246 taller = -1; 247 } 248 else if (p->bf == 0) 249 { 250 p->bf = 1; 251 taller = 0; 252 } 253 else 254 { 255 p1 = p->lchild; 256 if (p1->bf == 0) 257 { //需作LL調整 258 p->lchild = p1->rchild; 259 p1->rchild = p; 260 p1->bf = -1; 261 p->bf = 1; 262 p = p1; 263 taller = 0; 264 } 265 else if (p1->bf == 1) 266 { //需作RL調整 267 p->lchild = p1->rchild; 268 p1->rchild = p; 269 p->bf = p1->bf = 0; 270 p = p1; 271 taller = 1; 272 } 273 else 274 { //需作LR調整 275 p2 = p1->rchild; 276 p1->rchild = p2->lchild; 277 p2->lchild = p1; 278 p->lchild = p2->rchild; 279 p2->rchild = p; 280 if (p2->bf == 0) 281 { 282 p->bf = 0; 283 p1->bf = 0; 284 } 285 else if (p2->bf == 1) 286 { 287 p->bf = -1; 288 p1->bf = 0; 289 } 290 else 291 { 292 p->bf = 0; 293 p1->bf = 1; 294 } 295 p2->bf = 0; 296 p = p2; 297 taller = 1; 298 } 299 } 300 } 301 302 // 處理被洗掉節點左右子樹不空的情況 303 void deleteNotNull(BSTNode *q, BSTNode *&r, int &taller) 304 { 305 if (r->rchild == NULL) 306 { 307 q->key = r->key; 308 q = r; 309 r = r->lchild; 310 free(q); 311 taller = 1; 312 } 313 else 314 { 315 deleteNotNull(q, r->rchild, taller); 316 if (taller == 1) 317 rightProcessDelete(r, taller); 318 } 319 } 320 321 // 洗掉元素 322 int deleteElement(BSTNode *&p, KeyType x, int &taller) 323 { 324 int k; 325 BSTNode *q; 326 if (p == NULL) 327 return 0; 328 else if (x < p->key) 329 { 330 k = deleteElement(p->lchild, x, taller); 331 if (taller == 1) 332 leftProcessDelete(p, taller); 333 return k; 334 } 335 else if (x > p->key) 336 { 337 k = deleteElement(p->rchild, x, taller); 338 if (taller == 1) 339 rightProcessDelete(p, taller); 340 return k; 341 } 342 else 343 { 344 q = p; 345 if (p->rchild == NULL) 346 { // 被刪結點右子樹為空 347 p = p->lchild; 348 free(q); 349 taller = 1; 350 } 351 else if (p->lchild == NULL) 352 { // 被刪結點左子樹為空 353 p = p->rchild; 354 free(q); 355 taller = 1; 356 } 357 else 358 { // 被刪結點左右子樹均不空 359 deleteNotNull(q, q->lchild, taller); 360 if (taller == 1) 361 leftProcessDelete(q, taller); 362 p = q; 363 } 364 return 1; 365 } 366 } 367 368 // 銷毀AVL樹 369 void destroyBSTree(BSTNode *&b) 370 { 371 if (b != NULL) 372 { 373 destroyBSTree(b->lchild); 374 destroyBSTree(b->rchild); 375 free(b); 376 } 377 }
主函式：
1 /* 2 * @Author: bpf 3 * @Date: 2020-05-13 10:49:57 4 * @LastEditTime: 2020-05-13 13:47:11 5 * @Description: AVL測驗 6 * @FilePath: \Learn in the Internet\Code\Algorithms\AVLMain.cpp 7 */ 8 9 # include <stdio.h> 10 # include "avlTree.cpp" 11 12 int main() { 13 BSTNode *b = NULL; 14 KeyType a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15}; 15 int n = 9; 16 int taller = 0; 17 printf(">>> 1.創建AVL樹...\n"); 18 for(int i=0; i<n; i++) { 19 printf(" 步驟%d: 插入元素%2d ", i+1, a[i]); 20 insertElement(b, a[i], taller); 21 dispBSTree(b); 22 printf("\n"); 23 } 24 25 printf(">>> 2.洗掉關鍵字...\n"); 26 int e[] = {11, 9, 14}; 27 for(int i=0; i<3; i++) { 28 printf(" 步驟%d: 洗掉元素%2d ", i+1, e[i]); 29 deleteElement(b, e[i], taller); 30 dispBSTree(b); 31 printf("\n"); 32 } 33 34 printf(">>> 3.銷毀AVL樹...\n"); 35 destroyBSTree(b); 36 37 return 0; 38 }
9. 實作2-3樹
此演算法中洗掉元素方法還不夠完善，
1 /* 2 * @Author: bpf 3 * @Date: 2020-05-13 14:11:00 4 * @LastEditTime: 2020-05-13 20:45:45 5 * @Description: 實作2-3樹 6 * @FilePath: \Learn in the Internet\Code\Algorithms\B3Tree.cpp 7 */ 8 9 #include <stdio.h> 10 #include <malloc.h> 11 #include <memory.h> 12 #define NUM(p) ((p==NULL)? 0 : p->num) 13 14 typedef struct node { 15 int a[3]; 16 int num; // 存盤陣列長度1,2,3 17 18 struct node *left_child; 19 struct node *mid_child; 20 struct node *right_child; 21 struct node *tmp_child; 22 23 struct node *parent; 24 } Btree, *BtreePtr; 25 26 void exchange(int *a, int *b) { 27 int tmp = *a; 28 *a = *b; 29 *b = tmp; 30 } 31 32 // 創建節點 33 BtreePtr _node(const int key) { 34 BtreePtr p = (BtreePtr)malloc(sizeof(Btree)); 35 if (p != NULL) { 36 memset(p, 0, sizeof(p)); 37 p->a[0] = key; 38 p->num = 1; 39 p->left_child = NULL; 40 p->right_child = NULL; 41 p->mid_child = NULL; 42 p->tmp_child = NULL; 43 p->parent = NULL; 44 } 45 else { 46 puts("記憶體不足"); 47 } 48 return p; 49 } 50 51 // 排序陣列 52 void _sort(BtreePtr b) { 53 int length = b->num; 54 for (int i = 0; i < length; i++) { 55 for (int j = i; j < length; j++) { 56 if ((b->a[j]) < (b->a[i])) { 57 exchange(&(b->a[j]), &(b->a[i])); 58 } 59 } 60 } 61 } 62 63 // 平衡2-3樹 64 BtreePtr _checkNum(BtreePtr p) { 65 if (NUM(p) == 1) { //2-結點 66 if (NUM(p->left_child) == 3) { //case 2 67 p->a[1] = p->left_child->a[1]; 68 p->num++; 69 _sort(p); 70 71 BtreePtr l = _node(p->left_child->a[0]); 72 l->left_child = p->left_child->left_child; 73 l->parent = p; 74 75 BtreePtr r = _node(p->left_child->a[2]); 76 r->left_child = p->left_child->mid_child; 77 r->right_child = p->left_child->right_child; 78 r->parent = p; 79 80 81 p->left_child = l; 82 p->mid_child = r; 83 } 84 else if (NUM(p->right_child) == 3) { //case 3 85 p->a[1] = p->right_child->a[1]; 86 p->num++; 87 _sort(p); 88 89 BtreePtr l = _node(p->right_child->a[0]); 90 l->left_child = p->right_child->left_child; 91 l->parent = p; 92 93 BtreePtr r = _node(p->right_child->a[2]); 94 r->left_child = p->right_child->mid_child; 95 r->right_child = p->right_child->right_child; 96 r->parent = p; 97 98 p->mid_child = l; 99 p->right_child = r; 100 } 101 102 } 103 else if (NUM(p) == 2) { //3-結點 104 if (NUM(p->left_child) == 3) { //case 4 105 p->a[2] = p->left_child->a[1]; 106 p->num++; 107 _sort(p); 108 109 p->tmp_child = p->mid_child; 110 p->mid_child = _node(p->left_child->a[2]); 111 112 BtreePtr l = _node(p->left_child->a[0]); 113 l->left_child = p->left_child->left_child; 114 l->right_child = p->left_child->mid_child; 115 l->parent = p; 116 117 BtreePtr r = _node(p->left_child->a[2]); 118 r->left_child = p->left_child->tmp_child; 119 r->right_child = p->left_child->right_child; 120 r->parent = p; 121 122 p->left_child = l; 123 } 124 else if (NUM(p->right_child) == 3) { //case 5 125 p->a[2] = p->right_child->a[1]; 126 p->num++; 127 _sort(p); 128 129 p->tmp_child = _node(p->right_child->a[2]); // 130 131 BtreePtr l = _node(p->right_child->a[0]); 132 l->right_child = p->right_child->left_child; 133 l->right_child = p->right_child->mid_child; 134 l->parent = p; 135 136 BtreePtr r = _node(p->right_child->a[2]); 137 r->right_child = p->right_child->tmp_child; 138 r->right_child = p->right_child->right_child; 139 r->parent = p; 140 141 p->right_child = l; 142 } 143 else if (NUM(p->mid_child) == 3) { 144 p->a[2] = p->mid_child->a[1]; 145 p->num++; 146 _sort(p); 147 148 //p->tmp_child = p->mid_child; 149 //p->mid_child = _node(p->left_child->a[2]); 150 151 BtreePtr l = _node(p->mid_child->a[0]); 152 l->left_child = p->mid_child->left_child; 153 l->right_child = p->mid_child->mid_child; 154 l->parent = p; 155 156 BtreePtr r = _node(p->mid_child->a[2]); 157 r->left_child = p->mid_child->tmp_child; 158 r->right_child = p->mid_child->right_child; 159 r->parent = p; 160 161 p->mid_child = l; 162 p->tmp_child = r; 163 } 164 } 165 if (p->num == 3) { 166 if (p->parent == NULL) { // case 1; 167 BtreePtr t = p->left_child; 168 p->left_child = _node(p->a[0]); 169 p->left_child->left_child = t; 170 p->left_child->right_child = p->mid_child; 171 p->left_child->parent = p; 172 173 t = p->right_child; 174 p->right_child = _node(p->a[2]); 175 p->right_child->left_child = p->tmp_child; 176 p->right_child->right_child = t; 177 p->right_child->parent = p; 178 179 p->mid_child = NULL; 180 p->tmp_child = NULL; 181 182 p->a[0] = p->a[1]; 183 p->num = p->num - 2; 184 } 185 } 186 return p; 187 } 188 189 // 插入元素子函式 190 BtreePtr _insertBTree(BtreePtr b, const int key, const int pos) { 191 if (b->left_child == NULL && b->right_child == NULL) { //葉子節點 192 b->a[b->num] = key; 193 b->num++; 194 _sort(b); 195 } 196 else { 197 if (b->num == 1) { 198 if (key < b->a[0]) { //num =1, 2 199 b->left_child = _insertBTree(b->left_child, key, pos); 200 } 201 else if (key > b->a[0]) { //num = 2 202 b->right_child = _insertBTree(b->right_child, key, pos); 203 } 204 } 205 else if (b->num == 2) { 206 if (key < b->a[0]) { //num =1, 2 207 b->left_child = _insertBTree(b->left_child, key, pos); 208 } 209 else if (key > b->a[1]) { //num = 2 210 b->right_child = _insertBTree(b->right_child, key, pos); 211 } 212 else { 213 b->mid_child = _insertBTree(b->mid_child, key, pos); 214 } 215 } 216 } 217 218 b = _checkNum(b); 219 return b; 220 } 221 222 // 插入元素 223 BtreePtr insertBTree(BtreePtr root, const int key, const int pos) { 224 if (root == NULL) { 225 root = _node(key); 226 } 227 else { 228 root = _insertBTree(root, key, pos); 229 } 230 return root; 231 } 232 233 // 處理洗掉節點資料項只有一個的情況 234 BtreePtr _deleteGen(BtreePtr b, const int key) { 235 BtreePtr b1 = b->right_child; 236 237 if(b1->num == 1 && (b1->left_child==NULL || b1->right_child==NULL)) { 238 // b = insertBTree(b->left_child, b1->a[0], b->left_child->num+1); // 此方法不理想 239 // b->num++; 240 // b->left_child = b->right_child = NULL; 241 // free(b1->parent); 242 // free(b1); 243 244 b1->left_child = b->left_child; 245 free(b); 246 b = b1; 247 } 248 else if(b1->num == 1 && (b1->left_child!=NULL || b1->right_child!=NULL)) { 249 b->a[0] = b1->a[0]; 250 _deleteGen(b1, key); 251 } 252 else if(b1->num == 2) { 253 b->a[0] = b1->a[0]; 254 b1->a[0] = b1->a[1]; 255 b1->num--; 256 } 257 // else if(b1->num == 2 && (b1->left_child!=NULL || b1->right_child!=NULL)) { // 包含在第三種情況中 258 // b->a[0] = b1->a[0]; 259 // b1->a[0] = b1->a[1]; 260 // b1->num--; 261 // } 262 263 return b; 264 } 265 266 // 處理洗掉元素子函式 267 BtreePtr _deleteBTree(BtreePtr b, const int key) { 268 if (b->left_child == NULL && b->right_child == NULL) { // 葉子節點 269 switch (b->num) { 270 case 1: 271 if(b->a[0] == key); 272 break; 273 case 2: 274 if(b->a[0] == key) 275 b->a[0] = b->a[1]; 276 else if(b->a[1] == key); 277 break; 278 case 3: 279 if(b->a[0] == key) { 280 b->a[0] = b->a[1]; 281 b->a[1] = b->a[2]; 282 } 283 else if(b->a[1] == key) 284 b->a[1] = b->a[2]; 285 else if(b->a[2] == key); 286 break; 287 } 288 if(b != NULL) 289 b->num--; 290 // _sort(b); 291 _checkNum(b); 292 } 293 else { 294 if (b->num == 1) { 295 if (key < b->a[0]) { //num =1, 2 296 b->left_child = _deleteBTree(b->left_child, key); 297 if(b->left_child->num == 0) 298 b->left_child = NULL; 299 } 300 else if (key > b->a[0]) { //num = 2 301 b->right_child = _deleteBTree(b->right_child, key); 302 if(b->right_child->num == 0) 303 b->right_child = NULL; 304 } 305 else 306 b = _deleteGen(b, key); 307 } 308 else if (b->num == 2) { 309 if(key == b->a[0]) { 310 b->a[0] = b->a[1]; 311 b->num--; 312 } 313 else if(key == b->a[1]) { 314 b->num--; 315 } 316 else if (key < b->a[0]) { //num =1, 2 317 b->left_child = _deleteBTree(b->left_child, key); 318 } 319 else if (key > b->a[1]) { //num = 2 320 b->right_child = _deleteBTree(b->right_child, key); 321 } 322 else { 323 b->mid_child = _deleteBTree(b->mid_child, key); 324 } 325 } 326 } 327 328 b = _checkNum(b); 329 return b; 330 } 331 332 // 洗掉元素 333 BtreePtr deleteBTree(BtreePtr root, const int key) { 334 if (root == NULL) { 335 return root; 336 } 337 else { 338 root = _deleteBTree(root, key); 339 } 340 return root; 341 } 342 343 // 輸出2-3樹 344 void dispTree(BtreePtr p) { 345 if(p != NULL) { 346 switch (NUM(p)) 347 { 348 case 1: 349 printf("[%d]", p->a[0]); 350 break; 351 case 2: 352 printf("[%d,%d]", p->a[0], p->a[1]); 353 break; 354 case 3: 355 printf("[%d,%d,%d]", p->a[0], p->a[1], p->a[2]); 356 break; 357 } 358 if(p->left_child!= NULL || p->mid_child!= NULL || p->right_child!= NULL) { 359 printf(" ("); 360 dispTree(p->left_child); 361 if (p->mid_child != NULL) 362 printf(", "); 363 dispTree(p->mid_child); 364 if(p->right_child != NULL) 365 printf(", "); 366 dispTree(p->right_child); 367 printf(")"); 368 } 369 } 370 } 371 372 // 銷毀2-3樹 373 void freeTree(BtreePtr p) { 374 if (p->left_child != NULL) { 375 freeTree(p->left_child); 376 } 377 if (p->right_child != NULL) { 378 freeTree(p->right_child); 379 } 380 if (p->mid_child != NULL) { 381 freeTree(p->mid_child); 382 } 383 free(p); 384 p = NULL; 385 }
主函式：
1 /* 2 * @Author: bpf 3 * @Date: 2020-05-13 20:36:47 4 * @LastEditTime: 2020-05-13 20:40:30 5 * @Description: 測驗2-3樹 6 * @FilePath: \Learn in the Internet\Code\Algorithms\B3Main.cpp 7 */ 8 # include <stdio.h> 9 # include "B3Tree.cpp" 10 11 int main() { 12 int a[] = {9, 5, 8, 3, 2, 4, 7}; 13 int n = 7; 14 printf(">>> 1.創建2-3樹...\n"); 15 BtreePtr b = NULL; 16 for (int i = 0; i < n; i++) { 17 b = insertBTree(b, a[i], i); 18 printf(" 步驟%d: 插入元素%2d ", i+1, a[i]); 19 dispTree(b); 20 printf("\n"); 21 } 22 23 printf(">>> 2.輸出2-3樹...\n"); 24 dispTree(b); 25 printf("\n"); 26 27 printf(">>> 3.洗掉關鍵樹...\n"); 28 int e[] = {4, 8}; 29 for(int i=0; i<2; i++) { 30 printf(" 步驟%d: 洗掉元素%2d ", i+1, e[i]); 31 b = deleteBTree(b, e[i]); 32 dispTree(b); 33 printf("\n"); 34 } 35 36 printf(">>> 4.銷毀2-3樹...\n"); 37 freeTree(b); 38 return 0; 39 }
10. 貪心演算法實作活動安排
1 /* 2 * @Author: bpf 3 * @Date: 2020-06-10 09:42:34 4 * @LastEditTime: 2020-06-10 10:49:38 5 * @Description: 活動安排 貪心演算法實作 6 * @FilePath: \Learn in the Internet\Code\Algorithms\Activity.cpp 7 */ 8 9 /* n個活動 start[]存放開始時間 end[]存放結束時間 play[]存放活動是否入選 10 1. 按照結束時間非降序排序陣列end 11 2. 貪心演算法找出結束時間最早的活動，存入play[] 12 3. 找出下一個結束時間最早的相容的活動，存入play[] 13 4. 回圈2、3 14 5. 回傳總活動數量 15 */ 16 #include <stdio.h> 17 #define MAX 100 18 19 void printArray(int n, int a[]) { 20 for(int i=0; i<n; i++) { 21 printf("%d ", a[i]); 22 } 23 printf("\n"); 24 } 25 26 void swit(int *a, int *b) { 27 int tmp = *a; 28 *a = *b; 29 *b = tmp; 30 } 31 32 void upSort(int n, int start[], int end[]) { 33 int min; 34 for(int i=0; i<n-1; i++) { 35 min = i; 36 for(int j=i+1; j<n; j++) { 37 if(end[min] > end[j]) { 38 min = j; 39 } 40 } 41 if(min != i) { 42 swit(end+min, end+i); 43 swit(start+min, start+i); 44 } 45 } 46 } 47 48 int ActivityManage(int n, int start[], int end[], bool printManage) { 49 // play[]置0, 默認所有活動都不安排 50 bool play[MAX] = {0}; 51 // 非降序排序陣列end 52 upSort(n, start, end); 53 // 貪心找出活動 54 play[0] = 1; // 第一個活動被安排 55 int count = 1; // 統計被安排的活動總數 56 for(int i=1, j=0; i<n; i++) { 57 if(start[i] >= end[j]) { 58 play[i] = 1; 59 j = i; 60 count++; 61 } 62 } 63 64 // 輸出被安排活動詳情 65 if(printManage) { 66 // printArray(n, play); 67 printf("被安排活動為："); 68 for(int i=0; i<n; i++) 69 if(play[i]) 70 printf("(%d-%d) ", start[i], end[i]); 71 printf("\n被安排活動總數為：%d", count); 72 } 73 74 return count; 75 } 76 77 int main() { 78 int start [MAX] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; 79 int end [MAX] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; 80 int n = 11; 81 printf("1. 請輸入活動個數："); 82 scanf("%d", &n); 83 printf("2. 請輸入每個活動的開始時間與結束時間(空格分開)\n"); 84 for(int i=0; i<n; i++) { 85 printf("第%d個活動(開始時間 結束時間)：", i+1); 86 scanf("%d %d", &start[i], &end[i]); 87 } 88 89 ActivityManage(n, start, end, true); 90 91 return 0; 92 }
11. 貪心演算法實作背包問題
1 /* 2 * @Author: bpf 3 * @Date: 2020-06-10 10:29:59 4 * @LastEditTime: 2020-06-10 11:11:10 5 * @Description: 背包問題 貪心演算法實作 6 * @FilePath: \Learn in the Internet\Code\Algorithms\Knapsack.cpp 7 */ 8 9 /* 背包容量為W, 價值為V 10 n個物品, 重量分別為w[], 價值為v[] 11 1. 按照v/w從大到小排序 12 2. 貪心找出性價比最高的物品放入背包 13 3. 若背包有空間繼續放性價比最高的物品，若無空間結束 14 4. 回圈2、3 15 5. 回傳背包總價值V 16 */ 17 18 #include <stdio.h> 19 #define MAX 100 20 21 void printArray(int n, float a[]) { 22 for(int i=0; i<n; i++) { 23 printf("%6.3f ", a[i]); 24 } 25 printf("\n"); 26 } 27 28 void swit(float *a, float*b) { 29 float tmp = *a; 30 *a = *b; 31 *b = tmp; 32 } 33 34 void costSort(int n, float v[], float w[], float cost[]) { 35 for(int i=0; i<n; i++) { // 計算性價比 36 cost[i] = v[i] / w[i]; 37 } 38 39 // 快速排序cost[] 40 int min; 41 for(int i=0, j; i<n-1; i++) { 42 min = i; 43 for(j=i+1; j<n; j++) { 44 if(cost[min] < cost[j]) { 45 min = j; 46 } 47 } 48 if(min != i) { 49 swit(cost+min, cost+i); 50 swit(v+min, v+i); 51 swit(w+min, w+i); 52 } 53 } 54 } 55 56 float knapsack(int n, float W, float v[], float w[], bool printManage) { 57 // take[]置0 58 float take[MAX] = {0}; // 存放背包放置i物品的數量 59 // 按照性價比排序 60 float cost[MAX]; // 存放性價比 61 costSort(n, v, w, cost); // 按照性價比排序 62 float V = 0; // 存放背包的總價值 63 // 貪心找出性價比最高的物品 64 int i = 0; 65 while(w[i] < W) { 66 take[i] = 1; 67 V += v[i]; 68 W -= w[i]; 69 i++; 70 } 71 // 剩余空間不足一個物品，此時可拆出其中的零件 72 take[i] = W / w[i]; 73 V += take[i] * v[i]; 74 75 // 輸出被安排活動詳情 76 if(printManage) { 77 // printArray(n, take); 78 printf("背包中的物品為(v/w[take])：\n"); 79 for(int i=0; i<n; i++) 80 if(take[i] > 0) 81 printf("\t%6.2f/%6.2f[%4.2f]\n", v[i], w[i], take[i]); 82 printf("\n背包的總價值為：%.2f", V); 83 } 84 85 return V; 86 } 87 88 89 int main() { 90 float v[MAX] = {60, 120, 50}; 91 float w[MAX] = {20, 30, 10}; 92 int n = 3; 93 float W = 50; 94 knapsack(n, W, v, w, true); 95 96 97 return 0; 98 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/44991.html
標籤：C++