实现双向循环链表

双向循环链表

本文章将展示zack实现双向循环链表的代码

// list.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int data_type;
typedef struct list_node
{
	data_type data;
	struct list_node* next;
	struct list_node* prve;
}list_node;

list_node* buy_node(data_type x);

void list_init(list_node** pphead);

void list_print(list_node* phead);

void list_push_back(list_node* phead, data_type x);

void list_push_front(list_node* phead, data_type x);

bool list_empty(list_node* phead);

void list_pop_back(list_node* phead);

void list_pop_front(list_node* phead);

list_node* list_find(list_node* phead, data_type x);

// 在指定位置之前插入
void list_insert(list_node* pos, data_type x);

void list_erase(list_node* pos);

void list_destroy(list_node** pphead);

// list.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"

list_node* buy_node(data_type x)
{
	list_node* new_node = (list_node*)malloc(sizeof(list_node));
	if (new_node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	new_node->data = x;
	new_node->next = new_node->prve = new_node;
	return new_node;
}

void list_init(list_node** pphead)
{
	*pphead = buy_node(-1);
}

void list_print(list_node* phead)
{
	list_node* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

void list_push_back(list_node* phead, data_type x)
{
	assert(phead);
	list_node* new_node = buy_node(x);
	new_node->next = phead;
	new_node->prve = phead->prve;
	phead->prve->next = new_node;
	phead->prve = new_node;
}

void list_push_front(list_node* phead, data_type x)
{
	assert(phead);
	list_node* new_node = buy_node(x);
	new_node->next = phead->next;
	new_node->prve = phead;
	phead->next->prve = new_node;
	phead->next = new_node;
}

bool list_empty(list_node* phead)
{
	assert(phead);
	return phead->next == phead;
}

void list_pop_back(list_node* phead)
{
	list_empty(phead);
	assert(phead);
	list_node* del = phead->prve;
	phead->prve->prve->next = phead;
	phead->prve = phead->prve->prve;
	free(del);
	del = NULL;
}

void list_pop_front(list_node* phead)
{
	list_empty(phead);
	assert(phead);
	list_node* del = phead->next;
	phead->next->next->prve = phead;
	phead->next = phead->next->next;
	free(del);
	del = NULL;
}

list_node* list_find(list_node* phead, data_type x)
{
	list_node* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

void list_insert(list_node* pos, data_type x)
{
	assert(pos);
	list_node* new_node = buy_node(x);
	new_node->next = pos;
	new_node->prve = pos->prve;
	pos->prve->next= new_node;
	pos->prve = new_node;
}

void list_erase(list_node* pos)
{
	assert(pos);
	pos->prve->next = pos->next;
	pos->next->prve = pos->prve;
	free(pos);
	pos = NULL;
}

void list_destroy(list_node** pphead)
{
	assert(pphead && *pphead);
	list_node* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		list_node* del = pcur;
		pcur = pcur->next;
		free(del);
		del = NULL;
	}
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

// test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"

void list_test01()
{
	list_node* plist;
	list_init(&plist); // 这里是传哨兵位的地址，因为plist的指向发生改变
	list_push_back(plist, 1);
	list_push_back(plist, 2);
	list_push_back(plist, 3);
	list_push_back(plist, 4);
	list_push_back(plist, 5);
	list_print(plist);
	list_push_front(plist, 5);
	list_push_front(plist, 4);
	list_push_front(plist, 3);
	list_push_front(plist, 2);
	list_print(plist);
}

void list_test02()
{
	list_node* plist;
	list_init(&plist);
	list_push_back(plist, 1);
	list_push_back(plist, 2);
	list_push_back(plist, 3);
	list_push_back(plist, 4);
	list_print(plist);
	list_pop_back(plist);
	list_print(plist);
	list_pop_back(plist);
	list_print(plist);
	list_pop_back(plist);
	list_print(plist);
	list_pop_back(plist);
	list_print(plist);
}

void list_test03()
{
	list_node* plist;
	list_init(&plist);
	list_push_back(plist, 1);
	list_push_back(plist, 2);
	list_push_back(plist, 3);
	list_push_back(plist, 4);
	list_print(plist);
	list_pop_front(plist);
	list_print(plist);
	list_pop_front(plist);
	list_print(plist);
	list_pop_front(plist);
	list_print(plist);
}

void list_test04()
{
	list_node* plist;
	list_init(&plist);
	list_push_back(plist, 1);
	list_push_back(plist, 2);
	list_push_back(plist, 3);
	list_push_back(plist, 4);
	list_print(plist);
	list_node* pos = list_find(plist, 1);
	list_insert(pos, 22);
	list_print(plist);
	pos = list_find(plist, 22);
	list_erase(pos);
	list_print(plist);
	list_destroy(&plist);
}
int main()
{
	//list_test01();
	//list_test02();
	//list_test03();
	list_test04();
	return 0;
}

完