2011年度工作目标完成情况申报及自我

第4章 模型化 PART B,可视化计算,使用RAPTOR实现抽象数据类型,无论是进行科学计算或数据处理、过程控制等，都是对数据进行加工处理的过程 必须研究数据的特性及数据间的相互关系及其对应的存储表示 利用这些特性和关系设计出结构好、效率高的程序或算法,如何进行数据抽象?,数据结构是数据存在的形式 它用来反映一个数据的内部构成，即一个数据由哪些成分的数据构成，以什么方式构成，呈现什么结构 数据（Data）是信息的载体 能够被计算机识别、存储和加工处理 数据元素（Data Element）数据基本单位 在计算机程序中作为一个整体考虑和处理,如何进行数据抽象?,数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合 四类基本的数据结构： 集合结构 线性结构 树型结构 图形结构,如何进行数据抽象?,一个数据结构必须包含有数据元素的集合和数据关系的集合这两个基本要素 数据结构包括数据的逻辑结构和数据的物理结构,数据的逻辑结构,可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关 研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构,数据的物理结构,指数据结构在计算机中的表示方式，也称存储结构或映像 它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素和元素间关系的表示 例如：顺序存储方法是把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，可以借助于程序设计语言中的数组来实现,抽象数据类型,抽象数据类型(Abstract Data Type， ADT)是指一个与某种类型的数据结构行为模式有关的数学模型以及定义在此模型上的一组运算 而所有的运算必需在该类型的数据结构的数学限制条件下才是有效的,抽象数据类型举例,一个数据堆栈（Stack），可以定义三种运算： 压栈(push)：将一些数据插入该结构； 弹出(pop)：从结构中取出并清除数据（按照后入先出的顺序）； 检查（peek），检查结构顶端的数据而不做清除,抽象数据类型的实现,一般抽象数据类型需要通过某个系统子已有的数据类型来间接定义与实现 对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即子图、子程序或函数名，并且规定这些运算的参数性质,抽象数据类型的RAPTOR实现,在RAPTOR中实现所定义的抽象数据类型数据部分用一种已知的数据类型（如一维、二维数组，字符串等）来实现 抽象数据类型操作部分中的每个操作用RAPTOR子图或子程序来实现 这样能够同其他计算机程序语言实现算法具有一定的可比性,线性表的基本概念,数据结构分线性结构和非线性结构 线性结构包括线性表、栈、队列、数组和字符串 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前趋 除最后一个外，集合中的每个数据元素均只有一个后继,线性表的逻辑结构,一个线性表是n个数据元素的有限序列 特征： 元素个数n表长度，n=0：空表 1in时 ai的直接前趋是ai-1，a1无直接前趋 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,例 英文字母表（A,B,C,Z)是一个线性表,顺序表,用一组地址连续的存储单元存放一个线性表叫顺序表 特点： 表中的数据元素逻辑上相邻 实现随机存取 实现：可用RAPTOR的一维数组实现,也是构成本课程其他数据结构的基础,顺序存储结构的优缺点,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 应用:顺序表的主要应用 参见第5章 排序与查找,堆栈,堆栈是一种特殊的线性表，基本的工作方式是，后入先出（Last In First Out, LIFO） LIFO: 最后放入堆栈的数据最先被取走 常用的堆栈运算： 压栈（Push）,将新的元素放入堆栈 弹栈(Pop)，从堆栈顶端取走元素 堆栈可以使用数组或链表实现 应用：计算器、编译器、程序设计、数制转换,逆波兰表达式,某些计算器使用逆波兰表达式（ Reverse Polish Notation ）进行工作 1920年由J. Lukasiewicz发明 完成数学公式的计算，可以不用括号 例如： （3+4）*5，成为RPN以后： 3 4 + 5 *,RPN流程图与测试,RAPTOR的栈操作设计,初始化栈,压栈操作,弹栈操作,队列,队列是一种特殊线性表，基本的工作方式是，先入先出（First In First Out, FIFO） FIFO: 最先放入队列的数据最先被取走 常用的队列运算： 入队（ Enqueue ）,将新的元素放入堆栈 出队(Dequeue)，从堆栈顶端取走元素 队列可以使用数组或链表实现 应用：打印机、仿真、网络(路由器),Joseph's problem,一组n个候选者, 排列成环状，所有第m个人都会被淘汰，只有一位幸运者被选上 将队列Q中，所有人按1到n编号 当队列不空，做以下动作: a. 做以下m-1次 i. x=Dequeue Q ii. Enqueue Q(x) b. x=Dequeue Q 输出X作为最后的幸运者,Joseph's problem,请跟踪第1步和2b的执行，在6取3的情况下： 约瑟夫环上的哪个位子是幸运位？,RAPTOR的队列操作设计,入队操作,初始化队列,出队操作,非线性数据结构-树,树(Tree) 是一种重要的非线性数据结构。 不含有任何节点（元素）的树被称为空树 在一棵非空树中，它有且仅有一个称作根(root)的节点，其余的节点可分为m棵(m0)互不相交的子树(即称作根的子树) 每棵子树(Sub Tree)又同样是一棵树 显然，树的定义是递归的,树的结构与分解,树的基本术语,节点的度和树的度 树中所有节点的度的最大值被定义为该树的度 分支节点和叶子节点 在一棵树中，度等于0的节点称作叶子或终端节点，度大于0的节点称作分支节点或非终端节点 子节点、父节点和兄弟节点 节点的层数和树的深度(高度),树的基本术语,有序树和无序树 一棵反映父子关系的家族树，兄弟节点之间是按照排行大小有序的，所以它是一棵有序树 森林,森林是m(m0)棵互不相交的树的集合,树的性质,性质1: 树中的节点数等于所有节点的度数加1。 性质2: 度为k的树中第i层上至多有ki-1个节点（i1） 性质3深度为h的k叉树最多有 个节点 性质4具有n个节点的k叉树的最小深度为： logk(n(k-1)+1),树的存储,父子链表,使用文件描述树的基本数据,对树T的基本描述,保存在data.csv文件中，每一行保存一个节点的父节点，第一行保存的是根节点，所以其父节点为0 将树的描述保存在文件中，可以方便校验，减少屏幕交互,建立父子链表的main子图,建立父子链表的data_input_from_file子图,建立父子链表的 findchild子图,使用RAPTOR实现树的存储,parents，数组下标表示各个节点，数组元素保存各个节点的父节点,实际内容从文件得到,这是推断其他数据的基础； child数组是一个字符串数组，元素下标表示各个节点，数组元素使用字符串保存各个节点的子节点 Nodestr保存了所有节点的“数据”,树的运算,树的主要运算包括进行树的遍历、求树的深度、输出树等 常用的树的遍历包括前序遍历（或称深度优先遍历）和按层遍历（或称广度优先遍历）两种 前序遍历T：得到的节点序列为： A B D E G H I C F,小结与回顾,本章的内容围绕模型开始，主要内容可以划分为两个主要部分，使用有限状态机和图灵机对客观物体建立状态模型；使用数组表述抽象数据结构模型 由于软件功能和书的篇幅限制，本书中设计的大部分抽象数据结构都不可能按照经典文献的要求进行完整、规范的定义和描述。所以在实现上进行模拟，尽可能做到“神似”而不是“形似”。,