给数据结构初学者：跨过算法和程序之间的鸿沟

给数据结构初学者：跨过算法和程序之间的鸿沟【摘要】学习数据结构时，将各种基本操作通过程序实现，可以加深对算法的理解，也是提高编程能力的一种有效手段。针对初学者在搭建算法和程序之间联系困难的问题，本文以线性表部分为例，介绍了如何从读算法中找出实现程序的线索，围绕算法和程序之间的联系、抽象的描述和具体的实现之间的关系，引导读者学到抽象算法的精髓，最后对实践的路线、方案等进行了总结，并给出一些建议。【正文】计算机是算法的科学。学习IT的童鞋，在算法中下多大的功夫都不为过。在学习《数据结构》课程的时候，将教材中给出的算法用程序代码描述出来，在实现的过程中，可以不断加深思考；在调试程序的过程中，对算法的细节能够进行精细的钻研，这些都是获得算法精髓的方法。算法往往用“伪代码”的形式给出，学生在学习过程中，将这种抽象的描述与能够执行的具体形态的代码之间建立联系，使得算法形象起来，这样一个学习过程，以及由此带来的体验，将会使学生在技术成长之路上受益菲浅。在我组织的“未来IT工程师协会/CSDN高校俱乐部”的活动中，结合同学们正在“算法与数据结构”课程，创办“算法达人修炼营”，组成合作学习团体，实践相关的各种算法，讨论在算法学习中遇到的问题，以此来提高驾驭算法的能力。为帮助同学们做好抽象的数据结构、算法与某种语言编写的程序之间的过渡，特撰写此文。结合我校大二同学已经有的知识结构，本文以严蔚敏老师的《数据结构（C语言版）》为基础说数据结构和算法，实现算法的语言用C和C++。（建议：读本文中，一边翻着教材才有感觉。）一、读算法中找出实现程序的线索要看懂算法，解决其中存在的障碍，需要同学们在读书时能够做到前后对照。以P23中的算法2.3为例讲读算法的方法，以及如何前后对照。算法2.3的顺序存储的线性表的初始化问题，伪代码是：为便于后续的说明，为算法加些行号：[plain]viewplaincopyprint?1.1.StatusInitList_sq(SqList&L){2.2.//构造一个空的线性表L3.3.L.elem=(ElemType*)malloc(LIST_INIT_SIZE*size(ElemType));4.4.if(!L.elem)exit(OVERFLOW);//存储分配失败5.5.L.length=0;//空表长度为06.6.L.listsize=LIST_INIT_SIZE;//初始存储容量7.7.returnOK;8.8.}这个算法要解决的问题非常显然，用思维导图表达出来是：算法中的逻辑非常简单，常有同学说，算法是能看懂。这得益于抽象（后面专门要说），使我们忽略了很多实现中要考虑的细节，所以容易看懂，这是抽象的好处。而恰好由于忽略了实现细节中的具体形态，使得在考虑如何实现算法时出现障碍。这不是一个大问题，却成为初学者起步的一个障碍，尤其是对程序设计的功底并不很深的同学。（程序设计功底的加强是必需的，但已经到了这个阶段，并不是一定要先补上那一课再能学数据结构，时候不等人。实际上，学数据结构，同时也促程序设计。）障碍主要来自于，算法描述中出现的“词汇”和曾经编程中用过的似乎并不相同。“字”都不认识，谈何理解，又何谈实现。实际上，会看书的同学应该发现，算法中出现的“词”，在教材前面都曾经出现过，我们找出来，将其联系到一起。说有些同学不会看书可能委屈，更多的是没有耐心，一门课程起步阶段，基础性的内容要看细了。算法第1行：StatusInitList_sq(SqList&L)InitList_sq是函数名自不用说。Status显然是函数InitList_sq()的返回值类型，但究竟是什么类型呢？C和C++中没有这种数据类型，其他语言中也没有，可以猜到是自定义类型。教材P10有解释：教材接着给出了在C语言实现算法时的建议：[cpp]viewplaincopyprint?1.//Status是函数的类型，其值是函数结果的代码2.typedefintStatus其实如果用PASCAL实现，需要按PASCAL语言的语法写作：[delphi]viewplaincopyprint?1.typeStatus=integer;一个函数执行结束后，函数结果的代码给出一些约定（如1是成功，0是失败）通过返回值通知调用函数执行的情况，这种设计很常见。那么，此处Status用整型表示，其具体取值与含义是什么？从算法第7行returnOK;可以看出，这个OK就是Status可取的值。同样在P10，有一些常定义（只列两行，ERROR在其他函数中用到）：[cpp]viewplaincopyprint?1.#defineOK12.#defineERROR0在PASCAL中，对应的定义是：[delphi]viewplaincopyprint?1.constOK=1;2.constERROR=0;还没有说Java，不说不够意思。C/C++和PASCAL中利用自定义类型解决，而Java中没有提自定义类型一词，但实际就在不断地声明自定义类型(calss)。在此做自定义类实现涉嫌杀鸡用牛刀，一种合适的解决方法是用枚举类型（其实这种方法对C/C++也合适）：[java]viewplaincopyprint?1.enumStatus{ERROR,OK};理解：抽象的Status在各种语言中实现的途径不同，甚至在一种语言中也可以有不同的实现方案。算法这样的写法有两个方面的好处：（1）可以供使用不同语言编程的人使用；（2）对学习算法的人而言，可以忽略（用某语言实现的）细节，而将注意力集中到算法本身。这两点好处对于后面的复杂算法更加重要。再次强调，要习惯并喜欢上这种抽象的描述。接下来讲函数InitList_sq()的形式参数&L。形式参数&L的类型是对SqList类型的引用。SqList类型是何类型？自定义类型。SqList是一个结构体类型，其定义就在P22，算法2.3前的一点点：SqList结构体包括有三个数据成员，在函数中都会用到。Length和listsize成员的类型是整型int好理解，ElemType又是个什么类型？理解了前面Status抽象的意义后，可以猜到ElemType又是个抽象数据类型，对应的是顺序表中要存储的数据的类型。ElemType（见名知义，元素类型）在教材前面出现过，但放在不同应用背景下，可以给出不同的定义。这个数据可以是简单的整型（若干整数的序列构成一个线性表），也可以是浮点型，甚至ElemType是一个字符串、结构体。例如，可以是：[cpp]viewplaincopyprint?1.typedefintElemType还可以是：[cpp]viewplaincopyprint?1.typedefstructstudent{2.charnum[10];3.charname[16];4.intage;5.floatscore;6.}ElemType;在教材例2.4中，线性表中的数据是多项式中的一项，需要记录数据下系数和指数，使用了结构体：[cpp]viewplaincopyprint?1.typedefstruct{2.floatcoef;//系数3.intexpn;//指数4.}ElemType;至于用其他语言和任务的实现，不再给出分析和示例，道理一样。理解了上面的内容，从第2行开始就好办了。第2行注释说明了这个算法完成的操作，第3行分配内存空间：[cpp]viewplaincopyprint?1.L.elem=(ElemType*)malloc(LIST_INIT_SIZE*size(ElemType));malloc()函数是分配内存空间，相当于C++中的new运算符。查手册知malloc()的原型是：[cpp]viewplaincopyprint?1.void*malloc(unsignedintnum_bytes);由函数调用可以看出，分配的空间大小为LIST_INIT_SIZE*size(ElemType)，足够存放LIST_INIT_SIZE（定义的常量，值为100，见P22）个ElemType型的值，返回的地址指针转换为指向ElemType型的指针。函数调用结束后，将指针赋值给L.elem。算法第4行：if(!L.elem)exit(OVERFLOW);是在存储分配失败时的处理，OVERFLOW是P10定义的常量，值为-2。第5行和第6行算法就不再多述。其实也都是C中的内容，不清楚的内容通过参考资料可以解决。从上面的描述可以看出，教材中说得是用伪代码描述算法，算法实际上已经就是程序了。以C语言实现为例，在实现时，需要把这段算法/程序所需要的其他内容写到一个文件中。需要写一些类型定义typedef、常量定义#define、包含文件#include等，这是语言的要求。另外，还要增加mian()函数作为程序运行的入口，在其中设置测试和调试程序的代码，如果必要，还应该增加一些专门用于输入、输出的函数。这样，为实践算法2.3写出的对应程序是：[cpp]viewplaincopyprint?1.#includestdio.h//printf()等2.#includemalloc.h//malloc()等3.#includeprocess.h//exit()4.#defineOK15.#defineOVERFLOW-26.typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等7.typedefintElemType;//ElemType是线性表中数据元素的类型，此处用int8.#defineLIST_INIT_SIZE10//线性表存储空间的初始分配量，为方便测试，改为109.typedefstruct10.{11.ElemType*elem;//存储空间基址12.intlength;//当前长度13.intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)14.}SqList;15.StatusInitList(SqList&L)//算法2.316.{//操作结果：构造一个空的顺序线性表17.L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));18.if(!L.elem)19.exit(OVERFLOW);//存储分配失败20.L.length=0;//空表长度为021.L.listsize=LIST_INIT_SIZE;//初始存储容量22.returnOK;23.}24.StatusListTraverse(SqListL)25.{//初始条件：顺序线性表L已存在26.//操作结果：依次输出L中的每个数据元素，函数名没有用display，而是用了更专业的术语——遍历Traverse27.ElemType*p;28.inti;29.p=L.elem;30.printf(线性表当前容量为:%d，,L.listsize);31.if(L.length0)32.{33.printf(线性表中有%d个元素，分别是：,L.length);34.for(i=1;i=L.length;i++)35.printf(%d,*p++);36.}37.else38.printf(目前还是空线性表。);39.printf(\n);40.returnOK;41.}42.intmain()43.{44.SqListLa;45.Statusi;46.i=InitList(La);47.ListTraverse(La);48.return0;49.}对于上面的程序，运行结果为：上面的程序要用C++（或Java）实现时，将SqList定义为一个类，基本操作为成员函数（或称为方法）。二、理解算法和程序之间的“跨度”下面罗列网上收集来的几组说法，适当修改、补充，提供给读者从多个角度分别体会：说法1：算法是解决问题的步骤；程序是算法的代码实现。算法要依靠程序来完成功能；程序需要算法作为灵魂。说法2：算法与程序：(1)一个程