快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)

更新時間：2022年06月29日 11:11:26 作者：。菀枯。

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將用C語言實(shí)現(xiàn)單鏈表，需要的可以參考一下

3.1 創(chuàng)建鏈表前須知
3.2 定義結(jié)構(gòu)體
3.3 申請一個節(jié)點(diǎn)
3.4 鏈表的頭插
3.5 鏈表的尾插
3.6 鏈表的尾刪
3.7 鏈表的頭刪
3.8 尋找某節(jié)點(diǎn)
3.9 在指定節(jié)點(diǎn)前插入節(jié)點(diǎn)
3.10 刪除指定節(jié)點(diǎn)前的節(jié)點(diǎn)
3.11 鏈表的銷毀

一.為什么使用鏈表

在學(xué)習(xí)鏈表以前，我們存儲數(shù)據(jù)用的方式就是數(shù)組。使用數(shù)組的好處就是便于查找數(shù)據(jù)，但缺點(diǎn)也很明顯。

使用前需聲明數(shù)組的長度，一旦聲明長度就不能更改

插入和刪除操作需要移動大量的數(shù)組元素，效率慢

只能存儲一種類型的數(shù)據(jù).

為了解決上述的問題，我們就可以使用鏈表來存儲數(shù)據(jù)。

二.鏈表的概念

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的

三.鏈表的實(shí)現(xiàn)

3.1 創(chuàng)建鏈表前須知

結(jié)點(diǎn):鏈表中每一個元素稱為“結(jié)點(diǎn)”，每個結(jié)點(diǎn)都應(yīng)包括兩個部分：一為用戶需要用的實(shí)際數(shù)據(jù)；二為下一個結(jié)點(diǎn)的地址，

頭結(jié)點(diǎn)：在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn)，這個節(jié)點(diǎn)不存儲數(shù)據(jù)，稱之為頭結(jié)點(diǎn)

3.2 定義結(jié)構(gòu)體

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDateType; //鏈表中存儲的數(shù)據(jù)類型，可換成其他

typedef struct SListNode
{
	SLDateType date;
	struct SListNode* next; //指向下一個節(jié)點(diǎn)的指針
}SListNode;

3.3 申請一個節(jié)點(diǎn)

SListNode* BuyListNode(SLDateType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    if (NULL == newNode)
    {
        printf("malloc error\n"); //內(nèi)存開辟失敗
        exit(-1);
    }
    else
    {
        newNode->date = x; // 給新節(jié)點(diǎn)賦值
        newNode->next = NULL;
    }
    return newNode;
}

3.4 鏈表的頭插

void SListPushFront(SListNode** pphead/*要改動頭指針，所以要傳遞二級指針*/, SLDateType x)
{
    SListNode* newNode = BuyListNode(x); //申請節(jié)點(diǎn)
    newNode->next = *pphead;
    *pphead = newNode;
}

3.5 鏈表的尾插

void SListPushBack(SListNode** pphead, SLDateType x)
{
    SListNode* newNode = BuyListNode(x);
    if (*pphead == NULL) //若頭指針為空，則鏈表為空鏈表，直接將新節(jié)點(diǎn)接到頭指針后
    {
        *pphead = newNode;
    }
    else
    {
        SListNode* tail = *pphead;
        while (tail->next != NULL) //找鏈表的尾部
        {
            tail = tail->next;
        }
        tail->next = newNode;//將新節(jié)點(diǎn)接到尾部
    }
}

3.6 鏈表的尾刪

void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	if (*pphead == NULL)//鏈表為空，則不進(jìn)行任何操作
	{
		return;
	}
	else if ((*pphead)->next == NULL) //鏈表只有一個節(jié)點(diǎn)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//其余情況
	{
		SListNode* tail = *pphead; //鏈表的尾部節(jié)點(diǎn)
		SListNode* pre = NULL;//鏈表尾的前一個節(jié)點(diǎn)
		while (tail->next != NULL)//找尾
		{
			pre = tail;
			tail = tail->next;
		}
		pre->next = tail->next; //將尾節(jié)點(diǎn)的指針域賦值給前一個節(jié)點(diǎn)的指針域
		free(tail);
	}
}

3.7 鏈表的頭刪

void SListPopFront(SListNode** pphead)
{
    assert(pphead);
    if (*pphead == NULL) //鏈表為空什么也不做
    {
        return;
    }
    else
    {
        SListNode* head = *pphead;//記錄原本的第一個節(jié)點(diǎn)
        *pphead = head->next; //讓頭指針指向第二個節(jié)點(diǎn)
        free(head);//釋放第一個節(jié)點(diǎn)
    }
}

3.8 尋找某節(jié)點(diǎn)

SListNode* SListFind(SListNode* phead, SLDateType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->date == x) //找到則返回該節(jié)點(diǎn)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL; //未找到則返回空
}

3.9 在指定節(jié)點(diǎn)前插入節(jié)點(diǎn)

void SListInsert(SListNode** pphead, SListNode* pos/*要插入的位置*/, SLDateType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* cur = *pphead; //當(dāng)前所指向的位置
		SListNode* pre = NULL; //前一個節(jié)點(diǎn)
		while (cur != pos)
		{
			pre = cur;
			cur = cur->next;
		}
		SListNode* newNode = BuyListNode(x);
		pre->next = newNode;
		newNode->next = cur;
	}
}

3.10 刪除指定節(jié)點(diǎn)前的節(jié)點(diǎn)

void SListErase(SListNode** pphead, SListNode* pos/*要插入的位置*/)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* cur = *pphead;
		SListNode* pre = *pphead;
		while (cur != pos)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = cur->next;
		free(cur);
	}
}

3.11 鏈表的銷毀

void SListDestory(SListNode** pphead)
{
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        while (*pphead != NULL)
        {
            SListNode* cur = *pphead;
            *pphead = cur->next;
            free(cur);
        }
    }
}

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語言單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: