xml version="1.0" encoding="utf-8" standalone="yes"12bet++博客-sin的博客http://www.fometaux.com/sixinquan/时间悄悄地流过,今日你做了什么zh-cnSun, 25 Aug 2019 19:44:07 GMTSun, 25 Aug 2019 19:44:07 GMT6012bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2019/02/22/216254.htmlsinsinFri, 22 Feb 2019 04:51:00 GMThttp://www.fometaux.com/sixinquan/archive/2019/02/22/216254.htmlhttp://www.fometaux.com/sixinquan/comments/216254.htmlhttp://www.fometaux.com/sixinquan/archive/2019/02/22/216254.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/216254.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/216254.html将12bet怎么样搬至CSDN

sin 2019-02-22 12:51 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2013/10/29/203981.htmlsinsinTue, 29 Oct 2013 14:40:00 GMThttp://www.fometaux.com/sixinquan/archive/2013/10/29/203981.htmlhttp://www.fometaux.com/sixinquan/comments/203981.htmlhttp://www.fometaux.com/sixinquan/archive/2013/10/29/203981.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/203981.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/203981.html

自旋锁(spin lock)应用在多处理器环境中。假如内核操控途径发现自旋锁“开着”,就获取锁并持续自己的履行。相反,假如内核操控途径发现锁由运转在另一个CPU上的内核操控途径“锁 着”,就在周围“旋转”,重复履行一条紧凑的循环指令,直到锁被开释。自旋锁的循环指令表明“忙等”。即便等候的内核操控途径无事可做(除了浪费时间),它也在CPU上坚持运转。不过,自旋锁一般十分便利,由于许多内核资源只锁1毫秒的时间片段;所以说,等候自旋锁的开释不会耗费太多CPU的时间。

一般来说,由自旋锁所保护的每个临界区都是制止内核抢占的。在单处理器体系上,这种锁自身并不起锁的效果,自旋锁技能仅仅是用来制止或启用内核抢 占。请注意,在自旋锁忙等期间,由于并没有进入临界区,所以内核抢占仍是有用的,因而,等候自旋锁开释的进程有或许被更高优先级的所替代。这种规划是合理 的,由于不能由于占用CPU太久而使体系死锁。


互斥锁(mutex lock)的完结,实践上便是一把锁保护了一个等候行列和一个引证计数器,当获取锁之前,先对引证计数器减1操作,假如为非负,则能够获取锁进入临界区。不然将该使命设为不行中止状况(uninterruptible),挂在该等候对列上。获取锁的使命从临界区退出后,计数器加1操作,唤醒(wake up)等候行列上的被挂起进程。

sin 2013-10-29 22:40 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2013/10/26/203929.htmlsinsinSat, 26 Oct 2013 15:39:00 GMThttp://www.fometaux.com/sixinquan/archive/2013/10/26/203929.htmlhttp://www.fometaux.com/sixinquan/comments/203929.htmlhttp://www.fometaux.com/sixinquan/archive/2013/10/26/203929.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/203929.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/203929.html阅览全文

sin 2013-10-26 23:39 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2013/10/19/203817.htmlsinsinSat, 19 Oct 2013 13:36:00 GMThttp://www.fometaux.com/sixinquan/archive/2013/10/19/203817.htmlhttp://www.fometaux.com/sixinquan/comments/203817.htmlhttp://www.fometaux.com/sixinquan/archive/2013/10/19/203817.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/203817.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/203817.html
转自:http://blog.csdn.net/pathuang68/article/details/4156308

CSDN网友问:
class A
{
public:
   
~A() 
   { 
      cout 
< <"A::~A" < <endl; 
   }
};


class B:public A
{
public
   
virtual ~B() 
   { 
      cout 
< <"B::~B" < <endl; 
   }
};


class C:public B
{
public
   
~C() 
   { 
      cout 
< <"C::~C" < <endl; 
   }
};

 
int main()

   A 
*a=new A(); 
   B 
*b=new B(); 
   C 
*c=new C(); 
   A 
*d=new B(); 
   A 
*e=new C(); 
   B 
*f=new C(); 

   delete a; 
   cout 
< <endl; 
   delete b; 
   cout 
< <endl; 
   delete c; 
   cout 
< <endl; 
   delete d; 
   cout 
< <endl; 
   delete e; 
   cout 
< <endl; 
   delete f; 
   cout 
< <endl; 

   system(
"Pause");
}

