企业官网建设流程全解析

前言顺序表是数据结构与算法入门第一课也是链表、栈、队列的基础。很多同学只会背概念顺序表是什么静态 vs 动态顺序表区别插入删除为什么要挪动数据扩容怎么实现批量删除如何优化本文基于可扩容动态顺序表完整工程代码带你从结构体设计 → 函数实现 → 边界处理 → 性能优化 → 测试用例逐行讲解所有代码可直接复制运行。一、什么是顺序表1.1 定义顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。本质上用数组实现的线性表。1.2 静态 vs 动态静态顺序表固定大小满了不能存容易浪费 / 溢出动态顺序表可自动扩容按需分配空间空间利用率更高本文实现可自动 2 倍扩容的动态顺序表。1.3 优缺点总结优点空间利用率较高支持随机访问下标 O (1) 查找尾插、尾删效率极高O(1)缺点头部 / 中间插入删除需要挪动数据O(n)扩容有一定时间、空间代价1.4 适用场景大量随机访问增删多在尾部操作的场景。二、整体设计结构体与功能清单2.1 动态顺序表结构体和可实现的功能函数设计#pragma once//预处理指令防止头文件重复 #define INIT_SIZE 10//初始化 //可扩容的顺序表的结构体设计 typedef int ELEM_TYPE; typedef struct SeqList { ELEM_TYPE* elem;//用来接收malloc返回的数组首地址 int length;//存放有效值个数 int listsize;//存放数组的总的格子数 }SeqList,*PSeqList; //可实现的功能函数 //1.初始化 void Init_SeqList(struct SeqList* psl); //2.插入数据存 //头插 bool Insert_SeqList_head(PSeqList psl, ELEM_TYPE val); //尾插 bool Insert_SeqList_end(PSeqList psl, ELEM_TYPE val); //按位置插 bool Insert_SeqList_pos(PSeqList psl, ELEM_TYPE val, int pos); //3.删除数据取 //头删 bool Dete_SeqList_head(SeqList* psl); //尾删 bool Dete_SeqList_end(SeqList* psl); //按位置删 bool Dete_SeqList_pos(SeqList* psl, int pos); //按值删 bool Dete_SeqList_val(SeqList* psl, ELEM_TYPE val); //4.查找数据是否已存在若存在返回数组下标找不到返回-1 int Search_SeqList(PSeqList psl, ELEM_TYPE val); //5.判空 bool Is_Empty(PSeqList psl); //6.判满 bool Is_Full(PSeqList psl); //7.扩容函数1.52默认用2倍扩容 void Increase(PSeqList psl); //8.清空不释放已购买的内存 void Clear(PSeqList psl); //9.销毁需要释放malloc购买的内存 void Destroy(PSeqList psl); //打印 void Show(PSeqList psl); bool Insert_Seq(PSeqList va, ELEM_TYPE val); //可扩容的顺序表 //优点:1.空间利用率较高 2.支持随机访问 3.尾部 / 插入删除效率极高0(1) //缺点:1.头部按位置插入 / 删除(搬动数据)2.增容代价大 //适用场景:适用于需要大量随机访问数据操作并且增加/删除数据操作较少或者就算操作多也是在尾部进行(不需要挪动元素)核心成员elem指向 malloc 申请的连续空间length当前存了多少数据listsize当前最大能存多少数据2.2 功能接口完整实现初始化头插 / 尾插 / 按位置插头删 / 尾删 / 按位置删 / 按值删查找元素判空 / 判满2 倍自动扩容清空 / 销毁打印高级批量删除所有指定值两种算法三、核心接口实现逐行精讲3.1 初始化申请堆区空间设置初始长度与容量。//1.初始化 void Init_SeqList(struct SeqList* psl) { //0.安全处理 每一个函数都要写 assert(psl !NULL); assert(psl ! nullptr); if (nullptr psl) { exit(EXIT_FAILURE); } //1.对我们的elem用来去malloc在堆区购买一块连续的空间 psl-elem(ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE)); if (nullptr psl-elem) { exit(EXIT_FAILURE); } //2.对我们的length初始化为0 psl-length 0; //3.对我们的listsize初始化 INITSIZE psl-listsize INIT_SIZE; }3.2 插入操作重点3.2.1 头插需整体后移//2.插入数据存 //头插 bool Insert_SeqList_head(PSeqList psl, ELEM_TYPE val) { //0.assert; //0.5判满 if (Is_Full(psl)) { Increase(psl); } //此时肯定有空余格子 //1.集体向后挪尾巴先动 for (int i psl-length - 1; i 0; i--) { psl-elem[i 1] psl-elem[i]; } //2.将val放入0号下标 psl-elem[0] val; //3.有效值个数1 psl-length; return true; }3.2.2 尾插最高效//尾插 bool Insert_SeqList_end(PSeqList psl, ELEM_TYPE val) { //0.assert; //0.5判满 if (Is_Full(psl)) { Increase(psl); } //此时肯定有空余格子 psl-elem[psl-length] val; psl-length; return true; }3.2.3 按位置插入//按位置插 bool Insert_SeqList_pos(PSeqList psl, ELEM_TYPE val, int pos) { //默认pos0则认为是头插 //0.安全性处理 psl pos合法性判断 assert(nullptr ! psl); if (nullptr psl) { exit(EXIT_FAILURE); } assert(pos 0 pos psl-length); //0,5判满 if (Is_Full(psl)) { Increase(psl); } //1.将插入位置之后的元素统一的向后移动把插入位置给空出来 for (int i psl-length - 1; i pos; i--) { psl-elem[i 1] psl-elem[i]; } //2.插入 psl-elem[pos] val; //length psl-length; return true; }3.3 删除操作3.3.1 头删//3.删除数据取 //头删 bool Dete_SeqList_head(SeqList* psl) { //0.assert //0.5判空 if (Is_Empty(psl)) { return false; } //1.除了第一个元素之外统一向前移动 for (int i 1; i psl-length - 1; i) { psl-elem[i-1] psl-elem[i]; } //2.有效值个数-1 psl-length--; return true; }3.3.2 尾删最简单//尾删 bool Dete_SeqList_end(SeqList* psl) { //0.assert //0.5判空 if (Is_Empty(psl)) { return false; } psl-length--; return true; }3.3.3 按位置删除//按位置删 bool Dete_SeqList_pos(SeqList* psl, int pos) { //0.assert psl pos assert(psl ! nullptr); assert(pos 0 pos psl-length); //0.5判空 if (Is_Empty(psl)) { return false; } //1.将pos位置之后的有效值向前移动 for (int i pos 1; i psl-length - 1; i) { psl-elem[i - 1] psl-elem[i]; } psl-length--; return true; }3.3.4 按值删除//按值删 bool Dete_SeqList_val(SeqList* psl, ELEM_TYPE val) { //0.assert //0.5判空 int index Search_SeqList(psl,val); if (index -1) return false; return Dete_SeqList_pos(psl, index); }3.4 扩容机制2 倍扩容//7.扩容函数1.52默认用2倍扩容 void Increase(PSeqList psl) { ELEM_TYPE*tmp(ELEM_TYPE * )realloc(psl-elem, psl-listsize * sizeof(ELEM_TYPE) * 2); if (tmp ! nullptr) { psl-elem tmp; } }为什么 2 倍减少扩容次数空间分配效率高避免频繁申请释放3.5 查找、判空、判满//4.查找数据是否已存在若存在返回数组下标找不到返回-1 int Search_SeqList(PSeqList psl, ELEM_TYPE val) { //0.assert for (int i 0; i psl-length; i) { if (psl-elem[i] val) return i; } return -1; } //5.判空 bool Is_Empty(PSeqList psl) { return psl-length 0; } //6.判满 bool Is_Full(PSeqList psl) { return psl-length psl-listsize; }3.6 清空与销毁非常重要清空不释放内存//8.清空不释放已购买的内存 void Clear(PSeqList psl) { //malloc申请空间先不释放而是认为所有格子里都是无效值 psl-length 0; }销毁释放堆内存避免泄漏//9.销毁需要释放malloc购买的内存 void Destroy(PSeqList psl) { free(psl-elem); psl-length psl-listsize 0; }四、高级优化批量删除所有指定值方法 1朴素版多次遍历效率低//删除当前val值出现的所有位置1 bool Dete_SeqList_All_Vall(struct SeqList* psl, ELEM_TYPE val) { int count 0; for (int i 0; i psl-length; i) { if(psl-elem[i]val) count; } for (int i 0; i count; i) { int index Search_SeqList(psl, val); Dete_SeqList_pos(psl, index); } return false; }方法 2双指针思想最优 O (n)一次遍历完成删除高频//删除当前val值出现的所有位置2 bool Dete_SeqList_All_Vall2(struct SeqList* psl, ELEM_TYPE val) { int qianfangkongqiangezishu 0; for (int i 0; i psl-length; i) { if (psl-elem[i] val) { qianfangkongqiangezishu; } else psl-elem[i - qianfangkongqiangezishu] psl-elem[i]; } psl-length psl-length - qianfangkongqiangezishu; return true; }五、完整代码完整可运行#define _CRT_SECURE_NO_WARNINGS #includestdio.h #includeassert.h #includestdlib.h #include 顺序表.h #includevld.h//检测内存泄露 //1.初始化 void Init_SeqList(struct SeqList* psl) { //0.安全处理 每一个函数都要写 assert(psl !NULL); assert(psl ! nullptr); if (nullptr psl) { exit(EXIT_FAILURE); } //1.对我们的elem用来去malloc在堆区购买一块连续的空间 psl-elem(ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE)); if (nullptr psl-elem) { exit(EXIT_FAILURE); } //2.对我们的length初始化为0 psl-length 0; //3.对我们的listsize初始化 INITSIZE psl-listsize INIT_SIZE; } //2.插入数据存 //头插 bool Insert_SeqList_head(PSeqList psl, ELEM_TYPE val) { //0.assert; //0.5判满 if (Is_Full(psl)) { Increase(psl); } //此时肯定有空余格子 //1.集体向后挪尾巴先动 for (int i psl-length - 1; i 0; i--) { psl-elem[i 1] psl-elem[i]; } //2.将val放入0号下标 psl-elem[0] val; //3.有效值个数1 psl-length; return true; } //尾插 bool Insert_SeqList_end(PSeqList psl, ELEM_TYPE val) { //0.assert; //0.5判满 if (Is_Full(psl)) { Increase(psl); } //此时肯定有空余格子 psl-elem[psl-length] val; psl-length; return true; } //按位置插 bool Insert_SeqList_pos(PSeqList psl, ELEM_TYPE val, int pos) { //默认pos0则认为是头插 //0.安全性处理 psl pos合法性判断 assert(nullptr ! psl); if (nullptr psl) { exit(EXIT_FAILURE); } assert(pos 0 pos psl-length); //0,5判满 if (Is_Full(psl)) { Increase(psl); } //1.将插入位置之后的元素统一的向后移动把插入位置给空出来 for (int i psl-length - 1; i pos; i--) { psl-elem[i 1] psl-elem[i]; } //2.插入 psl-elem[pos] val; //length psl-length; return true; } //3.删除数据取 //头删 bool Dete_SeqList_head(SeqList* psl) { //0.assert //0.5判空 if (Is_Empty(psl)) { return false; } //1.除了第一个元素之外统一向前移动 for (int i 1; i psl-length - 1; i) { psl-elem[i-1] psl-elem[i]; } //2.有效值个数-1 psl-length--; return true; } //尾删 bool Dete_SeqList_end(SeqList* psl) { //0.assert //0.5判空 if (Is_Empty(psl)) { return false; } psl-length--; return true; } //按位置删 bool Dete_SeqList_pos(SeqList* psl, int pos) { //0.assert psl pos assert(psl ! nullptr); assert(pos 0 pos psl-length); //0.5判空 if (Is_Empty(psl)) { return false; } //1.将pos位置之后的有效值向前移动 for (int i pos 1; i psl-length - 1; i) { psl-elem[i - 1] psl-elem[i]; } psl-length--; return true; } //按值删 bool Dete_SeqList_val(SeqList* psl, ELEM_TYPE val) { //0.assert //0.5判空 int index Search_SeqList(psl,val); if (index -1) return false; return Dete_SeqList_pos(psl, index); } //4.查找数据是否已存在若存在返回数组下标找不到返回-1 int Search_SeqList(PSeqList psl, ELEM_TYPE val) { //0.assert for (int i 0; i psl-length; i) { if (psl-elem[i] val) return i; } return -1; } //5.判空 bool Is_Empty(PSeqList psl) { return psl-length 0; } //6.判满 bool Is_Full(PSeqList psl) { return psl-length psl-listsize; } //7.扩容函数1.52默认用2倍扩容 void Increase(PSeqList psl) { ELEM_TYPE*tmp(ELEM_TYPE * )realloc(psl-elem, psl-listsize * sizeof(ELEM_TYPE) * 2); if (tmp ! nullptr) { psl-elem tmp; } } //8.清空不释放已购买的内存 void Clear(PSeqList psl) { //malloc申请空间先不释放而是认为所有格子里都是无效值 psl-length 0; } //9.销毁需要释放malloc购买的内存 void Destroy(PSeqList psl) { free(psl-elem); psl-length psl-listsize 0; } //打印 void Show(PSeqList psl) { //assert for (int i 0; i psl-length ; i) { printf(%d , psl-elem[i]); } printf(\n); } //删除当前val值出现的所有位置1 bool Dete_SeqList_All_Vall(struct SeqList* psl, ELEM_TYPE val) { int count 0; for (int i 0; i psl-length; i) { if(psl-elem[i]val) count; } for (int i 0; i count; i) { int index Search_SeqList(psl, val); Dete_SeqList_pos(psl, index); } return false; } //删除当前val值出现的所有位置2 bool Dete_SeqList_All_Vall2(struct SeqList* psl, ELEM_TYPE val) { int qianfangkongqiangezishu 0; for (int i 0; i psl-length; i) { if (psl-elem[i] val) { qianfangkongqiangezishu; } else psl-elem[i - qianfangkongqiangezishu] psl-elem[i]; } psl-length psl-length - qianfangkongqiangezishu; return true; } int main() { struct SeqList sq; Init_SeqList(sq); //插入 Insert_SeqList_head(sq, 100); Insert_SeqList_head(sq, 101); Insert_SeqList_head(sq, 102); Insert_SeqList_end(sq, 200); Insert_SeqList_end(sq, 201); Insert_SeqList_end(sq, 202); Insert_SeqList_pos(sq, 301, 2); Insert_SeqList_pos(sq, 302, 3); Insert_SeqList_pos(sq, 303, 4); Show(sq); Insert_SeqList_head(sq, 1020); Insert_SeqList_end(sq, 2000); Show(sq); // 删除 Dete_SeqList_head(sq); Dete_SeqList_end(sq); Show(sq); Dete_SeqList_pos(sq, 4); Show(sq); Dete_SeqList_pos(sq, 7); Show(sq); Dete_SeqList_pos(sq, 0); Show(sq); Dete_SeqList_val(sq, 200); Show(sq); /*Clear(sq); Show(sq); Destroy(sq); Show(sq);*/ //--------------------------------- Insert_SeqList_pos(sq, 3, 2); Insert_SeqList_pos(sq, 3, 4); Insert_SeqList_head(sq,890); Show(sq); Insert_SeqList_pos(sq, 3, 7); Show(sq); // 批量删除 //Dete_SeqList_All_Vall(sq, 3); Dete_SeqList_All_Vall2(sq, 3); Show(sq); return 0; }六、顺序表高频考点头插和尾插效率为什么差很多头插需要挪动全部数据 O (n)尾插直接放 O (1)。扩容为什么用 2 倍不用 1.5 倍2 倍扩容减少扩容次数效率更高。顺序表和链表区别顺序表连续、随机访问快、插入删除慢链表不连续、查找慢、插入删除快最优批量删除算法时间复杂度O(n)一次遍历完成。为什么必须 free堆区不会自动释放不 free 会造成内存泄漏。需要完整源码头文件 源文件 测试文件的同学评论区扣1我直接发给你