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

嵌入式学习——数据结构——顺序表

news 来源：原创 2024/9/19 9:35:58

线性表的定义

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

线性表的常规操作

创建：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)将线性表中的所有元素删除，使线性表变为空表。

线性表顺序存储的优缺点

优点
- 无需额外存储逻辑关系：因为数据元素在物理上是连续存储的，其顺序就体现了逻辑关系，不需要额外的空间来存储元素之间的逻辑关系，节省了存储空间。
- 快速随机访问：可以直接通过数组下标在常数时间O(1)内访问任意位置的元素。例如，对于SeqList线性表，要访问第i个元素，可以直接通过list->head[i]来获取，不需要逐个元素遍历。
缺点
- 插入和删除操作复杂：当需要插入或删除一个元素时，需要移动插入或删除位置之后的所有元素。例如，在一个长度为n的线性表中，在第i个位置插入一个元素，需要将第i个及之后的元素都向后移动一位，平均需要移动n/2个元素，时间复杂度为O(n)。
- 无法动态存储：在创建线性表时需要预先指定其长度，在运行过程中不能根据实际需要动态地增加或减少存储空间。如果一开始估计的长度过小，可能导致数据无法全部存储；如果估计的长度过大，则会浪费存储空间。

代码示例

`seqlist.h`

#ifndef SEQLIST_H
#define SEQLIST_H// 定义一个名为 person 的结构体来存储人员信息
typedef struct person {char name[32];    // 姓名char gender;      // 性别int age;          // 年龄int score;        // 分数
}DATATYPE;// 定义一个名为 list 的结构体来表示顺序表
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 *newdata);
// 根据姓名删除顺序表中的元素
int DeleteSeqList(SeqList *list, char *name);
// 清空顺序表中的所有元素
int ClearSeqList(SeqList *list);
// 获取顺序表中元素的个数
int GetSizeSeqList(SeqList *list);
// 获取顺序表中指定位置的元素
DATATYPE* GetItemSeqList(SeqList *list, int pos);#endif // SEQLIST_H

`seqlist.c`

#include "seqlist.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>// 创建一个长度为 len 的顺序表
SeqList *CreateSeqList(int len)
{// 为 SeqList 结构体分配内存空间SeqList* sl = malloc(sizeof(SeqList));if(NULL == sl){// 如果内存分配失败，输出错误信息perror("CreateSeqList malloc");return NULL;}// 为存储数据元素的数组分配内存空间sl->head = malloc(sizeof(DATATYPE)*len);if(NULL == sl->head){perror("CreateSeqList malloc2");// 如果内存分配失败，释放之前为 SeqList 结构体分配的内存free(sl);return NULL;}// 初始化当前元素个数为 0，总长度为指定长度sl->clen = 0;sl->tlen = len;return sl;
}// 销毁顺序表，释放内存
int DestroySeqList(SeqList *list)
{// 先释放存储数据元素的数组的内存free(list->head);// 再释放 SeqList 结构体的内存free(list);return 0;
}// 在顺序表的尾部插入一个元素
int InsertTailSeqList(SeqList *list, DATATYPE *data)
{// 如果顺序表已满，则输出提示信息并返回 1if(IsFullSeqList(list)){printf("list is full\n");return 1;}// 将数据元素复制到顺序表的尾部memcpy(&list->head[list->clen],data,sizeof(DATATYPE));// 当前元素个数加 1list->clen++;return 0;
}// 判断顺序表是否已满
int IsFullSeqList(SeqList *list)
{// 如果当前元素个数等于总长度，则表示顺序表已满return list->clen == list->tlen;
}// 判断顺序表是否为空
int IsEmptySeqList(SeqList *list)
{// 如果当前元素个数为 0，则表示顺序表为空return 0 == list->clen;
}// 展示顺序表中的所有元素信息
int ShowSeqList(SeqList *list)
{int i = 0 ;int len = GetSizeSeqList(list);for(i=0;i<len;i++){// 输出每个元素的姓名、性别、年龄和分数printf("name:%s gender:%c age:%d score:%d\n",list->head[i].name,list->head[i].gender,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;}}// 如果没有找到匹配的姓名，则返回 -1return -1;
}// 获取顺序表中指定位置的元素
DATATYPE *GetItemSeqList(SeqList *list, int pos)
{int len = GetSizeSeqList(list);// 如果位置不合法，则返回 NULLif(pos<0||pos>=len){return NULL;}// 返回指定位置的元素的指针return &list->head[pos];
}// 根据旧元素的值修改为新元素的值
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{int ret = FindSeqList(list,old);// 如果没有找到旧元素，则返回 1if(-1 == ret){return 1;}// 将新元素复制到找到的旧元素的位置memcpy(&list->head[ret],newdata,sizeof(DATATYPE));return 0;
}// 在指定位置插入一个元素
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{int len = GetSizeSeqList(list);// 如果位置不合法，则返回 1if(pos<0||pos>len){return 1;}// 将插入位置及之后的元素向后移动一位for(int i=list->clen;i!=pos ;i--){list->head[i]= list->head[i-1];}// 将新元素插入到指定位置memcpy(&list->head[pos],data,sizeof(DATATYPE));// 当前元素个数加 1list->clen++;return 0;
}// 清空顺序表中的所有元素
int ClearSeqList(SeqList *list)
{// 将当前元素个数置为 0list->clen=0;return 0;
}// 根据姓名删除顺序表中的元素
int DeleteSeqList(SeqList *list, char *name)
{int ret = FindSeqList(list,name);if(-1 == ret){// 如果没有找到要删除的元素，则输出提示信息并返回 1printf("can't find %s\n",name);return 1;}// 将删除位置之后的元素向前移动一位for(int i=ret; i!=list->clen; i++){list->head[i] = list->head[i+1];}// 当前元素个数减 1list->clen--;return 0;
}

`main.c`

#include <stdio.h>
#include "seqlist.h"int main()
{// 定义一个包含人员信息的数组DATATYPE data[]={{"zhangsan",'m',20,80},{"lisi",'f',21,82},{"wangmazi",'f',22,70},{"lao6",'f',30,70},{"zhaosi",'f',30,50},};// 创建一个长度为 10 的顺序表SeqList*sl=  CreateSeqList(10);// 向顺序表尾部插入三个元素InsertTailSeqList(sl,&data[0]);InsertTailSeqList(sl,&data[1]);InsertTailSeqList(sl,&data[2]);// 展示顺序表中的所有元素信息ShowSeqList(sl);printf("--------find----------\n");char want_name[50]="li2si";// 在线性表中查找指定姓名的元素的位置int ret = FindSeqList(sl,want_name);if(-1 == ret){printf("can't find %s\n",want_name);}else{// 获取查找到的元素的指针并输出其信息DATATYPE* find_data = GetItemSeqList(sl,ret);printf("name:%s score:%d\n",find_data->name,find_data->score);}printf("--------modify----------\n");// 修改顺序表中指定姓名的元素的值ModifySeqList(sl,"lisi",&data[3]);ShowSeqList(sl);printf("--------ins pos----------\n");// 在指定位置插入一个元素InsertPosSeqList(sl,&data[4],2);ShowSeqList(sl);printf("--------delete----------\n");// 根据姓名删除顺序表中的元素DeleteSeqList(sl,"zhangsan");ShowSeqList(sl);// 销毁顺序表，释放内存DestroySeqList(sl);printf("Hello World!\n");return 0;
}