线性表总结（数据结构C++，大二下写，初学者）

这段时间，我学到了这门课的第一种数据结构——线性表。关于线性表的知识，我总结为三方面：课本上学到的知识、上机实现课本上的例子的过程所学到的知识和力扣做题学到的知识和技巧。

顺序表

线性表中第一个学到的是顺序表，为此我翻了一下课本。顺序表，顾名思义，是线性表的顺序存储结构。顺序表是以数组为基础实现的，其实就是在数组的上面加了一层函数和类的壳，方便实现插入、删除和查询等操作。首先定义一个顺序表的类，其私有成员有存元素的数组(data)和顺序表的长度（length），顺序表相当于一个大数组，构造函数时传入一个小数组，将小数组的元素值依次赋值给大数组，可以看出顺序表有一段空闲的内存空间。切记，构造时给定的数组元素个数和以后要插的元素个数之和不能大于初始定义的顺序表的存储空间。还有就是，顺序表的内存空间大小一旦定义之后就不能再修改。紧接着就是顺序表的各项功能：便利操作，按位查找和按值查找，前三项操作都很简单，不必赘述。插入操作，将所要插入的位置（第i位）之后的所有元素后移，然后把要插的元素值放到该位置上，具体的实现是从data的第length位置开始，将前一个元素的值赋值给后一个，直到第i-1位的值赋值给第i位为止。哎，到这里就有人会问了，你把第length-1位置的值赋值给第length位置，那length位置的值怎么办？？？在此就不得不提到顺序表的一个细节，明面上顺序表元素序号是从1开始的，但本质上还是和数组一样，是从0开始的（故写函数时，参数为i位，函数内对i-1位进行操作），所以在代码的实现过程中，我们对第i位进行操作，实际写的时候是写的i-1，所以长度为length的顺序表，第length位实际上是空的，而操作（直到第i-1位的值赋值给第i位为止），其实是将第i-1位空出来，然后插入。删除操作，同插入操作一样，只不过是前移（第i-1位的数被第i位赋值），这里就不在赘述了。

顺序表的所有功能本人均已调试完成并成功正确的运行了，并将删除操作升级为删除顺序表中所有值的x的元素！

单链表

紧接着在线性表中学到的就是单链表，这是线性表中的重点。首先我们要定义一个结构体，包含数据和指针。然后就是链表类，其中包含插入、删除、查询等基本操作。还有构造函数和析构函数（与顺序表不同，要手动写代码释放空间），其中构造函数有两种方法可以初始化链表，头插法和尾插法，在说这两种方法之前，我想先说一说头结点，头结点是用new动态申请的一个内存空间，其数据类型是上面定义的结构体类型的，头结点不是一个固定的结点，只要动态申请一个空间，将next指向NULL,他就可以成为头结点，头结点可以方便我们初始化链表，同时可以方便删除操作，没有头结点的话，第一个结点的删除就会变得复杂。

头插法

头插法，每次插入都插在头结点后面的位置，好处显而易见，插入的位置是明确的，有现成的指针，直接动态申请一个空间，赋值，让其next指向头结点的next,然后头结点的next指向新结点。注意，上面的顺序是固定的，刚学的时候我就在想，链表指针的改变是怎样进行的，我是这样理解的，在所有改变指针链的操作中，如s->next=first->next;等号左边的指针动作会销毁（即s和其next的点中间的指针链会断开），然后让s的next指针指向first->next所指的内容。

尾插法

尾插法，每次的插入都加在链表的末尾，这就需要有一个指针一直指向链表的最后一个位置，定义一个指向头结点的指针s，动态申请一个空间，赋值，让s的next直接指向新结点，然后再把新结点赋值给s（即让s指向新结点）。

插入操作

插入操作，按位查，定义指向头结点的指针，遍历链表，移动i次指针，将结点插入指针后；按值插，定义指向头结点的指针，遍历链表，移动指针，直到找到值为x的结点，通过指针操作插入。

删除操作

删除操作，按位删，找结点时和按位查类似，遍历到要删节点的上一个结点，定义临时指针指向要删结点，并记录要删节点的值，改换指针链，让其next指向next的next，释放临时指针所指节点的空间。按值删，不仅要找到要删值的结点，还要找到其上一个结点，所以我定义两个指针，一个指向头结点（p），另一个指向第一个结点(s)，用指针s找要删值的结点，则p就是其前驱结点，然后进行删除操作即可。从这里也可以看出头结点的优越性。

双链表

