【Educoder作业】C&C++线性表实训

第一次接触链表的话，可能会有疑惑。疑惑在于它到底比数组强在哪里。写完这次实训可能就会感受到，或者写了这10个题还是没有头绪，本篇结尾我们就稍微聊一聊。

T1 顺序构建线性表

这个题可以说是定了整个实训的基调，结构体里是包含了一个本身的数据datadatadata和一个指针nextnextnext，我们就是用这两个东西来构建链表的。
同时，我们默认：最后一个元素的nextnextnext为NULLNULLNULL。

#include "linearList.h"node *insertTail(node *h, node *t)
{// 请在此添加代码，补全函数insertTail/********** Begin *********/node *p = h;if (h == NULL) return t;while (p -> next != NULL) p = p -> next;p -> next = t;return h;/********** End **********/
}

T2 逆序构建线性表

这是容易的，因为我们构建的是单向链表。

#include "linearList.h"node * insertHead(node *h, node *t)
{// 请在此添加代码，补全函数insertHead/********** Begin *********/t -> next = h;return t;/********** End **********/
}

T3 排序构建线性表

想起来是比较容易的，我们考虑最后的情形：找到当前数据存放的位置，然后把当前数据塞进这个位置里。
那么，我们就同时需要p→nextp\rightarrow nextp→next和ppp，在写whilewhilewhile的时候也就会麻烦一点。

#include "linearList.h"node * insertSort(node *h, node *t)
{// 请在此添加代码，补全函数insertSort/********** Begin *********/node *p = h;if (h == NULL) return t;if (t -> data <= h -> data) return insertHead(h, t);if (h -> next == NULL) return insertTail(h, t);bool flag = false;while (p -> next -> data <= t -> data) {if (p -> next -> next == NULL) {flag = true;break;}p = p -> next;}if (flag) return insertTail(h, t);t -> next = p -> next;p -> next = t;return h;/********** End **********/
}

T4 查找元素

其实，知道了T3T_3T3​怎么做，剩下的都比较容易了。
只需要从表头开始顺序枚举链表，然后查找即可。

#include "linearList.h"node * search(node * h, int num)
{// 请在此添加代码，补全函数search/********** Begin *********/node *p = h;if (h == NULL) return NULL;while (p != NULL) {if (p -> data == num) return p;p = p -> next;}return NULL;/********** End **********/
}

T5 删除指定位置的结点

由于是删除指定位置，所以最后一步的情形一定是找到了这么一个ppp，然后有p→next=p→next→nextp\rightarrow next=p\rightarrow next\rightarrow nextp→next=p→next→next，所以我们的whilewhilewhile也就会更复杂一点。

#include "linearList.h"node * delAt(node * h, int i)
{// 请在此添加代码，补全函数delAt/********** Begin *********/node *p = h;if (!i) return h -> next;int cnt = 1;while (p -> next -> next != NULL) {if (cnt == i) {p -> next = p -> next -> next;return h;}cnt ++ ;p = p -> next;}p -> next = NULL;return h;/********** End **********/
}

T6 删除包含特定数据的结点

凡是这种删除的都会复杂一点，和T5T_5T5​一样，whilewhilewhile的判断会比较复杂。

#include "linearList.h"node * delHas(node * h, int n)
{// 请在此添加代码，补全函数delHas/********** Begin *********/if (h -> data == n) return h -> next;node *p = h;while (p -> next -> next != NULL) {if (p -> next -> data == n) {p -> next = p -> next -> next;return h;}p = p -> next;}if (p -> next -> data == n) {p -> next = NULL;return h;}/********** End **********/
}

T7 线性表长度

这个就比较容易了，从表头开始遍历然后计数即可。

#include "linearList.h"int listLength(node * h)
{// 请在此添加代码，补全函数listLength/********** Begin *********/int ans = 0;while (h != NULL) ans ++ , h = h -> next;return ans;/********** End **********/
}

T8 线性表应用一：栈

栈是一种数据结构，特点是FILO(FirstinLastout)FILO(First\ in\ Last\ out)FILO(First in Last out)。
但是用链表实现栈显然是没什么必要的，篇尾我们会讨论这个问题。

#include "mstack.h"
// 函数empty：判断栈sk是否为空
// 参数：sk-栈
// 返回值：true-sk为空，false-sk不为空
bool empty(intStack sk)
{// 请在此添加代码，补全函数empty/********** Begin *********/return sk == NULL ? true : false;/********** End **********/
}
// 函数pop：弹栈
// 参数：sk-栈，传引用，弹栈可能会改变sk的值
// 返回值：弹栈的弹出的整数，如果栈空，返回-1
int pop(intStack &sk)
{// 请在此添加代码，补全函数pop/********** Begin *********/intStack p = sk;if (empty(sk)) return 0;if (p -> next == NULL) {int re = p -> data;sk = NULL;return re;}while (p -> next -> next != NULL) p = p -> next;int re = p -> next -> data;p -> next = NULL;return re;/********** End **********/
}
// 函数push：压栈，将整数n压入栈sk中
// 参数：sk-栈，传引用，压栈会改变sk的值，n-要压栈的整数
// 返回值：无，采用链表实现栈，只要还有内存，压栈都会成功
void push(intStack &sk, int n)
{// 请在此添加代码，补全函数push/********** Begin *********/intStack p = sk;if (empty(sk)) {sk = new node;sk -> data = n;sk -> next = NULL;return;}while (p -> next != NULL) p = p -> next;p -> next = new node;p -> next -> next = NULL;p -> next -> data = n;/********** End **********/
}

T9 线性表应用二：队列

