前言
前面學習了順序表發(fā)現(xiàn)，順序表雖然好，但也有很多不足的地方，比方說，順序表是一塊連續(xù)的物理空間，如果頭插或者頭刪，那么整個數(shù)組的數(shù)據(jù)都要移動。但是鏈表不一樣，鏈表是通過指針訪問或者調(diào)整，鏈表是物理空間是不連續(xù)的，通過當前的next指針找到下一個。
插入和刪除時，數(shù)組平均需要移動n/2個元素，而鏈表只需修改指針即可
鏈表的優(yōu)點：
插入刪除速度快
內(nèi)存利用率高，不會浪費內(nèi)存
大小沒有固定，拓展很靈活
鏈表的概念及結構
概念：
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的
結構：
注意：
1.從圖上看，鏈式結構在邏輯上是連續(xù)的，但在物理上不一定連續(xù)
2.現(xiàn)實中節(jié)點一般都是從堆上申請出來的
3.從堆上malloc的空間是按照一定策略來分配的，第二次申請空間可能是連續(xù)的，也可能不是
鏈表的分類
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
單向或雙向鏈表：
帶頭節(jié)點或者不帶頭節(jié)點：
循環(huán)或者非循環(huán)：
最常用的兩種鏈表
無頭單向非循環(huán)鏈表：
帶頭雙向循環(huán)鏈表：
————————————————
鏈表的創(chuàng)建
鏈表是由數(shù)據(jù)和指針組成
那么我們在創(chuàng)建鏈表的時候，需要一個指針指向下一個節(jié)點
如下：
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
創(chuàng)建新的節(jié)點
創(chuàng)建新的節(jié)點，把要插入的值放進新的節(jié)點的data，然后再把next指針賦成空，最后返回這個節(jié)點的指針
//創(chuàng)建新的節(jié)點
SListNode* BuySLTNode(SLTDataType x)
{
SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
if (ret == NULL)
{
perror("BuySLTNode");
return NULL;
}
ret->data = x;
ret->next = NULL;
return ret;
}
尾插
既然是尾插，那就是在尾部插入元素
我們可以看到下面是用二級指針接收的，因為傳過來的是一級指針的地址，所以我們要用二級指針接收，并且我們使用的時候要解引用，因為我們要改變的是一級指針本身
如果傳過來的指針本身就是NULL，那就直接把新的節(jié)點賦給傳過來的指針
如果不是空，那我們就找尾，找到尾之后，再把新的節(jié)點插入到尾部的next指針
注：
tail指針是指向元素當前位置，我們一般不直接使用原有的指針，因為我們要保留第一個元素指針的位置，以便后續(xù)使用。
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode* tail = *pphead;
//找尾
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
頭插
我們把新節(jié)點的next指向第一個元素的指針，然后再把第一個節(jié)點的指針更新為newnode
//頭插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
SListNode* tail = *pphead;
newnode->next = *pphead;
*pphead = newnode;
}
尾刪
分為三種情況：
1.鏈表沒有元素，那我們直接斷言解決
2.如果鏈表只有一個元素，那我們判斷一下，然后free掉第一個指針指向的空間
3.鏈表多個元素，我們這里選擇的是，判斷tail->next->next是否為空，如果不為空，我們讓tail指針向后走一步，再繼續(xù)判斷，直到tail->next->next為空，我們free掉tail->next即可
//尾刪
void SLTPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);//如果*pphead為空，說明鏈表沒有元素
if ((*pphead)->next == NULL)//如果（*pphead）->next為空，說明鏈表只有一個元素，我們只需要free掉第一個指針指向的空間即可
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
//判斷tail->next->next是否為空，如果不為空，tail向后走一步，再判斷
while (tail->next->next != NULL)
{
tail = tail->next;
}
//循環(huán)不滿足，說明tail->next->next為空
//我們只需要free掉tail的next
free(tail->next);
tail->next = NULL;
}
}
頭刪
分為兩種情況：
1.鏈表為空，直接用斷言解決
2.鏈表多個元素，我們直接用tail指針保留第一個指針的位置，然后再更新第一個位置的指針，最后free掉剛剛保留的tail位置
//頭刪
void SLTPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SListNode* tail = *pphead;
*pphead = tail->next;
free(tail);
tail = NULL;
}
查找
把phead指針賦給cur，如果cur->data和要查找的值相同，返回cur，如果不相同讓cur繼續(xù)向后走，直到相同位置，返回cur，如果走到NULL都沒有相同的，說明沒有。
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
指定位置插入
進來直接判斷pos是不是第一個元素的空間，如果是，直接頭插
走到else里，我們定義一個prev指針，記錄pos前一個的位置，直到prev的next等于pos，然后把要插入的值放進prev的next位置，再把pos給newnode的next
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
指定位置刪除
判斷要刪除的節(jié)點是否就是第一個節(jié)點，如果是，直接調(diào)用頭刪
反之，定義一個prev指針記錄pos的前一個位置，直到prev的next指針等于pos的時候，把pos的next賦給prev的next進行拼接，然后free掉pos即可
//指定刪除
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
//判斷pos是否就是第一個節(jié)點
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
pos位置后插入
pos位置后插入相比指定插入，通俗易懂
直接把newnode的next指向pos的next，然后再把pos的next指向newnode
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
pos位置后刪除
把pos的next給del，del是等會要刪除的位置
然后pos的next指向del的next，最后free掉del
//pos位置后刪除
void SLTEease_After(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
打印
把phead給cur指針，讓cur指針往后走，每次cur打印data數(shù)據(jù)，直到走到NULL。
//打印
void SLTPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
銷毀
定義一個cur指針，再記錄一下cur的下一個位置，然后free掉cur，再把剛剛記錄的cur的next位置賦給cur，直到cur走到NULL為止
//銷毀
void SLTDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
完整代碼
SList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
//打印
void SLTPrint(SListNode* phead);
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x);
//頭插
void SLTPushFront(SListNode** pphead, SLTDataType x);
//尾刪
void SLTPopBack(SListNode** pphead);
//頭刪
void SLTPopFront(SListNode** pphead);
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x);
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//指定刪除
void SLTErase(SListNode** pphead, SListNode* pos);
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x);
//pos位置后刪除
void SLTErase_After(SListNode* pos);
//銷毀
void SLTDestroy(SListNode** pphead);
SList.c
#include "SList.h"
//打印
void SLTPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//創(chuàng)建新的節(jié)點
SListNode* BuySLTNode(SLTDataType x)
{
SListNode* ret = (SListNode*)malloc(sizeof(SListNode));
if (ret == NULL)
{
perror("BuySLTNode");
return NULL;
}
ret->data = x;
ret->next = NULL;
return ret;
}
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode* tail = *pphead;
//找尾
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//頭插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
SListNode* tail = *pphead;
newnode->next = *pphead;
*pphead = newnode;
}
//尾刪
void SLTPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//頭刪
void SLTPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead != NULL);
SListNode* tail = *pphead;
*pphead = tail->next;
free(tail);
tail = NULL;
}
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//指定插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
//指定刪除
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
//pos位置后插入
void SLTInsert_After(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//pos位置后刪除
void SLTEease_After(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SLTDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
Test.c(測試代碼)文章來源：http://www.zghlxwxcb.cn/news/detail-463634.html
void SListTest2()
{
SListNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SListNode* ret = SLTFind(plist, 2);
//SLTPrint(plist);
SLTInsert(&plist, ret, 22);
SLTPrint(plist);
SLTErase(&plist, ret);
SLTPrint(plist);
}
int main()
{
SListTest3();
return 0;
}
下期講解帶頭雙向循環(huán)鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-463634.html
到了這里，關于數(shù)據(jù)結構《鏈表》無頭單向非循環(huán)-動圖詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
