leeyupeng

leeyupeng@126.com

0%

发表于 更新于 分类于 ， 阅读次数： Valine：

发表于 更新于 分类于 ， ， 阅读次数： Valine：

自顶向下建堆

从根结点开始，然后一个一个的把结点插入堆中。当把一个新的结点插入堆中时，需要对结点进行调整，以保证插入结点后的堆依然是大根堆。
时间复杂度为$O(n\log_{2}{n})$

自底向上建堆

初始化建堆只需要对二叉树的非叶子节点调用Adjust()函数，由下至上，由右至左选取非叶子节点来调用Adjust()函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。

如果仅从下面展示的代码上直观观察，会得出构造二叉堆的时间复杂度为O(n)的结果，这个结果是错的，虽然该算法外层套一个n次循环，而内层套一个分治策略下的复杂度的循环，该思考方法犯了一个原则性错误，那就是构建二叉堆是自下而上的构建，每一层的最大纵深总是小于等于树的深度的，因此，该问题是叠加问题，而非递归问题。

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。

n个元素的完全二叉树，树高h为$log_{2}{(n+1)}$;

最下层非叶结点所需时间: $T(h-1) = 2^{(h-1)} * 1$;

第i层元素所需时间为$T(i) = 2^{i} * (h-i)$;

展开

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

发表于 更新于 分类于 ， 阅读次数： Valine：

寄存器

  • 1 ESP(Extended Stack Pointer): 堆栈指针，寄存器存放当前线程的栈顶指针；　　i.e: move ebp, esp — 用ebp保存当前栈指针；
  • 2 EBP(Extended Base Pointer): 基址指针，寄存器存放当前线程的栈底指针；　　i.e: push ebp — 将基址指针压入栈；
  • 3 EIP：寄存器存放下一个CPU指令存放的内存地址，当CPU执行完成当前的指令后，从EIP寄存器中读取下一条指令的内存地址，然后继续执行；
  • 4 EAX: 累加器(Accumulator)，加法乘法指令的缺省寄存器；
  • 5 EBX: 基地址(Base)寄存器，在内存寻址时存放基地址；
  • 6 ECX：计数器(Counter)，是重复(REP)前缀指令和LOOP指令的内定计数器；
  • 7 EDX：存放整数除法产生的余数；
  • 8 ESI/EDI: 源/目标索引寄存器(Source/Destination Index)， 在很多字符串操作指令中，DS：ESI指向源串，而ES：EDI指向目标串。
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

宏

编译器参数和条件编译

在头文件中经常见到下面的代码，以防止头文件的重复包含

1
2
3
4
#ifndef  _XXX_H
#define  _XXX_H
//...
#endif

编译宏

1
2
3
4
5
6
7
__LINE__  //行
__FILE__  //文件名
__DATE__  //日期  
__TIME__  //
__STDC__  //

__func__

无参宏

1
#define PI 3.1415926
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

.h叫做头文件，它是不能被编译的。“#include”叫做编译预处理指令，可以简单理解成，在1.cpp中的#include”1.h”指令把1.h中的代码在编译前添加到了1.cpp的头部。每个.cpp文件会被编译，生成一个.obj文件，然后所有的.obj文件链接起来你的可执行程序就算生成了。
发现了没有，你要在.h文件中严格区分声明语句和定义语句。好的习惯是，头文件中应只处理常量、变量、函数以及类等等等等的声明，变量的定义和函数的实现等等等等都应该在源文件.cpp中进行。

.h文件中能包含：

类成员数据的声明，但不能赋值

类静态数据成员的定义和赋值，但不建议，只是个声明就好。

类的成员函数的声明

非类成员函数的声明

常数的定义：如：constint a=5;

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

预处理器

编译器

汇编程序

目标程序

链接器

可执行程序

链接之前，所有的源文件都是单独编译的

C++ 语言支持”分别编译”（separatecompilation）。也就是说，一个程序所有的内容，可以分成不同的部分分别放在不同的 .cpp 文件里。.cpp 文件里的东西都是相对独立的，在编译（compile）时不需要与其他文件互通，只需要在编译成目标文件后再与其他的目标文件做一次链接（link）就行了。比如，在文件 a.cpp 中定义了一个全局函数 “void a(){}”，而在文件 b.cpp 中需要调用这个函数。即使这样，文件 a.cpp 和文件 b.cpp 并不需要相互知道对方的存在，而是可以分别地对它们进行编译，编译成目标文件之后再链接，整个程序就可以运行了。
这是怎么实现的呢？从写程序的角度来讲，很简单。在文件 b.cpp 中，在调用 “void a()” 函数之前，先声明一下这个函数 “voida();”，就可以了。这是因为编译器在编译 b.cpp 的时候会生成一个符号表（symbol table），像 “void a()” 这样的看不到定义的符号，就会被存放在这个表中。再进行链接的时候，编译器就会在别的目标文件中去寻找这个符号的定义。一旦找到了，程序也就可以顺利地生成了。

注意这里提到了两个概念，一个是”定义”，一个是”声明”。简单地说，”定义”就是把一个符号完完整整地描述出来：它是变量还是函数，返回什么类型，需要什么参数等等。而”声明”则只是声明这个符号的存在，即告诉编译器，这个符号是在其他文件中定义的，我这里先用着，你链接的时候再到别的地方去找找看它到底是什么吧。定义的时候要按 C++ 语法完整地定义一个符号（变量或者函数），而声明的时候就只需要写出这个符号的原型了。需要注意的是，一个符号，在整个程序中可以被声明多次，但却要且仅要被定义一次。试想，如果一个符号出现了两种不同的定义，编译器该听谁的？

阅读全文 »