地科数据结构总复习指导

1、数据结构复习备考指南下面列出的只作为复习重点，并非是考试题，可能是考试相关知识点的罗列；总则：认真复习每一次实验报告当中的内容，认真复习作业当中的内容；认真复习上课讲解的重要内容与课件；认真复习所上章节当中每个知识的基本概念；第一章*1：数据结构的概念，数据的逻辑结构和物理结构的联系与区别数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型的一门学科。简单地说，数据结构是指相互有关联的数据元素的集合，即数据的组织形式。*数据项、数据类型、数据元素、数据变量2、数据的逻辑结构和存储结构1、数据的逻辑结构

2、数据的逻辑结构是指数据之间的相互关系。一般包括：线性结构和非线性结构。1）线性结构：其特点是：结构中有且仅有一个始结点和一个终结点，始结占只有一个后继结点，终结点只有一个前趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。 线性结构最一般的情形是线性表。如下图：线性表 2）非线性结构 其特点是：结构中的结点可能有多个前趋结点和多个后继结点。通常有集合，树和网三种类型。如下图。最重要的非线形结构是“树”，树中有且仅有一个没有前趋结点的结点，称之为根结点；其他结点都仅有一个前趋结点，但允许有多个后继结点。从根结点到任一非根结点，都有且仅有一条路径。 集合 树 网2、数据的存储结构数据的最基本的

3、存储结构一般有以下四种： *顺序存储方法，链接存储方法，索引存储方法，散列存储方法。3 算法的五个特性： 有穷性 可行性 确定性 输入 输出参看教材。4 算法中基本操作重复执行的次数依据算法中最大语句频度来估算，它是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n)，表示随问题规模n的增大，算法执行时间的增长度和f(n)的增长度相同。 常用时间复杂度有如下关系：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)*参考练习分析以下程序段的时间复杂度。for(i=0;in;i+)for(j=0;jm;j+) Aij=0;解：该程序段的时间

4、复杂度为O(m*n)。如果m=n? Aij=0;改成x+;x=x+1;又为多少？在线性结构、树形结构和图形结构中，元素之间的联系分别对应为-、-和-一个算法的效率可分为-和-下面的程序段中，对x赋值的语句频度为-for(i=0;in;i+)for (j=0;ji;j+)for (k=0;kj;k+)x=x+m;数据的存储结构可用四种基本的存储方法表示，它们分别是-、-、-、-*理解数组与结构的定义与特征；并能够给出数组与结构的应用 线性第1部分*线性表的逻辑特征从以上的定义及例子可以看出，线性表具有以下逻辑特征：1）在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a

5、2；2）有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继ai+1。线性表是一种典型的线性结构。*2、顺序表的结构类型定义/*顺序表的定义：*/#define ListSize 100/*表空间大小可根据实际需要而定，这里假设为100*/typedef int DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef structDataType dataListSize;/*向量data用于存放表结点*/int length;/*当前的表

