堆栈方式实现字符回文数判断(可运行)
- 格式:wps
- 大小:20.00 KB
- 文档页数:3
//头文件//code.h#define TRUE 1#define FALSE 0#define ok 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0typedef int Status;//主函数//test.cpp#include"code.h"#include<stdlib.h>#include<process.h>#include<stdio.h>#include<String.h>#define STACK_SIZE 100 /* 栈初始向量大小 */ #define STACKINCREMENT 10//*************队列的操作函数*******************typedef char QElemType;typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct {QueuePtr front; //队首QueuePtr rear; //队尾}LinkQueue;Status InitQueue(LinkQueue &Q){ //构造空队列Q.front=Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;return ok;}Status DestoryQueue(LinkQueue &Q){ //销毁队列while(Q.front ){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}return ok;}Status EnQueue (LinkQueue &Q,QElemType e){ //在队尾插入元素QNode *p;p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit (OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return ok;}Status DeQueue(LinkQueue &Q,QElemType&e){ //删除队首元素,并返回其值if(Q.front==Q.rear) return ERROR;QNode *p;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;free(p);return ok;}//**************************栈的操作函数**************************typedef char ElemType;typedef struct SqStack{ElemType *base; /* 栈不存在时值为NULL */ElemType *top; /* 栈顶指针 */ int stacksize ; // 当前已分配空间,以元素为单位}SqStack ;Status InitStack(SqStack &s){ /*构造空栈s*/ElemType *a=(ElemType *)malloc(10*sizeof(ElemType));realloc(a,STACK_SIZE *sizeof(ElemType));s.base=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));if (! s.base) return ERROR; //存储分配失败s.top=s.base ; /* 栈空时栈顶和栈底指针相同 */ s.stacksize=STACK_SIZE;return ok ;}Status GetTop(SqStack S,ElemType &e){ //返回栈顶元素if(S.top==S.base) return ERROR;e=*(S.top-1);return ok;}Status push(SqStack &S,ElemType e){ //进栈if (S.top-S.base>=S.stacksize) return ERROR;*S.top=e;S.top++ ; /* 栈顶指针加1,e成为新的栈顶 */return ok;}Status pop( SqStack &S, ElemType &e ){ //出栈if ( S.top== S.base ) return ERROR ; /* 栈空,返回失败标志 */ S.top-- ;e=*S.top ;return ok ;}int stackLength( SqStack S){ //栈的长度return S.top-S.base ;}Status StackEmpty( SqStack &S){ //判断栈是否为空if ( S.top== S.base ) return TRUE;else return FALSE;}//**************************比较函数********************int compare(){SqStack T;LinkQueue R;InitStack(T);InitQueue(R);char ch;char a,b;printf("请输入要判断的字符串以@作为结束符\n");while((ch=getchar())!='@'){push(T,ch); //进栈EnQueue(R,ch); //入队}while(T.top!=T.base){pop(T,a); //出栈DeQueue(R,b); //出队if(a!=b) return ERROR; //比较字符是否相同else return ok;}}//*******************主函数***************************void main(){int r=compare();if(r==1)printf("%s","此为回文字符序列\n");elseprintf("%s","此不为回文字符序列\n");}。
数据结构回文序列判断实验报告1.实验目的本实验旨在通过使用数据结构中的栈来判断一个给定的序列是否为回文序列。
2.实验原理回文序列是指正读和反读都相同的序列。
在本实验中,我们使用栈来实现回文序列的判断。
具体原理如下:-将给定的序列逐个字符入栈,直到遇到序列结束符(如空格或结束符号)。
-之后,将栈中的字符逐个出栈,并与序列的对应字符比较。
-如果出栈的字符与序列的对应字符不相同,则该序列不是回文序列;如果全部对应字符相同,则该序列是回文序列。
-需要注意的是,如果序列为奇数个字符,那么中间的字符可以不进行比较。
3.实验步骤本实验的具体步骤如下:1)初始化一个空栈。
2)读入一个字符,并将其入栈,直到遇到序列结束符。
3)读入序列的每一个字符,并将其与栈顶字符进行比较。
4)如果比较结果不相同,则该序列不是回文序列;如果比较结果相同,则继续比较下一个字符。
5)如果栈为空且所有字符都比较完毕,则该序列是回文序列;否则,该序列不是回文序列。
4.实验结果本实验使用了多组样例数据进行测试,以下是部分实验结果:- 输入序列:"aba",输出:是回文序列。
- 输入序列:"abcba",输出:是回文序列。
- 输入序列:"abcca",输出:不是回文序列。
- 输入序列:"abcdcba",输出:是回文序列。
5.实验分析通过对实验结果的分析,可以得出以下结论:-本实验的算法能够正确判断给定序列是否为回文序列。
-由于使用了栈来辅助判断,算法的时间复杂度为O(n),其中n为序列的长度。
6.实验总结本实验通过使用数据结构中的栈,成功判断了一个给定序列是否为回文序列。
通过实验过程,我们深入理解了栈的应用和回文序列的判断原理,并熟悉了实际编程的过程。
同时,我们也认识到了栈在解决一些问题时的便捷性和高效性。
在今后的学习和工作中,我们将更加熟练地运用栈来解决问题。
一、实验目的1. 理解堆栈(栈)的基本概念和操作。
2. 掌握利用堆栈判断字符串是否为回文的方法。
3. 提高编程能力,巩固数据结构知识。
二、实验环境1. 操作系统:Windows 102. 编程语言:C++3. 开发工具:Visual Studio 2019三、实验原理回文是一种正读和反读都相同的字符串。
例如,"madam"、"racecar"等都是回文。
堆栈是一种先进后出的数据结构,利用堆栈可以方便地实现字符串的逆序。
因此,可以通过以下步骤判断一个字符串是否为回文:1. 将字符串的每个字符依次入栈。
2. 将字符串的每个字符依次出栈,并与原字符串进行对比。
3. 如果所有字符都能一一对应,则字符串为回文;否则,不是回文。
四、实验步骤1. 创建一个字符串输入函数,用于从用户处获取字符串。
2. 创建一个堆栈类,包括入栈、出栈、判空、判满等基本操作。
3. 创建一个判断回文的函数,实现上述实验原理。
4. 在主函数中调用输入函数、堆栈类和判断回文函数,输出结果。
五、实验代码```cpp#include <iostream>#include <string>using namespace std;// 堆栈类template <typename T>class Stack {private:T data; // 动态数组int top; // 栈顶指针int maxSize; // 栈的最大容量public:Stack(int size) : maxSize(size), top(-1) { data = new T[maxSize];}~Stack() {delete[] data;}// 入栈操作bool push(T element) {if (top == maxSize - 1) {return false; // 栈满}data[++top] = element;return true;}// 出栈操作bool pop(T &element) {if (top == -1) {return false; // 栈空 }element = data[top--];return true;}// 判空操作bool isEmpty() {return top == -1;}// 判满操作bool isFull() {return top == maxSize - 1; }};// 判断回文函数bool isPalindrome(string str) {Stack<char> stack;int len = str.length();// 将字符串的每个字符入栈for (int i = 0; i < len; i++) {stack.push(str[i]);}// 将字符串的每个字符出栈,并与原字符串进行对比 for (int i = 0; i < len; i++) {char c;if (stack.pop(c)) {if (c != str[i]) {return false; // 字符串不是回文}} else {return false; // 栈空,字符串不是回文 }}return true; // 字符串是回文}int main() {string str;cout << "请输入一个字符串:";getline(cin, str);if (isPalindrome(str)) {cout << "该字符串是回文。
以下是一个使用C++栈实现回文数的示例程序:c复制代码#include<iostream>#include<stack>using namespace std;bool isPalindrome(int n) {stack<int> s;int temp = n;while (temp != 0) {s.push(temp % 10);temp /= 10;}while (!s.empty()) {if (s.top() != n % 10) {return false;}s.pop();n /= 10;}return true;}int main() {int n;cout << "Enter a number: ";cin >> n;if (isPalindrome(n)) {cout << n << " is a palindrome." << endl;} else {cout << n << " is not a palindrome." << endl;}return0;}在这个程序中,我们首先定义了一个名为isPalindrome的函数,该函数接受一个整数作为参数,并返回一个布尔值,表示该整数是否为回文数。
我们使用一个名为s的stack对象来存储整数的各个数字,从个位开始依次入栈。
然后,我们使用一个循环来将整数从个位开始与栈顶元素进行比较,如果发现不相等,则返回false。
如果所有数字都相等,则返回true。
在主函数中,我们首先要求用户输入一个整数。
然后,我们调用isPalindrome函数来检查该整数是否为回文数,并输出相应的结果。
栈的应⽤_回⽂字符的判定stack.h#ifndef stack_h__#define stack_h__#include <stdio.h>#include <malloc.h>#include <stdlib.h>enum boolean{FALSE, TRUE};typedef enum boolean BOOL;typedef int ElementType;typedef struct stack_def{ElementType* data;int top;int sz;int length;}stack;void initStack(stack* s, int sz);BOOL isEmpty(stack s);BOOL isFull(stack s);BOOL Pop(stack* s);BOOL Push(stack* s, ElementType e);ElementType getTop(stack s);void destoryStack(stack* s);#endif // stack_h__stack.c#include "stack.h"void initStack(stack* s, int sz){if (sz < 0){puts("sz < 0");}else{s->top = -1;s->sz = sz;s->length = 0;s->data = (ElementType*)malloc(sizeof(ElementType)*s->sz);if (s->data == NULL)puts("s->data == NULL");}}BOOL isEmpty(stack s){return(BOOL)(s.length==0);}BOOL isFull(stack s){return(BOOL)(s.length==s.sz);}BOOL Pop(stack* s){ // 出栈,并不返回此元素值if (isEmpty(*s)){return FALSE;}s->top--;s->length--;}BOOL Push(stack* s, ElementType e){ // ⼊栈if (isFull(*s)){return FALSE;}s->data[++s->top] = e;s->length++;return TRUE;}ElementType getTop(stack s){if (isEmpty(s)){puts("stack s is empty.");exit(1);}return s.data[s.top];}void destoryStack(stack* s){free(s->data);}main.c#include "stack.h"#include <string.h>int isSpecalStr(char *str, int str_len){ //判断是否为回⽂字符串 stack s1, s2, tmp;int i, ret = 1;ElementType e;initStack(&s1, str_len/2);initStack(&s2, str_len/2);initStack(&tmp, str_len/2);for (i=0; i<str_len/2; i++){Push(&s1, str[i]);Push(&tmp, str[i+str_len/2]);}while (!isEmpty(tmp)){Push(&s2, getTop(tmp));Pop(&tmp);}// end whilewhile (!isEmpty(s1) && !isEmpty(s2)){if (getTop(s1) != getTop(s2)){ret = 0; break;}Pop(&s1); Pop(&s2);}// end whiledestoryStack(&s1);destoryStack(&s2);destoryStack(&tmp);return ret;}int main(){char str[50];stack s;int len ;initStack(&s, 50);printf("输⼊⼀个字符串:");gets(str);len = strlen(str);if (isSpecalStr(str, len))puts("YES");elseputs("NO");return 0;}运⾏结果:。
一、实验目的1. 理解栈的基本原理和操作。
2. 掌握使用栈判断字符串是否为回文的算法。
3. 分析算法的效率,并优化算法。
二、实验背景回文是一种特殊的字符串,它从前往后读和从后往前读都是相同的。
例如,“madam”、“racecar”等都是回文。
判断一个字符串是否为回文是一个常见的问题,而使用栈来解决这个问题是一种有效的方法。
三、实验内容1. 设计一个栈类,实现栈的基本操作:初始化、入栈、出栈、判断栈是否为空。
2. 编写一个函数,使用栈来判断一个字符串是否为回文。
3. 分析算法的效率,并进行优化。
四、实验步骤1. 定义栈类```pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()return Nonedef peek(self):if not self.is_empty():return self.items[-1]return None```2. 编写判断回文函数```pythondef is_palindrome(s):stack = Stack()for char in s:stack.push(char)result = Truewhile not stack.is_empty():if stack.pop() != s[stack.size() - 1 - stack.index()]:result = Falsebreakreturn result```3. 分析算法效率在这个算法中,我们需要遍历整个字符串一次来入栈,然后再遍历一次出栈。
因此,时间复杂度为O(n),其中n为字符串的长度。
数据结构C语言版判断回文数实验报告实验目的:1. 了解回文数的定义和判断方法2. 掌握C语言中字符串的处理方法3. 学习如何使用栈来判断字符串是否为回文数实验原理:回文数是一个正整数,它的各位数字倒过来排列后仍然是同一个数。
比如121、12321就是回文数,而123、56789就不是回文数。
判断一个字符串是否为回文数,可以将字符串中的每一个字符逐个压入栈中,然后再依次将栈中的字符弹出,与原字符串中的字符逐个比较。
实验步骤:1. 定义一个栈结构体,其中包含一个整型数组和一个顶部指针变量。
顶部指针变量用于指向栈顶的位置。
```c#define MAXSIZE 100 // 定义栈中最大元素数量typedef struct {int data[MAXSIZE]; // 栈中元素数据int top; // 栈顶指针} Stack;```2. 定义一个函数用于判断字符串是否为回文数。
函数接收一个字符串指针作为参数。
首先计算字符串的长度,然后将字符串中的每一个字符压入栈中。
接着依次将栈中的字符弹出,与原字符串中的字符逐个比较。
如果两者不同,则说明该字符串不是回文数,函数返回0并退出。
如果所有字符都比较完成后没有发现不同,说明该字符串是回文数,函数返回1并退出。
// 将字符串中的每一个字符压入栈中for (int i = 0; i < len; i++) {s.data[++s.top] = str[i];}return 1;}```3. 在主函数中,首先要输入一个字符串,然后调用is_palindrome函数进行判断,最后输出判断结果。
实验结果:测试数据:输入:"12321"请输入一个字符串:12321该字符串是回文数"abcde""aabbabbaa"分析:实验结果验证了判断回文数的方法和字符串操作的正确性,同时掌握了使用栈来判断字符串是否为回文数的方法,有助于更好地理解栈的概念和应用。
数据结构回文序列判断实验报告数据结构回文序列判断实验报告1. 实验目的本实验旨在探究如何使用数据结构来判断一个序列是否为回文序列,并通过实验验证算法的正确性和效率。
2. 实验背景回文序列是指正向和反向读取都相同的序列。
判断一个序列是否为回文序列可以在很多场景下使用,比如判断一个字符串是否为回文串,或者判断一个数字列表是否为回文数字。
回文序列判断问题是数据结构中非常经典的问题之一,能够有效地练习和运用数据结构的知识。
在本实验中,我们将使用栈来实现回文序列的判断。
3. 实验原理与方法3.1 栈的原理栈是一种数据结构,具有先进后出(Last in, First out,LIFO)的特点。
栈的操作主要有入栈和出栈两个动作,入栈将元素放置在栈顶,出栈则将栈顶元素弹出。
3.2 回文序列判断算法回文序列判断算法的基本思路是将原序列中的元素逐个入栈,然后逐个出栈与原序列中的元素进行比较,若相同则继续比较下一个元素,否则返回不是回文序列。
1. 将原序列中的元素逐个入栈。
2. 逐一出栈栈顶元素,并与原序列中的元素逐个比较。
3. 若任一对应位置的元素不相同,则返回不是回文序列。
4. 若所有元素都相同,则返回是回文序列。
3.3 实验步骤1. 创建一个空栈。
2. 将原序列中的元素逐个入栈,直到全部入栈完成。
3. 出栈栈顶元素,并与原序列中的元素逐个比较。
4. 若比较结果不相同,则返回不是回文序列。
5. 若比较结果都相同,重复步骤3和步骤4,直到栈为空。
6. 若全部比较结果都相同,则返回是回文序列。
4. 实验结果与分析为了验证回文序列的判断算法,我们选择了几个不同长度的序列进行实验,并记录下了实验结果。
4.1 实验结果案例1:序列:abcba实验结果:是回文序列案例2:序列:12321实验结果:是回文序列案例3:序列:abccbaa实验结果:不是回文序列4.2 分析通过以上实验结果可以发现,我们设计的回文序列判断算法在大多数情况下都能够正确判断出序列是否为回文序列。
利⽤栈和队列判断字符是否是回⽂(C语⾔)// File Name: palindrome.h//// Destination:利⽤栈和队列判断字符串是否是回⽂//#ifndef PALINDROME#define PALINDROME#include <stdio.h>// 链式队列结构的定义typedef char ElemType;typedef struct Node{char data; // 元素数据struct Node *next;// 链式队列中结点元素的指针}QNode,*QueuePtr;typedef struct{QueuePtr front;// 队列头指针QueuePtr rear;// 队列尾指针}LinkQueue;// 栈结构的定义typedef struct Stack{ElemType *base;ElemType *top;int stacksize;}SqStack;// 链式队列的基本操作bool InitQueue(LinkQueue *Q);bool EnQueue(LinkQueue *Q, ElemType e);bool DeQueue(LinkQueue *Q, ElemType *e);// 栈的基本操作bool InitStack(SqStack *S);bool Push(SqStack *S, ElemType e);bool Pop(SqStack *S, ElemType *e);#endif// File Name: palindrome.cpp//// Destination:利⽤栈和队列判断字符串是否是回⽂#include <stdlib.h>#include <malloc.h>#include "palindrome.h"const int STACK_INIT_SIZE = 100; // 初始分配的长度const int STACKINCREMENT = 10; // 分配内存的增量//操作⽬的:初始化队列//初始条件:⽆//操作结果:构造⼀个空的队列//函数参数://LinkQueue *Q 待初始化的队列//返回值:// bool 操作是否成功------------------------------------------------------------*/bool InitQueue(LinkQueue *Q){Q->front = Q->rear = (QueuePtr)malloc(sizeof (QNode)); if (!Q->front){exit(0);}Q->front->next = NULL;return true;}//操作⽬的:在队列末尾插⼊元素e//初始条件:队列Q已存在//操作结果:插⼊元素e作为队列新的尾结点//函数参数://LinkQueue *Q 队列Q//ElemType e 待插⼊的数据元素//返回值://bool 操作是否成功bool EnQueue(LinkQueue *Q, ElemType e){QueuePtr p = (QueuePtr)malloc(sizeof(QNode));if (!p){exit(0);}p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;return true;}//操作⽬的:删除链式队列的头结点//初始条件:队列Q已存在//操作结果:删除链式队列的头结点//函数参数://LinkQueue *Q 队列Q//ElemType *e 待插⼊的数据元素//返回值://bool 操作是否成功bool DeQueue(LinkQueue *Q, ElemType *e){if (Q->front == Q->rear) //空队列{return false;}QueuePtr p = Q->front->next;//p指向头结点的下个位置 *e = p->data;Q->front->next = p->next;if (Q->rear == p){Q->rear = Q->front;}free(p);return true;}//操作⽬的:初始化栈//初始条件:⽆//操作结果:构造⼀个空的栈//函数参数:// SqStack *S 待初始化的栈//返回值:// bool 操作是否成功bool InitStack(SqStack *S){S->base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if (S->base == NULL){return false;}S->top = S->base;S->stacksize = STACK_INIT_SIZE;return true;}//操作⽬的:压栈——插⼊元素e为新的栈顶元素//初始条件:栈S已存在//操作结果:插⼊数据元素e作为新的栈顶//函数参数://SqStack *S 栈S//ElemType e 待插⼊的数据元素//返回值:// bool 操作是否成功bool Push(SqStack *S, ElemType e){if (S->top - S->base >= S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); if (!S->base){return false;}S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}*(S->top++) = e;return true;}//操作⽬的:弹栈——删除栈顶元素//初始条件:栈S已存在且⾮空//操作结果:删除S的栈顶元素,并⽤e返回其值//函数参数://SqStack *S 栈S//ElemType *e 被删除的数据元素值//返回值://bool 操作是否成功bool Pop(SqStack *S, ElemType *e){if (S->top == S->base)return false;*e = (*--S->top);return true;}// File Name: main.cpp//// Destination:利⽤栈和队列判断字符串是否是回⽂//------------------------------------------------------#include <stdio.h>#include <stdlib.h>#include "palindrome.h"int main (){//声明⼀个栈⼀个队列SqStack S;LinkQueue L;//初始化⼀个栈⼀个队列InitStack (&S);InitQueue (&L);char c[30];ElemType a,b;printf("请输⼊要判断的字符,以@结束(最多30个字符):"); scanf("%s",c);int i = 0;int flag1 = 0;int flag2 = 0;while (c[i] != '@'){Push(&S,c[i]); //⼊栈EnQueue(&L,c[i]);//⼊队列flag1++;i++;}while (!(S.top == S.base)){Pop(&S,&b);//出栈DeQueue(&L,&a);//出队列if (a==b){flag2++;}else{break;}}if (flag1 == flag2){printf("\n是回⽂!\n\n");}else{printf("\n不是回⽂!\n\n");}system("pause");return 0;}。
数据结构⽤栈和队列判断回⽂数12321,你是不是你,这样的东西叫回⽂,由于队列和栈的存储⽅式不同,栈是LIFO,last in first out ,盘⼦⼀个⼀个堆,堆完后从上⾯开始拿;队列是FIFO,first in first out, 就像现实的排队。
将数字存进这两种结构中,逐⼀取出,如果相同,那就是回⽂数。
StackAndQueqe.h#include<stdio.h>typedef char DataType;typedef struct Node *PNode;struct Node{DataType info;PNode link;};typedef struct LinkQueqe *PQueqe;struct LinkQueqe{PNode f;PNode b;};typedef struct LinkStack *PStack;struct LinkStack{PNode top;};PStack createStack();int isEmptyStack(PStack pstack);void pushStack(PStack pstack,DataType element);DataType popStack(PStack pstack);DataType topStack(PStack pstack);void printStack(PStack pstack);PQueqe createQueqe();int isEmptyQueqe(PQueqe pqueqe);void pushQueqe(PQueqe pqueqe,DataType element);DataType popQueqe(PQueqe pqueqe);DataType topQueqe(PQueqe pqueqe);void printQueqe(PQueqe pqueqe);StackAndQueqe.c#include "StackAndQueqe.h"PQueqe createQueqe(){PQueqe pqueqe = (PQueqe)malloc(sizeof(struct LinkQueqe));if(pqueqe == NULL) printf("create fail");pqueqe ->f = NULL;pqueqe ->b = NULL;return pqueqe;}int isEmptyQueqe(PQueqe pqueqe){return (pqueqe ->f == NULL);}void pushQueqe(PQueqe pqueqe,DataType element){PNode p = (PNode)malloc(sizeof(struct Node));if(p == NULL) printf("nothing push");p ->info = element;p ->link = NULL;if(pqueqe ->f == NULL){pqueqe->f = p;//printf(" f %5d\n",pqueqe->f->info);}else pqueqe ->b ->link = p;pqueqe ->b = p;// printf("b %d\n",pqueqe->b->info);}DataType popQueqe(PQueqe pqueqe){PNode p;DataType temp;if(isEmptyQueqe(pqueqe)) printf("queqe is empty");p = pqueqe ->f;temp = p->info;pqueqe ->f = p->link;free(p);return temp;}DataType topQueqe(PQueqe pqueqe){if(pqueqe->f == NULL){printf("nothing top");return NULL;}return pqueqe -> f->info ;}void printQueqe(PQueqe pqueqe){PNode p = pqueqe ->f;if( isEmptyQueqe(pqueqe)){printf("nothing print");}while(pqueqe->f!= NULL){printf("%3c",pqueqe->f->info);pqueqe ->f = pqueqe ->f ->link;}pqueqe ->f = p;//此处的f随着link的变化变化最后需要还原回去!}PStack createStack(){PStack pstack = (PStack)malloc(sizeof(struct LinkStack));if(pstack == NULL) printf("create fail");pstack ->top = NULL;return pstack;}int isEmptyStack(PStack pstack){return(pstack->top == NULL);}void pushStack(PStack pstack,DataType element){PNode p = (PNode)malloc(sizeof(struct Node));if(p == NULL) printf("push fail");p ->info = element;p ->link = pstack ->top;pstack ->top = p;}DataType popStack(PStack pstack){PNode p;DataType temp;if(pstack ->top == NULL) printf("nothing pop");p = pstack ->top;temp = p->info;pstack ->top = pstack->top->link;free(p);return temp;}DataType topStack(PStack pstack){if(pstack ->top == NULL){printf("nothing pop");return NULL;}return pstack->top->info;}void printStack(PStack pstack){PNode p= pstack ->top;if(pstack ->top == NULL){printf("nothing pop");}while(pstack->top != NULL){printf("%3c",pstack ->top ->info);pstack ->top = pstack ->top ->link;}pstack ->top = p;}#include "StackAndQueqe.h"int main(){int i;char s[100];int n=0;PQueqe pqueqe ;PStack pstack;printf("please input string to judge whether it is a palindrome(回⽂数):\n"); scanf("%c",&s[0]);while(s[n]!='\n'){scanf("%c",&s[++n]);}printf(" the length is %d: \n",n);printf(" the string is : ");for(i=0;i<n;i++){printf("%c",s[i]);}pqueqe = createQueqe();for(i=0;i<n;i++){//printf("\n%c",s[i]);pushQueqe(pqueqe,s[i]);}pstack = createStack();for(i=0;i<n;i++){pushStack(pstack,s[i]);}printf(" \nthe queqe is : ");printQueqe(pqueqe);printf(" \nthe stack is : ");printStack(pstack);printf(" \n");for(i=0;i<n/2;i++){if(popQueqe(pqueqe)!= popStack(pstack)){printf("is not HUIWEN!\n");break;}else {printf("it is HUIWEN!\n");break;}}return 0;}简单的话只需要取出的数切半对⽐就⾏了。
基于栈的回⽂字符序列判断描述回⽂序列是正反读均相同的字符序列,如“abba”和“abdba”均是回⽂,但是“good”不是回⽂。
请设计⼀个算法判定给定的字符序列是否为回⽂。
输⼊多组数据,每组数据有⼀⾏。
每⼀⾏为⼀个长度不定的字符序列A。
当A为“0”时,输⼊结束。
输出对于每组数据输出⼀⾏。
若字符序列A是回⽂序列,则输出“YES”,否则输出“NO”。
输⼊样例 1abbaabdbagood输出样例 1YESYESNO个⼈思路:⼊栈后出栈,将出栈字符串输⼊⼀个新的数组,⽐较两个字符串的长度,这个⽅法时空复杂度都挺⾼的,不推荐。
#include<iostream>#include<cstring>using namespace std;#define MAXSIZE 1000#define OK 1#define ERROR -1typedef struct {char *base;char *top;int stacksize;}SqStack;int InitStack(SqStack& S){S.base=new char[MAXSIZE];if(!S.base)return ERROR;S.top=S.base;S.stacksize=MAXSIZE;return OK;}int Push(SqStack& S,char e){if(S.top-S.base==S.stacksize)return ERROR;*S.top++=e;return OK;}int Pop(SqStack& S){if(S.top==S.base)return ERROR;S.top--;return OK;}char GetTop(SqStack& S){if(S.top!=S.base)return *(S.top-1);}int main(){while(1){SqStack S;InitStack(S);char s[1000];char t[1000];char e;cin>>s;if(s[0]=='0')return0;int n=strlen(s);int i;for(i=0;i<n;i++)Push(S,s[i]);for(i=0;i<n;i++){t[i]=GetTop(S);Pop(S);}t[i]='\0';if(!strcmp(t,s))cout<<"YES"<<endl;elsecout<<"NO"<<endl; }}。
用栈实现回文判断的算法回文是指正读和反读都一样的字符串,例如"level"、"radar"等。
回文判断是计算机科学中的一个经典问题,也是算法学习中常见的一个练习题。
本文将介绍如何使用栈来实现回文判断的算法。
我们需要明确栈的概念。
栈是一种特殊的数据结构,它的特点是后进先出(Last-In-First-Out,LIFO)。
在栈中,我们只能在栈的顶部进行插入和删除操作。
这就意味着最后一个插入的元素将是第一个被删除的元素。
回文判断的思路是将字符串的每个字符依次入栈,然后再依次出栈与字符串的字符进行比较。
如果每一次出栈的字符与字符串对应位置的字符相等,那么这个字符串就是回文;如果有任何一次出栈的字符与字符串对应位置的字符不相等,那么这个字符串就不是回文。
接下来,我们来实现这个算法。
首先,我们需要定义一个栈的数据结构,并实现栈的入栈和出栈操作。
这里我们可以使用数组来实现栈。
```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):return len(self.stack) == 0```接下来,我们可以定义一个函数来判断一个字符串是否是回文。
首先,我们需要将字符串的每个字符入栈,然后再依次出栈与字符串的字符进行比较。
如果比较过程中有任何一个字符不相等,那么这个字符串就不是回文;如果全部字符比较完成后都相等,那么这个字符串就是回文。
```pythondef is_palindrome(string):stack = Stack()for char in string:stack.push(char)for char in string:if char != stack.pop():return Falsereturn True```我们可以测试一下这个算法的正确性。
使⽤栈判断给定字符串是否是回⽂的算法使⽤栈判断给定字符串是否是回⽂的算法/*使⽤栈stack类的实现*/function stack() {this.dataStore = [];//保存栈内元素,初始化为⼀个空数组this.top = 0;//栈顶位置,初始化为0this.push = push;//⼊栈this.pop = pop;//出栈this.peek = peek;//查看栈顶元素this.clear = clear;//清空栈this.length = length;//栈内存放元素的个数}function push(element){this.dataStore[this.top++] = element;}function pop(){return this.dataStore[--this.top];}function peek(){return this.dataStore[this.top-1];}function clear(){this.top = 0;}function length(){return this.top;}/*使⽤栈判断给定字符串是否是回⽂的算法*/function isPalindrome(word){var s = new stack();for(var i = 0;i < word.length;i++){s.push(word[i]);}var rword = "";while(s.length() > 0){rword += s.pop();}if(word == rword){return true;}else{return false;}}var word1 = "racecar";if(isPalindrome(word1)){console.log(word1 + " is a palindrome")//racecar is a palindrome}。
用栈实现回文判断的算法回文是指正读和反读都相同的字符串或序列,如"level"、"madam"等。
判断一个字符串是否为回文是编程中常见的问题,本文将介绍如何利用栈来实现这一功能。
栈是一种特殊的线性数据结构,具有后进先出(Last-In-First-Out,LIFO)的特点。
栈可以通过压栈(push)和弹栈(pop)操作来实现数据的存储和访问。
以字符串为例,我们可以通过将字符串中的每个字符依次入栈,然后再依次出栈,得到一个与原字符串相反的字符串。
如果这两个字符串相等,那么原字符串就是回文。
具体实现时,我们可以使用一个辅助栈来完成入栈和出栈操作。
首先,将原字符串的每个字符依次入栈,然后依次出栈并拼接到一个新的字符串中。
最后,将新的字符串与原字符串进行比较,如果相等,则原字符串是回文。
下面是用栈实现回文判断的算法的详细步骤:1. 创建一个空栈和一个空字符串。
2. 遍历原字符串的每个字符:- 将当前字符入栈。
3. 弹栈并将弹出的字符拼接到新字符串中,直到栈为空。
4. 将新字符串与原字符串进行比较:- 如果相等,则原字符串是回文;- 如果不相等,则原字符串不是回文。
下面是用栈实现回文判断的算法的Python代码实现:```pythondef is_palindrome(s):stack = []new_s = ""for c in s:stack.append(c)while stack:new_s += stack.pop()return new_s == s# 测试print(is_palindrome("level")) # 输出 Trueprint(is_palindrome("hello")) # 输出 False```通过上述算法的实现,我们可以用栈来判断一个字符串是否为回文。
算法的时间复杂度为O(n),其中n是字符串的长度。