天天看點
傳回

C語言實作單連結清單（無頭+單向+非循環連結清單）前言

不積跬步無以至千裡

文章目錄

  • 前言
    • 1 連結清單的概念及結構
    • 2 單連結清單的實作
      • 2.1 建立一個連結清單的節點
      • 2.2 動态申請一個結點
      • 2.3 建立一個n個節點的連結清單(用于測試)
      • 2.4 單連結清單的列印
      • 2.5 單連結清單的尾插(重點)
        • 問題一
        • 問題二
        • 完整尾插代碼
      • 2.6 單連結清單的尾删
      • 2.7 單連結清單的頭插
      • 2.8 單連結清單的頭删
      • 2.9 單連結清單的查找
      • 2.10 在pos之後插入節點
      • 2.11 在pos之前插入節點
      • 2.12 删除pos之後的節點
      • 2.13 删除pos位置的節點
      • 2.14 單連結清單的删除
    • 3 程式源碼
      • `SListNode.h`代碼
      • `SListNode.c`代碼
      • `test.c`代碼

前言

關于順序表的問題：

  1. 中間/頭部的插入删除，時間複雜度為O(N)
  2. 增容需要申請新空間，拷貝資料，釋放舊空間。會有不小的消耗。

  3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如目前容量為100，滿了以後增容到200，我們再繼續插入了5個資料，後面沒有資料插入了，那麼就浪費了95個資料空間。

    思考：如何解決以上問題呢？下面給出了連結清單的結構來看看

1 連結清單的概念及結構

概念：連結清單是一種實體存儲結構上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的 。

連結清單的結構由很多種，但是最常用的是無頭單項非循環單連結清單和帶頭雙向循環連結清單

C語言實作單連結清單（無頭+單向+非循環連結清單）前言
  1. 無頭單向非循環連結清單：結構簡單，一般不會單獨用來存資料。實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等。
  2. 帶頭雙向循環連結清單：結構最複雜，一般用在單獨存儲資料。實際中使用的連結清單資料結構，都是帶頭雙向循環連結清單。另外這個結構雖然結構複雜，但是使用代碼實作以後會發現結構會帶來很多優勢，實作反而簡單了。

2 單連結清單的實作

需要建立一個小項目工程

建立三個檔案

⭐SListNode.h放單連結清單的頭檔案，函數聲明

⭐SListNode.c放單連結清單的函數

⭐test.c是主函數，存放架構，測試函數

2.1 建立一個連結清單的節點

首先，我們可以類比順序表，在建立順序表的時候，是用一個結構體來建立的,是以我們可以用結構體建立，包括資料和下一個結構體的位址(用來找到下一個位址) 
typedef int SLTDataType;

//建立一個單連結清單的節點
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

為什們用動态開辟？

首先我們知道局部變量出了作用域，就自己消除了，如果我們在一個函數中自己申請空間用來建立結構體，如果我們出了這個函數，我們就找不到這個連結清單，但是如果用動态空間，所開辟的空間在堆上存放，即便我們出了作用域，我們都來能找到這個連結清單，這就是我們動态開辟的原因。

2.2 動态申請一個結點

前面隻是建立了一個節點的結構，我們現在在對上面的每個節點動态開辟一塊空間，并且為每個節點初始化一下。 
//在堆上為每個節點申請空間，将data指派為x,将next指派為NULL
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.3 建立一個n個節點的連結清單(用于測試)

