数据结构基本知识.ppt

数据结构基础知识
熟识数据结构相关的概念、知识内容
熟记数据结构的基本操作及相应的代码实现
理解数据结构的逻辑结构,能根据题目要求选择合适的数据结构
掌握基本操作及数据结构的基本应用,熟练基本应用的程序设计
一、栈
1、栈的定义
栈是一种线性表,对它的插入和删除都限制地表的同一端进行。这一端叫做栈的“顶”,另一端则叫做栈的“底”。
特点:后进先出(LIFO)、或者先进后出(FILO)
通常栈可以用顺序的方式存储(数组),分配一块连续的存储区域存放栈中的表目,并用一个变量t指向当前栈顶(如下图)。
假设栈中表目数的上限为m,所有表目都具有同一类型stype,则可以用下列方式定义栈:
Const
m=栈表目数的上限;
Var
s: array[1‥m] of stype ;{栈}
t: integer; {栈顶指针,初始值为0}
注意:不一定进栈结束后才出栈,进出栈可交叉进行。
2、栈的基本操作
栈的基本操作包括初始化(init)、进栈(push)、出栈(pop)和读取栈顶元素(top)四种。
1) 过程init(s,t)
procedure init;
begin
t:=0;
end;
2)、过程push(x)—往栈s中压入一个值为x的数据:
procedure push( x:stype);
begin
t←t+1;
s[t]←x; {x入栈}
end;{Push}
3)、函数pop—从栈中弹出一个表目
function pop :stype;
begin
pop←s[t]; {栈顶元素出栈}
t←t-1; {指针下移}
end;{pop}
4)、函数top—读栈顶元素
function top :stype;
begin
if t=0 then writeln (’stack empty’)
else top←s[t]; {返回栈顶元素}
end;{top}
【竞赛试题】
①以下哪一个不是栈的基本运算( C) (NOIP7)
A)删除栈顶元素 B)删除栈底的元素
C)判断栈是否为空 D)将栈置为空栈
②一个栈的输入顺序为1、2、3、4、5,下列序列中可能是栈的输出序列是( BCD )。
(A)54312 (B)24315
(C)21543 (D)12543
③若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是(C ) (NOIP7)
A)i B)n-1 C)n-i+1 D)不确定
n-i+1 栈的排列遵循先进后(即后进先出)出的原则因为P1是n,是出栈的第一个数字,说明在n之前进栈的数字都没有出栈,所以这个顺序是确定的。还可以知道,最后出栈的一定是数字1,也就是Pn。代入这个式子,是正确的。
4、设有一个顺序栈S,元素S1, S2, S3, S4, S5, S6依次进栈,如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1,则顺序栈的容量至少应为多少?A
3 B) 4 C) 5 D) 6
5、向顺序栈中压入新元素时,应当( A )。
,再存入元素
,再移动栈顶指针


二、队列
1 队列的定义
所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个队尾指针w指向队尾元素,即w总是指向最后被插入的元素;允许删除的一端称为队首,通常也用一个队首指针t指向排头元素。初始时t=w=0(如下图)。
3
2
6
5
4
1
9
队列头 t
队列尾 w
当他t>w时,队列空
队列数组a下标: 1 2 3 4 5 6 7……
我们按照如下方式定义队列:
Const
m=队列元素的上限;
Type
equeue=array[1…m] of qtype; {队列的类型定义}
Var
q:equeue; {队列}
t,w:integer; {队尾指针和队首指针}
2、队列的基本运算
队列的运算主要有两种:入队(aDD)和出队(DEL)
1、过程ADD(x)—在队列q的尾端插入元素x
procedure ADD( x:qtyper);
begin
{后移队尾指针并插入元素x}
w:=w+1;
q[w]←x;
end;{ADD}