單向鏈表

来源:http://www.cnblogs.com/web1013/archive/2016/05/29/5469706.html
-Advertisement-
Play Games

單向鏈表每個節點由兩個成員組成：一個是數據域，一個是指向自身結構的指針類型成員。如： struct slist { int data; struct slist *next; }; typedef struct slist SLIST; 單向鏈表的基本演算法包括：鏈表的建立、節點數據域的輸出、節點的插 ...


　　單向鏈表每個節點由兩個成員組成：一個是數據域，一個是指向自身結構的指針類型成員。如：

　　　　struct slist

　　　　{

　　　　　　int data;

　　　　　　struct slist *next;

　　　　};

　　　　typedef struct slist SLIST;

　　單向鏈表的基本演算法包括：鏈表的建立、節點數據域的輸出、節點的插入和刪除。

　　（1） 建立帶有頭結點的單向鏈表

　　建立單向鏈表的主要步驟如下：

  1. 讀取數據
  2. 生成新節點
  3. 將數據存入節點的成員變數中
  4. 將新節點插入到鏈表中，重覆上述操作直至輸入結束。

　　例1 編寫函數 creat_slist，建立帶有頭結點的單向鏈表。節點數據域中的數值從鍵盤輸入，以 -1 作為輸入結束標誌。鏈表頭結點的地址由函數值返回。

program

 1 //建立帶有頭結點的單向鏈表
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 //聲明結構體類型 SLIST
 6 struct slist
 7 {
 8     int data;
 9     struct slist *next;
10 };
11 typedef struct slist SLIST;
12 
13 //聲明鏈表建立函數
14 SLIST* creat_slist();
15 void print_slist(SLIST* head);
16 void insert_snode(SLIST* head, int x, int y);
17 
18 int main()
19 {
20     SLIST *head;
21     head = creat_slist();    //調用鏈表建立函數，得到頭結點地址
22     print_slist(head);
23     return 0;
24 }
25 
26 //定義鏈表建立函數
27 SLIST* creat_slist()
28 {    
29     //s指向新生成的節點；r指向鏈表的尾節點
30     SLIST *h, *s, *r;
31     int c;
32 
33     h = (SLIST*)malloc(sizeof(SLIST));
34     r = h;
35     scanf("%d", &c);        //讀入數據
36     
37     while (c != -1)            //-1作為輸入結束標誌
38     {
39         s = (SLIST*)malloc(sizeof(SLIST));        //生成新節點
40         s->data = c;        //將讀入的數據存入新節點的數據域
41         r->next = s;        //新節點鏈接到表尾
42         r = s;                //r指向當前表尾
43         scanf("%d", &c);    //讀入數據
44     }
45     r->next = '\0';            //鏈表結束標誌
46     return h;
47 }
48 
49 //順序輸出鏈表各節點數據
50 void print_slist(SLIST* head)
51 {
52     SLIST* p;
53     p = head->next;            //p指向頭結點後的第一個節點
54     
55     if (p == '\0')
56     {
57         printf("Linklist is null !\n");    //鏈表為空（只有頭結點）
58     }
59     else
60     {
61         printf("head");
62         do
63         {
64             printf("->%d", p->data);    //輸出當前節點數據域中的值
65             p = p->next;                //p指向下一節點
66         } while (p != '\0');            //未到鏈表尾，迴圈繼續
67     }
68 }
69 
70 //在值為x的節點前插入值為y的節點
71 void insert_snode(SLIST* head, int x, int y)
72 {
73     SLIST *s, *p, *q;
74     s = (SLIST*)malloc(sizeof(SLIST));    //生成新節點
75     s->data = y;                        //在新節點中存入y值
76     q = head;
77     p = head->next;                        //工作指針初始化，p指向第一個節點
78     while ( (p != '\0') && (p->data != x) )
79     {
80         q = p;
81         p = p->next;                    //q指向p的前趨節點
82     }
83     //x存在，插在x之前；x不存在，p的值為NULL，插在表尾
84     s->next = p;
85     q->next = s;
86 }
View Code

　　

