亚洲综合图片区自拍_思思91精品国产综合在线观看_一区二区三区欧美_欧美黑人又粗又大_亚洲人成精品久久久久桥本

鏈表是編程學(xué)習(xí)的一個難點。其實，在C語言編程以及單片機裸機開發(fā)中，鏈表運用并不多。但是如果想提升嵌入式技能水平或收入水平，可以考慮深入嵌入式系統(tǒng)層面（如參與操作系統(tǒng)設(shè)計、深入學(xué)習(xí)新的操作系統(tǒng)等），此時，鏈表技術(shù)至關(guān)重要。

本期講解一道C語言的算法題——反轉(zhuǎn)一個單向鏈表。

題目描述：

(資料圖片僅供參考)

已知鏈表的節(jié)點類型如下：

typedef struct node{

int data;   struct node* next;

}Node;

現(xiàn)在有一條單鏈表，其節(jié)點類型為Node，鏈表的頭節(jié)點為head，請設(shè)計一種方法反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后的鏈表。

Part 1

鏈表的基本介紹

Q1: 什么是節(jié)點？

A1: 節(jié)點是鏈表的構(gòu)成單元，節(jié)點類型本質(zhì)上是結(jié)構(gòu)體類型，如題中出現(xiàn)的Node類型。正常情況下，一個節(jié)點至少包含兩個成員，一個成員保存該節(jié)點的數(shù)據(jù)，比如int data; 另一個成員是一個指針，比如Node *next，用于指向下一個節(jié)點。因此多個節(jié)點可以串在一起，構(gòu)成鏈表。

Q2: 什么是鏈表？

A2: 百度百科中是這樣定義鏈表的?！版湵硎且环N物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的?！?/p>

核心：鏈表是一種存儲結(jié)構(gòu)。

可以將鏈表與數(shù)組進行對比，鏈表的優(yōu)勢在于：對存儲單元進行插入/刪除操作更靈活方便（節(jié)點是鏈表的構(gòu)成單元，元素是數(shù)組的構(gòu)成單元）、鏈表的容量可以動態(tài)改變（而數(shù)組一旦定義，則容量固定，可能會有溢出風(fēng)險）。

Q3: 鏈表的分類有哪些？

A3: 根據(jù)節(jié)點之間的關(guān)系，可以分為單鏈表（一般指單向不循環(huán)鏈表）、雙鏈表、循環(huán)單鏈表。

Part 2

解題思路

先確認下本題中的節(jié)點類型。

typedef struct node{           int data;           struct node* next;    }Node;

由于本題采用一個單向不循環(huán)鏈表，鏈表的尾節(jié)點的指針成員指向NULL，可在示意圖中先補充地址NULL。

圖示的原鏈表由4個節(jié)點構(gòu)成，分別是節(jié)點A、B、C和D，他們的data（數(shù)據(jù)成員）的值依次是1、2、3和4。節(jié)點A是首節(jié)點，即head保存節(jié)點A的地址。節(jié)點A的next（指針成員）指向節(jié)點B，節(jié)點B的next指向節(jié)點C，節(jié)點C的next指向節(jié)點D，節(jié)點D的next指向NULL。

觀察原鏈表和轉(zhuǎn)換后的圖示，可以看出轉(zhuǎn)換后節(jié)點之間的指向關(guān)系將完全反過來，節(jié)點D最終成為首節(jié)點，head將保存它的地址。

思考，得出以下結(jié)論：

在單向鏈表中，若要遍歷節(jié)點，必須從鏈表首節(jié)點開始逐個訪問，所以反轉(zhuǎn)鏈表時，必須要按照原鏈表節(jié)點順序逐個操作。（即按照從節(jié)點A到節(jié)點D的順序）除了尾節(jié)點外，更改每個節(jié)點的next（指針成員）值之前，必須先用指針指向在原鏈表中該節(jié)點的下一個節(jié)點（比如：在更改節(jié)點A的next為NULL之前，必須用指針指向節(jié)點B，否則將丟失數(shù)據(jù)）。head指針用于保存鏈表的首節(jié)點的地址，會隨著節(jié)點的反轉(zhuǎn)，逐漸移動（改變指向）。

Step1,定義兩個特殊用途的指針。

//指針p用于指向待反轉(zhuǎn)節(jié)點的前一個節(jié)點Node *P = NULL;//指針N用于指向待反轉(zhuǎn)節(jié)點的后一個節(jié)點Node *N = head;//本示例中head指針指向的節(jié)點也就是待操作的節(jié)點

Step2,用指針N指向待操作節(jié)點的下一個節(jié)點，反轉(zhuǎn)一個節(jié)點（改變待操作節(jié)點的next成員）。

N = N- >next;head- >next = P;

Step3,準(zhǔn)備反轉(zhuǎn)下個節(jié)點前，需要依次改變P指針和head指針。

P = head;head = N;

Step4,用指針N指向待操作節(jié)點的下一個節(jié)點，反轉(zhuǎn)一個節(jié)點（改變待操作節(jié)點的next成員）。

此步驟和Step2相同，已開始重復(fù)的操作了。故之后的步驟將省略。

需要注意的是，當(dāng)head指針在某次偏移之后，它將會指向原鏈表的尾節(jié)點（此時head->next == NULL為真），就說明此刻僅需要反轉(zhuǎn)最后一個節(jié)點。

Part 3

示例代碼

示例說明：

為了方便演示運行效果，將在主函數(shù)中構(gòu)建4個Node類型的結(jié)構(gòu)體變量，先對他們賦值，然后將他們串成鏈表，遍歷鏈表，打印節(jié)點數(shù)據(jù)（預(yù)期打?。?，2，3，4）。之后反轉(zhuǎn)鏈表，再次遍歷鏈表，打印節(jié)點數(shù)據(jù)（預(yù)期打印：4，3，2，1）。

核心代碼：鏈表反轉(zhuǎn)函數(shù)

Node *list_reverse(Node *head){  Node *i;  Node *P = NULL;  Node *N = head;  if(head == NULL)    return NULL;  while(head- >next != NULL) //判斷head是否為尾節(jié)點   {    N = N- >next;    head- >next = P;    P = head;    head = N;  }  head- >next = P; //反轉(zhuǎn)最后一個節(jié)點   return head; }

主程序設(shè)計

int main(void){  Node A,B,C,D;  //分別對4個節(jié)點的data賦值，并將他們串成鏈表   A.data = 1; A.next = &B;  B.data = 2; B.next = &C;  C.data = 3; C.next = &D;   D.data = 4; D.next = NULL;  Node *head = &A;    printf("原鏈表：\\n");  list_output(head);  head = list_reverse(head);  printf("\\n反轉(zhuǎn)后：\\n");  list_output(head);  return 0;}

運行結(jié)果

和預(yù)期一致，代碼驗證成功！