其实，动态集合的不同组织方式，可能带来 算法的变化和效率的变化 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;
数据实现部分：