第 1 章 绪论.pptVIP

(1) for (i=0;in;i++) for (j=0;jn; j++) A[i][j]=0; T(n)=O(n2) (2) s=0; for (i=0;in;i++) for (j=0;jn;j++) for (k=0;kn;k++) s=s+B[i][j][k]; sum=s; T(n)= O(n3) (3) i=s=0; while (sn) { i++; s+=i; //s=s+i } T(n)= O(n1/2) (4) i=1; while (i=n) i=i*2; T(n)= O(log2n) (5) x=91; y=100;  while (y0) { If (x100) { x=x-10; y--; } else x++; } T(n)= O(1) ◇ 这个程序看起来有点吓人， 总共循环运行了1000次，但是我们看到这段程序的运行是和n无关的，就算它再循环一万年，我们也不管它，只是一个常数阶的函数。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。 那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。 最后，我们有了这个表（数据结构），肯定要用它，那么就是要对这张表中的记录进行查询、修改、删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 一个数据结构示例 1.5 总结 求解问题的主要步骤 求解问题的两大类 什么是数据结构？ 四类逻辑结构 四类存储结构 算法的设计取决于逻辑结构，实现依赖于存储结构 抽象数据类型（三元组表示） 算法的定义，算法与程序的主要区别 算法的描述方法 算法的五个重要特性和设计算法的四个基本要求 空间效率、时间效率的相互制约 时间效率的度量方法（基本操作的执行次数） 空间效率的度量方法（额外辅助空间的数量） 作业： P27：复习题+算法分析题，要求在阅读第一章的基础上回答。不要求写到作业本上，但一定掌握。 P28上机题（1或2），准备第一次上机练习。 上机前，完成源码编写，初步完成“上机报告”。 上机完成后，提交“上机报告”。 上机实习报告的书写规范。 第一章 概论 为什么要学习数据结构？ （什么是数据结构？） 基本概念和术语 数据类型和抽象数据类型 算法描述与算法评价 总结 为什么要学？ 学习哪些内容？ 怎么学？ 1.1 为什么要学习数据结构？ 摘自《/u11/aa2f9efe-916b-4f1c-9fbb-43a7448b38fb.html?87474》 Keeya0416: 虽然不用重复造轮子,但我们起码得知道轮子为什么做成圆的。 Karnonlm: 会不会算法的区别，就是年薪10万和30万的区别。那种别人都已经做过的东西，拿来用用堆代码谁都会。真正有价值的程序都是从来没有人做过的，比如各种语言中第一个实现那些数据结构的人，这些人都是30万年薪都招不到的。各种应用中都有新的具体的未被人解决过的问题，这时就需要精通算法的人去解。这些牛人解出来后提供了API，给别人调用。明白了么？你觉得那些算法不重要，都有现成的，就是因为你现在只停留在堆别人写好的API的10万年薪的水平，而不是大牛的水平。 AlexTuring: 总有人说数据结构用处不大.我感觉吧 这东西就是一种思想.时刻贯穿在你的代码中.一个写程序10年的人和一个初学者写同样要求的程序,老手写的代码就是不一样.他们的差距就在于对编程和算法的思想理解深度不一样吧awe 打个比方，要做一件普通的家具，我们选用通用的各种板材和相应的配件就可以完成，就像宜家的家具。要制作一件杰出的家具，如果你依然只能选用通用的版材和配件，你成功的概率就会很低。如果你自己会设计和制作相应的板材和配件，你的成功率就会高很多。软件制作中