資料結構秘籍之鏈表-有解無憂

文章目錄

- 啥是鏈表？
- 單鏈表的實作
- 鏈表的帶環問題
- - 解題思路
  - 解題思路
  - 復制帶隨機指標的鏈表
- 解題思路
- 雙向回圈鏈表的實作

啥是鏈表？

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，
讓我們來一步步了解

在這里插入圖片描述
1.鏈表的大概形式（博主畫得有點丑）
2.鏈表分為資料域和指標域，資料域就是圖中data部分，這個部分是用來存盤資料的，而指標域就是next，next是記錄下一個鏈表的指標，最后一個指標為NULL，代表鏈表結束，
3.鏈表的資料型別，鏈表往往是由整形和xx指標組成的一個結構體，xx=結構體型別,代碼如下：

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

單鏈表的實作

1.動態申請一個節點

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode*));
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}

2.尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* cur = *pplist;
	if (cur == NULL
	{
		cur = BuySListNode(x);
		*pplist = cur;
		return;
	}
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = BuySListNode(x);
}

有的小伙伴可能要不知道這里為什么要傳二級指標，讓我們來康康
在這里插入圖片描述
當cur為NULL，尾插會改變表頭，如果只傳一級指標，只是原指標的拷貝，不會改變原指標pplist的內容（此時pplist指向的內容依然是NULL，而我們用來接收動態開辟的空間的指標會在出函式是銷毀，故動態開辟的記憶體的地址就不得而知了），所以當表頭會變時，需穿二級指標，
下面的一系列可能改變表頭的介面都需要傳二級指標，

3.頭插

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* tmp = *pplist;//拷貝舊的表頭
	*pplist = BuySListNode(x);
	(*pplist)->next = tmp;//將新的表頭鏈在舊表頭前
}

4.尾刪

void SListPopBack(SListNode** pplist)
{
	SListNode* cur = *pplist;
	if (cur == NULL)//此情況為鏈表為空，直接回傳
	{
		return;
	}
	else if (cur->next = NULL)//該情況為鏈表只有一個，當free過后需將頭指標置空
	{
		free(cur);
		*pplist = NULL;
		return;
	}
	while (cur->next != NULL)//找尾
	{
		cur = cur->next;
	}
	free(cur);
	cur = NULL;
}

5.頭刪

void SListPopFront(SListNode** pplist)
{
	SListNode* cur = *pplist;
	if (cur == NULL)
	{
		return;
	}
	SListNode* tmp = cur->next;
	free(cur);
	*pplist = tmp;
}

6.查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("不存在\n");
	return	NULL;
}

7.在pos位置之后插入x

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

8.鏈表的銷毀

void SListDestory(SListNode* plist)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
}

鏈表的帶環問題

在這里插入圖片描述

解題思路

使用快慢指標，快指標每次走2步，慢指標每次走一步，如果鏈表不帶環，快指標先走到NULL結束回圈；
如果鏈表帶環，快指標先進環，當慢指標進環時，它們相差x步（環的大小>x），而快指標比慢指標快一步，所以在x次回圈后會滿足快指標==慢指標，

代碼如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode * fastp=head;
    struct ListNode * slowp=head;
    if(!head)
    {
        return NULL;
    }
    while(fastp && fastp->next)
    {
        fastp=fastp->next->next;
        slowp=slowp->next;
        if(fastp==slowp)
        {
            return true;
        }
    }
    return false;
}

在這里插入圖片描述
這道題是上一道題的進階，需找到成環的第一個點，

解題思路

這道題有個巧妙的解法，我們創建兩個指標，一個指向鏈表表頭，一個指向題目1中的環中相遇點，這兩個指標同時迭代下一個節點，當這兩個指標相遇時，這個節點就是所求的入環的第一個節點，
那么這是為什么呢？我們來看看，

在這里插入圖片描述
1.首先我們假設表頭到入環的第一個節點的距離為m，入環點到相遇點的距離為x，slow入環前fast在環中回圈了n圈，環的大小k
2.fast=m+nk+x
3.slow=m+n
4.fast=2slow

