亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時間：2022年11月14日 11:36:24   作者：蝸牛牛啊  
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文主要和大家聊聊C語言中單鏈表(不帶頭結(jié)點)的基本操作，感興趣的小伙伴可以了解一下

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

1.空間不夠時需要擴容，擴容尤其是用realloc進行異地擴容時，是有一定代價的，其次還可能存在一定空間浪費。

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

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

一、單鏈表的概念

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

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

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

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

思考：為什么在申請的時候需要申請堆上的空間？因為堆上申請的空間存儲數(shù)據(jù)的時候不會因為函數(shù)銷毀而銷毀，堆上的空間需要的時候就申請，不需要的時候就釋放；函數(shù)棧幀上開辟的空間存儲的數(shù)據(jù)會因為函數(shù)棧幀的銷毀而釋放，后面在進行尾插和頭插時候新的結(jié)點不能鏈接到表上。

二、單鏈表的基本操作

1.創(chuàng)建單個結(jié)點

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個結(jié)點的鏈表

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;
//        }
//    }
//}

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

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;
    }
}

尾插時，要注意當(dāng)單鏈表的頭結(jié)點為空的時候，要先將新結(jié)點作為頭結(jié)點。因為當(dāng)頭結(jié)點為空時，需要改變頭指針，所以傳過來的為二級指針（也可以使用一級指針，不過此時要有返回值），要想改變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;
    }
}

尾刪時也要注意區(qū)分是否為頭結(jié)點；同時注意刪除后，要將其置空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)勢，尾插和尾刪是順序表的優(yōu)勢。同時在尾刪時注意將*pphead加上括號用來區(qū)分優(yōu)先級，否則會報錯。

8.查找某個結(jié)點

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個數(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)時，會有空指針的風(fēng)險，同時還會漏掉最后一個結(jié)點。

9.在某個結(jié)點后面插入

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

10.在某個結(jié)點前面插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某個結(jié)點的前面插入某個數(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.刪除某個位置后面的結(jié)點

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

12.刪除某個結(jié)點

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é)點置空。

三、測試代碼

#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)//查找某個數(shù)并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個結(jié)點的后面插入某個數(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)//在某個結(jié)點的前面插入某個數(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位置之后的那個位置
{
	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);//沒有返回值
	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;
}

以上就是C語言中單鏈表(不帶頭結(jié)點)基本操作的實現(xiàn)詳解的詳細內(nèi)容，更多關(guān)于C語言單鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • C++代碼實現(xiàn)貪吃蛇小游戲

    C++代碼實現(xiàn)貪吃蛇小游戲

    這篇文章主要為大家詳細介紹了C++貪吃蛇小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2020-11-11
  • C語言在輸入輸出時遇到的常見問題總結(jié)

    C語言在輸入輸出時遇到的常見問題總結(jié)

    大家在平時的做題中是否會遇到和我一樣的煩惱，題目的代碼已經(jīng)基本完成，但是在輸出時候，總是和題目給出的樣例輸出格式不同?，導(dǎo)致題目不能通過。為了解決這一煩惱，我總結(jié)了以下幾點，需要的可以參考一下
    2022-09-09

    • 最新評論