学完单链表之后，又对单链表进行拓展，学到了双链表（不仅有指向next的指针，还有指向前一个节点的指针，对于找前驱十分方便，其中包含的一个重要思想就是“空间换时间”。我重点讲一下插入、删除操作。插入操作，在结点p后插入结点s，先给s赋值，让其前驱指向p,后继指向p的后继，接着先修改p后继的前驱，让其指向s,再修改p的后继，让其指向s，即先修改前驱，在修改后继，如此就插入成功了。删除操作，三步即可，要删结点p，让其前驱的后继指向p的后继，然后让其后继的前驱指向p的前驱，顺序可变，最后释放p的空间即可），循环链表（首尾相连的链表），静态链表（是顺序表的升级版，解决了插入删除更改多个元素的繁琐操作，当存储大量元素时可以考虑使用）等。

上述就是我所学到的链表的知识，通过这些知识，我实现了课后实验二（用链表实现集合操作）和实验三（仓库的进货管理）

课后实验二（用链表实现集合操作）

实验二，用链表实现集合操作，要求有集合的，并、交、补集操作以及判断子集。在插入时要注意不能让链表有重复元素。首先我定义了一个查重函数，遍历链表，只要有重复的就返回true，否则返回false。然后就是初始化创建集合，我设定的是输入0时就结束，每次输入操作就会进行判重操作，只有不重复才进行插入，插入时用的尾插法。并集，函数的参数是两个集合，都是先定义一个集合类对象result，然后遍历集合L1和L2，用result调用插入函数（插入时也调用判重函数），将L1和L2的所有元素插入到result中，返回result。交、差集操作，函数的参数是两个集合，都是先定义一个集合类对象，然后遍历一个集合，用另一个集合调用判重函数，将满足条件的插入到新的集合中。判断子集时，遍历较短的集合，用较长的集合调用判重函数，只要有一个不重复，就不是子集。

课后实验三（仓库的进货管理）

实验三，仓库的进货管理，该题和上课所学的一元多项式求和有些类似，定义结构体的有三部分，价格、该价格电视机数量、指针。在仓库类中，我也和上一题一样，定义了判重函数，因为该题对重复的价格进行插入时，直接对该价格的电视机数量相加，而如果是不重复的价格，则要进行插入操作。

力扣做题

我在力扣做题时，学到的第一个思想是快慢指针思想，初见这类题时百思不得，学会快慢指针后，恨自己为什么想不到。例如：

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）要删除倒数第N个结点，就要知道其前驱节点，首先将链表加一个头结点，然后定义两个指针指向头结点，让一个指针（fast）向前移动N次，接着两个指针同时移动，直到fast指针到链尾，则另一个指针所指的位置就是倒数第N-1个结点，最后通过变换指针链进行删除操作即可。

876. 链表的中间结点 - 力扣（LeetCode）要找到链表的中间节点，可以用快慢指针的方法，在while循环中，当快指针非空，其next也非空时，快指针每次移动两个结点，慢指针每次移动一个结点,当跳出循环时，慢指针刚好就指向链表的中间结点。

141. 环形链表 - 力扣（LeetCode）判断链表是否有环，返回true/false，首先定义两个指针指向表头，在whie循环中，fast指针每次移动两步，slow指针每次移动一步，若链表中存在环时，则它们必定会相遇，只要fast==slow，就返回true，若退出while循环，就返回false。

142. 环形链表 II - 力扣（LeetCode）这个题不仅要判断链表是否有环，还要返回开始入环的第一个结点，首先要知道，从相遇点到入环点的距离刚好等于从链表头到相遇点的距离，根据这个思路来做题就简单多了。首先和上题一样找两个指针的相遇点，在满足fast==slow条件时，再定义一个指针pre指向链表头，让slow和pre同时移动，直到两者相遇，相遇点就是入环的第一个结点。另外，这个题还有一个解法，就是使用哈希表，这也是我第一次接触哈希表，不得不说，真的好用，只用指针遍历链表，依次将链表中的元素放入哈希表，只要遇到之前遍历过的元素，就返回该结点。

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

左边是我第一次写时使用的方法，我先遍历一次链表用vector记录链表中的各个元素，然后再一次遍历链表，当元素值的个数为1时即不重复时，将该节点的值赋值给一个动态申请的空间结点，然后将该节点加到一个空链表中，最终返回新生成的链表。

下面是舍友深夜给我发的代码，起初该代码没有head=k;且返回的是head。所以造成了当重复元素在首位时，会删不掉。经过讨论，发现是因为k->next=k1->next->next;让刚开始定义的k->next=head;改变了。而且我认为在没有头结点的情况下，是无法通过指针来删除第一个元素的，这也是链表中头节点存在的意义所在。又是一个充实的夜晚，学到了新方法。

