当前位置： 首页 > article >正文

C语言双向链表操作

article 2024/10/22 9:26:29

   双向链表（Double-Linked List）是链表的一种，相比于单链表，它的每个节点不仅包含数据域，还具备两个指针域，分别指向前一个节点和后一个节点。这样的结构赋予了双向链表更高的操作灵活性和更多的应用场景。双向链表的每个数据节点中都有两个指针，一个指针指向前一个，另一个指针指向下一个。头部指针的上一个指向尾部，尾部的下一个指向头部。

1.定义


struct node_t {
	struct node_t *pre;
	struct node_t *next;
};

struct person {
	char *name;
	int age;
	struct node_t node;
};

struct list {
	char *name; /* A班 */
	struct node_t head;
};

        首先定义个一个node_t的结构体，结构体中包含两个节点，struct node_t *pre;表示上一个节点，struct node_t *next;表示下一个节点。创建的person结构体包含person的名字、年龄以及节点。list链表包含了链表的名字以及头结点。

2.链表初始化

        创建一个空的双向链表，并设置头节点。头节点通常不存储实际数据，只作为链表的起始标志，并指向链表的第一个实际数据节点（如果存在）。同时，头节点的两个指针域通常初始化为指向自身，以形成循环链表的结构，便于后续操作。

void InitList(struct list *pList, char *name)
{
	pList->name = name;
	pList->head.next = &pList->head;
	pList->head.pre  = &pList->head;
}

初始化链表的名字，将链表头结点的下一个指向头结点本身，链表头结点的前一项指向头结点本身，以实现循环链表结构。

3.添加链表节点

        对双向链表进行插入节点操作，函数有两个参数，struct list *pList, struct node_t *new_node分别表示操作的链表、需要插入的新节点。

        最后一个节点last指向头结点的前一个节点，需要插入的新节点的下一个节点指向链表头结点的地址，last节点的下一个节点指向新节点。新节点的前一项指向last节点，而last节点是链表的头结点，因此新节点的前一项为头结点。头结点的下一项指向新节点，即完成了插入工作（在尾部插入）

void AddItemToList(struct list *pList, struct node_t *new_node)
{
	struct node_t *last = pList->head.pre;
	
	new_node->next  = &pList->head;
	last->next      = new_node;
	new_node->pre   = last;
	pList->head.pre = new_node;
}

这样即可在插入节点，每运行一次都能将新节点插入在最后位置

4.在节点后面插入节点

pre为插入新节点的前面一个节点，new_node为新节点，先创建一个右边节点ringht。将pre节点的下一个的值赋给*right，pre节点的下一个指向new_node节点，new_node的next指向right节点，rihgt的上一个指向new_node节点，new_node的前一个指向pre节点，这样即可完成插入操作。

void AddItemAfter(struct node_t *pre, struct node_t *new_node)
{
	struct node_t *right = pre->next;
	
	pre->next = new_node;
	new_node->next = right;
	
	right->pre = new_node;
	new_node->pre = pre;
}

5.删除节点

        删除节点，找到需要删除的节点，以及需要删除节点的左节点、以及右节点。把左节点的下一项指向右节点，右节点的前一项指向左节点即可。


void DelItemFromList(struct list *pList, struct node_t *node)
{
	struct node_t *left  = node->pre;
	struct node_t *right = node->next;
	
	left->next = right;
	right->pre = left;
}

6.比较年龄大小


int CmpPersonAge(struct node_t *pre, struct node_t *next)
{
	struct person *p;
	struct person *n;
	
	p = container_of(pre, struct person, node);
	n = container_of(next, struct person, node);
	
	if (p->age < n->age)
		return -1;
	else
		return 0;
}

7.排序

本次链表排序根据链表中person的年龄进行排序，小的在前大的在后。


void SortList(struct list *pList)
{
	struct node_t *pre1 = &pList->head;
	struct node_t *pre2;
	struct node_t *cur = pre1->next;
	struct node_t *next;
	struct node_t *tmp;
		
	while (cur != &pList->head)
	{
		pre2 = cur;
		next = cur->next;
		while (next != &pList->head)
		{
			if (CmpPersonAge(cur, next) == 0) //判断是否cur>next;
			{
				/* 交换节点 */
				/* 1. del cur */
				DelItemFromList(pList, cur);
				
				/* 2. del next */
				DelItemFromList(pList, next);
				
				/* 3. 在pre1之后插入next */
				AddItemAfter(pre1, next);
				
				/* 4. 在pre2之后插入cur */
				if (pre2 == cur)
					AddItemAfter(next, cur);
				else
					AddItemAfter(pre2, cur);
				
				/* 5. cur/next指针互换 */
				tmp = cur;
				cur = next;
				next = tmp;				
			}
			
			pre2 = next;
			next = next->next;
		}
		
		pre1 = cur;
		cur = cur->next;
	}
	
}

本次排序类似冒泡排序法，每次通过相邻的两位进行排序，如果cur的年龄大于next的年龄，那么删除cur节点，并删除next节点。并在pre1节点插入next节点，在pre2后插入cur节点。这样即可完成节点位置交换。

8.附录


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define container_of(ptr, type, member) \
	(type *)((char *)ptr - (unsigned int)&((type *)0)->member)

struct node_t {
	struct node_t *pre;
	struct node_t *next;
};

