问题求解-论题1-5 -数据与数据结构 陶先平.

Presentation on theme: "问题求解-论题1-5 -数据与数据结构 陶先平."— Presentation transcript:

1 问题求解-论题1-5 -数据与数据结构 陶先平

2 问题1：为什么每个数据都应该有个“类型”和它对应？
其实，计算机操纵的对象（数据）“类别”在表现形式上可以统一，但是： 表现形式的统一就是：01位串。但给定一个01位串，如何解读其含义？如何操纵其数据？是因数据代表的现实对象不同而不同的。这种不同必须在将对象数据化的时候就定义好，否则后期的处理将产生混乱。

3 X=X+1; 问题2：变量是不是量？ 我们该如何理解以下程序语句？ 从计算机的视角出发，这条语句“背后”我们能看到什么？ 变量是空间的代号
对数据的操纵：取，存（改变） 变量是空间的代号，对变量的使用（存、取）就是对变量所表示的空间中的数据的操纵。

4 变量、数据、类型 变量和数据 变量和数据类型 变量是用于跟踪、操纵几乎所有数据的简单(通用)工具 类型定义了变量的变化范围
数据是有“内存”地址的，变量名和地址是什么关系？ 变量和数据类型 类型定义了变量的变化范围 类型定义了计算对变量的操作方式

5 指针到底是什么？两个不同的赋值到底区别在哪里？
你能看清这个程序片段吗？ int *p1, *p2; *p1:=44; *p2:=99; P1:=P2; Print(*p1,*p2); int *p1, *p2; *p1:=44; *p2:=99; *p1:=*p2; Print(*p1,*p2); 指针到底是什么？两个不同的赋值到底区别在哪里？

6 多个数据的聚集管理而出现的“结构” 场景：“一队士兵”
每个士兵有了一个队伍中的唯一“位置” 位置是相对的，位置可以调整（how?） 如果设计一个按照位置进行的“游戏”，给定了位置就指定了人 按照上述观点，vector/list/one-dimensional array为什么被称为是 一种数据结构，它的“结构性”体现在哪里？

7 改变“位置”和改变“内容” How to exchange them?

8 如何理解以下文字？ 数组与循环？

9 Vector、Vector of vectors和Array有什么区别？

10 问题：如何访问“单个变量”、“向量”和“数组”？
问题：如何遍历“单个变量”、“向量”和“数组”？

11 问题：以下两者的区别何在？ 在书架中取一本书 在一桶纸杯中拿一个杯子 使用时的受限性：头存尾取 使用时的随意性：任意存取
在书架中取一本书 在一桶纸杯中拿一个杯子 代价在哪里？下标和“头尾” 使用时的受限性：头存尾取 使用时的随意性：任意存取 代价更高的数组才能实现如此的随意性 代价较低的队列就能实现受限的存取

12 两种用途非常广泛的特殊“vector”：队列、栈

13 我们再来理解以下文字： 从理解数据结构的“结构”角度出发，哪些词最为关键？

14 问题：为什么“树”也是一种数据结构？ 一种可以用来表达更为复杂的数据间“位置”关系（层次关系）的数据结构

15 树在内存中是如何实现的？ 128 76 402 128 76 Null Null 402 Null Null

16 第一步，将待排序数列表示为“二分搜索树”
和在Array中我们可以规定数据的“位置”一样，我们也可以在树中给数据“定位”，进而做一些有趣的事情 树排序： 第一步，将待排序数列表示为“二分搜索树”

17 第二步：以left-first traversal方式遍历树，标记出第二次出现的数
输出结果，一定是升序排列的！

18 相应的算法： 你能证明这个算法是正确的吗？

19 树结构和递归结构有着天然的联系！ 什么关系？
树结构和递归结构有着天然的联系！ 什么关系？

20

21

22

23

24 Once a person has understood the way variables are used in programming, he has understood the quintessence of programming. E. W. Dijkstra 精华，程序设计，就是对变量的处理

25 结束语 数据、数据类型和变量分别表示什么？三者 什么关系？ 什么是数据结构？数据类型和数据结构什么 关系？
为什么高级程序设计语言要提供“高级”数 据结构？ 程序员能否自行定义“数据类型”？

26 开放讨论题 请解读union数据结构：谈谈你对这个结构的认识，举例说明它的 用途和使用方法
尝试证明second visit traversal 算法的正确性（部分正确性）