《数据结构》第二章 线性表问题回收站问题 85到106楼参考答案

下面是答案是物联网1132班卢和云组收集整理的，对他们的劳动表示感谢！

?希望大家灵活理解相关问题！

85、有参构造函数中的两种构造方法，头插法和尾插法在编写时哪种更常用？

答：没有哪种更常用之说，这一个依赖于个人习惯，就我的见解，头插法与尾插法的区别只在于尾插法比头插法多了一个“尾指针”，也因为多了这个尾指针，使得他们的调用顺序不同。

86、在31页那里，除了开始节点外，其他的每个节点的存储结构都存放在其前驱结点的next区域中，开始节点有头指针指示的，为什么这样会增加出现bug的机会

答：查了一下资料，我总结了几点：1、 无头节点（链表）的头指针初始化：“head=NULL;”，有头结点的头指针初始化：“head->next=NULL。2、 插入节点的时候，无头节点（链表）第一个节点（开始节点）必须与其他节点区分操作。（这里便是最容易出现bug的地方）。3、 对于只有一个节点的链表，无头节点的链表是把值存放在头指针，而有头结点的是存在头结点存放的指针所指向的下一个位置。于是这里就容易出现bug。

87、单链表的存取结构是什么样子的，应该不是随机存储结构吧

答：随即存储结构：只要确定存储结构顺序表的起始位置（即基地址），计算任意一个元素的存储地址的时间是相等的存储结构。 单链表是通过寻址查找，必须通过头指针顺着next域逐个节点往下搜索找到！最好情况是O(1),最坏情况是O(n)。所以不是随机存储结构。

88、单链表的遍历操作的目的或者是意义是什么

答：遍历操作是指按序号依次访问单链表中的所有节点且仅访问一次。遍历操作可以输出单链表的所有数据，也可以查找数据（比如找出最大值）等等。

89、课时提到随机存取，老师用到a【i】来解释，顿时我就对“随机”二字不信任了。查了下百度百科：“随机存取（有时亦称直接存取）代表同等时间存取一组序列中的一个随意文件”。“随机”是不是这样来理解比较好？

答：所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。顺序表使用数组存储，而数组正好拥有这一特点。就我的理解，这里的“随机”并非是数学中的“随机”。

90、是不是每种数据结构都具有删除、查找、插入这三种基本操作？

答：个人鄙见：每种数据结构都具有插入，查找，删除等基本操作。不过如何使用便需要就实际情况而定了。

91、求解答：向量与顺序表的关系？

答：确切地讲，向量（vector）是从ADT角度而言的概念，是经过抽象之后的数据结构，而数组（array）分别是前者的一种实现方式。同理的有：列表（list）与链表（linked list）。

92、若p=first,p=p->next,cout<<p;是否就是输出了第一个结点的数据？

?答：首先，这个代码有问题，应该是：p=first;???? //是以分号为语句的结束标志，而非逗号，下面也一样。

p=p->next;// cout<<p;???????这里也错了，应该输出的是p所指向的数据域

cout <<p->data; ?最后，第一步，为什么偏要先吧first所指向的地址赋给呢，直接p=first->next;岂不是更省时省力。

93、为什么说有了头结点之后，空表和非空表的处理统一了？

答：有了头结点，无论链表是否为空，头指针始终指向头结点，而链表的插入，删除，查找等操作

94、单链表如何储存元素

答：单链表的每个节点有两个域：data域和next域。其中next域是存储后继节点，data域存储数据。

95、我想问下，p=first->next中的p为啥不用声明类型？

答：其实，这一个是需要的，但对于书本中为什么没有，我也不太清楚，但你在编译器操作的时候，不声明的话，编译会出错。

96、书本说单链表关心的只是它所表示的线性表中的数据元素以及数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置，难道节点中的指针域的地址不能说明数据元素在存储器中的位置？

答：可以说明，但我们可以通过前后节点的逻辑关系而找到存储所要找到的数据元素所在的节点，为什么还偏要去找到他所在的位置而找到这个元素呢？又由于链表的存储位置是随机分配的，所以通过之间的逻辑关系查找到数据元素，时间复杂度会更低。

97、节点我可以怎么理解？

答：结点就是链表数据链上的一个“元素”,如单链表的一个结点就是:new申请一个结构体内存空间.在该空间里存放一个数据域和指针域来构成单链表的一个元素.

98、单链表中是不是在指针域中存储的是下一个数据的指针？

答:是的,正是借此来链接下一个结点.以此来形成链.

99、请问空的线性表如何占用内存？

答:看顺序表和链表的初始化即构造函数就明白.顺序表仅仅使lengh=0,(但顺序表在定义时数组占用的空间就为其分配好了.链表也是建立一个空的头结点而已.

100、 请问为什么书本的例子中,类的无参构造函数为什么要建立一个空的头结点?感觉没有用,也没有必要啊!这不是和有参构造函数重复了?

答：对于一个对象，有参和无参构造函数不会是同时调用,而是一个一个的调用.所以不重复.

101、在单链表中实现插入和删除，是否需要移动结点？为什么

答:不移动.仅仅是对指针的操作.结点在分配空间时就已经固定了,但他的指针指向不是固定的,如果结点间的联系用箭头来表示的话.它就是箭头.改变它来实现操作是不需要移动节点的位置。

102、在编写程序时，先是无参构造函数建立了只有头结点的空链表，又是有参构造函数建立有n个元素的单链表，那一共是建立了两个链表，还是一个带有头结点的单链表？答：对于一个对象，有参和无参构造函数不会是同时调用。所以也不会出现你所理解的那种情况。

103、明哥，对于头插法建立链表，是动态的链表，那么单链表和头插法建立的链表有什么联系，这部分很不懂，有没有视频讲解？

答：建立单链表有两种方法：头插法和尾插法。

104、我想问下，循环链表中，定义尾指针时，要找到终端结点，是不是先遍历一遍，这样才能找到终端结点？

答：在生成链的时候，同时定义了尾指针，所以无需遍历链表，而尾指针就可以动态移动而始终指向尾结点（终端节点）。

（编辑：ASP站长网）