- 首页 > it技术 > >
数据结构之双向链表(带环,带头节点)
#pragma once
#include
#include
typedef char LinkType;
typedef struct LinkNode{
LinkType data;
struct LinkNode*next;
}LinkNode;
void LinkListInit(LinkNode** head);
void LinkListPushBack(LinkNode**head, LinkType value);
void LinkListPopBack(LinkNode**head);
void LinkListPushFront(LinkNode**head, LinkType value);
void LinkListPopFront(LinkNode**head);
LinkNode* LinkListFind(LinkNode*head,LinkType to_find);
void LinkListInsert(LinkNode**head,LinkType value,LinkNode* pos );
void LinkListErase(LinkNode**head, LinkNode*pos);
void LinkListRemove(LinkNode**head, LinkType value);
void LinkListRemoveAll(LinkNode**head, LinkType value);
void LinkListEmpty(LinkNode**head);
int LinkListSize(LinkNode*head);
LinkNode*LinklistGreateNode(LinkType*value);
/**
* @brief 逆序打印单链表.
*
* @param head
*/
LinkNode* LinkListReversePrint(LinkNode* head);
/**
* @brief 不允许遍历链表, 在 pos之前插入
*
* @param head
* @param pos
* @param value
*/
void LinkListInsertBefore(LinkNode** head, LinkNode* pos, LinkType value);
LinkNode* JosephCycle(LinkNode* head, size_t food);
/**
* @brief 单链表逆置
*
* @param head
*/
void LinkListReverse(LinkNode** head);
void LinkListReverse2(LinkNode** head);
/**
* @brief 单链表的冒泡排序
*
* @param head
*/
void LinkListBubbleSort(LinkNode* head);
/**
* @brief 将两个有序链表, 合并成一个有序链表
*
* @param head1
* @param head2
*
* @return
*/
LinkNode* LinkListMerge(LinkNode* head1, LinkNode* head2);
LinkNode* FindMidNode(LinkNode* head);
/**
* @brief 找到倒数第 K 个节点.
*
* @param head
*
* @return
*/
LinkNode* FindLastKNode(LinkNode* head, size_t K);
/**
* @brief 删除倒数第K个节点
*
* @param head
* @param K
*/
void EraseLastKNode(LinkNode** head, size_t K);
/**
* @brief 判定单链表是否带环. 如果带环返回1
*
* @param head
*
* @return
*/
LinkNode* HasCycle(LinkNode* head);
/**
* @brief 如果链表带环, 求出环的长度
*
* @param head
*
* @return
*/
size_t GetCycleLen(LinkNode* head);
/**
* @brief 如果链表带环, 求出环的入口
*
* @param head
*
* @return
*/
LinkNode* GetCycleEntry(LinkNode* head);
/**
* @brief 判定两个链表是否相交, 并求出交点
*
* @param head1
* @param head2
*
* @return
*/
LinkNode* HasCross(LinkNode* head1, LinkNode* head2);
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include"linklist.h"
void LinkListInit(LinkNode**head)
{
if (head == NULL)
{
return;
}
*head = NULL;
}
LinkNode*LinkListGreateNode(LinkType value)
{
LinkNode* ptr = (LinkNode*)malloc(sizeof(LinkNode));
ptr->data = https://www.it610.com/article/value;
ptr->next = NULL;
return ptr;
}
void LinkListPushBack(LinkNode** head, LinkType value)//需要修改头指针时使用**head，不修改则用*head。
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
*head = LinkListGreateNode(value);
return;
}
LinkNode*cur = *head;
while (cur->next != NULL)
{
cur = cur->next;
} LinkNode* new_node = LinkListGreateNode(value);
cur->next = new_node;
}
void LinkListDestoryNode(LinkNode* cur)
{
free(cur);
}
void LinkListPopBack(LinkNode**head)
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
return;
}
LinkNode*cur = *head;
while (cur->next == NULL)
{
LinkListDestoryNode(cur);
*head = NULL;
return;
}
while (cur->next != NULL)
{
if (cur->next->next == NULL)
{
LinkNode* to_delete = cur->next;
cur->next = NULL;
LinkListDestoryNode(to_delete);
}
else
cur = cur->next;
}
}
void LinkListPushFront(LinkNode**head, LinkType value)
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
*head = LinkListGreateNode(value);
return;
}
LinkNode* new_node=LinkListGreateNode(value);
new_node->next = *head;
*head = new_node;
}
void LinkListPopFront(LinkNode**head)
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
return;
}
LinkNode*cur = *head;
while (cur->next == NULL)
{
LinkListDestoryNode(cur);
*head = NULL;
return;
}
*head = (*head)->next;
LinkListDestoryNode(cur);
}
LinkNode* LinkListFind(LinkNode*head,LinkType to_find)
{
if (head == NULL)
{
return NULL;
}//参数非法
LinkNode*cur = head;
while (cur){
if (cur->data=https://www.it610.com/article/= to_find)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LinkListInsert(LinkNode** head,LinkType value,LinkNode*pos)//在任意位置插入数据
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
*head = LinkListGreateNode(value);
return;
}
if (pos == NULL)
{
LinkListPushBack(head, value);
}
LinkNode*cur = *head;
while (cur->next != NULL)
{
if (cur->next == pos)
{
LinkNode*new_node = LinkListGreateNode(value);
new_node->next = pos;
cur->next = new_node;
return;
}
else
cur = cur->next;
} return;
}
void LinkListErase(LinkNode**head, LinkNode*pos)
{
if (head == NULL||pos==NULL)
{
return;
}//参数非法
if (*head == NULL)
{
return;
}
if (*head == pos)
{
LinkNode*to_delete = pos;
*head = (*head)->next;
LinkListDestoryNode(to_delete);
return;
}
LinkNode*cur = *head;
LinkNode*to_delete = pos;
while (cur->next != NULL)
{
if (cur->next == pos)
{
cur->next = pos->next;
LinkListDestoryNode(to_delete);
return;
}
else
cur = cur->next;
}
return;
}
void LinkListRemove(LinkNode**head, LinkType value)
{
if (head == NULL)
{
return;
}//参数非法
LinkNode*pos = LinkListFind((*head), value);
LinkListErase(head, pos);
return;
}
void LinkListRemoveAll(LinkNode**head, LinkType value)
{
if (head == NULL)
{
return;
}//参数非法
while (1)
{
LinkNode*pos = LinkListFind((*head), value);
if (pos == NULL)
{
break;
}
LinkListErase(head, pos);
}
return;
}
void LinkListEmpty(LinkNode**head)
{ if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
return;
}
LinkNode*cur = *head;
while (cur != NULL)
{
LinkNode*to_delete = cur;
cur = cur->next;
LinkListDestoryNode(to_delete);
}
(*head) = NULL;
}
int LinkListSize(LinkNode*head)
{
int count = 1;
if (head == NULL)
{
return -1;
}//参数非法
LinkNode*cur = head;
if (cur->next == NULL)
{
return count;
}
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}/
void LinkListPrintChar(LinkNode*head, const char* msg)
{
printf("*****++++++++++*****++++++++++*****++++++++++*****++++++++++*****\n");
printf("[%s]:",msg);
LinkNode*cur = head;
for (;
cur != NULL;
cur = cur->next)
{
printf("[%c:%p]->", cur->data, cur);
}
printf("[NULL]");
printf("\n");
}
/**
* @brief 逆序打印单链表.
*
* @param head
*/LinkNode* LinkListReversePrint(LinkNode* head)
{
if (head == NULL||head->next==NULL)
{
return NULL;
}//参数非法
LinkNode*rev = NULL;
//定义一个逆向指针
LinkNode*cur = head;
while (cur != NULL)
{
LinkNode*temp = cur;
//保存第n个节点
cur = cur->next;
//指向n+1个节点
temp->next = rev;
//销毁n指向下一个的指针
rev = temp;
//反指向第n个节点
}
return rev;
}/**
* @brief 不允许遍历链表, 在 pos之前插入
*
* @param head
* @param pos
* @param value
*/
void LinkListInsertBefore(LinkNode**head,LinkNode* pos, LinkType value)
{
if (head == NULL||pos==NULL)
{
return;
}//参数非法
if (*head == NULL)
{
*head = LinkListGreateNode(value);
return;
}
LinkNode*new_node = LinkListGreateNode(pos->data);
pos->data = https://www.it610.com/article/value;
new_node->next = pos->next;
pos->next = new_node;
}待修改LinkNode* JosephCycle(LinkNode* head, size_t food)//约瑟夫环
{
if (head == NULL)
{
return NULL;
}
if (food == 0)
{
return NULL;
}
LinkNode*cur = head;
while (cur != cur->next)
{
size_t i= 0;
for (;
i < food;
++i)
{
cur = cur->next;
}
LinkNode*to_delete = cur->next;
//
cur->next = to_delete->next;
LinkListDestoryNode(to_delete);
}
return cur;
}/**
* @brief 单链表逆置
*
* @param head
*/
void LinkListReverse(LinkNode** head)
{
if (head == NULL )
{
return ;
}//参数非法
if (*head == NULL || (*head)->next == NULL)
{
return;
}
LinkNode*cur = *head;
while (cur->next != NULL)
{
LinkNode*to_delete = cur->next;
cur->next = to_delete->next;
to_delete->next = *head;
*head = to_delete;
}
}
void LinkListReverse2(LinkNode** head)
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL || (*head)->next == NULL)
{
return;
}
LinkNode*prev = *head;
LinkNode*cur = (*head)->next;
prev->next = NULL;
while (cur != NULL)
{
LinkNode*next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head = prev;
}
void swap(LinkType *x, LinkType *y)
{
LinkType temp = 0;
temp = *x;
*x = *y;
*y = temp;
}
/**
* @brief 单链表的冒泡排序
*
* @param head
*/
void LinkListBubbleSort(LinkNode* head)
{
if (head == NULL)
{
return;
}//参数非法
LinkNode*cur = head;
LinkNode*tail = NULL;
for (;
cur != NULL;
cur=cur->next)
{
LinkNode*pos = head;
for (;
pos->next != tail;
pos=pos->next)
{
if (pos->data > pos->next->data)
{
swap(&pos->data, &pos->next->data);
/*LinkType tmp = 0;
tmp = pos->data;
pos->data = https://www.it610.com/article/pos->next->data;
pos->next->data = https://www.it610.com/article/tmp;
*/
}
}
tail = pos;
}
}/**
* @brief 将两个有序链表, 合并成一个有序链表
*
* @param head1
* @param head2
*
* @return
*/
LinkNode* LinkListMerge(LinkNode* head1, LinkNode* head2)
{
LinkNode*cur1 = head1;
LinkNode*cur2 = head2;
LinkNode*new_head = NULL;
LinkNode*new_tail = NULL;
while (cur1 != NULL&&cur2 != NULL)
{
if (cur1->data <= cur2->data)
{
if (new_head == NULL)
{
new_head = new_tail = cur1;
}
else
{
new_tail->next = cur1;
new_tail = new_tail->next;
}
cur1 = cur1->next;
}
else if (cur1->data>cur2->data)
{
if (new_head == NULL)
{
new_tail = new_tail = cur2;
}
else
{
new_tail->next = cur2;
new_tail = new_tail->next;
}
cur2 = cur2->next;
}
}
if (cur1 != NULL)
{
new_tail->next = cur1;
}
else
{
new_tail->next = cur2;
}
return new_head;
}LinkNode* FindMidNode(LinkNode* head)
{
if (head == NULL)
{
return NULL;
}//参数非法
LinkNode*slow = head;
LinkNode*fast = head;
while (fast->next != NULL && fast != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}/**
* @brief 找到倒数第 K 个节点.
*
* @param head
*
* @return
*/
LinkNode* FindLastKNode(LinkNode* head, size_t k)
{
if (head == NULL)
{
return NULL;
}//参数非法
LinkNode*slow = head;
LinkNode*fast = head;
while (k--)
{
fast = fast->next;
}
while ( fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}/**
* @brief 删除倒数第K个节点
*
* @param head
* @param K
*/
void EraseLastKNode(LinkNode** head, size_t K)
{
if (head == NULL)
{
return;
}//参数非法
if (*head == NULL)
{
return;
}
LinkNode*p = NULL;
p = FindLastKNode(*head, K);
LinkListErase(head, p);
}/**
* @brief 判定单链表是否带环. 如果带环返回1
*
* @param head
*
* @return
*/
LinkNode* HasCycle(LinkNode* head)
{
if (head == NULL)
{
return NULL;
}//参数非法
LinkNode*slow = head;
LinkNode*fast = head;
while (fast != NULL&&fast->next != NULL)
{
if (fast == slow)
{
return slow;
}
else
{
fast = fast->next->next;
slow = slow->next;
}
}
return NULL;
}/**
* @brief 如果链表带环, 求出环的长度
*
* @param head
*
* @return
*/
size_t GetCycleLen(LinkNode* head)
{
if (head == NULL)
{
return 0;
}//参数非法
LinkNode*slow = head;
LinkNode*fast = head;
size_t sz = 1;
while (fast != NULL&&fast->next != NULL)
{
if (fast == slow)
{
LinkNode*get = slow;
slow = slow->next;
for (;
slow != get;
slow = slow->next)
{
sz ++;
}
return sz;
}
else
{
fast = fast->next->next;
slow = slow->next;
}
}
return 0;
}/**
* @brief 如果链表带环, 求出环的入口
*
* @param head
*
* @return
*/
LinkNode* GetCycleEntry(LinkNode* head)
{
LinkNode*meet = HasCycle(head);
if (meet == NULL)
{
return NULL;
}
LinkNode*cur1 = head;
LinkNode*cur2 = meet;
while (cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}/**
* @brief 判定两个链表是否相交, 并求出交点
*
* @param head1
* @param head2
*
* @return
*/
LinkNode* HasCross(LinkNode* head1, LinkNode* head2)
{
if (head1 == NULL || head2 == NULL)
{
return NULL;
}
size_t size1 = Linklistsize(head1);
size_t size2 = Linklistsize(head2);
LinkNode*cur1 = head1;
LinkNode*cur2 = head2;
if (size1 < size2)
{
size_t i = 0;
for (;
i < size2 - size1;
++i)
{
cur2 = cur2->next;
}
}
else
{
size_t i = 0;
for (;
i < size1 - size2;
++i)
{
cur1 = cur1->next;
}
}
while (cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
void test()
{
LinkNode* head=NULL;
LinkNode* p = NULL;
LinkNode* p1 = NULL;
size_t size = 0;
LinkListInit(&head);
LinkListInit(&p1);
LinkListPushBack(&head,'1');
LinkListPushBack(&head, '2');
LinkListPushBack(&head, '3');
LinkListPushBack(&head, '4');
LinkListPushBack(&head, '5');
LinkListPushBack(&head, '6');
LinkListPushBack(&head, '7');
LinkListPushBack(&head, '8');
LinkListPushBack(&head, '9');
p=head->next = LinkListGreateNode(2);
p->next = LinkListGreateNode(3);
p->next->next = head;
size = GetCycleLen(head);
printf("有环:%d\n",size);
p1 = GetCycleEntry(head);
printf("有环:%c\n", p1->data);
p1=HasCycle(head);
if (p1 != NULL){
printf("有环\n");
}
else
printf("无环！");
LinkListPrintChar(p, "");
EraseLastKNode(&head, 4);
LinkListPrintChar(head, "");
p=FindMidNode( head);
LinkListPrintChar(p, "");
LinkListPushBack(&p1, '1');
LinkListPushBack(&p1, '2');
LinkListPushBack(&p1, '3');
LinkListPushBack(&p1, '4');
LinkListPushBack(&p1, '5');
p=LinkListMerge(head, p1);
LinkListPrintChar(p, "合并");
LinkListReverse(&head);
LinkListPrintChar(head, "edcba");
LinkListBubbleSort(head);
LinkListPrintChar(head, "排序abcde");
size = LinkListSize(head);
printf("元素个数【%d】\n", size);
LinkListReverse2(&head);
LinkListPrintChar(head, "abcde");
LinkListBubbleSort(head);
LinkListPrintChar(head, "abcde");
p = LinkListFind(head, 'e');
p->next = head;
JosephCycle(head, 2);
LinkListPrintChar(head, "abcde");
p1=LinkListReversePrint(head);
LinkListPrintChar(p1, "abcde");
LinkListPopBack(&head);
size=LinkListSize(head);
printf("元素个数【%d】\n", size);
LinkListPrintChar(head, "abcd");
LinkListPopFront(&head);
LinkListPrintChar(head, "bcd");
LinkListPushFront(&head, 'a');
LinkListPrintChar(head, "abcd");
p = LinkListFind(head, 'f');
if (p != NULL){
printf("[%c:%p]\n", p->data, p);
}
else
printf("查无此值！");
p = LinkListFind(head, 'c');
if (p != NULL){
printf("[%c:%p]\n", p->data, p);
}
else
printf("查无此值！");
LinkListInsert(&head, '0', p);
LinkListPrintChar(head, "ab0cd");
LinkListInsertBefore(&head, p, 'f');
LinkListPrintChar(head, " 不遍历前插");
LinkListErase(&head, p);
LinkListPrintChar(head, "ab0d");
LinkListRemove(&head, '0');
LinkListPrintChar(head, "abd");
LinkListEmpty(&head);
LinkListPrintChar(head, "abd");
LinkListEmpty(&head);
LinkListPrintChar(head, "");
}
int main()
{
test();
system("pause");
return 0;
}
推荐阅读
