Linux嵌入式学习——数据结构——概念和Seqlist

🕗 发布于 2024-07-24 20:16 算法

数据结构

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

逻辑结构

集合，所有数据在同一个集合中，关系平等。

线性，数据和数据之间是一对一的关系。数组就是线性表的一种。

树，一对多

图，多对多可能用在地图里a

物理结构(在内存当中的存储关系)

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

链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续。

struct Per 数据元素
   {
       char name;// 数据项--》给数据赋予一定的意义
       int age;
       char phone;
   }

   struct Per list[100]; //数据对象

结构体集合

数据的类型，ADT abstruct datatype 抽象数据类型
       是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
       原子类型，int，char，float
       结构类型，sturct， union，

       抽象数据类型，数学模型 + 操作。

       程序 = 数据 + 算法

算法，

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

算法的特征，

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

算法的设计，

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

算法时间效率度量

（1）可以忽略加法常数

O(2n + 3) = O(2n)
（2）与最高次项相乘的常数可忽略

O(2n^2) = O(n^2)
（3）最高次项的指数大的，函数随着 n 的增长，结果也会变得增长得更快

O(n^3) > O(n^2)
（4）判断一个算法的（时间）效率时，函数中常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

O(2n^2) = O(n^2+3n+1)
O(n^3) > O(n^2

算法时间复杂度

也就是执行这个算法所花时间的度量
n 1 = O(n) O(1)

推到时间复杂度

1，用常数1 取代运行时间中的所有加法常数

2，在修改后的运行函数中，只保留最高阶项。

3，如果最高阶存在且不是1，则取除这个项相乘的常数。

3.举例：

int i,j;
for ( i = 0; i < n; ++i){
for(j = i; j < n; ++j){
/*时间复杂度为 O(1) 的程序步骤序列 */
}
}

for(i=0;i<n;i++)
       {
           i=5*i;
       }

       for()n
       {
           for()n
       }
       O(1)<O(logn)<O(N)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)



       for(int i = 0 ;i<100; i = *5)
       {

       }

线性表

一.定义

零个或多个数据元素的有限序列
   元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有一个前驱和一个后继。
   当线性表元素的个数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;

1. `SeqList *CreateSeqList(int len);`

功能：创建一个长度为len的顺序表。
实现思路：
- 动态分配一个足够大的内存空间（通常是len个元素加上一个可能的头部或尾部用于管理信息，如记录当前长度）。
- 初始化顺序表的长度、容量等信息。
- 返回指向新创建的顺序表的指针。

2. `int DestroySeqList(SeqList *list);`

功能：销毁顺序表，释放其占用的内存。
实现思路：
- 释放顺序表所占用的内存。
- 将指针置为NULL，避免野指针问题。
- 返回成功或失败的状态码。

3. `int ShowSeqList(SeqList *list);`

功能：显示顺序表中的所有元素。
实现思路：
- 遍历顺序表，依次打印每个元素。
- 返回成功或失败的状态码（通常是成功）。

4. `int InsertTailSeqList(SeqList *list, DATATYPE data);`

功能：在顺序表的尾部插入一个元素。
实现思路：
- 检查顺序表是否已满。
- 如果未满，将新元素插入到顺序表的末尾，并更新长度信息。
- 如果已满，可能需要扩容。
- 返回成功或失败的状态码。

5. `int IsFullSeqList(SeqList *list);`

功能：判断顺序表是否已满。
实现思路：
- 比较顺序表的当前长度与容量。
- 如果长度等于容量，返回true（或1），否则返回false（或0）。

6. `int IsEmptySeqList(SeqList *list);`

功能：判断顺序表是否为空。
实现思路：
- 检查顺序表的当前长度是否为0。
- 如果是，返回true（或1），否则返回false（或0）。

7. `int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);`

功能：在顺序表的指定位置pos插入一个元素。
实现思路：
- 检查位置pos是否有效（即在0到长度之间）。
- 如果有效，将pos及其之后的所有元素向后移动一位，为新元素腾出空间。
- 在pos位置插入新元素，并更新长度信息。
- 如果顺序表已满，可能需要扩容。
- 返回成功或失败的状态码。

8. `int FindSeqList(SeqList list, char name);`

