2011年11月

IA32CPU内存管理机制

最近看了一些Inter32CPU的内存管理机制,做个总结,但是我毕竟是新手,对很多东西也是一知半解,希望大家指教。
1.物理内存的管理,这不考虑MMU的内存管理机制,纯粹的对物理内存的管理,在电脑刚启动时候的实模式就应该是对实际物理内存的操作了。
2.虚拟内存的管理,Inter32CPU实现了一个分页的虚拟内存管理机制。

IA32CPU内存管理机制主要就是:分段和分页。平时程序里说的代码段,数据段不完全等于这个段。分页机制可以实现按需内存分配,虚拟地址等功能。对于分段和分页相结合的模式,非常灵活,最简单的情况下,采用平展段模式,禁止分页(通过CRO寄存器的一个比特位来实现)。要是复杂起来,采用不同段管理不同进程的不同数据,采
用分页机制实现按需分配,虚拟内存等。。。

- 阅读剩余部分 -

fedora16下codeblocks无法编辑----解决办法

     最近在fedora16下面安装了codeblocks,想写个程序,建了一个控制台程序,结果发现:可以输入!@#之类的,不能输入字母,但有时候重新启动能输入一个字母,之后再敲键盘就不行了。。。再是,我切换成中文的话是可以正常输入的,然后我再切换回英文,也能输入几个字母,一按下回车就又不能输入了‵‵‵‵非常奇怪。我重新卸载了,又安装,还是不能用,弄来弄去`````

    弄了几天终于找到问题了,原来我系统上安装的是ibus,这个输入法和codeblocks不兼容阿。。。我卸载了ibus就可以了,后来我又下载了个Fcitx输入法。。。总算都弄好了。。。。。。大笑

 

二叉树遍历--递归实现

递归这东西真是抽象,我看着看着算法,就囫囵吞枣地的写了下,写得囧了。这次先用递归实现先序,中序,后序遍历算法。先大概说下原理:我输入一大串字符,中间#就是代表了空,基本的储存结构就是二叉链表。主要就是二叉树的创建和三种顺序的遍历。二叉树的创建通过从左孩子开始创建不断递归,知道读取了#,开始创建对应的右孩子,继续递归。访问的时候对于三种顺序不过就是对于操作的顺序改变而已。

- 阅读剩余部分 -

Vim基本命令

    看了些资料,总结了一些适合编程人员的Vim基本命令,不是很全,但是最起码比较实用。。。都是最基本的大笑

vim 教程


在fedora下面,打开终端。
输入vim filename就进入了vim
///////////////////////////////

- 阅读剩余部分 -

二叉树按层次遍历--队列实现

二叉树(binary tree)

二叉树的基本形态
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
(1)空二叉树——(a)
(2)只有一个根结点的二叉树——(b)
(3)只有左子树——(c)
(4)只有右子树——(d)
(5)完全二叉树——(e)

度(Degree):节点孩子的数目。
叶子(Leaf): 度为0的节点称为叶子。
深度(Depth):树中最大的层次(从最上0开始数)

满二叉树:一棵深度为k且有2^k -1个节点的二叉树。
完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层有叶子节点,并且叶子节点都是从左到右依次排布,这就是完全二叉树。

性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2:深度为k的二叉树至多有2^k - 1个节点
性质3:任意一棵二叉树T,若其叶子节点数为n0,度为2的节点数为n2,则n0 = n2 + 1

对于完全二叉树:

性质4:具有n个节点的完全二叉树的深度是[log2n] + 1
性质5:有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I<>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

二叉树按层次遍历----队列实现
1.创建二叉树,输入#代表NULL,调用递归创建二叉树。
2.构建一个队列专门用来储存二叉树节点指针,先把根节点入队,假设是A,对A元素进行访问,然后对A的左右孩子依次入队,假设B,C。A出队列,再是对B进行访问,同样将B的左右孩子入队列,B出对列······重复以上,知道队列为空。

下面是的代码是实现按层次从上到下遍历二叉树:

[code]
#include <Windows.h>
#include <stdio.h>

#define ElemType char

typedef struct TreeNode{ //单位节点
struct TreeNode *LChild;
struct TreeNode *RChild;
ElemType c;
}TreeNode,* p_Tree;

typedef struct Link{ //单向链表
struct Link *Next;
TreeNode *Node;
}Link,*P_Link;

typedef struct Queue{ //形成队列
P_Link front;
P_Link rear;
int Q_Len;
}Queue,*p_Queue;

BOOL PrintElement(ElemType e); //对二叉树节点的操作,自定义,这里我设置为打印出内容
BOOL CreateTree(p_Tree* pBiTree); //创建二叉树
P_Link InitLink(P_Link L); //初始化链表
P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q); //插入队列
p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q); //取出队列第一个元素,并且访问左右孩子
p_Queue InitQueue(p_Queue T,P_Link L); //初始化队列

