數據結構一單鏈表

1.單鏈表

1.數據結構簡介

程序=數據結構+算法

數據

數據（data）是客觀事物的一個符號表示

數據元素（data element）是數據的基本單位，一個數據元素可以由若干個數據項（data item）組成。數據項是數據不可分割的最小單位。

數據結構

是數據元素之間相互關系的集合

邏輯結構 邏輯層面：同窗

數據元素之間存在的邏輯關系

集合：

數據結構中的元素之間除了“同屬一個集合”的相互關系外，別無其他關系

**線性結構： **排隊：一列

數據結構中的元素存在一對一的相互關系，如數組（索引）、鏈表（指針）、棧和隊列（操作順序）等。

**樹形結構： **排隊：方隊

數據結構中的元素存在一對多的相互關系，如樹和二叉樹（一個父節點對應多個子節點）等

圖形結構：

數據結構中的元素存在多對多的相互關系，如圖（每個節點都可以與多個節點相連，同時它也可以被多個節點所連接。）等

物理結構(存儲結構)

數據的物理結構或存儲結構是數據在計算機中的存儲表示或實現

順序結構：

數據元素在物理位置上相鄰，通過元素的存儲地址來表示數據元素之間的邏輯關系，比如數組

鏈表結構：

對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附設的指針域來表示

索引結構：

為每個數據結構建立索引表，每個數據元素占用表中的一項，每個表項通常包含關鍵字和地址指針 map

散列結構（哈希結構）：

根據數據元素的關鍵字通過哈希函數計算出一個數值用作數據元素的存儲地址，以實現快速查找和插入

2.線性表（邏輯上）

它表示元素之間具有一對一的相鄰關系的數據集合。

線性表的數據元素可以是各種各樣、但是同一個線性表中的元素必須是相同類型。

特性：

存在唯一的一個被稱為："第一個"的數據元素

存在唯一的一個被稱為：“最后一個”的數據元素

除了第一個元素之外，集合中的每一個數據元素前均只有一個節點

除了最后一個元素之外，集合中的每一個數據元素后均只有一個節點

線性表可以是順序結構也可以是鏈表結構.。順序存儲的線性表通常通過數組（Array）實現，而鏈式存儲的線性表則通過鏈表（Linked List）實現

2.1順序存儲的線性表（數組）

在C++中，數組是最簡單的順序存儲的線性表實現。數組中的元素在內存中連續存放，每個元素可以通過索引（或下標）快速訪問。

例子：

#include <iostream>  
using namespace std;  
int main() 
{  
int arr[5] = {1, 2, 3, 4, 5}; // 定義一個整型數組，大小為5  
for(int i = 0; i < 5; i++) 
{  
cout << arr[i] << " "; // 訪問并打印數組中的每個元素  
}

上述結構存在一些問題問題：我們在定義數組的時候，需要規定數組的長度，定義好了就不能修改了。

int a[10]; // 定義了一個元素為int類型的數組，數組大小為10個int類型
// 修改數組的大小
a = malloc(sizeof(int) * 100); // 不行的，因為a是常量指針，不能改變a指向。

*2.1鏈式存儲的線性表（鏈表）**

鏈表的定義：鏈表就是由一個或者是多個包含指針成員變量的結構體.

struct 類型名
{
類型1 變量1; // 數據1...
類型n 變量n; // 數據nstruct 類型名 *指針變量; // 存儲數據元素的地址。在單鏈表結構里面，存儲下一個數據元素的內
存地址
}

通過其指針變量來指向其他同類型結構體內存地址來形成一種邏輯上的鏈式的數據結構。我們把每一個結構體實例（變量/空間）稱為該鏈表的：節點（node)

鏈表中的每個元素都是一個節點（Node），節點之間通過指針連接。鏈表分為單向鏈表、雙向鏈表和循環鏈表等多種類型。

***問題1：***為什么是 struct （結構體）？

因為包含指針成員，，記錄下一個元素的地址。而其他數據類型可能與指針類型不同，因此需要能夠存放 不同數據類型的結構，因此是結構體。

