000山寨的笔记

000

受“ID紫麒麟”先生的影响，我也就决定也来发个笔记帖子吧，我也才学不久，就不记一些很难的东西了，而且发上来没准版主看了还给纠正就是捡了天大的漏子了！

000

一个关于中缀法转后缀法的一个程序

1. #include <stdio.h>  
   
2. #include <stdlib.h>  
   
3. #include <string.h>  
   
4.   
   
5. struct __stack  
   
6. {  
   
7.     double number;  
   
8.     char symbol;  
   
9.     struct __stack *next;  
   
10.     struct __stack *prev;  
    
11. };  
    
12. typedef struct __stack* p_list;  
    
13. // cdecl.cpp : 定义控制台应用程序的入口点。  
    
14. //  
    
15.   
    
16.   
    
17. #include "stdafx.h"  
    
18. bool priority(const char a, const char b)  
    
19. {  
    
20.     if ((a == '+' || a == '-') && (b == '*' || b == '/'))  
    
21.         return 1;  
    
22.     else if ((a == '+' || a == '-') && (b == '-' || b == '+'))  
    
23.         return 0;  
    
24.     else if ((a == '*' || a == '/') && (b == '*' || b == '/'))  
    
25.         return 0;  
    
26.     else  
    
27.         return 0;  
    
28. }  
    
29. void BeEmpty(p_list head)               //释放空间，不需要人为调用  
    
30. {  
    
31.     p_list temp = head;  
    
32.     for (; temp != NULL; head = temp)  
    
33.     {  
    
34.         temp = head->next;  
    
35.         free(head);  
    
36.     }  
    
37. }                 
    
38. void frist_time(p_list &head)       //首次创建头节点时使用  
    
39. {  
    
40.     head = (p_list)malloc(sizeof(struct __stack));  
    
41.     head->next = NULL;  
    
42.     head->prev = NULL;  
    
43. }  
    
44. void creat_list(p_list &node)       //创建其余节点时使用  
    
45. {  
    
46.     node->next = (p_list)malloc(sizeof(struct __stack));  
    
47.     node->next->prev = node;  
    
48.     node = node->next;  
    
49.     node->next = NULL;  
    
50. }  
    
51. double calc(p_list head)            //用于计算最后的结果，其中判断运算模式可以自行按照需要修改  
    
52. {  
    
53.     p_list stuck = NULL, temp, h_temp;  
    
54.     double sum;  
    
55.     for (h_temp = head; h_temp != NULL; h_temp = h_temp->next)  
    
56.     {  
    
57.         if (h_temp->symbol == 0)  
    
58.         {  
    
59.             if (stuck == NULL)  
    
60.             {  
    
61.                 frist_time(stuck);  
    
62.                 temp = stuck;  
    
63.             }  
    
64.             else  
    
65.                 creat_list(temp);  
    
66.             temp->number = h_temp->number;  
    
67.         }  
    
68.         else  
    
69.         {  
    
70.             if (h_temp->symbol == '+')  
    
71.             {  
    
72.                 temp->prev->number += temp->number;  
    
73.                 p_list t_temp = temp->prev;  
    
74.                 free(temp);  
    
75.                 temp = t_temp;  
    
76.             }  
    
77.             else if (h_temp->symbol == '-')  
    
78.             {  
    
79.                 temp->prev->number -= temp->number;  
    
80.                 p_list t_temp = temp->prev;  
    
81.                 free(temp);  
    
82.                 temp = t_temp;  
    
83.             }  
    
84.             else if (h_temp->symbol == '*')  
    
85.             {  
    
86.                 temp->prev->number *= temp->number;  
    
87.                 p_list t_temp = temp->prev;  
    
88.                 free(temp);  
    
89.                 temp = t_temp;  
    
90.             }  
    
91.             else if (h_temp->symbol == '/')  
    
92.             {  
    
93.                 temp->prev->number /= temp->number;  
    
94.                 p_list t_temp = temp->prev;  
    
95.                 free(temp);  
    
96.                 temp = t_temp;  
    
97.             }  
    
98.             else  
    
99.             {  
    
100.                 printf("\n******Unexpect symbol******\n");  
     
101.                 BeEmpty(head);  
     
102.                 BeEmpty(stuck);  
     
103.                 exit(1);  
     
104.             }  
     
105.         }  
     
106.     }  
     
107.     sum = stuck->number;  
     
108.     stuck->next = NULL;  
     
109.     BeEmpty(stuck);  
     
110.     BeEmpty(head);  
     
111.     return sum;  
     
112. }  
     
