堆栈 队列 串（45）课件.ppt

《堆栈 队列 串（45）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第3章栈,队列,串主讲教师：肖晨回顾------第2章线性表2.1线性表的逻辑结构定义具有相同类型的数据元素的有限序列(n>=0)数学表示L=(a1,a2,…,an)元素间具有严格的先后次序:前驱后继唯一逻辑表示：a1a2a3a4an2顺序表2.2物理结构之----顺序存储结构逻辑描述用一段地址连续的存储单元依次存储数据元素实现1.C++中用数组存储顺序表intiArray[20]2.线性表中的元素类型不固定，所以需要使用模板机制32.2顺序表的实现—插入课件.lnk标号数据域0a1=101a2=122a3=253a4=84a5=165a6=20标号数据

2、域0a1=101a2=122a3=253a4=84a5=165a6=206a7=20a6=16a5=8a4=25a3=1717插入42.2顺序表的实现—插入插入(1开始计算的)第i个位置的实现步骤插入位置i以后的元素后移for(intj=length;j>=i;j--)data[j]=data[j-1];将元素插入data[i-1]=t;表长度增1length++;插入在第i个位置(1开始计算)，而C语言数组是从“0”开始的；考试和开发中i/+1/-1经常错data[i-1]是(1开始计算的)第i个位置标号数据域0a1=101a2=122a3=253a4=84a

3、5=165a6=20标号数据域0a1=101a2=122a3=253a4=84a5=165a6=206a7=20a6=16a5=8a4=25a3=1717插入2.3链式存储结构2.3物理结构之----链式结构:单链表存储空间分配特点1物理上不连续2依赖后继指针定位下一个元素的位置链表的结点datanext数据域：存放数据指针域：存放后继结点的位置62.3.2单链表的实现—构造函数templateLinkList::LinkList(Ta[],intn){//初始化头结点Node*first=newNode;first->next

4、=NULL;for(inti=0;i*s=newNode;s->data=a[i];①s->next=first->next;②first->next=s;①②答疑（上机实验…下节课有时间看一下我的冯如杯，程序检测）VC++安装eVIBackupX64DevVS2010第3章栈、队列、串有操作约束的线性关系（逻辑结构）一个数据结构类型是一个值的集合和定义在这个的集合上的一组操作（操作）什么是栈、队列、串？普通的线性表1）可以存储

5、任意类型的数据2）可以在任意位置进行插入、删除操作。特殊的线性表栈：后进先出LIFO线性表队列：先进先出FIFO线性表串：字符为数据元素的线性表一个数据结构类型是值集(一类数据对象)及其上的一组操作103.1栈---实例1、出入电梯最后进电梯的人，最先出电梯2、叠放的盘子最先放的盘子在最下面，后放的盘子在上面3、程序/函数之间的调用层次关系最后调用的函数，最先被释放迷宫问题课件.lnk……3.1.1栈的定义栈的定义限制仅在表的一端进行插入和删除的线性表栈顶(top)栈底(bottom)空栈存取原则后进先出(LIFO)43210bottomtopCBA3.1.1栈

6、的定义栈的ADT数据Data存储结构：顺序结构or链式结构操作Operation1InitStack2DestoryStack3Push//压入栈4Pop//弹出栈5GetTop//获取栈顶元素6Empty133.1.2顺序栈顺序栈本质顺序表的简化，唯一需要确定的是数组的哪一端表示栈顶，哪一端表示栈底。通常栈底：下标为0的一端栈顶：top指针表示，空栈时top=-143210bottomtopCBA3.1.2顺序栈43210top空栈43210topCBAABC依次入栈43210topBAC出栈15思考3分钟时间(c.f古国)1．一个栈的输入序列为12345，则

7、下列序列中有可能是栈的输出序列的是（提示：push/pop操作可以是穿插使用）。A.14253B.54132C.31245D.23415ps/pp(1)ps(234)pp(4)【X】ps(1～5)pp(5)pp(4)【X】ps(123)pp(3)【X】ps(12)pp(2)ps/pp(3)ps/pp(4)pp(1)163.1.2顺序栈的实现constintSTACKSIZE=100;templateclassSeqStack{public:SeqStack();intEmpty();TGetTop();//获取栈顶元素voidPush(T);//

8、入栈TPop();//出