沈阳网站建设的公司,模板 网站 教程,e通网网站建设,河北省邢台市一、栈的定义与特点 栈#xff1a;只能在表的一端#xff08;栈顶#xff09;进行插入和删除运算的线性表 逻辑结构 与线性表相同#xff0c;仍为一对一关系 存储结构 用顺序栈和链栈存储均可#xff0c;但顺序栈更常见 访问结点时依照后进先出只能在表的一端栈顶进行插入和删除运算的线性表 逻辑结构 与线性表相同仍为一对一关系 存储结构 用顺序栈和链栈存储均可但顺序栈更常见 访问结点时依照后进先出LIFO或先进后出FILO的原则 进栈------压入-----push() 出栈-----弹出-----pop()
栈与线性表-仅在于运算规则不同 线性表: 逻辑结构一对一 存储结构顺序表、链表 运算规则 顺序表——随机存取 链表——顺序存取 栈 逻辑结构一对一 存储结构顺序栈、链栈 运算规则后进先出先进后出
栈顶线性表允许进行插入删除的那一端。
栈底固定的不允许进行插入和删除的另一端。
空栈不含任何元素的空表。
栈的数学性质n个不同元素进栈出栈元素不同排列的个数为1/n1)C ~2n~ *n
栈的抽象数据类型 ADT Stack { 数据对象D{ai| ai∈ElemSet, i1,2,...,n, n≥0 } 数据关系R1{ ai-1,ai| ,ai-1,ai∈D, i2,...,n } 约定an端为栈顶a1端为栈底。 基本操作 InitStack(S) 操作结果构造一个空栈 S。 DestroyStack(S) 初始条件栈 S 已存在。 操作结果栈 S 被销毁。 ClearStack(S) 初始条件栈 S 已存在。 操作结果将 S 清为空栈。 StackEmpty(S) 初始条件栈 S 已存在。 操作结果若栈 S 为空栈则返回TRUE否则返回FALSE。 StackLength(S) 初始条件栈 S 已存在。 操作结果返回栈 S 中元素个数即栈的长度。 GetTop(S, e) 初始条件栈 S 已存在且非空。 操作结果用 e 返回S的栈顶元素。 Push(S, e) 初始条件栈 S 已存在。 操作结果插入元素 e 为新的栈顶元素。 Pop(S, e) 初始条件栈 S 已存在且非空。 操作结果删除 S 的栈顶元素并用 e 返 回其值。 } ADT Stack
二、栈的顺序存储结构
顺序栈的存储方式 同一般线性表的顺序存储结构完全相同利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。 附设top指针指示栈顶元素在顺序栈中的位置。 另设base指针指示栈底元素在顺序栈中的位置。 为了方便操作通常top指示真正的栈顶元素之上的下标地址。 另外用stacksize表示栈可使用的最大容量。
顺序栈的表示
#define MAXSIZE 100 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack;
顺序栈初始化构造一个空栈 (1)分配空间并检查空间是否分配失败若失败则返回错误 (2)设置栈底和栈顶指针S.top S.base; (3)设置栈大小
Status InitStack( SqStack S ){ S.base new SElemType[MAXSIZE] if( !S.base ) return OVERFLOW; S.top S.base; S.stacksize MAXSIZE; return OK; } 判断顺序栈是否为空 bool StackEmpty( SqStack S ){ if(S.top S.base) return true; else return false; } 求顺序栈的长度 int StackLength( SqStack S ){ return S.top – S.base; } 清空顺序栈 Status ClearStack( SqStack S ){ if( S.base ) S.top S.base; return OK; }
销毁顺序栈 Status DestroyStack( SqStack S ){ if( S.base ){ delete S.base ; S.stacksize 0; S.base S.top NULL; } return OK; } 顺序栈进栈 (1)判断是否栈满若满则出错 (2)元素e压入栈顶 (3)栈顶指针加1 Status Push( SqStack S, SElemType e){ if( S.top - S.base S.stacksize ) // 栈满 return ERROR; *S.tope; return OK; } 顺序栈出栈 (1)判断是否栈空若空则出错 (2)栈顶指针减1 (3)获取栈顶元素e Status Pop( SqStack S, SElemType e){ if( S.top S.base ) // 栈空 return ERROR; e *--S.top; return OK; } 取顺序栈栈顶元素 判断是否空栈若空则返回错误 否则通过栈顶指针获取栈顶元素 Status GetTop( SqStack S, SElemType e){ if( S.top S.base ) return ERROR; // 栈空 e *( S.top – 1 ); return OK; }
三、共享栈 将编号为0和1的两个栈存放于一个数组空间V[m]中栈底分别处于数组的两端。当第0号栈的栈 顶指针top[0]等于-1时该栈为空当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。 栈空top[i] bot[i] i表示栈的编号 栈满top[0]1top[1] 或top[1]-1top[0] 共享栈定义 #define Maxsize 100 typedef struct{ int top[2], bot[2]; //栈顶和栈底指针 SElemType data[Maxsize]; //栈数组 }DblStack;
四、链栈 采用链式结构存储的栈称为链栈是运算受限的单链表只能在链表头部进行操作故没有必要附加头结点。栈顶指针就是链表的头指针。 typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack; 链栈初始化 void InitStack(LinkStack S ){ //构造一个空栈栈顶指针置为空 SNULL; }链栈判空 Status StackEmpty(LinkStack S){ if (SNULL) return TRUE; else return FALSE; } 链栈进栈 Status Push(LinkStack S , SElemType e){ pnew StackNode; //生成新结点p if (!p) exit(OVERFLOW); p-datae; p-nextS; //??为什么这里不是S-next呢 Sp; return OK; } 链栈出栈 Status Pop (LinkStack S,SElemType e){ if (SNULL) return ERROR; e S- data; p S; S S- next; delete p; return OK; } 取栈顶元素 SElemType GetTop(LinkStack S){ if (SNULL) exit(1) else return S–data; }
链栈的特点
1不存在栈满上溢的情况。
2栈顶指针就是链表头指针。 3头插法建立单链表相当于进栈。 4单链表的删除相当于出栈。
