当前位置： 代码网 > it编程>软件设计>数据结构 > 【海贼王的数据航海】链表—双向链表

【海贼王的数据航海】链表—双向链表

2024年08月02日 • 数据结构 •我要评论
可能需要搬移元素，效率低O(N)逻辑上连续，但物理上不一定连续。动态顺序表，空间不够时需要扩容。任意位置插入或者删除元素。元素高效存储+频繁访问。任意位置插入和删除频繁。

目录

往期

1 -> 带头+双向+循环链表(双链表)

1.1 -> 接口声明

1.2 -> 接口实现

1.2.1 -> 双向链表初始化

1.2.2 -> 动态申请一个结点

1.2.3 -> 双向链表销毁

1.2.4 -> 双向链表打印

1.2.5 -> 双向链表判空

1.2.6 -> 双向链表尾插

1.2.7 -> 双向链表尾删

1.2.8 -> 双向链表头插

1.2.9 -> 双向链表头删

1.2.10 -> 双向链表查找

1.2.11 ->  双向链表在pos的前面进行插入

1.2.12 -> 双向链表删除pos位置的节点

2 -> 顺序表和链表的区别

3 -> 完整代码

3.1 -> list.c

3.2 -> list.h

3.3 -> test.c

往期

链表-单链表

1 -> 带头+双向+循环链表(双链表)

1.1 -> 接口声明

#pragma once

#define  _crt_secure_no_warnings 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 带头+双向+循环链表增删查改实现
typedef int ltdatatype;

typedef struct ltnode
{
	ltdatatype data;
	struct ltnode* next;
	struct ltnode* prev;
}ltnode;

// 双向链表初始化
ltnode* ltinit();

// 动态申请一个结点
ltnode* buyltnode(ltdatatype x);

// 双向链表销毁
void ltdestory(ltnode* phead);

// 双向链表打印
void ltprint(ltnode* phead);

// 双向链表判空
bool ltempty(ltnode* phead);

// 双向链表尾插
void ltpushback(ltnode* phead, ltdatatype x);

// 双向链表尾删
void ltpopback(ltnode* phead);

// 双向链表头插
void ltpushfront(ltnode* phead, ltdatatype x);

// 双向链表头删
void ltpopfront(ltnode* phead);

// 双向链表查找
ltnode* ltfind(ltnode* phead, ltdatatype x);

// 双向链表在pos的前面进行插入
void ltinsert(ltnode* pos, ltdatatype x);

// 双向链表删除pos位置的节点
void lterase(ltnode* pos);

1.2 -> 接口实现

1.2.1 -> 双向链表初始化

// 双向链表初始化
ltnode* ltinit()
{
	ltnode* phead = buyltnode(-1);

	phead->next = phead;
	phead->prev = phead;

	return phead;
}

1.2.2 -> 动态申请一个结点

// 动态申请一个结点
ltnode* buyltnode(ltdatatype x)
{
	ltnode* newnode = (ltnode*)malloc(sizeof(ltnode));
	if (newnode == null)
	{
		perror("malloc fail");
		return null;
	}

	newnode->data = x;
	newnode->next = null;
	newnode->prev = null;

	return newnode;
}

1.2.3 -> 双向链表销毁

