@coder-pig
2021-02-24T15:25:32.000000Z
字数 1086
阅读 867
2020
要点:简单了解下概念,起码得知道「时间复杂度」和「空间复杂度」
顺序表是「线性表」中的一种,而线性表的简单介绍如下:
「顺序表」和「链表」都属于线性表!顺序表具有如下特点:
基本操作中的难点是「插入」和「删除」通过动图了解一波流程:
从图片不难看出「插入」的要点「从后往前移动元素(赋值,i+1=>i),直到遇到插入下标」
从图片不难看出「删除」的要点「从删除位置开始,从前往后移动元素(赋值,i=i+1),直到到达表尾」
Tips:如果无法理解,可自行执行动画试试,或者用实物模拟帮助理解~
注:常用数组来描述顺序表,但要注意,线性表是从1开始算的,而数组下标却是从0开始的,
所以要访问表中第i个元素,需要减1,具体可在代码中提现!
先上运行结果:
具体代码实现(SeqList.kt)
问题描述:
已知有A、B两个顺序表,元素按照从小到达排序,现在要你求两个表的并集C,且C中的元素页要按照从小到大排序,不能修改A和B中的数据。
解题思路:
- Step 1:构造表C,长度为A+B的元素个数之和;
- Step 2:定义两个指针(下标),用于A和B元素寻址;
- Step 3:遍历,A<B 插入A元素、A下标++ => 插入B元素、B下标++,知道其中一个下标到尾;
- Step 4:剩下的元素要么是表A的,要么是表B的,直接循环遍历
- Step 5:为表C定义代表前后两个指针(下标),遍历剔除重复元素
运行结果:
具体代码实现(UnionQuestion.kt)
源码地址:https://github.com/coder-pig/DataStructureNote