天天看點

循環連結清單、雙向連結清單

循環連結清單

    最後一個元素的指針域不是空,而是指向了頭結點。

  1. //判斷表空由 
  2. L->next == NULL; 
  3. //變為 
  4. L->next == L; 
  5. //判斷表尾由 
  6. p->next == NULL; 
  7. //變為 
  8. p->next == L; 

    此時我們更多使用指向最後一個元素的尾指針,因為這個指針通路第一個元素和最後一個元素時的時間複雜度都是常數級。

雙向連結清單

    基本結構

  1. typedef struct DulNode{ 
  2.     ElemType data; 
  3.     struct DulNode *next; 
  4.     struct DulNode *prior; 
  5. }DulNode,*DuLinkList 

    插入

循環連結清單、雙向連結清單
  1. s->prior = p;//一定要先處理新結點的指針問題  
  2. s->next = p->next; 
  3. p->next->prior = s; 
  4. p->next = s; 
  5. s->prior = p;//這種方式也可以  
  6. s->next = p->next; 
  7. p->next = s; 
  8. s->next->prior = s; 

    删除

  1. p->next->prior = p->prior; 
  2. p->prior->next = p->next; 

繼續閱讀