先构建一个结构体,对其链表进行初始化,尾插,尾删,头插,头删,查找,修改,中间插入,删除等相关操作。
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
//创建一个结点
typedef struct SListNode
{
//int data;
LTDataType data;
struct SListNode* next;//创建一个指针存下一个结点的地址
struct SListNode* prev;
}LTNode;
//初始化
LTNode* ListInit();
//void ListInit(LTNode** phead);
LTNode* BuyListNode(LTDataType x);
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);//找到了就返回链表的指针
//在pos前面插入x
void ListInsert(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos);
void ListClear(LTNode* phead);
void ListDestory(LTNode** pphead);
void ListPrint(LTNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
LTNode* ListInit()
{
//带哨兵位的头结点
//不存储有效数字,啥都不存
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
//void ListInit(LTNode** pphead)
//{
// //带哨兵位的头结点
// //不存储有效数字,啥都不存
// *pphead = BuyListNode(0);
// (*pphead)->next = *pphead;
// (*pphead)->prev = *pphead;
//}
LTNode* BuyListNode( LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
//assert(phead);
//LTNode* tail = phead->prev;
//LTNode* newnode = BuyListNode(x);
phead tail newnode
//tail->next = newnode;
//newnode->next = phead;
//phead->prev = newnode;
ListInsert(phead,x );
}
//void ListPopBack(LTNode* phead)
//{
// assert(phead);
// assert(phead->next != phead);
// LTNode* tail = phead->prev;
// LTNode* tailPrev = tail->prev;
// tailPrev->next = phead;
// phead->prev = tailPrev;
// //tailPrev->next = phead; // 将尾节点的前一个节点的next指向头节点
// //phead->prev = tailPrev; // 将头节点的prev指向新的尾节点
// free(tail);
// tail = NULL;
// //为什么不是phead->prev = tailPrev->next; 而是phead->prev = tailPrev,
// // 应该是尾指向头才对啊
// //在双向循环链表中,尾节点的 next 始终指向头节点 phead,而头节点的 prev 始终指向尾节点。
// //因此,在删除尾节点时,关键是要确保头节点的 prev 被正确地更新为新的尾节点(即 tailPrev)。
// //那么我们应该如何理解这两个不同的表达式呢?
// //双向循环链表的结构:
//
// //头节点 phead 的 next 指向第一个元素,prev 指向尾节点。
// //尾节点的 prev 指向倒数第二个元素,next 指向头节点。
// //在这种情况下,尾节点总是指向头节点,而头节点的 prev 始终指向尾节点。
//
// //删除尾节点的操作:
//
// //首先,获得尾节点 tail,并且获得尾节点的前驱节点 tailPrev。
// //然后,我们需要做的是:
// //将尾节点前驱节点 tailPrev 的 next 设置为 phead,
// //即让 tailPrev 的 next 指向头节点,保持链表的循环结构。
// //更新头节点 phead 的 prev 为 tailPrev,让 phead 的 prev 指向新的尾节点。
//
// //为什么不能是 phead->prev = tailPrev->next:
// //tailPrev->next 是 尾节点的 next,它指向头节点 phead。
// //如果你将 phead->prev 设置为 tailPrev->next,
// //这就意味着 phead->prev 会被设置为 phead,从而破坏链表的双向连接关系。
// //你应该将 phead->prev 设置为 tailPrev,让头节点的 prev 指向新的尾节点。
//}
//
void ListPopBack(LTNode* phead)
{
//assert(phead);
//assert(phead->next != phead);
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//tailPrev->next = phead;
//phead->prev = tailPrev;
tailPrev->next = phead; // 将尾节点的前一个节点的next指向头节点
phead->prev = tailPrev; // 将头节点的prev指向新的尾节点
//free(tail);
//tail = NULL;
ListErase(phead->prev);
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListPushFront(LTNode* phead, LTDataType x)
{
/*assert(phead);
LTNode* first = phead->next;
LTNode* newnode = BuyListNode(x);
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;*/
ListInsert(phead->next, x);
}
void ListPopFront(LTNode* phead)
{
/*assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;*/
ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* posPrev = pos->prev;
pos->prev = newnode;
newnode->next = pos;
posPrev->next = newnode;
newnode->prev = posPrev;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
void ListClear(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
}
void ListDestory(LTNode** pphead)
{
assert(*pphead);
//销毁
ListClear(*pphead);
free(*pphead);
*pphead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
TestList()
{
//LTNode* phead = NULL;
//ListInit(&phead);
LTNode* phead = ListInit();
ListPushBack(phead, 1);
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPushBack(phead, 4);
ListPrint(phead);
ListPopBack(phead);
ListPopBack(phead);
ListPopBack(phead);
ListPrint(phead);
ListPushFront(phead, 1);
ListPushFront(phead, 2);
ListPushFront(phead, 3);
ListPushFront(phead, 4);
ListPrint(phead);
ListPopFront(phead);
//ListPopFront(phead);
//ListPopFront(phead);
ListPrint(phead);
LTNode* pos = ListFind(phead, 3);
pos->data = 300;
ListInsert( pos, 30);
ListPrint(phead);
pos = ListFind(phead, 2);
ListErase(pos);
ListPrint(phead);
ListDestory(&phead);
}
int main()
{
TestList();
return 0;
}
先尾插 1 2 3 4,然后尾删三个数,头插 4个数,头删两个数,找到3将其改成300,并在300前面插入30,最后删除2