1、江苏省计算机等级考试三级偏软,欣诚教育,第2章 数据结构,主要内容,算法及其描述数据、数据元素和数据结构线性表栈和队列数组树图查找排序,算法及其描述,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法特性：有穷性确定性可行性输入，零个或多个输入。输出，一个或多个输出。,程序并不需要满足有穷性,算法及其描述,算法的描述方式流程图自然语言伪代码程序设计语言,C+,算法及其描述,算法设计要求（评价指标）：正确性健壮性 （如对非法数据的处理和反应）可读性简单性 （采用的数据结构和方法的简单程度）时间效率高存储空间少,算法分析,算法复杂度语句频度，算法中该语句执
2、行的次数。一个算法中所有语句的频度之和构成该算法的运行时间。一个算法的语句频度是其求解问题规模n的函数，记为T(n)。如果有某个函数F(n)，使得当问题规模n趋于无穷大时，有：则将O(F(n)称作算法的时间复杂度。,算法分析,算法复杂度例：下面算法为求n个自然数的和S=1+2+3+n。请给出该算法的语句频度。 sum(int n) int i, s=0; for (i=1;i=0）个具有相同特性的数据元素（结点）a1, a2, a3, , an组成的有限序列。通常记作： L =（a1, a2, a3, , an）n=0 时称为空表；表中 ai-1 是ai 的直接前驱，ai+1 是ai 的直接后
3、继；线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱和直接后继；ai是线性表的第 i 个元素，称 i 为数据元素ai 的序号，每一个元素在线性表中的位置，取决于其序号。,线性表,例1：一组实验数据（41, 21, 34, 53, 62, 71, 76, 45） 例2：26个大写英文字母组成的字母表（A, B, C, , Z） 例3：学生成绩统计表也是一个线性表。,线性表,顺序存储结构用一组地址连续的内存单元依次存放线性表的数据元素。,a1a2ai-1aiai+1an,Loc(ai ) = Loc( a1 )+ ( i 1)* L,Loc( a1 ),Loc(ai ),每
4、个元素占L个存储单元,顺序表通过元素的存储顺序反映线性表元素间的逻辑关系,线性表,顺序存储结构 #define max 100 / 线性表可能的最大长度 typedef struct sequenlist ElemType emax; /定义线性表为一维数组 int n; /当前线性表长度 SqList;,线性表,链式存储结构用一组地址任意的存储单元来存放表中各数据元素。特点：数据元素的逻辑次序和物理次序不一定相同。在存储数据元素时，除了要存储数据元素本身的信息外，还必须附加一个或多个指针用于指向该结点的后继结点或前驱结点的存储地址（或位置）。常见的链表有3种：单链表、循环链表、双链表,线性表
5、,线性表的链式存储结构单链表单链表中结点：,Typedef struct Node ElemType data; Struct Node *next; slink;,线性表,线性表的链式存储结构单链表,head=NULL，则该链表称为空表。,（不带表头结点）,线性表,线性表的链式存储结构单链表,head是头指针,ai-1,a2,a1,头结点,head,（带表头结点）,线性表,线性表的链式存储结构双向链表双向链表中结点：,线性表,线性表的链式存储结构循环链表,线性表,线性表的链式存储结构循环链表,线性表,线性表的链式存储结构双向循环链表,head,(b)空的双向循环链表,（c）非空的双向循环链表
6、,head,a,b,C,线性表的基本运算,线性表的插入运算是指在表的第i（1in+1）个（或符合要求的）位置上，插入一个新的结点x，使长度为n的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为n+1的线性表：( a1, , ai1, x, ai, ai+1, an ),线性表的基本运算,顺序表的插入由于顺序表中结点在计算机中是连续存放的，若在第i个结点之前插入一个新结点x，就必须将表中下标位置为i, i+1, , n上的结点依次向后移动到i+1, i+2, , n+1的位置上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结
7、点，直接将x插到表的末尾。新结点插入后，线性表的长度变成n+1。,线性表的基本运算,顺序表的插入在顺序表中插入一个新结点的过程如下： 检查顺序表的存储空间是否已满，若满则停止插入，退出程序运行； 将第in个结点之间的所有结点依次向后移动一个位置，空出第i个位置； 将新结点x插入第i个位置；修改线性表的长度，使其加1； 若插入成功，则函数返回值为1，否则函数值返回值为0。见教材p.45算法2-1,线性表的基本运算,单链表的插入假设指针p指向单链表中某个结点，指针s指向值为x的新待插结点。若将新结点s插入结点p之后，则称为后插；若将新结点s插到结点p之前，则称为前插。后插运算,y,x,p,head
8、,s,线性表的基本运算,单链表的插入后插运算,线性表的基本运算,单链表的插入前插运算,见教材p64算法2-10,线性表的基本运算,双向链表的插入前插运算,线性表的基本运算,双向链表的插入后插运算,线性表的基本运算,线性表的删除运算将线性表中第i个（或符合要求）的数据元素删除，使长度为n的线性表： ( a1, , ai1 , ai , ai+1 , an ) 变成为长度为n-1的线性表：( a1, , ai1, ai+1, an ),线性表的基本运算,顺序表的删除过程： 检查给定结点的删除位置是否正确，若删除位置有错，则显示出错信息，退出程序运行； 把表中第i+1n个结点之间的所有结点依次向前移
9、动一个位置； 将线性表的长度减1。 见教材p46算法2-2,线性表的基本运算,单链表的删除,见教材p65算法2-11,线性表的基本运算,双向链表的删除,顺序表插入和删除运算的时间分析,在线性表顺序存储结构中某个位置上插入和删除一个数据元素时，其插入与删除算法的主要执行时间都耗费在移动数据元素上，而移动元素的个数则取决于插入或删除元素的位置。假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动元素次数的期望值（平均次数）应为：,顺序表插入和删除运算的时间分析,同理，假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动元素次数的期望值（
10、平均次数）应为：,顺序表插入和删除运算的时间分析,假定在线性表任何位置上插入或删除元素都是等概率的，则: pi=1/(n+1) qi = 1/n在等概率情况下，上式可以分别简化为：若顺序表的长度为n，则顺序表的插入算法和删除算法的时间复杂度均为O(n)。,单链表上查找、插入和删除运算的时间分析,设Pi是单链表上查找第i个元素的概率，在长度为n的带头结点的单链表中可能进行查找的位置为i=0, 1, 2, , n。在等概率情况下P1=P2=Pi=1/(n+1)。若查找成功时，则单链表中查找任意位置上数据元素的平均比较次数为：单链表上查找、插入、删除算法的平均时间复杂度为O(n)。,顺序表和链表的比
11、较,空间性能的比较存储密度：存储结点中数据域占用的存储量与存储结点所占用的存储量之比称为存储密度。存储密度越大，则存储空间的利用率就越高。顺序表的存储密度是高于链表的存储密度。但是，顺序表要求事先估计容量，这是比较困难的。,顺序表和链表的比较,时间性能的比较当线性表的主要操作是查找运算时，最好采用顺序存储结构。对于需要频繁地进行插入和删除操作的线性表，最好采用链接存储结构。若链表的插入和删除操作主要发生在表的首、尾两端，采用尾指针表示的单循环链表则是最好的选择。,栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表。,（a1, a2, . , ai -1, ai , ai+1, , an ）,
12、插入,删除,栈,允许进行插入和删除运算的这一端称为栈顶，不允许进行插入和删除运算的另一端则称为栈底；向栈中插入一个新元素称为入栈或压栈，从栈中删除一个元素称为出栈或退栈；记录栈顶元素位置的变量称为栈顶指针，处于栈顶位置的数据元素称为栈顶元素；不含任何数据元素的栈则称为空栈。,栈,栈的特点后进先出,栈,栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。顺序栈可以用一个一维数组和一个记录栈顶位置的整型变量来实现，数组用于顺序存储栈中所有的数据元素，栈顶指针用于存储栈顶元素的位置。,emax,top,stack,栈,栈的链式存储
13、结构以某种形式的链表作为栈的存储结构，其组织形式与单链表类似。,栈,顺序栈的基本运算,见教材p48 算法2-3，算法2-4,栈,链栈的基本运算,栈,共享栈,栈在递归过程中的作用,所谓递归，是指一个函数、过程或者数据结构，若在其定义的内部又直接或者间接出现有定义自身的应用，则称其是递归的或者是递归定义的。在调用一个函数（程序）的过程中又直接或间接地调用该函数（程序）本身，称为函数的递归调用。,栈在递归过程中的作用,一般函数的调用机制,函数调用顺序 A B C,函数返回顺序 C B A,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,栈在递归过程中的作用,
14、递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。,A（ ） A( ) ; ,B( ) C( ) C( ); B( ); ,A 直接调用自己,B间接调用自己,栈在递归过程中的作用,递归算法的编写1）将问题用递归的方式描述（定义）2）根据问题的递归描述（定义）编写递归算法递归定义包括两项1）基本项（终止项）：描述递归终止时问题的求解；2）递归项：将问题分解为与原问题性质相同，但规模较小的问题；,栈在递归过程中的作用,递归算法的编写【例3.7】采用递归算法求解正整数n的阶乘（n！）。 正整数n的阶乘的递归定义为：,栈在递归过程中的作用,递归算法的编写/* 用递归方法求n的阶
15、乘的函数 */ float Fact(int n) float f = 0.0; if (n=j）。则其存储分配情况如图所示。,对称阵的压缩存储,在这种压缩结构中，为了便于访问对称矩阵A中元素并能进行处理，我们必须通过给定的一组下标（i, j）找到对称矩阵中任一元素aij在一维数组Bk中的存储位置，即在aij和Bk之间找到一个对应关系。,三角矩阵的压缩存储,以主对角线划分，三角矩阵分为两种：上三角矩阵和下三角矩阵。上三角矩阵，是指下三角（不包括主角线）中的元素均为常数c的n阶方阵。下三角矩阵，主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为0。对于任何一个n阶下三角矩阵都具有下述性质：
16、当ij时，aij=c；同理，对于任何一个n阶上三角矩阵：当ij时，aij=c。,三角矩阵的压缩存储,三角矩阵采用压缩存储方式时，只存储矩阵的下三角元素或上三角元素。如果让矩阵中所有重复元素c共享一个存储单元，那么三角矩阵中n2个元素就可以压缩存储到一维数组Bn(n+1)/2中，其中重复元素c放在数组的最后一个单元中。若按“行优先顺序”存储下三角矩阵中的元素，则矩阵下三角元素的压缩存储情况如下图所示。,三角矩阵的压缩存储,三角矩阵A中任一元素aij在一维数组Bk中的存储位置。上三角关系下三角关系,树,树是由n（n0）个结点组成的有限集合。若n=0，则树是一棵空树；若n0，则树是一棵非空树。一棵非
17、空树满足如下两个条件： 有且仅有一个特定的结点，该结点称为根结点； 除根结点外的其他结点可分为m（m0）个互不相交的有限集合T1, T2, , Tm，其中每个集合本身又是一棵树，这些集合称为根结点的子树。,树的定义,T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余结点可划分为3个互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M,树,树的定义,树是一种非线性数据结构，其特点是：1）树中每个结点都可以有零个或多个直接后继，若有多个后继结点，则后继结点是该结点的每个子树的根结点。2）除根结点之外的所有结点，有且
18、仅有一个直接前驱。3）数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。4）树型结构中数据元素之间的关系是一对多或者多对一的关系。,树,基本术语1结点的度和树的度结点具有的子树（分支）个数称为结点的度。一棵树中所有结点的度的最大值称为树的度。2叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。,树,基本术语3双亲结点、孩子结点和兄弟结点树中每个结点的子树的根称为该结点的孩子或儿子或子女；相应地，该结点称为孩子结点的双亲或父亲。具有同一个双亲的孩子们之间互称为兄弟。每个结点的祖先是从树的根结点到该结点所经过路径上的所有结点。反之，以某
19、结点为根的子树中的所有结点都称为该结点的子孙。,树,基本术语4结点的层数和树的高度结点的层数从树的根结点开始计算。假设树的根结点为第一层，它的孩子结点为第二层，其余类推。树中结点的最大层数就称为树的高度或深度。5森林森林是m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。6有序树和无序树若树中结点的各子树从左到右是有次序的，且相对次序是不能变换的，则该树被称为有序树，否则称为无序树。,二叉树,定义二叉树是有限的结点集合，这个集合或者为空，或者有一个根结点，它由两棵不相交的分别称为根的左子树和右子树的二叉树组成。左子树和右子树同样又都是一棵二叉树。,二叉树的5种基本形态,
20、二叉树,定义,两棵不同的二叉树,一棵普通的无序树,二叉树,二叉树的性质性质1：在二叉树的第i 层上最多有2i-1个结点。性质2：深度为 h 的二叉树最多有 2h-1 (h=1)个结点。性质3：设二叉树叶子结点数为n0，度为2的结点数为n2，则 n0 = n2 +1。满二叉树：如果深度为 k 的二叉树，有2k-1个结点则称为满二叉树。,二叉树,二叉树的性质完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树。性质4：具有n个结点的完全二叉树的深度为log2n+1,或 log2n+1,二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树
21、的结点按层序编号（每层从左到右），则对任一结点i (11，则其双亲是结点 i/2 ；2）2in：结点无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。3）2i+1n：结点无右孩子（结点I为叶子结点）；否则其右孩子是结点2i+1。,二叉树,二叉树的顺序存储结构把二叉树的所有结点，按照一定的次序顺序存放到一组地址连续的存储单元中。对完全二叉树中所有结点进行编号得到一个结点的线性序列，然后将完全二叉树各结点按其编号顺序存放到一个一维数组中，即将完全二叉树上编号为 i 的结点存入一维数组下标为 i 的分量中。对于编号为 i 的结点，若有左孩子，它的左孩子的编号为 2i；若有右孩子，它的右孩子的编号
22、为 2i+1。,二叉树,二叉树的顺序存储结构,二叉树,二叉树的顺序存储结构普通二叉树的顺序存储方法,二叉树,二叉树的链接存储结构,二叉树,二叉树的遍历按一定的次序“访问”二叉树的所有结点，使得每个结点仅被“访问”一次。实际上就是把二叉树的所有结点放入一个线性序列的过程。需要寻找一种规律来系统地访问二叉树的各个结点。三种方式：DLR，LDR，LRD,根,二叉树,二叉树的遍历,其第一个元素值为二叉树中根结点的数据值。,以根结点的数据值为界，将中序遍历序列分为两部分。,其最后一个元素值为二叉树中根结点的数据值。,算法见教材p73,二叉树,二叉树的遍历例有二叉树中序序列为：ABCEFGHD，后序序列为
23、：ABFHGEDC，画出此二叉树。,二叉树,二叉树的遍历【例】假设先序遍历某二叉树的结点次序为ABCDEFGHIJ，中序遍历该二叉树的结点次序为CBEDAGHFJI，试画出此二叉树。,求二叉树的高度运算算法,求二叉树的高度的递归模型如下： 0 若bt = NULL Max f (bt-lchild) , f ( bt-rchild ) + 1,f( bt ) =,求二叉树的高度运算算法,Int BTHeight ( bitree *bt ) int lchilddep, rchilddep; if ( bt = = NULL) return ( 0 ); else lchilddep = BT
24、Height ( bt -lchild ); rchilddep = BTHeight ( bt-rchild ); return(lchilddeprchilddep)?(lchilddep+1):(rchilddep +1 ); ,求二叉树结点个数运算算法,对应的递归模型如下： 0 若bt = NULL f ( bt -lchild ) + f ( bt-rchild ) +1,f( bt ) =,求二叉树结点个数运算算法,Int NodeCount ( bitree *bt ) int num1, num2; if ( bt = = NULL) return 0; Else num1 =
25、 NodeCount ( bt -lchild ); num2 = NodeCount ( bt -rchild ); return ( num1 + num2 +1 ); ,求二叉树叶子结点个数运算算法,对应的递归模型如下： 0 bt = NULL 1 bt为叶子结点 F ( bt -lchild ) + f ( bt -rchild ) 其他情况,F (bt) =,求二叉树叶子结点个数运算算法,Int LeafCount ( bitree *bt ) int num1, num2; if ( bt = = NULL ) return 0; else if ( bt -lchild = =
26、NULL ,树的存储结构,孩子兄弟链表存储结构,Fchild data nsibling,第一个孩子,下一个兄弟,树的存储结构,树的遍历两种方式先根遍历后根遍历,树、二叉树、森林的转换,树、二叉树、森林的转换,图,定义一个图G是由两个集合V(G)和E(G)组成的，图的二元组可定义为：G=(V, E) V(G)是顶点的有穷非空集合，每个顶点都可以标上不同的字符或数字。 E(G)是V中顶点边的有穷集合，而边是V中顶点的偶对。在特殊情况下，E(G)可以是空集。,图的定义,V(G1) = V1, V2, V3, V4 E(G1) = (V1, V2)，(V1, V3)，(V1, V4)， (V2, V3)，(V2, V4)，(V3, V4),V(G3)=V1, V2, V3 E(G3)=， ,图,基本术语 边、链接点、弧、权、网完全图子图度路径和简单路径回路连通图和强连通图,图的基本术语,顶点的度、入度和出度无向图中，与顶点v相邻接的边数称为该顶点的度。有向图中，以顶点v为终点的弧的数目称为顶点v的入度；以顶点v为起点的弧的数目称为顶点v的出度；有向图顶点v的度为该顶点的入度和出度之和。,