这段程序运转时有错,其时考的时分标题直接说写出运转成果,我就稀里糊涂得写下来,回来编下发现有错,请教下错在哪,最好告诉我为什么?

  

玄机逸士答复:

1. 一般来说,假如一个类要被别的一个类承继,而且用其指针指向其子类目标时,如标题中的A* d = new B();(假定A是基类,B是从A承继而来的派生类),那么其(A)析构函数有必要是虚的,不然在delete d时,B类的析构函数将不会被调用,因而会发作内存走漏和反常;

2. 在结构一个类的目标时,先结构其基类子目标,即调用其基类的结构函数,然后调用本类的结构函数;毁掉目标时,先调用本类的析构函数,然后再调用其基类的结构函数;

3. 标题给出的代码是能够编译的,但会呈现运转时过错。过错呈现在delete d;这一句。为谈论便利,咱们无妨将A类和B类改写如下:


class A
{
public:
    
int a;
    
~A()
    {
        cout 
<< "A::~A" << endl;
    }
};

class B : public A
{
public:
    
int b;
    
virtual ~B()
    {
        cout 
<< "B::~B" << endl;
    }
};


那么A* d = new B();这一句的左面所发作B的目标的内存结构如下:



A目标的内存结构如下:


可见d只能找到aA类的析构函数,而无法找到B目标的析构函数,所以当delete d;的时分,B目标所占用的内存就此被走漏掉了,也然后发作了反常。

假如将
A类的析构函数设为虚的,那么A类目标的内存结构将为:


B类目标的内存结构为:


