数据结构指的是数据之间的关系，一般包括三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算或操作。

数据的存储结构有四种基本方式：顺序结构、链接结构、索引结构、散列结构。 算法效率的度量分为：事后测量和事前估计。

物理结构：指数据在计算机中存放的方式，即数据逻辑结构的物理存储方式。主要有顺序存储和链式存储。

数据的操作指利用计算机对数据进行插入、删除、修改、查找、排序等操作。 数据类型：一个数据的集合，以及定义于这个数据集合上的一组操作的总称。

算法是对特定问题求解步骤的一种描述。算法是一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。

算法特性：输入、输出、确定性、有穷性、可行性。

算法评价：正确性、可读性、稳建性、时间复杂度、空间复杂度

线性表是 n(n>=0) 个相同类型数据元素a1, a2, …， an 构成的有限序列。是一种线性结构，允许在任意位置进行插入和删除操作。

一般表示为: L = ( a1, a2, …， an )

形式化定义： Linear_list = (D, R)

线性表的顺序存储结构:

用一组地址连续的存储单元依次存储线性表的各个数据元素。逻辑上相邻的元素在物理存储上也相邻。

顺序表的优点：空间单元利用率高、可以方便的随机存取表中的任一元素、算法简单 顺序表的缺点： 插入和删除运算需移动数据元素

线性表的链式存储结构特点：1、不要求逻辑上相邻的元素在物理位置上也相邻。可以用任意的存储单元存储数据元素。 2、线性表元素之间的逻辑关系由指针指示。顺序存取机制。

循环单链表与单链表的区别在于：循环链表的最后一个结点的指针指向头结点，整个链表形成一个环。优势在于：从表中任意一个结点出发都可找到表中其他结点。 静态链表 就是用数组中的结点来构造链表.主要用于不设“指针”的程序设计语言 单链表的优点：插入和删除操作时不需要移动数据元素

单链表的缺点:①每个结点要有一个指针域，空间单元利用率不高②算法相对复杂些 栈又称堆栈，是一种操作受限制的线性表，只允许在表的固定一端（表尾）进行插入或删除。

递归：一个算法直接或间接地调用自身，称该算法为递归算法。这个函数就称递归函数。

递归算法与栈的关系：

调用递归函数时，自动使用栈保存下述两类信息：调用后的返回地址；调用函数的局部变量值（包括实参）调用结束时，自动执行出栈操作，按返回地址返回。

队列也是一种操作受限的线性表，只允许在表的一端进行插入（表尾），在表的另一端进行删除（表头）。

树是n(n≥0)个结点的有限集。n=0的树称为空树。

任意一棵非空树，满足：

① 有且只有一个称为根的结点(root):②当n>1时，除根结点外的结点可分为 m(m>0)个互不相交的有限集T1 , T2 ,…, Tm。且每一集合本身又是一棵树，称其为根的子树。每棵子树的根结点是整棵树根结点的后继，整棵树的根结点是每棵子树根结点的前驱。

树的形式化定义

Tree = ( K , R ) K = { ki | 1≤i≤n , n≥0, ki∈ElemType}

R= { r }

当 n > 0(非空树)时，关系 r 满足下列条件：

①有且仅有一个结点没有前驱，此结点称为根。

②除根以外，其余结点有且仅有一个前驱结点。

③所有结点可以有任意多个(含0个)后继。

结点： 包含一个数据值和若干指向其子树的分支。

结点的度：结点拥有的子树个数。（degree）

树的度：树内各结点的度的最大值。

分支结点：度不为0的结点 (也称非终端结点) 。

分单、双、三分支结点等。

叶子结点：度为0的结点 (也称终端结点) 。

孩子（后继）、双亲（前驱）、兄弟结点：

一个结点的子树的根结点称为该结点的孩子结点。该结点称为孩子的双亲结点。同一双亲结点的结点称为兄弟结点。

结点的祖先：从根结点到该结点所经过的所有结点。

结点的子孙：以某结点为根的子树中所有结点。