int main()
{
p_Tree Tree = NULL;
P_Link Link = NULL;
p_Queue Queue = NULL;
if(!CreateTree(&Tree)) //创建二叉树
{
printf("Create Tree Error\n");
return 0;
}
p_Tree p_Temp_Node = Tree;
Link = InitLink(Link);
Queue = InitQueue(Queue,Link);

Link = InsertLink(Link,p_Temp_Node,&Queue); //根节点入队

BOOL(*Operate)(ElemType); //定义函数指针
Operate = PrintElement;

while(Queue->front != Queue->rear)
{
Queue = GetTopLinkNode(Link,Operate,Queue); //获取队列第一个节点
Link = InsertLink(Link,Queue->front->Node->LChild,&Queue); //左孩子入队
Link = InsertLink(Link,Queue->front->Node->RChild,&Queue); //右孩子入队
}

return 0;
}

BOOL CreateTree(p_Tree* pBiTree)
{
ElemType ch;
ch = getchar();
if (ch == '#') //#代表NULL
{
(*pBiTree) = NULL;
}
else
{
(*pBiTree) = (p_Tree)calloc(1,sizeof(TreeNode));
if (!(*pBiTree))
{
printf("Allocate Memory Error\n");
return FALSE;
}
else
{
(*pBiTree)->c = ch;
CreateTree(&(*pBiTree)->LChild); //调用递归创建二叉树
CreateTree(&(*pBiTree)->RChild);
}
}
return TRUE;
}

P_Link InitLink(P_Link L)
{
L = (P_Link)calloc(1,sizeof(Link));
if (!L)
{
printf("Memory Error\n");
return NULL;
}
L->Node = NULL;
L->Next = NULL;
return L;
}

p_Queue InitQueue(p_Queue T,P_Link L)
{
T = (p_Queue)calloc(1,sizeof(Queue));
T->Q_Len = 0;
T->front = L;
T->rear = L;
return T;
}

P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q)
{
if (Tree_Node == NULL)
{
return L;
}
else
{
static P_Link p = L;
P_Link pNew;
pNew = (P_Link)calloc(1,sizeof(Link));
if (!pNew)
{
printf("Memory Error\n");
return 0;
}
pNew->Node = Tree_Node; //New Node
pNew->Next = NULL;
p->Next = pNew; //p to Next
p = pNew;
(*Q)->rear = p; //Add Queue
(*Q)->Q_Len++ ; //Q len ++
return L;
}
}

p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q)
{
Q->front = Q->front->Next; //remove first Node
Visit(Q->front->Node->c);
Q->Q_Len--;
return Q;
}

BOOL PrintElement(ElemType e)
{
// 输出元素e的值
printf("%c",e);
return TRUE;
}
[/code]

fedora安装微软雅黑和consola

微软雅黑一直是我认为的最好看的中文字体,而consola字体则是最适合程序员的字体。我个人是很喜欢的。

下面介绍下在fedora下面安装微软雅黑和consola的方法:

1.如果你是windows+fedora双系统的话,就直接在通过fedora访问windows的系统盘(一般是C盘),然后到Windows/Fonts下面,找到consola.ttf和msyh.ttf,点击安装,这样字体    就安装好了。(要是你没有windows的话,可能要去下载个包了),安装好了后就可以比如在chrome里面的字体设置里面会出现这两种字体的选择。

- 阅读剩余部分 -

一个十几行简单的C程序引发的思考

 今天碰到一个很好玩的程序,我纠结了很久才弄明白。。。吐舌头

下面解释都是在Debug模式下的:

#include <STDIO.H>
#include <windows.h>

void Fun();

int main()
{
BYTE *p;
p = (BYTE *)Fun;
printf("p = %Xn",p);
printf("*p = %Xn",*p);
printf("Fun = %Xn",Fun);
Fun();
return 0;
}

void Fun()
{
printf("Hello Worldn");
}
在VC6.0下输出的结果是

