真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

一篇文章帶你學完鏈表基礎（C語言）-創(chuàng)新互聯(lián)

鏈表，也稱線性表的鏈式存儲結構，其元素在內存空間上不是連續(xù)的，通過指針鏈接來決定元素的次序。
鏈表

創(chuàng)新互聯(lián)是一家成都網(wǎng)站制作、成都網(wǎng)站設計，提供網(wǎng)頁設計，網(wǎng)站設計，網(wǎng)站制作，建網(wǎng)站，按需網(wǎng)站開發(fā)，網(wǎng)站開發(fā)公司，從2013年開始是互聯(lián)行業(yè)建設者，服務者。以提升客戶品牌價值為核心業(yè)務，全程參與項目的網(wǎng)站策劃設計制作，前端開發(fā)，后臺程序制作以及后期項目運營并提出專業(yè)建議和思路。目錄
  • 一、鏈表的分類
    • 1.單向或者雙向
    • 2.帶頭或者不帶頭
    • 3.循環(huán)或者非循環(huán)
  • 二、單鏈表的實現(xiàn)
    • 動態(tài)申請一個節(jié)點
    • 單鏈表打印
    • 單鏈表尾插
    • 單鏈表尾刪
    • 單鏈表頭插
    • 單鏈表頭刪
    • 單鏈表查找
    • 單鏈表pos之后插入x
    • 單鏈表pos之前插入x
    • 單鏈表刪除pos之后的節(jié)點
    • 單鏈表刪除pos節(jié)點
    • 單鏈表銷毀
  • 例題——刪除鏈表中等于給定值 val 的所有節(jié)點
    • 方法一：原鏈表修改
    • 方法二：創(chuàng)建新鏈表
    • 方法三：創(chuàng)建帶頭鏈表
  • 例題——反轉鏈表
    • 方法一：迭代法
    • 方法二：遞歸法
  • 三、雙向帶頭循環(huán)鏈表的實現(xiàn)
    • 動態(tài)申請一個節(jié)點
    • 初始化
    • 打印
    • 尾插
    • 尾刪
    • 頭插
    • 頭刪
    • 查找
    • 插入
    • 刪除
    • 判斷鏈表是否為空
    • 返回鏈表長度
    • 銷毀
  • 四、總結

一、鏈表的分類

鏈表的結構多種多樣，以下的情況組合起來就有8種鏈表結構。

1.單向或者雙向

單向
雙向

2.帶頭或者不帶頭

不帶頭
帶頭

3.循環(huán)或者非循環(huán)

非循環(huán)
循環(huán)
雖然有這么多種結構，但是我們最常用的只有兩種：
1.無頭單向非循環(huán)鏈表：結構簡單，一般不會單獨用來存儲數(shù)據(jù)。實際上更多是作為其他數(shù)據(jù)結構的子結構，如哈希桶，圖的鄰接表等。
非循環(huán)
2.帶頭雙向循環(huán)鏈表：結構最復雜，但實現(xiàn)起來比較簡單。
在這里插入圖片描述

