数据结构4—双向链表（附源码）

1.概念与结构

在整个链表中存在一个“哨兵位”，这个哨兵位不存储任何有效元素，置是站在这里放哨，空站一个位置。

2.源码

2.1 List.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//打印
void Print(LTNode* phead);//初始化
void LTInit(LTNode** pphead);//尾插
void LTPushBack(LTNode** pphead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找结点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入结点
void LTInsert(LTNode* pos, LTDataType x);

2.2 List.c

#include "List.h"void Print(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d", pcur->data);pcur = pcur->next;}
}LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->prev = newnode->next = newnode;return newnode;
}//初始化
void LTInit(LTNode** pphead)
{//创建一个头结点（哨兵位）*pphead = LTBuyNode(-1);
}void LTPushBack(LTNode* phead,LTDataType x)
{LTNode* NewNode = LTBuyNode(x);NewNode->next = phead;NewNode->prev = phead->prev;phead->prev->next = NewNode;phead->prev = NewNode;}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* NewNode = LTBuyNode(x);phead->next->prev = NewNode;NewNode->next = phead->next;phead->next = NewNode;NewNode->prev = phead;
}//判断是否是空链表
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//如果为空，返回true。返回false，不为空
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//保证不是空链表LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//保证不是空链表LTNode* del = phead->next;LTNode* prev = del->next;phead->next = prev;prev->prev = phead;free(del);del = NULL;}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

2.3 test.c

#include "List.h"void ListTest01()
{//创建双向链表LTNode* pList = NULL;LTInit(&pList);//LTPushBack(pList, 1);//LTPushBack(pList, 2);//LTPushBack(pList, 3);LTPushFront(pList,3);LTPushFront(pList,2);LTPushFront(pList,1);//LTPopBack(pList);//LTPopFront(pList);/*Print(pList);*/LTNode* pos = LTFind(pList, 2);LTInsert(pos, 6);Print(pList);if (pos == NULL){printf("没有找到");}else{printf("找到了");}
}int main()
{ListTest01();return 0;
}