83. 删除排序链表中的重复元素 - 力扣（LeetCode）相比与上一题就简单多了，首先定义一个指针指向链表头，while循环，保证指针所指的非空且next也非空，当指针所指的元素值与next所指的元素值相同时，改换指针链，让指向next的指针指向next的next，不相同时就移动指针。

86. 分隔链表 - 力扣（LeetCode）

思想：首先定义两个空链表，然后用两个指针分别指向这两个链表（通过指针的操作来修改与指针绑定的链表，且指针操作可以直接通过pre->next=dummy2->next;将两个链表连起来，因为pre一直指向链表最后一个元素，而dummy2表示的是第一个元素。最后返回时返回链表即可，此时仍是从第一个元素开始，而如果返回指针，因为指针所指的位置已改变，所以返回时就不会从第一个元素开始），遍历链表，元素值小于x，将该结点摘下，放入一个链表中，反之，放入另一个链表中。当然，也可以不摘链，直接让链表的next指向所要的结点，然后指针后移即可。

147. 对链表进行插入排序 - 力扣（LeetCode）

思想：当我还在为如何对链表进行排序苦恼时，我学到了插入排序。首先我们定义一个空链表dummy，然后遍历链表，在每次遍历时，都定义一个指针，指向dummy的表头（即每次都要从dummy头开始找），当指针所指的下一个元素的元素值小于该次遍历时head指向的元素值y时，指针移动，直到找到刚好比y大的元素x，然后将y插入到x前面即可。遍历完成之后，dummy就是排序完的链表。

1290. 二进制链表转整数 - 力扣（LeetCode）这个题我当时没做出来，看完答案后感觉很神奇，原来如此简单。首先 int res = 0，然后遍历链表，移动指针，res等于两倍的res再加上当前链表的元素值，这一步操作实现了让最高位的数（即最开始的元素值）乘以2的链表长度-1次方，往后的每一位一次递减，最后的值正好是每一位的二进制数转为十进制后的值之和。

21. 合并两个有序链表 - 力扣（LeetCode）首先定义一个空链表，再定义一个指针per指向该链表，要合并两个有序链表，我的思路是两个指针分别指向两个链表头，比较两指针所指元素值的大小，每次都让pre的next指向小的那个结点，然后小结点的那个指针后移，pre也后移。当两个有序链表的指针可能会有一个先到达最后，但没有到达最后的最多只会剩余一个结点，所以要加一个判空操作，如果指针没有指向NULL时，就让pre的next指向那个结点。

160. 相交链表 - 力扣（LeetCode）要找到相交的结点，首先要知道两个链表的长度，相交的结点只可能出现在链表长度相同的部分，前面超出的部分肯定不会相交。通过两个while循环就可以知道两个链表的长度，完成两个while循环后，参与遍历的两个指针肯定都指向两个链表的末尾，这时可以判断末尾是否相等，如果不等，则肯定不会有相交点。在确定链表长度后，通过移动较长链表的指针，只判断两链表相同长度的部分，同时移动两链表的指针，只要两指针相等时，就返回指针即可，指针所指的点就是两个链表的相交结点。

206. 反转链表 - 力扣（LeetCode）首先定义一个指针pre指向NULL,再定义一个指针cur指向链表头，在while循环中，先把cur的next存起来，然后让cur指向pre，在让cur指向pre所指的位置，最后让pre指向先前存好的结点。最终就能得到一个反转链表。

92. 反转链表 II 题解 - 力扣（LeetCode）这个题是上一个题的升级版，让我们在一定区间内反转链表，我刚开始的做法是用vector记录下给定区间内的元素值，然后再遍历这个区间，vector倒着输出，依次修改区间内的节点值。虽然提交之后也通过了，但我看官方解析上说，一般不让直接修改结点值，于是我就学习了一下官方用指针进行操作的方法。具体的实现思路是，生成一个带有头结点的链表，定义指针pre指向该链表，遍历链表，移动指针，让指针指向给定区间左边界的前一个结点，再定义一个指针cur指向区间左边界的结点和一个临时指针temp，让临时指针指向cur的下一个结点，然后将temp所指的结点摘下放到cur所指的结点前面,上述过程执行（区间内结点数-1）次，最终及得到了所需链表，该思想只需遍历一次链表，比我的方法好多了。

   在力扣做了一些题后，受益匪浅，学到了很多思想，也学到了一些做题技巧（例如：构造带有头结点的链表，while循环中临界条件的选择等），开阔了我的思路，果然，做题解决问题是一个不错的学习方法。