严蔚敏版数据结构课件.pptVIP

数据结构课程的内容1

第三章栈和队列3.1栈（Stack）3.2队列（Queue）1.定义1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式2.逻辑结构3.存储结构4.运算规则5.实现方式2

3.1栈限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）1.定义2.逻辑结构与同线性表相同，仍为一对一关系。3.存储结构用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。4.运算规则实现方式关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。5.基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。3

3.1栈问：堆栈是什么？它与一般线性表有什么不同？答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表逻辑结构：一对一堆栈逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝压入=PUSH（x)“出”＝弹出=POP(y)4

教材P44对栈有更详细定义：栈是仅在表尾进行插入、删除操作的线性表。表尾(即a端)称为栈顶top;表头(即a端)称为栈底basen1例如：栈s=(a,aaaa)2,3,……….,n-1,n1a1称为栈底元素an称为栈顶元素插入元素到栈顶（即表尾）的操作，称为入栈。从栈顶（即表尾）删除最后一个元素的操作，称为出栈。强调：插入和删除都只能在表的一端（栈顶）进行！5

栈的表示和实现?顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，?base为栈底指针，指向栈底的位置。toptopbasetopbasebaabase空栈进栈b进栈a6

顺序栈示意图data99...stop(栈顶)(栈底)3a3a2a1210

顺序栈的类型表示:?#defineSTACK_INIT_SIZE100；?#defineSTACKINCREMENT10；?typedefcharStackData;?typedefstruct{//顺序栈定义?StackData*base;//栈底指针?StackData*top;//栈顶指针?intstacksize；//当前已分配的存储空间?}SeqStack；8

顺序栈的基本运算:?判栈空?intStackEmpty(SeqStack*S){?if(S-top==S-base)return1//空则返回1elsereturn0;//否则返回0?}?判栈满?intStackFull(SeqStack*S){?if(S-top-S-base=S-StackSize)return1//判栈满,满则返回1?elsereturn0;//否则返回0?}9

§初始化voidInitStack(SeqStack*S){//置空栈S-base=(StackData*)malloc(STACK_INIT_SIZE*sizeof(StackData));if(!S-base)exit(OVERFLOW);S-top=S-base;S-stacksize=STACK_INIT_SIZE;Returnok;}10

表和栈的操作区别——对线性表s=(a,aaa)12,….,n-1,n顺序表V[n]顺序栈Sa栈顶top表尾高地址n+1高地址an……an……aiv[i]ai……a2……a2a栈底base表头低地址低地址a11写入：v[i]=ai读出：x=v[i]压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！11

入栈操作——例如用堆栈存放（A，B，C，D）（注意要遵循“后进先出”原则）高地址MtopDCBAtopCtoptopBBAAA低地址Ltop核心语句：top=L;顺序栈中的PUSH函数statusPush(ElemTypex){if(topM){上溢}elsev[top++]=x;}Push(A);Push(B);Push(C);Push(D);12

?入栈?intPush(SeqStack*S,StackDatax){?//插入元素x为新的栈顶元素?if(StackFull(S)){??S-base=(StackData*)ma