算法分析作业(C|C++版本)

算法分析作业：

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 InternetCodeAlgorithmssortArray.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("
快速排序法：");
56     QuickSort(a, Length);
57     Print(a, Length);
58     printf("
冒泡排序法：");
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 InternetCodeAlgorithmscatchString.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]!=''; i++)
15     {
16         for(j=0; cmp[j]!=''; j++)
17         {
18             if(s[i] !=cmp [j])
19                 break;
20             else
21                 i++;
22         }
23         if(cmp[j] == '')
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] = {""};
33     printf("源字符串：%s
", 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 InternetCodeAlgorithmsMutiplyLarge.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
", 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 InternetCodeAlgorithmsArrangment.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("
");
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);
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 InternetCodeAlgorithmsSonSet.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("
");
32     }
33 }
34 
35 int main() {
36     int n = 0;
37     printf("请输入集合的元素个数n: ");
38     scanf("%d", &n);
39     printf("集合的子集如下：
");
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 InternetCodeAlgorithmsInsertSort.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("
");
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 InternetCodeAlgorithmsEMutiply.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
", 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 InternetCodeAlgorithmsavlTree.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 InternetCodeAlgorithmsAVLMain.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树...
");
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("
");
23     }
24 
25     printf(">>> 2.删除关键字...
");
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("
");
32     }
33     
34     printf(">>> 3.销毁AVL树...
");
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 InternetCodeAlgorithmsB3Tree.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 InternetCodeAlgorithmsB3Main.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树...
");
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("
");
21     }
22 
23     printf(">>> 2.输出2-3树...
");
24     dispTree(b);
25     printf("
");
26 
27     printf(">>> 3.删除关键树...
");
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("
");
34     }
35     
36     printf(">>> 4.销毁2-3树...
");
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 InternetCodeAlgorithmsActivity.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("
");
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("
被安排活动总数为：%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. 请输入每个活动的开始时间与结束时间(空格分开)
");
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 InternetCodeAlgorithmsKnapsack.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("
");
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])：
");
79         for(int i=0; i<n; i++)
80             if(take[i] > 0)
81                 printf("	%6.2f/%6.2f[%4.2f]
", v[i], w[i], take[i]);
82         printf("
背包的总价值为：%.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 }