第3章栈和队列 要求 1、掌握栈与队列的逻辑结构 2、栈和队列的顺序存储和链式存储表示,即顺序栈、链栈如何表示:链队列与循环队列如何 表示 3、不同存储方式下操作算法 教材习题参考解答 3.1(1)有5种:123、321、132、213、231 (2)能得到135426,不能得到435612 3.2A 、顺序栈 #define maXsize 100 typedef struct ElemType elem [MAXSIZE I SeqStack: int IsEmpty(SeqStack *pS) return (pS->top==-1 int IsFull(SeqStack *pS) return (pS->top = MAXSIZE-1? 1: 0) 、链栈 typedef struct next ElemType data struct node *k next I NODE, *LinkStack int IsEmpty (Link Stack S) return(S->next = NULL 1: 0) 3.4参考教材P59~60 3.5//此程序为判断一个字符串是否为回文。字符串以@结尾 //中间以&’分隔 //程序的实现通过一个栈和一个队列来实现,首先将’&以前的所有字符压入栈 /然后将’&后的字符加入队列,再分别进行出栈和出队处理,比较栈顶和队头的字符
第 3 章 栈和队列 要求： 1、掌握栈与队列的逻辑结构； 2、栈和队列的顺序存储和链式存储表示，即顺序栈、链栈如何表示；链队列与循环队列如何 表示； 3、不同存储方式下操作算法。 教材习题参考解答： 3.1 (1)有 5 种：123、321、132、213、231 (2)能得到 135426，不能得到 435612。 3.2 A 3.3 一、顺序栈 #define MAXSIZE 100 typedef struct { ElemType elem[MAXSIZE]; int top; }SeqStack; int IsEmpty(SeqStack *pS) { return (pS->top==-1 ? 1 : 0); } int IsFull(SeqStack *pS) { return (pS->top == MAXSIZE-1 ? 1 : 0); } 二、链栈 typedef struct next { ElemType data; struct node * next; }NODE, *LinkStack; int IsEmpty(LinkStack S) { return (S->next == NULL ? 1 : 0); } 3.4 参考教材 P59～60 3.5 //此程序为判断一个字符串是否为回文。字符串以'@'结尾， //中间以'&'分隔 //程序的实现通过一个栈和一个队列来实现，首先将'&'以前的所有字符压入栈 //然后将'&'后的字符加入队列，再分别进行出栈和出队处理，比较栈顶和队头的字符
#include <stdio. h #include <stdlib. h /栈和队列均用链表实现,队列用循环队列 typedef struct node char data struct node *next I NODE, *LinkStack, *LinkQueue //初始化栈,创建一个头结点 void InitStack (LinkStack *pS) LinkStack p p=(LinkStack)malloc(sizeof (NODE)) p->next NULL: //入栈算法 int Push(LinkStack S, char e) LinkStack p p =(LinkStack)malloc(sizeof (NODE)) f(!p) //若创建结点不成功则返回0 return 0: //将新创建结点插入头结点之后 p->next S->next S->next =p retu //出栈算法 int Pop(LinkStack S, char *pe) LinkStack if(S->next==NULL)//若栈为空,则不能出栈,返回0 return 0 S->next p->next *pe p->data free(p) return /初始化队列算法 void InitQueue(LinkQueue *pQ)
#include <stdio.h> #include <stdlib.h> //栈和队列均用链表实现，队列用循环队列 typedef struct node { char data; struct node *next; }NODE, *LinkStack, *LinkQueue; //初始化栈，创建一个头结点 void InitStack(LinkStack *pS) { LinkStack p; p = (LinkStack)malloc(sizeof(NODE)); p->next = NULL; *pS = p; } //入栈算法 int Push(LinkStack S, char e) { LinkStack p; p = (LinkStack)malloc(sizeof(NODE)); if(!p) //若创建结点不成功则返回 0 return 0; //将新创建结点插入头结点之后 p->data = e; p->next = S->next; S->next = p; return 1; } //出栈算法 int Pop(LinkStack S, char *pe) { LinkStack p; if(S->next == NULL) //若栈为空，则不能出栈，返回 0 return 0; p = S->next; S->next = p->next; *pe = p->data; free(p); return 1; } //初始化队列算法 void InitQueue(LinkQueue *pQ) {
LinkQueue p p=(LinkStack)malloc(sizeof (NODE)) //形成一个环形链表 /进队算法,pQ为指向队尾结点的指针的指针 int EnQueue(LinkQueue *pQ, char e) LinkQueue p, Q: Q=**pQ //让Q指向队尾 p=(LinkStack)malloc(sizeof (NODE)) if(p) //如果创建结点不成功 return 0 //将p结点插入pQ之后 ->data =e: *p Q=p retu //出队算法 int DeQueue(LinkQueue *pQ, char *pe) LinkQueue p, Q Q=*pQ Q=*pQ //让Q指向队尾 //让Q指向头结点 Q==*pQ)/如果仅有头结点,则说明队列为空 return //如果不为空队,则进行出队处理 /先让p指向头结点的后继结点,再将p结点删除 *pe p->data a->next = p->next fr //如果出队后为空队,则原队尾指针的值要改变,即指向头节点 f(Q->next = Q) return 1 id maino
LinkQueue p; p = (LinkStack)malloc(sizeof(NODE)); p->next = p; //形成一个环形链表 p->data = 0; *pQ = p; } //进队算法，pQ 为指向队尾结点的指针的指针 int EnQueue(LinkQueue *pQ, char e) { LinkQueue p, Q; Q = *pQ; //让 Q 指向队尾 p = (LinkStack)malloc(sizeof(NODE)); if(!p) //如果创建结点不成功 return 0; //将 p 结点插入 pQ 之后 p->data = e; p->next = Q->next; Q->next = p; *pQ = p; return 1; } //出队算法 int DeQueue(LinkQueue *pQ, char *pe) { LinkQueue p, Q; Q = *pQ; Q = *pQ; //让 Q 指向队尾 Q = Q->next; //让 Q 指向头结点 if( Q == *pQ ) //如果仅有头结点，则说明队列为空 return 0; //如果不为空队，则进行出队处理 //先让 p 指向头结点的后继结点，再将 p 结点删除 p = Q->next; *pe = p->data; Q->next = p->next; free(p); //如果出队后为空队，则原队尾指针的值要改变，即指向头节点 if( Q->next == Q) *pQ = Q; return 1; } void main() {
char str[80], chl, ch2,= LinkStack s InitStack(&S) InitQueue(&Q) printf("请输入一个待判断是否为回文的字符串,以@结尾,中间为&':\n") str /分别对”&’前面的字符入栈,对后面的字符进队 while(*p) if((z==0)&&(*p!='&)&&(*p!='g)) if((z==1)&&(*!='&)&&(*p!='@)) EnQueue(&Q, *p) while( pop s, &ch1)&& DeQueue(&Q, &ch2) if(ch1!= ch2) printf("不是回文!n") sf =0 if(sf==1 && Pop(s, &ch1)&&! DeQueue( &Q, &ch2)) printf("是回文!n") else printf("不是回文!n") 解法二://利用栈实现回文判断 #include <stdio. h> #define max 80 //定义顺序栈结构 typedef struct
char str[80], ch1,ch2, *p; int z=0,sf=1; LinkStack S; LinkQueue Q; InitStack(&S); InitQueue(&Q); printf("请输入一个待判断是否为回文的字符串，以'@'结尾，中间为'&'：\n"); gets(str); p = str; //分别对'&'前面的字符入栈，对后面的字符进队 while(*p) { if( (z==0) && (*p != '&') && (*p !='@') ) Push(S, *p); if( (z==1) && (*p != '&') && (*p !='@') ) EnQueue(&Q, *p); if( *p == '&' ) z = 1; if( *p == '@') break; p++; } while( Pop(S, &ch1) && DeQueue(&Q, &ch2)) { if(ch1 != ch2) { printf("不是回文！\n"); sf = 0; break; } } if(sf==1 && !Pop(S, &ch1) && !DeQueue(&Q,&ch2)) printf("是回文！\n"); else if(sf==1) printf("不是回文！\n"); } 解法二：//利用栈实现回文判断 #include <stdio.h> #include <stdlib.h> #define MAX 80 //定义顺序栈结构 typedef struct {
char elem[MAX int to ISTACK void Init Stack (STACK *pS pS-top=-1;//top为栈顶元素在数组elem中的下标,由于开始没有元素,则为-1 int Push(STACK *pS, char e) if(ps->top >= MAX-1) return 0 pS->top++;/(改变栈顶位置 pS->elem [pS->top]=e return 1 int Pop (stacK =ps, char *pe if(ps->top ==-1 return 0 *pe= pS->elem[ps->top pS->top- return 1 void maino char str[80, cl, c2, *p; STACK S: Init Stack(&S) printf("请输入一串以@结尾中间为’&’字符的字符串:") //将’&’前面的字符依次入栈 while(*p!=”&’&&*p!=’10’) if(! Push(&S, *p)) printf("栈空间溢出!") exit(o)
char elem[MAX]; int top; }STACK; void Init_Stack(STACK *pS) { pS->top = -1; //top 为栈顶元素在数组 elem 中的下标，由于开始没有元素，则为－1 } int Push(STACK *pS, char e) { if(pS->top >= MAX-1) return 0; pS->top++; //改变栈顶位置 pS->elem[pS->top] = e; return 1; } int Pop(STACK *pS, char *pe) { if(pS->top == -1) return 0; *pe = pS->elem[pS->top]; pS->top--; return 1; } void main() { char str[80], c1,c2,*p; STACK S; Init_Stack(&S); printf("请输入一串以'@'结尾中间为'&'字符的字符串："); gets(str); p = str; //将'&'前面的字符依次入栈 while(*p != '&' && *p != '\0') { if(!Push(&S, *p)) { printf("栈空间溢出！"); exit(0); } p++;