数据结构(C语言描述).ppt

数据结构辅导，西安电子科技大学，李青山http:/202 . 117 . 118 . 45/教职工/李清山石 029-8820-4611，课程内容框架，数据结构，基本数据结构，应用程序数据结构，堆栈，队列，线性表，线性结构，非线性结构，字符串，查找，内部排序，外部排序，文件，动态存储管理存储，数组，广义表，树，二叉树，图形，基本概念，1.2基本概念和术语，数据，数据元素，数据数据对象结构*集合：松散关系*线性结构：一对一关系*树结构：一对多关系*网络结构：多对多关系数据结构数据结构=(D，s)，数据结构的分类，1.2基本概念和术语(续)，逻辑结构：数据元素之间的逻辑关系(原始关系)存储结构：计算机中数据结构的图像。 包括数据元素的表示和关系的表示。分类：*顺序存储结构*链式存储结构描述模式：用高级语言“数据类型”、算法、1.3算法和算法分析来描述。内涵：是对特定问题解决步骤的描述，并且是指令的有限序列，其中每个指令代表一个或多个操作。属性：*差：差的步骤、差的时间/每一步*确定性：指令的语义模糊性*可行性：算法可以通过基本操作完成*输入：零个或多个输入*输出：一个或多个输出、算法设计要求、1.3算法和算法分析(续)。正确性、可读取性、鲁棒性、高时间效率和低存储要求、算法时间效率的测量、1.3算法和算法分析(续)、算法时间效率测量的基本方法在该算法中，选择作为所研究问题的基本操作的原始操作，并且重复执行该基本操作的次数作为该算法的时间测量。一般来说，这个基本操作是最深循环语句中的原始操作。算法的时间复杂度T(n)=O(f(n)称为算法的渐近时间复杂度，简称为时间复杂度。算法存储空间的测量，1.3算法和算法分析(续)。算法存储空间测量的基本方法使用程序执行所需的辅助空间的消耗作为存储空间测量的基础，并且是问题规模n的函数。然而，程序本身所需的工作单位不能被计数。算法空间复杂度S(n)=O(f(n)称为算法空间复杂度。线性表3堆叠队列字符串线性数据结构的第一部分线性数据结构的特征2.1线性表的逻辑结构在非空的有限数据元素集中只有一个称为“第一”的数据元素。只有一个称为“最后”的数据元素；除了第一个，集合中的每个数据元素只有一个前置任务。除了最后一个，集合中的每个数据元素只有一个后继元素。基本概念和术语2.1线性表的逻辑结构(续)线性表：n个数据元素的有限序列(线性表中数据元素的具体含义在不同环境下可能不同，但同一线性表中的元素属性必须相同)。表格长度：线性表格中元素的数量n(n=0)。空表：当n=0时的线性表称为空表。位序：非空表中的数据元素ai是该表的第I个元素，那么我在线性表中称为ai位序。，线性表的抽象数据类型定义，2.1线性表的逻辑结构(续)，表数据对象：D=ai|ai属于elemset，I=1，2，n，n=0数据关系：R1=|ai-1，ai属于d，I=2，3，n，基本操作：InitList(p-next=s，对单链表执行删除操作，2.3线性表的链存储结构(续)，(a1，大赦国际，大赦国际1，表长度n，(a1，人工智能-1，人工智能1，表长度n-1，自由(Q)，下一个=下一个，2。线性表3。堆栈，队列和字符串，教学内容-第3章，堆栈，队列和字符串是特殊的线性表。3.1堆栈、队列和字符串的逻辑结构。堆栈和队列是具有有限操作的线性表。堆栈和队列的“操作限制”是指操作位置有限的字符串的特殊性。线性表中的数据元素只能是以子字符串作为运算单位的字符串。队列和字符串具有一般线性表的共同特征。相反，特殊的线性表格有更广泛的应用领域。栈的基本概念和术语，3.1栈的逻辑结构，队列和字符串(续)，栈：只有在表的末尾有插入或删除操作的线性表是有限的。顶端：插入或删除的表格的末端。底部：头端。空堆栈：空表。堆栈操作特征：LastInFirstOut - LIFO，堆栈抽象数据类型定义，3.1堆栈，队列和字符串逻辑结构(续)，ADTStack数据对象：D=ai|ai属于elemset，I=1，2，n，n=0数据关系：R1=|ai-1，ai属于d，I=2，3，n/a1是堆栈底部，堆栈顶部，基本操作：InitStack(j=1；/字符后的位置。如果它不存在，而(它0)返回It0；elsereturn0/索引算法时间复杂度：T(n)=O(n*m)，逻辑函数是索引(s，T，pos) s= a1a2.人工智能.an t= t1t2.涡轮喷气发动机.通常，m0)每个不相交的有限集合t1，T2，其中每个集合本身就是一棵树，并被称为根的子树。树的节点：指向其子树的数据元素和分支。节点度：节点拥有的子树数。末端节点(或叶):0度节点。非终端节点(或分支节点，或内部节点):度不为0的节点。树的度：树中每个节点的度的最大值。子节点：节点子树的根。6.1树的逻辑结构(续)，树的性质和树的表示，树的性质：递归层次结构，树的表示：树集合的嵌套表示，广义表的嵌套表示，凹的表示，6.2树的存储结构(续)，子兄弟的表示(二进制链表)，树的/-二进制链表的存储表示(子-兄弟)-typedeftrucsnode elemtypeddata；/树节点数据字段结构csnode * firstchild，* nextsiblingCSNode，* CSTree6.3二叉树的逻辑结构，二叉树的描述性定义及其基本形式，二叉树：二叉树BT是一个有限的n个节点的集合。在非空的二叉树中：(1)只有一个被称为根的特定节点；(2)当n1出现时，剩余的节点可以分成两个不相交的有限集合BTL、BTR、BTL、BTR，它们分别是二叉树，BTL称为根的左子树；BTR被称为根的右子树。二叉树的基本形式：五种：空二叉树；只有根节点的二叉树；右子树是一个空的二叉树；左右子树不为空的二叉树；左边的子树是一个空的二叉树。，6.3二叉树的逻辑结构(续)，二叉树的数学性质，性质1:在二叉树的第一级上最多2i-1个节点(I=1)；属性2:深度为k的二叉树最多有2k1个节点(k=1)；性质3:二叉树，如果叶节点数为n0，2度节点数为n2，则n0=N2 1；性质1:证明当I=1时，显然有2I-1=20=1；假设所有j，1=jdata) if(按遍历顺序(t-rchild，访问)returnok其他错误；/当访问失败时出现错误 elsereturnOK/一个递归访问终止InOrderTraverse/算法时间复杂度：0(n)，6.5二叉树遍历和线程(续)，中间序列遍历算法，StatusinorderTraverse 1(位流，状态(*访问)(远程类型)/中间序列遍历二叉树的非递归算法T，调用函数VisitInitStack(S)用于每个数据元素；推动(S，T)；/根指针堆叠时(！stack mpty(s) while(gettop(s，p) in order daverse/算法时间复杂度：o (n)，statusionorder traverse 2(bit reet，status(* visit)(teletypee)/按顺序遍历二叉树t的非递归算法，为每个数据元素调用函数visinitstackp=T；同时(p|！堆栈(S)如果(p)推(S，p)；p=p-lchild。/根指针堆栈，遍历左子树，否则/根指针返回，访问根节点，遍历右子树弹出(S，p)；如果(！访问(p-数据)返回错误/访问错误p=p-r child)；/else /Where关闭； InorderTraverse/算法时间复杂度：o (n)，6.5二叉树的遍历和线程化(续)，二叉树遍历的典型应用，已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，该二叉树可以唯一确定。步骤1:确定根，其被邮政编码称为A；步骤2:确定由InOrder称为cbedgfh的左子树元素集，步骤：确定由InOrder称为jik的右子树元素集，并且步骤4:根据中间序列和下面的序列对左子树元素集和右子树元素集递归地执行步骤1-步骤3，直到元素集为空。6.5二叉树的遍历和线程(续)。线程二叉树的遍历本质是节点间非线性关系的线性化过程。遍历后元素之间的一些线性关系通常隐藏在遍历规则下。如何提高多次遍历同一棵树的效率？在二进制链表结构中增加一个线索字段，明确描述遍历后的线索关系以节省线索字段的空间，充分利用二进制链表中的n 1指针字段线索链表：二叉树的存储结构，节点结构的定义显示在前面。线索：指向节点的前驱和后继的指针称为线索。线索二叉树：有线索的二叉树。线程化：按照一定的顺序遍历二叉树，把它变成线程化二叉树的过程。遍历线程二叉树的过程是根据线程和遍历规则连续寻找当前节点的后继节点的过程。6.5二叉树的遍历和线程化(续)，线程化二叉树的中间顺序遍历，顺序：CBEDGFHAJIK，设置当前节点指针为P，其前体节点为Q，后续节点指针为S，有：查找节点P的后继节点：1。如果p-rtag=1，s=p-rchild。2.如果p-rtag=0是p的右子树的中间顺序遍历序列的第一个节点，即右子树的最左下节点，则找到节点p的前身：1。如果p-ltag=1，q=p-l child；2.如果p-rtag=0q是p的左子树的中间顺序遍历序列的第一个节点，即左子树的最低右节点，6.6树，森林和二叉树的转换，森林和树的递归定义，森林：m个不相交树的集合。树：树是二元组树=(根，F)，根是根，F是m(m0)树的森林，f=t1，T2，其中t1=(R1，f1)是根的第一个子树；当我！当=0时，根和它的子树林之间有以下关系：射频= | 1=1，2，m，m0，6.6树，森林和二叉树转换(续)，树和二叉树转换。目的：简化二叉树操作对树和森林的操作；基础：树和二叉树有相同的二进制链表存储结构；6.6树、森林和二叉树转换(续)、6.6树、