做汽车微信广告视频网站有哪些,项目logo生成器,建设网站投资多少,配置无法运行wordpress前言我们都知道#xff0c;数据结构中逻辑结构可以划分为线性结构(线性表)与非线性结构两大类。而存储结构指的是数据元素在计算机中的存储及其逻辑关系的表现#xff0c;也就是在计算机当中对逻辑结构的表示。线性表的存储结构主要有顺序结构和链式结构两种实现形式。本文主… 前言我们都知道数据结构中逻辑结构可以划分为线性结构(线性表)与非线性结构两大类。而存储结构指的是数据元素在计算机中的存储及其逻辑关系的表现也就是在计算机当中对逻辑结构的表示。线性表的存储结构主要有顺序结构和链式结构两种实现形式。本文主要探讨基于线性表的顺序结构也就是顺序表的四种基本操作初始化、插入、删除、查找。这些知识点既可能出现在选择题的考察当中又可以出现在编程大题当中但是考察的侧重点不同选择题重点关注操作的时间复杂度以及特性(特别是不同结构的顺序表在实现某种操作时候的效率高低)编程大题只是关注代码实现能力。基本知识分析顺序存储 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。(为了便于理解大家可以近似得把这一段空间理解成一个C语言数组)由于元素顺序排列顺序存储具有以下性质和特征• 线性表的逻辑顺序与物理顺序一致;• 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现a1到an存放情况如图所示设每个元素占l个单元长度。(ps计算机中数组下标实际从0开始)ai的地址Loc(ai)Loc(a1)(i-1)×1因此顺序表的结构体当中应当包含 一块连续的地址空间、当前存放元素的长度、当前分配的存储容量。由此写出结构体如下typedef struct{ ElemType *elem;//存储空间基址 int length;//当前长度 int listsize;//当前分配的存储容量}SqList;在了解顺序表静态构造的基础上我们可以在这个基础上构建它的几个基本操作了。1初始化输入MAXSIZE表示要申请MAXSIZE个元素大小的地址单元。关键代码L-elem(ElemType *)malloc(MAX_SIZE*sizeof( ElemType));//分配空间L-length0;//空表长度为0L-listsizeMAX_SIZE;//初始存储容量2插入设n个元素存放在elem[0...length-1]内。输入ie表示要在下标为i处插入值为e的元素。分析插入过程导致的结果元素数量从length变成了length1如果只是简单地将下标为i处的元素替换成e会导致原先的元素丢失。因此插入操作可以表述为(1)将该元素以及该元素之后的所有元素都向后移动一个位。(2)元素大小加1。(3)再将e写入到下标为i处。比如对于[1,2]这个数组来说将0插入到第一位事实上是先使得第一位以及第一位之后的所有元素后移一位数组变成[1,1,2]然后将0写入第一位数组变成[0,1,2]关键代码//elem[i...length-1]向后移动for(j length-1; j i; j--){L-elem[j1] L-elem[j]}//元素大小加1length;//e写入下标为i处L-elem[i]e;3删除设n个元素存放在elem[0...length-1]内。输入i表示要删除下标为i处的元素。分析删除过程导致的结果元素数量从length变成了length-1如果只是简单地将下标为i处的元素被删除会导致此处出现一个空白单元。因此删除操作可以表述为(1)将该元素之后的所有元素都向前移动一个位。(2)元素大小减1。将i1处的元素移动到i处时完成了覆盖事实上等同于删除了i处的元素。比如对于[0,1,2]这个数组来说将第二个元素移动到第一个第三个元素移动到第二个也就是数组变成了[1,2,2]但是此时length2说明数组长度为2取前2个元素事实上完成了对0的删除。关键代码//elem[i1...length-1]向前移动for(j length-1; j i; j--){L-elem[j-1] L-elem[j]}//元素大小减1length--; 4查找设n个元素存放在elem[0...length-1]内。输入e表示查找值为e的元素。输出i表示值为e的元素位于下标为i处若查找不成功i-1(或者自己定义其他不属于0...length-1的值)分析查找过程其实是从头到尾遍历每一个元素比较当前元素是否等于查找值e若等于则返回下标i当遍历完毕n个元素还是没有返回值说明表中不存在要查询的元素。关键代码//遍历比较每一个元素for(i0; i length; i){if(EQ(L-elem[i], e)){ return i;}}//遍历结束没有返回值说明不存在return -1;选择题角度重点考察 时间复杂度、特性、以及执行相关操作的效率。根据前面的分析以及关键代码部分可以观察到1初始化关键代码只涉及到一次堆分配malloc以及修改listsize和length频度为3时间复杂度为O(1)。2插入关键代码分为三步(1)修改length频度为1时间复杂度为O(1)(2)elem[i...n-1]向后移动移动n-i次频度为n-i时间复杂度为O(n)(3)向下标为i处写入元素e频度为1时间复杂度为O(1)。综上总的时间复杂度为O(n)。3删除关键代码分为两步(1)修改length频度为1时间复杂度为O(1)(2)elem[i1...n-1]向前移动移动n-i-1次频度为n-i-1时间复杂度为O(n)。综上总的时间复杂度为O(n)。4查找关键代码遍历整个序列比较是否有元素的值为e遍历结束时查找不成功则返回-1。显然若第一个元素就是要找的元素时只比较一次若最后一个元素是要找的元素则比较n次若不存在该元素同样是比较n次比较次数的取值范围为1到n若每个元素出现频率相等查找成功的情况下平均比较次数为(n1)/2次时间复杂度为O(n)。综上在顺序表中访问下标为i的元素可以通过 随机访问 如elem[i]获取时间复杂度为O(1)但是对于插入和删除这样的动态操作时间复杂度都为O(n)顺序查找时间复杂度也为O(n)。编程角度一个完整的操作函数是由 健壮性保证 以及 关键代码 两部分组成的。1初始化malloc可能会有分配失败的可能因此要对此进行判断。bool InitList(SqList *L){ L-elem(ElemType *)malloc(MAX_SIZE*sizeof( ElemType));//分配空间if(!L-elem){ return false;}//基址指针为空时分配失败 L-length0;//空表长度为0 L-listsizeMAX_SIZE;//初始存储容量return true;}2插入• 对于elem[0...length-1]来说合法的插入范围应该是0~length要对输入的i进行判断。• 插入会使得表长加1可能会发生上溢也就是分配空间不够所以要对此进行判断。bool ListInsert(SqList *L, int i, ElemType e){int j;if(i 0 || i L-length) { return false;}//i输入是否合法if(L-length L-listsize){ newbase (ElemType *)realloc(L-elem, (L-listsize INCREMENT)*sizeof( ElemType));//分配空间if(!newbase){return false;}//分配失败 L-elem newbase; L-listsize INCREMENT; }//是否上溢//elem[i...n-1]向后移动for(j L-length-1; j i; j--){ L-elem[j1] L-elem[j] }//元素大小加1 L-length;//e写入下标为i处 L-elem[i]e;return true;}3删除• 对于elem[0...length-1]来说合法的删除范围应该是0~length-1要对输入的i进行判断。bool ListDelete(SqList *L, int i, ElemType e){if(i 0 || i L-length - 1){ retrun false;}//i输入是否合法 e *(L-elem[i]);//elem[i1...length-1]向前移动for(j L-length-1; j i; j--){ L-elem[j-1] L-elem[j] }//元素大小减1 L-length--;return true;}4查找int Locate(SqList* L, ElemType e){int i;//遍历比较每一个元素for(i0; i L.length; i){if(EQ(L-elem[i], e)){ return i;} }//遍历结束没有返回值说明不存在return -1;}以上就是学长给大家归纳的关于线性表的相关基本操作了。这里大牛学长帮大家最后总结一下。⭕ 对于增、删、查、改几个基本操作由于顺序表元素存在于一片连续空间。每一次做遍历相关操作的时候都需要用一个全局的for循环去近似遍历整个表因此这几个操作的时间复杂度都是O(n)即线性的。⭕ 对于增、删操作一定要做好合法性判断在编程大题中合法性判断是判卷老师对于学生编程素质的重点考察点你不能说老师一定会关注合法性判断但是写上合法性判断相关的代码一定会为你加上一点“印象分”今天是2020年8月18日距离2021考研还有 122 天 全力以赴才有资格说尽力。大牛学长一直在~
