數(shù)據(jù)結(jié)構(gòu)：線性表之-單向鏈表(無頭)

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)：線性表之-單向鏈表(無頭)。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

什么是單向鏈表

順序表和鏈表的區(qū)別和聯(lián)系

順序表：

鏈表：

鏈表表示(單項)和實現(xiàn)

1.1 鏈表的概念及結(jié)構(gòu)

1.2單鏈表(無頭)的實現(xiàn)

所用文件

將有以下功能：

鏈表定義

創(chuàng)建新鏈表元素

尾插

頭插

尾刪

頭刪

查找-給一個節(jié)點的指針

改

pos位置之前插入

刪除pos位置的值

成品展示

SList.h

SList.c

test.c

什么是單向鏈表

單向鏈表是一種常見的線性數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點組成，每個節(jié)點包含兩部分：數(shù)據(jù)和指向下一個節(jié)點的指針。每個節(jié)點只能訪問它后面的節(jié)點，而不能訪問前面的節(jié)點。

單向鏈表的特點：

每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。
最后一個節(jié)點的指針指向空值（NULL），表示鏈表的結(jié)束。
可以動態(tài)地添加或刪除節(jié)點，鏈表的長度可以根據(jù)需要進(jìn)行擴(kuò)展或縮小。
可以根據(jù)指針迅速插入或刪除節(jié)點，而不需要移動其他節(jié)點。

單向鏈表相對于數(shù)組來說，具有一些優(yōu)點和缺點：

優(yōu)點：插入和刪除元素的時間復(fù)雜度為O(1)，不需要像數(shù)組一樣進(jìn)行元素的移動；鏈表長度可以動態(tài)調(diào)整，沒有固定大小的限制。
缺點：要訪問特定位置的元素需要從頭開始遍歷，時間復(fù)雜度為O(n)；相比于數(shù)組，在使用額外的指針存儲下一個節(jié)點的信息，會占用更多的內(nèi)存空間。

由于單向鏈表的特點，它常常被用于需要頻繁插入和刪除元素的場景，或者在事先無法確定數(shù)據(jù)大小和數(shù)量的情況下使用。

順序表和鏈表的區(qū)別和聯(lián)系

順序表：

優(yōu)點：
空間連續(xù)、支持隨機(jī)訪問
缺點：

中間或前面部分的插入刪除時間復(fù)雜度O(N)
2.增容的代價比較大。

鏈表：

缺點：
以節(jié)點為單位存儲，不支持隨機(jī)訪問
優(yōu)點：

任意位置插入刪除時間復(fù)雜度為O(1)
沒有增容消耗，按需申請節(jié)點空間，不用了直接釋放。

鏈表表示(單項)和實現(xiàn)

1.1 鏈表的概念及結(jié)構(gòu)

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

1.2單鏈表(無頭)的實現(xiàn)

數(shù)據(jù)結(jié)構(gòu)：線性表之-單向鏈表(無頭),數(shù)據(jù)結(jié)構(gòu),鏈表,數(shù)據(jù)結(jié)構(gòu)

? 數(shù)據(jù)結(jié)構(gòu)：線性表之-單向鏈表(無頭),數(shù)據(jù)結(jié)構(gòu),鏈表,數(shù)據(jù)結(jié)構(gòu)

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都
是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶
來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

所用文件

定義三個文件：

頭文件 SList.h
函數(shù)的實現(xiàn)SList.c
代碼的測試test.c

將有以下功能：

//打印鏈表
void SListPrint(SLTNode* phead);

//創(chuàng)建新鏈表元素（動態(tài)申請一個節(jié)點）
SLTNode* BuySListNode(SLTDataType x);

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//尾刪
void SListPopBack(SLTNode** pphead);

//頭刪
void SListPopFront(SLTNode** pphead);

//查找->可在查找的基礎(chǔ)上進(jìn)行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);

//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);

//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

鏈表定義

定義鏈表基本結(jié)構(gòu)

typedef struct SListNode
{
	int data;
	struct SListNode* next;
}SLTNode;

創(chuàng)建新鏈表元素

創(chuàng)建新元素用于插入原鏈表

SLTNode* BuySListNode(SLTDataType x)
{
	//開辟空間
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//開辟空間
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		//防止開始時節(jié)點為空
		*pphead = newnode;
	}
	else
	{
		//找尾節(jié)點
		SLTNode* tail = *pphead;//找到鏈表首元素
		while (tail->next != NULL)
		{
			//檢索到未節(jié)點
			tail = tail->next;
		}
		//插入
		tail->next = newnode;
	}
}

頭插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;//地址傳給pphead  
	//*pphead=&plist
	
	/*
		頭插無需檢查是否為空
	*/
}

尾刪

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		//1，只有一個節(jié)點

		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2，有多個節(jié)點
		
		//將前一個鏈元素中存放的地址換為NULL，防止野指針
		/* 寫法一 */
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tailPrev = tail;//tail的地址
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;

		/* //寫法二
		* //tail尋找的是倒數(shù)第二個元素
		while (tail->next->next!=NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
		*/
	}
}

頭刪

void SListPopFront(SLTNode** pphead)
{ 
	//防止被刪空
	assert(*pphead);
	
	//找到首位鏈表元素
	SLTNode* next = (*pphead)->next;//存儲首元素存放下一個元素的地址
	free(*pphead);//釋放首元素
	*pphead = next;//將第二位元素改為首元素
}

查找-給一個節(jié)點的指針

//無需更改元素，故傳一級指針
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data==x)
			return cur;
		cur = cur->next;
	}
	//未找到指定元素，返回NULL
	return NULL;
}

改

