快捷導(dǎo)航

C/C++ 雙鏈表之逆序的實(shí)例詳解

更新時(shí)間：2017年07月04日 17:19:48 投稿：lqh

這篇文章主要介紹了C/C++ 雙鏈表之逆序的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下

C/C++ 雙鏈表之逆序的實(shí)例詳解

一、結(jié)點(diǎn)結(jié)構(gòu)

雙向鏈表的數(shù)據(jù)結(jié)構(gòu)定義如下：

 typedef struct node
    {
      ElemType data;
      struct node *prior
      struct node *next;
    }list;

其中，ElemType可以是任意數(shù)據(jù)類(lèi)型如int、float或者char等，在算法中，規(guī)定其默認(rèn)為int類(lèi)型。

二、帶頭結(jié)點(diǎn)

本文描述的是雙向鏈表逆序，鏈表逆序需要維護(hù)3個(gè)指針，分別指向前一個(gè)節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)，具體代碼如下：

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head->next, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;      // 保存當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)
        p2->next = p1;      // 改變當(dāng)前結(jié)點(diǎn)的next域，指向它的前一個(gè)結(jié)點(diǎn)
        p1->prior = p2;     // 改變前一個(gè)結(jié)點(diǎn)的prior域，指向它的后一個(gè)結(jié)點(diǎn)
        p1 = p2;         // 指針移到下一個(gè)結(jié)點(diǎn)
        p2 = p3;
      }
      head->next = p1;       // 恢復(fù)頭結(jié)點(diǎn)
      p1->prior = head;
      return head;
    }

在鏈表逆序過(guò)程中，非常重要的一點(diǎn)是要防止斷鏈問(wèn)題，因此，在移動(dòng)指針逆序某個(gè)結(jié)點(diǎn)時(shí)，需要用一個(gè)指針指向該結(jié)點(diǎn)的下一結(jié)點(diǎn)，防止下一結(jié)點(diǎn)丟失。

三、不帶頭結(jié)點(diǎn)

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;
        p2->next = p1;
        p1->prior = p2;
        p1 = p2;
        p2 = p3;
      }
      head = p1;
      return head;
    }

不帶頭結(jié)點(diǎn)的鏈表逆序與帶頭結(jié)點(diǎn)的區(qū)別在于紅色部分代碼，即初始p1指向的是第一個(gè)結(jié)點(diǎn)而不是頭結(jié)點(diǎn)，最后head直接指向p1而不是用其next來(lái)指向p1。

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章:

相關(guān)文章

c語(yǔ)言常見(jiàn)圖片格式判斷實(shí)例
這篇文章介紹了c語(yǔ)言常見(jiàn)圖片格式判斷實(shí)例，有需要的朋友可以參考一下
2013-09-09
c++實(shí)現(xiàn)簡(jiǎn)單的線(xiàn)程池
本文介紹的線(xiàn)程池采用C++語(yǔ)言，在windows平臺(tái)下實(shí)現(xiàn)。本著技術(shù)分享的精神寫(xiě)作本文同時(shí)公布源代碼。歡迎大家指出該線(xiàn)程池存在的問(wèn)題并對(duì)當(dāng)前性能進(jìn)行討論。
2015-03-03
桶排序算法的理解及C語(yǔ)言版代碼示例
桶排序算法顧名思義,就是把要排序的元素分桶排序后合并結(jié)果,這里我們就來(lái)看一下桶排序算法的理解及C語(yǔ)言版代碼示例:
2016-07-07
使用C語(yǔ)言實(shí)現(xiàn)五子棋游戲
這篇文章主要為大家詳細(xì)介紹了使用C語(yǔ)言實(shí)現(xiàn)五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-08-08
詳解C/C++中const限定符總結(jié)
const是一種限定符，被const所限定的變量其值不可以被改變。。這篇文章主要介紹了C/C++中const限定符總結(jié),通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2020-02-02
C++中string字符串分割函數(shù)split()的4種實(shí)現(xiàn)方法
最近筆試經(jīng)常遇到需要對(duì)字符串進(jìn)行快速分割的情景,下面這篇文章主要給大家介紹了關(guān)于C++中string字符串分割函數(shù)split()的4種實(shí)現(xiàn)方法,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
2022-06-06
C語(yǔ)言規(guī)避野指針的方法流程
野指針就是指針指向的不是一個(gè)有效（合法）的地址，在程序中，如果訪問(wèn)野指針，可能會(huì)造成程序的崩潰，這篇文章主要介紹了C語(yǔ)言如何規(guī)避野指針,需要的朋友可以參考下
2024-03-03
C語(yǔ)言實(shí)現(xiàn)二值圖像模擬灰值圖像顯示效果
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)二值圖像模擬灰值圖像顯示效果，分為圖案法、抖動(dòng)法兩個(gè)方法實(shí)現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-10-10
C++中的自增與自減
這篇文章主要介紹了C++中的自增與自減,自增與自減是C++當(dāng)中兩個(gè)使用頻率非常高的運(yùn)算符，不僅在循環(huán)當(dāng)中用到，在日常的代碼當(dāng)中也經(jīng)常使用,下面來(lái)看看文章得具體介紹
2021-11-11
詳解C語(yǔ)言之預(yù)處理(上)
這篇文章主要介紹了C語(yǔ)言程序的預(yù)處理,小編覺(jué)得這篇文章寫(xiě)的還不錯(cuò),需要的朋友可以參考下，希望能夠給你帶來(lái)幫助
2021-11-11