鏈表

前言

new一個(gè)奶黃包：沒(méi)關(guān)系，這條路我陪你走到底

認(rèn)識(shí)鏈表

單鏈表結(jié)構(gòu)圖

帶頭單循環(huán)鏈表結(jié)構(gòu)圖

雙向循環(huán)鏈表結(jié)構(gòu)圖

帶頭雙向循環(huán)鏈表結(jié)構(gòu)圖

鏈表特點(diǎn)

• 單鏈表在內(nèi)存中，并不是連續(xù)存儲(chǔ)的（邏輯上連續(xù)）。

• 不支持隨機(jī)訪問(wèn)

• 插入時(shí)只需要改變指針指向

• 沒(méi)有容量的概念

• 可以高效的在任意位置插入&&刪除

• 緩存利用率低

鏈表實(shí)現(xiàn)(帶頭雙向循環(huán)鏈表實(shí)現(xiàn))

鏈表結(jié)構(gòu)體

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

(1) 新建頭節(jié)點(diǎn)

LTNode* ListInit()//建立頭節(jié)點(diǎn)
{
	LTNode* phead = buyListNode(-1); //建立一個(gè)帶頭節(jié)點(diǎn)
	phead->next = phead;      
	phead->prev = phead;

	return phead;
}

(2) 建立新節(jié)點(diǎn)

LTNode* buyListNode(LTDataType x)//創(chuàng)建內(nèi)存初始化數(shù)據(jù)  
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	// 初始化：注意所對(duì)的結(jié)構(gòu)來(lái)初始化
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

(3)尾部插入節(jié)點(diǎn)

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x);
	LTNode* tail = phead->prev;
  
	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

(4)刪除節(jié)點(diǎn)

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;  //記錄上一個(gè)節(jié)點(diǎn)
	LTNode* tailmove =tail->prev;  //記錄上一個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
  
	tailmove->next = phead;    
	phead->prev = tailmove;
  
	free(tail);
}

(5)頭部插入節(jié)點(diǎn)

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyListNode(x); 
	LTNode* first = phead->next;

	newnode->next = first;
	first->prev = newnode;

	first->next = phead;
	phead->prev = first;
}

(6) 頭刪節(jié)點(diǎn)

void LTPopFront(LTNode* phead)
{
	assert(phead);  //判斷是否有頭節(jié)點(diǎn)
	assert(phead->next != NULL);  //判斷第一個(gè)節(jié)點(diǎn)是否存在
	LTNode* tail = phead->next;
	LTNode* tailmove = tail->next;

	tailmove->prev = phead;
	phead->next = tailmove;

	tailmove->next = phead;
	phead->prev = tailmove;
	free(tail);
}

(7) 尋找節(jié)點(diǎn)

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			//printf("找到了");
			return cur;//返回指針
		}
      cur=cur->next; //每次都走到下一個(gè)節(jié)點(diǎn)直到phead
	}
	//printf("找不到");
	return NULL;
}

(8) pos位置插入節(jié)點(diǎn)

void LTInsert(LTNode* pos, LTDataType x)//頭插尾插都可以調(diào)用這個(gè)函數(shù) 
{
	assert(pos);
	LTNode* newnode = buyListNode(x); //新建一個(gè)節(jié)點(diǎn)
	LTNode* prev = pos->prev;   //記錄pos位置的前一個(gè)節(jié)點(diǎn)

	newnode->next = pos;   //新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是pos
	pos->prev = newnode;   //pos位置節(jié)點(diǎn)prve就鏈接后面

	newnode->prev = prev;
	prev->next = newnode;
}

(9) 刪除pos位置節(jié)點(diǎn)

void LTErase(LTNode* pos)  //刪除節(jié)點(diǎn)
{
	assert(pos);
	LTNode* prve = pos->prev;
	LTNode* next = pos->next;

	prve->next = next;
	next->prev = prve;

	free(pos);
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-655496.html

(10) 打印鏈表

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
  
	while (cur!= phead)
	{
		printf("-> %d ",cur->data );
		cur = cur->next;
	}
  
}

測(cè)試用例

void test1()
{
	LTNode* ptail = ListInit();
	LTPushBack(ptail, 1);
	LTPushBack(ptail, 3);
	LTPushBack(ptail, 2);
	LTPushBack(ptail, 4);
	LTPushBack(ptail, 5);
	LTPopBack(ptail);
	LTPrint(ptail);
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——鏈表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！