文章出自:http://blog.csdn.net/sxhelijian/article/details/7959647
【摘要】学习数据结构时,将各种基本操作通过程序实现,可以加深对算法的理解,也是提高编程能力的一种有效手段。针对初学者在搭建算法和程序之间联系困难的问题,本文以线性表部分为例,介绍了如何从读算法中找出实现程序的线索,围绕算法和程序之间的联系、抽象的描述和具体的实现之间的关系,引导读者学到抽象算法的精髓,最后对实践的路线、方案等进行了总结,并给出一些建议。
【讲座和视频】见《讲座:跨过算法和程序之间的那道沟(带视频链接)》
【正文】
计算机是算法的科学。学习IT的童鞋,在算法中下多大的功夫都不为过。在学习《数据结构》课程的时候,将教材中给出的算法用程序代码描述出来,在实现的过程中,可以不断加深思考;在调试程序的过程中,对算法的细节能够进行精细的钻研,这些都是获得算法精髓的方法。算法往往用“伪代码”的形式给出,学生在学习过程中,将这种抽象的描述与能够执行的具体形态的代码之间建立联系,使得算法形象起来,这样一个学习过程,以及由此带来的体验,将会使学生在技术成长之路上受益菲浅。
在我组织的“未来IT工程师协会/CSDN高校俱乐部”的活动中,结合同学们正在“算法与数据结构”课程,创办“算法达人修炼营”,组成合作学习团体,实践相关的各种算法,讨论在算法学习中遇到的问题,以此来提高驾驭算法的能力。为帮助同学们做好抽象的数据结构、算法与某种语言编写的程序之间的过渡,特撰写此文。
结合我校大二同学已经有的知识结构,本文以严蔚敏老师的《数据结构(C语言版)》为基础说数据结构和算法,实现算法的语言用C和C++。(建议:读本文中,一边翻着教材才有感觉。)
一、读算法中找出实现程序的线索
要看懂算法,解决其中存在的障碍,需要同学们在读书时能够做到前后对照。
以P23中的算法2.3为例讲读算法的方法,以及如何前后对照。
算法2.3的顺序存储的线性表的初始化问题,伪代码是:
为便于后续的说明,为算法加些行号:
- 1. Status InitList_sq(SqList &L){
- 2. //构造一个空的线性表L
- 3. L.elem =(ElemType *)malloc(LIST_INIT_SIZE * size(ElemType));
- 4. if(!L.elem) exit(OVERFLOW); //存储分配失败
- 5. L.length = 0; //空表长度为0
- 6. L.listsize = LIST_INIT_SIZE; //初始存储容量
- 7. return OK;
- 8. }
这个算法要解决的问题非常显然,用思维导图表达出来是:
算法中的逻辑非常简单,常有同学说,算法是能看懂。这得益于抽象(后面专门要说),使我们忽略了很多实现中要考虑的细节,所以容易看懂,这是抽象的好处。而恰好由于忽略了实现细节中的具体形态,使得在考虑如何实现算法时出现障碍。这不是一个大问题,却成为初学者起步的一个障碍,尤其是对程序设计的功底并不很深的同学。(程序设计功底的加强是必需的,但已经到了这个阶段,并不是一定要先补上那一课再能学数据结构,时候不等人。实际上,学数据结构,同时也促程序设计。)
障碍主要来自于,算法描述中出现的“词汇”和曾经编程中用过的似乎并不相同。“字”都不认识,谈何理解,又何谈实现。实际上,会看书的同学应该发现,算法中出现的“词”,在教材前面都曾经出现过,我们找出来,将其联系到一起。
说有些同学不会看书可能委屈,更多的是没有耐心,一门课程起步阶段,基础性的内容要看细了。
算法第1行:Status InitList_sq(SqList &L)
InitList_sq是函数名自不用说。Status 显然是函数InitList_sq()的返回值类型,但究竟是什么类型呢?C和C++中没有这种数据类型,其他语言中也没有,可以猜到是自定义类型。教材P10有解释:
教材接着给出了在C语言实现算法时的建议:
- //Status是函数的类型,其值是函数结果的代码
- typedef int Status
其实如果用PASCAL实现,需要按PASCAL语言的语法写作:
- type Status=integer;
一个函数执行结束后,函数结果的代码给出一些约定(如1是成功,0是失败)通过返回值通知调用函数执行的情况,这种设计很常见。那么,此处Status用整型表示,其具体取值与含义是什么?从算法第7行 return OK;可以看出,这个OK就是Status可取的值。同样在P10,有一些常定义(只列两行,ERROR在其他函数中用到):
- #define OK 1
- #define ERROR 0
在PASCAL中,对应的定义是:
- const OK=1;
- const ERROR=0;
还没有说Java,不说不够意思。C/C++和PASCAL中利用自定义类型解决,而Java中没有提自定义类型一词,但实际就在不断地声明自定义类型(calss)。在此做自定义类实现涉嫌杀鸡用牛刀,一种合适的解决方法是用枚举类型(其实这种方法对C/C++也合适):
- enum Status {ERROR, OK};
理解:抽象的Status在各种语言中实现的途径不同,甚至在一种语言中也可以有不同的实现方案。算法这样的写法有两个方面的好处:(1)可以供使用不同语言编程的人使用;(2)对学习算法的人而言,可以忽略(用某语言实现的)细节,而将注意力集中到算法本身。这两点好处对于后面的复杂算法更加重要。再次强调,要习惯并喜欢上这种抽象的描述。
接下来讲函数InitList_sq()的形式参数&L。
形式参数&L的类型是对SqList类型的引用。SqList类型是何类型?自定义类型。SqList是一个结构体类型,其定义就在P22,算法2.3前的一点点:
SqList结构体包括有三个数据成员,在函数中都会用到。Length和listsize成员的类型是整型int好理解,ElemType又是个什么类型?理解了前面Status抽象的意义后,可以猜到ElemType又是个抽象数据类型,对应的是顺序表中要存储的数据的类型。ElemType(见名知义,元素类型)在教材前面出现过,但放在不同应用背景下,可以给出不同的定义。这个数据可以是简单的整型(若干整数的序列构成一个线性表),也可以是浮点型,甚至ElemType是一个字符串、结构体。例如,可以是:
- typedef