这下我就奇怪了,*p为什么是E9呢??毫无根据可言额.....(没学过汇编的人就是傻额大哭

我就开始调试了,*p是233 = 0XE9

疑问1.为什么*p的值是E9呢?

疑问2.Fun的值怎么是0X00401060呢?打印出来不是0X401005吗?

这是为什么呢??p的值不就是该函数的入口地址吗??函数名就是函数的入口地址啊?为什么就对了呢??

我继续调试,跑到里头去看看了····

首先可以知道一点就是,p = (BYTE *)Fun; 和 printf("Fun = %Xn",Fun);是通过一个偏移获取的一个地址,目前不知道这个地址是不是真正的函数入口地址。生气

再看Fun();这里call 0X00401005地址,我于是跟到了Fun()函数里面。下面是Fun函数的入口地址:

这下可就差不多可以解释了,这才是真正的函数入口地址啊!!奋斗那前面那个 0X00401005是什么呢???

我现在可以推断的就是编译器通过0X00401005来找到函数真正的函数入口地址(0X00401060) 。也就是说p =  00401005,这里存在一个跳转指令(E9)跳到了真正的函数入口地址。

再引入下函数输入表(不知道是不是这么叫的惊讶)的一些知识,程序一跑起来,会有一个函数的输入表,这里记录了部分调用函数的地址。看看那么多的DLL是怎样运作的呢?不需要把函数代码都嵌入到程序里面,到了运行的时候直接去找到对应的函数入口地址就行了,那么函数入口地址怎么找呢?就是通过函数输入表(专业的好像叫符号列表,也叫导出段)。在debug模式下面访问一个函数的时候往往都是先通过一个相对地址跳转找到函数输入表,然后找到函数输入表指定条目-------这里面就是函数入口地址,再通过跳转到真正的函数入口地址,执行函数。

 

上面的两个疑问就解决了

1. *p的值 E9 就是跳转指令,用于跳转到真正的函数入口地址。


2. 0X00401060才是Fun函数真正的入口地址,0X00401005则是Fun函数这一条目对应于函数输入表中的地址。


 

之后我用OD调试了下debug模式,下面是部分截图:

这里是相对偏移偏移地址,也就是p = (BYTE *)Fun;这句代码,从这里可以看出debug模式下确实是通过相对偏移来找到输入表中函数的地址。并且p = (BYTE *)Fun;和printf("Fun = %Xn",Fun);都是通过下面这种形式----即通过相对地址找到函数输入表,然后访问到真正函数来实现的。

 这里是函数调用处,也就是执行Fun();这句代码的地方,指令就是E9 后面的56000000是双字节的偏移量,再来看 p = 0X00401005,*p就是第一个字节(byte类型),也就是jmp指令(E9)。这调指令执行后就到了Fun()过程。

这里是Fun函数的入口点,地址是0X00401060,在反汇编里面叫做过程····

 

       刚刚在请教醒哥的时候,听了他讲了很多,还是只是了解了一小部分,全都是似有似无的概念,不过醒哥确实厉害,讲了些基本的理念之后,提醒我叫我自己去调试,并且告诉了我Debug模式下和Release模式下是不一样的。回到寝室我重新调了下,自己好好分析了才发现原来真是很不一样,不过这时候才真正理解了醒哥说的那些。。。

首先程序的输出就不一样了

 

下面是Release模式下的OD调试结果:

上面的反汇编我都做了些注释,可能有不对,因为自己不是很会,所以···(菜鸟只能这样,勤能补拙)。这里要注意的一点是这里代码中的0X00401060可不是上面那个Fun()

函数的地址额,这里应该只是巧合吧····(不是很懂,有点困了)。。。

从上面可以看出了Release模式下和Debug下的很大区别。在Release模式下就没有了函数输入表这个概念,访问函数的时候直接到了函数的真正的内存中的地址(不是物理地址(*^__^*) ),p = (BYTE *)Fun;和printf("Fun = %Xn",Fun);都是采用的都是真正地址,这样就比上面Debug模式少了一次访问,这个更加高效,这样就是为什么成型产品是一个Debug模式的一个原因吧。

额····有点累了,睡觉了···(*^__^*) 

Linux基本常用命令

    man vim

    命令帮助,查看命令使用形式。

命令行下快捷

有时候在 X-Window里由于程序出错,使鼠标键盘都不起作用, 这时候不用着急, 因为在Linux下几乎不会像在Win 9x里那样恶性死机, 你只须键入Ctrl+Alt+BackSpace键就可以回到
字符界面下了。

- 阅读剩余部分 -

基本调试命令

OD基本调试命令


F2:设置断点
F8:执行下一条指令
F7:单步步入,功能和F8类似,区别是遇到cll指令调试子程序会跟进子程序
F4:运行到选定位置
F9:运行程序,若是没有断点就一直处于运行状态
F12:停止运行

 

Debug基本调试命令


debug filename 进入调试
-R 查看,修改寄存器的内容,比如R CS,可以查看CS寄存器内容,并且可以修改
-D 查看内存中的内容。比如 D 0010,查看内存是0010的内容
-E 修改内存中的内容,和D使用一样
-U 将内存中的机器指令翻译成汇编指令
-T 执行下一条机器指令
-A 以汇编指令的格式在内存中写入一条机器指令

 

TC基本调试命令


F7:Trace into 单步跟踪,进入函数内部。
F8:Step over 单步跟踪,跳过函数。
Ctr+F7:查看变量
Ctr+F8:设置断点

Ctr+F9:执行到下一断点

一些基本的IDE调试命令就不说了,上面写的都是就是当作记事本了···