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

嵌入式开发学习———Linux环境下数据结构学习（一）

ai 2025/7/23 18:20:33

数据

数据是信息的载体，指能够被计算机识别、存储和处理的符号集合，包括数字、文本、图像、声音等。数据本身没有特定含义，需通过上下文或处理赋予价值。例如，数字“42”可能是年龄、温度或编号，具体含义取决于应用场景。

结构

结构指数据之间的逻辑或物理关系，用于组织和管理数据。它描述数据如何关联、排列或分类，例如线性关系（如数组）、层次关系（如树）或网状关系（如图）。结构的存在使得数据更易于高效操作和分析。

数据结构

数据结构是数据及其关系的抽象表示，包含数据元素、逻辑关系及操作规则。它是计算机存储、组织数据的方式，直接影响程序的效率和复杂度。常见数据结构包括：

  • 线性结构：数组、链表、栈、队列。
  • 非线性结构：树、图、堆、哈希表。

数据结构的选择需结合具体问题，平衡时间（操作速度）和空间（内存占用）复杂度。例如，频繁搜索用哈希表，动态增删用链表，分层管理用树。

线性表的概念

线性表是一种逻辑结构，由具有相同数据类型的有限序列组成。元素之间存在顺序关系，除首尾元素外，每个元素有且仅有一个直接前驱和一个直接后继。线性表的操作通常包括插入、删除、查找、修改等。

顺序表的定义

顺序表是线性表的物理实现方式之一，采用连续的存储空间存放元素。其特点是逻辑上相邻的元素在物理存储上也相邻，支持随机访问（通过下标直接定位元素）。

顺序表的特点

  • 优点：访问速度快（时间复杂度O(1)）；存储密度高（无需额外空间存储关系）。
  • 缺点：插入和删除需移动大量元素（时间复杂度O(n)）；预分配固定空间可能导致浪费或溢出。

顺序表的基本操作

以伪代码描述核心逻辑（避免具体编程语言语法）：

  1. 插入操作
    检查位置合法性后，从末尾向前循环移动元素腾出空位，插入新元素并更新长度。

    for i = length-1 downto pos  data[i+1] = data[i]  
data[pos] = new_element  
length++

  2. 删除操作
    检查位置合法性后，从前向后循环覆盖待删除元素并更新长度。

    removed = data[pos]  
for i = pos to length-2  data[i] = data[i+1]  
length--  
return removed

  3. 查找操作
    遍历顺序表，返回匹配元素的下标或状态。

    for i = 0 to length-1  if data[i] == target  return i  
return -1

复杂度对比

  • 访问：O(1)
  • 插入/删除：平均O(n)
  • 查找：无序时O(n)，有序时可通过二分法优化至O(log n)。

 作业：

1.顺序表的增删改查、排序、输出和去重等一系列操作以及Makefile的使用。

