大空新一-CSDN博客

代码内容来自《大话数据结构》，程杰著。原书中没有RightBalance函数实现，本处按照LeftBalance实现。#include #include #define LH +1 //左高#define EH 0 //相等#define RH -1 //右高typedef struct BitNode { int data;//结点数据 int bf;//结点平衡

2015-04-22 17:27:31 583

转载 KMP查找字串算法

代码内容来自《大话数据结构》，程杰著。针对书中源代码进行了修改，原书中字符串数组[0]存储为字符串长度，本代码处未使用该空间，字符串从[0]处开始存储。#include #include void get_next(char *T, int *next) { int i,j, len = strlen(T); i = 0; j = -1; next[0] = -1; whil

2015-04-21 11:15:38 581

原创 Linux系统ELF文件二进制格式分析(四)

一、重定位项重定位是将ELF文件中未定义的符号关联到有效位置的过程，特别是目标文件中这一项尤为重要。本例中引用了C语言库函数printf和exit，链接时必须替换为该进程的虚拟地址空间中机器代码所在位置。每个ELF中，都有专门的类型为REL的节包含重定位项，标识了需要进行重定位的位置。每一项都是用相同的数据结构表示的。1. 数据结构由于历史原因，有两种类型的重定位信息，由

2015-04-10 20:12:45 1425

翻译 Windows操作系统的分层

一、层次结构 Windows从总体上分为内核模式(Kernel Model)和用户模式(User Model)。谈到操作系统的内核模式和用户模式，一般会和CPU的特权层联系起来。CPU有多个特权层，例如，Intel的386CPU就有4个特权层，从第0层到第3层。其中第0层的特权最高，也就是可以执行任意代码，第3层特权最低，只能执行有限代码。 Windows将内核

2015-03-19 10:11:22 8287

原创 Linux系统ELF文件二进制格式分析(三)

本文接着《Linux系统ELF文件二进制格式分析(二)》进行分析四、符号表符号表保存了程序实现或使用的所有变量和函数，在一定程度上，变量和函数都可以认为是一种符号。如果一个目标文件当中使用了自身未定义的符号，则这个符号是未定义符号。这种符号必须在链接过程中解决其定义问题，可以是静态链接时在其他的目标文件或者库当中获取其定义，也可以是在加载时通过动态链接在共享库当中获取定义。符号表在

2015-03-17 20:03:00 2771

原创 Linux系统ELF文件二进制格式分析(二)

本文接着《Linux系统ELF文件二进制格式分析(一)》继续分析ELF文件格式

2015-03-11 11:16:35 4137

原创 Linux系统ELF文件二进制格式分析(一)

ELF是Executable andLinkable Format的缩写，它是Linux下可执行文件、目标文件和库文件的格式标准(Windows系统中可执行文件、目标文件和库文件的格式标准为PE格式)。ELF一个特别的优点在于同一文件格式可以用于Linux内核支持的几乎所有的体系结构上。该格式标准不仅用于用户空间应用程序和库文件，还用于构建模块，且内核本身也是ELF格式。我们知道，可执行文件可

2015-03-09 11:38:50 2541

翻译 Linux USB 驱动

一、USB连接结构USB采用树形拓扑结构，如图2.3所示。对于每个PC来说，都有一个或多个称为Host控制器(HC)的设备，该Host控制器和一个根Hub作为一个整体；这个根Hub下可以接多级的Hub，每个子Hub又可以接子Hub；每个USB作为一个节点接在不同级别的Hub上；一个Host控制器下最多可连接127个USB设备。

2014-10-30 11:01:13 587

翻译 Linux驱动模型

一、Linux设备驱动模型基本数据结构Linux设备驱动模型有两个基本数据结构：kobject，ksetkobject是组成设备模型的基本结构，类似于C++中的基类，它嵌入于更大的对象中用来描述设备模型的组件，如bus，devices，drivers，device_driver，bus_type等，这相当于面向对象程序设计语言中的继承机制[11]。每个kobject对象都对应于sy

2014-10-30 10:52:38 525

翻译 Windows驱动模型

Windows有两种驱动类型，一种是NT式驱动，另一种是WDM式驱动，两者最大不同是WDM式驱动支持即插即用(PNP)而NT式驱动则不支持。由于USB设备为即插即用设备，因此选择WDM为设计所用类型。一、重要数据结构Windows驱动中有两个重要的数据结构：DRIVER_OBJECT和DEVICE_OBJECT，两者结构中部分成员如下[19]： typedef struct

2014-10-30 10:45:57 2986

原创各种排序算法的比较

排序问题的解决方案是算法问题当中最多的，常见的有插入排序，选择排序，冒泡排序，归并排序，快速排序，堆排序等，下面将对不同的排序算法进行分析。假设均为实现从小到大排序，计算空间复杂度时，不考虑原本存储元素的空间，只考虑实现算法需要的额外空间。插入排序的基本思想是：从待排序的元素中选出一个，插入已排好序的元素队列中。重复操作直到所有元素全部被处理完。插入过程可以有两种情况：(1).