本步驟是為了測試連結清單到底有沒有建立好，為後續步驟做鋪墊的，不屬于單連結清單的結構。 
//建立指定數量的的節點，傳回頭節點的指針,為了測試用的
SListNode* CreatSListNode(SLTDataType n)
{
	int i = 0;
	SListNode* phead = NULL;
	SListNode* ptail = NULL;
	for (i = 0; i < n; i++)
	{
		SListNode* newnode = BuySListNode(i); //建立一個節點，指派為i
		if (ptail == NULL)
		{
			phead = ptail = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}

測試結果如下：可以看到很好的建立成功了

C語言實作單連結清單（無頭+單向+非循環連結清單）前言

2.4 單連結清單的列印

我們上面建立了連結清單，我們為了顯示我們的連結清單，我們就要列印連結清單，進而顯示我們連結清單，我們怎麼列印連結清單，就仔細看代碼就可以了，大家多看看注釋，這很重要。 
//列印節點
void PrintSListNode(SListNode* phead)
{
	//我們想一想，如果連結清單為空可不可以列印
	//很顯然是可以的，我們列印一個空指針就很OK
	//是以我們不對他進行斷言

	//我們一般不動我們的頭指針，是以我們要找一個東西代替他
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//因為最後一個肯定是空指針
	//為了列印的美觀，我們列印一個空指針
	printf("NULL\n");
}

2.5 單連結清單的尾插(重點)

現在我們将一個簡易的連結清單做了出來，我們要實作連結清單的功能。

首先實作尾插的功能，但是有很多注意的事項，我們先看兩段有點問題的代碼，首先先自己想一下問題是什們，然後自己再看答案，我們隻要解決了這個問題我們的功能基本上就解決了

問題一

C語言實作單連結清單（無頭+單向+非循環連結清單）前言

問題二 

//單連結清單尾插
void SLTPushBack(SLTNode* phead,SLTDataType n)
{
	SLTNode* newnode = BuySLTNode(n);
	SLTNode* tail = phead;
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next= newnode;
}
對于問題一，我們可以修改一下代碼，将tail->next作為判斷條件，這樣走到最後一個節點就停下來了,因為最後一個節點的下一個為NULL

但是如果我們的連結清單為空的時候，我們能不能在尾插内容呢？

答案顯而易見，當然是可以的，但是這時tail是NULL,我們在進行這個條件的時候tail->next，這時就發生了空指針的解引用。

于是我們可以用if條件差別一下空指針。我們先看代碼。和調試。 
//單連結清單尾插
void SLTPushBack(SLTNode* phead,SLDataType n)
{
	SLTNode* newnode = BuySLTNode(n);
	SLTNode* tail = phead;
	if (phead == NULL)
	{
		tail = phead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
我們發現在我們進行測試的時候，我們開頭是空指針的時候，并沒有尾插上，到底是什們原因呢？
C語言實作單連結清單（無頭+單向+非循環連結清單）前言

重點：

C語言實作單連結清單（無頭+單向+非循環連結清單）前言

是以我們想要改變

phead

，我們需要通過

phead

的指針來改變

phead

也就要用到二級指針

完整尾插代碼

C語言實作單連結清單（無頭+單向+非循環連結清單）前言
//尾插節點
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);

	//當連結清單為空時
	if (*pphead == NULL)
	{
		*pphead = newnode;  //修改頭
	}
	else
	{
		SListNode* tail = *pphead;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		//連結上
		tail->next = newnode;
	}
}

2.6 單連結清單的尾删

這裡後續除了列印和删除連結清單外，其他的都需要二級指針，因為要改變頭指針

plist

 
//尾删節點
void SListPopBack(SListNode** pphead)
{
	assert(*pphead);
	//隻有一個
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;  //最後一個的前一個
		//找尾
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);	//删除尾
		prev->next = NULL;
	}
}

2.7 單連結清單的頭插 

//頭插節點
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x); //建立一個節點
	newnode->next = *pphead; //連結頭
	*pphead = newnode; //更新頭
}

2.8 單連結清單的頭删 

//頭删節點
void SListPopFront(SListNode** pphead)
{
	assert(*pphead); //防止空指針解引用

	SListNode* next = (*pphead)->next; //儲存頭的下一個
	free(*pphead);	//删除頭
	*pphead = next;	//更新頭
}

2.9 單連結清單的查找

因為我們後面要進行，在連結清單的中間進行添加和删除，我們就是需要，先找到我們需要在哪裡添加和删除，我們就要進行查找。因為查找我們不需要進行修改頭指針，是以我們就不需要用二級指針。用一級指針就可以了。

我們知道了為什們查找，是以我們就看下面的代碼吧

//查找節點是否存在，存在傳回位置，否則傳回空指針
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
我們可以測試一下這個函數,在連結清單裡面查找100
C語言實作單連結清單（無頭+單向+非循環連結清單）前言

2.10 在pos之後插入節點

在

pos

