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

数据结构

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

 逻辑结构

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

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

树， 一对多
  

 图，多对多      可能用在地图里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.举例：

1. int i,j;

2. for ( i = 0; i < n; ++i){

3. for(j = i; j < n; ++j){

4. /*时间复杂度为 O(1) 的程序步骤序列 */

5. }

6. }

      

 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_Htypedef 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_Htypedef 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)。
空间分配问题：顺序表在初始化时需要预先分配一定大小的存储空间，如果预估不准确，可能会导致空间浪费（分配过多）或溢出（分配不足）。虽然可以通过动态扩容来解决溢出问题，但每次扩容都需要重新分配内存并复制数据，增加了时间成本。
扩容问题：当顺序表需要扩容时，虽然可以动态申请更大的内存空间，但这个过程涉及到旧数据的复制和新空间的申请，可能会影响到程序的性能。
表的大小固定：虽然可以通过动态扩容来解决表大小固定的问题，但在某些场景下，如果需要存储的数据量非常大，而内存空间有限，那么顺序表可能就不是一个很好的选择。