下载文档原格式
//头文件//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 分析通过以上实验结果可以发现，我们设计的回文序列判断算法在大多数情况下都能够正确判断出序列是否为回文序列。
