《软件技术基础课件3——数据结构与算法2剖析》由会员分享，可在线阅读，更多相关《软件技术基础课件3——数据结构与算法2剖析（49页珍藏版）》请在金锄头文库上搜索。
1、Shanghai Jiao Tong University 1 第二部分 数据结构与算法 线性表数据结构 p线性表堆栈（Stack）：一种特殊的线性表，其插入与删除运 算都只在线性表的一端进行 一端封闭，不允许进行插入与删除元素（栈底） 另一端开口，允许插入与删除元素（栈顶） 顺序存储结构下，插入与删除运算不需要移动表中其他数据元素 栈底元素总是最后被插入，最先能被删除 栈顶元素最先被插入，最后才能被删除素 p堆栈的操作原则： “先进后出”（first in last out，FILO） “后进先出”（last in first out，LIFO） p堆栈应用场合：需要先进后出的情形 手电筒装
2、电池、子弹装入弹夹 二叉树遍历时的临时量存储 Shanghai Jiao Tong University 2 第二部分 数据结构与算法 线性表数据结构 p堆栈的顺序存储 一维数组S（lm）作入栈退栈作为栈的顺序存储空间，其中m为栈的 最大容量 Shanghai Jiao Tong University 3 第二部分 数据结构与算法 线性表数据结构 p堆栈的基本运算 入栈：在栈顶位置插入一个新元素 将栈顶指针进1（即top+1） 将新元素插入到栈顶指针指向的位置 注：当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能再进行入 栈操作（上溢出） 退栈：取出栈顶元素并赋给一个指定的变量
3、 将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量 将栈顶指针退1（即 top1） 注：当栈顶指针为0时，说明栈空，不可能进行退栈操作（下溢出） 读栈顶元素：将栈顶元素赋给一个指定的变量 不改变栈顶指针 若栈顶指针为空，则说明堆栈已空 Shanghai Jiao Tong University 4 第二部分 数据结构与算法 线性表数据结构 p堆栈的基本运算 3种基本运算：入栈、退栈与读栈顶元素容量 Shanghai Jiao Tong University 5 第二部分 数据结构与算法 线性表数据结构 p线性表队列（Queue）：允许在一端进行插入、而在另一端 进行删除的线性表 允许插入的一
4、端称为队尾，用一个称为尾指针（rear）的指向队尾元 素，即尾指针总是指向最后被插入的元素； 允许删除的一端称为队头 p队列的操作原则： “先进先出”（first in first out，FIFO） p队列应用场合：需要先进先出的情形 机床的指令队列 计算机操作系统的程序排队 Shanghai Jiao Tong University 6 第二部分 数据结构与算法 线性表数据结构 p队列的存储常用一维数组作为队列的顺序存储空间表 预先分配一段连续的存储空间 入队操作进改变尾指针位置 退队操作仅改变头指针位置 p队列的运算 向队列的队尾插入一个元素入队运算 从队列的排头删除一个元素退队运算 S
5、hanghai Jiao Tong University 7 第二部分 数据结构与算法 线性表数据结构 p循环队列循环队列，就是将队列存 储空间的最后一个位置绕到第一个位置 ，队列循环使用 普通队列存在的问题 若队尾元素已占据存储空间的最底部，则无 法进行入队操作 循环队列中，当存储空间最底位置被占 用时，只要存储空间最顶位置空闲，便 可将元素加入到第一个位置，即将存储 空间最顶位置为队尾 用队尾指针rear指向队列中的队尾元素 ，用排头指针front指向排头元素的前一 个位置，因此从排头指针front指向的后 一个位置直到队尾指针rear指向的位置 之间所有的元素均为队列中的元素 Shang
6、hai Jiao Tong University 8 第二部分 数据结构与算法 线性表数据结构 p循环队列的运算 入队运算 退队运算 判断循环队列是否为空： rear=(front+1)%m； rear=front；但空队列和满队列时均出现 首尾指针指向同一位置！ #define QueSize 100 Typedef char DataType; Typedef Struct int front; int rear; int count; DataType dataQueSize; cirque; Shanghai Jiao Tong University 9 第二部分 数据结构与算法 线性
7、表数据结构 p循环队列的运算 置空： void EmptyQue (cirque *q) q-front=q-rear=0; q-count=0; 判断队列是否空： int IfQueEmpty (cirque *q) if q-coount=0 return 1; else return 0; Shanghai Jiao Tong University 10 第二部分 数据结构与算法 线性表数据结构 p循环队列的运算 判断队列是否为满： int IfQueFull (cirque *q) if q-coount= QueSize return 1; else return 0; 入队操作：
8、void EnterQue (cirque *q, DataType x ) if(IfQueFull (q) error(“overflow!”); q-count+; q-dataq-rear=x; q-rear=(q-rear+1)% QueSize ; Shanghai Jiao Tong University 11 第二部分 数据结构与算法 线性表数据结构 p循环队列的运算 出队操作： DataType DepartQue (cirque *q) DataType temp; If QueEmpty(q) error(“underflow!”); temp=q-dataq-front
9、; q-count-; q-rear=(q-rear+1)% QueSize ; return temp; Shanghai Jiao Tong University 12 第二部分 数据结构与算法 串结构 p概念：由 0 个或多个字符组成的有限序列 通常记为：s =“ a1 a2 a3 ai an ” ( n0 ) 必须有“”，引号不是串的内容，但必须存在，以此 避免与变量名或数的常量混淆 S串名 a1 a2 a3 ai an串值 x 的值为整数 6027。 x 的值为字符串 6027。 例：x = “6027” x = 6027 test =“test” Shanghai Jiao Ton
10、g University 13 第二部分 数据结构与算法 串结构 p空串：不含任何字符的串，串长度 = 0，用符号 表示。 p空格串：一个或多个空格组成的串 p子串：由串中任意个连续的字符组成的子序列 p主串：包含子串的串 p位置：字符在序列中的序号 子串在主串中的位置是子串的首字符在主串中的位置 p串相等：长度相等且各个对应位置的字符都相等 p举例： S=“Link16” S1=“n”、S2=“NA”、S=“Link16” 子串。 S4=“Lk6” 非子串（非串 S 中的连续字符所组成）。 在 S 中的位置：3 在 S 中的位置：1 串是任意串的子串，任意串是其自身的子串。 Shanghai
11、 Jiao Tong University 第二部分 数据结构与算法 串结构 p串的逻辑结构：与线性表相似 ，区别是串的数据对象约定是字 符集 p串的基本操作：与线性表不同，其复杂程度高于线性表 在线性表的基本操作中，大多以“单个元素”作为操作对象 在串的基本操作中，通常以“串的整体”作为 操作对象 例如： 在串中查找某个子串、求 取一个子串、在串的某个位置上 插入一个子 串以及删除一个子串等 五种最操 作：串赋值 StrAssign、串比较 StrCompare、求串 长 StrLength、串联接 Concat、求子串 SubString Shanghai Jiao Tong Univer
12、sity 第二部分 数据结构与算法 串结构 p串的表达：存储结构与线性表的存储结构 类似，但组成串的结 点是单个字符 p串的两种表示方法： 隐式表达：在串之后加入一个串的结束标志。如 C 中使用 “0”，“0” 不计入串长 显式表达：首地址显式地记录串的长度 T h i s i s a d o g . 0 14 T h i s i s a d o g . Shanghai Jiao Tong University 第二部分 数据结构与算法 串结构 p串的存储： 定长顺序存储：也称为静态存储分配的顺序串。用一 组地址连续地址连续的存储单元来依次存放依次存放串中的字符序列 若串的实际长度超过定长，
13、则被“截断” 堆分配存储：仍以一组空间足够大的、地址连续的存储单元 依次存放串值字符序列，但它们的存储空间是在程序执行过 程中动态分配动态分配 如：C 语言中提供的串类型即为这种存储方式。动态分配函数 malloc ( ) 分配一块实际串长所需要的存储空间 “堆”），如果 分配成功，则返回此空间的起始地址，作为串的基址。由 free( ) 函数释放串不再需要的空间 Shanghai Jiao Tong University 第二部分 数据结构与算法 串结构 p串的存储： 链串存储结构：单链表存放字符串，简称为链串链串。链串链串与单 链表的差异只是它的结点数据域为单个字符结点数据域为单个字符 便
14、于串的插入和删除操作，但是空间利用率不高 块链存储结构：为了提高空间的利用率，可以使每个结点存 放多个字符（顺序串顺序串和链串链串的折衷） S ABCDE S ABCDE S A B CD E # Shanghai Jiao Tong University 18 第二部分 数据结构与算法 树型结构（非线性结构） 结点之间有分支 具有层次关系 例 自然界：树 人类社会 家谱 军队组织结构 计算机领域 编译：用树表示源程序的语法结构 数据库系统：用树组织信息 算法分析：用树描述执行过程 行政组织机构 集团军 步2师步1师 炮兵旅 装甲师 3团 1团 雷达营 1营3营 侦察连 防空旅 2团 炮团 2
15、营 炮连 Shanghai Jiao Tong University 19 第二部分 数据结构与算法 树结构 p定义（递归定义）： 树 (Tree) 是 n (n0) 个结点的有限集。若 n = 0，称 为空树；若 n 0，则它满足如下两个条件： (1) 有且仅有一个特定的称为根根 (Root) 的结点； (2) 其余结点可分为 m (m0) 个互不相交的有限集 T1, T2, T3, , Tm，其中每一个集合本身又是一棵树，并称 为根的子树 (SubTree)。 Shanghai Jiao Tong University 第二部分 数据结构与算法 树结构 p术语： T3 T2 T1 结点的度度：结点拥有的子树数。 度 = 0 叶子叶子 终端结点终端结点 度 0 分支结点分支结点 非终端非终端 结点结点 根结点以 外的分支 结点称为 内部结点内部结点 树的度度：树内各结点的度的最大值。 双亲 孩子 兄弟 第 1 层 第 2 层 第 3 层 第 4 层 结点：结点：数据元素+ 指向子树的分支 根结点：根结点：非空树中无前驱结点的结点 E F G H I A B C D J K L M 堂兄
