數據結構--鏈表

来源:https://www.cnblogs.com/CangLing/archive/2018/01/13/7448020.html
-Advertisement-
Play Games

網上關於鏈表的文章很多，比我寫的好的前輩也多不勝數。工作一年總是感覺前面學的後面忘，於是就誕生了寫博客的想法，把自己的工作學習歷程記下來互勉。思來想去還是把鏈表作為我的處女博吧，畢竟這是我踏入程式員路上寫的第一個數據結構，以下內容在忐忑、羞射的心情下編寫。如果有什麼不能忍的地方歡迎大家指正! --與 ...


 　　網上關於鏈表的文章很多，比我寫的好的前輩也多不勝數。工作一年總是感覺前面學的後面忘，於是就誕生了寫博客的想法，把自己的工作學習歷程記下來互勉。思來想去還是把鏈表作為我的處女博吧，畢竟這是我踏入程式員路上寫的第一個數據結構，以下內容在忐忑、羞射的心情下編寫。如果有什麼不能忍的地方歡迎大家指正!

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--與鏈表無關純屬矯情

　　談到鏈表之前，就想先說一下線性表。線性表是最基本、也是最常用的一種數據結構。一個線性表是多個數據的集合，除了第一個和最後一個數據元素之外，其它數據元素都是首尾相接的。線性表有兩種存儲方式，一種是順序存儲結構，另一種是鏈式存儲結構。

　　我們常用的數組就是一種典型的順序存儲結構。鏈表就是下麵要詳細說的鏈式存儲結構。

　　順序存儲結構就是兩個相鄰的元素在記憶體中也是相鄰的，這種存儲方式的優點是查詢比較方便，通過首地址和偏移量就可以訪問到某個元素，匹配的查找演算法也有好多，最快的可以達到O(logn)。缺點是插入刪除很不方便，複雜度最壞能達到O(n)，例如你想在某個位置插入/刪除元素，你需要將這個位置之後的所有元素都後移/前移一位。另外一個不方便的地方是元素數量的確定，必須在使用前創建一個足夠大的數組放置所有的元素，但是開闢的數組空間往往不能夠充分的利用造成資源浪費。

               

　　鏈式存儲結構就是相鄰的兩個元素在記憶體中不一定相鄰，這種存儲方式的優點是只需要操作指針就可以添加刪除元素，比較方便，時間複雜度為O(1)；另外一個優點就是節省記憶體，元素在需要添加的時候才開闢記憶體，不需要的時候就釋放，也不需要事先預估元素的數量，相對於順序存儲結構要靈活許多。缺點就是查找的演算法比較少，一般只能通過遍歷查找，時間複雜度為O(n)，還有一個缺點就是申請或者釋放記憶體會消耗時間，如果頻繁的對記憶體申請釋放，消耗的時間是很可觀的。

　　鏈表中的元素稱為結點，一般由兩部分組成：指針域和值域，值域可以是基本數據類型也可以是結構體等複雜數據類型，存放需要的具體數據；指針域為指向下一個節點的指針。根據指針域的不同鏈表可以分為單向鏈表，雙向鏈表，迴圈鏈表等等。

                                                                

　　如上圖所示就是一個由四個節點組成的單向鏈表，其中每個Data和Next為一個節點，第一個節點稱為頭節點，最後一個節點稱為尾節點，Head為一個指向頭節點的指針。Data為節點的值域，用來存放數據；Next為節點的指針域，指向下一個節點。尾節點的指針域為空。

　　鏈表的操作主要是圍繞著指針域和對記憶體的申請釋放進行，一般的操作就是增、刪、改、查。頭節點可以與其他的節點數據類型不同，頭節點的值域中可以存放一些鏈表的信息，比如說鏈表的長度，創建時間，創建人等等。

 　　下麵還是以一個簡單的C程式來具體操作一下。

　　整個程式由三個文件組成Chain——chain.h　　存放一些類型、函數等的聲明

　　　　　　　　　　　　　　　 |——chain.c　　存放函數的具體實現

　　　　　　　　　　　　　　　 |——main.c　　調用、測試實現的函數

　　　　　　　　　　　　　　　 |____Makefile　　MakeFile文件，編譯的時候使用，如果是初次接觸的話請忽略，後續的博客中會更新。

　　以下為chain.h文件

#ifndef _CHAIN_H_
#define _CHAIN_H_

/*聲明一些數據類型*/
typedef int datatype;//聲明鏈表存儲的數據類型
typedef unsigned short uint16;
typedef unsigned char bool;
/*返回結果*/
typedef enum
{
    TRUE,
    FALSE
}bool_val;

/*聲明鏈表節點*/
typedef struct node
{
    datatype data;
    struct node* next;
}ListNode;

/*聲明鏈表頭*/
typedef struct head
{
    char info[20];
    unsigned short length;
    ListNode* next;
}ListHead;

