文章目录一、顺序表的概念与结构1. 线性表的基础2. 顺序表与数组的区别二、顺序表的分类三、顺序表的结构设计四、核心功能实现1. 初始化与销毁2. 空间检查与扩容3. 插入操作尾插头插指定位置之前插入4. 删除操作尾删头删指定位置删除5. 查找与打印五、测试代码与运行结果六、顺序表的应用通讯录1. 项目需求2. 核心设计思路1数据结构设计2核心功能实现七、顺序表的问题与思考优点缺点数据结构的作用高效存储数据方便快速查找支持灵活的增删改查操作最基础的数据结构是数组但它的局限性很大。比如当数组已满时插入新数据需要手动扩容频繁计算有效元素个数还会降低效率。这就是我们需要学习更高级结构的原因——顺序表就是数组的升级版。一、顺序表的概念与结构1. 线性表的基础顺序表属于线性表的一种。线性表是由n个相同特性的数据元素组成的有限序列常见的还有链表、栈、队列等。它的逻辑结构是一条连续的直线但物理存储方式可以是数组或链式结构。线性表物理结构不一定连续逻辑结构是连续的。顺序表物理结构和逻辑结构都是连续的2. 顺序表与数组的区别顺序表的底层基于数组实现但它对数组进行了封装提供了更完善的操作接口。简单说数组是原料顺序表是加工后的成品。比如数组只能通过下标访问而顺序表会额外记录有效元素个数和容量让数据管理更可控。二、顺序表的分类顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构通常采用数组存储。根据存储空间的分配方式可分为两类静态顺序表使用固定大小的数组存储数据空间一旦确定无法更改动态顺序表使用动态开辟的数组存储数据可根据需要动态扩容更灵活实用本文重点实现动态顺序表因为它能更好地适应数据量变化的场景。三、顺序表的结构设计首先我们需要定义顺序表的结构体动态顺序表需要包含三个核心要素typedefintSLDataType;// 数据类型别名方便后续修改存储类型structSeqList{SLDataType*arr;// 指向动态开辟的数组intsize;// 有效数据个数intcapacity;// 容量大小能存储的最大数据个数};typedefstructSeqListSL;// 重命名简化代码这样的设计有几个好处使用SLDataType统一数据类型后续要存储char或float只需修改这里分离size和capacity清晰区分当前数据量和总容量用指针指向动态数组实现存储空间的动态管理四、核心功能实现1. 初始化与销毁初始化函数将顺序表初始化为空状态voidSLInit(SL*p)// 传地址而不是传值因为要修改结构体内容{p-arrNULL;p-sizep-capacity0;// 初始状态无数据容量为0}销毁函数释放动态开辟的空间避免内存泄漏voidSLDes(SL*p){if(p-arr)// 如果数组存在则释放{free(p-arr);}p-arrNULL;// 置空指针避免野指针p-sizep-capacity0;// 重置状态}2. 空间检查与扩容动态顺序表的关键在于自动扩容我们实现一个专门的函数来处理voidcheckCapacity(SL*p){assert(p);// 确保指针有效// 当有效数据个数等于容量时需要扩容if(p-sizep-capacity){// 初始容量为4之后每次翻倍intnewCapacityp-capacity0?4:2*p-capacity;// 使用realloc进行扩容首次调用时相当于mallocSLDataType*tmp(SLDataType*)realloc(p-arr,newCapacity*sizeof(SLDataType));if(tmpNULL)// 检查扩容是否成功{perror(realloc fail!!);exit(1);// 扩容失败则退出程序}// 扩容成功更新指针和容量p-arrtmp;p-capacitynewCapacity;}}为什么选择2倍扩容这是一种时间和空间效率平衡的策略既能减少频繁扩容的开销又不会过度浪费空间。3. 插入操作尾插voidSLPushBack(SL*p,SLDataType x){assert(p);checkCapacity(p);// 先检查空间p-arr[p-size]x;// 直接在末尾赋值p-size;// 有效数据个数加 1}头插voidSLPushFront(SL*p,SLDataType x){assert(p);checkCapacity(p);// 从最后一个元素开始依次向后移动一位for(intip-size;i1;i--){p-arr[i]p-arr[i-1];}p-arr[0]x;// 头部位置赋值p-size;// 更新数据个数}指定位置之前插入voidSLInsert(SL*p,intpos,SLDataType x){assert(p);assert(pos0posp-size);// 确保位置有效checkCapacity(p);// 从最后一个元素到pos位置依次后移for(intip-size;ipos;i--){p-arr[i]p-arr[i-1];}p-arr[pos]x;// 在pos位置插入新元素p-size;}4. 删除操作尾删voidSLPopBack(SL*p){assert(p);assert(p-size);// 确保顺序表不为空p-size--;// 只需将有效数据个数减1逻辑删除}头删voidSLPopFront(SL*p){assert(p);assert(p-size);// 确保顺序表不为空// 从第二个元素开始依次向前移动一位for(inti0;ip-size-1;i){p-arr[i]p-arr[i1];}p-size--;// 更新数据个数}指定位置删除voidSLErase(SL*p,intpos){assert(p);assert(p-size);// 确保顺序表不为空assert(pos0posp-size);// 确保位置有效// 从pos位置开始依次用后一个元素覆盖前一个for(intipos;ip-size-1;i){p-arr[i]p-arr[i1];}p-size--;}5. 查找与打印查找元素返回元素所在位置未找到返回-1intSLFind(SL*p,SLDataType x){assert(p);for(inti0;ip-size;i){if(p-arr[i]x)returni;}return-1;// 未找到}打印顺序表遍历输出所有元素voidSLPrint(SL s){for(inti0;is.size;i){printf(%d ,s.arr[i]);}printf(\n);}五、测试代码与运行结果我们编写测试函数来验证各个功能voidSLtest01(){SL s1;SLInit(s1);// 初始化// 尾插测试SLPushBack(s1,1);SLPushBack(s1,2);SLPushBack(s1,3);SLPushBack(s1,4);SLPushBack(s1,5);SLPrint(s1);// 输出1 2 3 4 5// 指定位置插入测试SLInsert(s1,0,9);// 头部插入SLPrint(s1);// 输出9 1 2 3 4 5SLInsert(s1,s1.size,6);// 尾部插入等价于尾插SLPrint(s1);// 输出9 1 2 3 4 5 6// 指定位置删除测试SLErase(s1,1);// 删除索引1的元素SLPrint(s1);// 输出9 2 3 4 5 6SLErase(s1,2);// 删除索引2的元素SLPrint(s1);// 输出9 2 4 5 6SLErase(s1,s1.size-1);// 删除最后一个元素SLPrint(s1);// 输出9 2 4 5// 查找测试intfindSLFind(s1,4);printf(%d\n,find);// 输出2元素4在索引2位置SLDes(s1);// 销毁}六、顺序表的应用通讯录1. 项目需求实现一个具有以下功能的通讯录存储至少100个人的通讯信息保存信息包括名字、性别、年龄、电话、地址等支持增加、删除、查找、修改、显示联系人等操作程序结束后通讯录信息不丢失2. 核心设计思路1数据结构设计首先定义联系人信息结构体#defineNAME_MAX100#defineSEX_MAX4#defineTEL_MAX11#defineADDR_MAX100typedefstructPersonInfo{charname[NAME_MAX];// 姓名charsex[SEX_MAX];// 性别intage;// 年龄chartel[TEL_MAX];// 电话charaddr[ADDR_MAX];// 地址}PeoInfo;然后基于动态顺序表实现通讯录// 数据类型为PersonInfotypedefstructPersonInfoSQDataType;// 动态顺序表typedefstructSeqList{SQDataType*a;// 存储联系人数据intsize;// 有效联系人个数intcapacity;// 容量}SLT;// 通讯录类型定义typedefstructSeqListcontact;2核心功能实现初始化通讯录voidInitContact(contact*con){SeqListInit(con);// 初始化顺序表LoadContact(con);// 加载历史数据}添加联系人voidAddContact(contact*con){PeoInfo info;printf(请输入姓名:\n);scanf(%s,info.name);printf(请输入性别:\n);scanf(%s,info.sex);printf(请输入年龄:\n);scanf(%d,info.age);printf(请输入联系电话:\n);scanf(%s,info.tel);printf(请输入地址:\n);scanf(%s,info.addr);SeqListPushBack(con,info);// 尾插printf(插入成功!\n);}删除联系人voidDelContact(contact*con){charname[NAME_MAX];printf(请输入要删除的用户姓名:\n);scanf(%s,name);intposFindByName(con,name);// 查找位置if(pos0){printf(要删除的用户不存在,删除失败!\n);return;}SeqListErase(con,pos);// 删除指定位置元素printf(删除成功!\n);}数据持久化为了保证程序结束后数据不丢失需要将数据保存到文件voidSaveContact(contact*con){FILE*pffopen(contact.txt,wb);if(pfNULL){perror(fopen error!\n);return;}// 将通讯录数据写入文件for(inti0;icon-size;i){fwrite(con-ai,sizeof(PeoInfo),1,pf);}printf(通讯录数据保存成功!\n);fclose(pf);}程序启动时加载数据voidLoadContact(contact*con){FILE*pffopen(contact.txt,rb);if(pfNULL){printf(fopen error!\n);return;}// 循环读取文件数据PeoInfo info;while(fread(info,sizeof(PeoInfo),1,pf)){SeqListPushBack(con,info);}printf(历史数据导入通讯录成功!\n);fclose(pf);}菜单交互voidmenu(){contact con;InitContact(con);intop-1;do{printf(********************************\n);printf(*****1、添加用户 2、删除用户*****\n);printf(*****3、查找用户 4、修改用户*****\n);printf(*****5、展示用户 0、退出 *****\n);printf(********************************\n);printf(请选择您的操作:\n);scanf(%d,op);switch(op){case1:AddContact(con);break;case2:DelContact(con);break;case3:FindContact(con);break;case4:ModifyContact(con);break;case5:ShowContact(con);break;case0:printf(退出程序\n);break;default:printf(输入有误,请重新输入\n);break;}}while(op!0);// 销毁通讯录,同时保存数据DestroyContact(con);}七、顺序表的问题与思考优点随机访问可以通过下标直接访问任意元素时间复杂度O(1)缓存友好数据存储连续充分利用CPU缓存访问效率高实现简单相比链表结构和操作更简单缺点插入删除效率问题中间或头部的插入删除操作需要移动大量元素时间复杂度为O(N)增容消耗增容时需要申请新空间、拷贝数据、释放旧空间会产生额外消耗空间浪费增容通常是2倍增长可能导致部分空间闲置例如容量从100增到200却只再插入5个数据就浪费了95个空间这些问题也引出了另一种重要的数据结构——链表它在解决上述问题上有独特优势。在实际开发中我们需要根据具体场景选择合适的数据结构。
