双向链表的基本操作C语言

双向链表的实现

本质: 其实就是定义两个指针域, 分别存放直接前驱结点的指针和直接后继结点的指针.

具体实现

定义一个双向链表

//定义一个双向链表
typedef struct LNode {
	int data;
	struct LNode* next;
	struct LNode* prior;
}LNode, *LinkList;

创建一个指定大小的双向链表

//创建一个指定大小的双向链表
void CreateList(LinkList* L, int n) {
	if (n < 1) {
		printf("输出有误\n");
		return;
	}
	printf("请输入 %d 个数据:", n);
	//创建头结点
	*L = (LinkList)malloc(sizeof(LNode));
	if (!(*L)) {
		exit(0);
	}
	LinkList rear = *L;
	LinkList p = NULL;
	for (int i = 0; i < n; ++i) {
		p = (LinkList)malloc(sizeof(LNode));
		if (!p) {
			exit(0);
		}
		scanf("%d", &p->data);
		rear->next = p;
		p->prior = rear;
		rear = p;
	}
	rear->next = NULL;
}

求链表的长度

//求链表的长度
int Length(LinkList L) {
	int len = 0;
	while (L->next != NULL) {
		++len;
		L = L->next;
	}
	return len;
}

双向链表的插入操作

//双向链表的插入操作
void Insert(LinkList* L, int pos, int e) {
	//判断插入的位置是否合理
	if (pos < 1 || pos > Length(*L) + 1) {
		printf("插入位置不合理\n");
		return;
	}
	LinkList adjust = *L;
	int i = 0;
	//只许循环 pos - 1 次
	while (i++ < pos - 1) {
		adjust = adjust->next;
	}
	LinkList p = (LinkList)malloc(sizeof(LNode));
	if (!p) {
		exit(0);
	}
	p->data = e;
	//连接
	p->next = adjust->next;
	adjust->next->prior = p;
	adjust->next = p;
	p->prior = adjust;
}

双向链表的删除操作:与插入操作类似, 在此不再赘述
双向链表的遍历

//双向链表的遍历
void Traverse(LinkList L) {
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
	printf("\n");
}

双向链表的销毁

//双向链表的销毁
void Destroy(LinkList* L) {
	LinkList adjust = *L;
	while (*L) {
		adjust = adjust->next;
		free(*L);
		*L = adjust;
	}
}

双向链表的倒序遍历

void Reverse(LinkList L) {
	LinkList adjust = L;
	while (adjust->next) {
		adjust = adjust->next;
	}
	while (adjust != L) {
		printf("%d ", adjust->data);
		adjust = adjust->prior;
	}
	printf("\n");
}

测试

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
//定义一个双向链表
typedef struct LNode {
	int data;
	struct LNode* next;
	struct LNode* prior;
}LNode, *LinkList;
//创建一个指定大小的双向链表
void CreateList(LinkList* L, int n) {
	if (n < 1) {
		printf("输出有误\n");
		return;
	}
	printf("请输入 %d 个数据:", n);
	//创建头结点
	*L = (LinkList)malloc(sizeof(LNode));
	if (!(*L)) {
		exit(0);
	}
	LinkList rear = *L;
	LinkList p = NULL;
	for (int i = 0; i < n; ++i) {
		p = (LinkList)malloc(sizeof(LNode));
		if (!p) {
			exit(0);
		}
		scanf("%d", &p->data);
		rear->next = p;
		p->prior = rear;
		rear = p;
	}
	rear->next = NULL;
}
//求链表的长度
int Length(LinkList L) {
	int len = 0;
	while (L->next != NULL) {
		++len;
		L = L->next;
	}
	return len;
}
//双向链表的插入操作
void Insert(LinkList* L, int pos, int e) {
	//判断插入的位置是否合理
	if (pos < 1 || pos > Length(*L) + 1) {
		printf("插入位置不合理\n");
		return;
	}
	LinkList adjust = *L;
	int i = 0;
	//只许循环 pos - 1 次
	while (i++ < pos - 1) {
		adjust = adjust->next;
	}
	LinkList p = (LinkList)malloc(sizeof(LNode));
	if (!p) {
		exit(0);
	}
	p->data = e;
	//连接
	p->next = adjust->next;
	adjust->next->prior = p;
	adjust->next = p;
	p->prior = adjust;
}
//双向链表的遍历
void Traverse(LinkList L) {
	while (L->next) {
		printf("%d ", L->next->data);
		L = L->next;
	}
	printf("\n");
}
//双向链表的销毁
void Destroy(LinkList* L) {
	LinkList adjust = *L;
	while (*L) {
		adjust = adjust->next;
		free(*L);
		*L = adjust;
	}
}
void Reverse(LinkList L) {
	LinkList adjust = L;
	while (adjust->next) {
		adjust = adjust->next;
	}
	while (adjust != L) {
		printf("%d ", adjust->data);
		adjust = adjust->prior;
	}
	printf("\n");
}
int main() {
	LinkList L1;
	CreateList(&L1, 5);
	Reverse(L1);
	//Traverse(L1);
	//Insert(&L1, 3, 100);
	//Traverse(L1);
	Destroy(&L1);
	if (!L1) {
		printf("OK\n");
	}
	system("pause");
	return 0;
}

效果图

希望该文章能对大家有所帮助
同时真诚接受大家宝贵评论和建议