113. p_list scan_list()              //输入中缀表达式  
     
114. {  
     
115.     p_list t_head = NULL, pl_temp;  
     
116.     char c_temp = '#', str_temp[10];  
     
117.     printf("Input the calculation method:");  
     
118.     for (; c_temp != '\n';)  
     
119.     {  
     
120.         if (!scanf_s("%[0-9]", str_temp, 10))  
     
121.         {  
     
122.   
     
123.   
     
124.             if ((c_temp = getchar()) == '\n');  
     
125.             else  
     
126.             {  
     
127.                 if (t_head == NULL)  
     
128.                 {  
     
129.                     frist_time(t_head);  
     
130.                     pl_temp = t_head;  
     
131.                 }  
     
132.                 else  
     
133.                     creat_list(pl_temp);  
     
134.                 pl_temp->symbol = c_temp;  
     
135.                 pl_temp->number = (double)0xcccccccccccccccc;  
     
136.             }  
     
137.         }  
     
138.         else  
     
139.         {  
     
140.             if (t_head == NULL)  
     
141.             {  
     
142.                 frist_time(t_head);  
     
143.                 pl_temp = t_head;  
     
144.             }  
     
145.             else  
     
146.                 creat_list(pl_temp);  
     
147.             pl_temp->number = atoi(str_temp);  
     
148.             pl_temp->symbol = 0;  
     
149.         }  
     
150.     }  
     
151.     return t_head;  
     
152. }  
     

复制代码

000

1. void print_list(const p_list head)      //打印链表  
   
2. {  
   
3.     p_list temp = head;  
   
4.     for (; temp != NULL; temp = temp->next)  
   
5.     {  
   
6.         if (temp->number == (double)0xcccccccccccccccc)  
   
7.             printf("%c ", temp->symbol);  
   
8.         else  
   
9.             printf("%f ", temp->number);  
   
10.     }  
    
11. }  
    
12. p_list m_bracket(p_list p_temp,p_list &temp, char *stuck_symbol, int i, bool(*p_function)(const char a, const char b))        
    
13.                         //遇到括号时调用的函数  
    
14. {  
    
15.     char *temp_stuck_symbol = stuck_symbol + i;                                                             //其中第一个参数对应中缀式节点，第二个对应后缀式节点  
    
16.     int t_i = 0;  
    
17.     for (p_temp = p_temp->next; p_temp->symbol != ')'; p_temp = p_temp->next)                                              //第三个是符号栈，第四个是地址偏移量  
    
18.     {  
    
19.         if (p_temp->symbol == '(')                                                                   //第五个是优先级判断函数，此函数需要用户按照需求自定义  
    
20.         {  
    
21.             p_temp = m_bracket(p_temp, temp, temp_stuck_symbol, t_i, p_function);                                           //递归调用括号中遇到括号时的情况  
    
22.             if (p_temp->symbol == ')')  
    
23.                 break;  
    
24.         }  
    
25.         if (p_temp->symbol == 0)  
    
26.         {  
    
27.             if (temp == NULL)  
    
28.                 frist_time(temp);  
    
29.             else  
    
30.                 creat_list(temp);  
    
31.             temp->number = p_temp->number;  
    
32.             temp->symbol = 0;  
    
33.             continue;  
    
34.         }  
    
35.         if (t_i == 0 || p_function(stuck_symbol[t_i - 1], p_temp->symbol))  
    
36.         {  
    
37.             temp_stuck_symbol[t_i] = p_temp->symbol;  
    
38.             ++t_i;  
    
39.         }  
    
40.         else  
    
41.         {  
    
42.             for (--t_i; t_i >= 0 && !p_function(temp_stuck_symbol[t_i], p_temp->symbol); --t_i)  
    
43.             {  
    
44.                 creat_list(temp);  
    
45.                 temp->symbol = temp_stuck_symbol[t_i];  
    
46.                 temp->number = (double)0xcccccccccccccccc;  
    
47.             }  
    
48.             ++t_i;  
    
49.             temp_stuck_symbol[t_i] = p_temp->symbol;  
    
50.             ++t_i;  
    
51.         }  
    
52.     }  
    
53.     for (--t_i; t_i >= 0; --t_i)  
    
54.     {  
    
55.         creat_list(temp);  
    
56.         temp->symbol = temp_stuck_symbol[t_i];  
    
57.         temp->number = (double)0xcccccccccccccccc;  
    
58.     }  
    
59.     p_temp = p_temp->next;  
    
60.     return p_temp;  
    
61. }  
    
