Author Archives: verynix

Page 20 of 21« First...10...1718192021

感悟《数据结构与算法分析(C++描述)》中的一些超经典递归函数

在这里,我想感悟一下关于数据结构方面的经典著作《数据结构与算法分析(C++描述)》中的两个经典的递归函数。  

 

一、AVL树中的插入操作 

基本思想:由于AVL树是一种平衡树(每个节点的左右子树高度差不超过1),所以每进行一次插入操作,就有可能破坏AVL树的性质。当破坏性质之后就要进行相应的调整,调整的内容在这里我就不赘述了。

下面是作者:Mark Allen Weiss写的关于AVL树的插入函数: 

1.树节点的定义:

struct AVLNode
{
 T element;
 AVLNode* left; //左子树
 AVLNode* right; //右子树
 int height; //节点高度(节点的高度:节点的高度是指该节点到一片树叶的最长的路径长。)
 
 AVLNode(const T& eIn,AVLNode* lt = NULL,AVLNode* rt = NULL,int h = 0)
        :element(eIn),left(lt),right(rt),height(h) { }
};  

 

2.插入函数

/*x 是需要插入的数据项; t是子树的根;插入之后更新子树的根。*/
void insert(const T& x,AVLNode* & t)
{
     if(t == NULL)
        t = new AVLNode(x,NULL,NULL);//空节点
     else if(x < t -> element) //向左插入节点
     {
         insert(x,t -> left);

         if(height(t -> left) – height(t -> right) == 2) //如果破坏了AVL树的性质,进行相应调整
         {
              if(x < t -> left -> element)//向左儿子的左子树进行插入
                  rotateWithChild(t); //进行一次左单旋转
              else
                  doubleWithLeftChild(t);//进行一次左双旋转 
          }
     } 
     else if(x > t -> element) //向右插入节点
     {
          insert(x,t -> right);
         
          if(height(t -> right) – height(left) == 2) //破坏了AVL树性质
          {
              if(t -> right -> element < x) //向右儿子的右子树进行一次插入
                  rotateWithRightChild(t); //进行一次右单旋转
              else
                  doubleWithRightChild(t);//进行一次右双旋转 
          }
     }
     else //该树中已经存在该节点   
         ;      

    //更新节点高度 
     t -> height = max(height(t -> left),height(t -> right)) + 1;  

其他函数: 

(1)int max(int lhs,int rhs) //计算高度

{

     return lhs > rhs ?: rhs;

(2)int height(AVLNode* t) const //返回及节点的高度  

{

     return t == NULL ? -1:t -> height;

}   

(3)void rotateWithLeftChild(AVLNode* & k) //进行一次左单旋转

{

       AVLNode* k1 = k -> left;  

       k -> left = k1 -> right;

       k1 -> right = k;

       k -> height = max(height(k -> left),height(k -> right)) + 1;//更新根的高度   

       k1 -> height = max(height(k1 -> left),k2 -> height) + 1;//更新新根的高度

       k = k1; //新的根

(4)void doubleWithLeftChild(AVLNode* k) //进行左双旋转 

{

      rotateWithRightChild(k -> left);//先对左儿子进行一次右单旋转

      rotateWithLeftChild(k -> right);//再旋转根节点

}   

剩余的那两个旋转和这两个旋转函数是对称的,这里就不多说了。

 

请注意插入函数最后我弄成蓝色的那行代码。

     我们一般都会这么想:在插入之后判断是否还平衡,如果不平衡的话,我们就进行相应的调整。我们会编写这样的一个函数:

int calculateHeight(AVLNode* t)。 这个函数是递归的,递归的计算节点的高度。如果出现不平衡的情况,则进行相应的调整。可是,如果这样的话,就会增加一些递归的开销,实在没有必要。

     但是这个作者另辟蹊径,他不是编写递归函数,而是在递归的过程中完成,在弹栈的过程中完成了这个工作。在弹栈的过程中,首先判断在压栈的过程中经过的那些节点的左右子树的高度差,如果发现左右子树高度差超过了1,那么进行相应的调整;之后再更新节点的高度。

天才的作者,看来他对递归的过程了如指掌了:压栈,出栈~~在出栈的过程中更新节点的高度,好经典!!

 

二、左式堆的合并函数

思想:递归的合并小堆的右子堆和大堆。 以下是作者写的两个合并函数:

1.LeftistNode* merge(LefttistNode* h1,LeftistNode* h2) //合并两个子堆

{

    if(h1 == NULL)

        return h2;

    if(h2 == NULL)

        return h1;

    if(h1 -> element < h2 -> element)

        return merge1(h1,h2);//merge1函数假设第一个参数是小堆 

    else

        return merge1(h1,h2);

}      

2.//下面的这个函数假设第一个参数是小堆。

 LeftistNode* merge1(LeftistNode* h1,LeftistNode* h2)

{

      if(h1 -> left == NULL)

          h1 -> left = h2;//处理单个节点的情况,此时h1的右子树早已为空,为什么呢??呵呵~~  

      else

      {

          h1 -> right = merge(h1 -> right,h2);

          if(h1 -> left -> npl < h1 -> right -> npl)

               swapChildren(h1);//交换左右子树

        

       //风格的又一体现

         h1 -> npl = h1 -> right -> npl + 1;

       }

       return h1;

}   

说这本书是经典之作,一点都不夸张,代码写得好美!!他试图给我们养成一种思维习惯!!

家驹,beyond

   初识家驹,初识beyond,是在初二的时候。一次偶然的机会,我借了同学一盘Beyond的磁带回家听,当时听了几遍,觉得调子很好听,特别是《海阔天空》,《光辉岁月》,《真的爱你》。《海阔天空》给我一种很开阔的感觉;《光辉岁月》和《真的爱你》给我一种很轻快的感觉。

   一次在电视上看见有人点播beyond的《光辉岁月》和《岁月无声》。里面家驹赤膊的弹吉他的样子给我留下的印象好深刻,当时就感觉好亲切:自己喜欢的歌曲居然有人点播。感觉家驹弹吉他的样子真的好帅气,每一个动作透露出来的尽是一种自信,一种征服听众的感觉。我开始关注家驹,关注beyond,听不懂那些歌词我会想向邻居一位会粤语的哥们提问,终于,我慢慢的听懂了一些歌曲:《海阔天空》,《光辉岁月》~~

   终于,我再也不愿意把那盘磁带还给我同学,我用2块钱买下了那盒磁带。红色的色调,它静静地跟我度过了7个春秋,现在它依然完好地保存在我的盒子中。

   到了高中,很幸运,我遇到了一位也喜欢听beyond歌曲的老乡,他了解beyond的东西比我还多。我经常跟他聊beyond,想他学习一些关于beyond的知识,我也经常到新知图书城翻阅一些关于beyond的资料。

   一件小事,一些经历,一秒,一分,一年,足以改变一个人,更何况是三年。三年的高中改变了我,我开始变得成熟,我开始变得稳健,我开始变得自信,我开始变得开朗,我开始变得沉着。高一刚进宏志班的时候,我顿时感觉到我一无是处,我不断地提问自己:我的优越感哪去了?想当年我也是全校第一名,现在怎么会变成倒数了?我行吗??一遍一遍的提问始终找不到答案。

   我依然清晰地记得,高中的第一次期中考,我考了全班第26名(当时班里面有50名同学),全校几百名以后。理科给我的打击好大,我的数学没有及格,物理刚过六十分,化学差强人意。我顿时感觉压力从天而降:怎么这么多的强人?他们真的好难被打败。

   我需要发泄,发泄心中的不满,发泄心中的怨气,发泄心中的不平衡。我开始学会写信,写信给初中同学,写信给小学同学,告诉他们我们这个班竞争压力很大,自己很受委屈;他们当然会一如既往的鼓励我。但是他们毕竟在远方啊,怎么可能随时听我心中的那份苦楚呢?于是,这个时候,我总是会情不自禁的想起那盒红色的磁带:beyond《光辉岁月》。每次晚上睡觉之前,我总是习惯性地把那盒磁带放进我的复读机,一遍又一遍地听。

   高三这年是我心事最多的一年:家,分数,奖学金考试,英才班,年级排名~~每周一次的小测验,每月一次的月考,每三月一次的省统考,我无不为这些考试绞尽脑汁。我会为我的马虎而自责,我会为我的物理而无奈,我会期待我的数学出现奇迹,我会烦英语。每一次考试之前我都会对自己说:下次要考好。但是我还是会紧张,因为我自卑。这个时候,又是那盒《光辉岁月》救了我。每一次考试之前,我都会重复地播放《不再犹豫》,因为那样,我会获得无穷的动力,我会自信。但是面对分数,我更多的是无奈。晚上我会一个人到楼下的树林下一个散步,一个人静静的想,期待早些下课,因为我要回宿舍,我要听歌,我要听beyond的歌曲。

   高三的时候,我多了一个习惯:睡觉之间听那盒磁带,静静地听。

 

听《光辉岁月》: 

   听家驹对黑人领袖曼德拉总统的赞美。每个人心中都有这样或者那样的偶像和喜欢的人,从他的歌声中,我知道,我应该学习他们的哪些方面,那激昂的调子会让我兴奋得睡不着觉;我会联想他弹吉他的样子,他身上透露出的那种自信试图征服现场的每一位观众,包括钟一钧,他的忠实听众。每次我总是情不自禁的哼那段哨子,心情顿时开阔不少;而他那经典的“我爱你”手势,早已铭记在我的心田。

 

听《不再犹豫》:

   高中每次考试之前,我总是习惯性的听《不再犹豫》。“达到理想不太易”,我理解,要实现心中的理想真的不太容易,幸亏有beyond,有家驹,我不然我总是以为随便随便就可以成功,天上总是会掉馅饼,总是想不劳而获。

   于是,我不再急躁,一步一步地提高,慢慢地做好每一步:数学不好,我可以做好多的题目,终于,我也可以考上120分;英语不好,我可以背单词,我可以读英语,我可以做完型填空,呵呵,原来我也可以考及格的。

 

 

听《海阔天空》:

   我会为家驹身上那种开阔的胸襟所折服,我会为2003年北京beyond的那份不放弃的精神而感动得泪水直流。如果说家驹在《海阔天空》中说“跌倒了不要紧”,那么2003年的beyond已经是一种升华:家驹走了,他们还能走下去吗?

   很多家驹迷一直被这个问题所困扰;但是这次他们证明了,他们行,虽然家驹走了,但是他们还要开演唱会,开世界巡回演唱会,以此来实现家驹心中的那个未实现的梦想。 我呢?告诉自己说:再来一次。

 

 

听《午夜怨曲》:

  当初,家驹帮别人弹吉他,但是家驹很不小心,把别人的吉他弦给拨断了,那人对家驹说:你永远也不会弹吉他。可是,家驹真的不服气,因为他从来都是那么好胜,他鄙视那些看不起他的人。于是,他不断地练习,直到手指都夹出血为止。正如这首歌里面所写的那样:“再次听到昨日的冷嘲”,“冷笑变作故事的作者”,他总是那么上进,或许,我这方面性格或多或少受这首歌曲的影响。 

 

听《再见理想》:

 

   在唱这首歌之前,他讲了这么一些话:“我们Beyond在这几年间经历了很多东西~~从我们没有机会直至有机会,一路在改变,我们有开心有不开心,但是都不要紧,我们Beyond会永远夹Band夹到我们的手指不会弹为止,坚持我们乐队之前的信念,希望大家的想法跟我们的一样。一首很旧很旧的歌,这首歌讲出了我们在早期时间一些玩音乐的感觉~~一种孤独与落寞的感觉。” 

创办这个乐队的辛酸和落寞都写在这首歌曲里面了,大家都说:一些事情只有自己经历过了才知道。真的,那种孤独和落寞只有beyond才能体会得到:“独坐在路边街头,冷风吹醒,慢慢地伴着我的孤影”,“只想将吉他紧抱,诉出辛酸”。

 

 

听《谁伴我闯荡》:

   每次我听这首歌曲,我的眼里总是擒满了泪水,好想哭。前奏把内心的那种孤独感和落寞感表达得淋漓尽致。

   每次我感到孤独,寂寞和浮躁的时候,我总是要听这首歌。大一的时候,虽然目标很明确:编程.但是累的时候总是会很浮躁,很不自信:我这样能找到工作吗?我这样会不会变成一个孤僻的一个人?我会不会找不到老婆?我的视力会不会急剧下降?这样努力,我为的是什么?我值得这样做吗?

   带着一系列的问题,我只能在这首歌中找到答案。原来家驹也跟我一样有这样的感觉:“前路是哪方?谁伴我闯荡?”,“沿路没有指引,若我走上又是狭巷。”。但是他终于还是想通了:“只有淡忘”,“只有顽强”。

   听歌的时候,我总是联想,联想到那些在冰天雪地里面卖冰糖葫芦的人;联想到我家乡那些“脸朝黄土背朝天”的亲戚们;联想到那些吃了上顿没下顿的人们~~~于是,我对自己说:如果你都这样了想了,他们呢?

   我终于想通了,我不累,我是在为以后的生活奋斗啊,“只有淡忘”,“只有顽强”。

 

 

听《真的爱你》:

   我知道,我要理解母亲的一言一行;我要做个孝顺的孩子,不让母亲受苦受累;我要学会珍惜。

 

   家驹之于我,beyond之于我,已经是一种精神象征,我的生活中不可能少了家驹和beyond的歌声,即使在未来。

以前我不相信很多事情,但现在相信了

     又到了周六晚上,我还是想往常一样,坐在计算机大楼的某个座位上静静地听师兄们发表技术之道。我总是很愿意和那些比我年长的人聊天,因为他们在我的心目中总是那么的博学,那么的有才,那么的深邃,我总是希望在他们的话语中悟出一些东西~~~
     今天晚上又到梁师兄给我们讲专题了:走近百度。
     百度是自己心仪的公司之一,之前总觉得那里离自己很远,很远~~~今天师兄的一个讲座,让我感觉百度
就在自己的身边,感觉好近~~那一个个视频都是一种震撼,一张张图片都是那么的诱人:  理想国际大厦,普天大厦,第三极大厦,上地大厦~~~  

下面是那震撼人心的视频:

        

     

     大一的时候不相信能和百度走得这么近;听了师兄今晚的讲座后才知道,这是真的。

 

    以前不相信很多东西,现在相信了~~~

     没读书的时候,不相信自己家里能有一台电视机。当时家里没有,我和我弟弟就经常跑到隔壁家去看电视,有时候我们被他们轰在门外,不能进去他们家,他们说我们身上脏;我和弟弟很委屈,跑到家里跟妈妈说:妈妈,他们嫌我们脏,不让我们进去他们家里看电视~~妈妈安慰我们说:儿子,没事,以后咱们家有钱了再买。虽然当时我们不信,心想:我们家这么穷,什么时候能买~~但是当时还是很欣慰,很期待的,现在依然还很怀念那种感觉。高二的时候家里终于买电视了,那是占用农田的补贴。终于相信家里能有电视了。  

     没有读书的时候,很羡慕电视上的那些明星,不相信有那么一天,自己能亲眼见到或者接触到那些明星。大一的时候,迪克牛仔来到我们体育馆唱了几首歌曲,当时把我兴奋的,疯狂地转发了好几十条短信;前不久,心目中的神:科比,也在中国弄了一个青葱计划,准备在中国招收徒弟(呵呵,我很想去),原来 ,我也可以有机会亲眼见到心目中的偶像;看完春晚之后,不相信有那么一天,自己也可以有机会亲眼见到小沈阳,但是前不久去他博客瞎逛的时候,我相信了。现在相信了,原来他们都没有住在天上。

      上幼儿园的时候,不相信家里能有一辆轿车来接我回家,现在相信了,以后会有的。

      上小学的时候,不相信每天早上都有1块钱买早餐;高一的时候相信了,原来每天早上真的可以有1块钱买两个包子,甚至高兴的时候,可以再买一杯豆浆和一个鸡蛋。  

      上小学的时候,不相信有一天,自己的手里能撰着红红的一张钞票;初二有一次,在自己家的附近捡到了两百块钱,当时心脏差点吓掉到地上,接着我一个很要好的同学挥霍了;从那时起,开始相信了,原来自己也可以有100块钱。 

       小学毕业的时候,自己考了全班的前列,不相信自己居然进了全县口碑最差的初中;但是,当我只收到那个中学的录取通知书时,我相信了。   

      小学,我不相信很多事情~~~初中依然不相信很多事情~~~ 

      初一的时候,不相信自己第一学期考了全校第一,轰动了整个校园,身边的人不安了:看,那个小孩居然是全校第一;拿到奖学金时,我相信了。

        初二的时候,不相信自己会写了平生的第一封情书给自己暗恋一年多的小学同桌;但是,当把情书递给我的一个好友转交给她时,我相信了。  

      初二的时候,在追她的某一天,不相信她会在我面前把我写给她的情书撕了;呵呵,当时我反应过来的时候,我相信了。

     初二的时候,不相信还会和自己追过的那个女生成为好朋友;在高一我们通了第一封信件的时候,我相信了。   

      初二当自己迷上网络游戏《传奇》的时候,不相信有那么的一天,会有自己的一台电脑;2008年四月份配了台式机之后,我相信了。 

      初三毕业的时候,不相信自己能到外地去读书;当踏进昭通市一中时,自己相信了。 

      高中的时候,依然不相信很多事情~~~~ 

      高一的时候,不相信,当年第一名的我,来到高中以后竟然变得什么也不是;第一次期中考考了全年级几百名之后,相信了,原来,比我厉害的人那么多,我不再那么骄傲;现在想来,也未必是件坏事。

      高一的时候,不相信自己能考到全班的前10名;高考之后相信了,原来,我可以考进前10名的。  

      高二的时候,不相信自己有一天能那么自如的在篮球场上运球;现在相信了。

      刚进大一的时候,我都不知道“下载”是个什么概念,相当羡慕会重装系统的同学;但现在相信了,原来我也可以懂这些东西~~

       以前,不相信自己会拥有很多东西,现在我相信会有的,至少在将来的某一天。

      从现在开始,我要相信很多事情,没错的。
 

 

Gentoo下面从kde3.5升级到kde4.2的经历

 一.首先是安装不上amarok2 

 安装完Gentoo基本系统、kde桌面以后,一款电影播放器和音乐播放器自然是少不了啦。早就听说amarok的大名, 于是就找个机会下载amarok.   (1)emerge -av amarok          接着我一直在那里等,不幸的事情发生了:amarok中的某些包被我系统中的kdebase-startkde和x11-server这两个包block了,当时第一反应就google。         

 后来找到了Gentoo关于portage的官方文档,找到了解决办法:把系统中block的那些包都删除了。但是仔细想想,不对劲啊,那可是kdebase和x11的包啊,不能删除。  但是当时特别的想下载amarok,也没有管那么多,心中还是有些侥幸吧:反正出问题之后还可以安装。终于狠下心把这两个包都删除了。结果出问题了:打开不了home folder和system,我知道出问题了。终于退出桌面,回到基本系统:黑屏幕。我先删除kde3.5和xorg-x11,但是要命的是,在安装显卡驱动时又出错了,当时冒出的一大堆错误我也看不懂,好在之前安装Gentoo基本系统的时候训练好了心态,要不然我又得哭上一场;不想再去google了,于是又做出了如下决定:格式化整个盘,在重新安装Gentoo,这样也省事,要不然等我找到那个错误的话,我已经有60多岁了,呵呵~~   不出意料,安装过程挺顺利的,不过为了保险,还是安装了kde3.5。用了一阵子之后更新系统,但是,又出问题了,我的kdebase-startkde-3.5.10又block了一些包,我当时狂晕,又google,还发邮件给我的师兄,他们的回答出奇的一致:把kde3.5删了,当时把我郁闷的,我终于痛下决心,一定要把kde4.2.1安装到我的电脑上~~~很大的一个原因在下面:             

二.无法安装上sandbox  

第二次安装上kde3.5之后,更新系统,但是安装不了sandbox,冒出很多的错误信息,最后的一行引起了我的注意: FEATURES=”-sandbox” emerge sandbox ,又按照提示重新:emerge  FEATURES=”-sandbox” emerge sandbox,但是不管用,还是出那个错误。我又郁闷了,问题出在那里了???我一直在问,但是终究还是没有结果,最后不得不google,终于找到了解决办法:原来是内核编译是没有打开模拟32位程序运行的选项,打开即可。内核选项如下:    Executable file formats / Emulations      [*] IA32 Emulation    [*] IA32 a.out support  

 这是原文地址: http://justice666.blog.ccidnet.com/blog-htm-do-showone-type-blog-itemid-230384-uid-68180.html     

很感谢这篇文章。我弄明白了,原来是和cpu的位数有关系,于是我又赶紧(1)cd /usr/src/linux;(2)make menuconfig; 按照上面所说的一步一步配置内核。 更糟糕的事情发生了,我的内核选项里面竟然没有 [*] IA32 Emulation        [*] IA32 a.out support      这两项,我当时无语~~~当时几乎又放弃了,但是想想,如果放弃的话,之前的努力不都是白费了吗??安慰了自己之后又开始自己的google之路,我在搜索框中试着输入:

IA32 Emulation。我在google中找到了下面关于AMD64常见问题的帖子:http://www.gentoo.org/doc/zh_cn/gentoo-amd64-faq.xml                我当时吓坏了:我的CPU是AMD64的,但是刚开始我一直按照x86手册安装Gentoo;心情很复杂:该高兴吧,因为自己犯了一个超级严重的错误,在这个偶然的机会被发现了;该难过吧,因为又得重新把系统格式化了,重新安装~~~我从安装Gentoo基本文件那里重新安装,最后还是没有成功,到了chroot那步出了这样的问题:

chroot :cannot run command bin bash’ exec format error。      又google,找到了一篇对我很重要的文章:http://www.gentoo-wiki.info/Chroot_from_a_livecd 就是这段文字救了我:

 Troubleshooting Exec format error If the chroot command returns with the error “chroot: cannot run command `/bin/bash': Exec format error“, this usually indicates that the livecd environment is not compatible with that of the installed system.For example, the error is most frequently seen when trying to chroot to a 64-bit system (eg. amd64) from a 32-bit livecd (eg. x86).The solution is to use a livecd which is using the same architecture as the installed system.  

 我恍然大悟,原来我刻录的盘和我的cpu架构不一样~~我乐坏了,我又迫不及待地下载:install-amd64-minimal-2008.0-r1.iso刻了盘,重新踏上安装Gentoo之路,终于顺利安装完Gentoo基本系统,而且这个选项也有:Executable file formats / Emulation  [*] IA32 Emulation              [*] IA32 a.out support       接下来的重头戏当然是安装kde4,在网上搜了很多的帖子,也吸取了很多的教训,“天道酬勤”,老天爷终于还是很眷顾我,顺利完成了kde4的安装。 一个字:高兴、快乐。     

三.总结一下我成功安装kde4的经验以及一些好的帖子      

  (1)安装好gentoo基本系统之后,先安装nvidia-drivers,然后在安装xorg-x11,官方文档上有;

(2)添加gentoo-overlay-china(参看下面的帖子):

  http://www.linuxsir.org/bbs/thread272832.html 

(3)在/etc/portage下面新建:package.keywords文件,在里面输入以下内容(直接点击链接):package.keywords     (我在2009年4月7日添加的,可能以后有更新,版本:kde4.2)  

这些东西在Gentoo kde4的官方指南上找的,大家可以参考一下,下面的地址是Gentoo kde4官方指南: 

http://www.gentoo.org/proj/en/desktop/kde/kde4-guide.xml   

呵呵,英文的,当时我要是看懂我就已经安装成功了。(PS:但是主要是没有看懂其中的sets那部分东西,现在想来还真的很后悔,因为只不过就是添加几个sets而已。);

(4)添加kde overlay:    #layman -a kde    (以root用户运行)  ;

(5)下载桌面:  #emerge -pv kdebase-startkde  ;   把列出来的USE标记都写好,然后去掉-pv:emerge kdebase-startkde ,你就可以安装kde基本环境了; 如果你想安装kde完整的环境(更多的应用程序),你应该:emerge kde-meta    .至此,期待已久的kde4终于安装成功了~~

大家如果还有什么问题的话可以给我发邮件:zhongyijun48729730@gmail.com 

下面是kde4.2的两个截图: 

          

 

kde4.2 package.keywords

app-arch/libarchive
app-misc/strigi
app-office/akonadi-server
app-text/ebook-tools
dev-cpp/eigen:2
>=dev-libs/libical-0.33-r1
dev-libs/libzip
dev-libs/soprano
>=dev-util/cmake-2.6.2
>=kde-base/qimageblitz-0.0.4
media-sound/phonon
>=sci-mathematics/gmm-3.0
>=x11-apps/xinit-1.0.5-r2

kde-base/akonadi:4.2
kde-base/akregator:4.2
kde-base/amor:4.2
kde-base/ark:4.2
kde-base/automoc
kde-base/blinken:4.2
kde-base/bomber:4.2
kde-base/bovo:4.2
kde-base/cervisia:4.2
kde-base/dolphin:4.2
kde-base/dragonplayer:4.2
kde-base/drkonqi:4.2
kde-base/gwenview:4.2
kde-base/juk:4.2
kde-base/kaddressbook:4.2
kde-base/kalarm:4.2
kde-base/kalgebra:4.2
kde-base/kalzium:4.2
kde-base/kamera:4.2
kde-base/kanagram:4.2
kde-base/kapman:4.2
kde-base/kappfinder:4.2
kde-base/kapptemplate:4.2
kde-base/kate:4.2
kde-base/katomic:4.2
kde-base/kbattleship:4.2
kde-base/kblackbox:4.2
kde-base/kblocks:4.2
kde-base/kbounce:4.2
kde-base/kbreakout:4.2
kde-base/kbruch:4.2
kde-base/kbugbuster:4.2
kde-base/kcachegrind:4.2
kde-base/kcalc:4.2
kde-base/kcharselect:4.2
kde-base/kcheckpass:4.2
kde-base/kcminit:4.2
kde-base/kcmshell:4.2
kde-base/kcolorchooser:4.2
kde-base/kcontrol:4.2
kde-base/kcron:4.2
kde-base/kdeaccessibility-colorschemes:4.2
kde-base/kdeaccessibility-iconthemes:4.2
kde-base/kdeaccounts-plugin:4.2
kde-base/kdeartwork-colorschemes:4.2
kde-base/kdeartwork-desktopthemes:4.2
kde-base/kdeartwork-emoticons:4.2
kde-base/kdeartwork-iconthemes:4.2
kde-base/kdeartwork-iconthemes:4.2
kde-base/kdeartwork-kscreensaver:4.2
kde-base/kdeartwork-sounds:4.2
kde-base/kdeartwork-styles:4.2
kde-base/kdeartwork-wallpapers:4.2
kde-base/kdebase-cursors:4.2
kde-base/kdebase-data:4.2
kde-base/kdebase-desktoptheme:4.2
kde-base/kdebase-kioslaves:4.2
kde-base/kdebase-startkde:4.2
kde-base/kdebugdialog:4.2
kde-base/kdedglobalaccel:4.2
kde-base/kdegraphics-strigi-analyzer:4.2
kde-base/kde-l10n:4.2
kde-base/kdelibs:4.2
kde-base/kdemaildir:4.2
kde-base/kde-menu:4.2
kde-base/kde-menu-icons:4.2
kde-base/kdemultimedia-kioslaves:4.2
kde-base/kdenetwork-filesharing:4.2
kde-base/kdepasswd:4.2
kde-base/kdepim-icons:4.2
kde-base/kdepim-kresources:4.2
kde-base/kdepimlibs:4.2
kde-base/kdepim-strigi-analyzer:4.2
kde-base/kdepim-wizards:4.2
kde-base/kdeplasma-addons:4.2
kde-base/kdesdk-kioslaves:4.2
kde-base/kdesdk-misc:4.2
kde-base/kdesdk-scripts:4.2
kde-base/kdesdk-strigi-analyzer:4.2
kde-base/kdessh:4.2
kde-base/kdesu:4.2
kde-base/kde-wallpapers:4.2
kde-base/kdf:4.2
kde-base/kdialog:4.2
kde-base/kdiamond:4.2
kde-base/kdm:4.2
kde-base/kdnssd:4.2
kde-base/kdnssd:4.2
kde-base/keditbookmarks:4.2
kde-base/kephal:4.2
kde-base/kfile:4.2
kde-base/kfilereplace:4.2
kde-base/kfind:4.2
kde-base/kfloppy:4.2
kde-base/kfourinline:4.2
kde-base/kgamma:4.2
kde-base/kgeography:4.2
kde-base/kget:4.2
kde-base/kgoldrunner:4.2
kde-base/kgpg:4.2
kde-base/khangman:4.2
kde-base/khelpcenter:4.2
kde-base/khotkeys:4.2
kde-base/kiconfinder:4.2
kde-base/kig:4.2
kde-base/killbots:4.2
kde-base/kimagemapeditor:4.2
kde-base/kinfocenter:4.2
kde-base/kioclient:4.2
kde-base/kiriki:4.2
kde-base/kiten:4.2
kde-base/kjots:4.2
kde-base/kjumpingcube:4.2
kde-base/kleopatra:4.2
kde-base/klettres:4.2
kde-base/klines:4.2
kde-base/klinkstatus:4.2
kde-base/klipper:4.2
kde-base/kmag:4.2
kde-base/kmahjongg:4.2
kde-base/kmail:4.2
kde-base/kmailcvt:4.2
kde-base/kmenuedit:4.2
kde-base/kmimetypefinder:4.2
kde-base/kmines:4.2
kde-base/kmix:4.2
kde-base/kmousetool:4.2
kde-base/kmouth:4.2
kde-base/kmplot:4.2
kde-base/knetattach:4.2
kde-base/knetwalk:4.2
kde-base/knetworkconf:4.2
kde-base/knewstuff:4.2
kde-base/knode:4.2
kde-base/knotes:4.2
kde-base/knotify:4.2
kde-base/kode:4.2
kde-base/kolf:4.2
kde-base/kollision:4.2
kde-base/kolourpaint:4.2
kde-base/kommander:4.2
kde-base/kompare:4.2
kde-base/konqueror:4.2
kde-base/konquest:4.2
kde-base/konsole:4.2
kde-base/kontact:4.2
kde-base/kontactinterfaces:4.2
kde-base/kontact-specialdates:4.2
kde-base/kopete:4.2
kde-base/korganizer:4.2
kde-base/kpasswdserver:4.2
kde-base/kpat:4.2
kde-base/kpilot:4.2
kde-base/kppp:4.2
kde-base/kquitapp:4.2
kde-base/krdc:4.2
kde-base/kreadconfig:4.2
kde-base/kreversi:4.2
kde-base/krfb:4.2
kde-base/krosspython:4.2
kde-base/krossruby:4.2
kde-base/kruler:4.2
kde-base/krunner:4.2
kde-base/ksame:4.2
kde-base/ksaneplugin:4.2
kde-base/kscd:4.2
kde-base/kscreensaver:4.2
kde-base/kshisen:4.2
kde-base/ksirk:4.2
kde-base/ksmserver:4.2
kde-base/ksnapshot:4.2
kde-base/kspaceduel:4.2
kde-base/ksplash:4.2
kde-base/ksquares:4.2
kde-base/kstars:4.2
kde-base/kstart:4.2
kde-base/kstartperf:4.2
kde-base/kstartupconfig:4.2
kde-base/kstyles:4.2
kde-base/ksudoku:4.2
kde-base/ksudoku:4.2
kde-base/ksysguard:4.2
kde-base/ksystemlog:4.2
kde-base/ksystraycmd:4.2
kde-base/kteatime:4.2
kde-base/ktimer:4.2
kde-base/ktimetracker:4.2
kde-base/ktimezoned:4.2
kde-base/ktouch:4.2
kde-base/ktraderclient:4.2
kde-base/kttsd:4.2
kde-base/ktuberling:4.2
kde-base/kturtle:4.2
kde-base/ktux:4.2
kde-base/kubrick:4.2
kde-base/kuiserver:4.2
kde-base/kuiviewer:4.2
kde-base/kurifilter-plugins:4.2
kde-base/kuser:4.2
kde-base/kwallet:4.2
kde-base/kwalletd:4.2
kde-base/kweather:4.2
kde-base/kwin:4.2
kde-base/kwordquiz:4.2
kde-base/kwrite:4.2
kde-base/kwrited:4.2
kde-base/kxsldbg:4.2
kde-base/libkcddb:4.2
kde-base/libkcompactdisc:4.2
kde-base/libkdcraw:4.2
kde-base/libkdeedu:4.2
kde-base/libkdegames:4.2
kde-base/libkdepim:4.2
kde-base/libkexiv2:4.2
kde-base/libkholidays:4.2
kde-base/libkipi:4.2
kde-base/libkleo:4.2
kde-base/libkmahjongg:4.2
kde-base/libkonq:4.2
kde-base/libkpgp:4.2
kde-base/libksane:4.2
kde-base/libksieve:4.2
kde-base/libkworkspace:4.2
kde-base/libplasmaclock:4.2
kde-base/libtaskmanager:4.2
kde-base/lilo-config:4.2
kde-base/lokalize:4.2
kde-base/lskat:4.2
kde-base/marble:4.2
kde-base/mimelib:4.2
kde-base/nepomuk:4.2
kde-base/nsplugins:4.2
kde-base/okteta:4.2
kde-base/okular:4.2
kde-base/parley:4.2
kde-base/phonon-kde:4.2
kde-base/plasma-apps:4.2
kde-base/plasma-workspace:4.2
kde-base/powerdevil:4.2
kde-base/printer-applet:4.2
kde-base/pykde4:4.2
kde-base/renamedlg-plugins:4.2
kde-base/solid:4.2
kde-base/solid-hardware:4.2
kde-base/soliduiserver:4.2
kde-base/step:4.2
kde-base/superkaramba:4.2
kde-base/svgpart:4.2
kde-base/sweeper:4.2
kde-base/system-config-printer-kde:4.2
kde-base/systemsettings:4.2
kde-base/umbrello:4.2

# meta ebuilds
kde-base/kdeaccessibility-meta:4.2
kde-base/kdeadmin-meta:4.2
kde-base/kdeartwork-meta:4.2
kde-base/kdebase-meta:4.2
kde-base/kdeedu-meta:4.2
kde-base/kdegames-meta:4.2
kde-base/kdegraphics-meta:4.2
kde-base/kde-meta:4.2
kde-base/kdemultimedia-meta:4.2
kde-base/kdenetwork-meta:4.2
kde-base/kdepim-meta:4.2
kde-base/kdesdk-meta:4.2
kde-base/kdetoys-meta:4.2
kde-base/kdeutils-meta:4.2

搞定断错误(Segmentation faults)和两次释放内存的问题

我满怀信心的编写了链表函数,结果运行时得到了两个错误:

1.段错误(Segmentation faults)

  我当时编写了一个链表的排序函数如下:

  void Linkedlist::sort()
    //to sort the list
     {
          int data = 0;
   
          Node* p1 = head;
         Node* p2 = head;
   
         if(head != NULL)
          {
          //selection sort
           while(p2 -> next != NULL)
           {
             while(p1 != NULL)  
             {
              p1 = p1 -> next; //move p1 to next node  (问题就出现在这里,因为p1 -> next 可能是NULL
   
             //exchange two node’s data
               if(p1 -> data <= p2 -> data)
               {
                 data = p1 -> data;
                 p1 -> data = p2 -> data; 

                  p2 -> data = data;
             }
             }
   
             p2 = p2 -> next; //move p2 to the next node
             p1 = p2;
            }
          }
     }


当时我去google了一下,找到了很多的帖子,总结起来有一下的几个原因:

1。 针没有赋值;
2。 量赋值类型有错误。

3。数组越界也能产生断错误;

4。 最主要的错误就是声明了指针,但是没有初始化 ,结果再后来的时候进行间接引用 ,就出现问题了。


又找到了一个很好的英文网址:

http://en.wikipedia.org/wiki/Segmentation_fault   


我也感觉到我很大一部分原因出现在指针的操作上了,但是一直没有看出来,后来就不得不上csdn,终于在那些大牛人的帮助下搞定了,超级感谢他们。     

2.两次释放内存,出现:double free or corruption (fasttop): 0x0890e008   

*** glibc detected *** ./l1: double free or corruption (fasttop): 0x0890e008 ***
======= Backtrace: =========
/lib/libc.so.6[0xb7d0ba00]
/lib/libc.so.6(cfree+0x89)[0xb7d0d6f9]
/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6(_ZdlPv+0x21)[0xb7ebc1a1]
./l1(__gxx_personality_v0+0x279)[0x8048a01]
./l1(__gxx_personality_v0+0x29d)[0x8048a25]
./l1[0x8048e60]
/lib/libc.so.6(__libc_start_main+0xdc)[0xb7cbbfdc]
./l1(__gxx_personality_v0+0x59)[0x80487e1]

======= Memory map: ========
08048000-0804a000 r-xp 00000000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0804a000-0804b000 r–p 00001000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0804b000-0804c000 rw-p 00002000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0890e000-0892f000 rw-p 0890e000 00:00 0          [heap]
b7b00000-b7b21000 rw-p b7b00000 00:00 0
b7b21000-b7c00000 —p b7b21000 00:00 0
b7ca5000-b7ca6000 rw-p b7ca5000 00:00 0
b7ca6000-b7dd0000 r-xp 00000000 08:03 2932840    /lib/libc-2.6.1.so
b7dd0000-b7dd2000 r–p 0012a000 08:03 2932840    /lib/libc-2.6.1.so
b7dd2000-b7dd3000 rw-p 0012c000 08:03 2932840    /lib/libc-2.6.1.so
b7dd3000-b7dd6000 rw-p b7dd3000 00:00 0
b7dd6000-b7de0000 r-xp 00000000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de0000-b7de1000 r–p 00009000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de1000-b7de2000 rw-p 0000a000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de2000-b7e06000 r-xp 00000000 08:03 2932821    /lib/libm-2.6.1.so
b7e06000-b7e07000 r–p 00023000 08:03 2932821    /lib/libm-2.6.1.so
b7e07000-b7e08000 rw-p 00024000 08:03 2932821    /lib/libm-2.6.1.so
b7e08000-b7ee6000 r-xp 00000000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7ee6000-b7eea000 r–p 000dd000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7eea000-b7eeb000 rw-p 000e1000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7eeb000-b7ef2000 rw-p b7eeb000 00:00 0
b7eff000-b7f01000 rw-p b7eff000 00:00 0
b7f01000-b7f02000 r-xp b7f01000 00:00 0          [vdso]
b7f02000-b7f1c000 r-xp 00000000 08:03 2932839    /lib/ld-2.6.1.so
b7f1c000-b7f1d000 r–p 00019000 08:03 2932839    /lib/ld-2.6.1.so
b7f1d000-b7f1e000 rw-p 0001a000 08:03 2932839    /lib/ld-2.6.1.so
bfd08000-bfd1d000 rw-p bffeb000 00:00 0          [stack]
已放弃

又查了很多的帖子,调试了好几次程序,但是弄错了方向,我还以为是我的creat函数出错呢,还是没有找出来,不得不再次上csdn,在几个人的提醒下终于发现自己的析构函数有问题了,果真是释放了好几次内存: 

Linkedlist::~Linkedlist()
{
    deleteL();

void Linkedlist::deleteL()
//delete the linkedlist 
{
    Node* p1 = head;
    Node* p2 = head;

    if(head != NULL)
    {
        while(p1 != NULL)
        {
            p1 = p1 -> next; //move p1 to the next node 
            delete p2; //delete the previous node       (这里出现问题,因为p2没有继续移动) 
        }  
        head = NULL;
    }
}

哎,终于搞定了,学了不少,既学会了使用gdb,又长了见识~~


Page 20 of 21« First...10...1718192021