小蝠猫学算法#4——[线性表表示]

文章寄语

命运负责洗牌和发牌，而我们只能出牌。
　　　　　　　　　　　　　　　　　　　　—— 叔本华<<人生的智慧>>

引言

数据结构笔记第四篇。线性表的顺序表示[考纲有此内容]

知识点大致按照《Hello!算法》书籍进行。因为数据结构与算法在非常多的考试中都有。

本人自知学疏才浅，一定有许多错误，恳请批评指正。

下面是几个上述提到的链接：

《Hello!算法》网页版全国计二级官网洛谷官网-刷题可用

星空如此灿烂，灯塔与之响应。出发吧

第四节线性表的顺序表示

线性表定义

线性表是具有相同数据类型的有限序列(想成数组).特点如下

当表长为0时,即表中没有元素,称为空表.
第一个元素称为表头元素，最后一个元素称为表尾元素。
什么直接前驱直接后驱，简单来讲就是除了表尾，每个元素的后面都有且仅有一个元素；同理除了表头，每个元素的前面都有且仅有一个元素。即具有逻辑上的顺序性。
因为相同数据类型，所以每个元素占用的空间相同。
仅仅讨论逻辑性，即每个元素的位置，逻辑关系等。而不关心这些元素到底是什么。

线性表的基本操作

主要操作如下：

InitList(&L);初始化表，构造一个名为L的空线性表。涉及对L实际修改，需要加上引用。
Length(L);统计表L中元素的个数。也可以说是长度。
LocateElem(L, e);定位元素，即在L中按值查找值为e的元素。
GetElem(L, i);获取元素，即给定i，在L中按位获取第i位的元素。
ListInsert(&L, i, e);插入元素，在L中的第i位上插入元素e，一般是前插。涉及对L实际修改，需要加上引用。
ListDelete(&L, i, &e);删除元素，删除L中的第i位元素e，并返回e的值。涉及对L实际修改，需要加上引用。e主函数应该有东西绑，不太理解。
PrintList(L);按前后顺序打印输出L的所有元素值。
Empty(L);判断L是否是空表，即元素个数是否为0。空表返回1，否则返回0。
DestroyList(&L);销毁线性表，释放内存(抽屉里的空间)。涉及对L实际修改，需要加上引用。

笨蛋笔记

关于C++中引用符号’&’：

void swap(int &x, int &y) {
  int temp = x;
  x = y;
  y = temp;
}
int main() {
   int a = 5;
   int b = 10;
   swap(a, b);
   return 0;
}

在这个例子里，想要实现的功能是交换这两个数字的值。一般情况下，我会写 int swap(int x, int y)。

但是写到最后发现，咦，函数不是只能返回一个值吗？不能返回两个值。如果返回两个值，需要用到坐标类型的结构。相对于只是简单交换两个数的问题，显然是有点小题大做。

而不写函数直接在主函数内的操作的话，这确实是一个好主意。但是，如果需要交换数字的地方很多，总不能每个地方都写吧。我从来不写重复的代码x。

补充说明1：c++引用号

后来我发现，c++里面有一个 &符号。其实是一种元素别名。对于上面的交换数字的代码，我想用自己的语言解释解释。

首先在主函数内定义好了a和b的值，然后使用 swap(a, b)传入a和b的值。在 void swap(int &x, int &y)内开始处理。

因为 &引用号是一种元素别名，他需要一个东西来绑定。上述这两句代码，使用了 &后，x即和a永久绑定，y即和b永久绑定。

在函数内部 void swap(int &x, int &y)中，对x，y的修改，其实就是直接对a，b进行了修改。对引用的操作等同于对原始变量的操作。

所以我的上述问题就解决了。函数内的x，y将直接对主函数的a，b进行覆盖改写，甚至不用返回值，使用void即可。复杂性大大大降低。

补充说明2：引用注意

x，y是变量，所以他们也当然需要声明，不过声明时就应该直接和原始变量绑定（初始化），不能改绑，也不能先声明后绑定(初始化)。

如果是类似于 void swap(int &x, int &y)，将引用作为函数参数时。上一句话也说了，类似于 int &x相当于直接定义x了，下面直接用就行。

