概述：
?由于順序表插入和刪除元素需要移動大量數(shù)據(jù)，導(dǎo)致運行效率下降。因此引入了另一種數(shù)據(jù)結(jié)構(gòu) —— 鏈表。鏈表又分為單鏈表和雙鏈表。單鏈表結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
一. 單鏈表的定義
?單鏈表通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，不需要使用地址連續(xù)的存儲單元，因此它不要求在邏輯上相鄰的兩個元素在物理位置上也相鄰。
構(gòu)成：
?單鏈表由一系列節(jié)點組成，每個節(jié)點包含兩個部分：數(shù)據(jù)域（存儲數(shù)據(jù)元素）和指針域（存儲下一個節(jié)點地址）。
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;//數(shù)據(jù)域
struct SListNode* next;//指針域
}SLTNode;
特點：
- 單鏈表的節(jié)點是離散分布在內(nèi)存中的，通過指針將它們串聯(lián)起來。
- 單鏈表可以動態(tài)地分配內(nèi)存空間，可以根據(jù)需要靈活地插入、刪除節(jié)點。
二. 單鏈表的創(chuàng)建
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;//數(shù)據(jù)域
struct SListNode* next;指針域
}SLTNode;
首先創(chuàng)建一個結(jié)構(gòu)體struct SListNode用來存儲數(shù)據(jù)和指針。
考慮到后續(xù)數(shù)據(jù)類型修改的方便性，我們將struct SListNode 用typedef重命名為SLNode。
同時為方便以后調(diào)用接口實現(xiàn)不同數(shù)據(jù)類型鏈接，我們將數(shù)據(jù)域的類型int重命名為SLDateType。(后續(xù)存儲不停數(shù)據(jù)只需修改此處即可)
三、單鏈表各種接口實現(xiàn)
1. 動態(tài)申請一個結(jié)點
?后續(xù)要插入新節(jié)點時，首先要創(chuàng)建一個節(jié)點來存儲相關(guān)信息，在連接到單鏈表合適位置。
代碼實現(xiàn)：
SLTNode* BuySListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
return newnode;
}
2. 單鏈表打印
打印單鏈表，我們只需記錄頭節(jié)點，然后遍歷訪問，依次打印即可。
代碼實現(xiàn)：
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}
3. 尾插
尾插分兩種情況：沒有節(jié)點和有節(jié)點。
①：沒有節(jié)點：創(chuàng)建一個新節(jié)點，然后頭指針指向新節(jié)點。
②：有節(jié)點：遍歷找到最后一個節(jié)點，然后將其下一個節(jié)點指向新節(jié)點
代碼實現(xiàn)：
//由于尾插第一種情況需要改變結(jié)構(gòu)體指針，所以我們要傳結(jié)構(gòu)體二級指針
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)//沒有節(jié)點
{
*pphead = newnode;
}
else
{
//有節(jié)點
SLTNode* tail = *pphead;
while (tail->next)//遍歷找到最后一個節(jié)點
{
tail = tail->next;
}
//尾插
tail->next = newnode;
}
}
4. 頭插
頭插就相對簡單。不管原鏈表有無節(jié)點，只需插入新節(jié)點即可。
代碼實現(xiàn)：
//由于頭插會改變頭指針，所以我們傳二級指針
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);//新節(jié)點
//頭插
newnode->next = *pphead;
*pphead = newnode;
}
5. 尾刪
尾刪分3中情況：
①：首先要判斷鏈表中是否還有節(jié)點可刪。
②：鏈表中只有一個節(jié)點。一個節(jié)點比較簡單，將頭指針置空，然后釋放頭節(jié)點即可。
③：鏈表中有多個節(jié)點。多個節(jié)點，首先要遍歷找到尾節(jié)點的前一個節(jié)點。然后將其指針域置空，并釋放尾節(jié)點。
代碼實現(xiàn)：
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空
assert(*pphead);
if ((*pphead)->next == NULL)//2.一個節(jié)點
{
(*pphead)->next = NULL;
}
else
{
//3.多個節(jié)點
SLTNode* tail = *pphead;
遍歷找到尾節(jié)點的前一個節(jié)點
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
6. 頭刪
頭刪分兩種情況：
①：首先判斷鏈表中是否還有節(jié)點可刪。
②：鏈表還有節(jié)點可刪。首先保存第二個節(jié)點，在釋放頭節(jié)點。并將頭指針指向第二個節(jié)點。
代碼實現(xiàn)：
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newnode = (*pphead)->next;//保存第二個節(jié)點
free(*pphead);//釋放頭節(jié)點
*pphead = newnode;
}
7、查找
查找和打印一樣，直接遍歷訪問即可。找到了返回地址，沒有找打返回空指針。
代碼實現(xiàn)：
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->date == x)
return cur;
cur = cur->next;
}
return NULL;
}
8、在pos之前插入x
鏈表中，不管是單鏈表還是雙鏈表在某處插入新節(jié)點，一般默認前插。
前插分兩種情況：
①：pos位置為第一個節(jié)點?？梢詮?fù)用前面頭插接口實現(xiàn)。
②: 遍歷訪問鏈表找到pos前一個節(jié)點prev，然后將pos、prev、新節(jié)點連接起來。
代碼實現(xiàn)：
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(*pphead);
if (*pphead == pos)
{
SLTPushFront(pphead, x);//頭插
}
else
{
SLTNode* prev = *pphead;
//遍歷找到pos前一個節(jié)點
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
//prev,newnode,pos三個節(jié)點鏈接
prev->next = newnode;
newnode->next = pos;
}
}
9、在pos后插入x
在pos之前插入x，相對來所比較復(fù)雜。所以如果沒有特殊要求，可以采用pos后插。所以我們在這提供pos后插接口。
代碼實現(xiàn)：
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
//后插
newnode->next = pos->next;
pos->next = newnode;
}
10、刪除pos位置的值
刪除pos位置的值一樣分兩種情況：
①：如果pos為頭節(jié)點，復(fù)用頭刪接口。
②：遍歷找到pos前一個節(jié)點prev。然后將pos前一個節(jié)點和后一個節(jié)點鏈接起來，并釋放pos即可。
代碼實現(xiàn)：
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
//free(pos);
}
}
11、刪除pos位置之后的值
要刪除pos位置之后的值，我們首先將pos和pos后兩個節(jié)點指針鏈接起來，并釋放pos后一個節(jié)點即可。（要判斷pos是否為尾節(jié)點）
代碼實現(xiàn)：
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//檢查pos是否為尾節(jié)點
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}
12、銷毀
代碼實現(xiàn)：
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
四、所有代碼展示
List.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDateType x);
void SLTPushBack(SLTNode** pphead, SLTDateType x);
void SLTPushFront(SLTNode** pphead, SLTDateType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
//刪除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);
//銷毀
void SLTDestory(SLTNode** pphead)
List.h:文章來源：http://www.zghlxwxcb.cn/news/detail-632273.html
include "SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuySListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空
assert(*pphead);
//2.一個節(jié)點
//3.多個節(jié)點
if ((*pphead)->next == NULL)
{
(*pphead)->next = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newnode = (*pphead)->next;
free(*pphead);
*pphead = newnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->date == x)
return cur;
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
assert(*pphead);
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
//free(pos);
}
}
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//檢查pos是否為尾節(jié)點
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-632273.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)入門指南】單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
