答疑解惑

常见问题汇总

  标题：如何学习数据结构?
    我是一名计算机专业大二学生，我想知道在c语言基础比较好的情况下，怎样学习数据结构才能把它学好来？除了教科书外，是否还需要其他课外书。学了c语言后，觉得自己把老师讲的内容消化了，但是还是觉得不够。又不知道如何去测试，提高自己的水平，我决心考研，我想现在就开始好好打下计算机基础，不知您能否给予一些学习建议和要求，感激不尽！

    我想现在书店里有很多数据结构的教材，你学习其中任何一本都可以，找一本你觉得学起来比较顺的为主，遇到问题再参看其它教本，不一定都去买，学校里的图书馆一般都会有好几本数据结构的书。学习数据结构最重要的是“动手”，不仅是边看书边作题，即使是看的过程中也要拿笔随时画一下。和其它课程度学习一样，学习中多问为什么，对每一个算法和结论都要得到能完全说服自己的理由为止。

  标题：数据结构（c语言版）对c语言的要求是什么? 　
    请问自学数据结构（c语言版）对需要对c语言中的哪些内容复习阿。因为我c语言只有基本的了解，所以可能要先看c才能看您的数据结构，但是c语言中的内容比较多，有哪些内容可以不看吗？

    C语言中最基本的语法 数据结构(C版)中描述算法用的是伪码语言，其中涉及的只是C语言中最基本的语法，因此如果只是看书的话，只要先将第一章中关于描述语言的部分仔细看明白即可。但学习数据结构最好能自己上机完成1至2个题，可以边做题边看C语言的书，带问题地学更有效。

  标题：主函数我不会编？　
    主函数我不会编？

    多看程序! 可以看一下其他程序是怎么实现的，答案可以交流 。

  标题：双端队列的输入输出序列有点糊涂. 　
    若以1234作为双端队列的输入序列.问:能由输入受限的双端队列得到,但是不能由输出受限的双端队列得到的输出序列是什么? 我感觉答案很多,这样的组合很灵活,不能理解书上给出的4132.请老师你讲解下思路.还有对于这样的队列输入,好象已经不是队列的性质还带有栈的特点?

    双端队列确是好像两个栈底靠在一起的栈，但这两个栈底又是互通的。它确是很灵活，因此不可能出现的出队的序列只可能是四个车厢都已经入队的情况，因为如果队列中只有1个或2个或3个都是能调度过来的，但当4个都进去之后就受一定限制了，对于输入受限的双端队列此时队列中车厢的排列必定是1234,因此尽管两头都能出去，也不可能出现是42**这样的出队序列，而对于输出受限的双端队列，无论怎么进去，在队列中也形不成4132和4231这样的序列。

  标题：请帮我解释一下孩子链表?　
    请帮我解释一下孩子链表?

    数据结构习题集的两题涉及孩子链表，关于该链表的结构情况可否详细一下？该链表融合了线性表和链表，是如何融合的呢？书上说头指针组成一个线性表，是否是说线性表的数组元素和链表元素共用一个节点空间？本节点本身的数据域是在那里显示呢？谢谢！ 孩子链表　你可以对照来看对邻接表的语言描述。"头指针构成线性表"是指线性表的数据元素是"记录每个结点的所有孩子点的链表的头指针加上该结点的数据元素"，换句话说，"每个结点的数据元素和含有该结点所有孩子结点信息的链表头指针"作为线性表的一个数据元素。链表中孩子结点的信息可由孩子结点在表中的序号到线性表中找到。对线性表来说，它的数据元素不限于什么类型，也可以是一个数据结构，在邻接表中，其数据元素是一个由"结点的数据元素"和"单链表的头指针"构成的结构。

  标题："前缀表示式"还是不太清楚！
    "前缀表示式"还是不太清楚！

    "前缀表示式"的求值规律是，从左向右判别字符，若是运算符，则入栈，直至连续出现的两个操作数，应和栈顶的运算符构成一个最小表达式即进行运算，"中缀"丢失了原表达式中的括弧信息，无法求值，"后缀表示式"的求值规律最简单，遇操作数则入栈，遇运算符即从栈中连续出栈两个运算符进行运算，当然先出栈的为第二操作数， 表达式树求值即进行后序遍历，清华大学出版社出版的《数据结构及应用算法教程》中有详细算法例子。

  标题：常用的存储表示方法有哪几种? 　
    常用的存储表示方法有哪几种?

    常用的存储表示方法有四种 常用的存储表示方法有四种: 　● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 　● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 　● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ● 散列存储方法：就是Hash。

  标题：能举一个生活中的数据结构的例子吗？　
    能举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

    一个生活中的数据结构的例子 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。 　　这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

  标题：算法的时间复杂度仅与问题的规模相关吗? 　
    算法的时间复杂度仅与问题的规模相关吗?

    算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

  标题：什么是头指针、头结点、开始结点？ 　
    什么是头指针、头结点、开始结点？

    开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

  标题：何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 　
    何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

    在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 　1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 　2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

  标题：为什么在单循环链表中设置尾指针比设置头指针更好? 　
    为什么在单循环链表中设置尾指针比设置头指针更好?

    单循环链表中设置尾指针的好处 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。

  标题：链栈中为何不设置头结点? 　
    链栈中为何不设置头结点?

    链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

  标题：如何判别循环队列的空和满? 　
    如何判别循环队列的空和满?

    循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

  标题：静态分配的顺序串和动态分配的顺序串有何不同？ 　
    静态分配的顺序串和动态分配的顺序串有何不同？

    静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

  标题：三维数组地址计算公式是什么？　
    三维数组地址计算公式是什么？

    三维数组地址计算公式 C语言的数组下标下界是0，所以 Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d

  标题：请问广义表和线性表的区别与联系？　
    请问广义表和线性表的区别与联系？

    广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

  标题：一棵度为2的有序树与一棵二叉树有何区别? 　
    一棵度为2的有序树与一棵二叉树有何区别?

    有序树与二叉树：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。

  标题：线索对求指定结点在相应次序下的前趋和后继都有帮助吗? 　
    线索对求指定结点在相应次序下的前趋和后继都有帮助吗?

    线索对求指定结点在相应次序下的前趋和后继。分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。

  标题：n个顶点的连通图至少有几条边? 　
    n个顶点的连通图至少有几条边?

    n个顶点的连通图至少有n-1条边

  标题：有序数组是堆吗? 　
    有序数组是堆吗? 　

    有序数组是堆。因为有序数组中的关键字序列满足堆的性质。若数组为降序，则此堆为大根堆，反之为小根堆。