/*一下為一些鏈表操作函數的聲明*/
ListHead* CreateList();//創建鏈表
bool ViewList(ListHead* head);//遍歷鏈表
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data);//在指定位置添加節點
bool DelNodeByLoc(ListHead* head, uint16 loc);//刪除指定位置的節點
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data);//修改指定位置的節點數據
datatype FindDataByLoc(ListHead* head, uint16 loc);//返回指定位置的節點數據
bool DestoryList(ListHead* head);//銷毀鏈表



#endif
chain.h

　　以下為chain.c文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "chain.h"

/*創建鏈表*/
ListHead* CreateList()
{
    ListHead* head =  NULL;
    head = (ListHead*)malloc(sizeof(ListHead));    //申請記憶體
    memset(head, 0, sizeof(head));
    
    /*初始化鏈表信息*/
    head -> length = 0;
    strcpy(head -> info, "CangLing's List");
    head -> next = NULL;
    return head;
}

/*遍歷鏈表*/
bool ViewList(ListHead* head)
{
    /*合法性判斷*/
    if(head == NULL)
    {
        return FALSE;
    }
    ListNode* p = NULL;
    
    /*列印鏈表信息*/
    printf("The List Info is %s\n",head -> info);
    printf("The List Length is %d\n",head -> length);

    /*輸出節點內容*/
    p = head -> next;
    while(p != NULL)
    {
        printf("%d\n",p -> data);
        p = p -> next;
    }

    return TRUE;
}

/*根據位置添加節點，大於鏈表長度的位置添加在鏈表末尾*/
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* node = head -> next;
    ListNode* tmp = NULL;
    /*初始化要創建的節點*/
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p -> data = data;
    p -> next = NULL;

    if(head -> length == 0)//對只有頭節點的鏈表進行處理
    {
        head -> next = p;
        p -> next = NULL;
    }
    else if(loc <= head -> length)//對1<loc<length的情況進行處理
    {
        /*添加在頭節點之後*/
        if(loc == 1)
        {
            head -> next = p;
            p -> next = node;
        }
        else
        {
            /*尋找對應位置的前一個節點*/
            while(loc > 2)
            {
                loc--;
                node = node -> next;
            }
            tmp = node -> next;//保存loc位置的節點地址
            node -> next = p;//將要添加的節點放在loc位置
            p -> next = tmp;
        }

    }
    else//對loc>length的情況進行處理
    {
        while(node -> next != NULL)
        {
            node = node -> next;
        }

        node -> next = p;
    }

    head -> length++;//修改鏈表信息
    ret = TRUE;

    return ret;

}

/*刪除loc位置的節點*/
bool DelNodeByLoc(ListHead* head, uint16 loc)
{
    /*進行合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* tmp = head -> next;
    ListNode* freenode = NULL;

    if(loc == 1)//針對第一個節點的處理
    {
        freenode = tmp;
        head -> next = tmp -> next;
    }
    else//對1<loc<length的情況進行處理
    {
        while(loc > 2)//找到loc的前一個節點
        {
            loc--;
            tmp = tmp -> next;
        }

        freenode = tmp -> next;//保存要釋放的節點地址
        tmp -> next = freenode -> next;
    }

    /*釋放節點並修改鏈表信息*/
    free(freenode);
    head -> length --;

    return ret;
}

/*修改loc位置的節點信息*/
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    bool_val ret = FALSE;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc節點
    {
        tmp = tmp -> next;
        loc --;
    }

    tmp -> data = data;//修改節點數據
    return ret;
}

/*返回loc節點的數據*/
datatype FindDataByLoc(ListHead* head, uint16 loc)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    datatype ret = 0;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc節點
    {
        tmp = tmp -> next;
        loc --;
    }

    ret = tmp -> data;

    return ret;
}

bool DestoryList(ListHead* head)
{
    ListNode* p = NULL;
    ListNode* node = NULL;
    if(head == NULL)
    {
        return TRUE;
    }

    /*釋放除頭節點之外的節點*/
    p = head -> next;

    while(p != NULL)
    {
        node = p;
        p = p -> next;
        free(node);
    }

    /*釋放頭節點*/
    free(head);

    return TRUE;
}
chain.c

　　以下為main.c文件

#include <stdio.h>
#include "chain.h"

int main()
{
    int i = 0;
    ListHead* head =  NULL;
    head = CreateList();//創建鏈表

    printf("Now we will Add four Nodes\n");
    for(i = 1; i < 5; i++)
    {
        AddNodeByLoc(head, i, i);//添加鏈表節點
    }
    ViewList(head);//遍歷鏈表

    printf("Now we will Delete the third Node\n");
    DelNodeByLoc(head, 3);//刪除鏈表的第三個節點
    ViewList(head);

    printf("Now we will modify the third Node to 5\n");
    ModNodeByLoc(head, 3, 5);//將第三個節點的信息修改為5
    ViewList(head);

    printf("Now we will view the second Node\n");
    printf("%d\n",FindDataByLoc(head, 2));//查看第二個節點的數據
    DestoryList(head);//銷毀鏈表
}
main.c