注意：这里假设顺序表存储的是某种具有名称的对象，且DATATYPE可能不是直接相关的。这个函数的具体实现取决于SeqList和DATATYPE的具体定义。
功能：在顺序表中查找具有指定名称的元素。
实现思路：
- 遍历顺序表，检查每个元素的名称是否与name匹配。
- 如果找到匹配项，返回其位置（或某种表示找到的信息）。
- 如果遍历结束仍未找到，返回未找到的信息。

9. `int ModifySeqList(SeqList list, char old, DATATYPE new);`

注意：与FindSeqList类似，这里也假设顺序表存储的是具有名称的对象。
功能：将顺序表中名称与old匹配的元素替换为新的值new。
实现思路：
- 遍历顺序表，找到名称与old匹配的元素。
- 如果找到，将其替换为new。
- 返回成功或失败的状态码（或修改的元素数量）。

10. `int DeleteSeqList(SeqList list, char name);`

功能：从顺序表中删除名称与name匹配的元素。
实现思路：
- 遍历顺序表，找到名称与name匹配的元素。
- 如果找到，将该元素之后的所有元素向前移动一位，以覆盖被删除的元素。
- 更新顺序表的长度信息。
- 返回成功

11.清楚顺序表。

示例代码：

sqelist.h

#ifndef SEQLIST_H
#define SEQLIST_H


typedef struct{
    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 size);
int DestroySeqList(SeqList*sl);
int InsertTailSeqList(SeqList *list, DATATYPE *data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int ShowSeqList(SeqList* list);
int GetSizeSeqList(SeqList* list);
int FindSeqList(SeqList *list, char *name);
DATATYPE* GetSeqListItem(SeqList *list,int ind);
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos);
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata);
int DeleteSeqList(SeqList *list, char *name);
int ClearSeqList(SeqList *list);
#endif // SEQLIST_H

seqlist.c

#include "seqlist.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
SeqList *CreateSeqList(int size)
{
    if(size<=0)
    {
        fprintf(stderr,"size is error,range >1");
        return NULL;
    }
    SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));
    if(NULL == sl)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }

    sl->head = (DATATYPE*)malloc(sizeof(DATATYPE)*size);
    if(NULL == sl->head)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }

    sl->tlen = size;
    sl->clen = 0;
    return sl;
}


int DestroySeqList(SeqList *sl)
{
    if(NULL == sl)
    {
        fprintf(stderr,"SeqList point not NULL");
        return 1;
    }
    if(sl->head)
        free(sl->head);
    free(sl);
    return 0;
}

int InsertTailSeqList(SeqList *list, DATATYPE *data)
{
    if(NULL == list)
    {
        fprintf(stderr,"InsertTailSeqList error,list is null\n");
        return -1;
    }

    if(IsFullSeqList(list))
    {
        fprintf(stderr,"InsertTailSeqList error ,seqlist is full\n");
        return 1;
    }
    //list->head[list->clen] = *data;
    memcpy(&list->head[list->clen] , data,sizeof(DATATYPE));
    list->clen++;
    return 0;
}

int IsFullSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"IsFullSeqList error,list is null\n");
        return -1;
    }
    return list->clen == list->tlen;
}

int IsEmptySeqList(SeqList *list)
{
    return 0==list->clen;
}

int ShowSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"list error,list is null\n");
        return -1;
    }
    int i = 0 ;
    int len = GetSizeSeqList(list);
    for(i=0;i<len;i++)
    {
        printf("name:%s sex:%c age:%d score:%d\n",list->head[i].name,list->head[i].sex,list->head[i].age
               ,list->head[i].score);
    }
    return 0;
}

int GetSizeSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"GetSizeSeqList error,list is null\n");
        return -1;
    }
    return list->clen;
}

int FindSeqList(SeqList *list, char *name)
{
    if(NULL == list)
    {
        fprintf(stderr,"FindSeqList error,list is null\n");
        return 1;
    }
    if(IsEmptySeqList(list))
    {
        fprintf(stderr,"FindSeqList error,seqlist is empty\n");
        return -1;
    }
    int len = GetSizeSeqList(list);
    int i = 0 ;
    for(i=0;i<len;i++)
    {
        if(0==strcmp(list->head[i].name,name))
        {

            return i;
        }
    }
    return -1;

}