二、單鏈表的實現(xiàn)
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;
	struct SListNode* next;
}SLTNode;
//動態(tài)申請一個節(jié)點
SLTNode* BuySListNode(SLTDataType x);
//單鏈表打印
void SLTPrint(SLTNode* phead);
//單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//單鏈表尾刪
void SLTPopBack(SLTNode** pphead);
//單鏈表頭插
void SLTPushFount(SLTNode** pphead, SLTDataType x);
//單鏈表頭刪
void SLTPopFount(SLTNode** pphead);
//單鏈表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//單鏈表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//單鏈表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//單鏈表刪除pos之后的結點
void SLTEraseAfter(SLTNode* pos);
//單鏈表刪除pos結點
void SLTErase(SLTNode** pphead, SLTNode* pos);
//單鏈表銷毀
void SLTDestroy(SLTNode** pphead);
動態(tài)申請一個節(jié)點
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{perror("malloc file:");
		exit(-1);//退出程序
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
單鏈表打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;
	while (cur != NULL)
	{printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
單鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{*pphead = newnode;
	}
	else
	{SLTNode* tail = *pphead;
		while (tail->next)
		{	tail = tail->next;
		}
		tail->next = newnode;
	}
}

這里使用二級指針是因為當鏈表為空時，需要改變一級指針phead為newnode，想要改變一級指針的值要用二級。

單鏈表尾刪
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);
	if ((*pphead)->next == NULL)
	{free(*pphead);
		*pphead = NULL;
	}
	else
	{SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{	prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
單鏈表頭插
void SLTPushFount(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
單鏈表頭刪
void SLTPopFount(SLTNode** pphead)
{assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
單鏈表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;
	while (cur)
	{if (cur->data == x)
		{	return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
單鏈表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
單鏈表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);
	if (*pphead == pos)
	{SLTPushFount(pphead, x);
	}
	else
	{SLTNode* prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

------為什么在pos之后插入x相比在之前插入要簡單呢？
因為想要在pos之前插入，必須要找到pos的前一個節(jié)點，只能通過遍歷鏈表來找到它。后面的刪除指定結點也是相同的道理。

單鏈表刪除pos之后的節(jié)點
void SLTEraseAfter(SLTNode* pos)
{assert(pos);
	if (pos->next == NULL)
	{return;
	}
	else
	{SLTNode* nextNode = pos->next;
		pos->next = pos->next->next;
		free(nextNode);
	}
}
單鏈表刪除pos節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);
	if (*pphead == pos)
	{SLTPopFount(pphead);
	}
	else
	{SLTNode* prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
單鏈表銷毀
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;
	while (cur)
	{SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

通過以上代碼可以看出，相比順序表，鏈表的頭插和頭刪要簡便許多，而尾插和尾刪要繁瑣一些，這是因為鏈表不能隨機存取，想要找到最后一個結點必須從頭開始遍歷。
學會了單鏈表的實現(xiàn)，那么有不少單鏈表的題就可以有思路了，許多題看似復雜，但實際上就是單鏈表的插入、刪除。

例題——刪除鏈表中等于給定值 val 的所有節(jié)點

給你一個鏈表的頭節(jié)點 head 和一個整數(shù) val ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點，并返回 新的頭節(jié)點 。
val = 5：
圖例

方法一：原鏈表修改
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *p = head;
	
    while (cur)
    {if(cur == head) //當cur為頭時
        {if (cur->val == val)
            {cur = cur->next;
                head = cur;
                p = cur;
            }
            else 
            {cur = cur->next;
            }
        }
        else if (cur->next == NULL) //當cur為尾時
        {if (cur->val == val)
            {cur = cur->next;
                p->next = NULL;
            }
            else 
            {cur = cur->next;
            }
        }
        else //當cur在中間
        {if (cur->val == val)
            {cur = cur->next;
                p->next = p->next->next;
            }
            else 
            {p = cur;
                cur = cur->next;
            }
        }
    }
    return head;
}

這是我做這道題時想出的第一個方法，這個方法非常繁瑣，要考慮三種情況，就是當cur在頭、尾、中間。這個方法很容易想到但難以用代碼去實現(xiàn)，在寫代碼的過程中經常容易亂。
其實這個方法可以優(yōu)化一下，把“if (cur->val = val)”這個判斷拿到外層。代碼如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *prev = head;
    while (cur)
    {if (cur->val == val)
        {if (cur == head) //當cur為頭時
            {cur = cur->next;
                free(head);
                head = cur;
                prev = cur;
            }
            else //當cur不為頭
            {prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

這下看起來是不是簡單多了？
回到優(yōu)化前的代碼：在每一個判斷cur位置的條件語句中，都包含了對cur->val的判斷，于是我想到不妨把里面的這個條件語句拿出來，這樣外層就只需要if-else就好了，少了一層判斷。再看內部，我也只分了兩個條件，一個是cur為頭，另一個就是不為頭，當cur在中間和尾時的操作其實時相同的，所以把它們合并在一起。并且加上了free函數(shù)，把要刪除的結點free掉，防止內存泄漏。
其實很多人第一次寫都會寫出像優(yōu)化前那樣的代碼，這很正常，因為初次接觸思路可能沒有那么清晰，多練練就好了。

方法二：創(chuàng)建新鏈表

與其像方法一那樣在原鏈表上進行操作，我們不妨創(chuàng)建一個新的鏈表，然后把符合條件的值尾插到新鏈表中。

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
    struct ListNode* newhead = NULL; //新鏈表的頭
    struct ListNode* tail = NULL; //新鏈表的尾
    while (cur)
    {if (cur->val != val)
        {if (tail == NULL) //判斷新鏈表是否為空
            {newhead = tail = cur;
            }
            else
            {tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if (tail) //把新鏈表的尾結點的next置NULL
    {tail->next = NULL;
    }
    return newhead;
}

這種方法想起來不難，實現(xiàn)起來也不難，寫完之后就會發(fā)現(xiàn)這不就是單鏈表的尾插嗎，只不過就是加了一個篩選條件而已。

方法三：創(chuàng)建帶頭鏈表

第三種方法是創(chuàng)建一個帶頭鏈表。
我們知道，單鏈表的尾插相比頭插要復雜一些，于是我想到采用帶頭鏈表。
采用帶頭鏈表可以省去判斷新鏈表是否為空，因為它一定帶有頭節(jié)點不為空，使代碼更簡潔。
注意：本題要求返回的鏈表不能帶有頭節(jié)點，所以在最后應該返回頭節(jié)點的next。

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
    struct ListNode* guard, *tail;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); //動態(tài)開辟一個頭結點
    guard->next = NULL;

    while (cur)
    {if (cur->val != val)
        {tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        else 
        {struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    tail->next = NULL;
    struct ListNode* newhead = guard->next;
    free(guard); 
    return newhead;
}

這種方法不用考慮多種情況，是我最喜歡的方法。

例題——反轉鏈表

給你單鏈表的頭節(jié)點 head ，請你反轉鏈表，并返回反轉后的鏈表。
圖例

方法一：迭代法

這題其實很容易，我們只需要創(chuàng)建一個新鏈表，然后依次把原鏈表中的元素頭插到新鏈表中即可。代碼如下:

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head; 
    struct ListNode* rhead = NULL;
    while (cur)
    {struct ListNode* next = cur->next;
        cur->next = rhead;
        rhead = cur;
        cur = next;
    }
    return rhead;
}
方法二：遞歸法

這道題也可以采用遞歸的方法，不過有些難以理解。

struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL || head->next == NULL)
    {return head;
    }
    struct ListNode* newhead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
}

圖解

三、雙向帶頭循環(huán)鏈表的實現(xiàn)

雙向帶頭循環(huán)鏈表雖然結構最復雜，但是實現(xiàn)起來可一點也不復雜，相信你通過前面對單鏈表的學習，一定能自己寫出雙向鏈表。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
//動態(tài)申請一個結點
LTNode* BuyListNode(LTDataType x);
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾刪
void LTPopBack(LTNode* phead);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//頭刪
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//插入
void LTInsert(LTNode* phead, LTDataType x);
//刪除
void LTErase(LTNode* phead);
//判斷鏈表是否為空
bool LTEmpty(LTNode* phead);
//返回鏈表長度
size_t LTSize(LTNode* phead);
//銷毀
void LTDestroy(LTNode* phead);
動態(tài)申請一個節(jié)點
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}
初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;
	while (cur != phead)
	{printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\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;
	//LTInsert(phead, x);
}
尾刪
void LTPopBack(LTNode* phead)
{assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	//LTErase(phead->prev);
}
頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);
	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
	//LTInsert(phead->next, x);
}
頭刪
void LTPopFront(LTNode* phead)
{assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
	//LTErase(phead->next);
}
查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{if (cur->data == x)
		{	return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
刪除
void LTErase(LTNode* pos)
{assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

在實現(xiàn)插入、刪除后，我們其實可以將其復用到尾插尾刪頭插頭刪中。

判斷鏈表是否為空
bool LTEmpty(LTNode* phead)
{assert(phead);
	return phead->next == phead;
}
返回鏈表長度
size_t LTSize(LTNode* phead)
{assert(phead);
	LTNode* cur = phead->next;
	size_t size = 0;
	while (cur != phead)
	{++size;
		cur = cur->next;
	}
	return size;
}
銷毀
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;
	while (cur != phead)
	{LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
四、總結

本文主要講述了單鏈表和雙向帶頭循環(huán)鏈表的實現(xiàn)，其中單鏈表尤為重要，在筆試和面試中經常會考到，建議各位讀完本文多去刷一些有關單鏈表的題，它還有許多奧秘等待大家去探索。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧


網(wǎng)站名稱：一篇文章帶你學完鏈表基礎（C語言）-創(chuàng)新互聯(lián)
分享鏈接：http://weahome.cn/article/icgig.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部