首页 > 数据库 > Sybase > 正文
数据结构-队列的链式实现
2015-04-29       个评论    来源:王照陆博客  
收藏    我要投稿

队列的链式实现

1 队列的链式存储表示
队列的链式存储结构简称为链队列,它是限制在表头进行删除操作和表尾进行插入操作的单链表。
需要两类不同的结点:数据元素结点,队列的队首指针和队尾指针的结点
指针结点类型定义:

typedef struct link_queue
{   QNode  *front ,  *rear ;
}LinkQueue ;

2 链队运算及指针变化
链队的操作实际上是单链表的操作,只不过是删除在表头进行,插入在表尾进行。插入、删除时分别修改不同的指针

3    链队列的基本操作
⑴ 链队列的初始化
Status Init_LinkQueue(LinkQueue  *Q )
{   /*成功返回OK,否则返回ERROR*/
   QNode  *p ;
p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */
if(p==NULL) return ERROR;
p->next=NULL ;
Q->front=Q->rear=p ; 
return OK;
}
⑵ 链队列的入队操作
       在已知队列的队尾插入一个元素e ,即修改队尾指针(Q.rear)。
Status  Insert_LinkQueue(LinkQueue  *Q , ElemType  e)
      /*  将数据元素e插入到链队列Q的队尾  */
{  QNode  *p ;
   p=(QNode *)malloc(sizeof(QNode)) ;
if (!p)  return  ERROR;
/*  申请新结点失败,返回错误标志 */
p->data=e ; p->next=NULL ;       /*  形成新结点 */
Q->rear->next=p ;  Q->rear=p ;  /* 新结点插入到队尾  */
return OK;
}
链队列的出队操作
Status  Delete_LinkQueue(LinkQueue  *Q, ElemType *x)
   {   QNode *p ;
if  (Q->front==Q->rear)  return ERROR ;   /* 队空  */
p=Q->front->next ;   /*  取队首结点  */
*x=p->data ; 
Q->front->next=p->next ;      /*  修改队首指针  */
if  (p==Q->rear)  Q->rear=Q->front ;
     /*  当队列只有一个结点时应防止丢失队尾指针  */
    free(p) ;   
return OK ; 
}
⑷ 链队列的撤消
void  Destroy_LinkQueue(LinkQueue  *Q )
   /*  将链队列Q的队首元素出队  */
{   while  (Q->front!=NULL)
{Q-> rear= Q-> front->next;   
      /*  令尾指针指向队列的第一个结点   */
free(Q-> front);      /*  每次释放一个结点  */ 
    /*  第一次是头结点,以后是元素结点  */
Q-> front= Q-> rear;
}
}
点击复制链接 与好友分享!回本站首页
上一篇:after触发器
下一篇:数据结构-逻辑结构和存储结构
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站