软件发布| 专题库| 优优资讯| 苹果专区| 安卓专区| 软件下载| 首页
优优资讯 电脑教程 安卓教程 安卓攻略 苹果教程 苹果攻略 新闻资讯

数据结构基础之栈的顺序存储表示与实现

时间:2015-06-10 来源:本站整理 我要评论

  一、栈的定义

  栈是限定仅在表尾进行插入或删除操作的线性表。

  栈的表尾称为栈顶,表头称为栈底,不含元素的空表称为空栈。

  栈的抽象数据类型定义

  ADT Stack{

  数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}

  数据关系:R1={<ai-1,ai>|ai-1,ai(- D,i=2,...,n}

  基本操作:

  InitStack(&S) 构造一个空栈S

  DestroyStack(&S) 栈S存在则栈S被销毁

  ClearStack(&S) 栈S存在则清为空栈

  StackEmpty(S) 栈S存在则返回TRUE,否则FALSE

  StackLength(S) 栈S存在则返回S的元素个数,即栈的长度

  GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素

  Push(&S,e) 栈S存在则插入元素e为新的栈顶元素

  Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值

  StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败

  }ADT Stack

  二、栈的表示和实现

  栈的存储方式:

  1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置

  2、链栈:利用链表实现

  顺序栈的类C语言定义:

  typedef struct{

  SElemType *base;

  SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空

  int StackSize; //栈的当前可使用的最大容量.

  }SqStack;

  顺序栈的的模块说明:

  struct STACK {

  SElemType *base;

  SElemType *top;

  int stacksize;

  };

  typedef struct STACK Sqstack;

  Status InitStack(SqStack &S);

  Status DestroyStack(SqStack &S);

  Status ClearStack(SqStack &S);

  Status StackEmpty(SqStack S);

  int StackLength(SqStack S);

  Status GetTop(SqStack S,SElemType &e);

  Status Push(SqStack &S,SElemType e);

  Status Pop(SqStack &S,SElemType &e);

  Status StackTraverse(SqStack S,Status (*visit)());

  Status InitStack(SqStack &S) {

  S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));

  if(!S.base)exit(OVERFLOW);

  S.top=S.base;

  S.stacksize=STACK_INI_SIZE;

  return OK;

  }//IniStack

  Status DestroyStack(SqStack &S); {

  }//DestroyStack

  Status ClearStack(SqStack &S); {

  S.top=S.base;

  } //ClearStack

  Status StackEmpty(SqStack S); {

  if(S.top==S.base) return TRUE;

  else return FALSE;

  } //StackEmpty

  int StackLength(SqStack S); {

  int i; SElemType *p;

  i=0;

  p=S.top;

  while(p!=S.base) {p++; i++; }

  } //stackLength

  Status GetTop(SqStack S,SElemType &e); {

  if(S.top==S.base) return ERROR;

  e=*(S.top-1);

  return OK;

  } //GetTop

  Status Push(SqStack &S,SElemType e); {

  if(S.top - s.base>=S.stacksize) {

  S.base=(ElemType *) realloc(S.base,

  (S.stacksize + STACKINCREMENT) * sizeof(ElemType));

  if(!S.base)exit(OVERFLOW);

  S.top=S.base+S.stacksize;

  S.stacksize+=STACKINCREMENT;

  }

  *S.top++=e;

  return OK;

  } //Push

  Status Pop(SqStack &S,SElemType &e); {

  if(S.top==S.base)

  return ERROR;

  e=*--S.top;

  return OK;

  }//Pop

  Status StackTraverse(SqStack S,Status (*visit)()); {

  }//StackTraverse

  以上伪代码的C语言源码

  三、总结

  栈的定义

  栈的顺序存储实现
 

用户评论

(已有0条评论)
表情
注:您的评论需要经过审核才能显示哦,请文明发言!
还没有评论,快来抢沙发吧!
快速检索
0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z