数据结构C语言考试重点必背

1、1/ 11第一章： 绪论1.1 ：数据结构课程的任务是：讨论数据的各种 逻辑结构 、在计算机中的存储结构以及 各种操作的算法设计。1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机 接收的各种集合的统称。数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的 基本单位 。 数据项 ：是数据元素中有独立含义的、不可分割的最小标识单位。数据结构概念包含三个方面：数据的 逻辑结构 、数据的存储结构的数据的操作。1.3 数据的 逻辑结构 指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合 上的若干关系来表示，数据结构可以分为三种： 线性结构 、树结构和图。1.

2、4 ：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结构。 数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。2.1 ：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问 题的操作序列。算法规则需满足以下五个特性：输入 算法有零个或多个输入数据。输出 算法有一个或多个输出数据，与输入数据有某种特定关系。有穷性 算法必须在执行又穷步之后结束。确定性 算法的每个步骤必须含义明确，无二义性。可行性 算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和 纸做有穷次就可以完成。有穷性和可行性是算法最重要的两个特征。2.2 ：算法与数据结构 ：算法

3、建立数据结构之上，对数据结构的操作需用算法来描述。 算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。2.3 ：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结高时间效率：算法的执行时间越短，时间效率越高。 果。2/ 11高空间效率：算法执行时占用的 存储空间 越少，空间效率越高。 可读性：算法的可读性有利于人们对算法的理解。2.4 ：度量算法的时间效率， 时间复杂度 ，(课本 39 页)。2.5 ：递归 定义：即用一个概念本身直接或间接地定义它自己。 递归 定义有两个条件：

4、至少有一条初始定义是非 递归 的， 如 1！ =1. 由已知函数值逐步递推计算出未知函数值， 如用( n-1 )！定义 n！。 第二章： 线性表1.1 线性表：线性表是由 n(n=0)个类型相同的数据元素 a0,a1,a2,a组成的有限 序列，记作：Li nearList = (a0,a1,a2,-1)a n其中，元素 ai 可以是整数、 浮点数 、字符、也可以是对象。 n 是线性表的元素个数， 成为线性表长度。若 n=0 ，则 LinearList 为空表。若 n0 ，则 a0 没有前驱元素， an-1 没有后继元素，ai(0in-1 )有且仅有一个直接前驱元素 ai-1 和一个直接后继元素

5、 ai+1 。1.2 线性表的顺序存储是用一组连续的内 存单元依次存放线性表的数据元素，元素在内 存的物理存储次序与它们在线性表中的逻辑次序相同。线性表的数据元素数据同一种数据类型，设每个元素占用 c 字节，a0 的存储地址为Loc (a0)，贝 V ai 的存储地址 Loc (ai)为：Loc (ai) = Loc (a0) + i*c数组是顺序存储的随机存储结构，它占用一组连续的 存储单元 ，通过下标识别元素， 元素地址是下标的 线性函数 。1.3：顺序表的插入和删除操作要移动数据元素。平均移动次数是属数据表 长度的一半。(课本第 50 页)1.4：线性表的链式存储是用若干地址分散的 存储

6、单元 存储数据元素，逻辑上相邻的数 据元素在物理位置上不一定相邻，必须采用附加信息表示数据元素之间的顺序关系。它有两个域组成：数据域和地址域。通常成为节点。(课本第 55 页及 56 页)1.5 单链表 (课本 56 页)单链表 的遍历：Node p = head; while(p!=null)访问 p 节点；p = p.next;单链表 的插入和删除操作非常简便，只要改变节点间的链接关系，不需移动数据元素。单链表的插入操作： 1)：空表插入 /头插入 2) 中间插入/尾插入3/ 11if(head = null)Node q = new Node(x); head = new Node(x)

7、; q.next = p.next;else p.next = q;Node q=new Node(x); 中间插入或尾插入都不会改变单表q.next = head; 的头指针 head 。head = q;单链表 的删除操作：头删除： head = head.next;中间 / 尾删除：if(p.next!=null) p.next = p.next.next; 循环单链表：如果单链表最后一个节点的 next链保存单链表的头指针 head 值，则该 单链表成为环形结构，称为循环单链表。(课本 67)若 rear 是单链表的尾指针，则执行( rear.next=head; )语句，使单链表成为

8、一条循环 单链表。当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 =

