双向循环链表详解及C语言简单实现-创新互联
概念
名称栏目：双向循环链表详解及C语言简单实现-创新互联
转载注明：http://scyanting.com/article/hecce.html
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。而双向链表顾名思义通过指针域向前查找或者向后查找，且头结点与尾节点直接相连构成环。
#ifndef DLIST_H
#define DLIST_H
// 数据类型，可根据需要自行定义
#define Item int
// 链表节点信息
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
// 初始化双向链表，带头结点
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;
}
// 链表项数
int DListcounts(DList *dlist)
{assert(dlist);
return dlist->size;
}
// 插入数据 1）将数据封装成节点 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++;
}
// 在循环链表中查找指定数据的节点
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;
}
}
// 在双向循环链表中获取指定数据的节点，并返回
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 ;
}
// 释放构建链表所申请的堆内存
void freeDList(DList *dlist)
{DLNode *cur =NULL, *next = NULL;
for (cur = dlist->head->next; cur != dlist->head; cur = next)
{next = cur->next; // 获取下一个节点
free(cur); // 释放节点
}
free(dlist->head);
dlist->head = NULL;
}
// 主函数，对上述各接口调用
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
class Solution {public:
Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;
Node* cur = head;
// 1. 复制各节点，并构建拼接链表
while(cur != nullptr) {Node* tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
// 2. 构建各新节点的 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; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
};
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
名称栏目：双向循环链表详解及C语言简单实现-创新互联
转载注明：http://scyanting.com/article/hecce.html
