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

自学嵌入式 day 18 - 数据结构 1

backend 2025/5/16 8:24:11

数据结构

相互之间存在一种或多种特定关系的数据元素的集合

1.特定关系：

（1）逻辑结构：

①集合：所有在同一个集合中，关系平等。

②线性关系：数据和数据之间是一对一的关系。（数组是线性表的形式之一）

③树状关系：一对多

④图状解构：多对多

（2）物理结构（在内存当中的存储关系，即将上述关系存入内存）：

①顺序存储：数据存放在连续的存储单位中。逻辑关系和物理关系一致

②链式结构（链表）：数据存放的单位是随机或任意的

Struct Per 数据元素

{

char name;

int age;

char phone;

}

程序 = 数据 + 算法

2.算法：

①定义：是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。

②特征（函数）：

1），输入，输出特性，输入时可选的，输出时必须的。
2），有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
3），确定性，同一个输入，会得到唯一的输出。
4），可行性，每一个步骤都是可以实现的。

③设计：

1），正确性：语法正确
合法的输入能得到合理的结果。
对非法的输入，给出满足要求的规格说明
对精心选择，甚至刁难的测试都能正常运行，结果正确
2），可读性，便于交流，阅读，理解
3），健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4），高效，存储低，效率高

④算法时间复杂度：执行算法所时间的度量，o（n）-粗略的估计

1）推算:   用常数1 取代运行时间中的所有加法常数
                在修改后的运行函数中，只保留最高阶项。
                如果最高阶存在且不是1，则取除这个项相乘的常数。

3.线代表

①定义：零个或多个数据元素的有限序列
②特征：元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有一个前驱和一个后继。
当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

③线代表的常规操作：

线性表的常规操作 ADT
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef int Datatype;
typedef struct list {
DATATYPE *head;
int tlen;
int clen;
}SeqList;

SeqList *CreateSeqList(int len);//创建顺序链表
int DestroySeqList(SeqList *list);//销毁链表
int ShowSeqList(SeqList *list);//遍历输出链表
int InsertTailSeqList(SeqList *list, DATATYPE data);//尾部元素赋值
int IsFullSeqList(SeqList *list);//判断链表是否已满
int IsEmptySeqList(SeqList *list);//判断链表是否为空
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);//指定位置插入元素
int FindSeqList(SeqList *list, char *name);//查找元素
int ModifySeqList(SeqList *list, char *old, DATATYPE new);//修改成员值
int DeleteSeqList(SeqList *list, char *name);//删除成员
int ClearSeqList(SeqList *list);//清空元素

④上述操作代码表示:

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
SeqList *CreateSeqList (int len)//创建顺序链表
{
SeqList *sl = malloc (sizeof (SeqList));
if (NULL == sl) {
fprintf (stderr, "CreateSeqList malloc error\n");
return NULL;
}

sl->head = malloc (sizeof (DATATYPE) * len);
if (NULL == sl->head) {
fprintf (stderr, "CreateSeqList malloc2 error\n");
return NULL;
}
sl->tlen = len;
sl->clen = 0;

return sl;
}

int IsFullSeqList (SeqList *list)//判断链表是否已满
{
if (NULL == list) {
fprintf (stderr, "IsFullSeqList paramter error\n");
return 1;
}
return list->clen == list->tlen;
}

int InsertTailSeqList (SeqList *list, DATATYPE *data)//尾部元素赋值
{
if (IsFullSeqList (list)) {
fprintf (stderr, "seqlist full\n");
return 1;
}

memcpy (&list->head[list->clen], data, sizeof (DATATYPE));
list->clen++;
return 0;
}

int ShowSeqList (SeqList *list)//遍历输出链表
{
int len = GetSizeSeqList (list);
int i = 0;
for (i = 0; i < len; ++i)
{
printf ("%s %c %d %d\n", list->head[i].name, list->head[i].sex,
list->head[i].age, list->head[i].score);
}
return 0;
}

int GetSizeSeqList (SeqList *list)
{
return list->clen;

}

int FindSeqlist(SeqList *list,char *name)//查找元素
{
int i = 0;
int len = GetSizeSeqList(list);
for(i = 0;i < len;++i)
{
if(0 == strcmp(list -> head[i].name,name))
{
return i;
}

}
return -1;
}
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)//指定位插入元素
{
if(IsFullSeqList(list))
{
return 1;
}
int len = GetSizeSeqList(list);
if(pos < 0 || len < pos)
{
   return 1;
}
int i ;
for(i = list -> clen;i > pos;--i)
{
   memcpy(&list -> head[i],&list -> head[i - 1],sizeof(DATATYPE));
}
memcpy(&list -> head[pos],data,sizeof(DATATYPE));
list -> clen++;
return 0;
}

int IsEmpList(SeqList *list)//判断链表是否为空
{
   return 0 == list -> clen;
}

int DeleteSeqList(SeqList *list,char *name)//删除链表
{
   if(IsEmpList(list))
   {
       return 1;
   }
   int ret = FindSeqlist(list,name);
   if(-1 == ret)
   {
       return 1;
   }
   int len = GetSizeSeqList(list);
   int i ;
   for(i = ret;i < len - 1;++i)
   {
       memcpy(&list -> head[i],&list -> head[i + 1],sizeof(DATATYPE));
   }
   list -> clen--;
   return 0
｝