南京大学：《计算机问题求解》课程教学资源（课件讲稿）基本数据结构

计算机问题求解一论题2-11 基本的数据结构 2016年04月28日

计算机问题求解 – 论题2-11 - 基本的数据结构 2016年04月28日

问题：任意输入一行字符串，以#结束。输 出这个字符串的反串 Program reverse(input,output); var elements:array[O:n]of char; (*n is big enough*) index:int;length:int;c:char; begin 问题：N.Wirth说过 read(c);length:=0; 程序=算法+数据结构。 while (c<>'#)do 你能就这个例子解释这句 begin 话的含义吗？ elements[length]:=c; length :length+1; read(c); end for index:=length-1 to 0 do write(elements[index]); end

问题：任意输入一行字符串，以#结束。输 出这个字符串的反串 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 begin elements[length]:=c; length := length+1; read(c); end for index:=length-1 to 0 do write(elements[index]); end. 问题1：N.Wirth说过 程序=算法+数据结构。 你能就这个例子解释这句 话的含义吗？

问题2： 你能从上例中的”var elements:array[O:n]of char;"”以及某个 具体输入“damrngiz”中解释以下几个概念的关系吗？ 数据；数据类型；数据结构 我们引入Dynamic seti这个概念的用意是什么？

问题2： 你能从上例中的” var elements: array[0:n] of char; ”以及某个 具体输入“damrnqiz”中解释以下几个概念的关系吗？ 数据；数据类型；数据结构 我们引入Dynamic set这个概念的用意是什么？

SEARCH(S,k) A query that,given a set S and a key value k,returns a pointer x to an element 问题3：你 in S such that x.key =k,or NIL if no such element belongs to S. INSERT(S,x) A modifying operation that augments ement pointed to 除了能看出 by x.We usually a ded by the set imp DE 动态集合上 本质上，我们所采用 re- 的所有表达动态集合 x,not 常见的操作 的高级数据结构，定 S 外，能否看 义其上的操作，少不 element of S 出“结构” 了上述基本功能 SUCCES 来？ A query tro y is from a totally ordered set S, returns a pointer to the next ment in S,or NIL if x is the maximum element. PREDECESSOR(S,x) A query that,given an element x whose key is from a totally ordered set S, returns a pointer to the next smaller element in S,or NIL ifx is the minimum element

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

问题4：我们只能采用数组来组织和管理动态 集合吗？ Out Roughly,a stack is a set of objects which arrive at different points in time and are added to the set.When elements are deleted from the set, the object which was inserted last is removed first. A stack can be visualised as a pile of objects where objects can be added to or removed from the pile only from the top (see figure 2.3). Figure 2.3 Pictorial model of a stack

问题4：我们只能采用数组来组织和管理动态 集合吗？

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

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

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

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

stack:set of elements of type elemtype (elemtype is used to refer to the type of the individual elements in a stack. Elemtype can potentially be any defined type * Operations: procedure initialise(var S:stack); 数据结 This procedure assigns an empty stack to S. procedure push(var S:stack;a:elemtype); 构stack Stack S should not be full.This procedure adds the elemep the top of the stack. 的定义 procedure pop(var S:stack); 问题6：定义一 Stack S should not be empty.The top removed. 个数据结构，必 function top(S:stack):elemtype; 须定义哪些东西？ Stack S should be non-empty and this fe element of the stack S.The stack S is left unc type is a structured type,this function should be rewren a procedure,see note 1 of section 3.1.) function empty(S:stack):boolean; This function returns true if S is empty and false otherwise. function full(S:stack):boolean; If S is full this function returns a true value. Otherwise it returns a false value

数据结 构stack 的定义 问题 6：定义一 个数据结构，必 须定义哪些东西？

用高级语言提供的基本数据类型和数据结构来 实现在自定义结构中定义的数据和操作 ●。。9●● n last Figure 2.6 Array implementation of stacks

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

数据实现部分： const n (x n is the maximum size of a stack x) type stack record elements array [1..n]of elemtype; last 0..n (x 0 signifies an empty stack x) end;

数据实现部分：