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

数据结构基础之队列的定义与实现方法

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

一、队列的定义:
       队列是一种先进先出的线性表。它只允许在表的一端进行插入,而在另一端删除元素。象日常生活中的排队,最早入队的最早离开。
      在队列中,允许插入的的一端叫队尾,允许删除的一端则称为队头。

      抽象数据类型队列:
      ADT Queue{
      数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
      数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
      基本操作:
      InitQueue(&Q) 构造一个空队列Q
      Destroyqueue(&Q) 队列Q存在则销毁Q
      ClearQueue(&Q) 队列Q存在则将Q清为空队列
      QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
      QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
      GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
      EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
      DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
      QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
      }ADT Queue
二、链队列-队列的链式表示和实现

      用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。

 

 

 

 

Q.front ->

 

|

 

 

 

\|/

 

 

1

|

队头

 

 

\|/

 

 

2

|

 

 

 

\|/

 

 

3

|

 

 

 

\|/
\|/

 

Q.rear ->

9

/\

队尾

 

 

 

 

Q.front ->

 

|

 

 

 

\|/

 

 

1

|

队头

 

 

\|/

 

 

2

|

 

 

 

\|/

 

 

3

|

 

 

 

\|/
\|/

 

Q.rear ->

9

/\

队尾

链队列表示和实现:
      //存储表示
      typedef struct QNode{
      QElemType data;
      struct QNode *next;
      }QNode,*QueuePtr;
      typedef struct{
      QueuePtr front;
      QueuePtr rear;
      }LinkQueue;
      //操作说明
      Status InitQueue(LinkQueue &Q)
      //构造一个空队列Q
      Status Destroyqueue(LinkQueue &Q)
      //队列Q存在则销毁Q
      Status ClearQueue(LinkQueue &Q)
      //队列Q存在则将Q清为空队列
      Status QueueEmpty(LinkQueue Q)
      // 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
      Status QueueLenght(LinkQueue Q)
      // 队列Q存在,返回Q的元素个数,即队列的长度
      Status GetHead(LinkQueue Q,QElemType &e)
      //Q为非空队列,用e返回Q的队头元素
      Status EnQueue(LinkQueue &Q,QElemType e)
      //队列Q存在,插入元素e为Q的队尾元素
      Status DeQueue(LinkQueue &Q,QElemType &e)
      //Q为非空队列,删除Q的队头元素,并用e返回其值
      Status QueueTraverse(LinkQueue Q,QElemType vivsit())
      //Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败
      //操作的实现
      Status InitQueue(LinkQueue &Q) {
      //构造一个空队列Q
      Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
      if(!Q.front)exit(OVERFLOW);
      Q.front->next=NULL;
      return OK;}
      Status Destroyqueue(LinkQueue &Q) {
      //队列Q存在则销毁Q
      while(Q.front){
      Q.rear=Q.front->next;
      free(Q.front);
      Q.front=Q.rear;
      }
      return OK;}
      Status EnQueue(LinkQueue &Q,QElemType e) {
      //队列Q存在,插入元素e为Q的队尾元素
      p=(QueuePtr)malloc(sizeof(QNode));
      if(!p) exit(OVERFLOW);
      p->data=e;p->next=NULL;
      Q.rear->next=p;
      Q.rear=p;
      return OK;}
      Status DeQueue(LinkQueue &Q,QElemType &e) {
      //Q为非空队列,删除Q的队头元素,并用e返回其值
      if(Q.front==Q.rear)return ERROR;
      p=Q.front->next;
      e=p->data;
      Q.front->next=p->next;
      if(Q.rear==p)Q.rear=Q.front;
      free(p);
      return OK;}
三、总结

      链队列的存储表示
      链队列的操作及实现


用户评论

(已有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