当前位置: 首页 > backend >正文

嵌入式开发学习———Linux环境下数据结构学习(三)

单向循环链表

单向循环链表是一种特殊的单向链表,尾节点的指针指向头节点,形成一个闭环。适用于需要循环访问的场景,如轮询调度。

  • 结构特点:每个节点包含数据域和指向下一个节点的指针,尾节点的指针指向头节点而非空值。
  • 操作复杂度
    • 插入/删除头节点:O(1)
    • 插入/删除尾节点:O(n)(需遍历到尾部)
  • 代码示例(C++)
struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};

双向链表

双向链表的每个节点包含前驱和后继指针,支持双向遍历,但需要更多内存存储指针。

  • 结构特点:节点包含前驱指针(prev)、数据域和后续指针(next)。
  • 操作复杂度
    • 任意位置插入/删除:O(1)(已知前驱节点时)
    • 按值查找:O(n)
  • 代码示例(C++)
struct DNode {int data;DNode* prev;DNode* next;DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

 
作业:

 1.双向链表的部分操作

#include "linklist.h"int main(int argc, const char *argv[])
{//定义一个头linklistptr headptr=NULL;//定义循环变量int i;//定义位置变量int seat;//头的初始化headptr=LinklistHeadnodeApply();//定义新输入数据datatype nwedata;//循环输入数据for(i=0;i<5;i++){puts("请输入一个数:");scanf(" %d",&nwedata);//调用双向链表的头插函数LinklistHeadinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的遍历函数frontLinklistShowfront(headptr);//循环输入数据for(i=0;i<5;i++){puts("请输入一个数:");scanf(" %d",&nwedata);//双向链表的尾插函数LinklistTailinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的头删函数LinklistHeaddelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的尾删函数LinklistTaildelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts("输入想插入的位置:");scanf(" %d",&seat);puts("输入想插入的数据:");scanf(" %d",&nwedata);//调用双向链链表按位置插入函数LinklistSeatinsert(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts("输入想删除的位置:");scanf(" %d",&seat);//调用双向链链表按位置插入函数LinklistSeatdelete(headptr,seat);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts("输入想要修改的位置:");scanf(" %d",&seat);puts("输入想改成的数据:");scanf(" %d",&nwedata);//调用双向链链表按位置修改函数LinklistSeatalter(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts("输入想查找的位置:");scanf(" %d",&seat);//调用双向链链表按位置查找函数LinklistSeatsift(headptr,seat);return 0;
}
#ifndef _LINKLIST_H__
#define _LINKLIST_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>//返回值枚举
enum returntype
{//失败返回FAULSE=-1,//成功返回SUCCESS
};//存储数据类型
typedef int datatype;//双向链链表结构体
typedef struct Node
{//数据域共用体union{//头节点数据域int len;//普通节点数据域datatype data;};//前向指针域struct Node *front;//后向指针域struct Node *next;
}linklist,*linklistptr;//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void);//普通节点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata);//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata);//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr);//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr);//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata);//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr);//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr);//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat);//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat);#endif
#include "linklist.h"//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void)
{//头节点堆区申请linklistptr headptr=(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(headptr==NULL){return NULL;}//初始化headptr->len=0;headptr->front=NULL;headptr->next=NULL;return headptr;
}//普通点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata)
{//普通节点堆区申请linklistptr comptr=(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(comptr==NULL){return NULL;}//初始化comptr->data=nwedata;comptr->front=NULL;comptr->next=NULL;return comptr;
}//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{//定义普通节点指针linklistptr comptr=NULL;//判断是否为nullif(headptr==NULL){return FAULSE;}//普通节点申请comptr=LinklistComnodeApply(nwedata);//申请判断if(comptr==NULL){return FAULSE;}//头插comptr->next=headptr->next;comptr->front=headptr;//判断是否为首个数据if(headptr->next){headptr->next->front=comptr;}headptr->next=comptr;//个数自增headptr->len++;return SUCCESS;
}//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr)
{//定义链表指针linklistptr ptr=NULL;//定义循环变量int i;//判断是否为null//判断链表是否为空if(headptr==NULL||headptr->len==0){return FAULSE;}//输出ptr=headptr->next;puts("正序链表现有数据:");while(ptr){printf("%d ",ptr->data);ptr=ptr->next;}putchar(10);return SUCCESS;
}//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr)
{//定义链表指针linklistptr ptr=NULL;//定义循环变量int i;//判断是否为NULL//判断链表是否为空if(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr->next;while(ptr->next){ptr=ptr->next;}//输出puts("逆序链表现有数据:");while(ptr!=headptr){printf("%d ",ptr->data);ptr=ptr->front;}putchar(10);return SUCCESS;
}//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{//定义链表指针和普通节点指针linklistptr ptr=NULL,comptr=NULL;//判断头是否为nullif(headptr==NULL){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}//初始化普通节点comptr=LinklistComnodeApply(nwedata);//判断申请是否成功if(comptr==NULL){return FAULSE;}//尾插ptr->next=comptr;comptr->front=ptr;//个数自增headptr->len++;return SUCCESS;
}
//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断头是否为nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找到要删除的数据第一个节点deltr=headptr->next;//头删headptr->next=deltr->next;//判断是否只有一个节点if(deltr->next){deltr->next->front=headptr;}free(deltr);deltr=NULL;//个数自减headptr->len--;return SUCCESS;
}//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断头是否为nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}ptr->front->next=NULL;free(ptr);ptr=NULL;headptr->len--;return SUCCESS;
}//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针和普通节点指针linklistptr ptr=NULL,comptr=NULL;//判断头是否为NULL//判断位置是否合法if(headptr==NULL||seat<=0||seat>headptr->len+1){return FAULSE;}//找到对应位置的前一个位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}//初始化普通节点comptr=LinklistComnodeApply(nwedata);//if(comptr==NULL){return FAULSE;}//插入comptr->next=ptr->next;comptr->front=ptr;if(ptr->next!=NULL){ptr->next->front=comptr;}ptr->next=comptr;headptr->len++;return SUCCESS;
}//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到对应位置的前一个位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}deltr=ptr->next;ptr->next=deltr->next;if(deltr->next!=NULL){deltr->next->front=deltr->front;}free(deltr);deltr=NULL;headptr->len--;return SUCCESS;
}//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针linklistptr ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到对应位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}ptr->data=nwedata;return SUCCESS;
}//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针linklistptr ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return NULL;}//找到对应位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}printf("linklist[%d]=%d\n",seat,ptr->data);return ptr;
}

