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

《401编号给数据结构初学者：跨过算法和程序之间的鸿沟》由会员分享，可在线阅读，更多相关《401编号给数据结构初学者：跨过算法和程序之间的鸿沟（11页珍藏版）》请在金锄头文库上搜索。

1、给数据结构初学者：跨过算法和程序之间的鸿沟 【摘要】学习数据结构时，将各种基本操作通过程序实现，可以加深对算法的理 解，也是提高编程能力的一种有效手段。针对初学者在搭建算法和 程序之间联 系困难的问题，本文以线性表部分为例，介绍了如何从读算法中找出实现程序的 线索，围绕算法和程序之间的联系、抽象的描述和具体的实现之间的关 系，引 导读者学到抽象算法的精髓，最后对实践的路线、方案等进行了总结，并给出一 些建议。 【正文】 计算机是算法的科学。学习 IT 的童鞋，在算法中下多大的功夫都不为过。 在学习数据结构课程的时候，将教 材中给出的算法用程序代码描述出来， 在实现的过程中，可以不断加深思考；在

2、调试程序的过程中，对算法的细节能够 进行精细的钻研，这些都是获得算法精髓的方 法。算法往往用“伪代码”的形 式给出，学生在学习过程中，将这种抽象的描述与能够执行的具体形态的代码之 间建立联系，使得算法形象起来，这样一个学习过 程，以及由此带来的体验， 将会使学生在技术成长之路上受益菲浅。 在我组织的“未来 IT 工程师协会/CSDN 高校俱乐部”的活动中，结合同学 们正在“算法与数据结构”课程，创办“算法达人修炼营”，组成合作学习团体， 实践相关的各种算法，讨论在算法学习中遇到的问题，以此来提高驾驭算法的能 力。 为帮助同学们做好抽象的数据结构、 算法与某种语言编写的程序之间的过渡， 特撰写此