此刻经过A* d = new B();A目标的内存结构中的vfptr,即虚函数表指针,便是B目标的vfptr(B目标的vfptrbitwise copy,即浅拷贝到A目标的vfptr。如B是从A虚承继而来的,则需求加一个offset,状况要更杂乱,见http://blog.csdn.net/pathuang68/archive/2009/04/24/4105902.aspx),因而,A目标的vfptr所指向的是B目标的虚函数表,而B的析构函数坐落书札数表0的方位,因而,这样就能够经过A类目标的指针d,找到B类目标的析构函数,然后在delete d;时,能够毁掉B目标,而不会发作内存走漏和反常。


事实上,该标题只需将A中的析构函数设成虚的,B类中的析构函数前面的virtual关键字不论是否存在,其析构函数也必定是虚的,C类同此道理。因而,得到定论便是,只需能够保证承继联系中最高的基类的析构函数是虚的,那么就不会发作前面所谈及的问题。这便是为什么在想运用多态特性的时分,需求将基类的析构函数设成虚的真实原因。

 



sin 2013-10-19 21:36 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2013/10/18/203808.htmlsinsinFri, 18 Oct 2013 13:54:00 GMThttp://www.fometaux.com/sixinquan/archive/2013/10/18/203808.htmlhttp://www.fometaux.com/sixinquan/comments/203808.htmlhttp://www.fometaux.com/sixinquan/archive/2013/10/18/203808.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/203808.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/203808.html滑动窗口协议的基本原理便是在恣意时间,发送方都坚持了一个接连的答应发送的帧的序号,称为发送窗口;一起,接纳方也坚持了一个接连的答应接纳的帧的序号,称为接纳窗口。发送窗口和接纳窗口的序号的上下界纷歧定要相同,乃至巨细也能够不同。不同的滑动窗口协议窗口巨细一般不同。发送方窗口内的序列号代表了那些现已被发送,可是还没有被承认的帧,或许是那些能够被发送的帧。下面举一个比方(假定发送窗口尺度为2,接纳窗口尺度为1):


①初始态,发送方没有帧宣布,发送窗口前后沿相重合。接纳方0号窗口翻开,等候接纳0号帧;
②发送方翻开0号窗口,表明已宣布0帧但尚承认回来信息。此刻接纳窗口状况不变;
③发送方翻开0、1号窗口,表明0、1号帧均在等候承认之列。至此,发送方翻开的窗口数已达规则极限,在未收到新的承认回来帧之前,发送方将暂停发送新的数据帧。接纳窗口此刻状况仍未变;
④接纳方已收到0号帧,0号窗口封闭,1号窗口翻开,表明预备接纳1号帧。此刻发送窗口状况不变;
⑤发送方收到接纳方发来的0号帧承认回来信息,封闭0号窗口,表明从重宣布中删去0号帧。此刻接纳窗口状况仍不变;
⑥发送方持续发送2号帧,2号窗口翻开,表明2号帧也归入待承认之列。至此,发送方翻开的窗口又已达规则极限,在未收到新的承认回来帧之前,发送方将暂停发送新的数据帧,此刻接纳窗口状况仍不变;
⑦接纳方已收到1号帧,1号窗口封闭,2号窗口翻开,表明预备接纳2号帧。此刻发送窗口状况不变;
⑧发送方收到接纳方发来的1号帧收毕的承认信息,封闭1号窗口,表明从重宣布中删去1号帧。此刻接纳窗口状况仍不变。


sin 2013-10-18 21:54 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2012/07/29/185545.htmlsinsinSun, 29 Jul 2012 06:44:00 GMThttp://www.fometaux.com/sixinquan/archive/2012/07/29/185545.htmlhttp://www.fometaux.com/sixinquan/comments/185545.htmlhttp://www.fometaux.com/sixinquan/archive/2012/07/29/185545.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/185545.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/185545.html

如上图,Linux分配页时,只能分配2^n个页。内核保护MAX_ORDER个链表,每个链表记录着接连的闲暇页。榜首个链表中的每一项为1个闲暇页,第二个链表中的每一项为2个闲暇页,第三个链表中的每一项为4个闲暇页。。。,顺次类推。分配页时,从对应的链表上去除闲暇页;开释页时,将对应的页归还到对应的链表。分配开释页的进程中,或许伴随着内存页的拆分和兼并。比方要分配16个闲暇页,可是对应的链表为空,这时假如32个闲暇页对应的链表假如不为空,则从链表中去除32个闲暇页,并将其一分为二,其间16个页用于内存分配,剩下16个页则刺进到16个页对应的链表中。

尽管页的分配算法是简略的,可是实践进程却十分杂乱。这是由于分配页式有必要考虑一下几点:
1 备用内存区。当从一个内存区无法得到内存时,体系会从同一内存节点的其它内存区或许从另一个内存节点中的内存区中获取内存。
2 页的换入和换出,在没有足够多的闲暇页时,或许需求将页换出以获取闲暇内存。
3 页的收回,对一些缓冲区的不再运用的页进行收回,以获取闲暇页。
4 体系中有必要坚持必定“水位”的闲暇页,以敷衍对内存的紧迫分配。假如体系将页分配完,在急需内存时,再进行页的收回或换出,无疑是十分糟糕的规划。体系中有必要坚持必定量的内存页。
5 不同的分配战略。不同的分配战略或许选用的办法有差异。
总归,页的分配和开释需求考虑许多要素,尽量满意内存分配的一起,要保证体系的稳定性和健壮性。

sin 2012-07-29 14:44 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2012/07/29/185090.htmlsinsinSun, 29 Jul 2012 01:38:00 GMThttp://www.fometaux.com/sixinquan/archive/2012/07/29/185090.htmlhttp://www.fometaux.com/sixinquan/comments/185090.htmlhttp://www.fometaux.com/sixinquan/archive/2012/07/29/185090.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/185090.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/185090.htmlUMA(Uniform Memory Access),即一致性内存拜访。这种状况下,CPU拜访内存的任何方位,价值都是相同的。
NUMA)(Non Uniform Memory Access),即非一致性内存拜访。这种状况下,CPU拜访不同方位的内存,价值是纷歧样的。在多CPU状况下,对每个CPU来说有本地内存和远端内存,拜访本地内存的价值比拜访远端内存的价值小。保证CPU拜访内存价值最小,是十分重要的一点。

Linux支撑多种硬件体系结构,因而Linux有必要选用通用的办法来描绘内存,以便利对内存进行办理。为此,Linux有了内存节点、内存区、页框的概念,这些概念也是一望而知的。
内存节点:首要依据CPU拜访价值的不同而区别。多CPU下环境下,本地内存和远端内存便是不同的节点。即便在单CPU环境下,拜访一切内存的价值都是相同的,Linux内核依然存在内存节点的概念,只不过只需一个内存节点罢了。内核以struct  pg_data_t来描绘内存分区。
内存分区:Linux对内存节点再进行区别,分为不同的分区。内核以struct zone来描绘内存分区。一般一个节点分为DMA、Normal和High Memory内存区,详细下面再介绍。
页框:Linux选用页式内存办理,页是物理内存办理的基本单位,每个内存分区又由许多的页框组成。内核以struct page来描绘页框。页框有许多特点,这些特点描绘了这个页框的状况、用处等,例如是否被分配。


上图中的zone_mem_map是一个页框的数组,它记录了一个内存分区的一切页框的运用状况。

