二叉树是一种非常重要的数据结构，今天我们来讲讲它。
滚粗。。。老子不是遇到很好的知识点，我才懒得理你呢。。。
以下性质暗含root node 为第一层
证明：数学归纳法。
i=1时，显然2^(1-1) = 2^0 = 1个节点是对的
现在假设对所有的j，1<=j<i,第j层上至多有2^(j-1)个节点，那么可以证明j=i时命题 也成立。
由归纳假设，第i-1层上至多有2^(i-2)个节点，由于二叉树的每个度最多为2，故第i层 上节点数为第i-1层上的2倍，即2*2^(i-2).
证明： 根据上面的1，每层最多节点数之和是一个等比数列，故证之。
证明：设度为1的节点为n1，则二叉树T中节点总数n等于n=n1+n2+n0. 如二叉树T分枝数为B，因为二叉树中除了根节点没有入度，其余节点都有一个入度，所 以n=B+1.又因为这些分支由度为1或者2的节点射出的，则B=n1+2n2，所以有 1+n1+2n2=n1+n2+n0 ==> n0=n2+1
如果使用数组代表二叉树的话，那么数组里的元素依次就是从根节点水平方向读取来的 (也就是依照层进行读取的)
如果根节点在数组的下标是从1开始,那么就有如下性质：
PARENT(i) return floor(i/2)
LEFT(i) return 2i
RIGHT(i) return 2i + 1
如果根节点从数组下标为0开始，那么有如下性质：
PARENT(i) return floor[(i-1)/2]
LEFT(i) return 2*i+1
RIGHT(i) return 2i + 2
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode *newNode(int data) {
struct TreeNode *p = (struct TreeNode *)malloc(sizeof(struct TreeNode));
p->val = data;
p->left = p->right = NULL;
}
struct TreeNode *createBinaryTree(struct TreeNode *root,int *array, int pos, int nums) {
if ( pos < nums) {
struct TreeNode *p = newNode(array[pos]);
root = p;
// left
root->left = createBinaryTree(root->left, array, 2*pos + 1, nums);
root->right = createBinaryTree(root->right, array, 2*pos +2, nums);
}
return root;
}
void show(struct TreeNode *p) {
if(p == NULL)
return ;
else {
show(p->left);
if(p->val == -1)
printf("#\t");
else
printf("%d\t", p->val);
show(p->right);
}
}
int main() {
//int a[] = {1,4,5,1,9,6,5};
int a [] = {1,2,3,4,-1,-1,7,-1,9,-1,-1,-1,-1,4};
int n = sizeof(a)/sizeof(a[0]);
struct TreeNode *root = createBinaryTree(root,a, 0,n);
show(root);
printf("\n");
}
上面的代码就是按层次遍历依次读进二叉树，-1代表空节点。打印的时候是先打印左孩子，再是根节点，最后是右节点。
下面可以看做是有关树的API操作。
typedef struct Node{
struct Node* left;
struct Node* right;
int data;
}Node;
Node* newNode(int data)
{
Node* node=(Node*)malloc(sizeof(Node));
node->left=node->right=NULL;
node->data=data;
return node;
}
/* 将root == NULL的返回值置为-1或者0，结果不一样*/
int getHeight(Node* root) {
if(root == NULL)
return -1;
/* 返回为0， 结果是从根节点到叶子节点的节点数，
* 返回为-1， 是经历的路径长度 */
int left_height = getHeight(root->left);
int right_height = getHeight(root->right);
return (left_height > right_height ? left_height : right_height ) + 1 ;
}
/* The number of node*/
int node_num_tree(Node* root)
{
if(root == NULL)
return 0;
/* 这里的返回 0 还是有区别的 */
return 1 + node_num_tree(root->left) + node_num_tree(root->right);
}
/* the numbers of leaves */
int leaf_num_tree(Node* root)
{
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)
return 1;
return leaf_num_tree(root->left) + leaf_num_tree(root->right);
}
除了可以在配置文件外指定已发送邮箱存储的文件，如果不这样，你第一次使用mutt 的时候，会提示你自动创建sent邮箱。
当你再次键入neomutt命令时，进入的是收件箱的UI.怎么才能找到发件箱呢？
方法；type c then display Open mailbox('?' for list mailbox).So you can type sent.If you want to return
to mailbox(received mail box),you can type the mailbox of dir,in my example it is /var/mail/me
the article.
The method: first you must be enable configure option duplicate_threads = yes.you can type :set ?duplicate_threads to ensure the results.
Then you can type o to resort all mails in certainly pattern.For exampled,which will be sort mail as date model.
As last you say T tag pattern,put in ~= as the pattern.Duplicate mail are now tagged.The mail tagged will show start with a *.To delete them,either type just dor type ; then hit d.
You can add configure option in .muttrc to delete duplicate mail automatically.
订阅了lkml,可是经常有很多的邮件看不了而删了。现在，强大的命令来了，请接招:
首先，使用命令
mutt
进入，接着按__c__, 选择邮箱，这里我是自己用的是IMAP，这个协议把你的mutt当作 了终端。你在邮箱服务器上有几个文件夹或者标签，在mutt上就会有几个信箱。假如 你没有使用mutt，那么可以忽略这一步。
接着，在当前的邮箱下，键入：shift D
shift d
它会提示
Delete messages matching:
汉语就是
删除符合此样式的信件：
接着使用:
~s .*
回车，所有的邮件被标记上了D，这就是你单封删除邮件的作用。或者，还可以使用
~A
也可以达到以上相同的效果
这个功能更是geek,首先新建一个.mailcap的文件在主目录下：
更新： mutt只是一个管理邮箱的软件，并不会显示很复杂的邮件内容， 比如，网页类型的及非ascii编码类型的。如果想使用以上效果，那么就需要 其他软件配合了。
我首先使用的lynx文本网页浏览器，有一点我是开始没有理会 的，无法显示中文的邮件内容，lynx的配置在.mailcap的配置如下：
text/html; lynx -dump -width=78 -nolist %s | sed 's/^ //';
sopiousoutput; needsterminal;nametemplate=%s.html
这样mutt就会将mail中html格式的信息转化为PLAIN/TEXT格式，方便阅读。
mutt对于英语的支持那是相当不错，可是在浏览由中文邮箱发过来的邮件 时便会遇到可恶的乱码问题，如今，你可以使用w3m这个对中文支持好的。
将上面.mailcap文件的注释掉，使用下面的语句：
text/html; w3m -dump -ppc 9 -I %{charset} -T text/html %s|uniq; copiousoutput
这样子你就可以看见你亲切的汉字邮件了。
在.muttrc内新建命令绑定
# 设置键绑定 ,为了使用urlview.
macro pager \cb <pipe-entry>'urlview'<enter> 'Follow links with urlview'
前提是你要安装urlview这个软件。
然后使用命令ctrl-b就可以打开链接了
</del>
现在使用urlscan命令，同样，在.muttrc配置文件中写入man手册的语句。
现在，这几大发行版本已经把NeoMutt作为默认的版本了，但是使用源码安装的时候会遇上各种各样的包依赖，这时候，你要熟悉你的发行版的搜索软件的命令，以debian为例，那就是这样：
sudo apt-cache search xx
将源代码包下载下来后，使用如下的编译选项：
这个软件首先安装字符库或者图形界面的需要，推荐使用slang。当完成以后，使用./configure.autosetup –help,因为下面的命令已经不适用了。
./configure --with-slang=/usr/local/src/slang-2.2.4
--ssl --disable-doc --debug
接着使用
make
make install
简单记录LWP的应用。
$document = get(“URL”); 这个函数没有返回码。
这个函数就是将访问到的URL内容保存下来。 两个参数哈 在这里面有两个状态值is_success()和is_error()判断上面的正确与否；
#!/usr/bin/perl -w
use strict;
use LWP::Simple;
my $url = 'http://www.baidu.com';
my $file = '/tmp/baidu.html';
my $status = getstore($url,$file);
die "Error $status on $url" unless is_success($status);
open(IN,"<$file") || die "Can't open $file: $!";
while(<IN>){
if (m/百度/){
print "hello,baidu,$url";
last;
}
}
close(IN);
这个函数抓取接着打印，后面的参数是URL；
perl -MLWP::Simple -e "getprint('http://cpan.org/RECENT') || die" | grep Apache
url很重要，这样子你就可以了解相关软件的perl模块的最新情况。
#!/usr/bin/perl -w
use strict;
use LWP;
my $url = 'http://www.baidu.com/';
my $browser = LWP::UserAgent->new();
my $response = $browser->get($url);
print $response->header("Server"), "\n";
这段代码很有用，它可以让你知道你所测的主机的服务器使用的什么服务器。 最关键的是面向对象的思想在里面
linux下c或者c++编程始终离不开动态动态库”*.so”,具体它是怎么产生的、如何使用， 现在就简单介绍一下。
这里用一个简单的例子，比如有三个.c文件so_a.c、so_b.c、so_c.c;一个头文件so_he ad.h,我们将他们连接编译成一个动态库: libso.so. 文件的内容分别如下：
so_head.h:
#include<stdio.h>
void print_a();
void print_b();
void print_c();
so_a.c:
#include "so_head.h"
void print_a()
{
printf("This is print_a\n");
}
so_b.c:
#include "so_head.h"
void print_b()
{
printf("This is print_b\n");
}
这里省略so_c.c的源文件。 将这几个文件编译成一个动态库:libso.so 下面是Makefile:
SRCS = $(wildcard *.c)
OBJS = libso.so
$(OBJS):
gcc $(SRCS) -fPIC -shared -o $(OBJS)
:-shared
这里的-shared是指定生成的动态链接库，(让链接器生成的T类型的导出符号表，有 时候也生成弱连接w类型的导出符)。不用该标志外部程序无法连接。(为什么呢)
:-fPIC
表示编译为位置独立的代码，不用此选项的编译后的代码是位置相关的，这样在动态载 入时通过代码拷贝的方式来满足不同进程的需要，而不能真正达到代码共享的目的
所谓的连接就是将你所编译成的动态库连接你的可执行文件。 上面，我们已经生成了libso.so,那么我们需要编写一个文件调用里面的函数。
/* so_test.c */
#include "so_test.h"
int main(){
print_a();
print_b();
}
将上面的Makefile改写成:
SRCS = so_a.c \
so_b.c \
so_c.c \
so_head.h
OBJS = libso.so
PROC = so_test.c
EXE = test
$(EXE): $(OBJS)
gcc $(PROC) -L. -lso -o $(EXE)
$(OBJS):
gcc $(SRCS) -fPIC -shared -o $(OBJS)
-L.:
表示要连接到库所在的当前目录。
-lso:
就是查找动态连接库时隐含的命名规则，即在给出的名字前面加上lib，后面加上库的 名称。上面的默认的就是libso.so 这个时候，你使用ldd命令查看一下可执行文件test,里面就包含着libso.so呢。
以上步骤完全正确，但有时程序无法执行，也就是找不到so动态库，这时你就要通过 修改LD_LIBRARY_PATH的值来确定了。
LD_LIBRARY_PATH=.
即可，当然，还有其他的修改方法
常见的有三种：
T类：是在库中定义的函数，用T表示； U类：在库中被调用，但并没用在库中定义(表名需要其他库的支持)； W类： 所谓的“弱态”符号，虽然在库中被定义，但是可能被其他库中的同名符号覆盖；
所以，你想知道某个动态库中是否引用了printf(), 可以使用下面的命令：
nm libxx.so grep printf
将可执行文件内的内容读出来 比如： riscv 的readelf -h 如下：
readelf -h Hello (riscv bin)
ELF 头：
Magic： 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
类别: ELF64
数据: 2 补码，小端序 (little endian)
Version: 1 (current)
OS/ABI: UNIX - System V
ABI 版本: 0
类型: EXEC (可执行文件)
系统架构: RISC-V
版本: 0x1
入口点地址： 0x278be
程序头起点： 64 (bytes into file)
Start of section headers: 609704 (bytes into file)
标志： 0x5, RVC, double-float ABI
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 9
Size of section headers: 64 (bytes)
Number of section headers: 19
Section header string table index: 17
上面是riscv的elf头文件. x86_64的elf文件源代码: cat elf.c:
int main(){
printf("Hello Wrold\n");
}
下面是x86_64 的elf文件展出:
readelf -h elf
ELF 头：
Magic： 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
类别: ELF64
数据: 2 补码，小端序 (little endian)
版本: 1 (current)
OS/ABI: UNIX - System V
ABI 版本: 0
类型: DYN (共享目标文件)
系统架构: Advanced Micro Devices X86-64
版本: 0x1
入口点地址： 0x530
程序头起点： 64 (bytes into file)
Start of section headers: 8696 (bytes into file)
标志： 0x0
本头的大小： 64 (字节)
程序头大小： 56 (字节)
Number of program headers: 9
节头大小： 64 (字节)
节头数量： 34
字符串表索引节头： 33
ELF Magic tag表明这是一个elf文件，如果没有这16个字节，则就不是elf文件。
根据上一个工具readelf读出相应地址的内容 ?
反汇编代码
请先参考这篇文章 ELF(Executable and Linking Format)是一种对象文件格式,从名字上我们也能窥探出 他的作用来。这里主要三种类型的。
1 可重定位(relocalable)
2 可执行文件(Exectuable)
3 共享目标文件(shared object file)
gcc生成的object文件在linking和Execution的角度来看是不一样的。 先说在Linking的角度：
linking view _________________ | ELF Header | |----------------| |Program Header | | Table Optional | |----------------| | Section 1 | |----------------| | ... | |----------------| | Section n | |----------------| |Section Header | | Table | |----------------|
还是在这里分开吧
Executeable View |----------------| | ELF Header | |----------------| | Program Header | | Table | |----------------| | | | segment 1 | |----------------| | | | segment 2 | |----------------| | ... | |----------------| | section Header | | Table Optional | |________________|
其实上面的图示忽略了一点，即segment是由多个Section组成的。
在这两种的观点来看，都是包含着指令、数据、符号表、重定位等信息。 program header table 告诉系统如何创造一个进程镜像 .在链接阶段必须有一个 section header table.
as输出的目标文件至少有三个section，他们是text,data,bss段。你如果不写出.text 或者.data段，但是目标文件依然会有他们，只不过是空的。
update: as 汇编器连接的.S文件生成的是.o文件，这是一个重定位文件 然后才是ld的任务生成可执行文件,当生成了可执行文件， 以静态连接为例，作为ld的输入文件，可重定位文件x.o的包含了好几个sections:指令 、被初始化的全局变量、未初始化的变量。
./p
会激活装载器(loader)，它的作用是将可执行文件中的数据和代码复制到内存中去。 然后开始执行程序
Address 0 ---->|--------------|
| .text |
|______________|
| .data |
|______________|
| .bss |
|______________|
#