请选择 进入手机版 | 继续访问电脑版

C++编程

 找回密码
 立即注册

QQ登录

只需一步,快速开始

楼主: 000

000山寨的笔记

[复制链接]

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-3 20:58:31 | 显示全部楼层
上边的例程不完整,应为没有在转换时对深度值做修改,后期修改补上即可
回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-3 21:03:58 | 显示全部楼层
好吧,这里最后再分析下节点深度的函数好了,上面的例程在旋转时没有对节点深度做修改,这里分析下这个函数,也就算是可以了吧
:递归调用Insert总有深度为零,但是+1,所以递归调用Insert 的次数越多,+1次数越多,所以深度就出来了
回复 支持 反对

使用道具 举报

8

主题

31

帖子

323

积分

版主

Rank: 7Rank: 7Rank: 7

积分
323
QQ
发表于 2017-4-4 13:31:13 | 显示全部楼层
000 发表于 2017-4-3 21:03
好吧,这里最后再分析下节点深度的函数好了,上面的例程在旋转时没有对节点深度做修改,这里分析下这个函数 ...

不错,不错,学习算法了
VC纵横、磐实编程网
回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-4 14:18:34 | 显示全部楼层
本帖最后由 000 于 2017-4-4 14:21 编辑

再贴一个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. }
复制代码

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

回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-6 20:25:09 | 显示全部楼层
本帖最后由 000 于 2017-4-6 20:26 编辑

贴一个二叉堆的基本吧实现,有注释的
  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. }
复制代码


回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-6 20:31:05 | 显示全部楼层
对这个做个补充吧(应为在删除的时候我没有做到这一点),发现没有,在删除的时候for循环是(更具上面的注释)以遍历到做节点为结束,那么如果一个树为偶数节点,那么就可能会被漏掉,所以还有一种方法,就是建立一个不会达到的大数当作结尾,以那个位标志
回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-6 21:27:07 | 显示全部楼层
本帖最后由 000 于 2017-4-7 16:27 编辑

改进之后添加了:
  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. }
复制代码

回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-10 16:13:59 | 显示全部楼层
最近要开始接触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,编译器编译器会为临时数据创建一个新的、无名的临时变量(妥协机制),同时也可以类似于上面的强制转换修改值,虽然没有任何意义。。但是是不会对零食数据的值造成修改的。
上课了,晚点来继续,学的东西很多,要来这里说一遍缕一缕才扎实
回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-10 17:21:42 | 显示全部楼层
现在在上一个无聊到炸的课,继续吧
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)
回复 支持 反对

使用道具 举报

6

主题

62

帖子

206

积分

初软

Rank: 3Rank: 3

积分
206
 楼主| 发表于 2017-4-10 21:06:53 | 显示全部楼层
现在来说说类吧(才开始接触到一小部分)
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模式下)
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|C++编程  

GMT+8, 2019-7-22 20:48 , Processed in 0.093750 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表