运行示例:


2.牛客网刷题

http://www.xdnf.cn/news/16123.html

相关文章:

  • 《Flutter篇第一章》基于GetX 和 Binding、Dio 实现的 Flutter UI 架构
  • 跨境支付入门~国际支付结算(风控篇)
  • 学习游戏制作记录(技能系统)7.24
  • 二、计算机网络技术——第4章:网络层
  • 《计算机“十万个为什么”》之 [特殊字符] 深浅拷贝 引用拷贝:内存世界的复制魔法 ✨
  • 傅里叶转换(机器视觉方向)
  • MST技术加持,简化桌面多屏布局
  • 解决sparksql创建出来的数据库路径错误的问题
  • 音视频中一些常见的知识点
  • 《狼道》:生存智慧与处世哲学
  • sqlsuger 子表获取主表中的一个字段的写法
  • Python 程序设计讲义(8):Python 的基本数据类型——浮点数
  • 基于springboot的乡村旅游在线服务系统/乡村旅游网站
  • 使用Imgui和SDL2做的一个弹球小游戏-Bounze
  • 回顾 Palantir:八年之旅的反思
  • RCLAMP0502A.TCT Semtech:超低电容TVS二极管,高速接口+军工级防护!
  • lumerical——光纤布拉格光栅(Fiber Bragg gratings)
  • 2025 ACT 汽车功能安全相关PPT分享
  • Python-初学openCV——图像预处理(一)
  • 【盘古100Pro+开发板实验例程】FPGA学习 | Modelsim 的使用和 do 文件编写
  • IO补充.
  • WebGIS 中常用空间数据格式
  • UE 模型动画播放控制
  • Linux下的lcd屏幕显示操作
  • Java学习---Spring及其衍生(上)
  • S段和G段到底有什么区别
  • 算法笔记之归并排序
  • Windows 用 Python3 快速搭建 HTTP 服务器
  • linux驱动开发笔记--GPIO驱动开发
  • WPF的一些基础知识学习记录