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

给数据结构初学者：跨过算法和程序之间的鸿沟 【摘要】学习数据结构时，将各种基本操作通过程序实现，可以加深对算法的理 解，也是提高编程能力的一种有效手段。针对初学者在搭建算法和 程序之间联 系困难的问题，本文以线性表部分为例，介绍了如何从读算法中找出实现程序的 线索，围绕算法和程序之间的联系、抽象的描述和具体的实现之间的关 系，引 导读者学到抽象算法的精髓，最后对实践的路线、方案等进行了总结，并给出一 些建议。 【正文】 　　计算机是算法的科学。学习 IT 的童鞋，在算法中下多大的功夫都不为过。 在学习《数据结构》课程的时候，将教 材中给出的算法用程序代码描述出来， 在实现的过程中，可以不断加深思考；在调试程序的过程中，对算法的细节能够 进行精细的钻研，这些都是获得算法精髓的方 法。算法往往用 “伪代码”的形 式给出，学生在学习过程中，将这种抽象的描述与能够执行的具体形态的代码之 间建立联系，使得算法形象起来，这样一个学习过 程，以及由此带来的体验， 将会使学生在技术成长之路上受益菲浅。 　　在我组织的 “未来 IT 工程师协会/CSDN 高校俱乐部”的活动中，结合同学 们正在“算法与数据结构”课程，创办“算法达人修炼营”，组成合作学习团体， 实践相关的各种算法，讨论在算法学习中遇到的问题，以此来提高驾驭算法的能 力。为帮助同学们做好抽象的数据结构、算法与某种语言编写的程序之间的过渡， 特撰写此文。 　　结合我校大二同学已经有的知识结构，本文以严蔚敏老师的《数据结构（C 语言版）》为基础说数据结构和算法，实现算法的语言用 C 和 C++。（建议：读 本文中，一边翻着教材才有感觉。） 　　一、读算法中找出实现程序的线索 　　要看懂算法，解决其中存在的障碍，需要同学们在读书时能够做到前后对照。 　　以 P23 中的算法 2.3 为例讲读算法的方法，以及如何前后对照。 　　算法 2.3 的顺序存储的线性表的初始化问题，伪代码是： 　　为便于后续的说明，为算法加些行号： [plain] view plaincopyprint? 1. 1. Status InitList_sq(SqList L){ 2. 2. //构造一个空的线性表 L 3. 3. L.elem =(ElemType *)malloc(LIST_INIT_SIZE * size(ElemType)); 4. 4. if(!L.elem) exit(OVERFLOW); //存储分配失败 5. 5. L.length = 0; //空表长度为 0 6. 6. L.listsize = LIST_INIT_SIZE; //初始存储容量 7. 7. return OK; 8. 8. } 　　这个算法要解决的问题非常显然，用思维导图表达出来是： 　 　算法中的逻辑非常简单，常有同学说，算法是能看懂。这得益于抽象（后 面专门要说），使我们忽略了很多实现中要考虑的细节，所以容易看懂，这是抽 象的好 处。而恰好由于忽略了实现细节中的具体形态，使得在考虑如何实现算 法时出现障碍。这不是一个大问题，却成为初学者起步的一个障碍，尤其是对程 序设计的功底 并不很深的同学。（程序设计功底的加强是必需的，但已经到了 这个阶段，并不是一定要先补上那一课再能学数据结构，时候不等人。实际上， 学数据结构，同时也 促程序设计。） 　　障碍主要来自于，算法描述中出现的 “词汇”和曾经编程中用过的似乎并不 相同。 “字”都不认识，谈何理解，又何谈实现。实际上，会看书的同学应该发 现，算法中出现的 “词”，在教材前面都曾经出现过，我们找出来，将其联系到 一起。 　　说有些同学不会看书可能委屈，更多的是没有耐心，一门课程起步阶段，基 础性的内容要看细了。 　　算法第 1 行：Status InitList_sq(SqList L) 　　InitList_sq 是函数名自不用说。Status 显然是函数 InitList_sq()的返回 值类型，但究竟是什么类型呢？C 和 C++中没有这种数据类型，其他语言中也没 有，可以猜到是自定义类型。教材 P10 有解释： 　　教材接着给出了在 C 语言实现算法时的建议： [cpp] view plaincopyprint? 1. //Status 是函数的类型，其值是函数结果的代码 2. typedef int Status 　　其实如果用 PASCAL 实现，需要按 PASCAL 语言的语法写作： [delphi] view plaincopyprint?