链表——双向链表的实现
链表的概念及结构
概念： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构：
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
带头双向循环链表的介绍（重点）
双向链表的实现
模型
思路（独一份）
双链表的各种方法实现
创建结构体并创建结构体指针变量
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
注意：
我们并不知道要存储什么数据,以int为例. 之所以用 LTDataType是为了以后修改int类型或其他类型方便。
实现双向表初始化
LTNode* BuyListNode(LTDataType x)//写一个结点
{
LTNode* new = (LTNode*)malloc(sizeof(LTNode));
if (new == NULL)
{
perror("BuyListNode");
}
new->data = x;
new->next = NULL;
new->prev = NULL;
return new;
}
LTNode* ListInit()//将双向表初始化
{
LTNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
实现双向链表销毁
void ListDestroy(LTNode* phead)
{
assert(phead);
size_t i = ListSize(phead);
while (i--)
{
ListPopBack(phead);
}
//free(phead);
//phead = NULL;
}
ListDestroy(list);
free(list);
list = NULL;
实现双向链表打印
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
双向链表打印已经没什么可说的了，无非是遍历这里要注意的点是：双向链表实现的是双向带头循环链表，因此当循环指向头结点时循环结束。
实现双向链表在任意位置的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* new = BuyListNode(x);
p->next = new;
new->prev = p;
new->next = pos;
pos->prev = new;
}
实现双向链表在任意位置进行删除
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
free(pos);
pos = NULL;
p->next = n;
n->prev = p;
}
实现双向链表的头删和尾删、头插和尾插
注意：双向链表的头删和尾删、头插和尾插的实现时，要注意pos的位置
void ListPopBack(LTNode* phead)
{
assert(phead);
ListErase(phead->prev);
}
void ListPopFront(LTNode* phead)
{
assert(phead);
ListErase(phead->next);
}
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}
实现双向链表查找
经历过上方的增删的实现这个查的实现就相对简单，只需遍历（但注意指针到头结点时停止循环）
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (x == cur->data)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
实现双向链表的判空
bool ListEmpty(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
if (cur == phead)
{
return true;
}
else
{
return false;
}
}
实现求双向链表的元素数量
这个是实现方法与双向链表打印相似，都是遍历（但注意指针到头结点时停止循环）
size_t ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
size_t i = 0;
while (cur != phead)
{
i++;
cur = cur->next;
}
return i;
}
原码
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
void ListPrint(LTNode* phead);
LTNode* BuyListNode(LTDataType x);
//void ListInit(LTNode** pphead);
LTNode* ListInit();
void ListDestroy(LTNode* phead);
bool ListEmpty(LTNode* phead);
size_t ListSize(LTNode* phead);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDataType x);
void ListErase(LTNode* pos);
void ListInsert(LTNode* pos, LTDataType x);
List.c
#include"List.h"
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
LTNode* BuyListNode(LTDataType x)
{
LTNode* new = (LTNode*)malloc(sizeof(LTNode));
if (new == NULL)
{
perror("BuyListNode");
}
new->data = x;
new->next = NULL;
new->prev = NULL;
return new;
}
LTNode* ListInit()
{
LTNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
bool ListEmpty(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
if (cur == phead)
{
return true;
}
else
{
return false;
}
}
size_t ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
size_t i = 0;
while (cur != phead)
{
i++;
cur = cur->next;
}
return i;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (x == cur->data)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* new = BuyListNode(x);
p->next = new;
new->prev = p;
new->next = pos;
pos->prev = new;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* p = pos->prev;
LTNode* n = pos->next;
free(pos);
pos = NULL;
p->next = n;
n->prev = p;
}
void ListPopBack(LTNode* phead)
{
assert(phead);
ListErase(phead->prev);
}
void ListPopFront(LTNode* phead)
{
assert(phead);
ListErase(phead->next);
}
void ListDestroy(LTNode* phead)
{
assert(phead);
size_t i = ListSize(phead);
while (i--)
{
ListPopBack(phead);
}
//free(phead);
//phead = NULL;
}
test.c
#include"List.h"
int main()
{
LTNode* list= ListInit();
ListPushBack(list, 1);
ListPushBack(list, 2);
ListPushBack(list, 3);
ListPushBack(list, 4);
ListPushBack(list, 5);
ListPrint(list);
ListPopBack(list);
ListPrint(list);
ListPopFront(list);
ListPrint(list);
ListDestroy(list);
free(list);
list = NULL;
//ListPrint(list);
return 0;
}
运行结果
终于~结束了