25考研王道数据机构课后习题-----顺序表链表部分

1.顺序表题目

下面的这个说的是：下面的哪一个是组成我们的顺序表的有限序列，这个应该是数据元素，n个字符组成的这个内容我们称之为字符，数据项表示的是我们的这个数据元素的这个基本的组成单位；

我们可以在这个学生表里面，把这个每一个学生的记录理解为这个数据元素，但是这一个数据元素里面包含我们的学生的姓名，学号，年龄等等之类的，这个每一个属性就是一个数据项，例如这个例子里面的这个姓名是一个数据项，学号是一个数据项，年龄是一个数据项；

这个题目我觉得并不是非常的严谨，因为这个题目问的是线性表，第一个选项就说了自己是集合，而且这个线性表是有限的这个序列，但是我们的这个C里面是所有的整数，这个就是无限多个的，邻接表是使用的多个链表拼接起来的，因此这个只能选择B了，但是这个B实际上是一个串，这个只是一个线性结构，说上是线性表也是不合适的，但是只有这个B是比较符合题目要求的；

这个是顺序存储的这个优点，首先这个可以进行插入和删除是没错，但是这个涉及到数据的挪动，很消耗时间，因此这个链表才是方便进行这个数据的插入和删除的首选；

这个存储密度大是我们的这个顺序存储结构的这个优点；

A非常很有意思：顺序表可以使用一维数组进行表示，但是顺序表和一维数组在这个逻辑结构上面不是一样的，因为我们的顺序表可以当作数组进行理解，但是两者并不完全等价，因为我们的这个数组是编程语言的内置的数据结构，但是我们的顺序表是抽象的数据结构，而且我们的顺序表可以灵活调整这个空间容量（即满了之后可以进行扩容的这个操作，但是我们的数组不可以）可见他们之间还是存在区别的，但是不完全等价，我们平常只是为了方便进行理解，把这个顺序表当作数组进行看待，但两者不可以划等号；

输出元素的值：这个显然是我们的顺序表直接输出更方便，我们的链表的话需要从这个第一个元素一直走到最后的这个元素，这个效率和根本没有我们的顺序表的效率高；

交换两个位置的元素的数值：这个就是我们的顺序表（调用这个temp进行交换，只需要三步），但是我们的链表，还是要从头进行走，走到交换的这个位置，这个过程就很浪费时间；

顺序输出n个元素，这个我们的顺序表和链表是没有优劣的，因此这个不符合题目要求；

我们删除元素，这个位置后的元素都需要移动，因此这个对应的时间复杂度肯定不是O（1),但是这个改变某一个位置的元素，这个时间复杂度就是O（1）；

上面的这个同样涉及到我们的删除元素，这个删除之后后面的元素需要全部向前移动，因此这个的时间复杂度肯定就不是O（1）,但是我们的获取元素就是O（1）,这个其实是可以和我们的上面的那个改变数据的值，一起进行记忆，两个的这个操作都是一样的；

2.链表相关题目

我们的这个是在数组的基础上面进行这个单链表的建立的相关的操作，这个一维数组如果是有序地，这个时候我们想要去建立这个链表，这个时候直接去插入就可以了，这个时间复杂度就是O（n)；

如果这个数组里面的这个元素是没有顺序的，这个时候我们的数组想要去变成链表，需要先进行排序，最快的这个排序的算法就是nlogn，然后是去进行这个插入是O（n)，这个合起来就是nlog n:

我们想要把这个n链表连接到我们的这个m链表的后面，这个时候我们首先需要做的就是去找到这个m链表的最后的这个元素，其实这个问题的时间复杂度主要就是取决于我们的这个m链表的长度，因此这个时间复杂度就是O（m);

这个题目考查的就是带有哨兵位的这个头结点和没有这个哨兵位的这个头结点的区别，分别去进行这个链表是不是空的这个判断，我们的这个哨兵位主要的这个作用就是进行这个数据元素的插入和删除，因此如果是带头结点，我们的判断的这个条件就是这个head->next是空就证明这个链表是空的，如果是没有这个头结点，这个head->next是空的，就证明我们的这个链表是空的；

下面的这个是我们的顺序表元素，插入到这个链表里面去，这个是头插法的相关的操作；但是这个图里面的这个up写的是有问题的，因为我们的这个里面头插的话是从1开始的，而不是从这个顺序表里面的这个最后的一个元素开始的，但是这个链表的顺序和我们的这个顺序表里面的合格元素的顺序是相反的，这个是没有问题的；

这个考察的是我们的双向的链表里面进行这个数据的插入的整个过程，就是通过这个前驱节点和后继结点改变这个里面的指针的额指向即可；