6、长度*/SeqList;*/*顺序表的建立：*/void CreateList(SeqList *L,int n)int i; for (i=0;idatai);L-length=n;/*顺序表的打印：*/void PrintList(SeqList L,int n)int i;for (i=0;in;i+)printf(%d ,L.datai);printf(n);顺序表的查找算法/*顺序表的查找：*/int LocateList(SeqList L,DataType x)int i=0;while (iL.length & L.datai!=x) +i;if (iTop=-1;s-Maxs

7、tack=maxsize;*2）判断栈是否为空BOOL isempty(Stack s)return s.Top=s.Maxstack-1;*4) 入栈void Push(Stack *s,T x)if(isfull(*s) printf(underflow);else s-Elements+s-Top=x;*5）出栈void Pop(Stack *s) if(isfull(*s) printf(underflow); else s-Top-;*参考练习1）线性表和栈都是-结构，可以在线性表的-位置插入和删除元素，对于栈只能在-位置插入和删除元素（2）一个栈的入栈序列是A、B、C、D、E，则栈

8、的出栈序列是-（3）顺序栈是空栈的条件是-A top=0 B top=1 C top=-1 D top=m (4) 栈是限定在- 处进行插入或删除操作的线性表A端点 B栈底 C栈顶 D中间（5）设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后（push每次操作是压入一个元素，pop每次操作弹出一个元素），输出序列是2，3（）栈是限定在（_）处进行插入或删除操作的线性表A端点 B栈底 C栈顶 D中间线性第2部分队列*队列的定义队列（Queue）也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允

9、许删除的一段称为队头（Front），允许插入的一段称为队尾（Rear）。出队出队a1a2a3aian队头（front）队尾（rear）队列的修改是按先进先出的原则进行的。因此，队列又称为先进先出（First In First Out）的线性表，简称为FIFO表。假若队列Q= a1，a2，an，进队列的顺序为a1，a2，an，则队头元素为a1，队尾元素为an。*队列是一个受限的线性表存在惟一的第一个元素（队头） ； 存在惟一的最后一个元素（队尾）； 除第一个元素之外，每个元素均只有一个直接前驱； 除最后一个元素之外，每个元素均只有一个直接后继*循环队列（Circular Queue）（教材当中）

10、1） 基本概念2） 循环队列满队与空队的条件判断*参考练习(1)队列是限定在（）处进行插入操作的线性表-A端点 B队头 C队尾 D中间（2）队列的特点是-A先进先出 B后进先出 C先进后出 D不进不出（3）循环队列Sq是空队列的条件是-ASq-read=Sq-front B(Sq-read+1)%maxsize=Sq-front C Sq-read=0 D Sq-front=0(4) 循环队列Sq是满队列的条件是- ASq-read=Sq-front B(Sq-read+1)%maxsize=Sq-front C Sq-read=0 D Sq-front=0（）队列是限制插入只能在-，而删除在

11、表的-的线性表。线性第3部分数组1、数组的定义数组（Arrays）是由一组类型相同的数据元素构造而成的。它的每个元素由一个值和一组下标确定。一维数组:如果数组元素只含有一个下标，这样的数组称为一维数组。如果把数据元素的下标顺序换成线性表中的序号，则一维数组就是一个一维数组。二维数组: 如果数组的每一个元素都含有两个下标，这样的数组称为二维数组，也称为矩阵（Matrix）。如下图，Amn就是一个m行n列的矩阵，可以用一个二维数组来表示，它的每一个元素由aij及一组下标来确定。数组一旦被定义，它的维数就不再改变。因此，数组通常只有两种基本运算：给定一组下标，存取相应的数据元素和修改相应的数据元素的

12、值。数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。下面主要介绍二维数组的顺序存储结构。要将二维数组的元素按顺序结构进行存储，就必须要按某种次序将元素排成一个线性序列。通常有两种存储方式来存储二维数组的元素：行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。在PASCAL、C语言中，数组就是按行优先顺序存储的。如：a11,a12,a1n,a21,a22,a2n,am1,am2,amn 列优先顺序：列优先顺序：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。在FORTRAN语言中，数组就是按列优先顺序存储的。如：a11,a21,am1,a1

13、2,a22,am2,an1,an2,anm我们很容易根据数组元素的下标，求出其存储地址。设二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，则aij的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)n+j-1d对应C语言来说，数组Amn的两个下标的下界均为0，上界分别为m-1、n-1，每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由下列公式确定。LOC i,j= LOC 0,0+( n * i + j ) * k其中，loc0,0是A00的存储位置，它是该二维数组的起始地址。loci,j是Aij的存储位置。这个式子确定了C语言的二维数组元

14、素的位置和下标的关系。稀疏矩阵（Sparse Matrix）：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(s=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。如图： 一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。从该定义可知：只有一个结点的树，该结点为根结点；多个结点的树，除根结点之外，它的M棵子树T1，T2，Tm也是树，且互不相交。*2、有关术语度（Degree）：一

15、个结点拥有的子树数称为该结点的度。树的度：一棵树的度是指该树中结点的最大度数。叶子（Leaf）和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。双亲（Parents）和孩子（Child）：树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。兄弟（Sibling）和堂兄弟：同一个双亲的孩子称为兄弟。双亲在同一层的结点互为堂兄弟。祖先（Ancestor）和子孙（Descendant）：一个结点的祖先是指从树的根到该结点所经分枝上的所有结点（包括根结点）。一个结点的子树的所有结

16、点都称为该结点的子孙。结点的层数（Level）：是从根起算，设根的层数为1，其余结点的层数等于其双亲结点的层数加1。树的高度（Height）：树中结点的最大层数称为树的高度或深度（Depth）。有序树（Ordered Tree）和无序树（Unordered Tree）：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。森林（Forest）：是m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林；反之，给一个森林加上一个结点，使原森林的各棵树成为所加结点的子树，便得到一棵树。*二、二叉树二叉树在树结构的应用中起着非常重要的作用，因

17、为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。1、二叉树的定义二叉树（Binary Tree）是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。若二叉树为空集，则称为空二叉树。二叉树是有序的，它的每个结点至多只有两棵子树，且有左、右之分，不能互换；左右子树也可以是空二叉树。2、二叉树的基本形态二叉树的基本形态一般有下面这些：AABABACB空二叉树 仅有根结点的二叉树右子树为空的二叉树 左子树为空的二叉树 左右子树均非空的二叉树*3、树与二叉树的区别1

18、）树至少包含一个称为根的结点，而二叉树可以是空二叉树； 2）树的结点可有任意有限棵子树（直接后续），而二叉树的任一结点至多只有两棵子树（直接后续）；3）树中各子树可以不必区分各子树之间的次序（但有序树规定了左、右排列次序），而二叉树中将两棵子树明确地区分为左子树和右子树，并且当二叉树中一棵子树为空、另一棵子树为非空时，也要明确地指出它们的左、右次序。*4、二叉树的特殊形态满二叉树（Full Binary Tree）：一棵深度为k且有2k-1个结点的二叉树。 满二叉树特点1：二叉树的所有分支结点都存在左子树和右子树 特点2：二叉树的所有叶子结点都在同一层上 完全二叉树（Complete Bina

19、ry Tree）：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。即第1层到第k-1层构成一棵深度为k-1的满二叉树，第 k层的结点不满2k-1个结点，而这些结点都满放在该层最左边(若某个结点没有左孩子，则一定没有右孩子)。如下图。特点1：叶子结点只可能在层次最大的两层上出现 特点2：对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为 L 或 L+1 完全二叉树 非完全二叉树满二叉树和完全二叉树的关系：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。*5、二叉树的性质（特别是课件上的几个思考题）性质1：在

20、二叉树的第i层上至多有2i-1个结点（i1）。性质2： 深度为k的二叉树至多有2k-1个结点（k1）。性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n21性质4： 具有n个结点的完全二叉树的深度为 log2n +1(其中 x 表示“不大于x的最大整数”)性质5： 如果对一棵有n个结点的完全二叉树（其深度为 log2n +1）的结点按层序编号（从第1层到第 log2n +1层，每层从左到右），则对任一结点i（1in），有1） 如果 i=1，则结点i是二叉树的根，无双亲；如果 i1，则其双亲PARENT(i)是结点i/2。 2） 如果2in，则结点i无左孩子（

21、结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。 3）如果2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1三链式存储结构rchildDatalchild链式存储结构：二叉树的链式存储结构是用链来建立树中结点之间的关系，二叉树的这种链式存储结构我们通常称为二叉链表。在链式存储结构中，每个结点包括三个域：数据域和左、右指针域。结点类型说明如下：有时，也可以采用含有三个指针域的结点结构： *四遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个

22、结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。其递归算法为(假设以链式结构存储)：voi

23、d PreOrder(BinTNode *T) if(bt!=NULL) printf(“%c”,bt-data); PreOrder(bt-lchild); PreOrder(bt-rchild); 2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。其递归算法为(假设以链式结构存储)：void InOrder(BinTNode *T) if(bt!=NULL) InOrder(bt-lchild); printf(“%c”,bt-data); InOrder(bt-rchild); 3、后序遍历二叉树的操作定义为：若二叉

24、树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。其递归算法为(假设以链式结构存储)：void PostOrder(BinTNode *T) if(bt!=NULL) PostOrder(bt-lchild); PostOrder(bt-rchild) ; printf(“%c”,bt-data); 五树和森林参看课件内容 * *（一）树、森林与二叉树的转换1、树转换为二叉树的步骤（1）在所有兄弟结点之间加一连线；（2）对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线；（3）以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分。2、

25、森林转换成二叉树的步骤（1）先将森林中的每棵树变为二叉树； （2）将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。3、二叉树转换为森林的步骤（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子都与该结点的双亲结点用线连起来； （2）删掉原二叉树中所有的双亲结点与右孩子结点的连线； （3）整理上述两步所得到的树或森林，使之结构层次分明。六Huffman树及应用（参看课件*，特别是我们实验所讲的那个程序的解读）1、基本术语路径（Path）：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度：路径上的分支数目称做路径长度。树的路径长度：从树根到每一结

26、点的路径长度之和。树的带权路径长度（Weighted Path Length of Tree）：树中所有叶结点的带权路径长度之和。记作：WPL=Huffman树：又称最优二叉树，它是n个带树叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。2、Huffman树的构造算法Huffman树的构造算法描述如下：(1) 根据给定的n个权值w1,w2,，wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2) 在F中选取两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和

27、。(3) 在F中删除这两棵树，同时将新得到的二叉树加入F中。(4) 重复(2)和(3)，直到F只含一棵树为止。这棵树便是 Huffman树。*参考练习：8 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，则该二叉树的先、中、后序遍历序列为先序序列： 二叉树的几个重要性质及其变化如一棵深度为k的满二叉树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为_，最大值为_2k-1，2k-1设一棵完全二叉树具有10001002998个结点，则它有多少个叶子结点?有多少个度为2的结点?并给出求解过程。树与二叉树相互转化的步骤及其写出最终结果Huffman树的创建与编码，参考实

28、验程序/参考课件* *优胜树,堆的概念，大根堆，小根堆的概念*编程创建：二叉树创建，遍历，以及求其结点数和叶子结点数（注意复习作业当中的相关内容）第6图*一、基本术语图（Graph）：图G由两个集合V和E组成，记为G=(V,E)，这里，V是顶点的有穷非空集合，E是边（或弧）的集合，而边（或弧）是V中顶点的偶对。 顶点（Vertex）：图中的结点又称为顶点。 边（Edge）：相关顶点的偶对称为边。 有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，vi，vj表示一条有向边，vi是边的始点（起点）

29、，vj是边的终点。因此，vi，vj和vj，vi是两条不同的有向边。弧（Arc）：又称为有向边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。 弧尾（Tail）：边的始点。 弧头（Head）：边的终点。 无向图（Undigraph）：若图G中的每条边都是没有方向的，则称G为无向图。 在无向图中，一条无向边是由两个顶点组成的无序对，无序对通常用圆括号表示。例如，(vi，vj)表示一条无向边，(vi，vj)和(vj，vi)是一样的。顶点vi和vj互为邻接点。邻接点（Adjacent）：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点。无向完全图（Undirecte

30、d Complete Graph）：恰好有n(n-1)/2的无向图。 有向完全图（Directed Complete Graph）：恰好有n(n-1)条边的有向图。度（Degree）：无向图中顶点v的度是关联于该顶点的边的数目，记为TD(v)。 入度（Indegree）：若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID(v)。 出度（Outdegree）：若G为有向图，则把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。 对于有向图：TD(v)=ID(v)+OD(v) 子图（Subgraph）：设G=(V,E)是一个图，若E是E的子集，V是V的子集，使得E中的边仅与V

31、中顶点相关联，则图G=(V,E)称为图G的子图。 路径（Path）：无向图G=(V,E)中从顶点v到顶点v的路径是一个顶点序列(v=vi0,vi1,vin=v)，其中(vij-1,vij)E，1jn。有向图G=(V,E)中从顶点v到顶点v的路径是一个顶点序列v=vi0,vi1,vin=v，其中vij-1,vijE，1jn。 简单路径：序列中顶点不重复出现的路径。 环（Cycle）：又称回路，第一个顶点和最后一个顶点相同的路径。 简单回路：又称简单环，除了第一个顶点和最后一个顶点外，其余顶点不重复的回路。连通：在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的。 连通图（Connect

32、ed Graph）：如果对于图中的任意两个顶点vi、vjV，vi和vj都是连通的，则称该图为连通图。 连通分量（Connected Component）：无向图中的极大连通子图。 强连通图：在有向图G中，如果对于每一对vi，vjV，vivj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。 强连通分量：有向图中的极大连通子图。 生成树（Spanning Tree）：含有连通图的全部顶点的一个极小连通子图。 顶点数为n，则边数为n-1。若边数大于n-1，则不是一个极小连通子图；若边数小于n-1，则不连通。网络（Network）：若将图的每条边都赋上一个权，则称这种带权图为网络。 *什么叫权？二、图的存储结构 1、邻接矩阵表示法*邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵： 例：给出一个有向图或无向图，请写出其邻接矩阵。（*）邻接矩阵特点 ：无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个