DMA内存区:即直接内存拜访分区,一般为物理内存的开始16M。首要是供一些外设运用,外设和内存直接拜访数据拜访,而无需体系CPU的参加。
Normal内存区:从16M到896M内存区。
HighMemory内存区:896M今后的内存区。

为什么高端内存的鸿沟是896M?这是由于,32位Linux虚拟内存空间为0-4G,其间0-3G用于用户态,3G-4G用于内核态。这意味着内核只需1G的虚拟地址空间,假如物理内存超越1G,内核就无法映射了。Linux采纳的战略是,内核地址空间的前896M选用固定映射,映射办法是:虚拟地址-3G = 物理地址,只能映射到物理地址的前896M。也便是说内核虚拟地址空间的3G到3G+896M这部分,页表的映射是固定的,体系初始化时就树立起来。而虚拟地址空间的终究128M,也便是3G+896M到4G部分选用动态映射,也便是说页表映射的物理地址可变的。在体系运转进程中,经过更新页表,就能够映射到不同的物理地址,当然也包含高端物理内存。

这首要处理了两个问题:榜首,这能够使内核地址空间映射到高端物理内存;第二,虚拟地址空间的3G+896M到4G部分,接连的虚拟地址空间能够映射到非接连的物理内存,只需经过更新页表就能够做到,这和用户态的虚拟内存映射选用了相同这种办法。这在没有大段接连的闲暇物理地址时,是十分重要的。

备用内存区:
在一个内存区别配页时,假如这个内存区没有满意条件的内存页,则需求从其它内存区或从其它内存节点分配。Linux为每个内存区都树立了备用内存区列表,当时内存区没有满意条件的内存时,就从备用内存区别配。比方,体系中有4个内存节点A,B,C,D,每个内存节点又分为DMA、Normal、HighMemory内存区。对节点B来说,内存区别配列表或许是B(HighMemory)、B(Normal)、B(DMA)、
A(HighMemory)、A(Normal)、A(DMA)、
C(HighMemory)、C(Normal)、C(DMA)、
D(HighMemory)、D(Normal)、D(DMA)。
分配内存时,优先从本地内存节点分配,再从其它内存节点分配。对一个内存节点,优先从HighMemory分配,再从Normal或DMA分配。


sin 2012-07-29 09:38 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2012/07/19/184234.htmlsinsinThu, 19 Jul 2012 13:22:00 GMThttp://www.fometaux.com/sixinquan/archive/2012/07/19/184234.htmlhttp://www.fometaux.com/sixinquan/comments/184234.htmlhttp://www.fometaux.com/sixinquan/archive/2012/07/19/184234.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/184234.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/184234.html
段式内存办理,便是将内存分红段,每个段的开始地址便是段基地址。地址映射的时分,由逻辑地址加上段基地址而得到物理地址。朴实的段式内存办理的缺陷很明显,便是灵敏性和功率比较差。首先是段的长度是可变的,这给内存的换入换出带来诸多不便,怎么挑选一个段的长度是一个扎手的问题;其次进程在运转进程中,或许会扩大地址空间,这就要添加段,然后构成进程的地址空间由许多小段构成,在进程运转进程中,拜访不同的段时,就需求频频切换段基地址;再一点,段式内存办理假如有太多的小段,在开释段的时分,会构成外部碎片。

页式内存办理,内存分红固定长度的一个个页片。地址映射的时分,需求先树立页表,页表中的每一项都记录了这个页的基地址。经过页表,由逻辑地址的高位部分先找到逻辑地址对应的页基地址,再由页基地址偏移必定长度就得到终究的物理地址,偏移的长度由逻辑地址的低位部分决议。一般状况下,这个进程都能够由硬件完结,所以功率仍是比较高的。页式内存办理的长处便是比较灵敏,内存办理以较小的页为单位,便利内存换入换出和扩大地址空间。

严厉说Linux选用段页式内存办理,也便是既分段,又分页。地址映射的时分,先确认对应的段,确认段基地址;段内分页,再找到对应的页表项,确认页基地址;再由逻辑地址低位确认的页偏移量,就能找到终究的物理地址。可是,实践上Linux选用的是页式内存办理。原因是Linux中的段基地址都是0,相当于一切的段都是相同的。这样做的原因是某些体系结构的硬件约束,比方Intel的i386。作为软件的操作体系,有必要要契合硬件体系。尽管一切段基地址都是0,可是段的概念在Linux内核中是的确存在的。比方常见的内核代码段、内核数据段、用户态代码段、用户态数据段等。除了契合硬件要求外,段也是有实践意义的。

