• 熱門專題

數據結構隊列的鏈式實現

作者:  發布日期:2015-04-30 01:05:49
Tag標簽:鏈式  數據結構  隊列  
  • 隊列的鏈式實現

    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;
    }
    }
    
About IT165 - 廣告服務 - 隱私聲明 - 版權申明 - 免責條款 - 網站地圖 - 網友投稿 - 聯系方式
本站內容來自于互聯網,僅供用于網絡技術學習,學習中請遵循相關法律法規
彩票联盟网站 珠海市| 宁波市|