回文序列判断(运用栈以及队列完成)

数据结构回文实验报告1. 实验目的本实验旨在通过使用数据结构中的栈和队列的知识，设计并实现一个回文判断程序，以检测给定的字符串是否为回文。

2. 实验原理回文是指正读和反读都相同的字符串。

在本实验中，我们将使用栈和队列来判断给定字符串是否为回文。

具体步骤如下：2.1 将字符串加入栈和队列将给定的字符串依次加入栈和队列中，保持顺序一致。

2.2 从栈和队列中弹出字符从栈和队列中分别弹出字符，并进行比较。

2.3 判断是否为回文如果所有字符都一一相等，那么该字符串就是回文。

否则，不是回文。

3. 实验步骤接下来，我们将按照上述原理，逐步进行回文判断的实验。

3.1 导入所需库由于本实验仅使用了基本的数据结构，无需导入额外的库或模块。

3.2 创建栈和队列首先，我们需要创建栈和队列的数据结构。

栈可以通过使用列表来实现，而队列则可以通过使用双端队列来实现。

# 创建栈stack = []# 创建队列from collections import dequequeue = deque()3.3 输入字符串接下来，我们需要从用户获取一个待判断的字符串。

# 获取待判断的字符串string = input("请输入待判断的字符串：")3.4 将字符串加入栈和队列将输入的字符串依次加入栈和队列中。

# 将字符串加入栈和队列for char in string:stack.append(char)queue.append(char)3.5 从栈和队列中弹出字符并比较从栈和队列中分别弹出字符，并进行比较，直到栈或队列为空。