62. p_list Excange(p_list head,bool (*p_function)(const char a, const char b))                                  //中缀转换后缀主函数，函数指针为优先级判断函数，此函数需要用户按照需求自定义  
    
63. {         
    
64.     p_list p_temp = head, t_head = NULL, temp;  
    
65.     temp = t_head;  
    
66.     char stuck_symbol[1024];  
    
67.     int i = 0;  
    
68.     for (; p_temp != NULL; p_temp = p_temp->next)  
    
69.     {  
    
70.         if (p_temp->symbol == '(')                                                                           //遇到括号时  
    
71.             if (temp == t_head)  
    
72.             {  
    
73.                 p_temp = m_bracket(p_temp, t_head, stuck_symbol, i, p_function);  
    
74.                 temp = t_head;  
    
75.                 for (; t_head->prev != NULL; t_head = t_head->prev);  
    
76.                 if(p_temp == NULL)  
    
77.                     break;  
    
78.                 if (p_temp->symbol == ')')                                                                   //当调用结束后的反括号处理（跳过对这个符号的处理）  
    
79.                     break;  
    
80.             }  
    
81.             else  
    
82.             {  
    
83.                 p_temp = m_bracket(p_temp, temp, stuck_symbol, i, p_function);  
    
84.                 if (p_temp == NULL)  
    
85.                     break;  
    
86.                 if (p_temp->symbol == ')')  
    
87.                     break;  
    
88.             }  
    
89.         if (p_temp->symbol == 0)  
    
90.         {  
    
91.             if (t_head == NULL)  
    
92.             {  
    
93.                 frist_time(t_head);  
    
94.                 temp = t_head;  
    
95.                 t_head->number = p_temp->number;  
    
96.                 t_head->symbol = 0;  
    
97.                 continue;  
    
98.             }  
    
99.             else  
    
100.                 creat_list(temp);  
     
101.             temp->number = p_temp->number;      
     
102.             temp->symbol = 0;  
     
103.             continue;  
     
104.         }  
     
105.         if (i == 0 || p_function(stuck_symbol[i-1], p_temp->symbol))  
     
106.         {  
     
107.             stuck_symbol[i] = p_temp->symbol;  
     
108.             ++i;  
     
109.         }  
     
110.         else  
     
111.         {  
     
112.             for (--i; i >=0&&!p_function(stuck_symbol[i], p_temp->symbol); --i)  
     
113.             {  
     
114.                 creat_list(temp);  
     
115.                 temp->symbol = stuck_symbol[i];  
     
116.                 temp->number = (double)0xcccccccccccccccc;  
     
117.             }  
     
118.             ++i;  
     
119.             stuck_symbol[i] = p_temp->symbol;  
     
120.             ++i;  
     
121.         }  
     
122.     }  
     
123.     for (--i; i >= 0; --i)                                                                                       //清空符号栈  
     
124.     {  
     
125.         creat_list(temp);  
     
126.         temp->symbol = stuck_symbol[i];  
     
127.         temp->number = (double)0xcccccccccccccccc;  
     
128.     }  
     
129.     BeEmpty(head);  
     
130.     return t_head;  
     
131. }  
     
132. int main(void)  
     
133. {  
     
134.     double sum;  
     
135.     p_list head;  
     
136.     head = scan_list();  
     
137.     head = Excange(head,priority);  
     
138.     print_list(head);  
     
139.     sum = calc(head);  
     
140.     printf("\nsum is : %f", sum);  
     
141.     return 0;  
     
142. }

复制代码

000

