鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。而雙向鏈表顧名思義通過指針域向前查找或者向后查找,且頭結(jié)點(diǎn)與尾節(jié)點(diǎn)直接相連構(gòu)成環(huán)。
#ifndef DLIST_H
#define DLIST_H
// 數(shù)據(jù)類型,可根據(jù)需要自行定義
#define Item int
// 鏈表節(jié)點(diǎn)信息
typedef struct DLNode
{Item item;
struct DLNode *prev;
struct DLNode *next;
} DLNode;
typedef struct DList
{int size;
DLNode *head;
} DList;
// Interfaces
void InitDList(DList *dlist);
void InsertDlist(DList *dlist);
DLNode *searchDlist(Dlist *dlist);
void DeleteDlist(DList *dlist, const Item data);
void ShowDlist(const DList *dlist);
void freeDList(DList *dlist);
#endif //DLIST_H
接口源代碼#include#include#include#include
// 初始化雙向鏈表,帶頭結(jié)點(diǎn)
void InitDList(DList *dlist)
{dlist->head = (DLNode *)malloc(sizeof(DLNode));
if (dlist->head == NULL)
return;
dlist->size = 0;
dlist->head->item = -1;
dlist->head->prev = dlist->head;
dlist->head->next = dlist->head;
}
// 鏈表項(xiàng)數(shù)
int DListcounts(DList *dlist)
{assert(dlist);
return dlist->size;
}
// 插入數(shù)據(jù) 1)將數(shù)據(jù)封裝成節(jié)點(diǎn) 2)插入鏈表尾
void InsertDList(DList *dlist, const Item data)
{assert(dlist != NULL);
DLNode *newnode = (DLNode *)malloc(sizeof(DLNode));
if(newnode == NULL)
{printf("out of memory !!\n");
exit(1);
}
newnode->item = data;
newnode->prev = dlist->head->prev;
newnode->next = dlist->head;
dlist->head->prev->next = newnode;
dlist->head->prev = newnode;
dlist->size++;
}
// 在循環(huán)鏈表中查找指定數(shù)據(jù)的節(jié)點(diǎn)
DLNode *searchDList(DList *dlist, const Item data)
{int i;
assert(dlist != NULL);
if(dlist->size == 0)
{printf("the dlist is empty, do not find element:%d\n", data);
return NULL;
}
DLNode *cur = dlist->head->next;
for (i = 0; i< dlist->size; i++)
{if(cur->item == data)
{printf("find it ^_^!!!\n");
return cur;
}
cur = cur->next;
}
if( i == dlist->size)
{printf("unlucky, the element:%d is not exist in dlsit\n");
return NULL;
}
}
// 在雙向循環(huán)鏈表中獲取指定數(shù)據(jù)的節(jié)點(diǎn),并返回
void deleteDList(DList *dlist, const Item data)
{DLNode *node = searchDList(dlist, data);
if(node == NULL)
{printf("the delete element is not exist in dlist!!\n");
return;
}
node->prev->next = node->next;
node->next->prev = node->prev;
dlist->size--;
free(node);
printf("delete it successfully!!\n");
return ;
}
// 釋放構(gòu)建鏈表所申請的堆內(nèi)存
void freeDList(DList *dlist)
{DLNode *cur =NULL, *next = NULL;
for (cur = dlist->head->next; cur != dlist->head; cur = next)
{next = cur->next; // 獲取下一個(gè)節(jié)點(diǎn)
free(cur); // 釋放節(jié)點(diǎn)
}
free(dlist->head);
dlist->head = NULL;
}
測試結(jié)果// 主函數(shù),對上述各接口調(diào)用
int main()
{DList list;
DLNode *node;
InitDList(&list);
InsertDList(&list, 1);
InsertDList(&list, 2);
showDList(&list);
node = searchDList(&list, 3);
int counts1 = DListcounts(&list);
printf("the counts of dlist is %d\n", counts1);
deleteDList(&list, 1);
int counts2 = DListcounts(&list);
printf("the counts of dlist is %d\n", counts2);
showDList(&list);
freeDList(&list);
return 0;
}
[postgres@test dlist_test]$ ./Dlist
1 2
unlucky, the element:3 is not exist in dlsit
the counts of dlist is 2
find it ^_^!!!
delete it successfully!!
the counts of dlist is 1
2
LeetCode 試題class Solution {public:
Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;
Node* cur = head;
// 1. 復(fù)制各節(jié)點(diǎn),并構(gòu)建拼接鏈表
while(cur != nullptr) {Node* tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
// 2. 構(gòu)建各新節(jié)點(diǎn)的 random 指向
cur = head;
while(cur != nullptr) {if(cur->random != nullptr)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
// 3. 拆分兩鏈表
cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next != nullptr) {pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr; // 單獨(dú)處理原鏈表尾節(jié)點(diǎn)
return res; // 返回新鏈表頭節(jié)點(diǎn)
}
};
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧
本文標(biāo)題:雙向循環(huán)鏈表詳解及C語言簡單實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文網(wǎng)址:http://muchs.cn/article24/hecce.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供域名注冊、品牌網(wǎng)站制作、網(wǎng)站營銷、用戶體驗(yàn)、網(wǎng)站制作、外貿(mào)建站
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容