9、p.prev;循环双链表：当 head.next=head 且 head.prev=head 时，循环双链表为空。第三章：栈和 队列1.1 栈：栈是一种特殊的线性表，其中插入和删除操作只允许在线性表的一端进行。允许操作的一端称为栈顶，不允许操作的一端称为栈底。栈有顺序栈和链式栈栈中插入元素的操作称为入栈，删除元素的操作称为出栈。没有元素的中称为空栈。 栈的进出栈顺序：后进先出，先进后出。(及75 页的思考题)。4/ 111.2 ：队列 ：队列是一种特殊的线性表，其中插入和删除操作分别在线性表的两端进行。 向队列中插入元素的过程称为入队，删除元素的过程称为出对，允许入队的一端称为 队尾，允许出队

10、的一端称为对头。没有元素的队列称为空队列。队列是 先进先出 。 第四章：串1.1 ：串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。一个串记为：s= “ s0s1s2 -1 ”n 其中 n=O,s 是串名，一对 双引号括起来的字符序列 s0s1s2sn 是串值，si(i=0，1，2，-n-1 )为特定字符集合中的一个字符。一个串 中包含的字符个数称为串的长度。长度为 0 的串称为空串，记作 “，”而由一个或多个空格字符构成的字符串称为空格串。 子串：由串 s 中任意连续字符组成的一个子序列sub 称为 s 的子串，s 称为 sub 的主串子串的序号是指该子串的第一个字符在主串中

11、的序号。串比较：两个串可比较是否相等，也可比较大小。两个串(子串)相等的 充要条件 是 两个串(子串)的长度相同，并且各对应位置上的字符也相同。两个串的大小由对应位置的第一个不同字符的大小决定，字符比较次序是从头开始依 次向后。当两个串长度不等而对应位置的字符都相同时，较长的串定义为较 “大”。 第五章：数组和广义表1.1 ：数组是一种数据结构，数据元素具有相同的 数据类型 。一维数 组的逻辑结构是线 性表，多 维数 组是线性表的扩展。1.2 ：一 维数 组：一维数组采用顺序存储结构。一个一维数组占用一组连续的 存储单元设数组第一个元素 a0 的存储地址为 Loc (a0)，每个元素占用 c

12、字节，则数组其他元素 ai 的存储地址 Loc (ai)为： Loc (ai) = Loc (a0) +i*c数组通过下标识别元素，元素地址是下标的 线性函数 。一个下标能够唯一确定一个元 素，所划给的时间是 O(1 )。因此数组是随机存取结构，这是数组最大的优点。1.3 ：多维数组的 遍历 ：有两种次序：行主序和列主序。行主序：以行为主序，按行递增访问数组元素，访问完第 i 行的所有元素之后再访问第 i+1 行的元素，同一行上按列递增访问数组元素。aOO,aO1,aO-n）, a10,a11,a1（n a（m1）0,a（m- 1）1,，a（m1）（n-1）2） 列主序：以列为主序，按列递增访

13、问数组元素，访问完第 j 列的所有元素之后再 访问第 j+1列的元素，同一列上按列递增访问数组元素。多维数组的存储结构：多维数组也是由多个一维数组组合而成，组合方式有一下两 种。5/ 11静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储。 按行主序存储时，元素 aij 的地址为： Loc（ aij ） = Loc （a00）+（i*n+j ）*c按列主序存储时， Loc（aij）= Loc （a00）+ （j*m+i ）*c 动态多维数组的存储结构。二维数组 元素地址就是两个下标的 线性函数 。无论采用哪种存储结构，多维数组都 是基于一维数组的，因此也只能进行赋值、取值两种存取操作，

14、不能进行插入，删除 操作。树是数据元素（结点）之间具有层次关系的非 线性结构 。在树结构中，除根以外的结 点只有一个直接前驱结点，可以有零至多个直接后继结点。根没有前驱结点。树是由 n（n=0 ）个结点组成的有限集合（树 中元 素通常称为结点）。N=0 的树称为 空树；n0大的树 T；有一个特殊的结点称为根结点，它只有后继结点，没有前驱结点。除根结点之外的其他结点分为 m（m=0 ）个互不相交的集合 T0,T1,T3 .,T-m1 ， 其中每个集合 Ti（ 0=i=0 )棵互不相干的树的集合。给森林加上一个根结点就变成一棵树， 将树的根节点删除就变成森林。二叉树的性质 1:若根结点的层次为 1