顺带把算法流程图贴上吧
：

000

这里再贴两个关于树的插入和完全删除的两个方法吧：

1. struct Tree
   
2. {
   
3.         struct Tree * left;
   
4.         struct Tree * right;
   
5.         int times;
   
6.         int numb;
   
7. };
   
8. 
   
9. typedef struct Tree * t_point;

复制代码

这里是插入

1. t_point Insert(int x, t_point node)
   
2. {
   
3.         if (node == NULL)
   
4.         {
   
5.                 node = (t_point)malloc(sizeof(struct Tree));
   
6.                 if (errno)
   
7.                         printf("%s", strerror(errno));
   
8.                 else
   
9.                 {
   
10.                         node->numb = x;
    
11.                         node->times = 1;
    
12.                         node->left = node->right = NULL;
    
13.                 }
    
14.         }
    
15.         else
    
16.                 if (x < node->numb)
    
17.                         node->left = Insert(x, node->left);
    
18.                 else
    
19.                         if (x > node->numb)
    
20.                                 node->right = Insert(x, node->right);
    
21.                         else
    
22.                                 if(x == node->numb)
    
23.                                         ++node->times;
    
24.         return node;
    
25. }

复制代码

这里是删除（非懒惰删除）

1. t_point Delete(int x, t_point node)                                               
   
2. {
   
3.         t_point temp;
   
4.         if (node == NULL)
   
5.                 printf("Not Find");
   
6.         else
   
7.                 if (x < node->numb)
   
8.                         node->left = Delete(x, node->left);
   
9.                 else
   
10.                         if (x > node->numb)
    
11.                                 node->right = Delete(x, node->right);
    
12.                         else
    
13.                                 if (node->left&&node->right)
    
14.                                 {
    
15.                                         temp = Find_Min(node->right);
    
16.                                         node->numb = temp->numb;
    
17.                                         node->times = temp->times;
    
18.                                         node->right = Delete(node->numb, node->right);
    
19.                                 }
    
20.                                 else
    
21.                                 {
    
22.                                         temp = node;
    
23.                                         if (node->left == NULL)
    
24.                                                 node = node->right;
    
25.                                         else
    
26.                                                 if (node->right == NULL)
    
27.                                                         node = node->left;
    
28.                                         free(temp);
    
29.                                 }
    
30.         return node;
    
31. }

复制代码

000

在删除中，当遇到删除元素既有做儿子又有右儿子时，需要找到又支中最小的哪一个节点代替即将删除的节点，所以会有Find_Min函数，以及后面对Delete函数的递归调用（对右支而言，删除最小节点的）。

000

再记录一个关于AVL树的构建&删除吧（清明这几天就在学这两个玩意）

1. struct AVL_Tree
   
2. {
   
3.         struct AVL_Tree *left;
   
4.         struct AVL_Tree *right;
   
5.         int numb;
   
6.         int times;
   
7.         int height;
   
8. };
   
9. typedef struct AVL_Tree * AT_Point;

复制代码

000

构建函数:

1. #define Max(x,y) ((x)>(y)? (x):(y))
   
2. int Height(AT_Point node)
   
3. {
   
4.         if (node == NULL)
   
5.                 return -1;
   
6.         else
   
7.                 return node->height;
   
8. }
   
9. AT_Point SingleLeft(AT_Point node)
   
10. {
    
11.         AT_Point temp = node->left;
    
12.         node->left = temp->right;
    
13.         temp->right = node;
    
14.         node->height = Max(Height(node->right), Height(node->left)) + 1;
    
15.         temp->height = Max(Height(temp->right), node->height) + 1;
    
16.         return temp;
    
17. }
    
18. AT_Point SingleRight(AT_Point node)
    
19. {
    
20.         AT_Point temp = node->right;
    
21.         node->right = temp->left;
    
22.         temp->left = node;
    
23.         node->height = Max(Height(node->right), Height(node->left)) + 1;
    
24.         temp->height = Max(Height(temp->left), node->height) + 1;
    
25.         return temp;
    
26. }
    
27. AT_Point DoubleLeft(AT_Point node)
    
28. {
    
29.         node->left = SingleRight(node->left);
    
30.         return SingleLeft(node);
    
31. }
    
