粉丝4108获赞3.2万


数据结构顺序表, 这次课我们给大家讲解一下顺序表在程序里面的话呢,我们经常会需要呢将一组相同类型的数据元素呢作为一个整体啊,对它进行管理或者使用。 比如说我们会将一组相同类型的数据元素作为一个函数的参数呢传进去, 在函数题里面,对当前这个数据元素呢,可能会增加,也可能会删除,最后将这一组相同类型的数据元素呢对他进行返回。对于这一组需求,最简单的解决方案呢,就是将这样一组元素呢看成是一个序列,我们对这个 序列呢要进行组织,这样的一组序列元素组织形式,我们可以将其抽象的认为呢就是信息表,那信息表和我们当天这个顺序表有什么样的关系呢? c c 表的话呢,就是母类元素的一个集合,它呢记录的元素之间的一组存储关系。 c c 表的话,它是数据结构最基本的一个, 而且它的使用呢是非常广的,经常呢被用作我们更复杂的数据结构实现的基础。 根据这个信息表的实际存储方式分为呢两种实现的模型,其中一种呢就是我们的顺序表,另一种的话呢就是我们的列, 所以说顺序表的话呢,它是以序列啊或者是数组一种呢存储形式的一个线性表,它里面的话呢就是将元素呢顺序的存放到一块连续的存储空间里面, 元素阶的顺序关系呢,由他们的存储顺序自然表示, 这时候我们就肯定会想到我们的列表 list 以及我们的 top, 对非常好啊,我们的 list 和我们的 top 呢,就是我们 pass 呢采用数据表的实现技术, 企图 list 和 top 宝,它有个区别,就是我们的 top 宝呢是不可变类型,它呢不能对 它里面的元素呢进行更改,所以说 top 的话呢,它是一个不变的顺序表,其他的获取元素便利和历史的使用呢,是非常类似的, 那我们对 list 里面可以对它进行删除元素,也可以对它进行添加元素,那它是怎么样实现的呢? 接下来我们看一下顺序表增加元素,比如说我们要为这个顺序表呢增加一个幺幺啊,幺幺幺这一个元素。 当前呢看一下这个图,我们增加元素,在 list 里面我们有 apart 方法,也有音色的方法,如果 apart 方法我们知道呢,它是在当前列表的末尾呢最佳。如果是 insta 的话呢,需要呢传入当前你是在哪一个位置呢进行插入。首先呢我们看一下在列表的末尾呢进行最佳元素, 这一包有一个 max, max 代表盗窃列表里面最大的存储元素呢是八个 number, 现在存储呢是五个, 当前他已经存储啊零一二三啊,这个位置上面呢已经有元素了,我们要在末尾追加我们的幺幺幺啊,直接呢在四啊这一个位置呢,当前添加我们的元素幺幺幺即可, 可以看到啊,它在末尾呢直接啊推最佳。如果呢,我们是要将呢当前这 这个元素插入到当前列表里面,我们知道呢,当前这个 list 列表的话呢,它是保存我们这个顺顺序的, 在一道接顺序表里面,在指定位置进行插入的时候呢,由非宝序啊还有我们的宝序列表,我们先看了一下宝序,这个非宝序的话呢,不常见啊,经常我们使用的是宝序元素进行插入, 比如说我要在呢,所以一处呢继续插入我这个幺幺幺,我在一处继续插入的时候,一处的话呢已经有元素啊六百九十三, 而且呢这个顺序还不能乱,也就是我插入完以后呢,也就是第一个幺三二八,第二个是幺幺幺,第三个是我们的六九三,第四个二五二九,第五个幺 幺五四这样的顺序。所以说我们插入的时候呢,他呢进行的时候呢,就是先将我们当前的 在第三个所引处的幺五四,把它呢移动到了第四个啊,移动到第四个,在第二个上面的二五二九呢移动到了第三个, 在第一个锁引处的六九三移入到了我们的第二个,这时候将锁引啊一这个地方的位置呢空出来。最后呢我们将幺幺幺呢放进去, 这样就在指定位置呢进行插入,我们可以看到呢在指定位置进行插入的时候呢,我们要呢将当前他后边的元素呢依次的 向后移一个,向后移一个,如果我现在插入的时候呢,比如说我插入的时候呢,要将幺幺幺啊插入到我们 所以为零啊这一个地方,我们要将当前列表里面所有的元素呢都要向后移,首先移最后一个,再倒数第二个 到第三个,一直呢将当前你所引零处这个位置上面元素移动到所引一处,将幺幺幺呢插入到当前这个零这一个位置。 所以说在插入的时候,这个音 set 和我们这个 apart 它所用的这个时间啊,肯定是不一样的。那我们来分析一下, 如果呢是在尾部进行插入的时候,他这个时间复杂度直接呢在末尾追加,直接在当前啊锁引处呢,加上我们这个幺幺幺就可以了,所以说他的时间复杂度就是我们的 o 一。而如果的话呢,我们是在 指定位置进行插入的时候,比如说我们最快的我在头,也就是所以为零这个位置,他要将当前列表里面所有元素都要向后移动,比如说是 n 个移动呢 n 次,所以说他的时间复杂度呢,就是我们的 o n, 那我们等下可以看到呢,所有的时间尾部进行插入的时候要快,我们这个宝序元素指定位置进行插入,他就比较慢, 如果是非保序啊,这一组不常用,我们可以看一下,如果是非保序的话呢,你要在幺幺幺这个位置呢,继续插入的时候, 我们可以将幺幺这个地方这个元素放在我们当前尾部,再加幺幺幺呢,插入到一, 也就是他执行的第一步叫幺幺幺,也就是元不,所以我们一处的这个元素六百九十三放在末尾,再将我们的幺幺幺啊直接放到了所以为一啊这个地方就可以了,他呢执行两步啊,所以说他的时间复杂度也是 o 一, 但是我们列表拍摄里面的列表 list, 它呢要保持这个顺序,所以说指定位置插入它的时间复杂度就是 o n, 而尾部进行 插入它的时间复杂都是 o e。 我们再看一下删除元素,这个删除元素的时候呢,我们可以看到将幺幺幺啊这个元素进行删除,比如说 我先出删除啊,尾部啊,删除尾部,删除尾组尾部,现在的尾部元素,我们是幺五四进行删除的时候呢, 指尖 r 加幺五四这个地方的元素啊弹出把它清空,所以说他执行是一步, 如果呢,我们是在保序的情况下将我插入啊本人当前这个位置,所以唯一这个位置呢是我们的幺幺幺。我现在呢要进行删除的 时候呢,将,所以也就是二处的这个六九三要把它移到所以一处,把所以为三的二五二九这个元素呢移住到所以二处,最后把幺五四哎往上移, 也就是依次的最后呢幺幺幺啊,也就是被每一个元素呢进行覆盖,这样幺幺幺的话呢已经被删除, 我们可以看到呢,如果是在尾部删除,直接呢只写一步,所以说它这个时间复杂度也是我们的 o 一。 如果呢我们是在保序,而且进行删除指定位置上面这个元素的时候,我们要进行移位,如果我幺幺幺啊本来是 在头部的时候呢,我要将后面的这些元素呢依次的啊向前面呢移一,这样移的 n 点一次, 所以说它的时间复杂度啊,删除元素它的是 o n 啊,在保序的这一种情况, 那非宝旭这一组结块进行删除的时候呢,他直接啊将我们最后一个元素呢直接覆盖到我们指定要删除这个位置啊,他也是 o 一,但是非宝旭这一组呢使用比较少,我们这 当前列标里面啊指定元素上面删除还,而且也是进行一位,所以说 python 里面标准的这个类型 list 呢,就是一个元素 个数可变的,我们的线线表可以呢插入也可以进行删除,而且的话呢他的顺序是保持不变的,所以说他是保序的, 我们可以呢看到宝旭这一组情况的话呢,在插入和删除的时候,他如果呢你删除的这个位置插入的位置不一样,他的执行效率呢是不一样的。 比如说我们这个插入 apen 的插入和音色的插入,它的效率是不一样的。 在下次课的时候呢,我们呢测试一下当前 apend 和 insert 它执行的效率。