第 4 章 数据结构.ppt

《第 4 章 数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章　数据结构1.1基本数据结构与算法1.2线性表1.3栈和队列1.4树和二叉树1.5查找1.6内部排序ABCDEFG姓名学号成绩班级李红976105995机97.61065865<例>一叠书或一叠盘子。……栈顶栈底a1栈s=(a1,a2,…，an)a2············an-1an一种操作受限的线性表只允许在表的一端进行插入和删除1.栈的定义定义：只允许在线性表的一端进行插入和删除的线性表。与栈有关的相关术语：1.3栈和队列(1)栈顶：允许插入与删除的一端称为栈顶(2)栈底：不允许插入与删除的一端称为栈底(3)入栈：栈的插入操作(往栈中插入一个元素)(4)出栈：

2、栈的删除操作(从栈中删除一个元素)(5)栈空：top=0(6)栈满：top=m(m为栈最大容量)a1a2….an进栈出栈栈顶栈底假设栈：s=(a1,a2,…，an)1.3.1栈栈空：top=-1栈示意图：修改栈的原则：(考点)先进后出(FILO,FirstInLastOut)或后进先出(LIFO)栈顶元素总是最后入栈，而最先出栈的栈底元素总是最先入栈，而最后出栈的a1a2….an进栈出栈栈顶栈底堆栈操作A进BA进A出CA进A出DA进A出出初始出栈元素顺序：B→C→D→A1.栈的定义1.3栈和队列1.3.1栈2.顺序栈及其运算1)栈的两种存储结构顺序存储结构：利用一组地址连

3、续的存储单元依次存放自栈底到栈顶的数据元素。链式存储结构：用于收集计算机存储器中所有空闲存储空间,来保存自栈底到栈顶的数据元素。顺序栈：顺序存储结构的栈称为顺序栈。链栈：链式存储结构栈称为链栈。top=0123450栈空top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空顺序栈实现：一维数组data[M]注意：数组是倒过来图示的。故，top指向的是其箭头上面的存

4、储空间顺序栈实现：一维数组data[M]栈顶指针并不一定是指针变量，也可以是下标变量#defineSIZE50typedefstruct{chardata[SIZE];inttop;}SeqStack;/*置栈空*/ voidInitStack（SeqStack*S）{   S->top=0;   }/*进栈*/voidPush（SeqStack*S，charx）{   if(StackFull(S))     {printf(“Stackoverflow”);//上溢，退出运行exit(0);}     S->data[S->top]=x;//将x入栈S->

5、top=S->top+1;//栈顶指针加1 }/*出栈*/charPop（SeqStack*S）{if(StackEmpty(S))   {printf(“Stackunderflow”);//下溢，退出运行exit(0);}S->top=S->top-1;//将栈顶指针减1returnS->data[S->top];//栈顶元素返回}top=0栈空123450Atop=1假设：调用两次Push函数Push(S,‘A’);Push(S,’B’);top=2B假设：调用一次Pop函数Pop(S);1.栈的定义1.3栈和队列1.3.1栈2.顺序栈及其运算1)栈的两种存

6、储结构2)顺序栈的基本运算：入栈、出栈与读栈顶元素(1)入栈新元素插入到栈顶指针指向位置栈顶指针top加1步骤：注意:栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误.栈空：top=0思考：当栈空条件为：top=-1时，入栈步骤1.栈的定义1.3栈和队列1.3.1栈2.顺序栈及其运算1)栈的两种存储结构2)顺序栈的基本运算：入栈、出栈与读栈顶元素(2)出栈步骤：栈顶指针top减1栈顶元素赋给一个指定的变量栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误1.栈的定义1.3栈和队列1.3.1栈2.顺序栈及其运算1)栈的两种存储结构2)顺序栈的基本

7、运算：入栈、出栈与读栈顶元素(3)读栈顶元素概念：将栈顶元素赋给一个指定变量注意：不删除栈顶元素，栈顶指针不会改变1.栈的定义1.3栈和队列1.3.1栈2.顺序栈及其运算1)栈的两种存储结构2)顺序栈的基本运算：3)栈的典型应用进制的转换1392(余1692(余1342(余0172(余182(余042(余022(余0110001011(139)10=(10001011)22(余10除余倒序法(139)10＝（？）21392692342172824222120除余倒序法(139)10＝（？）211010001余数栈定义：指允许在