DATATYPE *GetSeqListItem(SeqList *list, int ind)
{
    if(NULL == list)
    {
        fprintf(stderr,"seqlist is NULL\n");
        return NULL;
    }
    if(ind<0 || ind>GetSizeSeqList(list))
    {
        fprintf(stderr,"index is error . range>0  && <size\n");
        return NULL;

    }
    return &list->head[ind];
}

int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{

    if(NULL == list)
    {
        fprintf(stderr,"list is null\n");
        return 1;
    }
    if(IsFullSeqList(list))
    {
        fprintf(stderr,"list is full\n");
        return 1;
    }
    if(pos<0 ||pos>GetSizeSeqList(list))
    {
        fprintf(stderr,"pos is error\n");
        return 1;
    }

    int i = 0 ;

    for(i =GetSizeSeqList(list); 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 ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{
    if(NULL == list)
    {
        fprintf(stderr,"ModifySeqList error,list is null\n");
        return 1;
    }
    int ret = FindSeqList(list,old);
    if(-1 == ret)
    {
        fprintf(stderr,"modify error,can't find\n");
        return 1;
    }
    DATATYPE* tmp = GetSeqListItem(list,ret);
    memcpy(tmp,newdata,sizeof(DATATYPE));
    return 0;
}

int DeleteSeqList(SeqList *list, char *name)
{
    if(NULL == list)
    {
        fprintf(stderr,"DeleteSeqList error,list is null\n");
        return 1;
    }
    int ret = FindSeqList(list,name);
    if(-1 == ret)
    {
        return 1;
    }
    else
    {
        int i = 0 ;
        for(i =ret; i <GetSizeSeqList(list)-1 ; i++)
        {
            memcpy(&list->head[i] ,&list->head[i+1],sizeof(DATATYPE));
        }
    }

    list->clen--;
    return 0 ;
}

int CleanSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"CleanSeqList error,list is null\n");
        return 1;
    }
    list->clen = 0 ;
    return 0;

}

main.c

#include <stdio.h>
#include "seqlist.h"
int main()
{
    SeqList* sl = CreateSeqList(10);

    DATATYPE data[5]={
        {"zhangsan",'m',20,70},
        {"lisi",'f',21,60},
        {"wangmazi",'m',25,80},
        {"liubei",'f',30,85},
        {"caocao",'f',40,90},
    };
    InsertTailSeqList(sl,&data[0]);
    InsertTailSeqList(sl,&data[1]);
    InsertTailSeqList(sl,&data[2]);


    ShowSeqList(sl);
    //    char find_name[50]="li1si";
    //    int ret = FindSeqList(sl,find_name);
    //    if(-1 == ret)
    //    {
    //        printf("can't find person ,%s\n",find_name);
    //    }
    //    else
    //    {
    //       DATATYPE* tmp   =  GetSeqListItem(sl,ret) ;
    //       printf("name:%s score:%d\n",tmp->name,tmp->score);
    //    }
    printf("----------------pos------------------\n");
    InsertPosSeqList(sl,&data[3],3);
    ShowSeqList(sl);
    printf("----------------modify------------------\n");
    ModifySeqList(sl,"li1si",&data[4]);
    ShowSeqList(sl);
    printf("----------------del------------------\n");
    DeleteSeqList(sl,"lisi");
    ShowSeqList(sl);
    DestroySeqList(sl);
    printf("Hello World!\n");
    return 0;
}

内存泄露检测工具
sudo apt-get install valgrind
valgrind ./all

char buf[1024];

练习：

1.把dict.txt 内容放到顺序表中。
提供查询功能。找到了，显示意思。
如果没找到，显示输入错误。
#quit ，退出程序。

dict.h

#ifndef DICT_H
#define DICT_H

typedef struct
{
    char word[20];
    char meaning[1022];
    int ret;
}MSG;

typedef struct list
{
   MSG *head;
    int tlen;
    int clen;
}SeqList;

