数据结构-栈及其应用

《数据结构-栈及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-栈对于程序设计来说：编程语言是工具；数据结构是基础；算法设计是方法。程序=数据结构+算法数据结构数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的内涵“操作”的对象：数据。数据与数据间的关系。针对数据的基本操作。数据结构的形式定义data_structure=(D,S)D:数据元素的有限集；S:Ｄ上关系的有限集；数据结构相关概念数据(data)计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符、图像、声音都属于数据的范畴。数据元素(dataelement)是数据的

2、基本单位，在程序中作为一个整体进行考虑。有时一个数据元素有若干数据项。数据对象(dataobject)是性质相同的数据元素的集合，是数据的一个子集。逻辑结构图例数据元素间的关系结构名特性数据元素属于或不属于集合集合结构松散；用其他结构代替数据元素一个对一个线性结构结构简单数据元素一个对多个树形结构结构复杂数据元素多个对多个图结构结构复杂前述“关系”即结构(sructure)，指数据之间的逻辑关系，又称逻辑结构。物理结构1顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中相邻。2链式结构：借

3、助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中不一定相邻。用高级语言中的数据类型(数组、动态变量)来描述逻辑结构、物理结构密切相关算法的设计取决于所选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。线性结构线性表、栈、队列、串、数组、广义表非线性结构树、图由n个数据元素的有限序列除头元素外，每个元素都有一个前趋除尾元素外，每个元素都有一个后继线性结构线性表线性表是最常用且最简单的一种数据结构，它是由有限个数据元素组成的有序集合。每个数据元素有一个数据项或者含多个数据项。线性表的

4、两种存储方式1、顺序存储结构顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）十位移来访问每一个元素。2、链式存储结构在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后件的数组下标或地址。最后一个结点的指针域的值为0或nil。数组的插入与删除1234567891011126.5数组的插入与删除均需要移动后面的元素插入：删除：123456789

5、101112123456789101112123456789101112链表的插入与删除无需移动任何元素线性表的具体实现顺序存储结构用数组类型：list:array[1..maxlen]ofelemtp;链式存储结构用指针类型和动态变量：pointer=nodetype^;nodetype=recorddata:elemtp;next:pointer;end;顺序存储与链式存储操作的对比顺序存储链式存储特点逻辑相邻的元素其物理位置也相邻逻辑相邻的元素其物理位置不一定相邻特点优点随机存取i元素o(1)查找X和第i元素需遍历整个链表o(n)缺点缺

6、点插入、删除需移动大量元素o(n)插入、删除不需移动大量元素o(1)优点缺点预先分配大空间不需预先分配空间优点缺点表容量难以扩充表容量扩充灵活优点优点操作简单操作较复杂缺点限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(lastinfirstout)线性表(LIFO结构)栈顶——表尾栈底——表头栈通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（如下图）。栈的实现（一）Constm=栈表目数的上限；Typestack=array[1..m]ofstype；{栈类型}Vars：stac

7、k；{栈}top：integer；{栈顶指针}栈sm1top栈的实现（二）constm=栈表目数的上限；typestack=recordelem:array[1..m]ofelemtp;top:0..m;{栈顶指针}end;Vars：stack；{栈}TOP=0表示栈空Top=m表示栈满栈的基本操作栈的基本操作包括四种初始化（init）、进栈（push）、出栈（pop）、读取栈顶元素（top）。1）过程init(s,t)—初始化procedureinit;begint:=0;end;2)、过程push(x)—往栈s中压入一个值为x的数据：pr

8、ocedurepush(vars：stack；x：stype；vart：integer)；beginift=mthenwriteln(‘overflow’){上溢}