改元素是建立再查找基礎(chǔ)之上進(jìn)行更改

void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
	printf("修改成功:\n");
	//先找到相應(yīng)元素，再進(jìn)行更改
	SLTNode* ret = SListFind(phead, y);
	ret->data = x;
}

pos位置之前插入

任意位置之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	//頭插
	if (pos == *pphead)
		SListPushFront(pphead, x);
	else
	{ 
		//任意位置之前插入
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
		}
		//找到位置
		SLTNode* newnode = BuySListNode(x);//創(chuàng)建新鏈表元素，并賦值
		prev->next = newnode;//給前一個元素賦上下一元素地址
		newnode->next = pos;//給插入元素存放下一個元素的地址
	}
}

刪除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
		SListPopFront(pphead);//頭刪
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
			//移到pos前一位，next存放的是pos的地址
		}
		//將prev存放的地址改為pos后一個元素的地址
		prev->next = pos->next;
		//釋放pos
		free(pos);
		pos = NULL;
	}
}

成品展示

SList.h

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode
{
	int data;
	struct SListNode* next;
}SLTNode;

//打印鏈表
void SListPrint(SLTNode* phead);

//創(chuàng)建新鏈表元素（動態(tài)申請一個節(jié)點）
SLTNode* BuySListNode(SLTDataType x);

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//尾刪
void SListPopBack(SLTNode** pphead);

//頭刪
void SListPopFront(SLTNode** pphead);

//查找->可在查找的基礎(chǔ)上進(jìn)行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);

void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);

//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include "SList.h"
 
//打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur!=NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//存放下一個元素的地址
	}
	printf("NULL\n");
}

//創(chuàng)建新鏈表元素
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySListNode(x);//data

	if (*pphead == NULL)
	{
		//防止開始時節(jié)點為空
		*pphead = newnode;
	}
	else
	{
		//找尾節(jié)點
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			//存放新節(jié)點地址
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;//地址傳給pphead  
	//*pphead=&plist
	
	/*
		頭插無需檢查是否為空
	*/
}

//尾刪
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	
	if ((*pphead)->next==NULL)
	{
		//1，只有一個節(jié)點

		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2，有多個節(jié)點

		//將前一個鏈元素中存放的地址換為NULL，防止野指針
		/* 寫法一 */
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tailPrev = tail;//tail的地址
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;

		/* //寫法二
		* //tail尋找的是倒數(shù)第二個元素
		while (tail->next->next!=NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
		*/
	}
}

//頭刪
void SListPopFront(SLTNode** pphead)
{ 
	//防止被刪空
	assert(*pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//查找-給一個節(jié)點的指針
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data==x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
	assert(phead);
	printf("修改成功:\n");
	SLTNode* ret = SListFind(phead, y);
	ret->data = x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	//頭插
	if (pos == *pphead)
		SListPushFront(pphead, x);
	else
	{ 
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
		}
		//找到位置
		SLTNode* newnode = BuySListNode(x);//創(chuàng)建新鏈表元素，并賦值
		prev->next = newnode;//給前一個元素賦上下一元素地址
		newnode->next = pos;//給插入元素存放下一個元素的地址
	}
}

//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
		SListPopFront(pphead);//頭刪
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
			//移到pos前一位，next存放的是pos的地址
		}
		//將prev存放的地址改為pos后一個元素的地址
		prev->next = pos->next;
		//釋放pos
		free(pos);
		pos = NULL;
	}
}

test.c

test.c僅僅是用于測試代碼，本文以弄懂單向鏈表為主，故不進(jìn)行菜單制作
但改測試中也包含了對部分鏈表結(jié)構(gòu)即原理進(jìn)行了講解，請耐心看完

#include "SList.h"
void TestSList1()
{	
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n1);

	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n2);

	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n3);

	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n4);
	
	n1->data=1;
	n2->data=2;
	n3->data=3;
	n4->data=4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	
	SListPrint(n1);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	//傳的是plist指針的地址
	
	//如果直接傳plist，將導(dǎo)致SLTNode* phead中
	//phead為臨時拷貝，不影響實參
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	
	SListPrint(plist);//不改變無需傳二級指針

	SListPushFront(&plist,0);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPrint(plist);
	
	SListPopBack(&plist);
	/*SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);*/
	/*SListPopBack(&plist);
	SListPrint(plist);*/
}
	
void TestSList3()
{
	SLTNode* plist = NULL;
	//傳的是plist指針的地址

	//如果直接傳plist，將導(dǎo)致SLTNode* phead中
	//phead為臨時拷貝，不影響實參
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);

	SListPrint(plist);//不改變無需傳二級指針


	//查找
	SLTNode* ret = SListFind(plist, 3);
	if (ret)
	{
		//返回值不為空則為找到
		printf("找到了\n");
	}
	SListPrint(plist);
	修改
	//SListAlter(plist, 20, 2);
	//SListPrint(plist);

	//插入
	SLTNode* pos = SListFind(plist, 3);//先要找到再進(jìn)行更改
	if (pos)
	{
		SListInsert(&plist, pos, 40);
	}
	SListPrint(plist);

	//刪除
	pos = SListFind(plist, 2);//先要找到再進(jìn)行刪除
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

int main()
{
	TestSList3();
	 
	return 0;
}

單向鏈表講解完畢啦！創(chuàng)作不易，如果喜歡請留下個贊吧，感激不盡?? 數(shù)據(jù)結(jié)構(gòu)：線性表之-單向鏈表(無頭),數(shù)據(jù)結(jié)構(gòu),鏈表,數(shù)據(jù)結(jié)構(gòu) 文章來源地址http://www.zghlxwxcb.cn/news/detail-703402.html