鏈表的概念及結構

概念

鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，

結構

代碼

struct Slist
{
	int* a;
	struct Slist* next;
};

邏輯結構:
物理結構：
注意:

從上圖可以看出，鏈式結構在邏輯上是連續的，但是在物理上是不一定是連續的，
這些結點一般是從堆上申請出來的，
從堆上申請的空間，是按照一定的策劃來分配的，兩次申請的空間可能連續，大概率是不連續的，

鏈表的分類

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1. 單向或者雙向
①單向

②雙向
2.帶頭或者不帶頭
①帶頭

②不帶頭
3.回圈或者非回圈
①回圈
②非回圈
雖然有這么多種結構的鏈表，但是我們實際中最常用的只有兩種結構:
1. 無頭單向非回圈鏈表2.帶頭雙向回圈鏈表

1. 無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，

2. 帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而簡單了，后面我們代碼實作了就知道了，

單鏈表的實作（無頭）

單鏈表結構

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

單鏈表需要的功能

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表列印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表洗掉pos位置之后的值
// 分析思考為什么不洗掉pos位置？
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestory(SListNode** pplist);

功能實作


SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->data = x;
	return newnode;
}

void SListPrint(SListNode* plist)
{
	if (plist == NULL)
	{
		printf("NULL\n");
		return;
	}
	else
	{
		while (plist)
		{
			printf("%d->", plist->data);
			plist = plist->next;
		}
		printf("NULL\n");
	}
}

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* tail = *pplist;
	SListNode* newnode = BuySListNode(x);
	newnode->next = NULL;
	if (tail == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	SListNode* tail = *pplist;
	SListNode* Pretail = NULL;
	if (tail->next == NULL)
	{
		*pplist = NULL;
		return;
	}
	else
	{
		while (tail->next)
		{
			Pretail = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		Pretail->next = NULL;
	}
}

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* front = *pplist;
	*pplist = front->next;
	free(front);
	front = NULL;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* pos = plist;
	while (pos && pos->data != x)
	{
		pos = pos->next;
	}
	return pos;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* node = pos->next;
	pos->next = node->next;
	free(node);
}

void SListDestory(SListNode** pplist)
{
	SListNode* node = *pplist;
	SListNode* PreNode = NULL;
	while (node)
	{
		PreNode = node->next;
		free(node);
		node = PreNode;
	}
}

雙向鏈表的實作

雙向鏈表的結構

typedef int LTDateType;

typedef struct ListNode
{
	LTDateType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

雙向鏈表的功能

//創建鏈表回傳頭結點
LTNode* ListInit();
// 雙向鏈表銷毀
void ListDestory(LTNode* phead);
// 雙向鏈表列印
void ListPrint(LTNode* phead);

// 雙向鏈表尾插
void ListPushBack(LTNode* phead, LTDateType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* phead);
// 雙向鏈表頭插
void ListPushFront(LTNode* phead, LTDateType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* phead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* phead, LTDateType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(LTNode* pos, LTDateType x);
// 雙向鏈表洗掉pos位置的節點
void ListErase(LTNode* pos);

功能實作

LTNode* ListInit()
{
	//哨兵位頭結點
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		printf("開辟空間失敗!!!\n");
		exit(-1);
	}
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	LTNode* p = NULL;
	LTNode* tail = phead->prev;
	while (cur != tail)
	{
		p = cur;
		cur = cur->next;
		free(p);
	}
	free(tail);
}

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* front = phead->next;
	while (front != phead)
	{
		printf("%d ", front->data);
		front = front->next;
	}
	printf("\n");
}

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	LTNode* tail = phead->prev;
	LTNode* TailFront = tail->prev;
	TailFront->next = phead;
	phead->prev = TailFront;
	free(tail);
}

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* next = phead->next;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	LTNode* head = phead->next;//頭結點
	phead->next = head->next;
	head->next->prev = phead;
	free(head);
}

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

總結:鏈表和順序表的區別

不同點	順序表	鏈表
存盤空間上	物理上一定連續	邏輯上連續，物理上不一定連續
隨機訪問	支持	不支持
任意位置上插入或者洗掉元素	可能需要移動元素，效率低下	只需修改指標指向
插入	動態順序表，空間不夠時需要擴容	沒有容量的概念
應用場景	元素高效存盤+頻繁訪問	任意位置插入和洗掉頻繁

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352214.html

標籤：其他

上一篇：【資料結構】堆的實作

下一篇：《手撕資料結構經典題系列》有效括號問題