代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fastp=head;
    struct ListNode * slowp=head;
    struct ListNode * meet=NULL;
    if(!head)
    {
        return NULL;
    }
    while(fastp && fastp->next)
    {
        fastp=fastp->next->next;
        slowp=slowp->next;
        if(fastp==slowp)
        {
            meet=fastp;
            break;
        }
    }
    if(meet)
    {
        while(1)
        {
            if(head==meet)
            {
                return meet;
            }
            head=head->next;
            meet=meet->next;
        }
    }
    return NULL;
    
}

復制帶隨機指標的鏈表

在這里插入圖片描述
簡單來說就是這個鏈表多了一個random指標，這個指標指向的內容時隨機的，可能是任意一個鏈表，也可以是NULL，
這道題的難度就是如何拷貝random

解題思路

在這里插入圖片描述
1.首先，我們將原鏈表的每一個節點拷貝并鏈接在其后（只拷貝資料和next，不拷貝random）
2.以第一個節點為例（下面通常cur），我們將通過cur->next找到cur的備份（下面通常bcp）,bcp的random就是cur的random所指的節點的下一個，依次把整個鏈表遍歷一遍
3.將原鏈表和備份鏈表分別指向自己的next
4.回傳備份鏈表的頭節點

代碼

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    struct Node* next=NULL;
    if(!head)
    {
        return NULL;
    }
    while(cur)//拷貝子鏈表并插入在每個子鏈表之后
    {
        next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        copy->next=next;
        cur->next=copy;
        cur=next;
    }
     struct Node* copy=head->next;
     cur=head;
     while(copy)//原子鏈表的random->next就是新子鏈表的random
     {
         if(cur->random==NULL)
         {
             copy->random=NULL;
         }
        else
        {
            copy->random=cur->random->next;
        }
         if(copy->next==NULL)
         {
             break;
         }
         copy=copy->next->next;
         cur=cur->next->next;
     }
     copy=head->next;
     struct Node* newhead=copy;
     cur=head;
	 while(copy->next)//將新舊鏈表分開
     {
         cur->next=copy->next;
         cur=cur->next;
         copy->next=cur->next;
         copy=copy->next;
     }
     return newhead;
}

雙向回圈鏈表的實作

結構體型別

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

與單鏈表相比，多了一個prev指標，

1.創建節點

ListNode* ListBuy(int x)
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	tmp->_prev = tmp->_next = NULL;
	tmp->_data = x;
	return tmp;
}

2.創建鏈表的頭節點（該節點的資料無效）

ListNode* ListCreate()
{
	ListNode* tmp = ListBuy(0);
	tmp->_prev = tmp->_next = tmp;
	return tmp;
}

3.銷毀

void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
}

4.尾插

void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
}

5.尾刪

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next!=pHead);
	ListNode* tail = pHead->_prev;
	tail->_prev->_next = tail->_next;
	tail->_next->_prev = tail->_prev;
    free(tail);
}

6.頭插

void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* head = pHead->_next;
	ListNode* tmp = ListBuy(x);
	tmp->_prev = pHead;
	pHead->_next = tmp;
	tmp->_next = head;
	head->_prev = tmp;
}

7.頭刪

void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	ListNode* head = pHead->_next;
	pHead->_next = head->_next;
	head->_prev = pHead;
	if (head != pHead)
	{
		free(head);
	}
}

8.查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

9.在pos前插入

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* tmp = ListBuy(x);
	ListNode* prev = pos->_prev;
	tmp->_prev = prev;
	tmp->_next = pos;
	pos->_prev = tmp;
	prev->_next = tmp;

}

10.洗掉pos處的節點

void ListErase(ListNode* pos)
{
	assert(pos);
	assert(pos->_next != pos);
	pos->_prev->_next = pos->_next;
	pos->_next->_prev = pos->_prev;
	free(pos);
}

此型別的鏈表相對與單鏈表，不用找尾，不會移動頭節點，進行修改資料的效率高，

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

標籤：其他

上一篇：【零基礎搞定C語言——7】

下一篇：多項式加法運算（鏈表實作）