数据结构知识点
1、数据：所有能被计算机识别、存储和处理的符号的集合。
2、数据元素：是数据的基本单位，具有完整确定的实际意义。
3、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
5、数据类型：是一个值的集合和定义在该值上的一组操作的总称。
6、抽象数据类型：由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。
7、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
8、算法的基本特性：输入、输出、有穷性、确定性、可行性。
9、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求。
10、线性表的定义：用数据元素的有限序列表示。
11.顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
12.链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。
13.线性表的逻辑结构：指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。
14.顺序存储结构：用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。
15.栈的定义及操作：栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。
16.队列的定义及操作：队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两种存储结构中，都需要队头和队尾两个指针。
17.二叉树的遍历：指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。
18.查找表：是称为集合的数据结构。是元素间约束力最差的数据结构，元素间的关系是元素仅共在同一个集合中。
数据结构知识点总结
线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。
用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。
串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
串的表示和实现
数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。
二维数组，多维数组，广义表，树，图都属于非线性结构
数组
数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。
广义表
广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。
三个结论
考点
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
基本术语
1.树结点：包含一个数据元素及若干指向子树的分支；
2.孩子结点：结点的子树的根称为该结点的孩子；
3.双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
4.兄弟结点：同一双亲的孩子结点；
5.堂兄结点：同一层上结点；
6.结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
7.树的高（深）度：树中最大的结点层
8.结点的度：结点子树的个数，就是有几个孩子
9.树的度： 树中最大的结点度。
10.叶子结点：也叫终端结点，是度为0的结点；
11.分枝结点：度不为0的结点（非终端结点）；
12.森林：互不相交的树集合；
13.有序树：子树有序的树，如：家族树；
14.无序树：不考虑子树的顺序；
二叉树
二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
注意区分： 二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树
二叉树遍历
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：一维数组存储二叉树，总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
二叉树性质
1.在二叉树的第 i 层上至多有2的i次幂-1个结点
2.深度为 k 的二叉树上至多含 2的k次幂-1 个结点（k≥1）
3.树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历
一些概念
1.路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
2.路径长度：路径上的分支数目称为路径长度；
3.树的路径长度：从根到每个结点的路径长度之和。
4.结点的权：根据应用的需要可以给树的结点赋权值；
5.结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
6.树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li
7.哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
图搜索->形成搜索树
1.穷举法
2.贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数
3.回溯法，根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理
无向图
1.回路或环：第一个顶点和最后一个顶点相同的路径。
2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
3.连通：顶点v至v’ 之间有路径存在
4.连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
5.连通分量：极大连通子图，子图中包含的顶点个数极大
6.所有顶点度的和必须为偶数
有向图
1.回路或环：第一个顶点和最后一个顶点相同的路径。
2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
3.连通：顶点v至v’之间有路径存在
4.强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
5.强连通分量：极大连通子图
6.有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
7.生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。
8.完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
9.有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
10.一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
图的邻接矩阵和邻接表
1.邻接矩阵和加权邻接矩阵
深度优先搜索利用栈
深度优先遍历类似于树的先序遍历，是树的先序遍历的推广
广度优先遍历
图的广度优先遍历就类似于树的层序遍历
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图
最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
Kruskal算法 ：令最小生成树集合T初始状态为空，在有n个顶点的图中选取权值最小的边并从图中删去，若该边加到T中有回路则丢弃，否则留在T中；依次类推，知道T中有n-1条边为止
Prim算法： 它的基本思想是以顶点为主导地位，从起始顶点出发，通过选择当前可用的最小权值边把顶点加入到生成树当中来：
1.从连通网络N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边（U0,V）,将其顶点加入到生成树的顶点集合U中。
2.以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(U,V),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
Prim算法，Kruskal算法和Dijkstra算法都属于贪心算法
Dijkstra算法适用于边权值为正的情况，如果边权值为负数就才用另一种最短路算法Bellman-Ford算法。该算法是指从单个源点到各个结点的最短路，该算法适用于有向图和无向图。复杂度O(n^2)
Dijkstra算法图文详解
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为 重（双）连通图。
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为 关节点。
没有关节点的连通图称为双连通图
1.生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
2.对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。
AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。
拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：
采用 深度优先搜索 或者 拓扑排序 算法可以判断出一个有向图中是否有环（回路）。
深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。
拓扑算法描述 ：
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
常用哈希函数
1.直接定址法。
2.数字分析法。
3.平方取中法。
4.折叠法。
5.除留余数法。
6.随机数法。
冲突解决
1.开放定址法：当发生冲突时，形成一个探查序列，沿此序列逐个地址探查，知道找到一个空位置，将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。
2.链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。
3.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n (n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n (n+1)/2次探测
4.Hash查找效率：装填因子=表中记录数/表容量
5.开哈希表——链地址法；闭哈希表——开放地址法
B树的查找
时间复杂度O(logn)
B树的插入
例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15构建5阶B树
因为构建5阶的B树，所以每个节点的关键字个数范围为[2,4]
插入11时，该节点的关键字个数超出范围，进行分裂
之后直接插入4，8，13
当插入10时，节点关键字个数再次超出范围
将子节点分裂
直接插入5，17，9，16，插入20
关键字个数超出范围，进行分裂
继续插入3
关键字个数超出范围，进行分裂
继续插入15
关键个数超出范围，进行分裂
这时候根节点关键字个数也超出范围，继续分裂
B+的优点
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查询叶到叶子节点，查询更加稳定
3.所有叶子节点形成有序链表，便于范围查询。
数据结构知识点
1、继承不同
HashMap继承了AbstractMap，AbstractMap实现了Map接口
HashTable继承了Dictionary类
2、线程安全不同
HashMap不是线程安全的，HashTable是线程安全的
3、允许null值
HashMap允许key和value为空，而HashTable不允许
4、遍历方式实现不同
HashMap的迭代器是fail-fast迭代器，HashTable的enumerator迭代器不是fail-fast的
5、哈希值的使用不同
HashMap重新计算哈希值，HashTable直接使用对象的哈希值
6、初始容量和扩容方式不同
HashMap初始大小为16，扩容大小一定是2的指数
HashTable初始大小为11，扩容大小为old*2+1
7、hashmap新增红黑树结构
当碰撞链表过长时，就把链表转为红黑树
1、直接定址法
取关键字或关键字的某个线性函数值为散列地址
特点：关键字连续时较方便，但关键字不连续时将造成内存单元的大量浪费
2、数字分析法
取关键字中取值比较均匀的若干数位作为哈希值。
特点：适用于关键字全部已知，并要对关键字中每一位进行分析
3、平方取中法
取关键字平方后中间几位作为哈希地址
特点：因为平均值的中间部分跟关键字的每一位都有关，出现随机值的概率较大
4、分段叠加法
按哈希表地址位数将哈希表分为位数相等的几段（最后一段可以较短），然后将这几部分相加，舍弃最高位的进位得到哈希值。
具体分为：移位法与折叠法
移位法：将每部分低位对其相加
折叠法：从一段向另一端沿分割线来回折叠（奇数段为正序，偶数段为倒序）
例如关键字123603247112020,哈希表长度为1000，则应把关键字分成3位一段
移位法得到105，折叠法得到907
5、伪随机数法
采用伪随机函数作为哈希函数
6、除留余数法
用关键字除以某个不大于哈希表长度的数，取余数作为哈希值。
1、开放定址法
当关键字key的哈希值p=H（key）出现冲突时，以p为基础产生新的哈希值p1，如果p1仍冲突，则产生p2，以此类推。
函数形式如下：
Hi = (H(key) + di) % m
根据di的不同分为
（1）线性探测
di = 1， 2， 3， …… ，（m-1）
（2）平方探测
d i =1 2 ，-1 2 ，2 2 ，-2 2 ，…，k 2 ，-k 2 ( k<=m/2 )
（3）伪随机探测
di = 伪随机数序列
2、再哈希法
构造多个不同的哈希函数，当出现冲突时，使用新的哈希函数
3、链地址法
将散列到同一位置的冲突元素存入一个链表中
4、建立一个公共溢出区
将哈希表分为基本表和溢出表
左旋：
右旋
红黑树是一颗特殊的二叉查找树，除了二叉查找树的所有性质
1、若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2、若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3、任意节点的左右子树也为二叉查找树
4、没有键值相等的节点
还满足
1、每个节点要么是红的要么是黑的
2、根节点是黑的
3、每个叶节点（null节点）是黑的
4、如果一个节点是红的，那么它的两个儿子都是黑的
5、任意节点到叶节点（null节点）的每条路径都包含相同数目的黑节点
红黑树保证没有一条路径比另一条路径长出两倍，保证了自身是接近平衡的二叉树，能保证在最坏的情况下查找的时间复杂度为O（logN），而二叉查找树最坏为O（N）
红黑树牺牲了严格的高度平衡为代价，只要求部分达到部分平衡条件，降低了对旋转的要求，从而提高了性能。红黑树能够以O（logN）的时间复杂度进行添加，删除，查找。由于它的设计，任何不平衡都可以在三次旋转之内解决。
1、相比BST（二叉搜索树）
红黑树的最长路径不大于最短路径两倍，保证了最差搜索效率为O（logN）,而二叉搜索树最差效率会达到O（N）
2、相比AVL（平衡二叉树）
（1）红黑树的查询性能略逊于平衡二叉树，因为它比平衡二叉树会最多多一层。
（2）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。
数据结构知识归纳
第一章：数据结构概述 一、什么是数据结构 1、作者开篇谈到： 一般来说解决一个具体的问题时，大致需要经过下列几个步骤：首先要从具体的问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序代码，进行测试、调整直至得到最终的解决方案。 总结为：现实中具体的问题—>数学模型—>算法程序—>解决方案 动作为：抽象提取、设计编码、测试调整 2、数学角度阐述： 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 3、定义数据结构： 描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构，因此，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科，用一句话来说就是，数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 研究对象：1、集合2、线性结构3、树形结构4、图状结构（网状结构） 结构分类：1、数据的逻辑结构2、数据的物理结构（存储结构） 关系表示：1、顺序映像2、非顺序映像，两者分别对应为顺序存储结构、链式存储结构 二、算法和算法分析 1、算法的五个特性：有穷性、确定性、可行性、输入和输出 2、算法设计的要求：正确性、可读性、健壮性以及效率与低存储量需求 3、算法的度量：时间复杂度和空间复杂度 总结：编写代码设计算法时候首先先考虑算法的正确性，确保程序能够满足要求，在正确性的前提下再进一步考虑算法的可读性、健壮性、拓展性以及算法的效率等。 第二章：线性表 一、线性表的定义 线性结构的特点是：在数据元素的非空有限集中（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最后一个元素之外，集合中每个数据元素均只有一个后继。 线性表是最常用并且最简单的一种数据结构，简单来说，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，既可以是一个数也可以是一个符号等等。 二、线性表的操作 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不但可以进行访问，还可以进行插入和删除等操作。线性表存储方式有两种，顺序存储和链式存储，下面通过代码进行简单模拟操作。 第三章：栈和队列 栈和队列是两种重要的线性结构，从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限制的线性表，因此可以称为限定性的数据结构。 一、栈的定义 栈是限定在表尾进行插入或删除操作的线性表，栈的特定是先进后出。栈的存储方式有两种，一种是顺序栈另外一种是链式栈，下面只通过代码简单模拟栈的操作。 二、栈的应用 栈的应用主要有数制转换、括号匹配的检验、迷宫问题求解以及表达式求值。另外栈递归实现的经典例子有八皇后问题、汉诺塔问题等。 三、队列的定义 队列和栈有点不同，队列是一种先进先出得线性表，它只能够在表的一端进行插入另外一头进行删除操作。队列在程序设计中比较常见的例子是操作系统中的作业排队。双端队列、循环队列有时间再进一步演进，暂时先了解些基本概念。 第四章：串 一、串的定义 计算机上的非数值处理的对象基本上都是字符串数据。串是由零个或多个字符组成的有限序列。串中字符的数目成为字符串的长度，零个字符的串成为空串。串的模式匹配算法经典的是KMP算法。 第五章：数组和广义表 一、数组和广义表定义 数组是读者已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设为固有的类型。数组的应用中涉及到一个比较重要的数学知识，矩阵的压缩存储问题。广义表是线性表的推广，在java开发中好像用得不多，有时间再进一步学习。 第六章：树和二叉树 一、树的定义和基本操作 1、树的特点 树是一个结点n的有限集，在任意一颗树非空树中：1、有且只有一个根结点，2、当n>1时，其余结点分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，叫做根的子树。 关键词组：有限集、唯一性、对称性、递归性。 基本术语：结点、度、叶子、分支结点、孩子、双亲、兄弟、层次以及深度等。 基本操作：构造初始化树、取得左子树或右子树、插入结点、删除结点、树的遍历等等。 2、线性结构VS树结构 线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。 二、二叉树的定义 1、二叉树的特点 每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。 关键词组：对称、次序 2、二叉树的具体实例 满二叉树、完全二叉树、平衡二叉树等，具体区别参考书籍教材详解。 3、二叉树的存储结构 主要分为两种方式，一类是顺序结构（可使用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素），另外一类是链式存储结构，这两种存储方式各有利弊，具体要看实际操作的场合。 4、二叉树的遍历方式 遍历方案有先序遍历、中序遍历、后序遍历，具体的算法实现有递归的算法和非递归的算法。二叉树线索化初步了解，待有需要再进一步编码实战。 三、树的应用实例 1、树和森林 树的存储表示方式主要有三种：双亲表示法、孩子表示法以及孩子兄弟法。树和森林之间的相互转换也比较简单，不过多分析。 2、树的应用 （1）树的等价问题：离散数学中引入的等价和等价类的概念 （2）赫夫曼树及其应用（赫夫曼树又叫最优二叉树） （3）回溯法与树的遍历 （4）树的计数 四、代码实战参考题目 1、构造/初始化一颗二叉树 2、递归/非递归中序遍历该二叉树 3、二叉树和森林的相互转换模拟实现 //具体看存储的方式，比如孩子兄弟法 4、对平衡二叉树进行增加、删除结点操作 补充：参考学习资料： http://justsee.iteye.com/blog/1106693赫夫树、赫夫曼编码实现
数据结构的考点是什么？
在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分。 一、考查目标 (1)理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 (2)掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 (3)能够选择合适的数据结构和方法进行问题求解。 二、知识点解析 1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。 3、树与二叉树 二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。 在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。 多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。 最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。 http://ky.educity.cn/sjjg/200808051202101241.htm
数据结构知识
线性表是一种链式的存储结构，表指针就是用来放地址的，就是指向下一个结点的指针，头结点在链表里面一般是用来存放链式表第一个结点的地址，而它的数据域是空的，只有指针域，就相当于一群幼稚园的小孩子，最前面那位是老师，后面拉着第一个小孩，小孩又拉另一个，一直这样接下来下去，头结点就是老师。表头结点，跟你说的头结点是一个意思