x86硬件分段单元:

逻辑地址分为两部分组成:段标识符和指定段内相对地址的偏移量。
段描绘符:用来寄存段开始地址,段巨细,存储权限等。
段描绘符表:寄存段描绘的表项。
段寄存器:寄存段标识符。6个段寄存器称为cs(代码段寄存器),ss(栈段寄存器),ds(数据段寄存器),es,fs 和gs。
段基地址寄存器:指向段描绘符表地址。

Linux分段机制:
Linux对分段运用十分有限。作为一个跨硬件体系的操作体系,要支撑多种硬件体系,而一些硬件体系结构式不支撑分段的,Linux把一切段开始地址都设为0。
Linux选用4个段进行寻址,用户态代码段,用户态数据段,内核态代码段,内核态数据段。


x86分页单元:

x86选用两级页表。
榜首级为页目录表,存储在一个4K字节的页中,每个表项包含了一个页表的物理地址。线性地址最高的10位(22-31)用来发作榜首级表索引,由该索引得到的表项中的内容定位了二级表中的一个表的地址,即下级页表地点的内存块号。
第二级为页表,存储在一个4K字节页中,每个表项包含了一个页的物理地址。线性地址的中心10位(12-21)位进行索引,定位页表表项,取得页的物理地址。页物理地址的高20位与线性地址的低12位构成终究的物理地址。
分页机制由CR0寄存器中的PG位启用。如PG=1,启用分页机制,把线性地址转换为物理地址。如PG=0,禁用分页机制,直接段机制发作的线性地址当作物理地址运用。
页目录表的物理地址寄存在CR3寄存器。每个进程有它自己的页大局目录和自己的页表集。当发作进程切换时,Linux把CR3操控寄存器的内容保存在前一个履行进程的描绘符中,然后把下一个要履行进程的描绘符的值装入CR3寄存器中。这保证了当新进程重新开始在CPU上履行时,分页单元指向一组正确的页表。

Linux分页机制:
作为一个通用的操作体系,Linux需求兼容各种硬件体系,包含不同位数的CPU。对64位的CPU来说,两级页表依然太少,一个页表会太大,这会占用太多名贵的物理内存。Linux选用了通用的四级页表。实践选用几级页表则详细受硬件的约束。

四种页表别离称为: 页大局目录、页上级目录、页中心目录、页表。关于32位x86体系,两级页表现已足够了。Linux经过使“页上级目录”位和“页中心目录”位全为0,完全取消了页上级目 录和页中心目录字段。不过,页上级目录和页中心目录在指针序列中的方位被保存,以便相同的代码在32位体系和64位体系下都能运用。

sin 2012-07-19 21:22 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2010/03/16/109802.htmlsinsinTue, 16 Mar 2010 01:57:00 GMThttp://www.fometaux.com/sixinquan/archive/2010/03/16/109802.htmlhttp://www.fometaux.com/sixinquan/comments/109802.htmlhttp://www.fometaux.com/sixinquan/archive/2010/03/16/109802.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/109802.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/109802.html
#include <stdio.h>
#include 
<stdlib.h>

#define MAX_SIZE 128

struct node 
{
    
int        data;
    
struct node*    lchild;
    
struct node*    rchild;
};

struct bin_search_tree 
{
    
struct node*    root;
};


void    init_search_tree(struct bin_search_tree *tree);
void    clear_search_tree(struct bin_search_tree *tree);
void    insert_node(struct bin_search_tree *tree, int element);

void    pre_order(struct node *p);
void    in_order(struct node *p);
void    post_order(struct node *p);

void    visit(struct node *p);


int main()
{
    
struct bin_search_tree tree;
    
int i,arr[] = {4030501127987479915037};
    
    init_search_tree(
&tree);
    
for (i=0; i<sizeof(arr)/sizeof(int); i++)
    {
        insert_node(
&tree, arr[i]);
    }

    
//前序遍历
    pre_order(tree.root);
    printf(
"\n");

    
//中序遍历
    in_order(tree.root);
    printf(
"\n");

    
//后续遍历
    post_order(tree.root);
    printf(
"\n");

    clear_search_tree(
&tree);
    getchar();
    
return 0;
}



/*
* 二叉树的初始化
*/
void init_search_tree(struct bin_search_tree *tree)
{
    tree
->root = NULL;
}

