数据结构-栈及其应用
48页1、数据结构-栈,对于程序设计来说: 编程语言是工具; 数据结构是基础; 算法设计是方法。,程序=数据结构+算法,数据结构,数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构的内涵 “操作”的对象:数据。 数据与数据间的关系。 针对数据的基本操作。,数据结构的形式定义 data _ structure=(D,S) D:数据元素的有限集; S:上关系的有限集;,数据结构相关概念,数据(data) 计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符、图像、声音都属于数据的范畴。 数据元素(data element) 是数据的基本单位 ,在程序中作为一个整体进行考虑。 有时一个数据元素有若干数据项。 数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。,逻辑结构,前述“关系”即结构(sructure),指数据之间的逻辑关系,又称逻辑结构。,物理结构,1 顺序结构:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 逻辑上关联的数据元素,物理存储结构中相邻。 2 链式结构 :借助元素存储地址
2、的指针(pointer)表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素,物理存储结构中不一定相邻。 用高级语言中的数据类型(数组、动态变量)来描述 逻辑结构、物理结构密切相关 算法的设计取决于所选定的数据(逻辑)结构,而算法的实现依赖于所采用的存储结构。,由n个数据元素的有限序列 除头元素外,每个元素都有一个前趋 除尾元素外,每个元素都有一个后继,线性结构,线性表,线性表是最常用且最简单的一种数据结构,它是由有限个数据元素组成的有序集合。 每个数据元素有一个数据项或者含多个数据项。,线性表的两种存储方式,1、顺序存储结构 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素,通常用数组实现。数组的物理实现是一块连续的存储空间,它是按首址(表中第1个元素的地址)十位移来访问每一个元素。,2、链式存储结构 在链式存储结构的线性表中,逻辑上相邻的两元素,其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型,数据域存储结点的值,指针域存储后件的数组下标或地址。最后一个结点的指针域的值为0或nil。,数组的插入与删除,6,6.5,数组的插入与删除均需要移动后
3、面的元素,插入:,删除:,6,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,链表的插入与删除,无需移动任何元素,线性表的具体实现,顺序存储结构 用数组类型: list: array 1maxlen of elemtp; 链式存储结构 用指针类型 和 动态变量: pointer = nodetype ; nodetype = record data : elemtp ; next : pointer ; end;,顺序存储与链式存储操作的对比,限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out )线性表 (LIFO结构) 栈顶表尾 栈底表头,栈,通常栈可以用顺序的方式存储(数组),分配一块连续的存储区域存放栈中的表目,并用一个变量t指向当前栈顶(如下图)。,栈的实现(一),Const m=栈表目数的上限; Type stack=array1m of stype; 栈类型 Var s:stack;栈 top: integer; 栈顶指针,栈s,m,1,top,栈的实现(二),const m
4、=栈表目数的上限; type stack=record elem: array1m of elemtp; top:0m; 栈顶指针 end; Var s:stack;栈,TOP=0 表示栈空 Top=m 表示栈满,栈的基本操作,栈的基本操作包括四种 初始化(init)、 进栈(push)、 出栈(pop)、 读取栈顶元素(top)。,1) 过程init(s,t) 初始化 procedure init; begin t:=0; end; 2)、过程push(x)往栈s中压入一个值为x的数据: procedure push (var s:stack; x:stype; var t:integer); begin if t=m then writeln(overflow) 上溢 else begin tt+1;stx;end;else x入栈 end;Push,3)函数pop(s,t)从栈中弹出一个表目 function pop (var s:stack; var t:integer):stype; begin if t=0 then writeln (underflow) 下溢 else
《数据结构-栈及其应用》由会员san****019分享,可在线阅读,更多相关《数据结构-栈及其应用》请在金锄头文库上搜索。
高中化学实验方案的设计第一节制备实验方案设计
高中生物实验室配置
高中体育与健康课程田径必修模块单元教学方案
高中通用技术方案的构思方法-设计分析教案苏教版必修
高中生物室配置
高中信息技术网络技术应用选修模块教学评价方案
骆小学教师戏曲知识培训方案(I)
麻村小学阳光体育活动计划及实施方案
高桥小学幼小衔接活动方案
马摆小学控辍保学实施方案
金阳街道中心小学未成年人思想道德建设实施方案
龙扬小学第32个爱国卫生月活动方案
魏家井联小学度控辍保学工作方案
高区第九届初中骨干教师课堂教学能力展示活动
长沙县2018年度小学生课外阅读知识竞赛及书目
阳江中心小学一月一事之五月主题活动方案
长营小学校园体育活动实施方案
高考历史备考方案-陈军
高考语文第5课父亲课前预案苏教版选修现代散文选读
高考语文第9课铃兰花课前预案苏教版选修现代散文选读
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页