問題2：：為什么指針成員是 struct 類型名 *（當前結構體指針類型）？

因為需要存放下一個元素的地址，而下一個元素是 struct 類型名類型的。如果是 struct 類型名，要為當前類型分配空間，因為結構題沒有定義完全**，沒有辦法分配內存**。

struct 類型名 *的話是指針，無論什么類型指針都是分配八個字節。

特殊的節點：

***頭節點：***是鏈表中唯一一個沒有前節點、只有后節點的節點，是整個鏈表的第一個節點（開端）。

***尾節點：***是鏈表中唯一一個沒有后節點，只有前節點的節點，是整個鏈表的最后一個節點（結尾）。因此尾節點的指針指向空( NULL )，以保證尾節點的指針成員不會成為野指針。可以通過判斷指針是否指向空來判斷是不是查詢到了最后一個元素。

畫個圖
在這里插入圖片描述

2.3鏈表的創建過程

(單鏈表 Singly Linked List)

2.3.1 定義鏈表節點結構

首先，需要定義一個鏈表節點的結構體，該結構體至少包含兩個成員：存儲數據的部分（數據域）和指向下一個節點的指針（指針域）。

//定義鏈表節點結構
typedef struct listNode{int val; // 整型數據  
struct li

2.3.2 初始化鏈表頭指針

在創建鏈表之前，需要初始化鏈表的頭指針。頭指針是一個指向鏈表第一個節點的指針。如果鏈表為空，則頭指針通常設置為 NULL 。

//初始化鏈表頭指針
ListNode* head = NULL; // 初始化鏈表為空鏈表

在這里插入圖片描述

創建并添加節點到鏈表

接下來，可以通過創建新的節點并將其插入到鏈表中來構建鏈表。插入操作可以根據需要在鏈表的不同位置進行（如頭部、尾部或特定位置）。

2.3.3 創建節點

//創建節點 value新節點存儲的數據
//可以是普通結構體變量，但是之后用到的要&listNode *createNode(int value)
{listNode *newNode=new listNode{ value};//動態分配內存，設置新節點的值if(newNode!=NULL){newNode->next=NULL;//新節點的next指針初始化為NULL，沒有后面的元素}return newNode;//此處可以返回局部變量的地址是因為newNode在堆區，生命周期在delete后才結
束}

推薦創建節點時用 new/malloc 在堆區申請節點，而不是棧區。

因為堆區空間由程序員維護，可以控制其聲明周期，

而棧區內存空間由編譯器維護，無法控制生命周期，有可能內存空間被意外收回。

2.3.4 插入節點

如果頭節點為空，新創建的節點即為頭節點

在這里插入圖片描述

頭插直接讓新節點指向頭節點，那么新節點就變成了新的頭節點

//頭插 2-3   ->   1-2-3直接讓新節點指向頭節點，新節點變成新的頭節點
//頭部添加節點//希望形參影響實參
listNode *insertNodeAtHead(listNode*head/*頭節點的地址*/,int value/*數據*/)//head是一級指針要有返回值，
// 因為是值傳遞，用返回值更新head指向 二級指針不需要 地址傳遞
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);return head;}![屏幕截圖 2025-03-31 065839](D:\筆記\4-2 數據結構 （復習筆記）\屏幕截圖 2025-03-31 065839.png)//創建新節點listNode *newHead=createNode(value);//讓新節點指向頭節點newHead->next=head;//返回新的頭節點return newHead;}

添加頭節點如果為空直接創建，新節點就是頭節點，如果不為空直接讓新節點指向頭節點，新節點變成新的頭節
在這里插入圖片描述

尾部插入：如果要在鏈表尾部添加節點，需要遍歷鏈表直到最后一個節點，然后將最后一個節點的next指針指向新節點

