《常用数据结构及其存储.ppt》由会员分享，可在线阅读，更多相关《常用数据结构及其存储.ppt（27页珍藏版）》请在三一办公上搜索。
1、第21讲常用数据结构及其存储,大学计算机基础 第三部分 计算机专业理论介绍,主要内容,21.1 算法21.2 数据结构的基本概念21.3 线性表21.4 栈与队列21.5 树与二叉树,21.1 算法,定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题的方法和步骤。特征：有穷性 确定性 有效性 零个或多个输入 一个或多个输出,例如：一元二次方程求根算法。,算法复杂度,评价一个算法优劣的主要标准是：算法的执行效率与存储需求 算法的效率：指的是时间复杂度（Time Complexity）存储需求：指的是空间复杂度（Space Complexity）一般情况下，算法中的基本操作重复操作执行的
2、次数是问题规模n的某个函数f(n)，算法的时间复杂度记做：T(n)=O(f(n),21.2 数据结构的基本概念,数据与数据结构 数据:是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。数据元素:是数据的基本元素，即数据集合中的个体。数据项:具有独立意义的最小数据单位。数据对象:具有相同特性的数据元素的集合，是数据的子集。数据结构:互相之间存在着一种或多种关系的数据元素的集合。,数据的逻辑结构,集合 线性结构 树形结构 图状或网状结构,数据的存储结构,一、顺序存储结构主要特点：所有元素所占的存储空间是连续的；各个元素在存储空间中是按逻辑顺序依次存放的；元素可随机
3、存取，但插入、删除运算不便，会引起大量结点的移动。,二、链式存储结构,主要特点：存储数据结构的存储空间可以不连续；各结点的存储顺序与元素之间的逻辑关系可以不一致，元素之间的逻辑关系由指针域来确定；插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。,数据的运算,检索：在数据结构里查找满足一定条件的结点 插入：往数据结构里增加新的结点 删除：把指定的结点从数据结构里去掉 更新：修改指定结点的一个或多个域的值 排序：保持线性结构的结点序列里结点数不变，将结点按某种指定的顺序重新排列,21.3 线性表,线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列。（a1，a2
4、，an）顺序表：指用顺序存储结构存储的线性表。链表：用链式存储结构存储的线性表。栈和队列：是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表。,顺序表,各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表。若顺序表中结点个数为n，则：插入一个结点平均需要移动之结点个数为 n/2，算法的时间复杂度是O(n)；删除一个结点平均需移动结点个数为（n-1）/2，算法的时间复杂度是O(n)。,链表,线性链表（单链表）：删除算法的时间复杂度为O(n)，其主要执行时间是搜索删除位置。循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）。
5、,21.4 栈和队列,栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。表中无元素即空栈。栈中有元素a1,a2,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则;栈的物理存储可以用顺序存储结构或链式存储结构;栈的运算还有取栈顶元素，检查栈是否为空，清除等。,栈的插入和删除,TOP,TOP,TOP,TOP,TOP,TOP,进栈,出栈,栈底,栈结构,(3),(1),(2),(5),(4),(6),栈顶,队列,队列：是限定所有的插入都在表的一端进行，所有的
6、删除都在表的另一端进行的线性表。进行删除的一端叫队头，进行插入的一端叫队尾，如下页图所示。在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则。队列的物理存储可以用：顺序存储结构，也可用链式存储结构。,队列的示意图,出队列 a1 a2 a3 an 入队列 队头 队尾,队列的插入和删除示例,21.5 树与二叉树,树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构。树（Tree）:是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1
7、，T2，Tm，每个子集又是一棵树，称作这个根的子树（subtree）。,树形结构的常用术语,结点的度（Degree）：一个结点的子树的个数。树的度：树中各结点的度的最大值。树叶（Leaf）：度为0的结点。分支结点：度不为0的结点。双亲（Parent）、子女（Child）：结点的各子树的根称作该结点的子女；相应的该结点称作其子女的双亲。兄弟（Sibling）：具有相同双亲的结点互为兄弟。结点的层数（Level）；树的深度（Depth）森林（Forest）,二 叉 树,二叉树（Binary Tree）:是n（n0)个结点的有限集合，这个集合或者为空集（n=0），或者由一个根结点及两棵不相交的、分别
8、称作这个根的左子树和右子树的二叉树组成。二叉树是树的特殊情形。二者的区别是：二叉树为有序树。,二叉树的性质：1、在二叉树的i层上，最多有2i-1个结点（i1）2、深度为k的二叉树最多有2k-1个结点(k1)3、对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。4、具有n个结点的完全二叉树的深度为log2n+1。其中，log2n是不大于log2n的最大整数。,满二叉树和完全二叉树,一棵深度为k且具有2k-1个结点的二叉树称为满二叉树（Full Binary Tree）。深度为k，有n个结点的二叉树，当且仅当其妹一个结点都与深度为k的满二叉树中编号从1到n的
9、结点一一对应时，称为完全二叉树。,二叉树的存储,二叉树的存储通常采用：链接方式。每个结点除存储结点自身的信息外再设置两个指针域Ichild和rchild，分别指向结点的左子女和右子女，当结点的某个指针为空时，则相应的指针值为空（NIL或）。结点的形式为：,二叉树的遍历,遍历一个树形结构是指：按一定次序系统的访问该结构中的所有结点，使每个结点恰好被访问一次。前序遍历法（NLR次序）访问根，按前序遍历左子树，按前序遍历右子树。后序遍历法（LRN次序）按后序遍历左子树，按后序遍历右子树，访问根。中序遍历法（LNR次序）按中序遍历左子树，访问根，按中序遍历右子树。,例如：如图二叉树。,前序遍历序列：ABDGCEHF中序遍历序列：BGDAEHCF后序遍历序列：GDBHEFCA,本讲结束,