之後插入節點,配合

SListFind()

使用，先找到位置，再插入

//在pos之後插入節點
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	//方法1
	/*SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;*/

	//方法2：以前儲存下一個節點
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;  //儲存pos的下一個
	pos->next = newnode;
	newnode->next = next;
}
可以看到我們很好的在1後面插入了100
C語言實作單連結清單（無頭+單向+非循環連結清單）前言

2.11 在pos之前插入節點 

//在pos之前插入節點
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pos);  //如果*pphead為空，assert(pos)就會報錯了，是以不需要assert(*pphead)

	//pos在第一個位置
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		//找pos前一個的位置
		SListNode* prev = *pphead; 
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

2.12 删除pos之後的節點 

//删除pos之後的節點
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);   //防止pos之後沒有節點

	SListNode* next = pos->next->next; //儲存pos的下下個節點
	free(pos->next);
	pos->next = next;
}

2.13 删除pos位置的節點 

//删除pos位置的節點
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pos);

	//pos在第一個位置
	if (pos == *pphead)
	{
		SListPopFront(pphead); //頭删
	}
	else
	{
		SListNode* prevNode = *pphead;
		//找pos的前一個
		while (prevNode->next != pos)
		{
			prevNode = prevNode->next;
		}
		prevNode->next = pos->next;
		free(pos);
	}
}

2.14 單連結清單的删除 

//删除單連結清單
void SListDestroy(SListNode** pphead)
{

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

3 程式源碼

SListNode.h

 代碼 

#pragma once

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


typedef int SLTDataType;

//建立一個單連結清單的節點
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;


//在堆上為每個節點申請空間，将data指派為x,将next指派為NULL
SListNode* BuySListNode(SLTDataType x);


//建立指定數量的的節點，為了測試用的
SListNode* CreatSListNode(SLTDataType n);

//列印節點
void PrintSListNode(SListNode* phead);

//尾插和尾删節點
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPopBack(SListNode** pphead);

//頭插和頭删節點
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPopFront(SListNode** pphead);

//查找節點是否存在
SListNode* SListFind(SListNode* phead, SLTDataType x);

//在pos之後插入節點
void SListInsertAfter(SListNode* pos, SLTDataType x);
//删除pos之後的節點
void SListEraseAfter(SListNode* pos);


//在pos之前插入節點
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//删除pos位置的節點
void SListErase(SListNode** pphead, SListNode* pos);


//删除單連結清單
void SListDestroy(SListNode** pphead);

SListNode.c

 代碼 

#define _CRT_SECURE_NO_WARNINGS 1

#include "slist.h"

//在堆上為每個節點申請空間，将data指派為x,将next指派為NULL
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//建立指定數量的的節點，傳回頭節點的指針,為了測試用的
SListNode* CreatSListNode(SLTDataType n)
{
	int i = 0;
	SListNode* phead = NULL;
	SListNode* ptail = NULL;
	for (i = 0; i < n; i++)
	{
		SListNode* newnode = BuySListNode(i);
		if (ptail == NULL)
		{
			phead = ptail = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}


//列印節點
void PrintSListNode(SListNode* phead)
{
	//我們想一想，如果連結清單為空可不可以列印
	//很顯然是可以的，我們列印一個空指針就很OK
	//是以我們不對他進行斷言

	//我們一般不動我們的頭指針，是以我們要找一個東西代替他
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//因為最後一個肯定是空指針
	//為了列印的美觀，我們列印一個空指針
	printf("NULL\n");
}


//删除單連結清單
void SListDestroy(SListNode** pphead)
{

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

//尾插節點
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);

	//當連結清單為空時
	if (*pphead == NULL)
	{
		*pphead = newnode;  //修改頭
	}
	else
	{
		SListNode* tail = *pphead;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		//連結上
		tail->next = newnode;
	}
}

//尾删節點
void SListPopBack(SListNode** pphead)
{
	assert(*pphead);
	//隻有一個
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;  //最後一個的前一個
		//找尾
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);	//删除尾
		prev->next = NULL;
	}
}


//頭插節點
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x); //建立一個節點
	newnode->next = *pphead; //連結頭
	*pphead = newnode;		//更新頭
}

