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

學無先后，達者為師

網站首頁 編程語言 正文

C語言中單鏈表(不帶頭結點)基本操作的實現詳解_C 語言

作者：蝸牛牛啊 ? 更新時間： 2022-12-12 編程語言

通過對順序表的學習，我們可以發現順序表有以下幾點缺陷：

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

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

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

一、單鏈表的概念

鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

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

用代碼表示鏈表中的數據域和指針域如下：

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

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

二、單鏈表的基本操作

1.創建單個結點

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.創建具有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;
//        }
//    }
//}

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

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

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

尾刪時也要注意區分是否為頭結點；同時注意刪除后，要將其置空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;
}

頭插和頭刪是單鏈表的優勢，尾插和尾刪是順序表的優勢。同時在尾刪時注意將*pphead加上括號用來區分優先級，否則會報錯。

8.查找某個結點

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

注意循環條件，當循環條件寫為while(tail->next)時，會有空指針的風險，同時還會漏掉最后一個結點。

9.在某個結點后面插入

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

10.在某個結點前面插入

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

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

12.刪除某個結點

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

注意最后要將頭結點置空。

三、測試代碼

#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)//查找某個數并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個結點的后面插入某個數
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
	pos->next = newnode;
	newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某個結點的前面插入某個數
{
	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;
}

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

欄目分類
最近更新