队列的特点是FIFO(FirstinFirstout)FIFO(First\ in\ First\ out)FIFO(First in First out)
实现起来用前面的函数，显然也是容易的。

#include "mqueue.h"// 函数queueEmpty：判断队列iq是否为空
// 参数：iq-整数队列
// 返回值：true-队列iq为空，false-iq不为空
bool queueEmpty(intQueue iq)
{// 请在此添加代码，补全函数queueEmpty/********** Begin *********/ return iq == NULL ? true : false;/********** End **********/
}
// 函数enQueue：将整数num入列到iq
// 参数：iq-整数队列，传引用，入列有可能改变队列头指针，num-入列的整数
// 返回值：无，只要还有内存，入列总会成功
void enQueue(intQueue &iq, int num)
{// 请在此添加代码，补全函数enQueue/********** Begin *********/node *t = new node;t -> data = num;t -> next = NULL;iq = insertTail(iq, t);/********** End **********/
}
// 函数deQueue：出列
// 参数：iq-整数队列，传引用，出列有可能改变队列头指针
// 返回值：出列结点的数据，如果队列为空，返回-1
int deQueue(intQueue &iq)
{// 请在此添加代码，补全函数deQueue/********** Begin *********/if (queueEmpty(iq)) return -1;int re = iq -> data;iq = delAt(iq, 0);return re;/********** End **********/
}

T10 线性表应用三：集合

集合是个很强大的数据结构，在C++C++C++的STLSTLSTL里也有集合，只不过那里的集合用的是红黑平衡树实现的，是一个很强大的数据结构。
这里的集合就很简单了，只能保证有序且不能重复，多余的操作复杂度都不能保证。

#include "mset.h"// 函数unionSet：求集合a和b的并集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的并集）
intSet unionSet(intSet a, intSet b)
{// 请在此添加代码，补全函数unionSet/********** Begin *********/node *re = NULL;node *p[2] = {a, b};// printList(p[0]), printList(p[1]);for (int i = 0; i < 2; i ++ ) {while (p[i] != NULL) {if (search(re, p[i] -> data) == NULL) {node *mdl = new node;mdl -> next = NULL, mdl -> data = p[i] -> data;re = insertSort(re, mdl);}p[i] = p[i] -> next;}}return re;/********** End **********/
}
// 函数intersection：求集合a和b的交集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的交集）
intSet intersection(intSet a, intSet b)
{// 请在此添加代码，补全函数intersection/********** Begin *********/node *re = NULL;node *p = a;while (p != NULL) {if ((search(b, p -> data) != NULL) && (search(re, p -> data) == NULL)) {node *mdl = new node;mdl -> data = p -> data, mdl -> next = NULL;re = insertSort(re, mdl);}p = p -> next;}return re;/********** End **********/
}
// 函数addElement：在集合is中增加元素num
// 参数：is-集合，num-要增加的元素
// 返回值：无
void addElement(intSet &is, int num)
{// 请在此添加代码，补全函数addElement/********** Begin *********/node *t = new node;t -> next = NULL, t -> data = num;if (search(is, num) == NULL) is = insertSort(is, t);/********** End **********/
}

写完了整个实训，我们来聊一聊链表。很多人也跟笔者探讨过这个问题，观点大同小异——不理解这个链表有什么用。
这就涉及到复杂度的问题，这个我之后单独出一篇BlogBlogBlog聊一聊。
比如说，我们想在数组的某个特定位置访问第iii号元素，直接访问ArrayiArray_iArrayi​即可，是瞬间完成的，也就是O(1)O(1)O(1)的。
但是链表不行，他需要从表头开始计数，直到计数器到达了iii，如果每次都是查找最后一个元素，那么这个操作就和表的长度有关，我们称之为O(n)O(n)O(n)的。
现在，数组的表现是优秀的多的。
这时我们考虑插入往指定位置插入一个元素，数组的话需要把这个元素后边的每个元素都向后挪一个位置，复杂度就是O(n)O(n)O(n)的，但是链表只需要改变他前一个元素的指针就可以完成这个操作。
这就是链表的意义，某些操作用链表完成会简单很多。
还有很多，比如动态分配空间这个事儿，链表也是很容易就能做到的。C++C++C++里有一个STLSTLSTL叫动态数组vectorvectorvector，使用的时候就是一个可以自动分配空间的数组，它的内部实现就是用指针+链表的思想实现的。
看到这，可能会有疑问：有没有一种数据结构能兼顾数组和链表的有点呢？既可以短时间访问元素，也可以短时间插入、删除元素？
当然是可以的，一些强大的数据结构很容易做到，splaysplaysplay和非旋转TreapTreapTreap为代表的平衡树就可以。
这里我们介绍容易理解的块状链表。
我们将一个长度为nnn的数组分为n\sqrt nn​个连续的块，显然每个块里都有n\sqrt nn​个元素。每个块内是数组，块与块之间用链表的思想连接起来，这个数据结构就是块状链表。
比如查询：我们只需要从表头开始，一次跳n\sqrt nn​个元素，如果发现了某个元素在某个块里，因为块是数组直接O(1)O(1)O(1)即可，复杂度就是整体链表访问的复杂度O(n)O(\sqrt n)O(n​)；比如插入一个元素，只需要找到了对应的块后，挪动块内的元素即可。因为在某个块里的插入一个元素，并不会影响其它块，因为块与块之间只链表连接的，所以复杂度也是O(n)O(\sqrt n)O(n​)的。
就聊这么多，其实每个数据结构总有它大放异彩的地方，即使它的作用只是引出一个更强大的数据结构。
写在篇尾不写在篇头，意义是读者又需要自取，大多数是不喜欢看这些引申东西的（小声