15、,则二叉树第 i 层最多有 2 的 i-1 次方(i=1 ) 个结点。二叉树的性质 2:在高度为 k 的二叉树中，最多有 2 的 k 次方减一个结点。二叉树的性质 3:设一棵二叉树的叶子结点数为n0,2 度结点数为 n2,则 nO=n2+1。一棵高度为 k 的满二叉树是具有 2 的 k 次方减一个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点进行连续编号,约定根节点的序号为0,从根节点开始,自上而下,每层自左至右编号。一棵具有 n 个结点高度为 k 的二叉树,如果他的每个节点都与高度为 k 的满二叉树中序号为 0n-1的结点一一对应，则这棵二叉树为为 完全二叉树 满二叉

16、树是 完全二叉树 ，而 完全二叉树 不一定是满二叉树。完全二叉树的第 1k-1 层 是满二叉树第 k 层不满，并且该层所有结点必须集中在该层左边的若干位置上。二叉树的性质 4：一棵具有 n 个结点的完全二叉树，其高度 k=log2n 的绝对值 +1二叉树的性质 5：一棵具有 n 个结点的完全二叉树，对序号为 i 的结点，有若 i=0，则 i 为根节点，无父母结点；若 i0，则 i 的父母结点的序号为(i-1) /2。若 2i+1n，贝 V i 的左孩子结点序号为 2i+1 ；否则 i 无左孩子。若 2i+2n ，则 i 的右孩子结点的序号为 2i+2 ，否则 i 无右孩子。二叉树的 遍历二叉树

17、的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访 问一次。二叉树的三种次序遍历1 ：先根次序；访问根节点，遍历左子树，遍历右子树。7/ 112：中根次序；遍历左子树，访问右子树，遍历右子树。3：后根次序；遍历左子树，遍历右子树，访问根节点。先根次序遍历时，最先访问根节点；后根次序遍历时，最后访问根节点；中根次序遍 历时，左子树上的结点在根节点之前访问，右子树上的结点在根节点之后访问。二叉树的插入和删除操作 P147二叉树的层次遍历 P149习题 P167 6 10， 619第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系。顶点之间的关系成为边。一个图 G 记为 G

18、= (V,E), V 是顶点 A 的有限集合，E 是边的有限集合。即 V=A|A 属于某个数据元素集合 E=(A,B)|A,B 属于 V或 E=|A,B 属于 V 且 Path (A,B) 其中 Path (A,B)表示 从顶点 A 到B 的一条单向通路，即 Path (A,B)是有方向的。无向图中的边事没有方向，每条边用两个顶点的无序对表示。有向图中的边是有方向，每条边用两个顶点的有序对表示。完全图指图的边数达到最大值。n 个顶点的完全图记为 Kn。无向完全图 Kn 的边数为n* ( n-1)/2,有向完全图 Kn 的边数为 n* ( n-1 )。子图：设图 G=(V,E),G =(V,若，

19、日包含于 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 的路径，则称该图 的强连通图。非强连通图的极大强连通子图称为该图的强连通图分量。图的遍历遍历图

20、是指从图 G 中任意一个顶点 V 出发，沿着图中的边前行，到达并访问图中的所 有顶点，且8/ 11每个顶点仅被访问一次。遍历图要考虑一下三个问题：指定遍历的第一个访问顶点由于一个顶点可能与多个顶点相邻，因此要在多个邻接顶点之间约定一种访问次序。由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到该顶点。深度优先搜索图的深度优先搜索 策略是，访问某个顶点 v，接着寻找 v 的另一个未被访问的邻接顶点 w 访问，如此反复执行，走过一条较长路径到达最远顶点；若顶点v 没有未被访问的其他邻接顶点，则回到前一个被访问顶点，再寻找其他访问路径。图的 深度优先搜索 遍历算法 P188联通的无回路

21、的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点 。各连 通分量均为树的图称为森林，树是森林。由于树中无回路，因此树中必定无自身环也无重边（否则他有回路）若去掉树中的任 意一条边，则变成森林，成为非联通图；若给树加上一条边，形成图中的一条回路， 则不是树。 P191生成树 和生成森林：一个连通无向图的 生成树 是该图的一个极小联通生成子图，它包含原图中所有顶点（n个）以及足以构成一棵树的 n-1 条边。一个非联通的无向图，其各连通图分量的生成图组成该图的生成森林。图的生成图或生成森林不是唯一的，从不同顶点开始、采用不同遍历可以得到不同的 生成树 或森林。在生成树中，任何树中，任何两个顶点之间只有唯一的一条路径。第八章折半查找算法描述 P206,P207二叉排序树 及其查