#include "sqelist.h"int main(int argc, const char *argv[])
{//定义循环变量int i;//定义顺序表结构体指针sqelistptr slptr=NULL;//调用顺序表堆区空间申请函数slptr=SqeListCreate();//需要插入的数据定义datatype nwedata;//循环输入要插入的数for(i=0;i<MAX;i++){puts("请输入一个数：");scanf(" %d",&nwedata);//调用尾插函数插入数据SqeListInsertrear(slptr,nwedata);}//调用顺序表输出函数SqeListOutput(slptr);//调用顺序表尾部删除函数SqeListDeleterear(slptr);//调用顺序表输出函数SqeListOutput(slptr);//下标变量定义及输入int indenx;puts("请输入想查找的下标：");scanf(" %d",&indenx);//调用按下标查找函数SqeListIdenxsift(slptr,indenx);//输入下标及数据puts("请输入想修改数据的下标：");scanf(" %d",&indenx);puts("请输入想要修改数：");scanf(" %d",&nwedata);//调用按下标修改SqeListIdenxalter(slptr,indenx,nwedata);//调用顺序表输出函数SqeListOutput(slptr);//输入下标puts("请输入想删除数据的下标：");scanf(" %d",&indenx);//调用按下标删除函数SqeListIdenxdelete(slptr,indenx);//调用顺序表输出函数SqeListOutput(slptr);//输入下标及数据puts("请输入想插入数据的下标：");scanf(" %d",&indenx);puts("请输入想要插入数：");scanf(" %d",&nwedata);//调用按下标插入函数SqeListIdenxinsert(slptr,indenx,nwedata);//调用顺序表输出函数SqeListOutput(slptr);//需要删除的数据定义datatype olddata;puts("请输入想要删除的数：");scanf(" %d",&olddata);//调用按数据删除函数SqeListDatadelete(slptr,olddata);//调用顺序表输出函数SqeListOutput(slptr);//需要删除的数据定义puts("请输入想要更改的数：");scanf(" %d",&olddata);puts("请输入想要更改为的数：");scanf(" %d",&nwedata);//调用按数剧更改函数SqeListDataalter(slptr,olddata,nwedata);//调用顺序表输出函数SqeListOutput(slptr);//调用顺序表去重函数SqeListUnique(slptr);//调用顺序表输出函数SqeListOutput(slptr);//调用顺序表排序函数SqeListSort(slptr);//调用顺序表输出函数SqeListOutput(slptr);//调用顺序表内存释放函数slptr=SqeListFree(slptr);return SUCCES;
}