//頭删節點
void SListPopFront(SListNode** pphead)
{
	assert(*pphead); //防止空指針解引用

	SListNode* next = (*pphead)->next; //儲存頭的下一個
	free(*pphead);	//删除頭
	*pphead = next;	//更新頭
}




//查找節點是否存在，存在傳回位置，否則傳回空指針
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}



//在pos之後插入節點
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);  
	//方法1
	/*SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;*/

	//方法2：以前儲存下一個節點
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;  //儲存pos的下一個
	pos->next = newnode;
	newnode->next = next;
}

//删除pos之後的節點
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);   //防止pos之後沒有節點

	SListNode* next = pos->next->next; //儲存pos的下下個節點
	free(pos->next);
	pos->next = next;
}


//在pos之前插入節點
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pos);  //如果*pphead為空，assert(pos)就會報錯了，是以不需要assert(*pphead)

	//pos在第一個位置
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		//找pos前一個的位置
		SListNode* prev = *pphead; 
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}


//删除pos位置的節點
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pos);

	//pos在第一個位置
	if (pos == *pphead)
	{
		SListPopFront(pphead); //頭删
	}
	else
	{
		SListNode* prevNode = *pphead;
		//找pos的前一個
		while (prevNode->next != pos)
		{
			prevNode = prevNode->next;
		}
		prevNode->next = pos->next;
		free(pos);
	}
}

test.c

 代碼 

#define _CRT_SECURE_NO_WARNINGS 1

#include "slist.h"

//測試建立一個長度為n的連結清單，并列印
void test1()
{
	SListNode* plist = CreatSListNode(5);
	PrintSListNode(plist);

	SListDestroy(&plist);//這個後續實作，這裡為了防止記憶體洩漏就先寫了
}


//測試尾插尾删
void test2()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);

	SListPopBack(&plist);
	SListPopBack(&plist);
	//SListPopBack(&plist);

	PrintSListNode(plist);
	SListDestroy(&plist);
}


//測試頭插頭删
void test3()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);

	SListPopFront(&plist);
	SListPopFront(&plist);

	PrintSListNode(plist);
	SListDestroy(&plist);
}

//測試查找數字是否存在
void test4()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);

	PrintSListNode(plist);

	SListNode* ret = SListFind(plist, 100);
	if (ret != NULL)
	{
		printf("該數字存在\n");
	}
	else
	{
		printf("該數字不存在\n");
	}

	SListDestroy(&plist);
}


//在pos之後插入節點,配合SListFind()使用
void test5()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);

	PrintSListNode(plist);

	SListNode* pos = SListFind(plist, 1);  //找到1的位置
	if (pos != NULL)
	{
		SListInsertAfter(pos, 100); //在1的後面插入100
		PrintSListNode(plist);
	}
	else
	{
		printf("該數字不存在\n");
	}

	SListDestroy(&plist);
}

//删除pos之後的元素
void test6()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);

	SListNode* pos = SListFind(plist, 2);  //找到1的位置
	if (pos != NULL)
	{
		SListEraseAfter(pos); //删除2
		PrintSListNode(plist);
	}
	else
	{
		printf("該數字不存在\n");
	}

	SListDestroy(&plist);
}

//在pos之前插入節點,配合SListFind()使用
void test7()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);

	SListNode* pos = SListFind(plist, 3);  //找到1的位置
	if (pos != NULL)
	{
		SListInsert(&plist, pos, 100);
		PrintSListNode(plist);
	}
	else
	{
		printf("該數字不存在\n");
	}

	SListDestroy(&plist);
}


//删除pos位置的元素
void test8()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);

	SListNode* pos = SListFind(plist, 1);  //找到1的位置
	SListErase(&plist, pos);

	PrintSListNode(plist);
	SListDestroy(&plist);
}



int main()
{

	test5();
	return 0;
}
資料結構初階(C語言) 連結清單 c語言 資料結構
上一篇: 2023年電動汽車驅動子產品行業頭部企業市場占有率及排名調研報告
下一篇: 模拟strcpy庫函數的實作（超詳細）前言一、簡介二、模拟實作strcpy三、傳回值四、完整代碼總結

繼續閱讀