/*
* 铲除二叉树,用二叉树层次遍历
*/
void clear_search_tree(struct bin_search_tree *tree)
{
    
int i,j;
    
struct node *p,*queue[MAX_SIZE];

    i 
= j = 0;
    queue[
0= tree->root;

    
while (i<=j)
    {
        
for ( ; i<=j; i++ )
        {
            p 
= queue[i];

            
if (p->lchild)
                queue[
++j] = p->lchild;
            
if (p->rchild)
                queue[
++j] = p->rchild;
        }
    }

    
for (i=0; i<=j; i++)
    {
        free(queue[i]);
    }

    tree
->root = NULL;
}

/*
* 二叉树中刺进节点element
*/
void insert_node(struct bin_search_tree *tree, int element)
{
    
struct node    *= tree->root;
    
struct node *child, *newnode;

    newnode 
= (struct node*)malloc(sizeof(struct node));
    newnode
->data = element;
    newnode
->lchild = NULL;
    newnode
->rchild = NULL;

    
if (tree->root == NULL)
    {
        tree
->root = newnode;
        
return;
    }

    
while (p)
    {
        
if ( element < p->data )
        {
            child 
= p->lchild;
            
if (NULL == child)
            {
                p
->lchild = newnode;
                
return;
            }
        }
        
else
        {
            child 
= p->rchild;
            
if (NULL == child)
            {
                p
->rchild = newnode;
                
return;
            }
        }

        p 
= child;
    }
}

/*
* 前序遍历,非递归
*/
void pre_order(struct node *p)
{
    
int top = -1;
    
struct node *stack[MAX_SIZE];

    
if (p == NULL)
        
return;

    stack[
++top] = p;
    
while (top>-1
    {
        visit(p
=stack[top--]);

        
if (p->rchild)
            stack[
++top] = p->rchild;
        
if (p->lchild)
            stack[
++top] = p->lchild;
    } 
}

/*
* 中序遍历,非递归
*/
void in_order(struct node *p)
{
    
int top = -1;
    
struct node *stack[MAX_SIZE];

    
while (top>-1 || p!=NULL)
    {
        
while (p)
        {
            stack[
++top] = p;
            p 
= p->lchild;
        }
        visit(p
=stack[top--]);
        p 
= p->rchild;
    }
}

/*
* 后序遍历,非递归
*/
void post_order(struct node *p)
{
    
int top = -1;
    
int flag[MAX_SIZE];
    
struct node *stack[MAX_SIZE];

    
while (top>-1 || p!= NULL)
    {
        
while (p)        //将p的一切左节点压入栈
        {
            stack[
++top] = p;
            flag[top] 
= 0;
            p 
= p->lchild;
        }

        p 
= stack[top];    //弹出栈顶
        if (flag[top--]==0 && p->rchild)
        {
            stack[
++top] = p;
            flag[top] 
= 1;
            p 
= p->rchild;
        } 
        
else
        {
            visit(p);
            p 
= NULL;    //将p置为NULL,避免进入while(p)循环
        }
    }
}

/*
* 拜访一个节点
*/
void visit(struct node *p)
{
    printf(
"%d  ", p->data);
}




sin 2010-03-16 09:57 宣布谈论
]]>
12bet++博客-sin的博客http://www.fometaux.com/sixinquan/archive/2010/03/15/109713.htmlsinsinSun, 14 Mar 2010 17:22:00 GMThttp://www.fometaux.com/sixinquan/archive/2010/03/15/109713.htmlhttp://www.fometaux.com/sixinquan/comments/109713.htmlhttp://www.fometaux.com/sixinquan/archive/2010/03/15/109713.html#Feedback0http://www.fometaux.com/sixinquan/comments/commentRss/109713.htmlhttp://www.fometaux.com/sixinquan/services/trackbacks/109713.html实践上,假如创立一个信号量,而且它的最大计数是1,那么它就与Mutex等价。

下面是个出产者-顾客问题的Win32程序,运转时的截图如下:


代码如下:
/* 出产者-顾客问题是一个经典的进程同步问题,该问题最早由Dijkstra提出;许多计算机问题都能够笼统为出产者-顾客问题。
 * 有1个出产者出产产品放到环形buffer中供5个顾客消费;出产者每次最多出产5个产品,顾客每次消费1个。
 * 要处理这个问题,咱们有必要保证:(1)而且当缓冲区中没有产品时,顾客不能消费,缓冲区满时,出产者也不能出产产品 (2)不同顾客  * 不能一起消费同一个产品;
 *
 * 处理(1)咱们用一个出产者信号量表明出产者者资源,即闲暇buffer数量;用一个顾客信号量表明顾客资源,即非闲暇buffer数量。
 * 处理(2)咱们用一个互斥量Mutex,得到这个Mutex的顾客才干消费。
*/

