二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(10)

if ( s==NULL ) return false; // 栈空 // 删除栈顶元素

p = s;

s = s->next;

x = p->data;

free ( p );

return true;

}

f) 栈顶元素

前提：栈非空。

bool Top ( LinkList &s, DataType &x ) {

if ( s==NULL ) return false; // 栈空 x = s->data;

return true;

}

顺序栈

存储结构

类似于顺序表，插入和删除操作固定于表尾。 类型定义

7简单说，“数组 + 长度”。 7 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

const int MAXSIZE = 栈的最大容量；

typedef struct {

DataType elem[MAXSIZE];

int top;

} SqStack;

基本形态

g) 栈空

条件 s.top == 0;

h) 栈满

条件 s.top == MAXSIZE

i) 栈不空、不满

基本算法

j) 入栈 Push (&s, x)

前提：栈不满

bool Push ( SqStack& s, DataType x )

{

if ( s.top == MAXSIZE ) return false; // 栈满 s.elem[top] = x; // 或者s.elem[top++] = x; top++;// 代替这两行

return true;

}

k) 出栈 Pop (&s, &x)

前提：栈非空

bool Pop ( SqStack &s, DataType &x )

{

if ( s.top==0 ) return false;

top--; // 可用x=s.elem[--top]; x = s.elem[top]; // 代替这两行

return true;

}

l) 栈顶元素

前提：栈非空

s.elem[top-1] 即是。

队列

队列，队头，队尾，空队列，先进先出(FIFO)。

链队列：队列的链式存储结构。

循环队列：队列的顺序存储结构之一。

链队列

存储结构

简而言之，“单链表 + 尾指针”。

类型定义

课本P61。

typedef struct {

LinkList front;

LinkList rear;

} LinkQueue;

基本形态

队列空：Q.front==Q.rear。

非空队列。

基本算法

m) 入队列

课本P62。插入队尾，注意保持Q.rear指向队尾。

n) 出队列

课本P62。删除队头元素，

特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。

循环队列

存储结构

9简单说，“数组 + 头、尾位置”。

类型定义

const int MAXSIZE = 队列最大容量;

typedef struct {

DataType elem[MAXSIZE];

int front, rear; // 队头、队尾位置

} SqQueue;

基本形态

通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 [front, rear)。

o) 队列空

条件：Q.front == Q.rear。

不能出队列。

p) 队列满

条件：(Q.rear+1)%MAXSIZE == Q.front （少用一个元素时）。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-10.html