网站建制作,建筑模板做凳子,工信部备案网站打不开,建筑信息公开平台文章目录 顺序表一#xff1a;线性表1.1概念#xff1a; 二#xff1a;顺序表2.1概念与结构#xff1a;2.2分类#xff1a;2.2.1静态顺序表2.2.2动态顺序表 2.3动态顺序表的实现声明#xff08;初始化#xff09;检查空间容量尾插头插尾删头删查找指定位置之前插入数据指… 文章目录 顺序表一线性表1.1概念 二顺序表2.1概念与结构2.2分类2.2.1静态顺序表2.2.2动态顺序表 2.3动态顺序表的实现声明初始化检查空间容量尾插头插尾删头删查找指定位置之前插入数据指定位置之后插入数据销毁 2.4顺序表算法题2.4.1移除元素2.4.2删除有序数组中的重复项2.4.3合并两个有序数组 2.5顺序表的问题与思考 结语 欢迎大家来到我的博客给生活来点impetus 今天我们主要学习顺序表数据结构初阶 顺序表
一线性表
1.1概念
线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 理解 相同特性分为物理结构和逻辑结构物理结构指数据元素在计算机存储器中的存储方式。它主要包括顺序存储结构底层逻辑是数组和链式存储结构。理解链式结构具体可参考单链表SList 逻辑结构指用户角度看到的数据结构与数据的存储无关带主观因素. 二顺序表
2.1概念与结构
概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储。 从定义我们可以明白 1:顺序表在物理结构和逻辑结构上都是连续的 2顺序表的底层逻辑就是数组. 那么数组与顺序表的区别体现在哪里呢 顺序表的底层结构是数组对数组的封装实现了常⽤的增删改查等接⼝ 看下方的图解你就明白了 这样是不是就能够清晰的明白数组与顺序表的区别了。
2.2分类
2.2.1静态顺序表
概念使用定长数组存储元素 来看一下基本代码 静态顺序表缺点空间不灵活。空间给少了不够用给多了空间浪费。 结论只有知道了总共的数据大小后才可能会使用静态顺序表。 2.2.2动态顺序表
概念使用了变长数组来存储元素。 来看一下基本代码 1:下方int不使用typedef定义后的名字是因为有效数据和空间容量只可能是整数。 2在绝大多数的情况下动态顺序表比静态顺序表要更好。 2.3动态顺序表的实现
在这里我们将会实现在顺序表中将实现声明初始化检查空间容量申请空间销毁空间尾插头插尾删头删查找指定位置之前插入数据指定位置之后插入数据。
声明初始化 检查空间容量 扩容那么究竟按照几倍来扩容呢 结论按照两倍来扩容。当按照很低倍数扩容编译器频繁的寻找新空间拷贝旧空间释放旧空间使得编译效率大大减低当按照很高倍数扩容容易造成空间的浪费。 使用二倍扩容利用数学概率论的知识能够更好的描述数据个数的变化趋势这里仅做了解知道结论就好。 来看一下这部分的代码 在这里容易犯错的几个点 1malloc创建空间的大小单位是字节所以要利用sizeof计算动态结构体的大小。 2创建空间要使用判断语句判断是否开辟成功 3要在函数中完成对实参的修改需要传地址 4考虑特殊情况如这里的初始值都为0的情况。 最后只要是数据的插入增加都需要事先判断空间是否需要扩容追加。
尾插
代码如下 以下对数据进行操作都需要断言传过来的指针是否为空指针。 头插
来看代码 总结:时间复杂度on相较于链表中的头插该处时间复杂度还是较高效率还是较低。 尾删
代码如下 总结 1删除必须断言是否有元素 2利用size有效数据个数对尾删进行操作 头删 这里的细节仍然是断言 查找 指定位置之前插入数据 这里需要注意判断pos插入的位置是否是正确的。 指定位置之后插入数据 与上一个操作的区别在于pos是否需要移动。 销毁 到这里我们对顺序表中的数据进行基本的增删查改操作就有一定的认识了。 下面我们来刷几道题来巩固一下吧
2.4顺序表算法题
2.4.1移除元素
https://leetcode.cn/problems/remove-element/description/ 说明一下思路 方法一 1. 从前往后遍历nums找到val第一次出现的位置 2. 将val之后的所有元素整体往前搬移即删除该val 3. nums中有效元素个数减少一个 循环进行上述操作直到nums中所有值为val的元素全部删除完 时间复杂度:O(N^2) 空间复杂度:O(1) 方法二 1. 创建一个长度与nums相同的数组temp 2. 遍历nums将nums中所有与val不同的元素搬移到temp中 3. 将temp中所有元素拷贝回nums中 时间复杂度: O(N) 空间复杂度: O(N) 优化: 因为题目说了数组中元素个数最大为100所以不用动态申请至二级创建100个元素数组即可 方法三 解题思路: 1. 设置一个变量count用来记录nums中值等于val的元素的个数 2. 遍历nums数组对于每个元素进行如下操作 a. 如果num[i]等于val说明值为val的元素出现了一次count b. 如果nums[i]不等于元素将nums[i]往前搬移count个位置 因为nums[i]元素之前出现过count个值等于val的元素已经被删除了 因此次数需要将nums[i]往前搬移 3. 返回删除之后新数组中有效元素个数 时间复杂度O(N) 空间复杂度O(1) 2.4.2删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/ 说明一下思路 方法一 1. 设置一个计数记录从前往后遍历时遇到的不同元素的个数 由于不同的元素需要往前搬移那count-1就是前面不同元素 搬移之后最后一个元素的位置下一次在遇到不同元素就应该 搬移到count位置 2. 遍历数组如果nums[i]与nums[count-1]不等就将nums[i]搬移 到nums[count]位置不同元素多了一个给count 3. 循环结束后返回count 2.4.3合并两个有序数组
https://leetcode.cn/problems/merge-sorted-array/description/ 说明一下思路 方法一 解题思路: 1. 从后往前遍历数组将nums1和nums2中的元素逐个比较 将较大的元素往nums1末尾进行搬移 2. 第一步结束后nums2中可能会有数据没有搬移完将nums2中剩余的元素逐个搬移到nums1 时间复杂度O(mn空间复杂度: O(1) 2.5顺序表的问题与思考 • 中间/头部的插⼊删除时间复杂度为O(N) • 增容需要申请新空间拷⻉数据释放旧空间。会有不⼩的消耗。 • 增容⼀般是呈2倍的增⻓势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插⼊了5个数据后⾯没有数据插⼊了那么就浪费了95个数据空间。 思考如何解决以上问题呢 接下来请移步单链表进行单链表的学习让我们对于上述问题提供解决方案。 单链表SList
结语
穷且益坚不坠青云之志。 在这个充满诱惑的年代希望读者能够坚定本心矢志不渝。 高中第一个我的恩施才哥跟我说过 加油