结点的层次：根结点为第1层，根的孩子为第2层。

树的深度：树中结点的最大层次为树的深度（或高度）。

有序树与无序树：如果树中结点的各子树是从左到右有次序的(不能互换)，则称为有序树；否则称无序树。

森林：m（m≥0）棵互不相交的树的集合。

树的性质 ：性质1 树中结点数等于所有结点的度数（即分支数）加1。性质2 度为k的树中第 i 层上最多有 ki-1个结点。(i ? 1)

小深度为 logk（n (k-1)+1） 性质3 深度为 h 的 k 叉树（即度为 k 具有n个结点的 k 叉树的最的树）最多有 (kh-1) / (k-1)个结点。 (h ?满k叉树: 当一棵k叉树的结点数等于 (kh-1)/(k-1) 时，称为满k叉树。

二叉树的性质

性质1 二叉树的叶子结点数为n0 ，所有度为2的结点

数为n2。则有 n0=n2+1

性质2 一棵非空二叉树的 第i 层最多有2i-1个结点。(i ? 1)

证明：由树的性质2可知。

深度为h 的二叉树最多有 2h-1个结点。

性质4 具有n个结点的完全二叉树的深度为 log2(n + 1) 或 log2n +1 。

所谓遍历就是对二叉树中的全部结点逐一进行访问，使得每个结点均被访问一次且仅一次。它是二叉树运算中最重要的运算。

根左右（先序或前序遍历）、左根右（中序遍历）、左右根（后序遍历） 森林转换成二叉树:

二叉树转换成森林:结点删除与双亲结点的连线；整理连线。 若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子，…，都与 y 用连线连起来，最后去掉所有双亲到右孩子的连线。

稀疏矩阵:非零元素个数远远少于零元素个数的矩阵

广义表是 n(n>=0) 个数据元素a1, a2, …， an 构成的有限序列，数据元素可以是单个元素（称为单元素），也可以是广义表（称为子表或表元素）。是递归定义。 广义表一般表示为:

LS = ( a1, a2, …， an )

n 称为广义表的长度，n=0 时称为空表

小根堆（大根堆）是具有如下特性的一棵完全二叉树：

(1) 若根结点存在左孩子，则根结点的值小于等于(大于等于)左孩子结点的值；

(2) 若根结点存在右孩子，则根结点的值小于等于(大于等于)右孩子结点的值；

(3)以左、右孩子为根的子树又各是一个堆。

n 个带权叶子结点构成的所有二叉树中，其中树的带权路径长度WPL最小的二叉树，称为哈夫曼树

构造哈夫曼树算法如下：

①对给定n个权值{w1,w2,…,wn}的叶子结点，构成

具有n棵二叉树的森林F={T1,T2,…,Tn}, 其中每棵二叉树Ti只有一个权值为Wi的根结点，其左右子树为空。

②在F中选取两棵根结点的权值最小的树作为左右

子树构造一棵新的二叉树，且新的二叉树的根结点的

权值为其左右子树上根结点的权值之和。

③从F中删除构成新树的两棵树，并把新树加入到F中。

④重复 2、3两步，直到F只有一棵树为止。则F中的树就是哈夫曼树。 所有兄弟结点之间加一条连线；除第一个双亲结点的孩子，所有

第二篇：数据结构考点总结

数据结构考点总结（清华大学C语言版）

1. 绪论》解答题：简述对【算法的五大特征，四大设计要求】的理解。 自己的话解释一下即可。

参考书上P13

2. 线性表》编程题：线性表的单链表形式，排序、逆序；两个（有序）链表的合并与求交。 排序：思想和数字的排序一样，只不过交换的是两个“结点”，代码如下：

LNode *p,*q,*k;

for(p=List->next;p!=NULL;p=p->next)

{

k=p;

for(q=k->next;q!=NULL;q=q->next)

{

if(q->data<k->data) k=q; }

if(k!=p)//注意交换结点的方法！！！！！！！！！！！！！

{

} } LNode *knext=k->next;//保存指针 LNode *pnext=p->next; LNode temp=*k; *k=*p; *p=temp; k->next=knext;//把原指针送回去 p->next=pnext;

3.

4.

5.

6.

7. 以上代码是头结点未使用的单链表List。 求交、合并代码参考书上P31代码。 栈和队列》解答题：表达式求值【画示意图】。 参考书上P54例3-1的图。 数组和广义表》解答题：稀疏矩阵的转置，一般转置（参考书上P99代码）和快速转置（参考书上P100代码）。 数组和广义表》解答题：根据广义表的存储结构还原出原广义表或根据给出的广义表画出对应的广义表存储结构。（表头表尾结构和层次结构建议大家都看看） 另外：广义表的表头、表尾等相关概念的含义建议大家看一下。 参考书上P108---P110。 树和二叉树》编程题：二叉树的遍历（递归非递归） 自己感觉如果考非递归，中序非递归可能性比较大，参考书上P130代码。另外，建议熟悉一下二叉树的五个性质，参考书上P123相关文字。 （鉴于水平有限，先序非递归、后续非递归代码就不再贴出。可以问度娘的~~~） 树和二叉树》解答题：根据给出的树，画树的存储结构示意图。

三种存储结构：双亲法、孩子法、（带双亲的孩子表示法）、孩子兄弟表示法。本人认为孩子兄弟表示法比较终点，因为和“森林与二叉树的转换”相关，所以建议看看“森林

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19. 与二叉树的转换”。 参考书上P135---P138。 树和二叉树》解答题：画哈夫曼树的执行过程图或示意图，注意看清是执行过程图还是示意图。 执行过程图参考书上P148图6.26；示意图参考书上P149图6.27。 图》解答题：根据给出的图，画出相应的存储结构（数组、邻接表）示意图。本人认为数组表示的存储结构考的可能性更大些。 参考书上P161和P163。 图》编程题：深度优先遍历和广度优先遍历。 参考书上P169和P170相关代码。 图》解答题：画最小生成树执行过程图（Prim算法）；或者画示意图（Prim算法和Kruskal算法）。 参考书上P174图7.14和P176图7.18 图》编程题：拓扑排序。问题也可能这样出—“判断图中是否有回路”，如果这样，拓扑和遍历都可以实现。 参考书上P182算法7.12相关代码 图》解答题：画关键路径和最短路径其中之一的执行过程图。 参考书上P186图7.31和P190最上面的图 查找》编程题：折半查找。 参考书上P220算法9.2相关代码 也可能考折半查找执行过程图，参考书上P219相关图表 查找》解答题：给一堆数据，根据“索引顺序表的查找”中相关算法思想，为这些数据建立索引，即建立存储结构。。 参考书上P225。 查找》解答题：二叉排序树、平衡二叉（排序）树、B-树插入删除过程中树形状的变化示意图。 参考书上P230图9.9和P234图9.12和P235图9.13和P242图9.16和P245图9.17 （这部分略麻烦，但是不难，建议大家找个安静的地方静下心来看看，，很简单的~~~） 查找》解答题：根据给出的哈希函数，构造哈希表。注意解决冲突的几种方法。 参考书上P257和P258。 内部排序》基数排序和希尔排序的画示意图；快排和堆排的编程。 希尔排序参考书上P271图10.5； 基数排序参考书上P287图10.14； 快排参考书上P174算法10.6和P175图10.7； 堆排参考书上P282算法10.10和算法10.11、和P281图10.11和图10.12。 据说还有几个小题，估计是某算法的时间复杂度等的分析，也可能考察对某些概念的理

解。所以建议大家看下各个排序和查找算法的时间复杂度以及自己不是很清楚的概念。

最后郑重申明：本人只是根据老师复习时的提示总结出相关考点，考不考不一定，用老师说的话就是“我说的百分之百考也就是50%”。不过作为计算机专业的，这些都是基本功，建议大家认真学习！！！！

最后祝大家期末考个好成绩~~~~~