‘壹’ 栈的链式存储结构是什么
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入、删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比在尾端进行相对容易一些，所以将单链表的首端作为栈的顶端，即将单链表的头指针作为栈顶指针。链栈如图1所示。
图1链栈的存储示意
‘贰’ c语言二级考试循环链表是循环队列的链式存储结构
循环队列本身是一种顺序存储结构，而循环列表是一种链式存储结构。两者之间是平级关系。（用于解释第一句话的错误原因。）
线性链表是线性表的链式存储结构，包括单链表，双链表，循环链表等。（补充说明）
队列的顺序存储结构一般采用循环队列的形式。（用于解释第二句话的正确原因。）
‘叁’ 给出用数组描述的栈的存储结构，以及操作
数据结构复习重点归纳[适于清华严版教材]
一、数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：
概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。
栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
多维数组及广义表
：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。
树和二叉树
：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
图 ：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
查找
：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序
：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。
二、数据结构各章节重点勾划：
第0章 概述
本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。
第一章 线性表
作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。
总体来说，线性表一章可供考查的重要考点有以下几个方面：
1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。
2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。
4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。
在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。
5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。
第二章 栈与队列
栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。
学习此章前，你可以问一下自己是不是已经知道了以下几点：
1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。
2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。
3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。
4.循环队列中判队空、队满条件，循环队列中入队与出队算法。
如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。
第三章 串
经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。
串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡垒有：
1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件
2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3.顺序串与链串及块链串的区别和联系，实现方式。
4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进之外。其中，理解算法是核心，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
第四章 数组与广义表
学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经“一回生，二回熟”了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。
广义表的概念，是数据结构里第一次出现的。它是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。
本章的考查重点有：
1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。
2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。
3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。
4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表L。大家要留意。
5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。
第五章 树与二叉树
从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。
总体来说，树一章的知识点包括：
二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
下面我们来看考试中对以上知识的主要考查方法：
1.二叉树的概念、性质和存储结构
考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。
2.二叉树的三种遍历算法
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇系列文章（）里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。
3.可在三种遍历算法的基础上改造完成的其它二叉树算法：
求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
4.线索二叉树：
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
5.最优二叉树（哈夫曼树）：
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。
6.树与森林：
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。
树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。
树一章，处处是重点，道道是考题，大家务必个个过关。
第六章 图
如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。
图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想象的。
下面我们看一下图这一章的主要考点以及这些考点的考查方式：
1.考查有关图的基本概念问题：
这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。
2.考查图的几种存储形式：
图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。
3.考查图的两种遍历算法：深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。
4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。
考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。
5.拓扑排序问题：
拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。
6.关键路径问题：
这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。
在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。
7.最短路径问题：
与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。注意区分。
第七章 查找
在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。
现实生活中，search几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间。
在复习这一章的知识时，你需要先弄清楚以下几个概念：
关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。
在DS的教材中，一般将search分为三类：1st，在顺序表上的查找；2nd，在树表上的查找；3rd，在哈希表上的查找。下面详细介绍其考查知识点及考查方式：
1.线性表上的查找：
主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。
2.树表上的查找：
这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。
二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。
B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。B树是报考名校的同学应该关注的焦点之一。
键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。
3.基本哈希表的查找算法：
哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。
第八章 内部排序
内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。
这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。
从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。
其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。
交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。
选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。
归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。
至此，数据结构所有章节的章节重点问题，我们已经规纳完毕，使用清华严版教材的同学，在复习的同时，可以参照本贴给出的重点进行复习。但是，由于作者本人水平有限，可能有很多考点没有规纳出来，也可能有些考点规纳有误，在此，作者本人诚恳希望诸位朋友直面提出，我会不断完善和发布新的关于数据结构复习的总结以及笔记
严蔚敏数据结构为主的笔记二
第二章：线性表(包括习题与答案及要点)
--------------------------------------------------------------------------------
本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
要求达到<识记>层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。
要求达到<综合应用>层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。
链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。
要求达到<领会>层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。
--------------------------------------------------------------------------------
线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。
关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。
--------------------------------------------------------------------------------
线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。
--------------------------------------------------------------------------------
线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即
‘肆’ 用单链表表示的链式栈的栈底在链表的表尾位置 这句话对还是错，尽量给下理由，必采纳，谢谢
这句话是对的。
只能将表头作为栈顶。如果用表尾作为栈顶，出栈后将无法找到前一个结点，因为是单向。
单链表的队头可以在O(1)的时间下，实现链表的插入跟删除。对于单链表的插入跟删除，存在尾指针的话 插入O（1），删除O(n)；不存在尾指针的话， 插入O(n), 删除O(n)。
显然对于队列而言，我们希望EnQueue和DelQueue的操作都是O（1），而且这两个操作必然在链表的两端，不难发现，对于链队列的话，只存在一种可行的情况，就是使用带尾指针的链表结构， 其中头指针负责删除，尾指针负责插入。
再根据队列的定义可知，删除操作发生在队头，插入操作发生在队尾。
(4)设链式栈用循环单链表存储扩展阅读
单链表的特点：
当访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前趋节点。
链表的第一个结点和最后一个结点，分别称为链表的 首结点和 尾结点。
尾结点的特征是其 next 引用为空（null）。
链表中每个结点的 next 引用都相当于一个指针，指向另一个结点，
借助这些 next 引用，我们可以从链表的首结点移动到尾结点。
在单链表中通常使用 head 引用来指向链表的首结点，由 head 引用可以完成对整个链表中所有节点的访问。
在单链表结构中还需要注意的一点是，由于每个结点的数据域都是一个 Object 类的对象，
因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。
与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的 next 引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的直接后续。
‘伍’ 假定栈用单链表的存储结构表示，栈的栈顶指针为top，进行退栈时执行的操作
top->next指向栈顶，top->next->next指向栈顶第二个元素，现在要退栈就是移除栈顶元素，而第二个元素现在变成了栈顶元素了，所以选D
‘陆’ c语言链表问题
链式存储结构就是链表。
单链表是只有一个方向的链式存储结构。
单链表实现栈的意思就是用单向链式存储结构实现栈，但是注意，头结点作为栈顶，这样出栈入栈操作的时间复杂度是O(1)，如果头结点作为栈底则需要遍历整个链表。
链式存储结构有很多种，单链表、双链表、十字链表等，一般用到的确实就只有两种，就是单和双，但是细分又可分为带或不带头结点，是否是循环链表等。
栈和队列是受限的线性表，有其特殊用途，随着学习的深入你就知道了，比方说计算表达式，就用到了栈（操作符栈和操作数栈），避免了很多误操作，直接用链表当然也可以，但是不保险，可能会误操作或被别有用心的人利用。
‘柒’ 假定栈用单链表的存储结构表示，栈的栈顶指针为top，进行退栈时执行的操作
用c++还是java描述？
假设用c++吧，思想都一样
length--;//栈顶指针后移
Node<T> *currentNode=tail;
Node<T> *tempTail=head;
for(int i=1; i<=length; i++)//这个地方到底是小于还是小于等于自己调试一下吧
tempTail=tempTail->next;//取到出栈后应该为尾节点；
delete tail;
tail=tempTail;//恢复尾节点
return currentNode;
‘捌’ 栈往往用单链表实现，可以用双链表吗哪个更好
栈往往用单链表实现，可以用双链表，双链表更好。
最好是用数组，其次应该用双链，因为它是双向变化的。双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点，顾名思义，单链表只能单向读取。
介绍
栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底（push），最后的数据在栈顶（top），需要读数据的时候从栈顶开始弹出数据（top）最后一个数据被第一个读出来。链式栈中的元素以Node的形式存储，节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node。
‘玖’ C语言二级考试循环链表是循环队列的链式存储结构
循环队列本身是一种顺序存储结构，而循环列表是一种链式存储结构。两者之间是平级关系。
线性链表是线性表的链式存储结构，包括单链表，双链表，循环链表等。
队列的顺序存储结构一般采用循环队列的形式。
循环队列的操作是按数组取摸运算的，所以是顺序存储，而循环链表本身就是收尾相连的，所以循环链表不是循环队列，两种不同的存储结构，虽然实现的功能是一样的，实现循环两种方式 顺序存储就是循环队列，链式存储就是循环链表。
(9)设链式栈用循环单链表存储扩展阅读：
1、比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找节点时链式存储要比顺序存储慢。
5、每个节点是由数据域和指针域组成。
6、由于簇是随机分配的，这也使数据删除后覆盖几率降低，恢复可能提高。
‘拾’ 长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢
就行了，准过！
第一章：绪论
1.1：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。
1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。
数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。
数据项：是数据元素中有独立含义的、不可分割的最小标识单位。
数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。
1.3数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。
1.4：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。
数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。
2.1：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性：
输入——算法有零个或多个输入数据。
输出——算法有一个或多个输出数据，与输入数据有某种特定关系。
有穷性——算法必须在执行又穷步之后结束。
确定性——算法的每个步骤必须含义明确，无二义性。
可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。
有穷性和可行性是算法最重要的两个特征。
2.2：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。
算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。
2.3：算法的设计应满足五个目标：
正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。
健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结
高时间效率：算法的执行时间越短，时间效率越高。 果。
高空间效率：算法执行时占用的存储空间越少，空间效率越高。
可读性：算法的可读性有利于人们对算法的理解。
2.4：度量算法的时间效率，时间复杂度，（课本39页）。
2.5：递归定义：即用一个概念本身直接或间接地定义它自己。递归定义有两个条件：
至少有一条初始定义是非递归的，如1！=1.
由已知函数值逐步递推计算出未知函数值，如用（n-1）！定义n！。
第二章：线性表
1.1线性表：线性表是由n(n>=0)个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整数、浮点数、字符、也可以是对象。n是线性表的元素个数，成为线性表长度。若n=0，则LinearList为空表。若n>0，则a0没有前驱元素，an-1没有后继元素，ai（0<i<n-1）有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1。
1.2线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素，元素在内存的物理存储次序与它们在线性表中的逻辑次序相同。
线性表的数据元素数据同一种数据类型，设每个元素占用c字节，a0的存储地址为
Loc（a0），则ai的存储地址Loc（ai）为：Loc（ai） = Loc（a0）+ i*c
数组是顺序存储的随机存储结构，它占用一组连续的存储单元，通过下标识别元素，元素地址是下标的线性函数。
1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是 属数据表长度的一半。（课本第50页）
1.4：线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。
它有两个域组成：数据域和地址域。通常成为节点。（课本第55页及56页）
1.5单链表（课本56页）
单链表的遍历：Node<E> p = head; while(p!=null)
单链表的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。
单链表的插入操作：1）：空表插入/头插入 2)中间插入/尾插入
if(head == null) Node<E> q = new Node<E>(x);
{ head = new Node<E>(x); q.next = p.next;
}else{ p.next = q;
Node<E> q=new Node<E>(x); 中间插入或尾插入都不会改变单表
q.next = head; 的头指针head。
head = q;
}
单链表的删除操作：
头删除：head = head.next;
中间/尾删除：if(p.next!=null)
循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值，则该单链表成为环形结构，称为循环单链表。（课本67）
若rear是单链表的尾指针，则执行（rear.next=head;）语句，使单链表成为一条循环单链表。当head.next==head时，循环单链表为空。
1.6：双链表结构：双链表的每个结点有两个链域，分别指向它的前驱和后继结点，
当head.next==null时，双链表为空。
设p指向双链表中非两端的某个结点，则成立下列关系：p=p.next.prev=p.prev.next。
双链表的插入和删除：1）插入 2)删除
q=new DLinkNode（x）； p.prev.next = p.next;
q.prev=p.prev;q.next =p; if(p.next=null){
p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}
循环双链表：当head.next==head且head.prev==head时，循环双链表为空。
第三章：栈和队列
1.1栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有顺序栈和链式栈。
栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。
栈的进出栈顺序：后进先出，先进后出。（及75页的思考题）。
1.2：队列：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。
向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为队尾，允许出队的一端称为对头。没有元素的队列称为空队列。队列是先进先出。
第四章：串
1.1：串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。一个串记为： s=“s0s1s2…sn-1” 其中n>=0,s是串名，一对双引号括起来的字符序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）为特定字符集合中的一个字符。一个串中包含的字符个数称为串的长度。
长度为0的串称为空串，记作“”，而由一个或多个空格字符构成的字符串称为空格串。
子串：由串s中任意连续字符组成的一个子序列sub称为s的子串，s称为sub的主串。子串的序号是指该子串的第一个字符在主串中的序号。
串比较：两个串可比较是否相等，也可比较大小。两个串（子串）相等的充要条件是两个串（子串）的长度相同，并且各对应位置上的字符也相同。
两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较“大”。
第五章：数组和广义表
1.1：数组是一种数据结构，数据元素具有相同的数据类型。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。
1.2：一维数组：一维数组采用顺序存储结构。一个一维数组占用一组连续的存储单元。
设数组第一个元素a0的存储地址为Loc（a0），每个元素占用c字节，则数组其他元素ai的存储地址Loc（ai）为： Loc（ai）= Loc（a0）+i*c
数组通过下标识别元素，元素地址是下标的线性函数。一个下标能够唯一确定一个元素，所划给的时间是O（1）。因此数组是随机存取结构，这是数组最大的优点。
1.3：多维数组的遍历：有两种次序：行主序和列主序。
行主序：以行为主序，按行递增访问数组元素，访问完第i行的所有元素之后再访问第i+1行的元素，同一行上按列递增访问数组元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列为主序，按列递增访问数组元素，访问完第j列的所有元素之后再访问第j+1列的元素，同一列上按列递增访问数组元素。
多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两种。
静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。
按行主序存储时，元素aij的地址为：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存储时，Loc（aij）= Loc（a00）+（j*m+i）*c
动态多维数组的存储结构。
二维数组元素地址就是两个下标的线性函数。无论采用哪种存储结构，多维数组都是基于一维数组的，因此也只能进行赋值、取值两种存取操作，不能进行插入，删除操作。
第六章：
树是数据元素（结点）之间具有层次关系的非线性结构。在树结构中，除根以外的结点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。
树是由n（n>=0）个结点组成的有限集合（树中元素通常称为结点）。N=0的树称为空树；n>0大的树T；
@有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。
@除根结点之外的其他结点分为m（m>=0）个互不相交的集合T0,T1,T3……..,Tm-1，其中每个集合Ti（0<=i<m）本身又是一棵树，称为根的子树。
树是递归定义的。结点是树大的基本单位，若干个结点组成一棵子树，若干棵互不相交的子树组成一棵树。树的每个结点都是该树中某一棵子树的根。因此，树是由结点组成的、结点之间具有层次关系大的非线性结构。
结点的前驱结点称为其父母结点，反之，结点大的后继结点称为其孩子结点。一棵树中，只有根结点没有父母结点，其他结点有且仅有一个父母结点。
拥有同一个父母结点的多个结点之间称为兄弟结点。结点的祖先是指从根结点到其父母结点所经过大的所有结点。结点的后代是指该结点的所有孩子结点，以及孩子的孩子等。
结点的度是结点所拥有子树的棵数。度为0的结点称为叶子结点，又叫终端结点；树中除叶子结点之外的其他结点称为分支结点，又叫非叶子结点或非终端结点。树的度是指树中各结点度的最大值。
结点的层次属性反应结点处于树中的层次位置。约定根结点的层次为1，其他结点的层次是其父母结点的层次加1。显然，兄弟结点的层次相同。
树的高度或深度是树中结点的最大层次树。
设树中x结点是y结点的父母结点，有序对（x，y）称为连接这两个结点的分支，也称为边。
设（X0,X1,….,Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0<=i<k-1）都是树中的边，则该序列称为从X0到Xk-1的一条路径。路径长度为路径上的边数。
在树的定义中，结点的子树T0，T1…..,Tm-1之间没有次序，可以交换位置，称为无序树，简称树。如果结点的子树T0,T1……,Tm-1从左到右是有次序的，不能交换位置，则 称该树为有序树。
森林是m（m>=0）棵互不相干的树的集合。给森林加上一个根结点就变成一棵树，将树的根节点删除就变成森林。
二叉树的性质1：若根结点的层次为1，则二叉树第i层最多有2 的i-1次方（i>=1）个结点。
二叉树的性质2：在高度为k的二叉树中，最多有2的k次方减一个结点。
二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2，则n0=n2+1。
一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号，约定根节点的序号为0，从根节点开始，自上而下，每层自左至右编号。
一棵具有n个结点高度为k的二叉树，如果他的每个节点都与高度为k的满二叉树中序号为0~n-1
的结点一一对应，则这棵二叉树为为完全二叉树。
满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树的第1~k-1层是满二叉树第k层不满，并且该层所有结点必须集中在该层左边的若干位置上。
二叉树的性质4：一棵具有n个结点的完全二叉树，其高度k=log2n的绝对值+1
二叉树的性质5：一棵具有n个结点的完全二叉树，对序号为i的结点，有
@若i=0，则i为根节点，无父母结点；若i>0，则i的父母结点的序号为[（i-1）/2]。
@若2i+1<n，则i的左孩子结点序号为2i+1；否则i无左孩子。
@若2i+2<n，则i的右孩子结点的序号为2i+2，否则i无右孩子。
二叉树的遍历
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。
二叉树的三种次序遍历
1：先根次序；访问根节点，遍历左子树，遍历右子树。
2：中根次序；遍历左子树，访问右子树，遍历右子树。
3：后根次序；遍历左子树，遍历右子树，访问根节点。
先根次序遍历时，最先访问根节点；后根次序遍历时，最后访问根节点；中根次序遍历时，左子树上的结点在根节点之前访问，右子树上的结点在根节点之后访问。
二叉树的插入和删除操作P147
二叉树的层次遍历P149
习题P167 6—10，6—19
第七章
图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图G记为G=（V,E），V是顶点A的有限集合，E是边的有限集合。即 V=
E=或E=其中Path（A,B）表示从顶点A到B的一条单向通路，即Path（A,B）是有方向的。
无向图中的边事没有方向，每条边用两个顶点的无序对表示。
有向图中的边是有方向，每条边用两个顶点的有序对表示。
完全图指图的边数达到最大值。n个顶点的完全图记为Kn。无向完全图Kn的边数为n*（n-1）/2,有向完全图Kn的边数为n*（n-1）。
子图：设图G==(V,E),G’=(V’,E’)，若V’包含于V且E’包含于E,则称图G’是G的子图。若G’是G的真子图。
连通图：在无向图G中，若从顶点VI到Vj有路径，则称Vi和Vj是联通的。若图G中任意一对顶点Vi和Vj（Vi不等于Vj）都是联通的，则称G为连通图。非连通图的极大联通子图称为该图的联通分量。
强连通图：在有向图中，若在每一对顶点Vi和Vj（Vi不等于Vj）之间都存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，也存在一条从Vi到Vj的路径，则称该图的强连通图。非强连通图的极大强连通子图称为该图的强连通图分量。
图的遍历
遍历图是指从图G中任意一个顶点V出发，沿着图中的边前行，到达并访问图中的所有顶点，且每个顶点仅被访问一次。遍历图要考虑一下三个问题：
@指定遍历的第一个访问顶点
@由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间约定一种访问次序。
@由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。
深度优先搜索
图的深度优先搜索策略是，访问某个顶点v，接着寻找v的另一个未被访问的邻接顶点w访问，如此反复执行，走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点，则回到前一个被访问顶点，再寻找其他访问路径。
图的深度优先搜索遍历算法P188
联通的无回路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。各连通分量均为树的图称为森林，树是森林。
由于树中无回路，因此树中必定无自身环也无重边（否则他有回路）若去掉树中的任意一条边，则变成森林，成为非联通图；若给树加上一条边，形成图中的一条回路，则不是树。P191
生成树和生成森林：
一个连通无向图的生成树是该图的一个极小联通生成子图，它包含原图中所有顶点（n个）以及足以构成一棵树的n-1条边。
一个非联通的无向图，其各连通图分量的生成图组成该图的生成森林。
图的生成图或生成森林不是唯一的，从不同顶点开始、采用不同遍历可以得到不同的生成树或森林。
在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。
第八章
折半查找算法描述 P206,P207
二叉排序树及其查找：
二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
@每个结点都有一个作为查找依据的关键字，所有结点的关键字互不相同。
@若一个结点的左子树不空，则左子树上所有结点的关键字均小于这个节点的关键字；
@每个结点的左右子树也分别为二叉排序树。
在一棵二叉排序树中，查找值为value的结点，算法描述如下：
@从根结点开始，设p指向根结点
@将value与p结点的关键字进行比较，若两者相等，则查找成功；若value值较小，则在p的左子树中继续查找；若value值较大，则在p的右子树中继续查找。
@重复执行上一步，直到查找成功或p为空，若p为空，则查找不成功。
习题 8-6
第九章
直接插入排序算法描述：p228
冒泡排序算法的描述：p232
快速排序算法描述p233
直接选择排序算法描述p236
直接选择排序算法实现如下：
Public static void selectSort(int[]table){
for(int i=0;i<table.length-1;i++){
int min=I;
for(int j=i+1;j<table.length;j++){
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]==table[min];
table[min]=temp;
}
}
}
}
堆排序是完全二叉树的应用，是充分利用完全二叉树特性的一种选择排序。
堆定义：设n个元素的数据序列，当且仅当满足下列关系
k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]
或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]时，序列称为最小堆或最大堆。将最小（大）堆看成是一颗完全二叉树的层次遍历序列，则任意一个结点的关键字都小于等于（大于等于）它的孩子节点的关键字值，由此可知，根结点值最小（大）。根据二叉树的性质5，完全二叉树中的第i（0<=i<n）个结点，如果有孩子，则左孩子为第2i+1个结点，右孩子为第2i+2个结点。
希望对你会有所帮助。