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

数据结构 day05

article 2025/2/25 8:23:31

数据结构 day05

  • 5. 队列
    • 5.3. 链式队列
      • 5.3.1. 特征
      • 5.3.2. 代码实现
  • 6. 双向链表
    • 6.1. 特性
      • 6.2. 代码实现

5. 队列

5.3. 链式队列

5.3.1. 特征

逻辑结构：线性结构
存储结构：链式存储
操作：创建、入列、出列、判空、清空

5.3.2. 代码实现

头文件：linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
typedef int datatype;
typedef struct node_t
{
   datatype data;
   struct node_t *next;
} linkqueue_node_t, *linkqueue_list_t;

typedef struct // 将队列头指针和尾指针封装到一个结构体里
{
   linkqueue_list_t front; // 相当于队列的头指针
   linkqueue_list_t rear;  // 相当于队列的尾指针
                           // 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
//1.创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue();
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data);
// 3. 出列
//思想：每次释放front所指节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p);
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
//5.求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
//6.清空队列
void clearLinkQueue(linkqueue_t *p);
#endif
  1. 创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue();
{
	// 申请空间存放队列结构
	linkqueue_list_t q = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
	if (q == NULL)
	{
		printf("Space opening failure!!\n");
		return -1;
	}
	// 初始化
	q->next = NULL;

	// 申请空间存放头尾指针
	linkqueue_t *p = (linkqueue_t*) malloc(sizeof(linkqueue_t));
	if(p == NULL)
	{
		printf("Space opening failure!!\n");
		free(q);
		return -1;
	}
	// 初始化
	p->front = q;
	p->rear = q;
	
	return p;
}
  1. 入列
int inLinkQueue(linkqueue_t *p, datatype data);
{
	// 开辟空间存放新节点，定义指针pnew指向新节点
	linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
	// 容错判断
	if(pnew == NULL)
	{
		printf("Space opening failure!!\n");
		return -1;
	}
	// 新节点初始化
	pnew->data = data;
	pnew->next = NULL;
	// 链接新节点
	p->rear->next = pnew;
	// 尾指针移动
	p->rear = pnew;
	
	return 0；
}
  1. 出列, 每次释放front所指下一个节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p);
{
	// 容错判断
	if(isEmptyLinkQueue(p))
	{
		printf("Linkqueue is empty!!\n");
		return -1;
	}
	// 定义指针pdel，指向被删除节点
	linkqueue_list_t pdel = p->front->next;
	// 定义变量，暂存出列数据
	datatype data = pdel->data;
	// 删除节点
	p->front->next = pdel->next;
	free(pdel);
	pdel = NULL;
	// 出列完成后，如果队列为空，那么召回rear
	if(p->front == NULL)
		p->rear = p->front;
	// 返回出列数据
	return data;
}
  1. 判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
{
	// 以队列的特性呈现
	return p->rear == p->front;
}

也可以使用p->front->next == NULL;来作为判断队列为空的条件，但这是链表特性的内容，作为队列的操作内容，尽量以队列的特性呈现

  1. 求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
{
	// 定义变量存放长度
	int len =0;
	// 定义头指针，头指针遍历链表
	linkqueue_list_t h = p->front;
	// 遍历链表
	while(h->next == NULL)
	{
		h = h->next;
		len ++;
	}
	return len;
}

多定义一个头指针的原因：通过地址找到的front，所以对于front来说，相当于地址传递，所以改变front的指向会影响队头的值

  1. 清空队列
void clearLinkQueue(linkqueue_t *p);
{
	while(!isEmptyLinkQueue(p))
		outLinkQueue(p);
}

6. 双向链表

6.1. 特性

逻辑特性：线性结构
存储结构：链式存储
操作：增删改查
创建：模仿链式队列的形式创建
双向链表的创建结构图

6.2. 代码实现

头文件 doublelinklist.h

#ifndef __DOUBLELINKLIST_H__
#define __DOUBLELINKLIST_H__

// 双向链表的节点定义

typedef int datatype;
typedef struct node_t
{
   datatype data;        // 数据域
   struct node_t *next;  // 指向下一个节点的指针 next 先前的
   struct node_t *prior; // 指向前一个节点的指针 prior 下一个
} link_node_t, *link_node_p;

// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{
   link_node_p head; // 指向双向链表的头指针
   link_node_p tail; // 指向双向链表的尾指针
   int len;          // 用来保存当前双向链表的长度
} double_list_t, *double_list_p;

//1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList();
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data);
// 3.遍历双向链表
void showDoubleLinkList(double_list_p p);
// 4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p);
// 5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p, int post);
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_p p);
//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p,datatype data);
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
void deleteDataDoubleLinkList(double_list_p p, datatype data)；
#endif
  1. 创建一个空的双向链表
double_list_p createEmptyDoubleLinkList()
{
   // 申请空间存放头尾指针
   double_list_p p = (double_list_p)malloc(sizeof(double_list_t));
   if (p == NULL)
   {
       printf("Space opening failure!!\n");
       return NULL;
   }
   // 申请空间存放头节点
   link_node_p ph = (link_node_p)malloc(sizeof(link_node_t));
   if (ph == NULL)
   {
       printf("Space opening failure!!\n");
       free(p);
       p = NULL;
       return NULL;
   }
   // 头尾指针初始化，头节点初始化
   p->head = ph;
   p->tail = ph;
   p->len = 0;
   ph->next = NULL;
   ph->prior = NULL;

   return p;
}
  1. 向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{
   // 容错判断
   if (post < 0 || post > p->len)
   {
       printf("post is err!!\n");
       return -1;
   }
   // 定义temp暂存head或tail
   link_node_p temp = NULL;
   // 定义pnew指向被插入节点
   link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));
   // 初始化
   pnew->data = data;
   pnew->prior = NULL;
   pnew->next = NULL;
   // 判断插入位置在前半段还是后半段
   if (post < p->len / 2)
   {
       temp = p->head;
       for (int i = 0; i < post; i++)
           temp = temp->next;
   }
   else
   {
       temp = p->tail;
       for (int i = p->len - 1; i > post; i--)
           temp = temp->prior;
   }
   // 建立链接
   pnew->next = temp->next;
   pnew->prior = temp;
   temp->next = pnew;
   if (post == p->len)
       // 尾指针移动
       p->tail = pnew;
   else
       pnew->next->prior = pnew;

   // 长度+1
   p->len++;
}
  1. 遍历双向链表