　　我們在函數中定義了一個名為 h 的指針變數，用於存放頭結點的地址；另外還定義了兩個工作指針：s 和 r，其中指針 s 用來指向新生成的節點，指針 r 總是指向當前鏈表的尾節點。每當把 s 所指的新開闢的節點連接到表尾後，r 便移向這一新的表尾節點，這時再用 s 去指向下一個新開闢的節點，就是使 r 承上，用 s 啟下。

　　鏈表最後一個節點的指針域中置 '\0'(NULL)，作為單向鏈表的結束標誌。鏈表建成後，頭結點的地址作為 creat_slist 函數的返回值由 return 語句返回並賦給 main 函數中的指針變數 head，因此函數的類型應該是基類型為 SLIST 的指針類型。

　　調用 creat_slist1 函數時，若一開始就輸入-1，控制流程不會進入 while 迴圈，而直接執行迴圈之後的 r->next = '\0'; 語句。這時建立的是一個空鏈表，其結構如圖1所示。由此可見，判斷此鏈表是否為空鏈表，可用條件：h->next == '\0';

圖1 帶有頭結點的空鏈表

　　（2） 順序訪問鏈表中各節點的數據域

　　所謂“訪問”，可以理解為取各節點的數據域中的值進行各種運算、修改各節點的數據域中的值等一系列的操作。

　　輸出單向鏈表各節點數據域中的內容的演算法比較簡單，只需利用一個工作指針 p ，從頭到尾依次指向鏈表中的每個節點；當指針指向某個節點時，就輸出該節點數據域中的內容，直到遇到鏈表結束標誌為止。如果是空鏈表，就只輸出相關信息並返回調用函數。

　　例2 編寫函數 print_slist，順序輸出單向鏈表各節點數據域中的內容。

program

 1 //建立帶有頭結點的單向鏈表
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 //聲明結構體類型 SLIST
 6 struct slist
 7 {
 8     int data;
 9     struct slist *next;
10 };
11 typedef struct slist SLIST;
12 
13 //聲明鏈表建立函數
14 SLIST* creat_slist();
15 void print_slist(SLIST* head);
16 void insert_snode(SLIST* head, int x, int y);
17 
18 int main()
19 {
20     SLIST *head;
21     head = creat_slist();    //調用鏈表建立函數，得到頭結點地址
22     print_slist(head);
23     return 0;
24 }
25 
26 //定義鏈表建立函數
27 SLIST* creat_slist()
28 {    
29     //s指向新生成的節點；r指向鏈表的尾節點
30     SLIST *h, *s, *r;
31     int c;
32 
33     h = (SLIST*)malloc(sizeof(SLIST));
34     r = h;
35     scanf("%d", &c);        //讀入數據
36     
37     while (c != -1)            //-1作為輸入結束標誌
38     {
39         s = (SLIST*)malloc(sizeof(SLIST));        //生成新節點
40         s->data = c;        //將讀入的數據存入新節點的數據域
41         r->next = s;        //新節點鏈接到表尾
42         r = s;                //r指向當前表尾
43         scanf("%d", &c);    //讀入數據
44     }
45     r->next = '\0';            //鏈表結束標誌
46     return h;
47 }
48 
49 //順序輸出鏈表各節點數據
50 void print_slist(SLIST* head)
51 {
52     SLIST* p;
53     p = head->next;            //p指向頭結點後的第一個節點
54     
55     if (p == '\0')
56     {
57         printf("Linklist is null !\n");    //鏈表為空（只有頭結點）
58     }
59     else
60     {
61         printf("head");
62         do
63         {
64             printf("->%d", p->data);    //輸出當前節點數據域中的值
65             p = p->next;                //p指向下一節點
66         } while (p != '\0');            //未到鏈表尾，迴圈繼續
67     }
68 }
69 
70 //在值為x的節點前插入值為y的節點
71 void insert_snode(SLIST* head, int x, int y)
72 {
73     SLIST *s, *p, *q;
74     s = (SLIST*)malloc(sizeof(SLIST));    //生成新節點
75     s->data = y;                        //在新節點中存入y值
76     q = head;
77     p = head->next;                        //工作指針初始化，p指向第一個節點
78     while ( (p != '\0') && (p->data != x) )
79     {
80         q = p;
81         p = p->next;                    //q指向p的前趨節點
82     }
83     //x存在，插在x之前；x不存在，p的值為NULL，插在表尾
84     s->next = p;
85     q->next = s;
86 }
View Code

　　

