1. 單鏈表
1.1 概念與結構
概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
1.1.1 結點
- 與順序表不同的是，鏈表里的每節都是獨立申請下來的空間，我們稱之為“節點/結點”
- 節點的組成部分主要有兩個部分組成：當前節點要保存的數據（數據域）和保存下一個節點的地址（指針域）
- 鏈表中每個節點都是獨立申請的，（需要插入數據時才去申請一塊節點的空間），需要指針變量來保存下一個節點的位置才可以從當前的節點找到下一個節點。
1.1.2 鏈表的性質
- 鏈表結構在邏輯上時連續的，在物理結構上不一定是連續的
- 節點一般是從堆上申請的
- 從堆上申請來的空間，是按照一定的策略來分配的，每次申請的空間可能是連續的，也可能是不連續的
每個節點對應的結構體代碼：
typedef int SLTDataType;
//定義鏈表節點的結構
typedef struct SListNode
{SLTDataType data; //節點數據struct SListNode* next; //下一個節點的地址
}SLTNode;1.1.3 鏈表的打印
//單鏈表的打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d -> ",pcur->data);pcur = pcur->next;}printf("NULL\n");
}1.2 實現單鏈表
SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定義單鏈表就是定義節點，因為單鏈表是由節點組成的，所以定義單鏈表就是定義節點
typedef int SLTDataType;
//定義鏈表節點的結構
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//單鏈表的打印
void SLTPrint(SLTNode* phead);//單鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//單鏈表的尾刪
void SLTPopBack(SLTNode** pphead);
SList.c
#include"SList.h"//單鏈表的打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ",pcur->data);pcur = pcur->next;}printf("NULL\n");
}//新節點的申請
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申請新節點這里傳的應該是節點類型而不是數據類型//單鏈表：每次插入一個節點時，需要分配一個節點（結構體）的內存，因此使用 `sizeof(節點類型)`。//順序表：在擴容時，需要為多個數據元素分配一塊連續的內存（即數組），因此使用 `元素個數 * sizeof(數據類型)`。if (node == NULL){perror("malloc fail!\n");exit(1);}node->data= x;node->next = NULL;return node;
}//單鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {//單鏈表為空assert(pphead);//SLTNode* Tail = *pphead; 不能在這里定義Tail 因為這里的Tail為空，后面循環中的Tail->next 就會報錯，不會進入循環當中SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else {//單鏈表不為空，找尾節點，插入新節點SLTNode* Tail = *pphead;while (Tail->next != NULL){Tail = Tail->next;}//跳出循環，插入新節點Tail->next = newnode;//newnode->next = NULL; 不需要寫是因為，newnode在初始化的時候就已經置為NULL了}
}//單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//單鏈表尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//只有一個節點的情況if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}SLTNode* Tail = *pphead;SLTNode* prev = NULL;while (Tail->next){prev = Tail;Tail = Tail->next;}//跳出循環prev->next = NULL;free(Tail);Tail = NULL;
}
后續還有其它的單鏈表的實現哦~~~