SeqList* CreateSeqList(int size);
int DestroySeqList(SeqList *sl);
int InsertTailSeqList(SeqList *list, MSG*data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int ShowSeqList(SeqList* list);
int GetSizeSeqList(SeqList* list);
int FindSeqList(SeqList *list, char *name);
MSG* GetSeqListItem(SeqList *list,int ind);

#endif // DICT_H

dict.c

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

SeqList *CreateSeqList(int size)
{
    if(size<=0)
    {
        fprintf(stderr,"size is error,range >1");
        return NULL;
    }
    SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));
    if(NULL == sl)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }

    sl->head = (MSG*)malloc(sizeof(MSG)*size);
    if(NULL == sl->head)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }

    sl->tlen = size;
    sl->clen = 0;
    return sl;
}


int DestroySeqList(SeqList *sl)
{
    if(NULL == sl)
    {
        fprintf(stderr,"SeqList point not NULL");
        return 1;
    }
    if(sl->head)
        free(sl->head);
    free(sl);
    return 0;
}

int InsertTailSeqList(SeqList *list, MSG*msg)
{
    if(IsFullSeqList(list))
    {
        fprintf(stderr,"InsertTailSeqlist error,seqlist is full\n");
        return -1;
    }
    memcpy(&list->head[list->clen],msg,sizeof(MSG));
    list->clen++;
    return 0;
}
int IsFullSeqList(SeqList *list)
{
    return list->clen == list->tlen;
}

int IsEmptySeqList(SeqList *list)
{
    return 0==list->clen;
}
int GetSizeSeqList(SeqList *list)
{
    return list->clen;
}

int FindSeqList(SeqList *list, char *word)
{
    if(IsEmptySeqList(list))
    {
         fprintf(stderr,"FindSeqList error,seqlist is empty\n");
        return -1;
    }
    int len = GetSizeSeqList(list);
    int i = 0 ;
    for(i=0;i<len;i++)
    {
        if(0==strcmp(list->head[i].word,word))
{
            return i;
 }

    }
   return -1;
 }
MSG *GetSeqListItem(SeqList *list, int ind)
{
    if(NULL == list)
    {
        fprintf(stderr,"seqlist is NULL\n");
        return NULL;
    }
    if(ind<0 || ind>GetSizeSeqList(list))
    {
        fprintf(stderr,"index is error . range>0  && <size\n");
        return NULL;

    }
    return &list->head[ind];
}

main.c

#include <stdio.h>
#include <string.h>
#include "dict.h"
#include <fcntl.h>
#include <stdlib.h>
int main()
{
    SeqList* sl = CreateSeqList(20000);
    MSG msg[2000];
    FILE *fp=fopen("/home/linux/cpz/dict.txt","r");
    if(NULL==fp)
    {
        perror(" ");
        exit(1);
    }
    while(1)
    {
        bzero(&msg,sizeof(msg));
        int i=0;
      char buf[1024]={0};

        if(NULL==fgets(buf,sizeof(buf),fp))
        {
            break;
        }
        char *word = NULL;
        char *mean = NULL;
        word=strtok(buf," ");
        mean=strtok(NULL,"\r");
        strcpy(msg[i].word,word);
        strcpy(msg[i].meaning,mean);
        InsertTailSeqList(sl,&msg[i]);
    }
    while(1)
    {
    char find_word[50]={0};
    fgets(find_word,sizeof(find_word),stdin);
 find_word[strlen(find_word)-1]='\0';
 if(0==strcmp(find_word,"#quilt"))
 {
     break;
 }
    int ret = FindSeqList(sl,find_word);
    if(-1 == ret)
    {
        printf("can't find word ,%s\n",find_word);
    }
    else
    {
        MSG* tmp   =  GetSeqListItem(sl,ret) ;
        printf("word:%s mean:%s\n",tmp->word,tmp->meaning);
    }
}

        printf("Hello World!\n");
    return 0;
}

线性表顺序存储的优点，缺点

优点
   1，无需为表中的逻辑关系增加额外的存储空间
   2，可以快速随机访问元素O(1)
缺点
   1，插入，删除元素需要移动元素o(n)
   2，无法动态存储。

优点：

随机访问：顺序表支持随机访问，即可以通过下标快速访问表中的任意元素，访问时间复杂度为O(1)。
存储密度高：顺序表在物理存储上是连续的，因此它的存储密度高，不会出现为了存储数据元素而额外申请大量空间的情况（相较于链表等数据结构）。
空间利用率高：在顺序表扩容之前，其空间是固定的，这有助于减少空间碎片，提高空间利用率。
易于实现：顺序表的基本操作（如插入、删除、查找等）相对简单，易于理解和实现。

