000山寨的笔记

000

上边的例程不完整，应为没有在转换时对深度值做修改，后期修改补上即可

000

好吧，这里最后再分析下节点深度的函数好了，上面的例程在旋转时没有对节点深度做修改，这里分析下这个函数，也就算是可以了吧
：递归调用Insert总有深度为零，但是+1，所以递归调用Insert 的次数越多，+1次数越多，所以深度就出来了

嬴政

000 发表于 2017-4-3 21:03
好吧，这里最后再分析下节点深度的函数好了，上面的例程在旋转时没有对节点深度做修改，这里分析下这个函数 ...

不错，不错，学习算法了

000

再贴一个AVL树双旋转的非递归写法吧：

1. AT_Point DoubleLeft1(AT_Point node)
   
2. {
   
3.         AT_Point temp1 = node->left->right;
   
4.         AT_Point temp2 = node->left;
   
5.         AT_Point temp3 = temp1->left;
   
6.         AT_Point temp4 = temp1->right;
   
7.         temp1->left = temp2;
   
8.         temp1->right = node;
   
9.         node->left = temp3;
   
10.         temp2->right = temp4;
    
11.         temp1->height -= 1;
    
12.         node->height += 1;
    
13.         return temp1;
    
14. }
    
15. AT_Point DoubleRight1(AT_Point node)
    
16. {
    
17.         AT_Point temp1 = node->right->left;
    
18.         AT_Point temp2 = node->right;
    
19.         AT_Point temp3 = temp1->right;
    
20.         AT_Point temp4 = temp1->left;
    
21.         temp1->left = node;
    
22.         temp1->right = temp2;
    
23.         node->right = temp4;
    
24.         temp2->left = temp3;
    
25.         temp1->height -= 1;
    
26.         node->height += 1;
    
27.         return temp1;
    
28. }

复制代码

主要思想就是把深度教高的那个节点提前为根，之后其左右儿子的地址由上面两个父节点和祖父节点分摊开来，补空位就好

000

贴一个二叉堆的基本吧实现，有注释的

1. #include <stdio.h>
   
2. #include <tchar.h>
   
3. #include <stdlib.h>
   
4. #include <errno.h>
   
5. #include <string.h>
   
6. struct Heap
   
7. {
   
8.         int capacity;
   
9.         int size;
   
10.         int *c;
    
11. };
    
12. typedef struct Heap * h_point;
    
13. //-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    
14. // binary heap
    
15. // Left 2i
    
16. // Right 2i+1
    
17. // Father i/2
    
18. //-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    
19. h_point
    
20. Initialize(int MaxSize)
    
21. {
    
22.         h_point head = (h_point)malloc(sizeof(struct Heap));
    
23.         if (errno)
    
24.                 printf("%s", strerror(errno));
    
25.         head->c = (int *)malloc(sizeof(int)*(MaxSize + 1));
    
26.         if (errno)
    
27.                 printf("%s", strerror(errno));
    
28.         head->capacity = MaxSize;
    
29.         head->size = 0;
    
30.         head->c[0] = 0xcccccccc;
    
31.         return head;
    
32. }
    
33. bool
    
34. IsFull(h_point head)
    
35. {
    
36.         return head->size == head->capacity ? 1: 0;
    
37. }
    
38. int
    
39. IsEmpty(h_point head)
    
40. {
    
41.         return head->size == 0 ? head->c[0] : 0;
    
42. }
    
43. void
    
44. Insert(int x, h_point head)
    
45. {
    
46.         int i;
    
47.         if (IsFull(head))
    
48.                 printf("FULL");
    
49.         for (i = ++head->size; head->c[i/2] > x; i /= 2)
    
50.                 head->c[i] = head->c[i / 2];
    
51.         head->c[i] = x;
    
52. }
    
53. int DeleteMin(h_point head)
    
54. {
    
55.         int i, child;
    
56.         int Min, Last;
    
57.         if (IsEmpty(head))
    
58.                 printf("Empty");
    
59.         Min = head->c[1];
    
60.         Last = head->c[head->size--];                                                //删除节点户籍
    
61.         for (i = 1; i * 2 <= head->size; i = child)                        // i 为根节点
    
62.         {
    
63.                 child = i * 2;                                                                                                        //以i为根的左节点
    
64.                 if (child != head->size && head->c[child + 1] < head->c[child]) //左节点小于右节点，此时右节点前移到删除的根节点处完成删除
    
65.                         ++child;
    
66.                 if (Last > head->c[child])
    
67.                         head->c[i] = head->c[child];
    
68.                 else
    
69.                         break;
    
70.         }
    
71.         head->c[child] = Last;
    
72.         return Min;
    
73. }
    
