当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

南京大学:《数据结构 Data Structures》课程教学资源(PPT课件讲稿)第三章 栈和队列

§3.1 栈(stack) §3.2 栈与递归 §3.3 队列(queue) §3.4 优先级队列 (priority queue)
资源类别:文库,文档格式:PPT,文档大小:845KB,文档页数:92,团购合买
点击下载完整版文档(PPT)

第三章 栈和队列 栈 队列 线性结构 优先级队列 与表不同的是,它们都是限制 存取位置的线性结构

1 第三章 栈和队列 栈 队列 优先级队列 与表不同的是,它们都是限制 存取位置的线性结构 线性结构

§3.1栈(stack) ·只允许在一端插入和删除的线性表 允许插入和删除 退栈 进栈 (弹出) (压入) 的一端称为栈顶 (top),另一端称 top an-1 为栈底(bottom) 4n-2 ·特点 1 o 后进先出(LIFO) bottom→ 2

§3.1 栈(stack) • 只允许在一端插入和删除的线性表 • 允许插入和删除 的一端称为栈顶 (top),另一端称 为栈底(bottom) • 特点 后进先出(LIFO) 2

栈的抽象数据类型 template class Stack{ public: Stack int=10 ) /构造函数 void Push(const E&item);/进栈 E Pop () 出栈 E getTop () /取栈顶元素 void makeEmpty () /置空栈 int IsEmpty (const; /判栈空否 int IsFull const; /判栈满否 } 3

template class Stack { public: Stack ( int=10 ); //构造函数 void Push ( const E & item); //进栈 E Pop ( ); //出栈 E getTop ( ); //取栈顶元素 void makeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 } 栈的抽象数据类型 3

栈的数组表示一顺序栈 0123456789 maxSize-1 elements top(栈空) #include class SeqStack public Stack private: int top; /栈顶指针 E *elements; /栈元素数组 int maxSize; /栈最大容量 void overflowProcess(;/栈的益出处理

栈的数组表示 — 顺序栈 #include template class SeqStack : public Stack { private: int top; //栈顶指针 E *elements; //栈元素数组 int maxSize; //栈最大容量 void overflowProcess(); //栈的溢出处理 0 1 2 3 4 5 6 7 8 9 maxSize-1 top (栈空) elements 4

public: Stack (int sz=10); /构造函数 ~Stack )delete elements; void Push (E x); /进栈 int Pop E&x); /出栈 int getTop (E&x); /取栈顶 void makeEmpty(){top=-l;}∥置空栈 int IsEmpty (const return top ==-1;} int IsFull (const return top =maxSize-1; 3 5

public: Stack (int sz = 10); //构造函数 ~Stack ( ) { delete [ ] elements; } void Push (E x); //进栈 int Pop (E& x); //出栈 int getTop (E& x); //取栈顶 void makeEmpty ( ) { top = -1; } //置空栈 int IsEmpty ( ) const { return top == -1; } int IsFull ( ) const { return top == maxSize-1; } } 5

b top→a top L top→空栈 M进栈 b进栈 top e top e d d C c b b L L e进栈 ∫进栈溢出 进栈示例 6

top 空栈 top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 进栈示例 6

e top d d C top C C b b top b L L L e退栈 d退栈 C退栈 b top L L b退栈 top→a退栈 top→空栈 退栈示例

top c 退栈 b 退栈 a b a a 退栈 空栈 top a b d d 退栈 c top a b c top top top a b d e e 退栈 c 退栈示例7

顺序栈的操作 template void SeqStack::overflowProcess( /私有数:当栈满则执行扩充栈存储空间处 理 E *newArray new E[2*maxSizel; 川创建更大的存储数组 for (inti=0;i<-top;i++) newArray[i]elements[i; maxSize +maxSize; delete elements; elements newArray; /改变elements指针 }; 8

8 顺序栈的操作 template void SeqStack::overflowProcess() { //私有函数:当栈满则执行扩充栈存储空间处 理 E *newArray = new E[2*maxSize]; //创建更大的存储数组 for (int i = 0; i <= top; i++) newArray[i] = elements[i]; maxSize += maxSize; delete [ ]elements; elements = newArray; //改变elements指针 };

template void SeqStack:Push(E x) /若栈不满,则将元素X插入该栈栈顶,否则溢出处理 if (IsFullO==true)overflowProcess(); /栈满 elements[++top]=x; /栈顶指针先加1,再进栈 }; template bool SeqStack:Pop(E&x) /川丞数退出栈顶元素并返回栈顶元素的值 if (IsEmpty()==true)return false; x elements[top--]; 川栈顶指针退1 return true; 川退栈成功 }; 9

9 template void SeqStack::Push(E x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess(); //栈满 elements[++top] = x; //栈顶指针先加1, 再进栈 }; template bool SeqStack::Pop(E& x) { //函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--]; //栈顶指针退1 return true; //退栈成功 };

template bool Seqstack::getTop(E&x) /若栈不空则極数返回该栈栈顶元素的地址 if (IsEmpty()==true)return false; x elements[top]; return true; }; 10

10 template bool Seqstack::getTop(E& x) { //若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() == true) return false; x = elements[top]; return true; };

点击下载完整版文档(PPT)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共92页,可试读20页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有