摘 要： 由于《数据结构》抽象性和灵活性等特点,给教学和学习带来一定的困难。本文对《数据结构》课程的教学进行了研究,就经典算法展开了讨论,期望能对读者有所帮助。
关键词：数据结构；算法；软件设计
1、经典算法的选择
选择经典算法的重要性，PASCAL语言的创始人、著名的计算机科学家N.沃思说得好“程序=数据结构+算法”,足以见得算法在程序设计中的重要地位。在合理的数据结构基础上,算法是对数据结构的操作(运算),是数据处理的核心。在《数据结构》中介绍的基本数据结构有线性表、堆栈、队列、数组、树、二叉树、图以及相应的算法。一个算法是建立在某种数据结构的基础上,一个算法不可能脱离数据结构而孤立存在。只有通过学习算法,才能真正掌握某种数据结构。可以说学习《数据结构》的过程基本上是学习各种算法的过程。在众多的算法中有简单的、有复杂的、有容易的、有难度大的,在有限的学时情况下,不可能也没有必要逐一讲解每一个算法。大多数的算法,要靠学生自己理解消化。在这种情况下,如何选择少量的经典算法进行分析讲解,显得尤其重要。一个经典算法往往能起到以一当十、以点带面的关键作用。通过经典算法的分析,一方面让学生加深对数据结构基本理论的理解另一方面让学生学习程序设计方法。
选择好经典算法后下一步就是要对其展开综合分析,下面以具体的算法为例进行讨论。
2、利用经典算法说明基本原理
经典算法应能体现某个数据结构的基本特征。我们知道线性表顺序存储时其优点是能够对每个数据元素随机访问,存储密度高,其缺点是插入、删除操作时需要移动大量的数据元素,操作效率低。“向有序(由小到大或由大到小)的线性表(顺序存储)插入一个新的数据元素”,这一经典算法集中反映了线性表顺序存储的这些特点。
分析:将一个值为X的数据元素插入到有序(由小到大或由大到小)的线性表(顺序存储)中,可以分两步进行,首先查找到值为X的数据元素在线性表中应有的位置,采用从头到尾循环比较的方法确定其位置I,然后,将第I个以后的全部数据元素向后移动一个存储单元,最后将值为X的数据元素存放到第I个位置上,线性表元素个数增1。
【算法1】
PROCEDURE INSERT(V,m,n,X)
//将值为X的数据元素插入到V数组中,(线性表顺序存贮在V中)m为最多元素个数,n为当前实际元素个数
IF (m=n) THEN{“OVERFLOW”;RETURN}
FOR I=1 TO n DO
IF (X〈V(I))THEN BREAK
FOR J=n TO I BY -1 DO V(J+1)=V(J)
V(I)=X
n=n+1
RETURN
分析:【算法1】的优点是简单,便于理解,缺点是①循环体内有提前退出语句,不利于结构化程序设计;②确定新数据元素位置和移动数据元素分两步进行,有重复操作,可以改进之,将两步合并一步完成,即将循环比较与移动数据元素同时进行。从线性表的尾部开始向前循环比较,比新数据元素大者后移,直到小于等于时停止。
【算法2】
PROCEDURE INSERT(V,m,n,X)
IF(m=n)THEN{“OVERFLOW”;RETURN}
I=n
WHILE (I〉=1)AND (V(I)〉X)DO {V(I+1)=V(I);I=I-1}
V(I+1)=X
n=n+1
RETURN
分析:注意【算法2】中循环条件,当循环结束后I=0或V(I)〈=X,新数据元素的位置为I+1,【算法1】的时间复杂度为0(2n),而【算法2】的时间复杂度为0(n),效率提高一倍。循环结构是结构化程序设计中最基本最核心的部分,归纳循环条件是关键。【算法2】能进一步推广。
2.2 利用经典算法学习算法设计
经典算法能给学习者以启示、示范作用。
分析:可以将【算法2】用于对线性表(顺序存储)排序算法中。在直接插入排序算法中,其算法思想是从第2个数据元素开始直到第n个数据元素,逐一插入到已有序的子线性表中。
【算法3】
PROCEDURE SORT(V,n)
FOR I=2 TO n DO
{ Y=V(I)
J=I-1
WHILE (J〉=1) AND (V(J)〉Y) DO {V(J+1)=V(J);J=J-1}
V(J+1)=Y }
RETURN
分析:【算示3】其结构分为双重循环,外循环完成逐一取数据元素,即取第I个数据元素,内循环完成将第I个数据元素插入到前I-1个已有序的子线性表中。内循环完成的功能可以独立成为一个子函数(子过程),可以借用【算法2】。这正是结构化程序设计思想的体现,即主程序完成任务的划分,说明“做什么”,子函数(子过程)完成任务的具体实现,说明“如何做”。结构化程序设计方法采取“分解”的手段来控制系统的复杂性,将大系统划分为若干个相对独立的、功能单一的子模块。一方面子函数(子过程)可以实现软件的重用性,在不同的程序段有相同的处理过程时调用子函数(子过程),减少软件开发的工作量;另一方面子函数(子过程)对具体的实现技术细节进行隐藏,便于开发人员集中精力把握软件开发的核心和主要问题,降低了软件开发难度,从而保证软件质量。在利用【算法2】时要稍加修改,见【算法4】
【算法4】
PROCEDURE INSERT(V,I,X)
//将值为X的数据元素插入到已有序的前I-1个数据元素中
J=I-1
Y=X
WHILE (J〉=1) AND (V(J)〉X) DO {V(J+1)=V(J);J=J-1}
V(J+1)=Y
RETURN
相应的主程序也要作修改,见【算法5】
【算法5】
PROCEDURE SORT(V,n)
FOR I=2 TO n DO
INSERT(V,I,V(I))
RETURN
3、结束语
在众多的算法中选择好少量的经典算法对于教好、学好《数据结构》至关重要;经典算法要有助于学生理解对应的数据结构,经典算法的分析要侧重于程序设计能力的提高。
参考文献：
[1]欧建圣《.数据结构》教学研究——经典算法的综合分析[J].武汉工程职业技术学院学报,2004.16(1):58~60
[2]范德宝,于晓聪,丁伟祥.提高数据结构课程教学效果的探讨[J].黑龙江科技信息,2007.9:194~194
[3]徐金梅,罗刘敏《.数据结构》教学方法研究和探讨[J].现代计算机(下半月版),2007.8:78~80