这个是双向循环链表，删除我们的之间的这个元素，这个需要做的修改这个节点前后的这个指针的指向即可，也就是让这个前面的这个节点跳过这个节点指向这个p后面的这个节点，前驱也是如此；

双向的链表里面需要进行这个数据的插入，这个时候就是建立相邻的这个指针之间的这个连接关系罢了，而且这个需要修改四个指针域，因为这个涉及到前面的这个节点和后面的节点，又因为是双向的，因此这个里面涉及到4个；

我们的这个带头结点的循环的单链表，是空的表的时候：满足我们说的这个头结点的指针域是和我们的这个L的值相等，这个时候相当于就是我们的这个指针域指向的就是我们的头结点自己；

想要进行这个末尾的元素的这个插入节点和删除节点的这个操作，如果是单循环的链表，想要删除这个最后的节点，还是需要从第一个开始走到最后，所以这个单向的链表很难去解决我们的这个地方遇到的问题；

但是如果我们使用的是这个双向的循环的链表，这个时候我们可以倒着走，就是从第一个节点直接找到最后一个，在倒着走一次，找到这个倒数的第二个节点；

up说这个题目是严蔚敏老师书上的原题，但是我们用的不是这个教材，想要实现两个循环的单链表之间的这个链接，我们需要做的就是下面的这个过程：

ra->next=fb->next fb表示的是我们第二个链表的头结点，ra是这个第一个链表的尾部节点；

rb->next=fa 这个表示的就是我们的第二个链表的尾部节点指向我们的第一个链表的头节点

最后我们发现这个fb是没有用的，也就是我们的这个第二哥链表里面的头结点是没有用的，因此我们就可以把这个节点直接释放掉；

我们的这个循环的单向的链表，想要删除这个里面的首元结点，如果这个链表没有头结点，只有这个表头指针，这个时候我们需要先找到这个链表里面的最后一个元素，然后改变这个最后一个元素的这个指针的指向，这个找到最后一个元素的过程就是O（n);

如果是B选项的话，我们想要找到这个尾部的节点很容易，直接就是这个表尾的指针的这个指向，这个时候根本不需要从第一个元素开始去找最后一个节点；

C里面的这个如果有头结点，我们的这个表尾指针直接指向这个头结点的后继的后继即可，就可以把这个首元结点删除，这个复杂度也不是o(n);

D里面的复杂度也是o(1)因为我们只需要直接把这个表头指针指向这个第二个有效元素即可；

这个题目就是两个情况：可能这个上面的第一个图示的情况，就是我们的这个线性表里面是只有一个元素，也可能就是一个空的，这个时候无论是多少次这个next指向，最终指向的都是自己；

h1是非循环的，这个时候删除这个首节点就是o(1)删除尾结点就是o(n);

h2是循环的，删除这个首节点就是o(1)删除尾节点，也是o(1)因为这个是循环的，我们可以直接从第一个的prev指针找到我们的最后一个节点的位置；

这个删除双向的循环链表里面的这个元素的操作就是去改变这个节点前后的这个指针的指向，并且把这个节点释放掉即可；

题解：

1）这个首先需要根据这个上面的数据元素的地址把这个链表的元素的前后顺序画出来；

2）最后确定我们的这个c就是第一个元素；

3）看看这个插入的元素会对于这个链表里面的哪两个元素的地址差生影响（链接地址）；

4）根据这个插入之后的情况，重新确定这个受到影响的这个元素的地址，并且进行更新；

5）根据题目找出这个更新之后的这个元素的新的地址；

题解：

1）h指向的是带头的链表的头部，也就是哨兵位节点；

2）这个里面的h->next=q->next实际上就是跳过了我们的这个链表里面的第一个元素，达到删除的效果；

3）但是这个判断p==q说的就是如果我们的这个链表里面只有一个元素，这个时候就是p=h，也就是p指向我们的头结点，因为p是尾指针嘛，p等于q时候，我们的这个元素删除之后链表就是空的，因此我们的尾指针需要移动位置；

这个是本来想要进行这个数据的插入，题目上说已经执行了两个步骤，让我们选择接下来需要执行的这个步骤：这个选择的是c:

s->next->prev其实说的就是我们的p节点，c的前半句意思就是s前驱是指向的这个p;

后半句是这个s->next->prev应该分为两个部分进行理解：

1）s->next这个表示的就是我们的s的后继，也就是我们的右上角的那个节点；

2）那个节点的prev指向我们的s这个节点，至此，这个完成插入的操作；

3.我的个人总结

个人觉得这个题目还是颇有难度的，我觉得自己还是需要复习下基础的知识，带头不带头的这个链表的类型之类的还需要补一补，这个408难度确实比我想象的要大，自身还是有很多的不足；