深圳大学-数据结构-2017栈和队列演示文档

《深圳大学-数据结构-2017栈和队列演示文档》由会员分享，可在线阅读，更多相关《深圳大学-数据结构-2017栈和队列演示文档（63页珍藏版）》请在装配图网上搜索。

.,第三章栈和队列,,,数据结构,.,一、栈,2,第一节　栈,栈是限定仅在表尾(top)进行插入或删除操作的线性表。 允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头) 特点：后进先出 (LIFO),.,二、栈的实现,3,第一节　栈,栈的存储结构主要有两种： 1. 顺序栈 2. 链式栈,.,一、顺序栈,4,第二节　顺序栈,顺序栈是栈的顺序存储结构 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。,.,二、顺序栈的定义,5,第二节　顺表栈,采用C语言中动态分配的一维数组表示顺序表,#define STACK_INIT_SIZE 100 //栈存储空间的初始分配量 #define STACKINCREMENT 10 //栈存储空间的分配增量 typedef struct { SElemType *base //存储空间基址 SElemType *top; //栈顶指针 int stacksize; //当前分配的存储容量(元素数) } SqStack;,.,三、顺序栈的特性,6,第二节　顺序栈,top==0 或top==base 表示空栈 base=NULL表示栈不存在 当插入新的栈顶元素时,指针top+1 删除栈顶元素时，指针top-1 当top>stacksize时，栈满，溢出,.,四、顺序栈的主要操作,7,第二节　顺序栈,ADT Stack { 数据对象：D = {ai | ai∈ElemSet, i=1,2,3,…,n} 数据关系：R = { | ai-1,ai∈D} 基本操作： Status InitStack(SqStack &S) // 构造空栈 Status Push(SqStack &S, e) // 进栈 Status Pop(SqStack &S, &e) // 出栈 Status GetTop(SqStack S, &e)// 取栈顶元素值 Status StackEmpty(SqStack S) // 栈是否为空 　 } ADT Stack,.,五、创建顺序栈,8,第二节　顺序栈,Status InitStack(SqStack } // InitStack,.,六、进栈（插入新元素）,9,第二节　顺序栈,Status Push(SqStack } // Push,.,七、出栈（删除元素）,10,第二节　顺序栈,Status Pop(SqStack } // Pop,.,八、取栈顶元素,11,第二节　顺序栈,Status GetTop(SqStack S, SElemType } // GetTop,.,1.创建堆栈节点类 template class LinStack;//前视定义,否则友元无法定义 template //模板类型为T class StackNode { friend class LinStack; //定义类LinStack为友元 private: T data; //数据元素 StackNode *next; //指针 public: StackNode(StackNode *ptrNext = NULL) //构造头结点 {next = ptrNext;} StackNode(const T,第三节　链栈,.,第三节　链栈,2.创建链式堆栈类 template class LinStack { private: StackNode *head; //头指针 int size; //数据元素个数 public: LinStack(void); //构造函数 ~LinStack(void);//析构函数 void Push(const T,.,第三节　链栈,3.链式堆栈的实现 template LinStack::LinStack() //构造函数 { head = new StackNode;//头指针指向头结点 size = 0; //size的初值为0 } template LinStack::~LinStack(void) //析构函数 { StackNode *p, *q; //释放所有动态申请的结点空间 p = head; //p指向头结点 while(p != NULL) //循环释放结点空间 { q = p; p = p->next; delete q; } } template int LinStack::NotEmpty(void) const //堆栈非空否 { if(size != 0) return 1; else return 0; },.,第三节　链栈,template void LinStack::Push(const T //元素个数加1 },.,第三节　链栈,template T LinStack::Pop(void) //出栈 { if(size == 0) { cout *p = head->next;//p指向栈顶元素结点 T data = p->data; head->next = head->next->next; //原栈顶元素结点脱链 delete p; //释放原栈顶结点空间 size--; //结点个数减1 return data; //返回原栈顶结点的data域值 },.,第三节　链栈,template T LinStack::GetTop(void)const //取栈顶元素 { return head->next->data; },.,一、数值转换,18,第四节　栈的应用举例,将十进制转换为其它进制(d)，其原理为： N = (N/d)*d + N mod d [例1]：（1348)10=(2504)8 ，其运算过程如下： N N /8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,.,一、数值转换,19,第四节　栈的应用举例,void conversion () { InitStack(S); // 创建新栈S scanf (“%d”,N); // 输入一个十进制数N while (N) { Push(S, N % 8); // 将余数送入栈中 N = N/8; // 求整除数 } while (!StackEmpty(S)) { // 如果栈不空 Pop(S,e); // 将栈中数出栈 printf ( "%d", e ); } } // conversion,.,二、行编辑程序,20,第四节　栈的应用举例,用户输入一行字符 允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正 假设从终端接受两行字符： whli##ilr#e（s#*s) 实际有效行为： while (*s),.,二、行编辑程序,21,第四节　栈的应用举例,[例2]:对用户输入的一行字符进行处理,直到行结束(“\n”) void LineEdit() { InitStack(s); ch = getchar(); //从终端接受一个字符 while (ch != ’\n’) { switch(ch) { case ’#’ : Pop(S, c);break; // 仅当栈非空时退栈 case ‘@’: ClearStack(S); break; default: Push(S, ch); break; // 有效字符进栈 } ch = getchar(); // 从终端接受一个字符 } //将从栈底到栈顶的栈内字符传送到调用过程的数据区; … },.,第四节　栈的应用举例,三.括号匹配 假设一个算术表达式中包括( )、[ ]和{ }三种形式的括号，设计一个判别表达式中括号是否正确匹对的程序。 1.算法思想： 算术表达式中右括号和左括号匹配的次序:后到括号要最先被匹配的“后进先出”堆栈操作特点，因此可用一个堆栈来进行判断。 顺序扫描算术表达式（表现为一个字符串）； 当遇到三种类型的左括号时，该括号进栈； 当遇到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈，继续进行判断； 若不匹配，则左右括号配对次序不正确，结束。 若字符串当前为某一类型的右括号而堆栈为空，则右括号多于左括号，结束。 若字符串扫描结束而堆栈非空，则左括号多于右括号，结束。 若字符串扫描结束而堆栈为空，则左右括号匹配正确，结束。,.,第四节　栈的应用举例,#include #include #include using namespace std; bool brackMatch(string str) //括号匹配 { int i = 0; stack stk; // 使用C++的stack类 while(inext; //p指向新的队头结点 T data = front->data; //保存原队头结点的data域值 delete front; //释放原队头结点空间 front = p; //front指向新的队头结点 count--; //计数器减1 return data; //返回原队头结点的data域值 },.,队列应用举例,实例: 编写判断一个字符序列是否回文的函数. 回文:一个字符序列以中间字符为基准且两边字符 完全相同。 算法描述: 字符数组中存放要判断的字符串。 把字符数组中字符逐个分别存入一个队列和一个堆栈 逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。,.,队列应用举例,const int MaxQueueSize = 10; const int MaxStackSize = 10; typedef char DataType; …… //构造一个顺序循环队列,一个顺序栈 void HuiWen(char str[]) //判断字符串str是否是回文 { SeqStack myStack; SeqQueue myQueue; int n = strlen(str); //求字符串长度 for(int i = 0; i < n; i++) { myQueue. EnQueue(str[i]); myStack.Push(str[i]); } while(myQueue.NotEmpty() },.,队列应用举例,void main(void) { char str1[] = {"ABCDEDCBA"}; char str2[] = {"ABCDEDBAC"}; cout << "字符串ABCDEDCBA"; HuiWen(str1); cout << "字符串ABCDEDBAC"; HuiWen(str2); },.,队列应用举例,下标 I j pre 0 1 1 -1 1 1 2 0 2 2 1 0 3 2 2 1 4 3 1 2 5 3 2 3 6 4 1 4 7 3 3 5 8 5 1 6 9 3 4 7 10 5 2 8 11 6 1 8 12 2 4 9 13 5 3 10 14 7 1 11 15 1 4 12 16 2 5 12 17 6 3 13 18 1 5 15 19 2 6 16 20 6 4 17,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,.,队列应用举例,下标 I j pre 1 6 18 6 5 20 5 5 22 7 5 22 4 5 23 5 6 23 8 5 24 4 6 25 5 7 26 8 6 27 4 7 28 5 8 29 6 7 29 8 7 30 3 7 31 4 8 31 6 8 32 8 8 34,迷宫求解结果： 迷宫路径： (1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (7,5) (8,5) (8,6) (8,7) (8,8),.,练 习,1.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少? 一个栈的入栈序列是abcde，则可能的出栈序列为: A.edcab B.decba C.debca D.cabde,.,练 习,3. 假定用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23，45，67，80，34，其中23为队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，48元素依次进队，再次画出对应的存储状态。 4. 表达式a*(b+c)-d的后缀表达式是 ？,.,练 习,5. 设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1,则栈的容量至少应该是（）。 A.2 B.3 C.4 D.5 6. 设已将元素a1，a2，a3依次入栈，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）。 A．a3 a1 a4 a2 B．a3 a2 a4 a1 C． a3 a4 a2 a1 D．a4 a3 a2 a1,.,练 习,7. 向一个栈顶指针为top的链栈中插入一个s所指结点时，其操作步骤为（）。 A．top->next=s. B．s->next=top->next;top->next=s. C．top->next=s;top=s. D．s->next=top; top=top->next. 8. 从栈顶指针为top的链栈中删除一个结点,并将被删结点的值保存到x中,其操作步骤为（）。 A．x=top->data; top=top->next; B．top=top->next; x=top->data; C．x=top; top=top->next; D．x=top->data.,.,练 习,9. 链栈和顺序栈相比，有一个较明显的优点是（）。 A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更加方便 D．删除操作更加方便   10. 设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作操作修改指针的是（） A．sq.front=(sq.front+1)%m B．sq.front=(sq.front+1)%(m+1) C．sq.rear=(sq.rear+1)%m D．sq.rear=(sq.rear+1)%(m+1)   11、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为（）。 A．f->next=c;f=s; B．r->next=s;r=s; C．s->next=r;r= s D．s->next=f;f=s;,.,队列应用举例,[课堂练习]:报数问题 有10个人站一排队,从左向右编号:1-10号 现从左向右报数”1,2,1,2,1,2,1,2,1,2”, 要求报数1的人出列,报数2的人立即站到队 尾,直到所有的人都出列,给出人们的出列顺 序算法.,