还有一点，有时候不需要用到引用号。简单来说就是，如果涉及到对绑定这组东西的实际修改，就都要加。如果没有实际操作只是访问，查找什么的，就不用加。

他不占用额外内存空间，而且安全易懂。所以，随便用。

题外闲话3：c++引用和c指针

和c语言的指针不同，指针的本质是一种数据类型，用于存储内存地址。指针比较危险，因为他是直接操纵底层，而且没有什么保护。

如果是空指针，就像员工手上有个物品，但他不知道放在哪个抽屉里(未指向任何存储单元)。虽然三思后行(先置空后赋值;先拿在手上想好了再放进去)的方法很对，但还是很危险。

如果是野指针，就像员工把物品硬塞到本来已经有东西的抽屉。因为抽屉的某部分已经放不了了(不可用内存区域)，硬塞进去后期拿这个东西(操作此元素)的时候就可能会炸了。

因为计算机是非常死板的，他只会遵守命令，多余的事他都不会干。发生以上两种事情的时候，就要给他发出命令，给他解决办法，以面对不知道怎么办的困境。这个就不展开了。

顺序表定义

线性表

顺序存储即顺序表，其将相同类型的元素顺序放置在一个大块，连续的内存中。元素在顺序表中的位次和在内存中的相同。如果某元素在顺序表中是第二个元素，那么在内存中(仅在分配的这块上面)也是第二位。

这个位次称作为元素在这个表中的”索引”。这个特点书上又称作为”逻辑顺序与其存储的物理顺序相同”

因为是相同元素类型，所以分配给每个元素单元的内存储存大小都是相同的。又因为它类似于等差数列的特性，可以通过索引和首地址轻松的算出任何元素的内存地址。

假设索引从0开始，首元素地址为00，每个元素分到4字节：

第0个元素内存地址为：00
第1个元素内存地址为：00 + 4 * 1
第n-1个元素内存地址为：00 + 4 * (n - 1)

所以我们可以任意的算出任何内存地址：首元素地址 + 元素大小 * 当前元素索引.这个任意算内存地址的性质叫”随机存取”,即随机元素都可以算出。

数组

数组是顺序存储的一种最常见的形式，他就是线性表。一维数组可以静态分配，也可以动态分配。

注意：

索引和位序是两种不一样的东西。位序更像是刚开始学不习惯从0开始，而用更好理解的从1开始。”座位”,这就是位序。索引就是数组下标，像是学了一段时间习惯了从0开始。这就是索引。

静态分配内存

所谓的静态分配，就是提前约定好这个顺序表(数组)的长度。一旦长度被确定好，因为同种类型元素，每个元素的内存空间都是相同的。现在总空间也被约定好了。总空间即元素个数 * 元素大小。

但是因为长度已经被约定好(比如说50)。如果此时对该数组的操作，导致出现了本该不存在的第51个元素。就像一栋楼只有5楼，坐电梯到6楼了。因为没有建造(数组没有定义)这个楼层，所以会导致恐慌。(程序报错)

这个报错就是常见的”数组越界”。 (ArrayIndexOutOfBoundsException) 解决办法也很简单，要不扩大数组，要不删除元素。一般都是扩大数组

Tips：

仅在C语言中，字符串数组的定义长度会包含结束符\0。意味着如果输入是5位，而长度定义也只有5位。因为包含1位结束符，他只能读取前面4位，从而导致第5位被忽略了。其他语言和数据类型不影响。所以我写c习惯数组长度+1（

动态分配内存

动态分配有一个单独的语句，它将提前申请一块内存，将这些元素存入。当顺序表占满后，如果还有元素存入，他可能会在原基础上扩或者重新申请。

就像是机构申请了一个有5层楼的住宅楼，每层2户，假设1户只住1个人。那么这栋楼就只能住10个人。当有第11个人想要住进来的时候，这时候有两种可能。

在原基础上扩展：最常用的办法，当没有违建，水电充足，空间充足的情况下，直接在加建几层楼就好了。只要和当地申请就好了(但是基本不可能xx都建好了怎么会让加建x)
重新申请：当因素限制或者没有空间了，可以重新申请一栋更大的楼。这栋楼可以有10层，把原来的住户强行转移后废弃原来的房子即可。(因为地皮(内存即抽屉)是有限空间，申请大概率驳回xx)

