鏈表的引入
對于順序表存在一些缺陷：
中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N) 。頭部插入需要挪動后面的元素
增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
增容一般是呈2倍的增長，勢必會有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個(gè)數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間
對于鏈表而言，能夠避免上述問題的出現(xiàn)。頭部插入數(shù)據(jù)不需要挪動大量的數(shù)據(jù)，按需申請釋放空間，不會造成空間的浪費(fèi)。
鏈表的概念及結(jié)構(gòu)
概念:鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
現(xiàn)實(shí)中 數(shù)據(jù)結(jié)構(gòu)中（箭頭實(shí)際上并不存在，這里只是形象化）:
鏈表的種類有很多
以下情況組合起來就有8種鏈表結(jié)構(gòu)：
單向或者雙向 ：
帶頭或者不帶頭：
循環(huán)或者非循環(huán)：
面對這么多種類的鏈表，我們該如何選擇？雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：
- 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等
- 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了
話不多說，直接進(jìn)入我們單鏈表的實(shí)現(xiàn)：
單鏈表的接口我們需要實(shí)現(xiàn)：
-
打印銷毀
-
頭插尾插創(chuàng)建新結(jié)點(diǎn)(由于后面會頻繁使用，故將其封裝成函數(shù))
-
尾刪頭刪查找
-
在pos之前插入、在pos之后插入
-
刪除pos、刪除pos之后的位置
我們還是老樣子，通過三個(gè)部分組成：
**SList.h:**包括頭文件的引用，結(jié)構(gòu)體的聲明定義，接口函數(shù)的聲明。
**SList.c:**對SList.h中接口函數(shù)進(jìn)行實(shí)現(xiàn)。
**test.c:**主函數(shù)進(jìn)行測試：通過void TestSList()函數(shù)對SList.c的函數(shù)進(jìn)行調(diào)用，測試有沒有錯(cuò)誤。
注意：對于一些問題的所在，我已經(jīng)通過注釋進(jìn)行相關(guān)說明。注釋才是精髓。
SList.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SLTNode* next;
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//創(chuàng)建新結(jié)點(diǎn)
SLTNode* BuySLTNode(SLTDataType x);
//銷毀
void SListDestory(SLTNode** pphead);
//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾刪
void SListPopBack(SLTNode**pphead);
//頭刪
void SListPopFront(SLTNode**pphead);
//查找
SLTNode* SListFind(SLTNode* pphead,SLTDataType x);
//在pos之前插入
void SListInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x);
//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos
void SListErase(SLTNode** pphead,SLTNode*pos);
//刪除pos后面位置,了解
void SListEraseAfter(SLTNode* pos);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//打印
void SListPrint(SLTNode* phead)
{
//phead不需要斷言。因?yàn)閜head有可能有空，沒有數(shù)據(jù)
//而順序表的結(jié)構(gòu)體不可能為空，所以要進(jìn)行斷言
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//創(chuàng)建新結(jié)點(diǎn)
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("mail fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//銷毀
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾插——有無結(jié)點(diǎn)。需要找前一個(gè)
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
//空,改變的是SListNode*,需要二級指針
//非空。尾插要改變的是結(jié)構(gòu)體SListNode，只需要結(jié)構(gòu)體的指針
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//尾刪——有無結(jié)點(diǎn)。需要找前一個(gè)
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
/*while (tail->next->next!=NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;*/
}
}
//頭刪
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
/*if (*pphead == NULL)
{
return;
}*/
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
assert(pphead);
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos之前插入，需要找前一個(gè)
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev);
}
prev->next = newnode;
newnode->next = pos;
}
}
//在pos后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//刪除pos位置，需要找前一個(gè)
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//檢查pos不是鏈表中的結(jié)點(diǎn)
assert(prev);
}
prev->next = pos->next;
free(pos);
}
}
//刪除pos后面位置
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//頭插、頭刪
void TestSList1()
{
SLTNode* plist = NULL;
SListPushFront(&plist, 1);
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListPopFront(&plist);
SListPrint(plist);
SListDestory(&plist);
}
//尾插、尾刪
void TestSList2()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListPopBack(&plist);
SListDestory(&plist);
}
//查找、在pos之前插入
void TestSList3()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
//修改
pos->data *= 10;
printf("找到了\n");
}
else
{
printf("找不到\n");
}
pos = SListFind(plist, 1);
if (pos)
{
SListInsert(&plist, pos, 10);
}
SListPrint(plist);
SListDestory(&plist);
}
//刪除pos位置、刪除pos后面的位置
void TestSList4()
{
SLTNode* plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPrint(plist);
SLTNode* pos = SListFind(plist, 3);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
pos = SListFind(plist, 1);
if (pos)
{
SListErase(&plist, pos);
}
SListPrint(plist);
}
int main()
{
//TestSList1();
//TestSList2();
//TestSList3();
TestSList4();
return 0;
}
以上就是單鏈表的相關(guān)操作，我們不難發(fā)現(xiàn)，單鏈表的優(yōu)勢在于頭插頭刪
而對于一些操作：如尾插尾刪而言，我們都需要去找前一個(gè)位置，這是比較麻煩的。單鏈表我們就先介紹到這里了。
這里同時(shí)也有一個(gè)問題存在：
刪除當(dāng)前位置我們需要去找前一個(gè)位置，這效率是比較低的，我們?nèi)绾胃倪M(jìn)這個(gè)問題?
找pos位置刪除，而就是不找前一個(gè)位置（即要求是O（1））：替換法刪除，把pos的值和下一個(gè)節(jié)點(diǎn)的值進(jìn)行交換，再把pos進(jìn)行釋放掉。但是有一個(gè)缺陷：pos不能是尾節(jié)點(diǎn)。尾節(jié)點(diǎn)沒有下一項(xiàng)。
那如果在pos位置之前插入，要求為O（1）呢：
直接插入到pos后面，然后進(jìn)行交換。文章來源：http://www.zghlxwxcb.cn/news/detail-408822.html
總結(jié)
- 我們從鏈表的引入開始，了解了為什么鏈表會出現(xiàn)，同時(shí)認(rèn)識了鏈表的概念和結(jié)構(gòu)。本篇博客主要介紹了單鏈表的操作，以及解決了一個(gè)問題。本次就先到這里結(jié)束了。
文章來源地址http://www.zghlxwxcb.cn/news/detail-408822.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
