一文弄懂C語言如何實(shí)現(xiàn)單鏈表
更新時(shí)間：2021年09月06日 16:20:29 作者：忱叁
單鏈表是由多個(gè)結(jié)點(diǎn)鏈接組成,它的每個(gè)結(jié)點(diǎn)包含兩個(gè)域,一個(gè)數(shù)據(jù)域和一個(gè)鏈接域(地址域),下面這篇文章主要給大家介紹了關(guān)于C語言如何實(shí)現(xiàn)單鏈表的相關(guān)資料,需要的朋友可以參考下
一、單鏈表與順序表的區(qū)別：
一、順序表：
1、內(nèi)存中地址連續(xù)
2、長度可以實(shí)時(shí)變化
3、不支持隨機(jī)查找
4、適用于訪問大量元素的，而少量需要增添/刪除的元素的程序
5、中間插入或者刪除比較方便，內(nèi)存命中率較高
二、鏈表
1、內(nèi)存中地址不連續(xù)（邏輯上連續(xù)，物理上不連續(xù)）
2、長度可以實(shí)時(shí)變化（避免浪費(fèi)空間）
3、不支持隨機(jī)查找，查找的時(shí)間復(fù)雜度為o(1),
4、適用于訪問大量元素的，對訪問元素?zé)o要求的程序
5、中間插入或者刪除比較方便，效率高
二、關(guān)于鏈表中的一些函數(shù)接口的作用及實(shí)現(xiàn)
1、創(chuàng)建接口，開辟空間
2、尾插尾刪
3、頭插頭刪
4、查找并修改
5、中插中刪
ps：我看了許多的單鏈表文章，在插刪的接口實(shí)現(xiàn)上大多數(shù)是往前進(jìn)行插刪，這里寫的則是往后進(jìn)行插刪
1、頭文件里的結(jié)構(gòu)體和函數(shù)聲明等等
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SListDataType;
//節(jié)點(diǎn)
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;
}SListNode;
//struct SList
//{
// SListNode* head;
// SListNode* tail;
//};
//尾插尾刪
void SListPushBack(SListNode** pphead, SListDataType x);
void SListPopBack(SListNode** pphead);
//頭插頭刪
void SListPushFront(SListNode** pphead, SListDataType x);
void SListPopFront(SListNode** pphaed);
void SListPrint(SListNode* phead);
//查找并修改
SListNode* SListFind(SListNode* phead, SListDataType x);
//中插中刪
void SListInserAfter(SListNode**pphead,SListNode* pos, SListDataType x);
void SListEraseAfter(SListNode* pos);
//從頭到尾打印鏈表
void PrintTailToHead(SListNode* pList);
2、創(chuàng)建接口空間
//開辟的下一個(gè)空間
SListNode* BuySListNode(SListDataType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
printf("申請結(jié)點(diǎn)失敗\n");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
return newNode;
}
3.尾插尾刪
//尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{
SListNode* newNode = BuySListNode(x);//我們指向頭指針的那個(gè)結(jié)點(diǎn)是**pphead，*pphead就是頭指針的地址
//如果頭指針的地址為空，我們就把新開辟的這個(gè)空間指針（已經(jīng)傳入值）再賦給頭指針，也就是下面的這個(gè)if循環(huán)
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
//找尾巴，判斷尾巴是不是空地址,這個(gè)函數(shù)實(shí)現(xiàn)的是尾插，我們找到尾巴后，如果尾巴是空地址，我們將插入的newNode賦給尾巴，此時(shí)
//實(shí)現(xiàn)了尾插，在下面的代碼中，我們首先把頭指針當(dāng)成尾巴，從頭指針開始依次往后找，如果下一個(gè)不是空指針，我們就令
//tail=tail->next,此時(shí)指向下一個(gè)結(jié)點(diǎn)，進(jìn)入循環(huán)繼續(xù)判斷，當(dāng)找到后，我們再令尾巴=newNode,在上面我們也判斷了頭指針為空的情況
SListNode* tail = *pphead;
while (tail->next!= NULL)
{
tail = tail -> next;
}
tail->next = newNode;
}
}
void SListPopBack(SListNode** pphead)
{
//1、空
//2、一個(gè)結(jié)點(diǎn)
//3、一個(gè)以上
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
//tail = NULL;//這個(gè)無所謂，因?yàn)槲覀冡尫藕螅隽诉@個(gè)作用域，tail和prev都被銷毀，沒人能拿到，所以不會被再找到
prev->next = NULL;
}
}
4、頭插頭刪
//頭插頭刪
void SListPushFront(SListNode** pphead, SListDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopFront(SListNode** pphead)
{
//1、空
//2、一個(gè)結(jié)點(diǎn)+3、一個(gè)以上
if (*pphead == NULL)
{
return;
}
//(*phead)->next:*和>都是解引用，同一優(yōu)先級，我們需要給*pphead帶括號，(*pphead)->next才是下一個(gè)結(jié)點(diǎn)
else{
//我們頭刪也會遇到情況，我們刪除第一個(gè)的話，第一個(gè)里面還存有第二個(gè)結(jié)點(diǎn)的地址，我們必須在刪除前，保存第二個(gè)結(jié)點(diǎn)的地址
SListNode* next = (*pphead)->next;
free(*pphead);//通過調(diào)試我們發(fā)現(xiàn)：free前后，*pphead的地址不變，但是*pphead里的值被置為隨機(jī)值，free不僅僅把這塊空間還給操作系統(tǒng)
//而且還把這塊空間存的值和地址都置為隨機(jī)值
*pphead = next;
}
}
5、單鏈表查找
//單鏈表查找
SListNode* SListFind(SListNode* phead, SListDataType x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
6、中間插入（在pos后面進(jìn)行插入）
void SListInserAfter(SListNode** pphead,SListNode* pos, SListDataType x)
{
assert(pos && pphead);
if (*pphead == pos)
{
SListPushFront(pphead, x);
}
else
{
SListNode* newnode = BuySListNode(x);
SListNode* tmp = *pphead;
while (tmp->next != pos)
{
tmp = tmp->next;
}
tmp->next = pos;
pos->next = newnode;
}
}
7、中間刪除（在pos后面進(jìn)行刪除）
void SListEraseAfter(SListNode* pos)
{
//刪除pos后面的
assert(pos);
if (pos->next)
{
//pos->next=pos->next->next//不推薦
SListNode* next = pos->next;
SListNode* nextnext = next->next;
pos->next = nextnext;
free(next);
}
}
8、單獨(dú)打印鏈表和從頭到尾打印鏈表
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void PrintTailToHead(SListNode* pList)
{
if (pList == NULL)
{
return;
}
PrintTailToHead(pList->next);
printf("%d->",pList->data);
}
9、test.c
#include"SList.h"
TestSList1()
{
SListNode* pList = NULL;//這個(gè)結(jié)構(gòu)體指針指向開辟的空間,頭指針指向鏈表的開頭
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 3);
SListPushBack(&pList, 4);
SListPrint(pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPrint(pList);
SListPushFront(&pList, 1);
SListPushFront(&pList, 2);
SListPushFront(&pList, 6);
SListPushFront(&pList, 4);
SListPushFront(&pList, 5);
SListPrint(pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPopFront(&pList);
SListPrint(pList);
}
TestSList2()
{
SListNode* pos1;
SListNode* pList = NULL;//這個(gè)結(jié)構(gòu)體指針指向開辟的空間,頭指針指向鏈表的開頭
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 3);
SListPushBack(&pList, 4);
SListPrint(pList);
SListNode* pos = SListFind(pList, 3);
if (pos)
{
pos->data = 30;//這里將cur-data改為pos->data,然后再將pos-data原來的值改為30
}
SListPrint(pList);
pos1 = SListFind(pList, 30);//我們先去找到這個(gè)pos1的位置，然后再去插入
SListInserAfter(&pList,pos1,50);//函數(shù)傳參要對應(yīng)起來，我們用指針傳用指針接收，不能在pos1位置直接寫個(gè)數(shù)字
SListPrint(pList);
SListEraseAfter(pos1);//pList指向第一個(gè)結(jié)點(diǎn)，pList->next指向第二個(gè)結(jié)點(diǎn)，那么我們刪除的是目標(biāo)節(jié)點(diǎn)后面
SListPrint(pList);
//PrintTailToHead(&pList);
}
int main()
{
TestSList1();
TestSList2();
return 0;
}
總結(jié)
到此這篇關(guān)于C語言如何實(shí)現(xiàn)單鏈表的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言 完整游戲項(xiàng)目坦克大戰(zhàn)詳細(xì)代碼
《坦克大戰(zhàn)》以二戰(zhàn)坦克為題材,既保留了射擊類游戲的操作性,也改進(jìn)了射擊類游戲太過于復(fù)雜難玩的高門檻特點(diǎn),集休閑與競技于一身。經(jīng)典再度襲來,流暢的畫面,瘋狂的戰(zhàn)斗,讓玩家再次進(jìn)入瘋狂坦克的世界。玩家的目標(biāo)是控制坦克躲避危險(xiǎn),消滅掉所有的敵人即可進(jìn)入下一關(guān)2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單電子通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-06-06
關(guān)于c++編譯protobuf時(shí)提示LNK2001 無法解析的外部符號的問題
這篇文章主要介紹了關(guān)于c++編譯protobuf時(shí)提示LNK2001 無法解析的外部符號的問題,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
C/C++是兩種廣泛使用的編程語言,特別是在系統(tǒng)編程、嵌入式開發(fā)以及高性能計(jì)算領(lǐng)域,這篇文章主要介紹了C/C++錯(cuò)誤信息處理的常見方法及函數(shù),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-04-04
這篇文章主要給大家介紹了C++語言中定義全局變量，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2021-10-10
C++通過循環(huán)實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要為大家詳細(xì)介紹了C++通過循環(huán)實(shí)現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-09-09
本文主要介紹了QChart繪制折線圖，Qt Charts基于Qt的Graphics View架構(gòu)，其核心組件是QChartView 和 QChart，感興趣的可以了解一下2022-04-04
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡單五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要介紹了C語言實(shí)現(xiàn)簡單的《三子棋》,本文通過功能區(qū)分一步步實(shí)現(xiàn)該案例,通過逐步的解析和代碼列舉,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語言中操作utmp文件的相關(guān)函數(shù)用法
這篇文章主要介紹了C語言中操作utmp文件的相關(guān)函數(shù)用法,包括getutent()函數(shù)和setutent()函數(shù)以及endutent()函數(shù),需要的朋友可以參考下2015-08-08