Monthly Archives: July 2009

HP笔记本:调制解调器驱动和电池驱动安装

重装系统不麻烦,麻烦的是装驱动。。。。。。

我的天,今天我总算深深地理解了,系统装驱动真的好麻烦。。。。。。

这个事情的来源是帮一个朋友装XP系统。装系统很简单,也就几分钟的事情,但是驱动很是让人头痛。 当然了,很大一部分原因是笔记本的,其中又是因为笔记本太娇贵了。我无语。。。。。

说Vista不好用,确实不好用:占太多系统资源,一些软件无法运行在Vista上,速度慢得要命。。。。。。这不,我干脆跟我朋友说了:把你的硬盘给格式化了,然后装一个XP。装之前还是把该备份的东西都备份好了,特别是驱动,我用了驱动人生。不出意外,几分钟就搞定了,我又不慌不忙,用驱动人生和驱动精灵把驱动都更新了,但是有两个东西怎么更新都安装不上:High Definition Audio总线上的调制解调器设备和microsoft ACPI-Compliant System。

怎么装都装不上,哎哟,我的天,我都无语了,我还以为,从此有了驱动人生和驱动精灵,驱动的问题就不是问题了,

不得不Google,果然,天道酬勤,算是找到解决办法了。

 

1.High Definition Audio总线上的调制解调器设备

这个东西用驱动人生搜索不到HP笔记本上的驱动,而驱动精灵搜索到的只是ThinkPad的驱动,你只需要下载下面这个驱动安装就可以解决问题了:

ftp://ftp.hp.com/pub/softpaq/sp37501-38000/sp37817.exe

 

 

2.microsoft ACPI-Compliant System

安装以上的那个驱动之后,还没有完事,还有一个硬件没有装上,查看了一下设备管理器,出现一个未知设备:

 

 

我看了一下设备属性,又google,好像那个设备和电池有关,解决办法如下:

1、右键单击“我的电脑”→“属性”→找到“硬件”选项卡→“设备管理器”;

2、在那个黄色的“未知设备”上右键单击,→“属性”→“更新驱动程序”→“从列表或指定位置安装(高级)”→“不要搜索,我要自己选择要安装的驱动程序”→“电池”→之后,蹦出警告,不理睬它→“APC UPS”,之后点击确定就可以了。

 

我的足迹:


感谢参加CityWalker活动,点击查看您的轨迹!

从AVL树和红黑树窥探树的节点设计

在这里,我想通过<数据结构与算法分析>中对AVL树的和<算法导论>中对红黑树的分析谈谈自己对树的节点中指针的设计方案的一点感悟.

今天晚上按照惯例,我又翻开了那本经典得不能再经典的<算法导论>,研究的是红黑树的一些基本操作:插入节点,旋转,删除节点.

看了将近半个小时的”左旋转”算法,一直没有看懂,郁闷了……不过,自己还是克服了心理障碍,又重新仔细地看了一遍那个算法的伪代码,终于弄懂了,原来自己没有弄懂代码中的那些父亲节点的变化问题.

我陷入了沉思,仔细地琢磨着:为什么这本书上的节点要这样设计?Why?

我想到了<数据结构与算法分析>中关于AVL树节点的插入问题.

1.节点的类:

struct AVLNode

{

      T* element;

      AVLNode* left; //左子树

      AVLNode* right; //右子树

      int height; // 高度

      AVLNode(const T& theElement,AVLNode* lt,AVLNode* rt,int h = 0)

              :element(theElement),left(lt),right(rt),height(h) {}

};

2.函数:        

