溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“C語言雙向鏈表是什么及怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
1、概念：概念：雙向鏈表是每個結點除后繼指針外還有?個前驅指針。雙向鏈表也有帶頭結點結構和不帶頭結點結構兩種，帶頭結點的雙向鏈表更為常用；另外，雙向鏈表也可以有循環和非循環兩種結構，循環結構的雙向鏈表更為常用。
頭文件List.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDateType;
typedef struct ListNode
{
LTDateType date;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//void ListInit(LTNode** pphead)；
void ListPrint(LTNode* phead);
void ListPopBack(LTNode* phead);
LTNode* ListInit();//初始化
LTNode* BuyLTNode(LTDateType x);
void ListPushBack(LTNode* phead, LTDateType x);
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 ListErease(LTNode* pos);
void ListDestory(LTNode* phead);源文件List.C
#include"List.h"
LTNode* BuyLTNode(LTDateType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->date = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//void ListInit(LTNode** pphead)
//{
// assert(pphead);
// *pphead = BuyLTNode(0);
// (*pphead)->next = *pphead;
// (*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->date);
cur = cur->next;
}
printf("\n");
}
void ListPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
ListInsert(phead->next, x);
}
void ListPopBack(LTNode* phead)//尾刪
{
assert(phead);
assert(phead->next != phead);//說明傳進來的不只有phead,不然phead被free掉了。
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//free(tail);
//tail = NULL;
//tailPrev->next = phead;
//phead->prev = tailPrev;
ListErease(phead->prev);
}
void ListPopFront(LTNode* phead)//頭刪
{
assert(phead);
assert(phead->next != phead);
ListErease(phead->next);
}
LTNode* ListFind(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->date == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//void ListInsert(LTNode* pos, LTDateType x)
//{
// assert(pos);
// LTNode* newnode = BuyLTNode(x);
// pos->prev->next = newnode;
// newnode->prev = pos->prev;
//
// pos->prev = newnode;
// newnode->next = pos;
//
//}
//更好的寫法
void ListInsert(LTNode* pos, LTDateType x)
{
assert(pos);
//無關寫的順序
LTNode* newnode = BuyLTNode(x);
LTNode* posPrev = pos->prev;
newnode->next = pos;
pos->prev = newnode;
posPrev->next = newnode;
newnode->prev = posPrev;
}
// 駝峰法
//函數和類型所以單詞首字母大寫
//變量：第一個單詞小寫后續單詞首字母大寫
void ListErease(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
free(pos);
//此時要把pos置成空，不然pos就是野指針了
pos = NULL;
prev->next = next;//LT的新的prev指向pos->next;
next->prev = prev;//LT的新的next的prev指向prev;
}
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;//從頭結點的下一個位置開始。
while (cur != phead)
{
LTNode* next = cur->next;//先記錄，再free
//ListErease(cur);//副用Erease函數實現destory
free(cur);//
cur = next;
}
free(phead);
//phead = NULL;形參的改變不影響實參
}| 不同點 | 順序表 | 鏈表 |
| 存儲空間上 | 物理上一定連續 | 邏輯上連續，但物理上不一定連 續 |
| 隨機訪問 | 支持O(1) | 不支持：O(N） |
| 任意位置插入或者刪除元 素 | 可能需要搬移元素，效率低O(N) | 只需修改指針指向 |
| 插入 | 動態順序表，空間不夠時需要擴容 | 沒有容量的概念 |
| 應用場景 | 元素高效存儲+頻繁訪問 | 任意位置插入和刪除頻繁 |
| 緩存利用率 | 高 | 低 |
1、鏈表中倒數第k個結點_牛客題霸_牛客網（鏈接）
思路：快慢指針法，fast先走k步， slow和fast同時走， fast走到尾時，slow就是倒數第k個
代碼示例：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* slow, *fast;
slow = fast = pListHead;
while(k --)//走k步
{
//判斷K是否大于鏈表的長度。
if(fast == NULL) return NULL;
fast = fast->next;
}
while(fast)//當fast 指針走到尾時
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
第二種寫法：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
struct ListNode* p1 = NULL, *p2 = NULL;
p1 = pListHead;
p2 = pListHead;
int a = k;
int c = 0;//記錄節點個數
//p1指針先跑，并且記錄節點數，當p1指針跑了k-1個節點后，p2指針開始跑，
//當p1指針跑到最后時，p2所指指針就是倒數第k個節點
while(p1)//當p1 不為空時
{
p1 = p1->next;
c ++;//節點個數增加
if(k < 1) p2 = p2->next;
k --;
}
if(c < a) return NULL;
return p2;
}2、21. 合并兩個有序鏈表（鏈接）
思路：歸并的思想，將小的值尾插到新鏈表。時間復雜度為n^2;如果再定義一個尾指針， 每次記錄尾。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1 == NULL)//list1和list2分別是兩個鏈表的頭指針
return list2;
if(list2 == NULL)
return list1;
struct ListNode* head = NULL, *tail = NULL;//head是新鏈表的頭指針，tail是新鏈表的尾指針
while(list1 && list2)
{
if(list1->val < list2->val)
{
if(tail == NULL)//這一步不太理解
{
head = tail = list1;
}
else
{
tail->next = list1;//先傳指針指向
tail = list1;//再把list 的地址傳給tail，相當于tail往前挪了一步。
}
list1 = list1->next;
}
else
{
if(tail == NULL)
{
head = tail = list2;
}
else
{
tail->next = list2;
tail = list2;//傳地址
}
list2 = list2->next;
}
}
if(list1)
{
tail->next = list1;//如果鏈表1不為空，而此時鏈表二為空，則直接把鏈表二的值連接過去就好了。
}
if(list2)
{
tail->next = list2;
}
return head;
}
//方法二：設置一個哨兵位頭結點
//head存隨機值， head->next存第一個鏈表的值。起到簡化代碼的作用。
//一般的鏈表沒有設置哨兵位頭結點。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* head = NULL, *tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next = NULL;
while(list1 && list2)
{
if(list1->val < list2->val)
{
tail->next = list1;//先傳指針指向
tail = list1;//再把list 的地址傳給tail，相當于tail往前挪了一步。
list1 = list1->next;
}
else
{
tail->next = list2;
tail = list2;//傳地址
list2 = list2->next;
}
}
if(list1)
{
tail->next = list1;//如果鏈表1不為空，而此時鏈表二為空，則直接把鏈表二的值連接過去就好了。
}
if(list2)
{
tail->next = list2;
}
//解決內存泄漏問題；
struct ListNode* list = head->next;
free(head);
return list;
}3、鏈表分割_牛客題霸_牛客網（鏈接）
思路：新設置兩個鏈表，小于x的插到第一個鏈表，大于x的插到第二個鏈表。
定義四個指針：LessHead, LessTail,GreatHead, GreatTail.
原鏈表的值分別尾插到這兩個鏈表， 然后分別更新LessTail,和GreatTail;
最后LessTail的指針再指向GreatHead。完成兩個鏈表的連接。
想極端場景：
1、所有值比x小
2、所有值比x大
3、比x大和小都有，最后一個值是比x小
4、比x大和小都有，最后一個值是比x大
//構成環鏈表，造成死循環。
//設置哨兵位
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lessHead, *lessTail, *greatHead, *greatTail;
lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
greatHead = greatTail = (struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next = greatTail->next = NULL;
struct ListNode* cur = pHead;
while (cur) {
if (cur->val < x) {
lessTail->next = cur;
lessTail = lessTail->next;
} else {
greatTail->next = cur;
greatTail = greatTail->next;
}
cur = cur->next;
}
//完成鏈接工作
lessTail->next = greatHead->next;
greatTail->next = NULL;//切斷greetTail的最后與greetHead的鏈接
struct ListNode* list = lessHead->next;
free(lessHead);
free(greatHead);
return list;
}
};4、鏈表的回文結構_牛客題霸_牛客網（鏈接）
思路：找出鏈表的中間節點， 然后逆置，判斷前后鏈表是否一致，若一致，則說明該鏈表是回文結構。
為什么奇數個時也能過，
例如：1 2 3 2 1
逆置完變為了 1 2 1 2 3 ；
當A走到2的位置時2->next = 3, rHead走到的 2->next = 3， 相等。
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow, * fast;
slow = fast = head;
while(fast && fast->next) //想的是結束的條件，寫的是繼續的條件
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* NewHead = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* next = cur->next;
//頭插
cur->next = NewHead;//更多代表鏈表的指向方向。
NewHead = cur;//接著把地址傳過來(更新)
cur = next;//（更新）
}
return NewHead;
}
bool chkPalindrome(ListNode* A) {
struct ListNode* mid = middleNode(A);
struct ListNode*rHead = reverseList(mid);//應該逆置mid，中間結點。
while(A && rHead)
{
if(A->val == rHead->val)
{
A = A->next;
rHead = rHead->next;
}
else
{
return false;
}
}
return true;
}
};5、力扣相交鏈表（鏈接）
思路1：A鏈表每個節點B跟鏈表依次比較，如果有相等，就是相交，第一個相等就是交點。
時間復雜度：o(N*M);
思路二：如果兩個鏈表相交，則這兩個鏈表的最后一個元素的地址相同。
包含思路二三：
代碼示例：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* tailA, *tailB;//因為之后還要用到headA,和headB,所以要用tail來進行迭代。
tailA = headA, tailB = headB;
int lenA = 1, lenB = 1;
while(tailA)//求出A的尾
{
tailA = tailA->next;
++lenA;//求出A的長度
}
while(tailB)//求出鏈表B的尾
{
tailB = tailB->next;
++lenB;//求出B的長度
}
if(tailA != tailB)//如果兩個鏈表的尾不相等，則返回空
{
return NULL;
}
//相交，求交點，長的先走差距步，再同時找交點。
struct ListNode* shortList = headA, *longList = headB;//默認A短B長
if(lenA > lenB)
{
shortList = headB;
longList = headA;
}
int gap = abs(lenA - lenB);//求出差距
while(gap--)//減gap次，若是--gap,就是減了gap - 1次
{
longList = longList->next;
}
while(shortList && longList)
{
if(shortList == longList)
return shortList;//此時shortList == longList;
longList = longList->next;
shortList = shortList->next;
}
//最最關鍵的一步：就是要在外面返回一個值，因為編譯器不會判斷代碼在哪返回，只會檢查你的代碼的語法問題。
return NULL;
}“C語言雙向鏈表是什么及怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
