C/C++ 雙鏈表之逆序的實例詳解
更新時間：2017年07月04日 17:19:48 投稿：lqh
這篇文章主要介紹了C/C++ 雙鏈表之逆序的實例詳解的相關(guān)資料,需要的朋友可以參考下
C/C++ 雙鏈表之逆序的實例詳解
一、結(jié)點結(jié)構(gòu)
雙向鏈表的數(shù)據(jù)結(jié)構(gòu)定義如下：
typedef struct node
{
ElemType data;
struct node *prior
struct node *next;
}list;
其中，ElemType可以是任意數(shù)據(jù)類型如int、float或者char等，在算法中，規(guī)定其默認為int類型。
二、帶頭結(jié)點
本文描述的是雙向鏈表逆序，鏈表逆序需要維護3個指針，分別指向前一個節(jié)點、當前節(jié)點和下一個節(jié)點，具體代碼如下：
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; // 保存當前結(jié)點的下一結(jié)點
p2->next = p1; // 改變當前結(jié)點的next域，指向它的前一個結(jié)點
p1->prior = p2; // 改變前一個結(jié)點的prior域，指向它的后一個結(jié)點
p1 = p2; // 指針移到下一個結(jié)點
p2 = p3;
}
head->next = p1; // 恢復頭結(jié)點
p1->prior = head;
return head;
}
在鏈表逆序過程中，非常重要的一點是要防止斷鏈問題，因此，在移動指針逆序某個結(jié)點時，需要用一個指針指向該結(jié)點的下一結(jié)點，防止下一結(jié)點丟失。
三、不帶頭結(jié)點
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é)點的鏈表逆序與帶頭結(jié)點的區(qū)別在于紅色部分代碼，即初始p1指向的是第一個結(jié)點而不是頭結(jié)點，最后head直接指向p1而不是用其next來指向p1。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
本文主要介紹了QT中進程的創(chuàng)建實現(xiàn),詳細介紹了創(chuàng)建進程的整個過程,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2023-08-08
C++vector的insert函數(shù)用法小結(jié)
std::vector::insert是C++中用于在指定位置插入元素的函數(shù),支持插入單個元素、多個相同元素、一個范圍的元素或初始化列表中的元素,插入操作可能會使插入點之后的迭代器失效,并且時間復雜度為O(n),本文介紹C++vector的insert函數(shù)用法小結(jié),感興趣的朋友一起看看吧2025-03-03
C++虛函數(shù)表與類的內(nèi)存分布深入分析理解
對C++ 了解的人都應該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）來實現(xiàn)的。簡稱為V-Table。本文就將詳細講講虛函數(shù)表的原理與使用，需要的可以參考一下2022-08-08
這篇文章主要介紹了C語言從編譯到運行的一個過程的相關(guān)資料,需要的朋友可以參考下面文章具體的內(nèi)容2021-09-09
今天小編就為大家分享一篇關(guān)于C++標準模板庫map的常用操作，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
今天小編就為大家分享一篇對C++ string append方法的常用用法詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-06-06
折半查找法也叫做?分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪?半中,再重復上述步驟知道找到?標key,下面這篇文章主要給大家介紹了關(guān)于C語言折半查找法的相關(guān)資料,需要的朋友可以參考下2022-08-08
這篇文章主要為大家詳細介紹了C++如何實現(xiàn)簡易掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
c++網(wǎng)絡編程下Linux的epoll技術(shù)和Windows下的IOCP模型
c++ 網(wǎng)絡編程LINUX-epoll/windows-IOCP下socket opoll函數(shù)用法 優(yōu)于select方法的epoll 以及windows下IOCP 解決多進程服務端創(chuàng)建進程資源浪費問題，感興趣的小伙伴一起來學習吧2021-08-08
QT?UDP網(wǎng)絡編程實現(xiàn)簡單消息傳輸
這篇文章主要為大家詳細介紹了QT?UDP網(wǎng)絡編程實現(xiàn)簡單消息傳輸，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08