32. AT_Point DoubleRight(AT_Point node)
    
33. {
    
34.         node->right = SingleLeft(node->right);
    
35.         return SingleRight(node);
    
36. }
    
37. AT_Point Insert(int x, AT_Point node)
    
38. {
    
39.         if (node == NULL)
    
40.         {
    
41.                 node = (AT_Point)malloc(sizeof(struct AVL_Tree));
    
42.                 if (errno)
    
43.                 {
    
44.                         char err[100];
    
45.                         strerror_s((&err)[100], errno);
    
46.                         printf("%s", err);
    
47.                 }
    
48.                 else
    
49.                 {
    
50.                         node->height = 0;
    
51.                         node->left = node->right = NULL;
    
52.                         node->numb = x;
    
53.                         node->times = 1;
    
54.                 }
    
55.         }
    
56.         else
    
57.                 if (x < node->numb)
    
58.                 {
    
59.                         node->left = Insert(x, node->left);
    
60.                         if (Height(node->left) - Height(node->right) == 2)
    
61.                                 if (x > node->right->numb)
    
62.                                         node = SingleLeft(node);
    
63.                                 else
    
64.                                         node = DoubleLeft(node);
    
65.                 }
    
66.                 else
    
67.                         if (x > node->numb)
    
68.                         {
    
69.                                 node->right = Insert(x, node->right);
    
70.                                 if (Height(node->left) - Height(node->right) == 2)
    
71.                                         if (x > node->right->numb)
    
72.                                                 node = SingleRight(node);
    
73.                                         else
    
74.                                                 node = DoubleRight(node);
    
75.                         }
    
76.                         else
    
77.                         {
    
78.                                 ++node->times;
    
79.                                 return node;
    
80.                         }
    
81.         node->height = Max(Height(node->left), Height(node->right)) + 1;
    
82.         return node;
    
83. }

复制代码

000

首先是AVL树的定义：个人理解为构建树时，每一个跟节点左右两支的深度差必须小于等于1（为了保证平衡）
所以在结构体里除了元素出现次数之外，还有一个关于每个节点左右深度的一个量。
之后是插入函数Insert
这个函数是建立在左（右）单（双）旋转，以及深度计算上的，基本都是递归调用，所以理解起来有点复杂，但是理解通了就会非常清晰
首先看单旋转（单旋转出现的时机就是一个节点的某一支深度比另一支的深度深到2时（总是为2，不可能更高），并且影响深度的那一个节点在左儿子的左边（或者右儿子的右边））
深度较高的那一节点看为k1（就分析右边的吧，左边的相反就好）
根结点看为k2好了，此时有
k2->right == k1
并且影响深度的那一个节点是k1的右儿子，此时要将想办法让k2->left总体深度加一，并且k1->right总体深度减一，那么就自然而然的想到将k1升为根结点，k2降为k1 的子节点
当k1升为根节点时k1->left就会降一，就会不成立，所以还要让k1->left深度不变
综上就有了保存k1->left的值，并且让k2成为k1->left（完成了k1->right深度-1,k2->left深度+1）此时原来的k1->left就应该成为k2->right（总是）应为跟具查找树的定义可知k2<(k1->left)<k1<(k1->right)
此时原来的k1->left的深度便保持了不变

000

此时我们分析双旋转，由上面的单旋转我们知道了一个节点的某一支深度比另一支的深度深到2时还有另外两个情况，就是：影响深度的那一个节点左儿子的右边（或是右儿子的左边）
我们拿右儿子的左边这种情况分析吧：
此时我们任然想到使用之前的想法，深度较高的那一节点看为k1，其父节点看为k2，然后使用但旋转让k2深度加一，k1深度减一，但是会发现，k1中，深度较高的是k1->left，如果进行单旋转，就会发现k1->left被交换到k2的右边，然而k2已经深度加以，所以此时k1->left的深度没有发生改变
那么我们想到，如果让k1和k1->left交换（k1->left暂时看为k3）就会有k1的深度加一，并且不论k3的是哪一支的深度较高，总是会有交换后的k1->right 成为深度较高的节点（因为AVL树的定义，左右两支深度差<=1），就转换为了第一种情况，最后只需要再执行一次单旋转即可