void showDoubleLinkList(double_list_p p)
{
   // 定义h，代替head移动遍历
   link_node_p temp = NULL;
   printf("正向遍历：");
   temp = p->head;
   while (temp->next != NULL)
   {
       temp = temp->next;
       printf("%-4d", temp->data);
   }
   printf("\n");
   printf("反向遍历：");
   temp = p->tail;
   while (temp != p->head)
   {
       printf("%-4d", temp->data);
       temp = temp->prior;
   }
   printf("\n");
}
  1. 判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p)
{
   return p->len == 0;
}
  1. 删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p, int post)
{
   // 容错判断
   if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1)
   {
       printf("deletePostDoubleLinkList err");
       return -1;
   }
   // 定义一个pdel指向被删除节点
   link_node_p pdel = NULL;
   // 判断前半段还是后半段
   if (post < p->len / 2)
   {
       pdel = p->head;
       for (int i = 0; i <= post; i++)
           pdel = pdel->next;
   }
   else
   {
       pdel = p->tail;
       for (int i = p->len - 1; i >= post; i--)
           pdel = pdel->prior;
   }
   // 删除操作
   pdel->prior->next = pdel->next;
   if (pdel->next == NULL)
       p->tail = pdel->prior;
   else
       pdel->next->prior = pdel->prior;

   return 0;
}
  1. 求双向链表的长度
int lengthDoubleLinkList(double_list_p p)
{
   return p->len;
}
  1. 查找指定数据出现的位置 data被查找的数据
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p, datatype data)
{
   // 定义temp指向头指针，代替头指针移动
   link_node_p temp = p->head;
   // 定义变量post，保存位置
   int post = 0;

   while (temp->next == NULL)
   {
       temp = temp->next;
       if (temp->data == data)
           return post;
       post++;
   }

   return -1;
}
  1. 修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
{
   // 容错判断
   if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1)
   {
       printf("changeDataDoubleLinkList err");
       return -1;
   }
   // 定义一个temp，代替头尾指针移动
   link_node_p temp = NULL;
       if (post < p->len / 2)
   {
       temp = p->head;
       for (int i = 0; i <= post; i++)
           temp = temp->next;
   }
   else
   {
       temp = p->tail;
       for (int i = p->len - 1; i >= post; i--)
           temp = temp->prior;
   }
   // 修改数据
   temp->data = data;
   return 0;
}
  1. 删除双向链表中的指定数据 data代表删除所有出现的data数据
void deleteDataDoubleLinkList(double_list_p p, datatype data)
{
   // 定义pdel遍历，暂存被删除节点
   link_node_p pdel = p->head->next;
   // 遍历链表，直到pdel指向最后一个节点时停止
   while (pdel == p->tail)
   {
       if (pdel->data == data)
       {
           pdel->prior->next = pdel->next;
           pdel = pdel->prior;
           free(pdel->next->prior);
           pdel->next->prior = pdel;
           p->len--;
       }
       pdel = pdel->next;
   }
   // 判断最后一个节点数据是否匹配，匹配删除，不匹配就结束遍历
   if (pdel->data == data)
   {
       p->len--;
       p->tail = pdel->prior;
       p->tail->next = NULL;
       free(pdel);
   }
   pdel = NULL;
}

从头节点后节点开始用指针pdel遍历，相当于遍历无头链表，遇到需要删除节点的就用pdel指向它然后删除，如果不需要删除则pdel继续往后走一个节点。


http://www.kler.cn/a/548434.html

相关文章：

  • 【机器学习】常见采样方法详解
  • DeepSeek赋能制造业：图表可视化从入门到精通
  • 《On Java进阶卷》阅读笔记（五）
  • 无人机遥感图像拼接软件有哪些？无人机遥感图像采集流程；遥感图像拼接的一般流程
  • 【原创】解决vue-element-plus-admin无法实现下拉框动态控制表单功能，动态显隐输入框
  • Github 2025-02-14 Java开源项目日报 Top10
  • Svelte 最新中文文档翻译（8）—— @html、@const、@debug 模板语法
  • 工控网络安全架构
  • 【2.10-2.16学习周报】
  • 深度学习框架探秘｜TensorFlow：AI 世界的万能钥匙
  • 如何在MacOS上查看edge/chrome的扩展源码
  • DeepSeek R1完全本地部署实战教程01-课程大纲
  • 2025年 Java 面试八股文
  • 【stm32】定时器输出PWM波形(hal库）
  • springboot整合mybatis-plus(保姆教学) 及搭建项目
  • C# Barrier 类使用详解
  • AI写代码工具赋能前端开发：解锁职业发展新高度
  • 买卖股票的最佳时机II(力扣122)
  • 离线量化算法和工具 --学习记录1
  • CAS单点登录（第7版）10.多因素身份验证