哈嘍，大家好，今天我們學習的是數(shù)據(jù)結(jié)構(gòu)里的鏈表，這里主要講的是不帶哨兵衛(wèi)頭節(jié)點的單向鏈表，下篇將會繼續(xù)帶大家學習雙向鏈表。
目錄
1.鏈表的概念
2.單向鏈表接口的實現(xiàn)
2.1動態(tài)申請一個節(jié)點
2.2單鏈表打印
2.3單鏈表尾插
2.4單鏈表頭插
2.5單鏈表尾刪
2.6單鏈表頭刪
2.7在pos位置插入x
2.7.1在pos位置前插入x
2.7.2在pos位置后插入x
2.8刪除pos位置值
2.9 查找x的地址
2.10銷毀鏈表
3.完整代碼
1.鏈表的概念
在上篇文章，我們已經(jīng)學習了順序表，不知大家有沒有發(fā)現(xiàn)順序表在一定程度上是存在缺陷的，比如說：
- 空間不夠了的時候需要擴容，擴容需要付出代價（特別是異地擴空間）
- 為了避免頻繁擴容，我們滿了基本都是擴2倍，可能會導致一定的空間浪費
- 順序表要求數(shù)據(jù)從開始位置連續(xù)存儲，那么我們在頭部或者中間位置插入刪除數(shù)據(jù)就需要挪動數(shù)據(jù)，效率不高
針對順序表的缺陷，就有了鏈表來存儲數(shù)據(jù)
概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
?鏈表的定義：
?這里的data就是要存放的數(shù)據(jù)
2.單向鏈表接口的實現(xiàn)
下面是要介紹的常用到的鏈表接口函數(shù)以及實現(xiàn)方法：
//打印
void SListPrint(SLTNode* phead);
//創(chuàng)建新節(jié)點
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//頭插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//頭刪
void SListPopBack(SLTNode** pphead);
//尾刪
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//刪除
void SListErase(SLTNode** pphead, SLTNode* pos);
//銷毀
void SListDestroy(SLTNode** pphead);
2.1動態(tài)申請一個節(jié)點
由于我們每次給鏈表插入數(shù)據(jù)時，都需要動態(tài)開辟空間來申請節(jié)點，所以我們把這個過程封裝成一個函數(shù)，方便后續(xù)操作。
動態(tài)申請一個節(jié)點的步驟是先向計算機內(nèi)存申請一塊空間，這里我們將申請的空間用指針變量newnode來存儲，然后將newnode中的data賦值，因為這是新開辟的節(jié)點，所以暫時將newnode中的next指向空。
注意：為了提高程序的可靠性，我們在動態(tài)內(nèi)存申請后記得檢查是否申請失敗了，如果申請失敗了輸出提示信息，并退出程序。
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果動態(tài)內(nèi)存申請失敗就退出程序
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}2.2單鏈表打印
打印鏈表就是一個遍歷鏈表的過程，我們首先定義一個指針(cur)指向鏈表的頭節(jié)點，然后輸出該節(jié)點的值，然后將指針指向下一個節(jié)點（cur=cur->next),依次進行，直到cur為空指針時停止
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//將cur指向下一個節(jié)點
}
printf("NULL\n");
}2.3單鏈表尾插
尾插，就是先找到鏈表中最后一個節(jié)點，然后將數(shù)據(jù)插入到最后。
但是，我們要先判斷鏈表是否為空，如果鏈表為空，我們直接直接將鏈表的頭指針賦予要插入的數(shù)據(jù)。
由于尾插要改變鏈表，所以傳參要用二級指針，包括下面的尾插，尾刪，頭刪等都要用二級指針傳參
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}2.4單鏈表頭插
頭插是比較簡單的一種操作，只需要申請新節(jié)點，將新節(jié)點的next指向鏈表的頭，再讓新節(jié)點成為鏈表的頭即可。
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}2.5單鏈表尾刪
尾刪：每次找到鏈表的最后一個節(jié)點和倒數(shù)第二個節(jié)點，然后釋放最后一個節(jié)點所占的看空間并將最后一個節(jié)點置空，同時將倒數(shù)第二個節(jié)點的next指向NULL；如果鏈表只剩下一個節(jié)點，直接釋放并置空該節(jié)點（這一步需要單獨考慮）
注意：為了避免鏈表為空但有調(diào)用尾刪的情況，我們需要斷言一下，當傳過來的鏈表是空鏈表的時候，程序就會報錯
void SListPopBack(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
//當鏈表中只有一個節(jié)點
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}2.6單鏈表頭刪
頭刪是將第一個節(jié)點釋放然后指向第二個節(jié)點，在此之前需要定義一個指針next來保存第二個節(jié)點的地址。
void SListPopFront(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}2.7在pos位置插入x
在pos位置插入x分為兩種情況，一種是在pos前位置插入x ，另一種是在pos后位置插入x，下面將分別為大家介紹：
2.7.1在pos位置前插入x
在pos位置前插入x,只需要找到pos的前一個位置，我們把pos的前一個位置命名為posPrev，然后創(chuàng)建一個新節(jié)點newnode，將posPrev的下一個節(jié)點指向newnode，newnode的下一個節(jié)點指向pos即可，如下圖：
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一個位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}2.7.2在pos位置后插入x
在pos位置后插入x比在pos位置前插入x要簡單，不需要遍歷鏈表即可完成
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
?? ?assert(pos != NULL);
?? ?SLTNode* newnode = BuyListNode(x);
?? ?newnode->next = pos->next;
?? ?pos->next = newnode;
}2.8刪除pos位置值
刪除pos位置值也需要先找到pos的前一個節(jié)點，因此也要考慮pos是鏈表的頭節(jié)點的情況
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}2.9 查找x的地址
查找x的地址，如果查找到了x，則返回該節(jié)點的地址，否則返回空指針。這個步驟也要遍歷鏈表。
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}2.10銷毀鏈表
銷毀鏈表需要將所有節(jié)點所占的內(nèi)存全部釋放，再將鏈表的頭置為空即可。
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.完整代碼
SList.h文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;//存放下一個鏈表的地址
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//創(chuàng)建新節(jié)點
SLTNode* BuyListNode(SLTDateType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
//頭插
void SListPushFront(SLTNode** pphead, SLTDateType x);
//頭刪
void SListPopBack(SLTNode** pphead);
//尾刪
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//刪除
void SListErase(SLTNode** pphead, SLTNode* pos);
//銷毀
void SListDestroy(SLTNode** pphead);SList.c文件：文章來源：http://www.zghlxwxcb.cn/news/detail-504774.html
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//將cur指向下一個節(jié)點
}
printf("NULL\n");
}
SLTNode* BuyListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//如果動態(tài)內(nèi)存申請失敗就退出程序
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
//當鏈表中只有一個節(jié)點
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
//保證鏈表不是空鏈表
assert(*pphead != NULL);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* tail = phead;
if (tail->data == x)
{
return tail;
}
while (tail ->data != x)
{
tail = tail->next;
if (tail->data == x)
{
return tail;
}
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead != NULL);
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
//找到pos的前一個位置
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pos != NULL);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead != NULL);
assert(pos != NULL);
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}
void SListDestroy(SLTNode** pphead)
{
assert(*pphead != NULL);
SLTNode* cur = *pphead;
while (cur != NULL)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}總結(jié)：這篇文章主要寫的是單向鏈表，后續(xù)將繼續(xù)帶領(lǐng)大家學習雙向鏈表。如果我寫的有什么的不好之處，請在文章下方給出你寶貴的意見。如果覺得我寫的好的話請點個贊贊和關(guān)注哦~??文章來源地址http://www.zghlxwxcb.cn/news/detail-504774.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
