网站地图
【www.arisingsemi.com--IT认证】
回文结构数据结构实验报告
回文判断
班 级
：
学号
：
学生姓名
：
指导教师
：
时间
：
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()：主函数，用于调用前面的模块，并输出最终的判断结果。
3．实验感想与体会
通过本次的上机，对栈的各项基本操作都有了更好的掌握，同时明白了一些小的细节问题可能会影响到整个程序的正确的运行，本次的实验我通过了运用栈和队列，可以说对队列的一些基本的操作也得以了巩固和提高。更加体会到，自己写程序上机操作的重要性，它要比课本上学的要多得多。
4．附录（源代码及运行图）
#include
#include
#define MAX 100
typedef struct//栈结构体
{
char e[MAX];
int top;
}SeqStack;
typedef struct NODE//队列结构体
{
char d;
struct NODE *next;
}LinkQN;
typedef struct//封装头指针为指针
{
LinkQN *front;
LinkQN *rear;
}LinkQ;
void InitStack(SeqStack *s)//初始化顺序栈
{
s->top=-1;
}
int push(SeqStack *s,char ch)//入栈
{
if(s->top==MAX-1)
return(0);
s->top++;
s->e[s->top]=ch;
return(1);
}
int pop(SeqStack *s,char *x)//出栈
{
if(s->top==-1)
return(0);
else
{
*x=s->e[s->top];
s->top--;
return(1);
}
}
void InitQuene(LinkQ *q)//链队列初始化
{
q->front=(LinkQN *)malloc(sizeof(LinkQN));
if(。q->front)
{
printf("分配空间失败。");
}
q->rear=q->front;
q->front->next=NULL;
}
int enter(LinkQ *q,char ch)//入队
{
LinkQN *np;
np=(LinkQN *)malloc(sizeof(LinkQN));
if(。
np)
return(0);
np->d=ch;
np->next=NULL;
q->rear->next=np;
q->rear=np;
return(1);
}
int deleteq(LinkQ *q,char *c)//出队
{ LinkQN *p;
if(q->front==q->rear)
return(0);
p=q->front->next;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
*c=p->d;
free(p);
return(0);
}
int huiwen(SeqStack s,LinkQ q)//回文判断
{
int flag=1,m=0,t=1;
int i;
char ch1,ch2,ch;
InitStack(&s);
InitQuene(&q);
printf("请输入字符序列当输入字符@时输入结束:\n");
while(ch。
="@")
{
ch=getchar();
if(ch。="@")
{
printf("%c",ch);
push(&s,ch);
enter(&q,ch);
m++;
}
}
printf("\n输入完成。
\n");
getchar();
if(m%2)
{
if(s.e[m/2]=="&")
{
for(i=1;i