#include 
<time.h>
#include 
<stdlib.h>
#include 
<Windows.h>


#define ASSERT(a) if (!(a)) \
    exit(EXIT_FAILURE)

#define MAX_PRODUCE_COUNT    5      //出产者每次最多出产数量
#define CONSUMER_COUNT        5     //顾客数量
#define BUFFER_SIZE        20       //缓冲区巨细
#define SLEEP_TIME        600
#define WM_FORCE_PAINT        (WM_APP+10)

void    ProduceAndConsume();
void    EndProduceConsume();

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM) ;  
//Win32窗口回调函数

DWORD    WINAPI    ProducerThread(LPVOID pVoid);   
//出产者线程函数
DWORD    WINAPI    ConsumerThread(LPVOID pVoid);   //顾客线程函数

int        iProducerPointer;         //出产者指针,指向能够放产品的的方位
int        iConsumerPointer;         //顾客指针,指向能够消费产品的方位
HANDLE        hProducerSemaphore;    //出产者信号量,初始有20个资源
HANDLE        hConsumerSemaphore;    //顾客信号量,初始有0个资源
HANDLE        hConsumerMutex;        //出产者Mutex

HANDLE        hProducerThread;                    
//出产者线程,不断出产产品
HANDLE        hConsumersThread[CONSUMER_COUNT];    //顾客线程,不断消费产品
HWND        hWnd;

int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
                    PSTR szCmdLine, 
int iCmdShow)
{
    
static TCHAR szAppName[] = TEXT("生长者顾客") ;
    MSG        msg ;
    WNDCLASS    wndclass ;


    wndclass.style        
= CS_HREDRAW | CS_VREDRAW ;
    wndclass.lpfnWndProc  
= WndProc ;
    wndclass.cbClsExtra   
= 0 ;
    wndclass.cbWndExtra   
= 0 ;
    wndclass.hInstance    
= hInstance ;
    wndclass.hIcon        
= LoadIcon (NULL, IDI_APPLICATION) ;
    wndclass.hCursor      
= LoadCursor (NULL, IDC_ARROW) ;
    wndclass.hbrBackground
= (HBRUSH) GetStockObject (WHITE_BRUSH) ;
    wndclass.lpszMenuName 
= NULL ;
    wndclass.lpszClassName
= szAppName ;

    
if (!RegisterClass (&wndclass))
    {
        MessageBox (  NULL, TEXT (
"This program requires Windows NT!"),
            szAppName, MB_ICONERROR) ;
        
return 0 ;
    }

    hWnd 
= CreateWindow( szAppName,      
        TEXT (
"生长者顾客"),   
        WS_OVERLAPPEDWINDOW,  
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        NULL,                 
        NULL,            
        hInstance,   
        NULL) ;     

    ShowWindow (hWnd, iCmdShow) ;
    UpdateWindow (hWnd) ;

    ProduceAndConsume();      
//创立出产者顾客线程、信号量、Mutex,并运转

    
while (GetMessage (&msg, NULL, 00))
    {
        TranslateMessage (
&msg) ;
        DispatchMessage (
&msg) ;
    }
    
    EndProduceConsume();

    
return (int)msg.wParam ;
}


LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    
int        iTemp;
    
int        iXStart,iYStart;
    HDC             hdc ;
    HBRUSH        hBrush;
    PAINTSTRUCT    ps ;
    RECT        rect;
    MSG        msg;

    