在C语言中，动态分配内存一般使用 malloc函数。当这块内存使用完毕时，如数组已经操作好了得出结果了，或是数组不需要了要销毁了，用 free函数释放该内存。不释放会导致内存泄露，让系统内存爆满，严重拖慢速度和性能。

一般来说都是报错的。除了 malloc函数，还可以使用 calloc函数动态分配内存(Ciallo～(∠・ω< )⌒☆)。

两者区别是：

前者malloc函数只有1个参数，直接申请开辟多少内存空间，单位是字节。空间值可能是随机的。
后者calloc函数需要2个参数，需要分开告诉申请个数和元素大小。同时会把空间值全部初始化成0。

相对下c++就直接用new函数实现。代表这是新的，。不过它们都需要指向当前数组的指针，还有限制最大元素量和记录当前元素防止其超过。

c语言的动态分配: 使用malloc函数开辟ElemType指当前元素数据类型，int或char这种。sizeof指获取当前元素大小。initsize指初始表长度。即对数组malloc了一个元素大小*个数的内存空间。

L.data = (ElemType*)malloc(sizeof(ElmeType) * InitSize);

c++语言的动态分配： 使用new函数开辟ElemType指当前元素数据类型，int或char这种。initsize指初始表长度。即对数组new了一个类型为ElemType初始个数为initsize的内存空间。

L.data = new ElmeType[InitSize];

优点①：可以任意的算出任何内存地址，即可以随机存取。在常数级时间内就可以找到。
优点②：存储密度高，因为只存值，不存其他别的。
缺点①：在中间添加或删除元素时，会导致牵一发而动全身。需要把后面的元素全部前移或后移，非常的麻烦。
缺点②：前面笔记做过了，内存空间就像一个抽屉，而这个抽屉的空间是有限的。数组就像是一个大盒子，能放进去，但是不能最大化利用空间。碎片率很高(空隙很多)，不够灵活。而且他还要连续的大块空间，中间要是有什么东西挡着就放不进去了。除非内存整理，把这个移到别的地方去。不然就放不进去，要另寻其他的内存空间。

顺序表的基本操作

Ⅰ.初始化元素

初始化元素有两种方式，一种为给定初始值，一种为无初始值。

当未指定初始值时，大部分编程语言会默认为0。但是在c语言中，因为不指定初始值的情况下是随机值。所以当进行数值操作时，可能会有意想不到的结果。

在内存方面，静态分配内存已经提前帮数组申请好了空间，元素仅需要一个一个入住即可。初始时数组长度为0。

而动态分配内存是暂时先申请定义内指定的内存空间。初始化时长度为0。当满了以后，扩容数组最大长度，一般增量和原来一致，扩成原来两倍。

Ⅱ.访问元素

前文写过笔记了。数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。

发现数组首个元素的索引为0，这似乎有些反直觉，因为从1开始计数会更自然。

但从地址计算公式的角度看，索引本质上是内存地址的偏移量。首个元素的地址偏移量是0，因此它的索引为0是合理的。

访问元素的时间复杂度为常数级。

Ⅲ.遍历元素

可以用索引，即下标遍历，也可以直接遍历[for和foreach函数]。

Ⅳ.插入元素

这是数组的缺点，因为元素在数组中和在内存中均是”连续存储”，什么是”连续存储”，就是数组中间不能有空隙，不能断，不能跳。就和排队一样

因为这个特性。当如果我们要在学校排队是插队，后面的人必须要全数往后退一步，腾出位置才能让其插入。数组里面也是一样。

但是有一种情况，因为数组是有界(长度固定)的，他被限制在一个房间里，如果最后一个人已经贴着后墙壁了，他就退不了了(空间已满)。

这种情况就会插入失败，并且有两种状况。一种是导致尾部元素数据丢失，一种是直接报错。