3、文。 结合我校大二同学已经有的知识结构，本文以严蔚敏老师的数据结构（C 语言版）为基础说数据结构和算法，实现算法的语言用 C 和 C+。（建议：读 本文中，一边翻着教材才有感觉。） 一、读算法中找出实现程序的线索一、读算法中找出实现程序的线索 要看懂算法， 解决其中存在的障碍， 需要同学们在读书时能够做到前后对照。 以 P23 中的算法 2.3 为例讲读算法的方法，以及如何前后对照。 算法 2.3 的顺序存储的线性表的初始化问题，伪代码是： 为便于后续的说明，为算法加些行号： plain view plaincopyprint? 1.1. Status InitList_sq(SqList 4

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. 这个算法要解决的问题非常显然，用思维导图表达出来是： 算法中的逻辑非常简单，常有同学说，算法是能看懂。这得益于抽象（后 面专门要说），使我们忽略了很多实现中要考虑的细节，所以容易看懂，这是抽 象的好 处。而恰好由于忽略了实现细节中的具体形态，使得在考虑如何实现算 法时出现障碍。这不是一个大问题，却成为初学者起步的一个障碍，尤其是对程 序

5、设计的功底 并不很深的同学。（程序设计功底的加强是必需的，但已经到了 这个阶段，并不是一定要先补上那一课再能学数据结构，时候不等人。实际上， 学数据结构，同时也 促程序设计。） 障碍主要来自于，算法描述中出现的“词汇”和曾经编程中用过的似乎并不 相同。“字”都不认识，谈何理解，又何谈实现。实际上，会看书的同学应该发 现，算法中出现的“词”，在教材前面都曾经出现过，我们找出来，将其联系到 一起。 说有些同学不会看书可能委屈，更多的是没有耐心，一门课程起步阶段，基 础性的内容要看细了。 算法第 1 行：Status InitList_sq(SqList 一个函数执行结束后，函数结果的代码给出一些约

6、定（如 1 是成功，0 是失 败） 通过返回值通知调用函数执行的情况， 这种设计很常见。 那么， 此处 Status 用整型表示，其具体取值与含义是什么？从算法第 7 行 return OK;可以看出， 这个 OK 就是 Status 可取的值。同样在 P10，有一些常定义（只列两行，ERROR 在其他函数中用到）： cpp view plaincopyprint? 1.#define OK 1 2.#define ERROR 0 在 PASCAL 中，对应的定义是： delphi view plaincopyprint? 1.const OK=1; 2.const ERROR=0; 还没有说

7、 Java，不说不够意思。C/C+和 PASCAL 中利用自定义类型解决， 而 Java 中没有提自定义类型一词， 但实际就在不断地声明自定义类型(calss)。 在此做自定义类实现涉嫌杀鸡用牛刀，一种合适的解决方法是用枚举类型（其实 这种方法对 C/C+也合适）： java view plaincopyprint? 1.enum Status ERROR, OK; 理解：理解：抽象的 Status 在各种语言中实现的途径不同，甚至在一种语言中也 可以有不同的实现方案。算法这样的写法有两个方面的好处：（1）可以供使用 不同语言编程的人使用 ； （2） 对学习算法的人而言， 可以忽略 （用某语言

8、实现的） 细节，而将注意力集中到算法本身。这两点好处对于后面的复杂算法更加重要。 再次强调，要习惯并喜欢上这种抽象的描述。 接下来讲函数 InitList_sq()的形式参数 3.char name16; 4.int age; 5.float score; 6.ElemType; 在教材例 2.4 中，线性表中的数据是多项式中的一项，需要记录数据下系 数和指数，使用了结构体： cpp view plaincopyprint? 1.typedef struct 2.float coef; /系数 3.int expn; /指数 4.ElemType; 至于用其他语言和任务的实现，不再给出分析和示

9、例，道理一样。 理解了上面的内容， 从第 2 行开始就好办了。 第 2 行注释说明了这个算法完 成的操作，第 3 行分配内存空间： cpp view plaincopyprint? 1.L.elem =(ElemType *)malloc(LIST_INIT_SIZE * size(ElemType); malloc()函数是分配内存空间，相当于 C+中的 new 运算符。查手册知 malloc()的原型是： cpp view plaincopyprint? 1.void *malloc(unsigned int num_bytes); 由函数调用可以看出，分配的空间大小为 LIST_INIT

10、_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

11、 语言实现为例，在实现时，需要把这段算法/程序所需要的其 他内容写到一个文件中。需要写一些类型定义 typedef、常量定义#define、包 含文件#include 等，这是语言的要求。另外，还要增加 mian()函数作为程序运 行的入口，在其中设置测试和调试程序的代码，如果必要，还应该增加一些专门 用于输入、输出的函数。 这样，为实践算法 2.3 写出的对应程序是： cpp view plaincopyprint? 1.#include /printf()等 2.#include / malloc()等 3.#include /exit() 4.#define OK 1 5.#define

12、 OVERFLOW -2 6.typedef int Status; /Status 是函数的类型,其值是函数结果状态代码，如 OK 等 7.typedef int ElemType; /ElemType 是线性表中数据元素的类型，此处用 int 8.#define LIST_INIT_SIZE 10 / 线性表存储空间的初始分配量，为方便测试，改为 10 9.typedef struct 10. 11. ElemType *elem; / 存储空间基址 12. int length; / 当前长度 13. int listsize; / 当前分配的存储容量(以 sizeof(ElemType

13、)为单位) 14. SqList; 15. Status InitList(SqList 18. if(!L.elem) 19. exit(OVERFLOW); / 存储分配失败 20. L.length=0; / 空表长度为 0 21. L.listsize=LIST_INIT_SIZE; / 初始存储容量 22. return OK; 23. 24. Status ListTraverse(SqList L) 25. / 初始条件：顺序线性表 L 已存在 26. / 操作结果：依次输出 L 中的每个数据元素，函数名没有用 display，而是用了更 专业的术语遍历 Traverse 27.

14、 ElemType *p; 28. int i; 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. else 38. printf(目前还是空线性表。); 39. printf(n); 40. return OK; 41. 42. int main() 43. 44. SqList La; 45. Sta

15、tus i; 46. i=InitList(La); 47. ListTraverse(La); 48. return 0; 49. 对于上面的程序，运行结果为： 上面的程序要用 C+（或 Java）实现时，将 SqList 定义为一个类，基本操 作为成员函数（或称为方法）。 二、理解算法和程序之间的“跨度”二、理解算法和程序之间的“跨度” 下面罗列网上收集来的几组说法，适当修改、补充，提供给读者从多个角度 分别体会： 说法 1： 算法是解决问题的步骤；程序是算法的代码实现。 算法要依靠程序来完成功能；程序需要算法作为灵魂。 说法 2： 算法与程序：(1)一个程序不一定满足有穷性，而算法需要在

16、有限步骤内完 成。(2)程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3) 算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若 用程序设计语言来描述，则它就是一个程序。 说法 3： 从计算机的角度讲， 程序是用一种计算机能理解并执行的计算机语言描述解 决问题的方法步骤。算法是解决问题的方法步骤（不一定要让计算机能理解并执 行）。程序设计是分析解决问题的方法步骤，并将其记录下来的过程，其关键就 是将算法描述出来。 数据结构课程里面的代码，都是伪代码，也就是说，用 C 编译器编译是通不 过的，还要做很多的修改才可以。算法是编程的核心，算法出来了，我们就可以 考虑用哪种语言实现比较