switch (message)
    {
    
case WM_CREATE:
        
return 0 ;

    
case WM_FORCE_PAINT:
        InvalidateRect(hWnd, NULL, TRUE);
        
while (PeekMessage(&msg, hWnd, WM_FORCE_PAINT, WM_FORCE_PAINT, PM_REMOVE))
            ;
        
return 0;

    
case  WM_PAINT:    
        hdc 
= BeginPaint (hwnd, &ps) ;

        GetClientRect(hWnd,
&rect);
        iXStart 
= (rect.right-rect.left)/2-200;
        iYStart 
= (rect.bottom-rect.top)/2-10;
        hBrush 
= SelectObject(hdc, (HBRUSH)GetStockObject(GRAY_BRUSH));
        iTemp 
= iConsumerPointer;

        
while (TRUE)
        {
            Rectangle(hdc, iXStart
+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            
if (++iTemp >= BUFFER_SIZE)
                iTemp 
= 0;
            
if (iTemp == iProducerPointer)
                
break;
        }

        SelectObject(hdc, hBrush);

        
while (TRUE)
        {
            Rectangle(hdc, iXStart
+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            
if (++iTemp >= BUFFER_SIZE)
                iTemp 
= 0;
            
if (iTemp == iConsumerPointer)
                
break;
        }

        EndPaint (hwnd, 
&ps) ;
        
return 0 ;

    
case   WM_DESTROY:
        PostQuitMessage (
0) ;
        
return 0 ;
    }

    
return DefWindowProc (hwnd, message, wParam, lParam) ;
}

DWORD WINAPI ProducerThread(LPVOID pVoid)
{
    
int        i;
    
int        iRandom;

    
while (TRUE)
    {
        srand((unsigned)time(NULL));
        iRandom 
= rand()%MAX_PRODUCE_COUNT;
        
if (iRandom == 0)
            iRandom
++;

        
//出产者请求iRandom个资源
        for (i=0; i<iRandom; i++)
            ASSERT( WAIT_OBJECT_0 
== WaitForSingleObject(hProducerSemaphore, INFINITE) );

        
//出产者出产iRandom个产品
        iProducerPointer = iProducerPointer+iRandom;
        
if (iProducerPointer>=BUFFER_SIZE)
            iProducerPointer 
= iProducerPointer-BUFFER_SIZE;

        SendMessage(hWnd, WM_FORCE_PAINT, 
00);
        Sleep(SLEEP_TIME);

        
//出产者出产了iRandom个产品,顾客有更多的产品消费了;所认为顾客开释iRandom个资源
        ASSERT(ReleaseSemaphore(hConsumerSemaphore, (long)iRandom, NULL));
    }

    
return 0;
}

DWORD WINAPI ConsumerThread(LPVOID pVoid)
{
    
while (TRUE)
    {
        
//顾客请求到Semaphore和Mutex后,才干消费
        ASSERT( WAIT_OBJECT_0 == WaitForSingleObject(hConsumerSemaphore, INFINITE) );
        ASSERT( WAIT_OBJECT_0 
== WaitForSingleObject(hConsumerMutex, INFINITE) );

        
//顾客消费一个产品
        iConsumerPointer++;
        
if (iConsumerPointer>=BUFFER_SIZE)
            iConsumerPointer 
= 0;

        SendMessage(hWnd, WM_FORCE_PAINT, 
00);
        Sleep(SLEEP_TIME
/2);
        
        
//顾客开释Mutex
        ASSERT(ReleaseMutex(hConsumerMutex));

        
//顾客消费了一个产品,buffer中多了一个闲暇方位,为出产者开释一个资源
        ASSERT(ReleaseSemaphore(hProducerSemaphore, (long)1, NULL));
    }

    
return 0;
}

void ProduceAndConsume()
{
    
int        i;
    DWORD    dwThreadID;

    iProducerPointer 
= 0;
    iConsumerPointer 
= 0;

    hProducerSemaphore 
= CreateSemaphore(NULL, BUFFER_SIZE, BUFFER_SIZE, NULL);      //创立出产者信号量,初始有20个资源
    hConsumerSemaphore = CreateSemaphore(NULL, 0, BUFFER_SIZE, NULL);                //创立顾客信号量,初始有0个资源
    hConsumerMutex       = CreateMutex(NULL, FALSE, NULL);                           //创立顾客Mutex

    hProducerThread       
= CreateThread(NULL, 0, ProducerThread, NULL, 0&dwThreadID);
    
for (i=0; i<CONSUMER_COUNT; i++)
    {
        hConsumersThread[i] 
= CreateThread(NULL, 0, ConsumerThread, NULL, 0&dwThreadID);
    }
}

void EndProduceConsume()
{
    
int i;

    ASSERT(CloseHandle(hProducerSemaphore));
    ASSERT(CloseHandle(hConsumerSemaphore));
    ASSERT(CloseHandle(hConsumerMutex));
    ASSERT(CloseHandle(hProducerThread));
    
for (i=0; i<CONSUMER_COUNT; i++)
    {
        ASSERT(CloseHandle(hConsumersThread[i]));
    }
}



sin 2010-03-15 01:22 宣布谈论
]]>