新手也很好上手的数据结构——循环双向链表(C语言)
带头双向循环链表
这应该是title最多的链表了吧!和无头单向非循环链表是一个鲜明对比,但是后者是OJ最长出的题目类型(90%以上),前者则是最复杂的,所以两个都讲完之后所有的链表基本都掌握了。
list.h 头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}ListNode;
//初始化链表
ListNode* ListInit();
//销毁链表
void ListDestroy(ListNode* plist);
//打印链表
void ListPrint(ListNode* phead);
//尾插
void ListPushBack(ListNode* phead, LTDataType x);
//头插
void ListPushFront(ListNode* phead, LTDataType x);
//尾删
void ListPopBack(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, LTDataType x);
//在和x相同的pos的位置前插入y,没有和x相同就不插
void ListInsert(ListNode* phead, LTDataType x, LTDataType y);
//清除节点
void ListErase(ListNode* phead, LTDataType x);
list.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//第1种初始化,需要传二级指针。
//
//
//void ListInit(ListNode** pphead)
//{
// if (pphead == NULL)
// {
// BuyListNode;
// pphead->next = pphead;
// pphead->prev = pphead;
// }
// else
// {
// }
//}
//第二种初始化,不需要传二级指针。
ListNode* ListInit()
{
ListNode* phead = BuyListNode(1);
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListDestroy(ListNode* plist);
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d—>", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* first = phead->next;
ListNode* newnode = BuyListNode(x);
newnode->next = phead->next;
newnode->prev = phead->next->prev;
phead->next->prev = newnode;
phead->next = newnode;
}
void ListPopFront(ListNode* phead)
{
assert(phead);
ListNode* first = phead->next;
phead->next = phead->next->next;
phead->next->next->prev = phead;
free(first);
first = NULL;
}
void ListPopBack(ListNode* phead)
{
assert(phead->next != phead);
ListNode* tail = phead->prev;//做标记这种方法很方便观看,会让你少动脑子。
ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{
ListNode* cur = phead;
ListNode* roll = phead->prev;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
if (cur == roll)
{
break;
}
}
cur = NULL;
return NULL;
}
void ListInsert(ListNode* phead, LTDataType x, LTDataType y)
{
ListNode* pos = ListFind(phead,x);
ListNode* newadd = (ListNode*)malloc(sizeof(ListNode));
newadd->data = y;
if (pos)
{
ListNode* prev = pos->prev;
newadd->prev = prev;
newadd->next = pos;
pos->prev = newadd;
prev->next = newadd;
}
else
{
printf("没有找到要插入的位置\n");
return;
}
}
main.c文件
void menu()
{
printf("********************************************\n");
printf("**********1.尾增信息 2.头增信息***********\n");
printf("**********3.尾删信息 4.头删信息***********\n");
printf("**********5.中间插入 6.清除信息***********\n");
printf("**********7.打印链表 0.退出链表***********\n");
printf("********************************************\n");
}
//使用枚举
enum ENUM_A
{
EXIT,
PushBack,
PushFront,
PopBack,
PopFront,
Insert,
ERASE,
PRINT,
};
int main()
{
testList1();
int input = 0;
ListNode* plist1 = ListInit();
int x=0, y=0;
scanf("%d", &input);
do
{
menu();
printf("请输入你的选择:");
scanf("%d", &input);
switch (input)
{
case PushBack:
printf("输入你要增加的数值:");
scanf("%d", &x);
ListPushBack(plist1, x);
break;
case PushFront:
printf("输入你要增加的数值:");
scanf("%d", &x);
ListPushFront(plist1, x);
break;
case PopBack:
ListPopBack(plist1);
break;
case PopFront:
ListPopFront(plist1);
break;
case Insert:
printf("输入你要插入的位置和数值:");
scanf("%d %d", &x, &y);
ListInsert(plist1, x, y);
break;
case ERASE:
printf("输入你要清除的数值:");
scanf("%d", &x);
ListErase(plist1,x);
break;
case PRINT:
ListPrint(plist1);
break;
case EXIT:
ListDestroy(plist1);
break;
default:
break;
}
} while (input);// do...while循环是需要加;的.
return 0;
}