2014-10-12 08:54:32 836

原创 C++类对象大小的计算(三)含有虚函数、虚继承类大小计算

前一篇文章《C++类对象大小的计算(一)常规类大小计算》初步介绍类大小计算后，我们继续来讨论含有虚函数时类的大小。

2014-10-01 21:05:45 2217

原创 C++类对象大小的计算(二)含有虚函数类大小计算

以下内存测试环境为Win7+VS2012

2014-10-01 15:54:24 3939

原创 C++类对象大小的计算(一)常规类大小计算

C++类对象计算需要考虑很多东西，如成员变量大小，

2014-10-01 10:28:29 1463 1

原创 C++需要注意的细节问题(无限期添加)

1.C++类初始化顺序：基类，成员变量，

2014-09-29 18:49:58 612

翻译 Ubuntu更新数据源

以下各命令都需要在root用户下执行1、首先备份Ubuntu12.04源列表cp /etc/apt/sources.list /etc/apt/sources.list.backup （备份原来的源列表）2、修改更新源gedit /etc/apt/sources.list （打开Ubuntu 源列表文件）3、把里面的列表替换成下面的列表(可以只写入一个源也可以写入多个源)

2014-04-01 21:27:31 860

原创二元查找树变成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。比如将二元查找树 10 / \ 6 14 / \ /　 \4 8 12 　16转换成双向链表4=6=8=10=12=14=16。思路：基本思路为递归，对某个

2014-03-30 16:54:10 521

原创 Linux内核源代码目录结构

arch：英文单词architecture的简写，包含和硬件体系结构相关的代码。每种平台占一个相应的目录，如i386、amd64、arm、mips等。block：块设备驱动程序I/O调度。crypto：常用加密和散列算法、压缩和校验算法。Documentation：各部分的注释信息。firmware：某些驱动需要的固件。driver：驱动程序。不同的驱动程序都存在于不同的子目录

2014-03-28 16:32:37 585

原创 Linux 2.6内核下外部模块的编译

Linux的模块编译在2.6内核后有了较大的修改，这使得在内核编译过程中对那些源码属于内核源码集中的模块的编译方便了许多。因此，如果想单独编译某些模块(如开发的驱动程序，这些代码为自主编写的)，仅靠一般的makefile文件是不够的。2.4及其之前的内核模块编译需要在makefile文件中显示调用gcc编译器，并且需要添加多个参数才能实现。而2.6内核中，需要调用内核源码目录当中的顶层的mak

2014-03-26 22:43:53 768

原创 Linux系统SSH无密码登录远端主机

SSH无密码登录远端主机是通过非对称密钥认证方式实现的。假设A主机要用SSH登录B主机，需要在A主机上生成一个密钥对，包括一个公钥和一个私钥，而后将公钥复制到B主机上。当A通过SSH连接B时，B就会生成一个随机数并用A的公钥对随机数进行加密，并发送给A。A收到加密数之后再用私钥解密，并将解密数回传给B，B确认解密数无误之后就允许A进行连接了。省去了输入密码的过程。要实现无密码登录需要有ssh和

2014-03-18 21:18:32 818

翻译 Windows操作系统结构

一、层次结构Windows从总体上分为内核模式(Kernel Model)和用户模式(User Model)。谈到操作系统的内核模式和用户模式，一般会和CPU的特权层联系起来。CPU有多个特权层，例如，Intel的386CPU就有4个特权层，从第0层到第3层。其中第0层的特权最高，也就是可以执行任意代码，第3层特权最低，只能执行有限代码。Windows将内核模式运行在CPU的第0层，将用户

2014-03-14 16:22:12 5034

转载 Linux各目录的内容

Linux是以“一切皆是文件”这一思想构建起来的操作系统，因此有必要熟悉其各目录的用途。Linux中目录结构仍然是树形结构，目录树的根节点称为根目录，用“/”表示。对你的电脑来说，有且只有一个根目录。所有的东西都是从这里开始。 /bin：该目录存放二进制可执行命令，bin是binary的简称，包含了引导启动所需的命令或普通用户可能用的命令。这些命令都是二进制文件的可执行程序，多是系统中重要

2014-03-14 16:01:10 539

原创 0-1背包问题

有N件物品和一个容量为T的背包。第i件物品的大小是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。该问题是一个很老的问题，可以用动态规划或者回溯法解决。动态规划的主要思想为自下而上求解该问题，在整个求解过程中，所得到的中间结果被完全保留下来，因为最终最优解的获得是通过这些中间结果得到的，这些中间结果不一定是当前状态下的最优解，但也许会是

2013-12-27 19:25:13 659

OVS主线流程之ovs-vswitchd主体结构分析

空空如也