数据结构回文报告
- 格式：doc
- 大小：48.00 KB
- 文档页数：7
《
数据结构》实验报告
实验名称：回文问题的实现
姓 名：
学 号：
专业班号：
实验日期： 2
指导教师：
第 页（共 页）
问题描述：
编程序判断一个字符序列是否是回文。要求程序从键盘输入一个字符串，长度小
于等于80，用于判断回文的字符串中不包括字符串的结束标记。
基本要求：
（1） 要求字符序列个数n由用户随意确定，且有0
（3） 字符序列由用户从键盘输入。
测试数据：
（1） abcdcba
（2） abcdefghig
算法思想：
把字符串中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队
列的数据元素和腿退栈的数据元素是否相等，若相等则是回文，否则不是。
模块划分：
（1） void Palindrome(char str[],int n)，判断字符序列是否回文函数。
（2） void EnterStr(char str[],int *n)，键盘输入字符序列函数。
（3） void main(void)，主函数。
上述三个函数存放在Palindrome.c中。
数据结构：
使用顺序堆栈和顺序循环队列辅助字符序列的回文判断。DataType为char型。
源程序：
/*SeqCQu.h*/
typedef struct
{
DataType queue[MaxQueueSize];
int rear;
int front;
}SeqCQueue;
void QueueInitiate(SeqCQueue *Q)
{
Q->rear=0;
Q->front=0;
}
int QueueNotEmpty(SeqCQueue Q)
{
if(Q.front==Q.rear) return 0;
else return 1;
}
第 页（共 页）
int QueueAppend(SeqCQueue *Q,DataType x)
{
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)
{
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)
{
if(Q.front==Q.rear)
{
printf("循环队列已空无数据元素可取!\n");
return 0;
}
else
{
*d=Q.queue[Q.front];
return 1;
}
}
第 页（共 页）
/*SeqStk.h*/
typedef struct
{
DataType stack[MaxStackSize];
int top;
}SeqStack;
void StackInitiate(SeqStack *S)
{
S->top=0;
}
int StackNotEmpty(SeqStack S)
{
if(S.top<= 0) return 0;
else return 1;
}
int StackPush(SeqStack *S,DataType x)
{
if(S->top>=MaxStackSize)
{
printf("堆栈已满无法插入!\n");
return 0;
}
else
{
S->stack[S->top]=x;
S->top ++;
return 1;
}
}
int StackPop(SeqStack *S,DataType *d)
{
if(S->top<=0)
{
printf("堆栈以空无数据元素出栈!\n");
return 0;
}
else
第 页（共 页）
{
S->top--;
*d=S->stack[S->top];return 1;
}
}
int StackTop(SeqStack S,DataType *d)
{
if(S.top<=0)
{
printf("堆栈已空!\n");
return 0;
}
else
{
*d=S.stack[S.top-1];
return 1;
}
}
/*Palindrome.c*/
#include
#include
#define MaxStackSize 80
#define MaxQueueSize 80
typedef char DataType;
#include "SeqStk.h"
#include "SeqCQu.h"
void Palindrome(char str[],int n)
{
SeqStack myStack;
SeqCQueue myQueue;
char x,y;
int i;
StackInitiate(&myStack);
QueueInitiate(&myQueue);
for(i=0;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;
}
}
测试情况
：
第 页（共 页）
结果分析：
程序运行正常，满足要求，实验成功。