　　（3）在單向鏈表中插入節點

　　在單向鏈表中插入節點，首先要確定插入的位置。當待插節點插在指針 p 所指的節點之前稱為“前插”；當待插節點插在指針 p 所指節點之後稱為“後插”。圖2示意了“前插”操作過程中各指針的指向。

圖2 單向鏈表中節點的插入

　　當進行“前插”操作時，需要三個工作指針：圖中s 用來指向新開闢的節點；用 p 指向插入的位置；q 指向 p 的前趨節點（由於是單向鏈表，沒有指針 q，就無法通過 p 去指向它前趨節點）。

　　例3 編寫函數 insert_snode，它的功能是：在值為 x 的節點前插入值為 y 的節點，若值為 x 的節點不存在，則插在表尾。

program

 1 //建立帶有頭結點的單向鏈表
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 //聲明結構體類型 SLIST
 6 struct slist
 7 {
 8     int data;
 9     struct slist *next;
10 };
11 typedef struct slist SLIST;
12 
13 //聲明鏈表建立函數
14 SLIST* creat_slist();
15 void print_slist(SLIST* head);
16 void insert_snode(SLIST* head, int x, int y);
17 
18 int main()
19 {
20     SLIST *head;
21     head = creat_slist();    //調用鏈表建立函數，得到頭結點地址
22     print_slist(head);
23     return 0;
24 }
25 
26 //定義鏈表建立函數
27 SLIST* creat_slist()
28 {    
29     //s指向新生成的節點；r指向鏈表的尾節點
30     SLIST *h, *s, *r;
31     int c;
32 
33     h = (SLIST*)malloc(sizeof(SLIST));
34     r = h;
35     scanf("%d", &c);        //讀入數據
36     
37     while (c != -1)            //-1作為輸入結束標誌
38     {
39         s = (SLIST*)malloc(sizeof(SLIST));        //生成新節點
40         s->data = c;        //將讀入的數據存入新節點的數據域
41         r->next = s;        //新節點鏈接到表尾
42         r = s;                //r指向當前表尾
43         scanf("%d", &c);    //讀入數據
44     }
45     r->next = '\0';            //鏈表結束標誌
46     return h;
47 }
48 
49 //順序輸出鏈表各節點數據
50 void print_slist(SLIST* head)
51 {
52     SLIST* p;
53     p = head->next;            //p指向頭結點後的第一個節點
54     
55     if (p == '\0')
56     {
57         printf("Linklist is null !\n");    //鏈表為空（只有頭結點）
58     }
59     else
60     {
61         printf("head");
62         do
63         {
64             printf("->%d", p->data);    //輸出當前節點數據域中的值
65             p = p->next;                //p指向下一節點
66         } while (p != '\0');            //未到鏈表尾，迴圈繼續
67     }
68 }
69 
70 //在值為x的節點前插入值為y的節點
71 void insert_snode(SLIST* head, int x, int y)
72 {
73     SLIST *s, *p, *q;
74     s = (SLIST*)malloc(sizeof(SLIST));    //生成新節點
75     s->data = y;                        //在新節點中存入y值
76     q = head;
77     p = head->next;                        //工作指針初始化，p指向第一個節點
78     while ( (p != '\0') && (p->data != x) )
79     {
80         q = p;
81         p = p->next;                    //q指向p的前趨節點
82     }
83     //x存在，插在x之前；x不存在，p的值為NULL，插在表尾
84     s->next = p;
85     q->next = s;
86 }
View Code

　　由於本例中的單向鏈表採用了帶有頭結點的結構，不需要單獨處理新節點插在表頭的情況，從而簡化了操作。函數 insert_snode 中綜合運用了“查找”和“前插”的演算法。在進行插入操作的過程中，可能遇到三種情況，函數 insert_snode 將對這三種情況進行處理：

　　（1）鏈表非空，值為 x 的節點存在，新節點應插在該節點之前。

　　（2）鏈表非空，但值為 x 的節點不存在，新節點應插在表尾。

