浅谈抽象思维在计算机学习与研究中的应用..doc

浅谈抽象思维在计算机学习与研究中的应用 摘要：本文从抽象思维的角度，运用“数据结构”中的经典例子来阐述在计算机的学习与研究过程中应运用抽象思维的方法达到“学其思维，掠其形式”的目的。同时论述了在计算机的应用中应运用科学的思维方法和注重计算机科学理论的研究。br　　关键词br本文来自：计算机毕业网 ：抽象思维；链表；二叉树；图；排序与查找br　　　　　　 br　　在几年的计算机教学与实践中，作者发现，大家在学习与应用计算机的过程中，往往采用的是具体的思维方法，即通过举一个实际的例子来“一步一步”地理解算法思想。本文认为这种“学其形式，掠其思维”的学习与研究方法是不足取的。在学习与研究计算机的过程中，我们应当运用抽象的思维方法，达到“学其思维，掠其形式”的目的。下面我们通过“数据结构”中的典型例子来说明抽象思维方法在计算机中的妙用。br　　br　　1线性表中的单链表的逆转(在利用原结点的情况下)br　　br　　设逆转后的单链表的表头结点为reversed_head(初始值为NIL)，当前正在转换的结点为current，未被转换的结点的单链表的表头结点为not_reversed_head，如图1所示。br　　br　　则我们可以很快写出如下的算法：br　　br　　procedure reverse_link(var head:pointer);br　　var br　　reversed_head，current，not_reversed_head:pointer;br　　beginbr　　reversed_head:=nil;br　　current:=head;br　　not_reversed_head:=current↑.link;br　　while currentnil dobr　　 br　　beginbr　　current↑.link:=reversed_head;br　　reversed_head:=current;br　　current:=not_reversed_head;br　　not_reversed_head:=current↑.linkbr　　end;br　　head:=reversed_headbr　　end;br　　br　　可见，运用抽象的思维方法，该算法变得很精炼。br　　br　　2二叉树遍历的递归算法与线索二叉树的删除算法br　　br　　二叉树遍历的算法有三种，即前序遍历、中序(对称序)遍历和后序遍历，通常用NLR，LNR，LRN来表示。运用抽象的思维方法，我们可以从NLR，LNR，LRN的书写当中，得出：br　　(1) 无论哪种遍历次序，二叉树的叶子始终以相同的相对次序出现，因为L始终在R的前面；br　　(2) 在NLR次序遍历的结点中，第一个结点是二叉树的根，最后一个结点是二叉树的最右下的结点；在LNR次序遍历的结点中，第一个结点是二叉树的最左下的结点，最后一个结点是二叉树的最右下的结点；在LRN次序遍历的结点中，第一个结点是二叉树的最左下的结点，最后一个结点是二叉树的根。br　　在对称序线索二叉树的删除算法中，运用抽象的思维方法，我们可以假设该线索二叉树的LNR次序遍历的结点序列为……rP……P1……或……P1……rP……，如图2所示：br　　这样，删除结点P时，可以找出如下的思路。br　　思路1：删除结点P时，将其右子树成为r的右子树，或将P的左了树成为P的右子树的最左下结点的左子树。br　　br　　思路2：删除结点P时，用r结点去替换结点P，此时，r的左子树应成为其双亲的右子树，或以P为根的二叉树的右子树的最左下结点去替换结点P，此时最左下结点的右子树应成为其双亲的左子树。br　　以思路1为例，我们可以写出如下的核心算法：br　　br　　P1↑.lchild:=P↑.lchild;或P1↑.rchild:=P↑.lchild;br　　r↑.rchild:=P↑.rchild’br　　dispose(P);br　　br　　3图中求最短径的Dijkstra算法br　　br　　Dijkstra在求图中从一个源点到其他任意顶点的最短路径时，运用贪婪法的思想，将顶点集分为“已确定最短路径的顶点集”和“未确定最短路径的顶点集”两部分，按照路径长度递增的顺序选择当前路径长度最短的顶点，同时修改当前“未确定最短路径的顶点集”的顶点的最短路径长度，直到选择完毕。初学者对该算法在选择的同时又进行修改，往往不能理解。如果我们运用抽象思维，用如下的图3表示这种情况，则会易于理解。br　　br　　其中dist[k]代表源点到当前确定最短路径长度的顶点k的最短路径长度；br　　dist[j]代表源点到原先运用贪婪法确定的最短路径长度的顶点j的最短路径长度；br　　cos