//尾部添加節點
listNode *insertNodeAtTail(listNode*head,int value)
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);}else{  //定義中間變量，找到尾節點listNode *current=head;while( current->next==NULL){//向后遍歷current==current->next;}//current指向尾節點 ，尾節點next指向新節點current->next=createNode(value);}//返回頭節點 在調用該函數時要用head接受該返回值來更新頭節點return head;}

在這里插入圖片描述

中間插入：：按照一定規則在某個位置插入元素

//中間插入（從小到大）
//head:鏈表的頭節點 newNode：插入節點
listNode *insertNodeAtMiddle(listNode*head,int value)
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);}else{//比頭節點小， 例如：2-3 頭插if(value<head->val);{// 頭插head=insertNodeAtHead(head,value);//結束return head;}//前面的節點listNode*first=head;//下一個的節點listNode*second=first->next;/*在兩者之間插入 只需要在first和second之間插入 鏈表只有一個元素 first：1 second null 直接摻入first后只要second為空 直接尾插*///first不是尾節點while(second){//判斷相鄰兩個節點的大小關系if(value>first->val&&value<second->val){listNode *newNode =createNode(value);//創建節點//一定是先連接后面節點，在連接前面節點，因為節點只記錄了下一個節點的地址信// 息，如果先連接前面，則后面的地址信息就丟失了//先連接后面的節點，即先連接2-3newNode->next=second;//然后讓前面的節點指向新節點，即1-2first->next=newNode;return head;}//向后遍歷first=second;second=second->next;}//1-2-3   4  尾插head=insertNodeAtTail(head,value);}}

在這里插入圖片描述

附加：

值傳遞和地址傳遞區別-------形參修改會不會影響實參

實參 int 形參 int 值傳遞 形參不會影響實參

實參 int 形參 int* 地址傳遞 形參會影響實參

實參 int* 形參 int* 值傳遞* 形參不會影響實參

2.3.5 刪除鏈表中的節點

將鏈表中某個節點刪除，刪除時要注意，創建節點時申請了內存，刪除時要釋放內存以防止內存泄露，同時將指針置為空

//刪除節點listNode  *deteleNode(listNode*head,int value)
{if (head==NULL){//如果鏈表是空，結束return 0;}else if(value==head->val){//紀律新的頭節點listNode*newHead=head->next;//刪除頭節點。防止內存泄漏delete head;//更新頭節點head=newHead;}//非頭節點else{listNode*current=head;//遍歷鏈表while(current->next){//只使用一個指針 刪除當前節點的下一個節點if(current->next->val==value){// 當前節點的下一個節點 1-2-3 delete 2 變成1-3listNode* needDeleNode =current->next;//中間節點if(current->next->next ){//更新節點指向current->next= current->next->next;}//尾節點1-2 刪除2 變1else{![屏幕截圖 2025-03-31 070326](D:\筆記\4-2 數據結構 （復習筆記）\屏幕截圖 2025-03-31 070326.png)current->next=NULL;}//刪除下一個節點delete needDeleNode;needDeleNode=NULL;//提前結束return head;}current=current->next;//向后遍歷}}//沒有找到刪除節點信息 return head;}

在這里插入圖片描述

鏈表使用完畢記得要刪除所有節點，防止內存泄露

void deinitNode(listNode*&head)
{//判斷鏈表是不是空鏈表if(head==NULL){std::cout<<"鏈表為空"<<std::endl;return ;}listNode *current=head;while(current){//要刪除的節點listNode *needDelNode=current;//遍歷current=current->next;//刪除節點delete  needDelNode;needDelNode=NULL;}}

2. 4 完整代碼

#include <iostream>using namespace std;
//定義鏈表節點結構
typedef struct listNode
{int val;//整形數據struct listNode *next;//指向下一個節點的指針//listNode *next;不行，因為listNode沒有定義出來
}listNode;//創建節點 value新節點存儲的數據
//可以是普通結構體變量，但是之后用到的要&
listNode *createNode(int value)
{listNode *newNode=new listNode{value};//動態分配內存，設置新節點的值if(newNode!=NULL){newNode->next=NULL;//新節點的next指針初始化為NULL，沒有后面的元素}return newNode;}//頭插 2-3   ->   1-2-3直接讓新節點指向頭節點，新節點變成新的頭節點
//頭部添加節點
//希望形參影響實參
listNode *insertNodeAtHead(listNode*head,int value)//head是一級指針要有返回值，// 因為是值傳遞，用返回值更新head指向 二級指針不需要 地址傳遞
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);return head;}//創建新節點listNode *newHead=createNode(value);//讓新節點指向頭節點newHead->next=head;//返回新的頭節點return newHead;}
//尾部添加節點
listNode *insertNodeAtTail(listNode*head,int value)
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);}else{  //定義中間變量，找到尾節點listNode *current=head;while( current->next){//向后遍歷current=current->next;}//current指向尾節點 ，尾節點next指向新節點current->next=createNode(value);}//返回頭節點 在調用該函數時要用head接受該返回值來更新頭節點return head;}//中間插入（從小到大）
//head:鏈表的頭節點 newNode：插入節點
listNode *insertNodeAtMiddle(listNode*head,int value)
{if(head==NULL){//鏈表是空，新節點就是頭節點head=createNode(value);}else{//比頭節點小， 例如：2-3 頭插if(value<head->val){// 頭插head=insertNodeAtHead(head,value);//結束return head;}//前面的節點listNode*first=head;//下一個的節點listNode*second=first->next;/*在兩者之間插入 只需要在first和second之間插入 鏈表只有一個元素 first：1 second null 直接摻入first后只要second為空 直接尾插*///first不是尾節點while(second){//判斷相鄰兩個節點的大小關系if(value>first->val&&value<second->val){listNode *newNode =createNode(value);//創建節點//一定是先連接后面節點，在連接前面節點，因為節點只記錄了下一個節點的地址信// 息，如果先連接前面，則后面的地址信息就丟失了//先連接后面的節點，即先連接2-3newNode->next=second;//然后讓前面的節點指向新節點，即1-2first->next=newNode;return head;}//向后遍歷first=second;second=second->next;}// listNode*current=head;// while(value)//1-2-3   4  尾插head=insertNodeAtTail(head,value);}return head;
}
//刪除節點listNode  *deteleNode(listNode*head,int value)
{if (head==NULL){//如果鏈表是空，結束return 0;}else if(value==head->val){//紀律新的頭節點listNode*newHead=head->next;//刪除頭節點。防止內存泄漏delete head;//更新頭節點head=newHead;}//非頭節點else{listNode*current=head;//遍歷鏈表while(current->next){//只使用一個指針 刪除當前節點的下一個節點if(current->next->val==value){// 當前節點的下一個節點 1-2-3 delete 2 變成1-3listNode* needDeleNode =current->next;//中間節點if(current->next->next ){//更新節點指向current->next= current->next->next;}//尾節點1-2 刪除2 變1else{delete current->next;current->next=NULL;}//刪除下一個節點delete needDeleNode;needDeleNode=NULL;//提前結束return head;}current=current->next;//向后遍歷}}//沒有找到刪除節點信息 return head;}//打印鏈表
void printtNode(listNode*head)
{//判斷鏈表是不是空鏈表if(head==NULL){std::cout<<"鏈表為空"<<std::endl;return ;}listNode *current=head;//遍歷while (current){std::cout<<current->val<<" ";   //輸出內容current=current->next;}std::cout<<std::endl;
}//清空鏈表
void deinitNode(listNode*&head)
{//判斷鏈表是不是空鏈表if(head==NULL){std::cout<<"鏈表為空"<<std::endl;return ;}listNode *current=head;while(current){//要刪除的節點listNode *needDelNode=current;//遍歷current=current->next;//刪除節點delete  needDelNode;needDelNode=NULL;}}int main()
{// 初始化鏈表頭指針listNode *head=NULL;//初始化鏈表為空鏈表//head=insertNodeAtHead的返回值//插入head=insertNodeAtMiddle(head,1);//頭head=insertNodeAtMiddle(head,5);//尾head=insertNodeAtMiddle(head,3);//中間head=insertNodeAtMiddle(head,4);//中間head=insertNodeAtMiddle(head,2);//中間//打印printtNode(head);//刪除head= deteleNode(head,1);//頭head= deteleNode(head,5);//尾head= deteleNode(head,3);//中間printtNode(head);    //打印//清理鏈表deinitNode(head);//寫完一個驗證一個return 0;}