缺点：

插入和删除操作成本高：当在顺序表中进行插入或删除操作时，可能需要移动大量的元素以保持顺序表的连续性，特别是在表的前端或中间位置进行操作时，时间复杂度较高，最坏情况下为O(n)。
空间分配问题：顺序表在初始化时需要预先分配一定大小的存储空间，如果预估不准确，可能会导致空间浪费（分配过多）或溢出（分配不足）。虽然可以通过动态扩容来解决溢出问题，但每次扩容都需要重新分配内存并复制数据，增加了时间成本。
扩容问题：当顺序表需要扩容时，虽然可以动态申请更大的内存空间，但这个过程涉及到旧数据的复制和新空间的申请，可能会影响到程序的性能。
表的大小固定：虽然可以通过动态扩容来解决表大小固定的问题，但在某些场景下，如果需要存储的数据量非常大，而内存空间有限，那么顺序表可能就不是一个很好的选择。

原文地址：https://blog.csdn.net/m0_71703182/article/details/140600197

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：「Ant Design」Antd 中卡片如何完全不展示内容区域、按需展示内容区域、不展示标题
下一篇：pikachu 之CSRF（跨站请求伪造）get和post型

【图像压缩感知】论文阅读：Self-supervised Scalable Deep Compressed Sensing
本文为个人阅读论文的笔记，仅作为学习记录所用。
阅读更多2024-11-10
kafka-clients之ProducerConfig
在Kafka2.4.0版本中，类提供了许多配置参数，用于控制生产者行为。这些参数可以调整Kafka生产者的性能、可靠性和行为。
阅读更多2024-11-10
Redhat8.6安装MySQL8.0.31
Redhat8.6安装MySQL8.0.31
阅读更多2024-11-10
python实战（七）——基于LangChain的RAG实践
本文详细介绍了使用LangChain构建RAG程序的各个流程，并给出了对应的python实现代码。
阅读更多2024-11-10
Jmeter中的线程
假设我们需要测试一个Web应用，模拟100个用户并发访问，并且每个用户在执行每个样本之间有随机的延迟时间。假设我们需要测试一个Web应用，模拟100个用户并发访问，并且每个用户执行测试脚本10次。假设
阅读更多2024-11-10
自动化爬虫DrissionPage
自动化爬虫DrissionPage
阅读更多2024-11-10
【软件工程】ATAM架构权衡评估方法
ATAM（Architecture Tradeoff Analysis Method）是一种系统架构评估方法，由卡梅隆大学软件工程协会提出。它主要用于在系统开发之前，对性能、可用性、安全性和可修改性等
阅读更多2024-11-10
【JavaEE进阶】HTML
HTML(Hyper Text Markup Language), 超⽂本标记语⾔.超⽂本:⽐⽂本要强⼤. 通过链接和交互式⽅式来组织和呈现信息的⽂本形式. 不仅仅有⽂本, 还可能包含图⽚, ⾳频,
阅读更多2024-11-10
nodejs 020: React语法规则 props和state
在 React 中，和是管理数据流的两种核心机制。理解它们之间的区别和用途是构建 React 应用程序的基础。
阅读更多2024-11-10
Conpair: 配对样本一致性concordance与污染contamination分析
Conpair 于2016年被发表在《Bioinformatics》上，用于分析配对样本（如某个病人的肿瘤样本和正常样本）WGS或WES测序的一致性和交叉个体污染。
阅读更多2024-11-10

Linux嵌入式学习——数据结构——概念和Seqlist

数据结构

逻辑结构

物理结构(在内存当中的存储关系)

算法，

算法的特征，

算法的设计，

算法时间效率度量

算法时间复杂度

3.举例：

线性表

一.定义

1. SeqList *CreateSeqList(int len);

2. int DestroySeqList(SeqList *list);

3. int ShowSeqList(SeqList *list);

4. int InsertTailSeqList(SeqList *list, DATATYPE data);

5. int IsFullSeqList(SeqList *list);

6. int IsEmptySeqList(SeqList *list);

7. int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);

8. int FindSeqList(SeqList *list, char *name);

9. int ModifySeqList(SeqList *list, char *old, DATATYPE new);

10. int DeleteSeqList(SeqList *list, char *name);