　　以下為MakeFile文件

main: chain.o main.o    #生成main依賴的文件
#執行命令cc chain.o main.o -o main生成最終的可執行文件main
    cc chain.o main.o -o main
main.o: main.c chain.h    #生成main.o依賴的文件

chain.o: chain.c chain.h    #生成chain.o依賴的文件

#刪除生成的中間文件
clean:    
    rm *.o main
MakeFile

　　上面的四個文件我在Linux的環境下使用，將上面的文件放在同一個文件夾下，輸入make運行，完成後生成chain.o main.o以及可執行文件main，運行make clean清除三個編譯生成的文件。

　　這裡我簡單說一下什麼是Makefile。在Windows下編譯工作都由IDE來完成，例如VC6.0編譯工程，你不需要管文件之間的依賴關係。但是在Linux環境下這部分工作由MakeFile完成。MakeFile關係到整個工程的編譯規則，一個工程下文件不計其數，按模塊、類型、功能分放在不同的目錄下，MakeFile指定了一系列規則來指定哪些文件先編譯，哪些文件需要後編譯，哪些文件需要重新編譯，甚至還有一些更複雜的功能操作。它帶來的好處就是“自動化編譯”，一旦寫好MakeFile文件，工程的編譯只需要一個make命令，整個工程就會全自動編譯。上面就是我為鏈表寫的一個很簡單的MakeFile文件，後續的博客中會更新MakeFile的相關用法。

       

　　如果很不習慣也可以直接運行編譯命令gcc main.c chain.c -o main當然也可以直接複製三個文件的內容直接在VC6.0下運行，效果是一樣的。

　　

　　下麵是鏈表運行的結果

      


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

-Advertisement-
Play Games
更多相關文章
  • 024模塊的概念
    ###模塊calculate是自己寫的，出現紅色也可以調用 ###包導入包中的模塊 導入包中包的模塊 導入包中包模塊的方法 導入包解釋了__init__文件導入模塊和包的區別，導入模塊把模塊解釋了一遍，導入包只是解釋了__init__文件###項目中的模塊導入比較複雜簡單目錄結構，最後執行bin.p ...
  • python基礎_特殊符號
    #\n 回車符 #\r 換行符 #\s 空格 #\t tab符號，不知道？開個txt文本，然後按電腦的tab鍵，就是caps lock上面那個，卧槽，看到一個大長空格（也可能是個超短空格），這個就是tab符 #其他基本不會用，這幾個夠用了 #%d 數字 print '%d' %2 #%s 字元串 p ...
  • 日常一篇之jsp頁面亂碼問題
    對於中文亂碼問題，根據產生的原因，主要有以下幾種解決方案： 一、以Post方法提交的表單數據中有中文字元時。 這樣的話，就可以在獲取請求參數值之前，調用request對象的setCharacterEncoding("")方法，將請求的解碼方式設定為UTF-8。像這樣： 二、以GET方法提交的表單數據 ...
  • python3 第八章 - 數據類型之Number（數字）
    Python 支持三種不同的數字類型： 整型(Int) - 通常被稱為是整型或整數，是正或負整數，不帶小數點。Python3 整型是沒有限制大小的，可以當作 Long 類型使用，所以 Python3 沒有 Python2 的 Long 類型。 浮點型(float) - 浮點型由整數部分與小數部分組成 ...
  • Java學習筆記33（集合框架七：Collections工具類）
    數組有工具類，方面操作數組 集合也有工具類：Collections 常用方法示例： ...
  • Java學習筆記32（集合框架六：Map介面）
    Map介面與Collection不同： Collection中的集合元素是孤立的，可理解為單身，是一個一個存進去的，稱為單列集合 Map中的集合元素是成對存在的，可理解為夫妻，是一對一對存進去的，稱為雙列集合 Map中存入的是：鍵值對，鍵不可以重覆，值可以重覆 Map介面中的常用集合： 1.Hash ...
  • 演算法 之 aabb
    題目描述：輸出所有形如aabb的4位完全平方數（即前兩位數字相等，後兩位數字也相等）。 分支和迴圈結合在一起時功能強大： 下麵列舉所有可能的結果aabb，然後判斷它們是否為完全平方數。註意a的範圍是1~9，但b可以是0. 上面的程式並不完整——“aabb是完全平方數”是中文描述，而不是合法的C語言表 ...
  • 測試代碼
    測試代碼 介紹如何使用Python模塊unittest 中的工具來測試代碼。 1. 測試函數 在Python中，測試函數是用於自動化測試，使用python模塊中的unittest中的工具來進行測試。 例如，創建一個函數max_function()接受兩個數字，求其最大值，再創建一個函數number_ ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類