is_palindrome =Truewhile len(stack) >0and len(queue) >0:stack_char = stack.pop()queue_char = queue.popleft()if stack_char != queue_char:is_palindrome =Falsebreak3.6 输出判断结果根据比较结果，输出判断字符串是否为回文。

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e) { Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

head第3章 栈和队列 自测卷答案 姓名 班级一、填空题（每空1分，共15分）1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。

不允许插入和删除运算的一端称为 栈底 。

3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。

(注：不一定，这是一种约定，在殷教材中是队首指针指向队列的首元素位置)5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。

6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。

(注：不一定，这是一种约定，在殷教材中是先 取出元素 ，后移动队首指针 )8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。

解：二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧调用子程序或函数常用，CPU 中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（×）5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

问题描述：编程序判断一个字符列是否是回文。

回文是指一个字符序列以中间字符为基准两边字符完全相同。

要求程序从键盘输入一个字符串，字符串长度小于等于80，用于判断回文的字符串中不包括字符串的结束标记符。

基本要求：（1）要求字符序列个数n可由用户随意确定，且有0<n<81；（2）可连续测试任意多个字符序列，可由用户决定退出测试程序；（3）字符序列由用户从键盘输入。

测试数据：（1）abcdcba（2）abcdefghi算法思想：判断回文函数Palinddrome()的算法思想是：把字符串的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列是回文，否则不是回文。

模块划分：（1）void Palindrome(char str[],int n)，判断字符序列是否回文函数。

（2）void EnterStr(char str[],int *n)，键盘输入字符序列函数。

（3）void main(void)，主函数。

循环调用函数EnterStr()和函数Palindrome()，当用户要求继续判断时则继续循环执行，否则结束。

上述三个函数存放在文件Palindrome.c中。

堆栈和队列分别利用第三章讨论的顺序堆栈和顺序循环队列，其文件分别为SeqStack.h和SeqCQueue.h。

数据结构：使用顺序堆栈和循环队列辅助字符序列的回文判断。

本问题中定义顺序堆栈和顺序循环队列的抽象数据类型DataType为cha类型。

源程序：/*文件SeqStack.h*/typedef struct{DataType stack[MaxStackSize];int top;}SeqStack;void StackInitiate(SeqStack *S) //初始化顺序堆栈S{S->top=0;}int StackNotEmpty(SeqStack S) //判断顺序堆栈S非空否，非空时返回1，否则返回0{if(S.top<=0) return 0;else return 1;}int StackPush(SeqStack *S,DataType x) //把数据元素值x压入顺序堆栈S，入栈成功时返回1，否则返回0{if(S->top>=MaxStackSize){printf("堆栈已满无法插入！\n");return 0;}else{S->stack[S->top]=x;S->top++;return 1;}}int StackPop(SeqStack *S,DataType *d) //弹出顺序堆栈S 的栈顶数据元素值到参数d，出栈成功是返回1，否则返回0{if(S->top<=0){printf("堆栈已空无数据元素出栈！\n");return 0;}else{S->top--;*d=S->stack[S->top];return 1;}}int StackTop(SeqStack S,DataType *d) //取顺序堆栈S的当前栈顶数据元素值到参数d，成功时返回1，否则返回0{if(S.top<=0){printf("堆栈已空！\n");return 0;}else{*d=S.stack[S.top-1];return 1;}}/*SeqCQueue.h*/typedef struct{DataType queue[MaxQueueSize];int rear; //队尾指针int front; //队头指针}SeqCQueue;void QueueInitiate(SeqCQueue *Q) //初始化顺序循环队列Q{Q->rear=0; //定义初始队尾指针下标值Q->front=0; //定义初始队头指针下标值}int QueueNotEmpty(SeqCQueue Q) //判断顺序循环队列Q非空否，非空时返回1，否则返回0{if(Q.front==Q.rear) return 0;else return 1;}int QueueAppend(SeqCQueue *Q,DataType x)//把数据元素值x插入顺序循环队列Q的队尾，成功返回1，否则返回0{if((Q->rear+1)%MaxQueueSize==Q->front){printf("队列已满无法插入！\n");return 0;}else{Q->queue[Q->rear]=x;Q->rear=(Q->rear+1)%MaxQueueSize;return 1;}}int QueueDelete(SeqCQueue *Q,DataType *d)//删除顺序循环队列Q的队头元素并赋给d，成功返回1，失败返回0{if(Q->front==Q->rear){printf("循环队列已空无数据元素出队列！\n");return 0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;return 1;}}int QueueGet(SeqCQueue Q,DataType *d) //取循序循环队列Q的当前队头元素并赋给D，成功返回1，失败返回0{if(Q.front==Q.rear){printf("循环队列已空无数据元素可取！\n");return 0;}else{*d=Q.queue[Q.front];return 1;}}/*文件Palindrome.c*/#include<string.h>#include<stdio.h>#define MaxStackSize 80 /*定义堆栈的数据元素最大个数*/#define MaxQueueSize 80 /*定义队列的数据元素最大个数*/typedef char DataType; /*定义具体应用的数据类型DataType*/#include"SeqStack.h"#include"SeqCQueue.h"void Palindrome(char str[],int n){SeqStack myStack;SeqCQueue myQueue;char x,y;int i;StackInitiate(&myStack);QueueInitiate(&myQueue);for(i=0;i<n;i++){QueueAppend(&myQueue,str[i]);StackPush(&myStack,str[i]);}while(QueueNotEmpty(myQueue)==1&&StackNotEmpty(myStack)==1) {QueueDelete(&myQueue,&x);StackPop(&myStack,&y);if(x!=y){printf("不是回文！");return;}}printf("是回文！");}void EnterStr(char str[],int *n){printf("输入字符串（不能超过80个字符）：");scanf("%s",str);*n=strlen(str);}void main(void){char ch,str[80];int n;while(1){EnterStr(str,&n);Palindrome(str,n);printf("\n要继续吗？（Y/N）:");scanf("%s",&ch);if(ch=='Y'||ch=='y')continue;else return;}}测试情况：。

3.6通常称正读和反读都相同的字符序列为”回文”,例如,abcdeedcba、abcdcba是回文。

若字符序列存储在一个单链表中，编写算法判断此字符序列是否是回文。

思路分析：为了方便编程实现，我们假设字符序列在字符数组中。

先把字符数组中的字符依次进栈和依次进队列，然后循环出栈顶元素、出队头元素，比较二者是否相同，只要有1个不同，就不是回文；如果最后栈、队列有1个不为空，也不是回文；最后栈、队列均空则是回文。

Char str=”abcdedcba”程序流程：定义顺序栈mystack定义顺序队列mysequeue初始化栈初始化队列将字符数组str[]的元素依次入栈将字符数组str[]的元素依次入队列While(栈不空&& 队列不空)｛出栈顶元素到x；出队头元素到y；If（x!=y）则不是回文，返回｝If(栈空&&队列空)则是回文否则不是回文本程序需要使用顺序栈头文件，顺序队列头文件。

下面已经给出，请写出判断是否是回文子程序，再写出测试main函数。

顺序栈头文件内容：#include<stdio.h>typedef struct{DataType data[MaxStackSize];int top;}seqstack;void InitStack(seqstack *s){s->top=-1;}int StackEmpty(seqstack *s){if(s->top==-1)return 1;elsereturn 0;}int SatckPush(seqstack *s,DataType x){if(s->top==MaxStackSize-1){printf("空间已满，无法入栈！\n");return 0;}s->top++;s->data[s->top]=x;return 1;}int StackPop(seqstack *s,DataType *x){if(s->top==-1){printf("堆栈已空，不能完成出栈操作！");return 0;}*x=s->data[s->top];s->top--;return 1;}int GetStackTop(seqstack *s,DataType *x){if(s->top==-1){printf("堆栈已空，不能完成取栈顶元素操作！");return 0;}*x=s->data[s->top];return 1;}顺序队列头文件内容：#include<stdio.h>typedef struct{DataType data[maxsize];int front;int rear;}sequeue;int InitQueue(sequeue *q){q->front=0;q->rear=0;return 1;}int LenQueue(sequeue *q){return (q->rear-q->front+maxsize)%maxsize;}int EmptyQueue(sequeue *q){if(q->front==q->rear)return 1;elsereturn 0;}int InsertQueue(sequeue *q,DataType x){if((q->rear+1)%maxsize==q->front){printf("队列已满,不能完成入队操作!\n");return 0;}q->data[q->rear]=x;q->rear=(q->rear+1)%maxsize;return 1;}int DelQueue(sequeue *q,DataType *x){if(q->front==q->rear){printf("队列已空,不能完成出队操作!\n");return 0;}*x=q->data[q->front];q->front=(q->front+1)%maxsize;return 1;}int GetHead(sequeue *q,DataType *x)5{if(q->front==q->rear){printf("队列已空,不能完成取队头操作!\n");return 0;}*x=q->data[q->front];return 1;}void output(sequeue *q){int i;for(i=q->front;i<q->front+(q->rear-q->front+maxsize)%maxsize;i++) {printf("%d\t",q->data[i%maxsize]);}printf("\n");}。

实验报告——栈和队列的应用第一篇：实验报告——栈和队列的应用实验5 栈和队列的应用目的和要求：（1）熟练栈和队列的基本操作；（2）能够利用栈与队列进行简单的应用。

一、题目题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。

所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。

例如，a+b&b+a等等。

题目2.假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

现要求写一算法模拟上述舞伴配对问题，并实现。

题目3.打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。

请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。

题目4.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。

试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

题目5.利用循环链队列求解约瑟夫环问题。

请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。

选择题目3：打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

二、程序清单//Ch3.cpp #include #include #include“ch3.h” template void LinkedQueue::makeEmpty()//makeEmpty//函数的实现{ LinkNode*p;while(front!=NULL)//逐个删除队列中的结点{p=front;front=front->link;delete p;} };template bool LinkedQueue::put_in(T&x）{//提交命令函数if(front==NULL){//判断是否为空front=rear=new LinkNode;//如果为空，新结点为对头也为对尾front->data=rear->data=x;if(front==NULL)//分配结点失败return false;} else{rear->link=new LinkNode;//如不为空，在链尾加新的结点rear->link->data=x;if(rear->link==NULL)return false;rear=rear->link;} return true;};template bool LinkedQueue::carry_out()//执行命令函数 { if(IsEmpty()==true)//判断是否为空{return false;} cout<data<LinkNode*p=front;front=front->link;//删除以执行的命令，即对头修改delete p;//释放原结点return true;};void main()//主函数 { LinkedQueue q;//定义类对象char flag='Y';//标志是否输入了命令const int max=30;//一次获取输入命令的最大个数while(flag=='Y')//循环{ int i=0;char str[max];//定义存储屏幕输入的命令的数组gets(str);//获取屏幕输入的命令while(str[i]!=''){q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中i++;}for(int j=0;j<=i;j++){if(q.IsEmpty()==true)//判断是否为空，为空则说明没有可执行的命令{cout<cin>>flag;continue;//为空跳出for循环为下次输入命令做好准备}q.carry_out();//调用执行命令的函数，将命令打印并删除}三、程序调试过程中所出现的错误无。

数据结构实验报告回文判断班级：学号：学生姓名：指导教师：时间：2015年5月5日1．实验目的：熟悉栈和队列的各项操作，区别栈和队列的操作原理。

2．实验内容：利用栈的操作完成读入的一个以@结尾的字符序列是否是回文序列的判断.回文序列即正读与反读都一样的字符序列;例如:123&321@是;123&4321@、123&312@不是算法思想：从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为@停止输入，因为要满足特定的要求：序列1&序列2，故设置夜歌标记量falg=1,判断输入的元素个数是否为奇数个，若为偶数个则令flag=0，若为奇数个继续判断栈的中间元素是否为&,若不是则令flag=0，若是，将栈和队列中的元素依次出列，判断是否相等，若不相等则令flag=0,最后将flag的值返回给主函数，若flag被修改为0说明不是回文序列，否则反之！！判断回文序列的流程图：算法实现：（1）void InitStack(SeqStack *s)：栈初始化模块，即初始化一个空栈，随后对该空栈进行数据的写入操作；（2）int push(SeqStack *s,char ch)：入栈操作，即给空栈中写入数据；（3）int pop(SeqStack *s,char *x)：出栈操作，即将栈中的数据输出，由于栈的操作是先进后出，因此，出栈的数据是原先输入数据的逆序；（4）void InitQuene(LinkQ *q)：队列初始化，即初始化一个空队列，最后对该空队列进行数据的写入操作；（5）int enter(LinkQ *q,char ch)：入队操作，即给空队列中写入数据；（6）int deleteq(LinkQ *q,char *c)：出队操作，即将队列中的数据输出，由于队列的操作是先进先出，因此，出队的数据室原先输入数据的正序；（7）int huiwen(SeqStack s,LinkQ q)：输入序列并判断所输入的序列是否是回文序列；（8）void main()：主函数，用于调用前面的模块，并输出最终的判断结果。

数据结构回文序列判断实验报告1.实验目的本实验旨在通过使用数据结构中的栈来判断一个给定的序列是否为回文序列。

2.实验原理回文序列是指正读和反读都相同的序列。

在本实验中，我们使用栈来实现回文序列的判断。

具体原理如下：-将给定的序列逐个字符入栈，直到遇到序列结束符（如空格或结束符号）。

-之后，将栈中的字符逐个出栈，并与序列的对应字符比较。

-如果出栈的字符与序列的对应字符不相同，则该序列不是回文序列；如果全部对应字符相同，则该序列是回文序列。

-需要注意的是，如果序列为奇数个字符，那么中间的字符可以不进行比较。

3.实验步骤本实验的具体步骤如下：1)初始化一个空栈。

2)读入一个字符，并将其入栈，直到遇到序列结束符。

3)读入序列的每一个字符，并将其与栈顶字符进行比较。

4)如果比较结果不相同，则该序列不是回文序列；如果比较结果相同，则继续比较下一个字符。

5)如果栈为空且所有字符都比较完毕，则该序列是回文序列；否则，该序列不是回文序列。

4.实验结果本实验使用了多组样例数据进行测试，以下是部分实验结果：- 输入序列："aba"，输出：是回文序列。

- 输入序列："abcba"，输出：是回文序列。

- 输入序列："abcca"，输出：不是回文序列。

- 输入序列："abcdcba"，输出：是回文序列。

5.实验分析通过对实验结果的分析，可以得出以下结论：-本实验的算法能够正确判断给定序列是否为回文序列。

-由于使用了栈来辅助判断，算法的时间复杂度为O(n)，其中n为序列的长度。

6.实验总结本实验通过使用数据结构中的栈，成功判断了一个给定序列是否为回文序列。

通过实验过程，我们深入理解了栈的应用和回文序列的判断原理，并熟悉了实际编程的过程。

同时，我们也认识到了栈在解决一些问题时的便捷性和高效性。

在今后的学习和工作中，我们将更加熟练地运用栈来解决问题。