// 双向链表销毁
void ltdestory(ltnode* phead)
{
	assert(phead);
	ltnode* cur = phead->next;
	while (cur != phead)
	{
		ltnode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

1.2.4 -> 双向链表打印

// 双向链表打印
void ltprint(ltnode* phead)
{
	assert(phead);

	printf("guard<==>");
	ltnode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

1.2.5 -> 双向链表判空

// 双向链表判空
bool ltempty(ltnode* phead)
{
	assert(phead);

	return phead->next == phead;
}

1.2.6 -> 双向链表尾插

// 双向链表尾插
void ltpushback(ltnode* phead, ltdatatype x)
{
	assert(phead);

	ltnode* tail = phead->prev;
	ltnode* newnode = buyltnode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	// 复用
	// ltinsert(phead, x);
}
// 尾插测试
void test1()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

 

1.2.7 -> 双向链表尾删

// 双向链表尾删
void ltpopback(ltnode* phead)
{
	assert(phead);
	assert(!ltempty(phead));

	ltnode* tail = phead->prev;
	ltnode* tailprev = tail->prev;

	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;

	// 复用
	// lterase(phead->prev);
}

// 尾删测试
void test2()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

1.2.8 -> 双向链表头插

// 双向链表头插
void ltpushfront(ltnode* phead, ltdatatype x)
{
	assert(phead);
	ltnode* newnode = buyltnode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

	// 复用
	// ltinsert(phead->next, x);
}
// 头插测试
void test3()
{
	ltnode* plist = ltinit();

	ltpushfront(plist, 1);
	ltpushfront(plist, 2);
	ltpushfront(plist, 3);
	ltpushfront(plist, 4);
	ltpushfront(plist, 5);

	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

1.2.9 -> 双向链表头删

// 双向链表头删
void ltpopfront(ltnode* phead)
{
	assert(phead);
	assert(!ltempty(phead));
	ltnode* first = phead->next;
	ltnode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);

	// 复用
	// lterase(phead->next);
}
// 头删测试
void test4()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

1.2.10 -> 双向链表查找

// 双向链表查找
ltnode* ltfind(ltnode* phead, ltdatatype x)
{
	assert(phead);

	ltnode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return null;
}

1.2.11 ->  双向链表在pos的前面进行插入

// 双向链表在pos的前面进行插入
void ltinsert(ltnode* pos, ltdatatype x)
{
	assert(pos);

	ltnode* prev = pos->prev;
	ltnode* newnode = buyltnode(x);

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

// 查找插入测试
void test5()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltnode* pos = ltfind(plist, 3);
	if (pos)
		ltinsert(pos, 99);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

1.2.12 -> 双向链表删除pos位置的节点

// 双向链表删除pos位置的节点
void lterase(ltnode* pos)
{
	assert(pos);

	ltnode* posprev = pos->prev;
	ltnode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;

	free(pos);
}

2 -> 顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持o(1)不支持:o(n)
任意位置插入或者删除元素可能需要搬移元素，效率低o(n)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

注：缓存利用率参考存储体系结构以及局部原理性。

3 -> 完整代码

3.1 -> list.c

#include "list.h"

// 双向链表初始化
ltnode* ltinit()
{
	ltnode* phead = buyltnode(-1);

	phead->next = phead;
	phead->prev = phead;

	return phead;
}

// 动态申请一个结点
ltnode* buyltnode(ltdatatype x)
{
	ltnode* newnode = (ltnode*)malloc(sizeof(ltnode));
	if (newnode == null)
	{
		perror("malloc fail");
		return null;
	}

	newnode->data = x;
	newnode->next = null;
	newnode->prev = null;

	return newnode;
}

// 双向链表销毁
void ltdestory(ltnode* phead)
{
	assert(phead);
	ltnode* cur = phead->next;
	while (cur != phead)
	{
		ltnode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

// 双向链表打印
void ltprint(ltnode* phead)
{
	assert(phead);

	printf("guard<==>");
	ltnode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

// 双向链表判空
bool ltempty(ltnode* phead)
{
	assert(phead);

	return phead->next == phead;
}

// 双向链表尾插
void ltpushback(ltnode* phead, ltdatatype x)
{
	assert(phead);

	ltnode* tail = phead->prev;
	ltnode* newnode = buyltnode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	// 复用
	// ltinsert(phead, x);
}

// 双向链表尾删
void ltpopback(ltnode* phead)
{
	assert(phead);
	assert(!ltempty(phead));

	ltnode* tail = phead->prev;
	ltnode* tailprev = tail->prev;

	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;

	// 复用
	// lterase(phead->prev);
}

// 双向链表头插
void ltpushfront(ltnode* phead, ltdatatype x)
{
	assert(phead);
	ltnode* newnode = buyltnode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

	// 复用
	// ltinsert(phead->next, x);
}

// 双向链表头删
void ltpopfront(ltnode* phead)
{
	assert(phead);
	assert(!ltempty(phead));
	ltnode* first = phead->next;
	ltnode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);

	// 复用
	// lterase(phead->next);
}

// 双向链表查找
ltnode* ltfind(ltnode* phead, ltdatatype x)
{
	assert(phead);

	ltnode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return null;
}

// 双向链表在pos的前面进行插入
void ltinsert(ltnode* pos, ltdatatype x)
{
	assert(pos);

	ltnode* prev = pos->prev;
	ltnode* newnode = buyltnode(x);

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

// 双向链表删除pos位置的节点
void lterase(ltnode* pos)
{
	assert(pos);

	ltnode* posprev = pos->prev;
	ltnode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;

	free(pos);
}

3.2 -> list.h

#pragma once

#define  _crt_secure_no_warnings 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 带头+双向+循环链表增删查改实现
typedef int ltdatatype;

typedef struct ltnode
{
	ltdatatype data;
	struct ltnode* next;
	struct ltnode* prev;
}ltnode;

// 双向链表初始化
ltnode* ltinit();

// 动态申请一个结点
ltnode* buyltnode(ltdatatype x);

// 双向链表销毁
void ltdestory(ltnode* phead);

// 双向链表打印
void ltprint(ltnode* phead);

// 双向链表判空
bool ltempty(ltnode* phead);

// 双向链表尾插
void ltpushback(ltnode* phead, ltdatatype x);

// 双向链表尾删
void ltpopback(ltnode* phead);

// 双向链表头插
void ltpushfront(ltnode* phead, ltdatatype x);

// 双向链表头删
void ltpopfront(ltnode* phead);

// 双向链表查找
ltnode* ltfind(ltnode* phead, ltdatatype x);

// 双向链表在pos的前面进行插入
void ltinsert(ltnode* pos, ltdatatype x);

// 双向链表删除pos位置的节点
void lterase(ltnode* pos);

3.3 -> test.c

#include "list.h"

// 尾插测试
void test1()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

// 尾删测试
void test2()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);
	ltpopback(plist);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

// 头插测试
void test3()
{
	ltnode* plist = ltinit();

	ltpushfront(plist, 1);
	ltpushfront(plist, 2);
	ltpushfront(plist, 3);
	ltpushfront(plist, 4);
	ltpushfront(plist, 5);

	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

// 头删测试
void test4()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);
	ltpopfront(plist);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

// 查找插入测试
void test5()
{
	ltnode* plist = ltinit();

	ltpushback(plist, 1);
	ltpushback(plist, 2);
	ltpushback(plist, 3);
	ltpushback(plist, 4);
	ltpushback(plist, 5);

	ltprint(plist);

	ltnode* pos = ltfind(plist, 3);
	if (pos)
		ltinsert(pos, 99);
	ltprint(plist);

	ltdestory(plist);
	plist = null;
}

int main()
{


	return 0;
}

感谢大佬们支持！！！

互三啦！！！

赞 (0)

相关文章:

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。

发表评论

验证码：
最近更新的文章
推荐阅读
大家感兴趣的文章
Copyright © 2017-2025  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱：2386932994@qq.com