计算机问题求解 – 论题2-11 - 基本的数据结构 2018年05月09日

问题：任意输入一行字符串，以#结束。输出这个字符串的反串 Program reverse(input, output); var elements: array[0:n] of char; (*n is big enough*) index: int; length: int; c: char; begin read(c); length:=0; while (c<>’#’) do elements[length]:=c; length := length+1; read(c); end for index:=length-1 to 0 do write(elements[index]); end. 问题1：N.Wirth说过程序=算法+数据结构。 你能就这个例子解释这句话的含义吗？ 提醒大家：1，数组存放是对数据的组织管理方式，算法很简单；2，多个对象的组织和管理，通常用动态集合这个词来解读；3，不同的组织方式，可能带来算法的变化和效率的变化。 用栈来组织和管理，解 我们用不同的数据组织形式来进行动态集合的实现，会带来不同的思维方式； 分析字符类型和数组、栈的关系，解释什么叫数据结构 逻辑结构：如何建议元素之间的关系；如何操纵这些元素； 物理结构：观察它们在计算机中的物理存储结构，理解访问这些元素的代价 抽象数据类型： ADT：什么叫定义一个数据结构？以栈为例；什么叫实现一个数据结构？用数组实现栈 ADT定义了一个数学模型，如何去保障这个模型在实现阶段没有错误？ADT的形式规约 使用ADT的若干好处 指针的本质含义：地址并非专指物理地址，任何能够检索到对象的数据，均可以是地址； 栈的指针实现技术； 队列数据结构：定义、队列的形式规约；队列的指针实现；队列的数组实现； 表数据结构：定义、表的形式规约；表的指针实现；表的数组实现； 树数据结构：定义、形式规约；指针实现；可以采用数组实现吗？

问题2： 我们引入Dynamic set这个概念的用意是什么？ 你能从上例中的” var elements: array[0:n] of char; ”以及某个具体输入“damrnqiz”中解释以下几个概念的关系吗？ 数据；数据类型；数据结构 多个对象的数据，需要有效组织和管理：数据结构；从一个集合的角度去观察，定义集合元素类型，可以开展的组织动作 描述对象的数据：类型：从一个个体的角度去观察； 集合：数学概念；动态集合：计算过程中的运行的模型 我们引入Dynamic set这个概念的用意是什么？

本质上，我们所采用的所有表达动态集合的高级数据结构，定义其上的操作，少不了上述基本功能 问题3：你除了能看出动态集合上常见的操作外，能否看出“结构”来？ 本质上，我们所采用的所有表达动态集合的高级数据结构，定义其上的操作，少不了上述基本功能 元素之间的关系！

问题4：我们只能采用数组来组织和管理动态集合吗？ 不同的组织方式，可能带来算法的变化和效率的变化。 用栈来组织和管理，解 我们用不同的数据组织形式来进行动态集合的实现，会带来不同的思维方式； 分析字符类型和数组、栈的关系，解释什么叫数据结构 逻辑结构：如何建议元素之间的关系；如何操纵这些元素； 物理结构：观察它们在计算机中的物理存储结构，理解访问这些元素的代价 抽象数据类型： ADT：什么叫定义一个数据结构？以栈为例；什么叫实现一个数据结构？用数组实现栈 ADT定义了一个数学模型，如何去保障这个模型在实现阶段没有错误？ADT的形式规约 使用ADT的若干好处 指针的本质含义：地址并非专指物理地址，任何能够检索到对象的数据，均可以是地址； 栈的指针实现技术； 队列数据结构：定义、队列的形式规约；队列的指针实现；队列的数组实现； 表数据结构：定义、表的形式规约；表的指针实现；表的数组实现； 树数据结构：定义、形式规约；指针实现；可以采用数组实现吗？

其实，动态集合的不同组织方式，可能带来算法的变化和效率的变化 Program reverse(input, output) var s: stack; c: char begin initialize(s); read (c); while c<>”#” do push(s,c);read(c); end while not empty(s) do write(top(s)); pop(s); 定义栈的管理动作：initialize(S):创建一个栈； push(S,c):将c压入栈S中; top(S):栈顶元素； pop(S):将栈顶元素去除; empty(S):判定S是否为空 full(s):判断S是否满 我们用不同的数据组织形式来进行动态集合的实现，会带来不同的思维方式；

问题5：至此，你必须能清楚的理解什么叫“定义并实现一个数据结构” 但是，上述程序是无法执行的： 大多数语言并没有像提供array, record, pointer那样提供stack这样的语言设施供我们使用： 如此的数据抽象，不是都被语言支持 我们还会根据应用需求、管理需求进行这样那样的抽象，构造自己的数据管理方式： 队列、链表、树、图…… 问题5：至此，你必须能清楚的理解什么叫“定义并实现一个数据结构”

问题6：定义一个数据结构，必须定义哪些东西？ 数据结构stack的定义 问题6：定义一个数据结构，必须定义哪些东西？ 数据+操作 操作主要反映基本操作+特定操作

用高级语言提供的基本数据类型和数据结构来实现在自定义结构中定义的数据和操作

数据实现部分：

操作实现部分 一旦我们小心翼翼地完成了定义和实现，我们就可以发布这个“数据结构”为一个“数据类型”供别的程序员直接使用，他们不用关心这个类型的所有实现细节，就像我们自己使用int类型一样！ 这个数据结构的定义中包含了动态集合中的元素逻辑结构和管理方式；实现中规定了物理结构和管理方式。

