实验题目
回文判断的算法一、需求分析
1．程序的功能:
实现对字符序列是否是一个回文序列的判断2．输入输出的要求:
从键盘读入一组字符序列，判断是否是回文，并将结果显示在屏幕上
3．测试数据:
回文字符序列输入：
非回文字符序列输入：
二、概要设计
1．本程序所用的抽象数据类型的定义:
typedef struct{
char item[STACKSIZE];
int top;
}SqStack;
typedef struct QNode{
char data;
struct QNode *next;
}LQNode, *PQNode;
typedef struct{
PQNode front,rear;
} LinkQueue;
2．主程序的流程及各程序模块之间的层次关系。（1）int InitStack(SqStack *S)：栈初始化模块，即初始化一个空栈，随后对该空栈进行数据的写入操作；（2）int Push(SqStack *s, char data)：入栈操作，即给空栈中写入数据，数据长度有宏定义给出；
（3）int Pop(SqStack *s, char *data)：出栈操作，即将栈中的数据输出，由于栈的操作是先进后出，因此，出栈的数据是原先输入数据的逆序；
（4）int InitQueue(LinkQueue *q)：队列初始化，即初始化一个空队列，最后对该空队列进行数据的写入操作；（5）int EnQueue(LinkQueue *q, char item)：入队操作，即给空队列中写入数据，数据长度一样有宏定义给出；
（6）int DeQueue(LinkQueue *q, char *item)：出队操作，即将队列中的数据输出，由于队列的操作是先进先出，因此，出队的数据室原先输入数据的正序；
（7）int main()：主函数，用于调用前面的模块，进行出队数据与出栈数据的比较，判断输入的序列是否是回文序列。
模块之间关系及其相互调用的图示：
三、详细设计
1．采用c语言定义相关的数据类型
整形，字符型，指针类型，聚合类型，自定义类型2．写出各模块的伪码算法:参照源程序
（1）int InitStack(SqStack *S)
（2）int Push(SqStack *s, char data)
（3）int Pop(SqStack *s, char *data)
（4）int InitQueue(LinkQueue *q)
（5）int EnQueue(LinkQueue *q, char item)
（6）int DeQueue(LinkQueue *q, char *item)
四、调试分析
1．调试中遇到的问题及对问题的解决方法: 问题：程序出现未知错误。
方法：在感觉容易出错的地方或者是已经出错的地方前面打断点，进一步调试。
2．算法的时间复杂度和空间复杂度。
时间复杂度：T（n） = O（n）
五、使用说明及测试结果
回文字符输入：
非回文字符输入：
六、源程序（带注释）
#include
#include
#include
#define STACKSIZE 100
typedef struct{
char item[STACKSIZE]; int top;
}SqStack;/*顺序栈的定义*/
typedef struct QNode{
char data;
struct QNode *next; }LQNode, *PQNode;
typedef struct{
PQNode front,rear;
} LinkQueue;/*链队列的定义*/
int InitStack(SqStack *S);/*初始化顺序栈*/
int StackEmpty(SqStack S);/*判断是否为空栈*/
int Push(SqStack *s, char data);/*入栈*/
int Pop(SqStack *s, char *data);/*出栈*/
int InitQueue(LinkQueue *q);/*初始化链队列*/
int QueueEmpty(LinkQueue q);/*判断是否为空队列*/ int EnQueue(LinkQueue *q, char item);/*入队*/
int DeQueue(LinkQueue *q, char *item);/*出队*/ int TraverseQueue(LinkQueue q);/*遍历*/
int InitStack(SqStack *S) /*初始化顺序栈*/
{
S->top = -1;
return 1;
}
int StackEmpty(SqStack S)/*判断是否为空栈*/
{
if(S.top == -1) return 1;
else return 0;
}
int Push(SqStack *s, char data)/*入栈*/
{
if(s->top == STACKSIZE - 1)
{
printf("\n栈已满，不能完成入栈操作！"); return 0;
}
s->top++;
s->item[s->top] = data;
return 1;
}
int Pop(SqStack *s, char *data)/*出栈*/
{
if (s->top == -1)
{
printf("\n堆栈已空，不能完成出栈操作！");
return 0;
}
*data = s->item[s->top];
s->top--;
return 1;
}
int InitQueue(LinkQueue *q)/*初始化链队列*/
{
q->front = q->rear = (PQNode)malloc(sizeof(LQNode));
if(!q->front)
{
printf("\n初始化队列失败！");
return 0;
}
q->front->next = NULL;
return 1;
}
int QueueEmpty(LinkQueue q)/*判断是否为空队列*/ {
if (q.front == q.rear)
{
printf("\n队列为空！");
return 1;
}
else return 0;
}
int EnQueue(LinkQueue *q, char item)/*入队*/ {
PQNode p;
p = (PQNode)malloc(sizeof(LQNode));
if(!p)
{
printf("\n内存分配失败");
return 0;
}
p->data = item;
p->next = NULL;
q->rear->next = p;
q->rear = p;
return 1;
}
int DeQueue(LinkQueue *q, char *item)/*出队*/
{
PQNode p;
if(q->front == q->rear)
{
printf("\n队列已空，不能出队");
return 0;
}
p = q->front->next;
*item = p->data;
q->front->next = p->next;
free(p);
if(q->rear == p) /*若删除的为最后一个结点，移动队尾指针*/
q->front = q->rear;
return 1;
}
int TraverseQueue(LinkQueue q)/*遍历*/ {
PQNode pos;
if(q.front == q.rear)
{
printf("\n队列为空！");
return 0;
}
pos = q.front->next;
printf("\nHere is the string:"); while(pos != NULL)
{
printf("%c", pos->data);
pos = pos->next;
}
printf("\n");
return 1;
}
int main()
{
int i,len,count1 = 0;
char str1[100],ch,ch1;
LinkQueue lq1,lq2;
SqStack sq;
printf("请输入字符:");
scanf("%s", &str1);
len = strlen(str1);
InitQueue(&lq1);
InitQueue(&lq2);
InitStack(&sq);
for(i=0;i { EnQueue(&lq1,str1[i]); } TraverseQueue(lq1); for(i=0;i { DeQueue(&lq1,&ch); Push(&sq,ch); EnQueue(&lq1,ch); } for(i=0;i { Pop(&sq,&ch); EnQueue(&lq2,ch); } TraverseQueue(lq2); for(i=0;i { DeQueue(&lq1,&ch); DeQueue(&lq2,&ch1); if(ch1 != ch) count1++; } if(count1 == 0) { printf("\n该字符串为回文"); } else printf("\n该字符串不是回文"); return 0; }
相关主题
文本预览