seo網(wǎng)站系統(tǒng)播放量自助下單平臺
目錄
什么是單向鏈表
順序表和鏈表的區(qū)別和聯(lián)系
順序表：
鏈表：
鏈表表示(單項(xiàng))和實(shí)現(xiàn)
1.1 鏈表的概念及結(jié)構(gòu)
1.2單鏈表(無頭)的實(shí)現(xiàn)
所用文件
將有以下功能：
鏈表定義
創(chuàng)建新鏈表元素
尾插
頭插
尾刪
頭刪
查找-給一個節(jié)點(diǎn)的指針
改
pos位置之前插入
刪除pos位置的值
成品展示
SList.h
SList.c
test.c
什么是單向鏈表
單向鏈表是一種常見的線性數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個節(jié)點(diǎn)包含兩部分：數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針。每個節(jié)點(diǎn)只能訪問它后面的節(jié)點(diǎn)，而不能訪問前面的節(jié)點(diǎn)。
單向鏈表的特點(diǎn)：
- 每個節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針。
- 最后一個節(jié)點(diǎn)的指針指向空值（NULL），表示鏈表的結(jié)束。
- 可以動態(tài)地添加或刪除節(jié)點(diǎn)，鏈表的長度可以根據(jù)需要進(jìn)行擴(kuò)展或縮小。
- 可以根據(jù)指針迅速插入或刪除節(jié)點(diǎn)，而不需要移動其他節(jié)點(diǎn)。
單向鏈表相對于數(shù)組來說，具有一些優(yōu)點(diǎn)和缺點(diǎn)：
- 優(yōu)點(diǎn)：插入和刪除元素的時間復(fù)雜度為O(1)，不需要像數(shù)組一樣進(jìn)行元素的移動；鏈表長度可以動態(tài)調(diào)整，沒有固定大小的限制。
- 缺點(diǎn)：要訪問特定位置的元素需要從頭開始遍歷，時間復(fù)雜度為O(n)；相比于數(shù)組，在使用額外的指針存儲下一個節(jié)點(diǎn)的信息，會占用更多的內(nèi)存空間。
由于單向鏈表的特點(diǎn)，它常常被用于需要頻繁插入和刪除元素的場景，或者在事先無法確定數(shù)據(jù)大小和數(shù)量的情況下使用。
順序表和鏈表的區(qū)別和聯(lián)系
順序表：
優(yōu)點(diǎn)：
空間連續(xù)、支持隨機(jī)訪問
缺點(diǎn)：
- 中間或前面部分的插入刪除時間復(fù)雜度O(N)
- 2.增容的代價比較大。
鏈表：
缺點(diǎn)：
以節(jié)點(diǎn)為單位存儲，不支持隨機(jī)訪問
優(yōu)點(diǎn)：
- 任意位置插入刪除時間復(fù)雜度為O(1)
- 沒有增容消耗，按需申請節(jié)點(diǎn)空間，不用了直接釋放。
鏈表表示(單項(xiàng))和實(shí)現(xiàn)
1.1 鏈表的概念及結(jié)構(gòu)
概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的
1.2單鏈表(無頭)的實(shí)現(xiàn)
?
- 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。- 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都
是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶
來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。
所用文件
定義三個文件：
- 頭文件 SList.h
- 函數(shù)的實(shí)現(xiàn)SList.c
- 代碼的測試test.c
將有以下功能：
//打印鏈表
void SListPrint(SLTNode* phead);//創(chuàng)建新鏈表元素（動態(tài)申請一個節(jié)點(diǎn)）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾刪
void SListPopBack(SLTNode** pphead);//頭刪
void SListPopFront(SLTNode** pphead);//查找->可在查找的基礎(chǔ)上進(jìn)行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);
鏈表定義
定義鏈表基本結(jié)構(gòu)
typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;
創(chuàng)建新鏈表元素
創(chuàng)建新元素用于插入原鏈表
SLTNode* BuySListNode(SLTDataType x)
{//開辟空間SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}
尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{//開辟空間SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//防止開始時節(jié)點(diǎn)為空*pphead = newnode;}else{//找尾節(jié)點(diǎn)SLTNode* tail = *pphead;//找到鏈表首元素while (tail->next != NULL){//檢索到未節(jié)點(diǎn)tail = tail->next;}//插入tail->next = newnode;}
}
頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址傳給pphead //*pphead=&plist/*頭插無需檢查是否為空*/
}
尾刪
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一個節(jié)點(diǎn)free(*pphead);*pphead = NULL;}else{//2，有多個節(jié)點(diǎn)//將前一個鏈元素中存放的地址換為NULL，防止野指針/* 寫法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //寫法二* //tail尋找的是倒數(shù)第二個元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}
頭刪
void SListPopFront(SLTNode** pphead)
{ //防止被刪空assert(*pphead);//找到首位鏈表元素SLTNode* next = (*pphead)->next;//存儲首元素存放下一個元素的地址free(*pphead);//釋放首元素*pphead = next;//將第二位元素改為首元素
}
查找-給一個節(jié)點(diǎn)的指針
//無需更改元素，故傳一級指針
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}//未找到指定元素，返回NULLreturn NULL;
}
改
改元素是建立再查找基礎(chǔ)之上進(jìn)行更改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{printf("修改成功:\n");//先找到相應(yīng)元素，再進(jìn)行更改SLTNode* ret = SListFind(phead, y);ret->data = x;
}
pos位置之前插入
任意位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//頭插if (pos == *pphead)SListPushFront(pphead, x);else{ //任意位置之前插入SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//創(chuàng)建新鏈表元素，并賦值prev->next = newnode;//給前一個元素賦上下一元素地址newnode->next = pos;//給插入元素存放下一個元素的地址}
}
刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//頭刪else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//將prev存放的地址改為pos后一個元素的地址prev->next = pos->next;//釋放posfree(pos);pos = NULL;}
}
成品展示
SList.h
#pragma once#include <stdlib.h>
#include <stdio.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;//打印鏈表
void SListPrint(SLTNode* phead);//創(chuàng)建新鏈表元素（動態(tài)申請一個節(jié)點(diǎn)）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾刪
void SListPopBack(SLTNode** pphead);//頭刪
void SListPopFront(SLTNode** pphead);//查找->可在查找的基礎(chǔ)上進(jìn)行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);
SList.c
#include "SList.h"//打印
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur!=NULL){printf("%d->", cur->data);cur = cur->next;//存放下一個元素的地址}printf("NULL\n");
}//創(chuàng)建新鏈表元素
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);//dataif (*pphead == NULL){//防止開始時節(jié)點(diǎn)為空*pphead = newnode;}else{//找尾節(jié)點(diǎn)SLTNode* tail = *pphead;while (tail->next != NULL){//存放新節(jié)點(diǎn)地址tail = tail->next;}tail->next = newnode;}
}//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址傳給pphead //*pphead=&plist/*頭插無需檢查是否為空*/
}//尾刪
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一個節(jié)點(diǎn)free(*pphead);*pphead = NULL;}else{//2，有多個節(jié)點(diǎn)//將前一個鏈元素中存放的地址換為NULL，防止野指針/* 寫法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //寫法二* //tail尋找的是倒數(shù)第二個元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}//頭刪
void SListPopFront(SLTNode** pphead)
{ //防止被刪空assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找-給一個節(jié)點(diǎn)的指針
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}return NULL;
}//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{assert(phead);printf("修改成功:\n");SLTNode* ret = SListFind(phead, y);ret->data = x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//頭插if (pos == *pphead)SListPushFront(pphead, x);else{ SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//創(chuàng)建新鏈表元素，并賦值prev->next = newnode;//給前一個元素賦上下一元素地址newnode->next = pos;//給插入元素存放下一個元素的地址}
}//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//頭刪else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//將prev存放的地址改為pos后一個元素的地址prev->next = pos->next;//釋放posfree(pos);pos = NULL;}
}
test.c
test.c僅僅是用于測試代碼，本文以弄懂單向鏈表為主，故不進(jìn)行菜單制作
但改測試中也包含了對部分鏈表結(jié)構(gòu)即原理進(jìn)行了講解，請耐心看完
#include "SList.h"
void TestSList1()
{ SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));assert(n1);SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));assert(n2);SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));assert(n3);SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));assert(n4);n1->data=1;n2->data=2;n3->data=3;n4->data=4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;SListPrint(n1);
}void TestSList2()
{SLTNode* plist = NULL;//傳的是plist指針的地址//如果直接傳plist，將導(dǎo)致SLTNode* phead中//phead為臨時拷貝，不影響實(shí)參SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改變無需傳二級指針SListPushFront(&plist,0);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopBack(&plist);/*SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*//*SListPopBack(&plist);SListPrint(plist);*/
}void TestSList3()
{SLTNode* plist = NULL;//傳的是plist指針的地址//如果直接傳plist，將導(dǎo)致SLTNode* phead中//phead為臨時拷貝，不影響實(shí)參SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改變無需傳二級指針//查找SLTNode* ret = SListFind(plist, 3);if (ret){//返回值不為空則為找到printf("找到了\n");}SListPrint(plist);修改//SListAlter(plist, 20, 2);//SListPrint(plist);//插入SLTNode* pos = SListFind(plist, 3);//先要找到再進(jìn)行更改if (pos){SListInsert(&plist, pos, 40);}SListPrint(plist);//刪除pos = SListFind(plist, 2);//先要找到再進(jìn)行刪除if (pos){SListErase(&plist, pos);}SListPrint(plist);
}int main()
{TestSList3();return 0;
}
單向鏈表講解完畢啦！創(chuàng)作不易，如果喜歡請留下個贊吧，感激不盡😊