Program reverse(input, output) var s: stack; c: char begin initialize(s); read (c); while c<>”#” do push(s,c);read(c); end while not empty(s) do write(top(s)); pop(s);

实际上，我们还可以采用不同的实现方式来实现某个数据管理方式！ 难道我们就定义了两个不同的stack了吗？

如果我们在构造自己的数据组织方式时，写出了一个关于这个方式的“约定”，而暂时没有涉及实现细节，甚至不再关心实现细节而交由其他人员实现时，我们写出来的“约定”就有了新名词： 抽象数据类型：ADT

完整的stack的ADT

自然语言能够描述清楚ADT中各个成分吗？ 狭义的程序设计中难得一见的科学内涵！

Stack的数据部分的形式约束 规约的数据部分 针对数据的规约 生命周期内保持

Stack操作部分的形式约束

Stack操作部分的形式约束

这些数据规约和操作规约明确了这个数据结构的：成员数据类型、组织方式、使用方式 Stack操作部分的形式约束 这些数据规约和操作规约明确了这个数据结构的：成员数据类型、组织方式、使用方式 但这些规约和具体的数据结构实现无关：数组方式？链表方式？ 实现这个ADT时：必须验证实现方法保持了这些约束的成立

这个规约和栈ADT中push的规约是等价的吗？ a-stack: 一种用数组实现的栈结构 这个规约和栈ADT中push的规约是等价的吗？ 必须要证明

下面的函数f是干什么的？ 建立了验证a-stack规约是否符合stack ADT规约的基础

a-stack中push操作的验证 ∀𝑎1∈𝑎 − 𝑠 𝑡𝑎𝑐𝑘: pre−condition s.push f a1 ,b ⇒pre−condition(a.push a1,b ) ∀𝑎1∈𝑎 − 𝑠 𝑡𝑎𝑐𝑘: pre−condition s.push f a1 ,b ) and p𝑜𝑠𝑡−condition(a.push a1,b ⇒ post−condition(s.push(f a1 ,b)

pre−condition s.push f a1 ,b ≡|elems|<max |elems|=last ∀𝑎1∈𝑎 − 𝑠 𝑡𝑎𝑐𝑘: pre−condition s.push f a1 ,b ⇒pre−condition(a.push a1,b ) pre−condition s.push f a1 ,b ≡|elems|<max |elems|=last Max=n under f Last<n pre−condition(a.push a1,b ) = T

∀𝑎1∈𝑎 − 𝑠 𝑡𝑎𝑐𝑘: pre−condition s. push f a1 ,b and p𝑜𝑠𝑡−condition(a ∀𝑎1∈𝑎 − 𝑠 𝑡𝑎𝑐𝑘: pre−condition s.push f a1 ,b and p𝑜𝑠𝑡−condition(a.push a1,b ⇒ post−condition(s.push(f a1 ,b) pre−condition s.push f a1 ,b ≡|elems|<max p𝑜𝑠𝑡−condition(a.push a1,b )≡ last’=last+1 and elements’[last’]=b c ′ =c+1 and (elements ′ last ′ ,last) ∈𝑒𝑙𝑒𝑚 𝑠 ′ (c’>c and(b,c)∈elems’) post−condition(s.push(f a1 ,b)成立

以定义ADT为目标去定义数据结构的好处： 关注分离 信息隐藏 模块化设计 可以加载形式化研究

问题8： 你能举出一些例子，说 明queue这种结构中哪 些数据成分必须有？它 们必须满足什么性质？ 哪些操作必须提供，它 们又必须遵循什么约定？

问题9： 栈与队列的本质差别是什么？ 为什么我们需要这种差别？ FIFO； 讨论题2：递归调用在程序运行时，常常利用栈数据结构。请解释一下为什么？

问题10: 你觉得在我们的讨论的“结 构”的背后是否有什么基本 的数学概念吗？ 数据和处理数据的方法：一个封闭的系统，封闭在这个动态集合中 代数系统

链表：一切操作均围绕指针 问题11： 这个结构有什么不便之处吗？ 数据的动态组织较为方便，但是数据的访问不够方便：worst case是n级别 问题11： 这个结构有什么不便之处吗？

如果给定的是key，而不是一个pointer，worst case是theta（n） 问题12： 删除一个对象的代价是多少？

问题13： 你能就下两例说说看，指针到底是什么？ 数据的位置信息

进一步的改进 问题14; 为什么是“改进”？ 监控“边界条件”

两列表单数组实现 基本原理：在一个数组空间维护两个链表，“实际数据”和“可用空间”。“此消彼长” 问题15： 你能解释一下 这几个图吗？

根树: 如何从链表的角度看它? Level 0 Root Inner node Leaf Level 1 Branching node Height=3 Level 2 Level 3 如果任意结点最多有两个子结点, 则该根树成为二叉树(binary tree), 显然用指针实现链表的方法很容易扩展到二叉树

这其实意味着: 即使问题逻辑需要多叉树, 我们也可以将其转换为二叉树来实现。

Open topics 用两个 queue 模拟一个 stack，要求尽可能高效，且不使用额外空间（可使用常数个额外变量）。 证明上述算法的正确性。

课外作业 TC pp.235-: ex.10.1-4; 10.1-5; 10.1-6 TC pp.240-: ex.10.2-1; 10.2-2; 10.2-3; 10.2-6; TC pp.245-: ex.10.3-4; 10.3-5; TC pp.248-: ex.10.4-2; 10.4-3; 10.4-4 TC pp.249-: prob.10-3