数据结构C语言实现之双链表

目录

链表的结构

链表的接口

接口的实现

链表有八种结构

1、单向不带头不循环链表

2、单项不带头循环链表

3、单项带头不循环链表

4、单项带头循环链表

5、双向不带头不循环链表

6、双向不带头循环链表

7、双向带头不循环链表

8、双向带头循环链表

而链表中的最优结构就是带头循环双链表

链表的接口

#pragma once
#include
#include
#include
#include

typedef int ListDateType;

typedef struct List
{
	struct List* prev;
	struct List* next;
	ListDateType data;
}List;

//链表的创建
List* ListCreater();

//链表pos位置之前插入
void Listinsert(List* pos, ListDateType x);

//删除pos位置数据
void Listerase(List* pos);

//头插
void Listpush_front(List* l, ListDateType x);

//头删
void Listpop_front(List* l);

//尾插
void Listpush_back(List* l, ListDateType x);

//尾删
void Listpop_back(List* l);

//打印链表
void Listprint(List* l);

//销毁链表
void Listdestroy(List* l);

//查找数据
List* Listfind(List* l, ListDateType x);

//检测链表是否为空
bool Listempty(List* l);

//检查链表大小
size_t Listsize(List* l);

接口的实现

#include"List.h"

//链表的创建
List* ListCreater()
{
	List* newnode = (List*)malloc(sizeof(List));
	if (newnode == NULL)
	{
		printf("malloc faildn");
		exit(0);
	}
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}

//链表pos位置之前插入
void Listinsert(List* pos, ListDateType x)
{
	assert(pos);
	List* newnode = (List*)malloc(sizeof(List));
	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	pos->prev = newnode;
	newnode->data = x;
}

//删除pos位置数据
void Listerase(List* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//头插
void Listpush_front(List* l, ListDateType x)
{
	assert(l);
	Listinsert(l->next, x);
}

//头删
void Listpop_front(List* l)
{
	assert(l);
	assert(l->next != l);
	Listerase(l->next);
}

//尾插
void Listpush_back(List* l, ListDateType x)
{
	assert(l);
	Listinsert(l, x);
}

//尾删
void Listpop_back(List* l)
{
	assert(l);
	assert(l->next != l);
	Listerase(l -> prev);
}

//打印链表
void Listprint(List* l)
{
	assert(l);
	List* cur = l->next;
	while (cur != l)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

//销毁链表
void Listdestroy(List* l)
{
	assert(l);
	List* tail = l->next;
	while (tail != l)
	{
		List* del = tail;
		tail = tail->next;
		free(del);
		del = NULL;
	}
}

//查找数据
List* Listfind(List* l, ListDateType x)
{
	assert(l);
	List* tail = l->next;
	while (tail != l)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}

//检测链表是否为空
bool Listempty(List* l)
{
	if (l->next == l)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//检查链表大小
size_t Listsize(List* l)
{
	assert(l);
	List* tail = l->next;
	size_t size = 0;
	while (tail != l)
	{
		size++;
		tail = tail->next;
	}
	return size;
}