App下載

C語言如何實現(xiàn)單鏈表結構的反轉 詳細代碼解析

拖延俱樂部 2021-08-19 14:13:30 瀏覽數(shù) (2497)
反饋

本篇文章為大家?guī)砹艘黄P于C語言數(shù)據(jù)結構的文章,如何使用C語言實現(xiàn)單鏈表結構的反轉。下面是詳情內容,詳細解析了C語言中關于實現(xiàn)單鏈表反轉的細節(jié),以及具體實例代碼,供大家學習參考。

一、理解指針

看懂鏈表的結構并不是很難,但是一旦把它和指針混在一起,就很容易讓人摸不著頭腦。所以,要想寫對鏈表代碼,首先就要理解好指針。

  有些語言有“指針”的概念,比如 C 語言;有些語言沒有指針,取而代之的是“引用”,比如 Java、Python。不管是“指針”還是“引用”,實際上,它們的意思都是一樣的,都是存儲所指對象的內存地址。

  將某個變量賦值給指針,實際上就是將這個變量的地址賦值給指針,或者反過來說,指針中存儲了這個變量的內存地址,指向了這個變量,通過指針就能找到這個變量。

  p->next=q。這行代碼是說,p 結點中的 next 指針存儲了 q 結點的內存地址。p->next=p->next->next。這行代碼表示,p 結點的 next 指針存儲了 p 結點的下下一個結點的內存地址。

C語言標準規(guī)定,對于一個符號的定義,編譯器總是從它的名字開始讀取,然后按照優(yōu)先級順序依次解析。對,從名字開始,不是從開頭也不是從末尾,這是理解復雜指針的關鍵! 

 對于初學者,有幾種運算符的優(yōu)先級非常容易混淆,它們的優(yōu)先級從高到低依次是:

定義中被括號( )括起來的那部分。后綴操作符:括號( )表示這是一個函數(shù),方括號[ ]表示這是一個數(shù)組。前綴操作符:星號*表示“指向xxx的指針”。

  在本章中我們最多只用到二級指針因此將對二級指針做下說明。比如int **p,是什么意思?

首先看 *p 。 “*”表示P是一個指針。但是是指向什么的指針呢?

在看前面的int* ,int是一個整型類型后面加一個“*”表示整型類型的指針。

  *p就是指向整型類型指針的指針。p保存的是整型類型指針的地址。

二、警惕指針丟失和內存泄漏

  不知道你有沒有這樣的感覺,寫鏈表代碼的時候,指針指來指去,一會兒就不知道指到哪里了。所以,我們在寫的時候,一定注意不要弄丟了指針。指針往往都是怎么弄丟的呢?我拿單鏈表的插入操作為例來給你分析一下。

  指針往往都是怎么弄丟的呢?我拿單鏈表的插入操作為例來給你分析一下。

  如圖所示,我們希望在結點 a 和相鄰的結點 b 之間插入結點 x,假設當前指針 p 指向結點 a。如果我們將代碼實現(xiàn)變成下面這個樣子,就會發(fā)生指針丟失和內存泄露。

p->next = x; // 將p的next指針指向x結點;
x->next = p->next; // 將x的結點的next指針指向b結點;

  初學者經(jīng)常會在這兒犯錯。p->next 指針在完成第一步操作之后,已經(jīng)不再指向結點 b 了,而是指向結點 x。第 2 行代碼相當于將 x 賦值給 x->next,自己指向自己。因此,整個鏈表也就斷成了兩半,從結點 b 往后的所有結點都無法訪問到了。

  對于有些語言來說,比如 C 語言,內存管理是由程序員負責的,如果沒有手動釋放結點對應的內存空間,就會產生內存泄露。所以,我們插入結點時,一定要注意操作的順序,要先將結點 x 的 next 指針指向結點 b,再把結點 a 的 next 指針指向結點 x,這樣才不會丟失指針,導致內存泄漏。所以,對于剛剛的插入代碼,我們只需要把第 1 行和第 2 行代碼的順序顛倒一下就可以了。同理,刪除鏈表結點時,也一定要記得手動釋放內存空間,否則,也會出現(xiàn)內存泄漏的問題。當然,對于像 Java 這種虛擬機自動管理內存的編程語言來說,就不需要考慮這么多了。

三、單鏈表反轉的C語言實現(xiàn)

  使用p指向第一個結點,cur指向當前結點,每次把cur->next結點摘掉放在p節(jié)點前面。然后更新p結點指向頭結點。具體實現(xiàn)代碼如下所示

 void revers_list(list1 **l)
 {
   if(!(*l)||!l)
   {
     exit(-1);
   }
 
   list1 *start=*l;
   list1 *start_next=NULL;
 
   while (start->next)
   {
     // 獲取當前節(jié)點的后繼節(jié)點 
     start_next = start->next; 
     // 將后繼節(jié)點摘鏈 72   
      start->next = start_next->next; 
     // 將后繼節(jié)點提到最前面 
     start_next->next = *l; 
     // 更新頭節(jié)點 
     *l = start_next;
   }
 }

到此這篇關于C語言實現(xiàn)單鏈表反轉的文章就介紹到這了,更多相關C語言數(shù)據(jù)結構的其他內容,請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關文章!



C

0 人點贊