日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無(wú)先后，達(dá)者為師

網(wǎng)站首頁(yè) 編程語(yǔ)言 正文

C語(yǔ)言中單鏈表(不帶頭結(jié)點(diǎn))基本操作的實(shí)現(xiàn)詳解_C 語(yǔ)言

作者：蝸牛牛啊 ? 更新時(shí)間： 2022-12-12 編程語(yǔ)言

通過(guò)對(duì)順序表的學(xué)習(xí)，我們可以發(fā)現(xiàn)順序表有以下幾點(diǎn)缺陷：

1.空間不夠時(shí)需要擴(kuò)容，擴(kuò)容尤其是用realloc進(jìn)行異地?cái)U(kuò)容時(shí)，是有一定代價(jià)的，其次還可能存在一定空間浪費(fèi)。

2.頭部或者中間插入刪除，需要挪動(dòng)數(shù)據(jù)，效率低下。

那我們可以對(duì)其所具有的缺陷進(jìn)行優(yōu)化：可以按需申請(qǐng)空間同時(shí)插入刪除時(shí)不挪動(dòng)數(shù)據(jù)。而單鏈表就符合這些優(yōu)化所具有特點(diǎn)。但是我們要注意的是單鏈表具有這些優(yōu)點(diǎn)并不代表鏈表就可以完全替代順序表。

一、單鏈表的概念

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

從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)，物理結(jié)構(gòu)中指針域存儲(chǔ)的是下一個(gè)結(jié)點(diǎn)的地址；而且鏈?zhǔn)浇Y(jié)構(gòu)的結(jié)點(diǎn)一般都是從堆上申請(qǐng)出來(lái)的；從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)。鏈表存儲(chǔ)數(shù)據(jù)的區(qū)域可分為數(shù)據(jù)域和指針域：

用代碼表示鏈表中的數(shù)據(jù)域和指針域如下：

typedef int STLDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}STLNode;

思考：為什么在申請(qǐng)的時(shí)候需要申請(qǐng)堆上的空間？因?yàn)槎焉仙暾?qǐng)的空間存儲(chǔ)數(shù)據(jù)的時(shí)候不會(huì)因?yàn)楹瘮?shù)銷毀而銷毀，堆上的空間需要的時(shí)候就申請(qǐng)，不需要的時(shí)候就釋放；函數(shù)棧幀上開辟的空間存儲(chǔ)的數(shù)據(jù)會(huì)因?yàn)楹瘮?shù)棧幀的銷毀而釋放，后面在進(jìn)行尾插和頭插時(shí)候新的結(jié)點(diǎn)不能鏈接到表上。

二、單鏈表的基本操作

1.創(chuàng)建單個(gè)結(jié)點(diǎn)

SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("BuySLTNode malloc");
        exit(-1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

2.創(chuàng)建具有n個(gè)結(jié)點(diǎn)的鏈表

SLTNode* CreateSList(int n)
{
    int i = 0;
    SLTNode* ptail = NULL,*phead = NULL;
    for (i = 0; i < n; i++)
    {
        SLTNode* newnode = BuySLTNode(i);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//    int i = 0;
//    SLTNode* ptail = NULL;
//    for (i = 0; i < n; i++)
//    {
//        SLTNode* newnode = BuySLTNode(i);
//        if (*pphead == NULL)
//        {
//            ptail = *pphead = newnode;
//        }
//        else
//        {
//            ptail->next= newnode;
//            ptail = newnode;
//        }
//    }
//}

上述代碼中提供了兩種實(shí)現(xiàn)方式，沒(méi)有注釋的是返回頭指針的，注釋內(nèi)容是沒(méi)有返回值，形參使用的是二級(jí)指針改變頭指針指向的地址。

3.打印單鏈表

void SLTPrint(SLTNode* phead)
{
    SLTNode* tail = phead;
    while (tail)
    {
        printf("%d ", tail->val);
        tail = tail->next;
    }
    printf("\n");
}

4.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
    SLTNode* tail = *pphead;
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾插時(shí)，要注意當(dāng)單鏈表的頭結(jié)點(diǎn)為空的時(shí)候，要先將新結(jié)點(diǎn)作為頭結(jié)點(diǎn)。因?yàn)楫?dāng)頭結(jié)點(diǎn)為空時(shí)，需要改變頭指針，所以傳過(guò)來(lái)的為二級(jí)指針（也可以使用一級(jí)指針，不過(guò)此時(shí)要有返回值），要想改變SLTNode*的值，就要傳遞它的地址即SLTNode**類型。

5.尾刪

void SLTPopBack(SLTNode** pphead)//尾刪
{
    assert(*pphead);
    if ((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

尾刪時(shí)也要注意區(qū)分是否為頭結(jié)點(diǎn)；同時(shí)注意刪除后，要將其置空prev->next = NULL。

6.頭插

void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

7.頭刪

void SLTPopFront(SLTNode** pphead)//頭刪
{
    assert(*pphead);
    SLTNode* nextnode = (*pphead)->next;
    free(*pphead);
    *pphead = nextnode;
}

頭插和頭刪是單鏈表的優(yōu)勢(shì)，尾插和尾刪是順序表的優(yōu)勢(shì)。同時(shí)在尾刪時(shí)注意將*pphead加上括號(hào)用來(lái)區(qū)分優(yōu)先級(jí)，否則會(huì)報(bào)錯(cuò)。

8.查找某個(gè)結(jié)點(diǎn)

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個(gè)數(shù)并返回所在位置
{
    SLTNode* tail = phead;
    while (tail)
    {
        if (tail->val == x)
        {
            return tail;
        }
        tail = tail->next;
    }
    return NULL;
}

注意循環(huán)條件，當(dāng)循環(huán)條件寫為while(tail->next)時(shí)，會(huì)有空指針的風(fēng)險(xiǎn)，同時(shí)還會(huì)漏掉最后一個(gè)結(jié)點(diǎn)。

9.在某個(gè)結(jié)點(diǎn)后面插入

void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個(gè)結(jié)點(diǎn)的后面插入某個(gè)數(shù)
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = pos->next;
    pos->next = newnode;
    newnode->next = tail;
}

10.在某個(gè)結(jié)點(diǎn)前面插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某個(gè)結(jié)點(diǎn)的前面插入某個(gè)數(shù)
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    if (pos == *pphead)
    {
        /*newnode->next = *pphead;
        *pphead = newnode;*/
        SLTPushBack(pphead, x);
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = newnode;
        newnode->next = pos;
    }
}

11.刪除某個(gè)位置后面的結(jié)點(diǎn)

void SLTEraseAfter(SLTNode* pos)//刪除pos位置之后的那個(gè)位置
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLTNode* tail = pos->next;
        pos->next = tail->next;
        free(tail);
    }
}

12.刪除某個(gè)結(jié)點(diǎn)

void SLTErase(SLTNode** pphead, SLTNode* pos)//刪除pos位置
{
    assert(pos);
    SLTNode* tail = *pphead;
    if (pos == *pphead)
    {
        SLTNode* nextNode = (*pphead)->next;
        free(*pphead);
        *pphead = nextNode;
    }
    else
    {
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = pos->next;
        free(pos);
    }
}

13.銷毀單鏈表

void SLTDestroy(SLTNode** pphead)//銷毀
{
    assert(*pphead);
    SLTNode* tail = *pphead;
    
    while (tail)
    {
        SLTNode* next = tail->next;
        free(tail);
        tail = next;
    }
    *pphead = NULL;
}

注意最后要將頭結(jié)點(diǎn)置空。

三、測(cè)試代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SList {
	struct Slist* next;
	SLTDataType val;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
SLTNode* CreateSList(int n)
{
	int i = 0;
	SLTNode* ptail = NULL, * phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}
void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead;
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)//尾刪
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)//頭刪
{
	assert(*pphead);
	SLTNode* nextnode = (*pphead)->next;
	free(*pphead);
	*pphead = nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個(gè)數(shù)并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個(gè)結(jié)點(diǎn)的后面插入某個(gè)數(shù)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
	pos->next = newnode;
	newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某個(gè)結(jié)點(diǎn)的前面插入某個(gè)數(shù)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = pos;
	}
}
void SLTEraseAfter(SLTNode* pos)//刪除pos位置之后的那個(gè)位置
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//刪除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}
void SLTDestroy(SLTNode** pphead)//銷毀
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}
void TestSL()
{
	SLTNode* plist = CreateSList(2);
	/*SLTNode* plist = NULL;
	CreateSList(&plist,10);//沒(méi)有返回值
	SLTPrint(plist);*/
	SLTPushBack(&plist, 600);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist, 300);
	SLTPushFront(&plist, 400);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 600);
	if (pos)
	{
		SLInsertAfter(pos, 700);
		SLTInsert(&plist, pos, 500);
		SLTEraseAfter(pos);
		//SLTErase(&plist, pos);

	}
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}
int main()
{
	TestSL();
	return 0;
}

原文鏈接：https://blog.csdn.net/weixin_53943591/article/details/127705136

欄目分類
最近更新