74. int _tmain(int argc,_TCHAR *argv[])
    
75. {
    
76.         FILE *fp;
    
77.         fp = fopen("in.txt", "r");
    
78.         h_point head = Initialize(10);
    
79.         for (int i = 0; i < 10; ++i)
    
80.         {
    
81.                 int j;
    
82.                 fscanf(fp, "%d", &j);
    
83.                 Insert(j, head);
    
84.         }
    
85.         for (int i = 1; i <= 10; ++i)
    
86.                 printf("%d   ", head->c[i]);
    
87.         int i = DeleteMin(head);
    
88.         printf("\n Min is　：　%d\n", i);
    
89.         for (int i = 1; i <= head->size; ++i)
    
90.                 printf("%d   ", head->c[i]);
    
91.     return 0;
    
92. }

复制代码

000

对这个做个补充吧（应为在删除的时候我没有做到这一点），发现没有，在删除的时候for循环是（更具上面的注释)以遍历到做节点为结束，那么如果一个树为偶数节点，那么就可能会被漏掉，所以还有一种方法，就是建立一个不会达到的大数当作结尾，以那个位标志

000

改进之后添加了:

1. #include<limits.h>

复制代码

Initialize中:

1. head->c = (int *)malloc(sizeof(int)*(MaxSize + 2));
   
2. head->c[MaxSize + 1] = INT_MAX;

复制代码

Delete中：

1. int DeleteMin(h_point head)
   
2. {
   
3.         int i, child;
   
4.         int Min, Last;
   
5.         if (IsEmpty(head))
   
6.                 printf("Empty");
   
7.         Min = head->c[1];
   
8.         Last = head->c[head->size--];                                                //删除节点户籍
   
9.         for (i = 1; i * 2 <= head->size; i = child)                        // i 为根节点
   
10.         {
    
11.                 child = i * 2;                                                                                                        //以i为根的左节点
    
12.                 if (head->c[child + 1] < head->c[child]) //左节点小于右节点，此时右节点前移到删除的根节点处完成删除不检测右儿子
    
13.                         ++child;
    
14.                 if (Last > head->c[child])
    
15.                         head->c[i] = head->c[child];
    
16.                 else
    
17.                         break;
    
18.         }
    
19.         head->c[child] = Last;
    
20.         return Min;
    
21. }

复制代码

000

最近要开始接触windows api了，现在正在从C转型到C++
就目前来说我接触到的新东西（以及之前学习时遗漏的）有以下：
1:const
1）例子：

1. #include <iostream>
   
2. int main()
   
3. {
   
4.         const int a = 10;
   
5.         int *b = (int *)&a;
   
6.         *b = 20;
   
7.         std::cout << a << " " << *b << std::endl;
   
8.         return 0;
   
9. }

复制代码

输出结果为:10   20
由此可知，在C++中的const是类似于#define一样在编译阶段便对a做了替换（只是类似，并不完全一样，否则取址无法进行）
2）例子：

1. #include <iostream>
   
2. void plus(const int &a)
   
3. {
   
4.         std::cout << a + 10 << std::endl;
   
5. }
   
6. int main()
   
7. {
   
8.         int a = 10;
   
9.         plus(a + 10);
   
10.         return 0;
    
11. }

复制代码

这里的&本来是不可以用于零时数据，零时数据可能只存在于寄存器内，不可寻址，但是使用了const，编译器编译器会为临时数据创建一个新的、无名的临时变量（妥协机制），同时也可以类似于上面的强制转换修改值，虽然没有任何意义。。但是是不会对零食数据的值造成修改的。
上课了，晚点来继续，学的东西很多，要来这里说一遍缕一缕才扎实

000

现在在上一个无聊到炸的课，继续吧
3）：对于对象而言const只可以访问到const类型成员。
4）：例子：

1. #include <iostream>
   
2. int main()
   
3. {
   
4.         int a = 4;
   
5.         float &b = *(float*)&a;//以float解读a
   
6.         std::cout<<b<<std::endl;
   
7.         const float &c = a;
   
8.         std::cout<<c<<std::endl;
   
9.         float *d = (float *)&c;
   
10.         *d = 0;
    
11.         std::cout<<a<<std::endl;
    
12.         std::cout<<c<<std::endl;
    
13.         return 0;
    
14. }

复制代码

输出结果： 5.06519 e-45    4    4   0
由此我们知道了对不同数据类型进行引用，并且想让其符合预期（自动转化）那么要加上const，此时情况同2）

000

现在来说说类吧（才开始接触到一小部分）
2：类
1）：class，就是一个封装能力更强的struct，在C++中，struct也可以和类一样，里面成员也可以是函数（和C的区别）但是在struct里面的成员全部都是public的（和class的区别之一），同时也可以用构造函数来进行初始化
例子：

1. #include <iostream>
   
2. using namespace std;
   
3. struct MyStruct
   
4. {
   
5.         MyStruct(int, char);
   
6.         ~MyStruct();
   
7.         friend void back_num(struct MyStruct); // 没有意义，毕竟都是public的
   
8.         int m_a;
   
9.         char m_b;
   
10. };
    
11. void back_num(struct MyStruct a)
    
12. {
    
13.         a.m_a = 2, a.m_b = 'b';
    
14. }
    
15. MyStruct::MyStruct(int a, char b) :m_a(a), m_b(b)
    
16. {
    
17.         cout << this->m_a << this->m_b << endl; //没有使用&     函数结束后自动调用析构函数出栈
    
18. }
    
19. MyStruct::~MyStruct()
    
20. {
    
21.         cout << this->m_a << this->m_b << endl;
    
22. }
    
23. int main()
    
24. {
    
25.         struct MyStruct temp(1, 'a');
    
26.         back_num(temp);
    
27.         return 0;
    
28. }

复制代码

输出结果：
1a
2b
1a
2）：构造函数&析构函数
例子：

1. #include <iostream>
   
2. using namespace std;
   
3. typedef int * i_point;
   
4. class MyClass
   
5. {
   
6. public:
   
7.         MyClass(int, char);
   
8.         ~MyClass();
   
9.         friend int *test(MyClass);    //重载要再次声明
   
10.         friend int *test(MyClass *&);
    
11.         void Delede(MyClass);
    
12. private:
    
13.         int m_a;
    
14.         char m_b;
    
15.         int *m_c;
    
16. };
    
17. MyClass::MyClass(int a, char b) :m_a(a), m_b(b)   //对像成员初始化
    
18. {
    
19.         this->m_c = new int[this->m_a];
    
20. }
    
21. MyClass::~MyClass()
    
22. {
    
23.         cout << "Used" << endl;
    
24. }
    
25. void MyClass::Delede(MyClass t)
    
26. {
    
27.         delete t.m_c;
    
28. }
    
29. int *test(MyClass a)
    
30. {
    
31.         cout << &a << endl;
    
32.         a.m_c[1] = 2;
    
33.         return a.m_c;
    
34. }
    
35. int *test(MyClass *&a)
    
36. {
    
37.         cout << a << endl;
    
38.         a->m_c[1] = 3;
    
39.         return a->m_c;
    
40. }
    
41. int main()
    
42. {
    
43.         i_point temp1, temp2;
    
44.         MyClass t(5, 'a');
    
45.         MyClass *t1 = new MyClass(5, 'b');
    
46.         cout << hex << showbase << &t << endl;
    
47.         temp1 = test(t);
    
48.         cout << t1 << endl;
    
49.         temp2 = test(t1);
    
50.         int *a = new int[5];
    
51.         a[1] = 1;
    
52.         delete a;
    
53.         delete t1;
    
54.         cout << a[1] << '\t' <<dec << temp1[1]<< '\t' << temp2[1] << endl;
    
55.         t.Delede(t);
    
56.         cout << hex << showbase << temp1[1] << endl;
    
57.         return 0;
    
58. }

复制代码

这个例程中出现了一个析构函数的一个点，在每一次函数出栈（只要定义了零时对象时）在函数结束时会调用析构函数进行出栈，目的是为了删除零时对象，但是，如果成员变量内的指针指向了一个由程序员分配的空间时，析构函数内应添加delete this->（成员变量的指针），否则只会将类中的指针赋值为0xdddddddd(Debug模式下)