/* x is the item to insert.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.*/
void insert(const T& x,AVLNode* & t)
{
     if(t == NULL) //如果子树为空
        t = new AVLNode(x,NULL,NULL); //申请新的节点 
     else if(x < t -> element) //如果x小于t中的元素
     {
         insert(x,t ->left); //往左插入 

         if(height(t -> left) – height(t -> right) == 2) //如果违反了AVL树的性质 
         { 
              if(x < t -> left -> element) //进行一次左旋转
                  rotateWithLeftChild(t);
              else
                  doubleWithLeftChild(t); //先进行一次左旋转,再进行一次右旋转
      }
      else if(x > t -> element)
      {
          insert((x,t -> right));  //想右插入

          if(height(t -> right) – height(t -> left) == 2) //违反了AVL树的性质 
              rotateWithRightChild(t); //进行一次右旋转
          else
              doubleWithRightChild(t); //先进行一次右旋转,再进行一次左旋转
     }
     else //元素重复
        ; 

     

t -> height  = max(height(t -> left),height(t -> right)) + 1; //更新t中的高度
     } 
}    
    

刚开始看最后那行代码的时候,我相当地困惑,根本看不懂.主要的问题是没有理解什么时候更新路过的那些节点的高度.

于是,我又不得不请教王师兄,他也仔细地跟我讲了两遍,然后在工作室的讨论班上他又认真研究了一番.但是,我依然模糊中……我当然不服啊,于是,又硬着头皮用gdb调试了好几遍……皇天不负有心人,终于,我弄明白了最后那行代码的意思了,进而,这个子程序我也差不多弄懂了:原来,在递归的过程中,节点经过的路径上的那些节点都被压入栈里面了;当节点被插入以后,出栈,在出栈的过程中,最后那行的代码不断地更新路径上的那些节点的高度,如果违反了AVL树的性质,则进行相应的调整.

随着所学知识的不断加深,人总对以前学过的知识进行反省……

<算法导论>上关于红黑树节点的旋转伪代码让我顿时陷入了沉思:为什么这他们要增加一个数据成员:指向父亲节点的指针??? 不觉得麻烦吗??(呵呵,当然,名著还是名著,当然有原因的…….)

我想到了上面 AVL树的那几行代码,我对比地看,对比地琢磨,终于明白了这本经典名著的良苦用心:为了更方便地寻找到一个节点的父亲节点.

有人纳闷了:这有什么大惊小怪的?

呵呵,别急,我先给你对比一下迭代和递归的优缺点:

1.如果一个问题刚开始难以解决,可以将其简化后再尝试解决。如果这个过程可以重复进行,问题最终会变得容易处理。由此引出两种不同的方法:递归和迭代。

2.循环或迭代,是一种重复执行一个过程的方法;递归是另一种方法。递归函数是通过调用函数自身来完成任务,而且在每次调用自身时减少任务量。而迭代是循环的一种形式,这种循环不是由用户输入而控制,每次迭代步骤都必须将剩余的任务减少;也就是说,循环的每一步都必须执行一个有限的过程,并留下较少的步骤。循环的进度通常用一个在每次迭代时都进行自增或自减的变量的值来衡量,直到到达预定的目标为止。

3.用递归算法表示许多问题的求解方法时算法思想非常简洁。但是递归算法不仅时间效率非常差,而且由于递归算法是不断的函数调用和函数返回过程,因此其实际的计算机运行时间通常远大于循环方式算法的计算机运行时间,甚至在有限的时间内无法求解。这就存在一个把递归算法化为非递归算法的问题。 

听说递归的时间效率有点低下,我自然会有将递归化为迭代的想法了.

在AVL树的节点插入之后,需要调整那些不平衡的节点,如果你用了含有指向父亲节点的指针之后,这个过程就变得相对的容易一些:你在回溯的过程中,只需要回溯到它的父亲节点就行了.

有人又说了,我可以用栈啊……

呵呵,我说,你不觉得那样很麻烦吗?而且,整个压栈和出栈的过程你能烂熟于心??这个过程就让你痛不欲生.

所以,我还是觉得,增加一个指向父亲节点的指针,这样进行回溯的时候相当的方便.

这样100%完美吗?

呵呵,不好说,我总觉得多了一个指针,有点浪费空间.当然,这只是感性的一些看法,具体的,还要研究研究……