struct person {
	char *name;
	int age;
	struct node_t node;
};

struct list {
	char *name; /* A班 */
	struct node_t head;
};

void InitList(struct list *pList, char *name)
{
	pList->name = name;
	pList->head.next = &pList->head;
	pList->head.pre  = &pList->head;
}

void AddItemToList(struct list *pList, struct node_t *new_node)
{
	struct node_t *last = pList->head.pre;
	
	new_node->next  = &pList->head;
	last->next      = new_node;
	new_node->pre   = last;
	pList->head.pre = new_node;
}

void AddItemAfter(struct node_t *pre, struct node_t *new_node)
{
	struct node_t *right = pre->next;
	
	pre->next = new_node;
	new_node->next = right;
	
	right->pre = new_node;
	new_node->pre = pre;
}

void DelItemFromList(struct list *pList, struct node_t *node)
{
	struct node_t *left  = node->pre;
	struct node_t *right = node->next;
	
	left->next = right;
	right->pre = left;
}

int CmpPersonAge(struct node_t *pre, struct node_t *next)
{
	struct person *p;
	struct person *n;
	
	p = container_of(pre, struct person, node);
	n = container_of(next, struct person, node);
	
	if (p->age < n->age)
		return -1;
	else
		return 0;
}

void SortList(struct list *pList)
{
	struct node_t *pre1 = &pList->head;
	struct node_t *pre2;
	struct node_t *cur = pre1->next;
	struct node_t *next;
	struct node_t *tmp;
		
	while (cur != &pList->head)
	{
		pre2 = cur;
		next = cur->next;
		while (next != &pList->head)
		{
			if (CmpPersonAge(cur, next) == 0) //判断是否cur>next;
			{
				/* 交换节点 */
				/* 1. del cur */
				DelItemFromList(pList, cur);
				
				/* 2. del next */
				DelItemFromList(pList, next);
				
				/* 3. 在pre1之后插入next */
				AddItemAfter(pre1, next);
				
				/* 4. 在pre2之后插入cur */
				if (pre2 == cur)
					AddItemAfter(next, cur);
				else
					AddItemAfter(pre2, cur);
				
				/* 5. cur/next指针互换 */
				tmp = cur;
				cur = next;
				next = tmp;				
			}
			
			pre2 = next;
			next = next->next;
		}
		
		pre1 = cur;
		cur = cur->next;
	}
	
}

void PrintList(struct list *pList)
{
	int i = 0;
	
	struct node_t *node = pList->head.next;
	struct person *p;
	
	while (node != &pList->head)
	{
		p = container_of(node, struct person, node);
		printf("person %d: %s is %d\r\n", i++, p->name, p->age);
		
		/* 后面还有人, 移动到下一个 */
		node = node->next;
	}
}

int main(int argc, char **arg)
{
	struct list a_list;
	int i;

	struct person p[] = {
		{"p1", 10, {NULL}},
		{"p2", 20, {NULL}},
		{"p3", 13, {NULL}},
		{"p4", 41, {NULL}},
		{"p5", 56, {NULL}},
		{"p6", 12, {NULL}},
		{"p7", 9, {NULL}},
		{"p8", 21, {NULL}},
		{"p9", 22, {NULL}},
		{"p10", 21, {NULL}},
		{"p11", 20, {NULL}},
		{NULL, 0, {NULL}},
	};
	
	
    HAL_Init();
    
    MX_USART1_UART_Init();

	InitList(&a_list, "A_class");

	i = 0;
	while (p[i].name != NULL)
	{
		AddItemToList(&a_list, &p[i].node);
		i++;
	}

	printf("add all person:\r\n");
	PrintList(&a_list);
	
	DelItemFromList(&a_list, &p[3].node);

	printf("del person %s:\r\n", p[3].name);
	PrintList(&a_list);

	DelItemFromList(&a_list, &p[0].node);
	
	printf("del person %s:\r\n", p[0].name);
	PrintList(&a_list);
	
	SortList(&a_list);
	printf("sort list, all person:\r\n");
	PrintList(&a_list);
    
    while(1)
    {
    }
}

9.运行结果


http://www.kler.cn/news/353682.html

相关文章：

  • I\O进程线程（Day29）
  • leetcode力扣刷题系列——【最小元素和最大元素的最小平均值】
  • uniapp vue3 watch监听使用情况
  • 【微服务】深入探讨微服务架构：现代软件开发的变革之路
  • 【Postgresql】根据响应数据反向实现建表语句与insert语句
  • C++11 wrapper装饰器 bind+function
  • 【服务器知识】Tomcat简单入门
  • 10月17日，每日信息差
  • Leetcode 最小栈
  • 小白投资理财 - 中国股票代号
  • NVIDIA Bluefield DPU上的启动流程4个阶段分别是什么？作用是什么？
  • 机器学习——主要分类
  • 2024软件测试面试大全（答案+文档）
  • Springboot 整合 Java DL4J 实现安防监控系统
  • 前端布局，y轴超出滚动、x轴超出展示方案
  • 全金属的两足机器人钢铁侠开发
  • [山河2024] week2
  • 基于机器学习的心脏病风险评估预测系统
  • JavaScript获取array中相同key的平均值
  • 基于SSM电子资源管理系统的设计