注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

SINOBANJO

IN GOD WE TRUST ! ~ ClueeZhuo

 
 
 
 
 

日志

 
 

SINOBANJO - 数据结构之栈和队列  

2014-09-03 01:29:27|  分类: 班卓数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

栈、队列

栈的基本概念

栈(Stack)是运算受限的线性表,这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶,另一端称为栈底。不含任何元素的栈称为空栈。处于栈顶位置的元素称为栈顶元素。栈的修改原则是后进先出(Last In First Out,因此栈又栈又称为后进先出线性表。栈的插入和删除运算分别称为进栈出栈SINOBANJO - 数据结构之栈和队列 - 班卓 - SINOBANJO

 

栈的顺序实现

初始化

int InitStack(SeqStk *stk)

{

      stk top =0;

      return 1;

}

 

判栈空

int EmptyStack(SeqStk *stk)

{

      //若栈为空,则返回值1,否则返回值0

      if(stktop = =0){return 1;}

      else{return 0;}

}

 

进栈

int Push(SeqStk *stk ,DataType x)

{

      if(stktop = =maxsize-1){error("栈已满"); return 0;}

      else

      {

           stktop++

           stkdata[stktop]=x;

           return 1;

      }

}

 

出栈

int Pop(SeqStk *stk)

{

      if(EmptyStack(stk)){error("下溢");return 0;}

      else{stktop--;return 1;}

}

 

取栈顶元素

DataType GetTop(SeqStk *stk)

{

      if(EmptyData(stk)){return NullData;}

      else{return stkdata[stktop];}

}

 

栈的链接实现

初始化

void InitStack(LkStk *LS){

      LS=(LkStk *)malloc(sizeof(LkStk));

      LSnext =NULL;

}

判栈空

int EmptyStack(LkStk *LS)

{

      if(LSnext = = NULL){ return 1;}

      else{return 0;}

}

 

进栈

void Push(LkStk *LS ,DataType x)

{

      LkStk *temp;

      temp=(LkStk * ) malloc(sizeof(LkStk));//temp指向申请的新结点

      tempdata=x;

      tempnext=LSnext//tempnext域指向原来的栈顶结点

      LSnext=temp

}

 

出栈

int Pop (LkStk *LS)

{

      LkStk *temp;

      if(!EmptyStack(LS))

      {

           temp=LSnext

           LSnext=tempnext//原栈顶的下个节点成为新的栈顶

           free(temp);

           return 1;

      }

      else{ return 0;}

}

取栈顶元素

DataType GetTop(LkStk *LS){

      if(!EmptyStack(LS)){ return LSnextdata} else{ return NULLData;}

}

队列的基本概念

队列是一种插入和删除操作受限的线性表,它只允许在表的一端进行插入,另一端进行删除。允许插入元素的一端称为队列尾端,允许删除元素的一端称为队列首部。队列是一种先进先出(First In Firs Out的线性表。循环队列满条件为:(CQ.rear +1 )%maxsize = =CQ.front)成立。循环队列空条件:(CQ.rear==CQ.front)成立。

 

循环队列的基本运算

初始化

void InitQueue (CycQue CQ)

{

      CQ.front=0;CQ.rear=0;

}

 

判队列空

int EmptyQueue(CycQue CQ)

{

      if(CQ.rear==CQ.front){return 1;}

      else{return 0;}

}

 

入队列

int EnQueue(CycQue CQ ,DataType x)

{

       if((CQ.rear+1)%maxsize = =CQ.front){error("队列满");return 0;}

       else{

       CQ.rear=(CQ.rear+1)%maxsize;

       CQ.data[CQ.rear]=x;

       return 1;

       }

}

出队列

int OutQueue(CycQue CQ)

{

       if(EmptyQueue(CQ)){error("队列空");return 0;}

       else{CQ.front=(CQ.front+1)%maxsize; return 1;}

}

 

取队列首元素

DataType GetHead(CycQue CQ)

{

       if(EmptyQueue(CQ)){return NULLData;}

       else{CQ.data[(CQ.front+1)%maxsize];}

}

链队列的基本运算

由于链接实现需要动态申请空间,故链队列在一定范围内不会出现队列满的情况,当(LQ.front==LQ.rear)成立时,队列中无数据元素,此时队列为空。

初始化

void InitQueue(LkQue *LQ)

{

       LkQueNode *temp;

       temp=(LkQueNode *) malloc(sizeof(LkQueNode));//生成队列头结点

       LQfront=temp;//队列头指针指向队列头结点

       LQrear=temp;//队列尾指针指向队列尾结点

       (LQfront)next=NULL;

}

判队列空

int EmptyQueue(LkQue LQ)

{

       if(LQ.rear==LQ.front){return 1;}

       else{return 0;}

}

入队列

void EnQueue(LkQue *LQ ,DataType x)

{

       LkQueNode *temp;

       temp=(LkQueNode * ) malloc (sizeof(LkQueNode));

       tempdata=x

       tempnext=NULL;

       (LQrear)next=temp;//新节点入队列

       LQrear=temp//置新的队列尾节点

}

 

出队列

int OutQueue(LkQue *LQ)

{

       LkQueNode *temp;

       if(EmptyQueue(LQ)){error("队列空"); return 0;}

       else

       {

              temp=(LQfront)next;//temp指向队列的首结点

              (LQfront)next=tempnext;//修改头结点的指针域指向新的首结点

              if(tempnext==NULL){LQrear=LQfront}

              free(temp);

              return 1;

       }

}

 

就写到这吧,TKS.

  评论这张
 
阅读(47)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017