//对数组L的第i位插入数据类型为ElemType的元素e
bool ListInsert (SqList &L, int i, ElemType e)
{
    //位序从1开始，所以范围是1~长度+1。为何是长度+1？因为可以加在最末尾。
    if(i < 1 || i > L.length + 1)
        return false;
    //length函数记录当前数组元素个数。如果大于等于最大值，表明数组已满无法存入。实际上是可以的。
    if(L.length >= MaxSize)
        return false;
    //因为是添加元素，插入元素位置的后续元素全部需要后移，所以倒序遍历。
    //从最后一位开始遍历到指定位置i，将后一位的值全部变成前一位，完成元素值后移
    for(int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    //现在已经腾出位置了，放入e。因为本来i-1位是有数字的，现已被转移到了i位。
    L.data[i - 1] = e;
    //顺序表元素总量+1
    L.length ++;
    return true;
}

如上述所讲，如果没有 if(L.length >= MaxSize)语句的话，而现在 L.length == MaxSize会产生两种状况。

因为 L.data[j] = L.data[j - 1];代码，在for里限制了j的最大值始终是数组长度。这时候最后一位(j位)就会被前一位j-1位覆盖掉，最后一位数据丢失，就没了。

然而如果把 L.data[j] = L.data[j - 1];代码换成 L.data[j + 1] = L.data[j];呢？虽然看起来功能相同，但是在数组L中，第length+1位是不存在的(与if的位序不能混淆)，这时候就会报错。

注意：

为防止忘记，= 赋值语句，是把右边的值赋给左边，左边会变右边不会。

对于书上的问题：

if语句用length+1是因为其是顺序表位序，他从1开始计数，原数组的最后一位就是length。可以添加在最后一位后面，所以是length+1。

而for语句中是数组索引，他严格来说是一个偏移量。偏移量一般从0开始计数，所以原数组的最后一位就是length-1。可以添加在最后一位后面，所以是length

而添加元素最坏的情况是在第一位数前面插入，那么所有元素都要往后移一位，操作了n次。所以是线性阶。

因此顺序表插入元素算法的时间复杂度是线性阶

Ⅵ.移除元素

和添加元素相同，只不过是元素前移。和插入元素几个不一样的点的话，我感觉是以下几点：

① if语句中现在是length而不是length+1。因为是删除元素，他可以在最后一位删除。但是他不会干出删除最后一位的后一位这种奇怪事。
② 队列元素-1，不同考虑队列满。所以没有第二个判断。
③ 删除某个位置上的元素相当于那个位置上的元素已经没有用了，直接用后面的元素覆盖，所以是 L.data[j - 1] = L.data[j]。前一位被后一位覆盖了。
④ 总元素个数-1，而不是+1。

和添加元素一样，但是现在只有一种情况了。

因为最后一位的前一位j-1被最后一位j覆盖了。现在倒数第二位就是最后一位的值。那么最后一位的值其实就是多出来的，这个值没有意义。为了省力，我们也不用特意去操作这个数。

和添加元素一样，在头部删除元素，后面的值全部要前移，操作n次。所以是线性阶。

因此顺序表删除元素算法的时间复杂度是线性阶

Ⅶ.查找元素

这里指按值查找，因为最坏情况需要全部遍历一遍才能找到，所以也是线性阶。

不过按序号查找很简单，因为有随机读取的特性，所以可以做到常数阶。

Ⅷ.扩容元素

因为数组扩容后，这些扩容的空间不可预测，没人知道扩容以后，这些空间是不是能用的。就像塞在抽屉里的东西一样，我不知道他变大了以后会不会把抽屉撑爆，所以不安全。

所以一般不会在原基础上扩展，而是重新申请，也是书上的观点。数组的长度是不可变的，只能通过重新建立一个更大的数组，把原来的元素全部复制过去来实现。

因为复制转移要全部遍历一遍，所以也是线性阶时间复杂度。而且在数组元素个数巨多的情况下更是耗时比较离谱

顺序表的优缺点

很简单，前面写过好几次了。优点是只存数值，密度高。支持随机访问。还有一个书上写的*缓存局部性(数组加载时还会加载周围的数据)*。

缺点也很明显，增删查都是线性阶。元素很多的时候效率较低。而且长度基本上不可变，扩容需要另开一个复制过去。同时多出来的这几个位置就造成内存浪费了。

总结

文章结语

我们现在所做的，只不过是我们自认为动态规划中的贪心罢了。
　　　　　　　　　　　　　　　　　　　　——博客园某用户

笔记完毕编辑完毕时间CST 7.18 22:55

最后编辑时间8.15 23:40

蝠池茶园