　　（3）鏈表為空表，這種情況相當於 x 的節點不存在，新節點應插在表尾，即插在頭結點之後，作為表的第一個節點。

　　在函數中，對於空表，在執行 p = head->next; 後，p 的值就為 NULL ，因此不會進入迴圈；當鏈表非空時進入迴圈，在 while 迴圈中，當出現 p == '\0' 時，將退出迴圈，這意味著查找結束，在鏈表中不存在值為 x 的節點。對於這兩種情況，語句 s->next = p; q->next = s; 將新節點插在表尾。當鏈表中存在值為 x 的節點時，p 的值一定部位 '\0'，語句 s->next = p; q->next = s; 將新節點插在 x 節點之前。

　　需要註意的是：while 迴圈中兩個條件的順序不能對調。當 p == NULL 時，C 編譯程式將“短路”掉第二個條件，不做判斷；否則如果先判斷 p->data != x 的條件，由於 p 中的值已為 NULL，這時再要訪問 p->data, 就會發生訪問虛地址的錯誤操作。

　　（4）刪除單向鏈表中的節點

　　為了刪除單項鏈表中的某個節點，首先要找到待刪除節點的前趨節點，然後將此前趨節點的指針域去指向待刪除節點的後續節點（q->next = p->next），最後釋放被刪除節點所占空間 free(p) 即可。圖3示意了節點的刪除操作。

圖3 單向鏈表節點的刪除


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 常用數據與VARIANT之間的轉換---從網上整理
    實現文件 ...
  • Java開發中的23種設計模式(轉)
    設計模式（Design Patterns） ——可復用面向對象軟體的基礎 設計模式（Design pattern）是一套被反覆使用、多數人知曉的、經過分類編目的、代碼設計經驗的總結。使用設計模式是為了可重用代碼、讓代碼更容易被他人理解、保證代碼可靠性。 毫無疑問，設計模式於己於他人於系統都是多贏的， ...
  • 學C++的經驗總結
    下麵的是學C++時要註意的。 1.把C++當成一門新的語言學習（和C沒啥關係！真的。）； 2.看《Thinking In C++》，不要看《C++變成死相》； 3.看《The C++ Programming Language》和《Inside The C++ Object Model》,不要因為他們 ...
  • 13.python中的字典
    字典其實和之前的元祖和列表功能相似，都是用來儲存一系列對象的。也就是一種可變容器，或者是我所比喻的革新派的菜單。 但也不是完全相同，我在之前曾經將字典稱為特殊的'序列'，是字典擁有序列的部分特性，但是又不符合序列的定義。 首先我們來看下字典是如何創建的： 我們可以使用{} 或者dict() 來創建一 ...
  • Java EE 遠程客戶的訪問EJB實現實例(Jboss wildfly)
    實例與上一篇GlassFish一致，應用伺服器換成wildfiy主要介紹差異部分。 1.準備工作，下載wildfly 10.0.0.final 2.創建管理員和用戶， 解壓縮wildfly-10.0.0.Final，在解壓後的文件夾中wildfly-10.0.0.Final\bin 下運行add-u ...
  • Java EE 遠程客戶的訪問EJB實現實例(GlassFish)
    這篇文章簡單實現在Java EE7 下實現遠程客戶端訪問Java EE伺服器EJB的功能 準備工作: 創建Enterprise Application 服務->伺服器右鍵添加服務伺服器->選擇GlassFish Server->安裝位置選擇java_ee_sdk解壓縮目錄下glassfish4文件夾 ...
  • Python 學習日記（第四周）
    set數據類型 先用一行代碼來說明一下 下麵的代碼的運行結果 通過代碼的結果可以看出 set是一個是一個無序且不重覆的元素集合 創建set 集合和字典相同{} 只有通過內部的元素才能體現出區別 創建空set集合,最好使用set()的方法創建，然後通過add方法添加元素 以下是set集合的一些常用方法 ...
  • 利用 filter 機制 給 靜態資源 url 加上時間戳，來防止js和css文件的緩存，利於開發調試
    直接上代碼： 配置下過濾器就行了，效果如下： 在開發階段還是比較有用的。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類