#ifndef _SQELIST_H__
#define _SQELIST_H__//宏定义顺序表最大容量
#define MAX  5#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>//返回常量
enum returntype
{FALUSE=-1,SUCCES
};//重定义顺序表数据元素数据类型
typedef int datatype;//顺序表结构体定义
typedef struct
{//数据元素datatype data[MAX];//顺序表长度int len;
}sqelist,*sqelistptr;//顺序表堆区空间申请函数
sqelistptr SqeListCreate(void);//顺序表尾部插入函数
int SqeListInsertrear(sqelistptr slptr,datatype nwedata);//顺序表输出函数
int SqeListOutput(sqelistptr slptr);//顺序表尾部删除函数
int SqeListDeleterear(sqelistptr slptr);//按下标查找函数
int SqeListIdenxsift(sqelistptr slptr,int indenx);//按下标更改函数
int SqeListIdenxalter(sqelistptr slptr,int indenx,datatype nwedata);//按下标删除函数
int SqeListIdenxdelete(sqelistptr slptr,int indenx);//按下标插入函数
int SqeListIdenxinsert(sqelistptr slptr,int indenx,datatype nwedata);//按数据查找函数
int SqeListDatasift(sqelistptr slptr,datatype olddata);//按数据删除函数
int SqeListDatadelete(sqelistptr slptr,datatype olddata);//按数据修改函数
int SqeListDataalter(sqelistptr slptr,datatype olddata,datatype nwedata);//顺序表去重函数
int SqeListUnique(sqelistptr slptr);//顺序表排序函数
int SqeListSort(sqelistptr slptr);//顺序表内存释放函数
sqelistptr SqeListFree(sqelistptr slptr);#endif
#include "sqelist.h"//顺序表堆区空间申请函数
sqelistptr SqeListCreate(void)
{//malloc申请堆区空间sqelistptr slptr=(sqelistptr)malloc(sizeof(sqelist)*MAX);//判断申请是否成功if(slptr==NULL)return NULL;//申请成功，空间置零bzero(slptr->data,sizeof(slptr->data));slptr->len=0;//返回申请的空间地址return slptr;
}//顺序表尾部插入函数
int SqeListInsertrear(sqelistptr slptr,datatype nwedata)
{//判断空间是否申请空间是否成功//判断顺序表是否为满if(slptr==NULL||slptr->len==MAX){return FALUSE;//失败返回-1}//有空间且值不满//尾插入数据slptr->data[slptr->len]=nwedata;slptr->len++;return SUCCES;//成功返回0
}//顺序表输出函数
int SqeListOutput(sqelistptr slptr)
{int i;//循环变量//判断空间是否申请空间是否成功//判断顺序表是否为空if(slptr==NULL||slptr->len==0){return FALUSE;//失败返回-1}//有空间且不为空//循环输出puts("现有数据为：");for(i=0;i<slptr->len;i++){printf("%d\t",slptr->data[i]);}putchar(10);return SUCCES;//成功返回0
}//
int SqeListDeleterear(sqelistptr slptr)
{//判断空间是否申请空间是否成功//判断顺序表是否为空if(slptr==NULL||slptr->len==0){return FALUSE;//失败返回-1}//有空间且不为空//直接len--删除slptr->len--;return SUCCES;//成功返回0
}int SqeListIdenxsift(sqelistptr slptr,int indenx)
{//判断空间是否申请空间是否成功//判断顺序表是否为空//判断indenx是否合法if(slptr==NULL || slptr->len==0 || indenx<0 || indenx>slptr->len){return FALUSE;}//按下标输出printf("data[%d]=%d\n",indenx,slptr->data[indenx]);return SUCCES;
}//按下标更改函数
int SqeListIdenxalter(sqelistptr slptr,int indenx,datatype nwedata)
{//判断空间是否申请空间是否成功//判断顺序表是否为空//判断indenx是否合法if(slptr==NULL || slptr->len==0 || indenx<0 || indenx>=slptr->len){return FALUSE;}//按下标修改slptr->data[indenx]=nwedata;return SUCCES;
}//按下标删除函数
int SqeListIdenxdelete(sqelistptr slptr,int indenx)
{int i;//判断空间是否申请空间是否成功//判断顺序表是否为空//判断indenx是否合法if(slptr==NULL || slptr->len==0 || indenx<0 || indenx>=slptr->len){return FALUSE;}//判断是否为最后一个元素if(indenx==slptr->len-1){//若为最后一个直接len--尾删slptr->len--;}else{//否则从下标位置开始向前移一位for(i=indenx;i<slptr->len;i++){slptr->data[i]=slptr->data[i+1];}slptr->len--;}return SUCCES;
}//按下标插入函数
int SqeListIdenxinsert(sqelistptr slptr,int indenx,datatype nwedata)
{//循环变量int i;//判断空间是否申请空间是否成功//判断顺序表是否为满//判断indenx是否合法if(slptr==NULL || slptr->len==MAX || indenx<0 || indenx>slptr->len){return FALUSE;}//循环后移indenx开始的数据for(i=slptr->len-1;i>=indenx;i--){slptr->data[i+1]=slptr->data[i];}//插入数据slptr->data[indenx]=nwedata;//增加长度slptr->len++;return SUCCES;
}//按数据查找函数
int SqeListDatasift(sqelistptr slptr,datatype olddata)
{int i;//判断空间是否申请空间是否成功//判断顺序表是否为空if(slptr==NULL||slptr->len==0){return FALUSE;//失败返回-1}//查找数据下标for(i=0;i<slptr->len;i++){if(slptr->data[i]==olddata)break;}//判断是否找到数据下标if(i==slptr->len){return FALUSE;}return i;
}//按数据删除函数
int SqeListDatadelete(sqelistptr slptr,datatype olddata)
{int i;//调用按数据查找函数i=SqeListDatasift(slptr,olddata);if(i==-1){return FALUSE;}//调用按下标删除函数SqeListIdenxdelete(slptr,i);return SUCCES;
}//按数据修改函数
int SqeListDataalter(sqelistptr slptr,datatype olddata,datatype nwedata)
{int i;//调用按数据查找函数i=SqeListDatasift(slptr,olddata);if(i==-1){return FALUSE;}//调用按下标更改函数SqeListIdenxalter(slptr,i,nwedata);return SUCCES;
}//顺序表去重函数
int SqeListUnique(sqelistptr slptr)
{int i,j;//判断空间是否申请空间是否成功//判断顺序表是否为空if(slptr==NULL||slptr->len==0){return FALUSE;//失败返回-1}for(i=0;i<slptr->len;i++){for(j=i+1;j<slptr->len;j++){if(slptr->data[j]==slptr->data[i]){//调用按下标删除函数SqeListIdenxdelete(slptr,j);j--;}}}return SUCCES;
}//顺序表排序函数
int SqeListSort(sqelistptr slptr)
{int i,j;datatype temp;//判断空间是否申请空间是否成功//判断顺序表是否为空if(slptr==NULL||slptr->len==0){return FALUSE;//失败返回-1}//冒泡排序for(i=0;i<slptr->len-1;i++)for(j=0;j<slptr->len-i-1;j++)if(slptr->data[j]<slptr->data[j+1]){temp=slptr->data[j];slptr->data[j]=slptr->data[j+1];slptr->data[j+1]=temp;}return SUCCES;
}//顺序表内存释放函数
sqelistptr SqeListFree(sqelistptr slptr)
{free(slptr);return NULL;
}
#********************变量*******************#最后的可执行文件
EXE=main#源文件生成的二进制文件
OBJES=$(patsubst %.c,%.o,$(wildcard ./*.c))#常见与定义变量gcc
CC=gcc#常见预定义变量编译器选项
CFLAGS=-c -o#********************规则*******************#执行规则的头规则
all:$(EXE)#第一个规则
#将二进制文件生成可执行文件
$(EXE):$(OBJES)$(CC) $^ -o $@#第二个规则
#将源文件生成二进制文件
%.o:%.c$(CC) $(CFLAGS) $@ $^#清除规则
#清除生成的二进制文件和可执行文件
clean:rm $(OBJES) $(EXE)

 2.牛客网刷题

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

相关文章：

  • GitHub 上的开源项目 ticktick（滴答清单）
  • Kotlin伴生对象
  • Kotlin 作用域函数 let 的实现原理
  • 什么是检索增强生成（RAG）？
  • 深入浅出控制反转与依赖注入：从理论到实践
  • 社交电商推客系统全栈开发指南：SpringCloud+分润算法+Flutter跨端
  • 深度学习篇---车道线循迹
  • CMake实践：CMake3.30版本之前和之后链接boost的方式差异
  • Pulsar存储计算分离架构设计之Broker无状态
  • linux: tar解压之后属主和属组不是当前用户问题
  • [c++11]constexpr
  • MCP消息协议和传输协议（Java角度）
  • 【数学建模|Matlab】Matlab「基础知识」和「基础操作」
  • es搜索实现既能模糊查询又能分词查询
  • Linux部署.net Core 环境
  • 8.4 Java 原生 TCP Socket 实现 HTTP 请求解析和请求分发
  • Dify接入MCP案例1：基于Chatflow旅行、吃饭、新闻、学习的AI智能体
  • 公司内部网址怎么在外网打开？如何让外网访问内网的网站呢？
  • 2025 年非关系型数据库全面指南：类型、优势
  • cddlib(用于凸多面体计算和线性不等式系统求解)的开源库
  • JAVA API (三)：从基础爬虫构建到带条件数据提取 —— 详解 URL、正则与爬取策略
  • Java 大视界 -- Java 大数据在智能交通自动驾驶车辆与周边环境信息融合与决策中的应用（357）
  • JMeter 实现 Protobuf 加密解密
  • UE5 UI 水平框
  • ansible 批量 scp 和 load 镜像
  • MybatisPlus-16.扩展功能-枚举处理器
  • Windows PE文件内未用空间学习
  • DNS应用层协议
  • Linux驱动-中断-共享队列
  • 两个android，一个客户端一个服务器端