13软工转本1 钱剑滨 实验报告
利用队列和栈判断回文实验报告
信息工程 系 13软工转本1 日期 2016年03月20日 姓名 钱剑滨 学号 13131116 电话 [1**********]
一、 实验内容
编写关于栈和队列操作的C 语言程序，要求能判断输入字符串是否为回文（回文：正序和逆序一样）。
二、 实验步骤
1. 分析栈和队列的实现算法。
2. 编写程序，通过队列来实现字符串正序输出，通过栈来实现字符串逆序输出。
3. 运行程序，纠正错误，对预测结果进行验证。
三、 设计概要
1. 本实验包含了7个函数：
a) 主函数 main()
b) 接收字符串函数get_string ()
c) 初始化队列函数init_queue ()
d) 初始化栈函数 init_stack ()
e) 入队函数 enter_queue ()
f) 出队函数 out_queue()
g) 压栈函数 push ()
h) 出栈函数 pop()
i) 字符串比较函数contrast()
四、 程序设计
1. 函数前包含的头文件名、结点类型定义、全局变量和函数声明 #include
#include
#include
#define N 100 //输入字符串的最大长度
typedef struct SeqQuene //定义循环队列
{
char *pBase_queue;
int front;
int rear;
}SeqQueue;
typedef struct SeqStack //定义栈
{
char *pBase_stack;
int bottom;
int top;
}SeqStack;
/*函数声明*/
void get_string(char *string_get, int *qString_side); //接受字符串
void init_queue(SeqQueue *queue, int string_side); //初始化队列
void init_stack(SeqStack *stack, int string_side); //初始化栈
void enter_queue(SeqQueue *queue, char *string_get, int
string_side); //入队
void out_queue(SeqQueue *queue, char *string_queue, int
string_side); //出队
void push(SeqStack *stack, char *string_get, int string_side); //压栈
void pop(SeqStack *stack, char *string_stack, int string_side);//出栈
void contrast(char *string_stack, char *string_queue, int string_side);
//字符串比较
2. 主函数main()
void main()
{
SeqStack stack; //这里定义普通变量，下面再传地址 SeqQueue queue; //如果定义指针变量会报错 char *string_get, *string_queue, *string_stack;
//定义字符指针，分别存放接收字符串、顺序输出字符串、逆序
输出字符串
int string_side; //定义接收字符串的长度
string_get = (char *)malloc(sizeof (char) * N);
//给字符指针分配空间，必须在声明的函数内部
get_string(string_get, &string_side); //接受字符串
string_queue = (char *)malloc(sizeof (char) * (string_side + 1));
string_stack = (char *)malloc(sizeof (char) * (string_side + 1));
init_queue(&queue, string_side); //初始化队列
init_stack(&stack, string_side); //初始化栈
enter_queue(&queue, string_get, string_side);
out_queue(&queue, string_queue, string_side);
push(&stack, string_get, string_side);
pop(&stack, string_stack, string_side);
contrast(string_stack, string_queue, string_side);
}
3. 接收字符串函数get_string ()
void get_string(char *string_get, int *qString_side) //接收字符串
{
int string_side;
printf("请输入要判断的字符串\n");
scanf("%s", string_get);
string_side = *qString_side = strlen(string_get);
//判断字符串长度
printf("输入的字符串长度为%d\n", string_side);
}
4. 初始化队列函数init_queue ()
void init_queue(SeqQueue *queue, int string_side) //初始化队列
{
queue->pBase_queue = (char *)malloc(sizeof (char) *
(string_side + 1));
queue->front = 0;
queue->rear = 0;
}
5. 初始化栈函数init_stack ()
void init_stack(SeqStack *stack, int string_side) //初始化栈
{
stack->pBase_stack = (char *)malloc(sizeof (char) *
(string_side + 1));
stack->bottom = -1;
stack->top = -1;
}
6. 入队函数enter_queue ()
void enter_queue(SeqQueue *queue, char *string_get, int
string_side) //入队
{
int i = 0;
while((queue->rear+1) % (string_side + 1) != queue->front) //队列满时跳出循环
{
queue->pBase_queue[queue->rear] = string_get[i]; //依次在队列里添加字符
queue->rear = (queue->rear + 1) % (string_side + 1); //循环队列
i++;
}
}
7. 出队函数out_queue()
void out_queue(SeqQueue *queue, char *string_queue, int
string_side) //出队
{
int i = 0;
while(queue->rear != queue->front) //当队列空时跳出循环
{
string_queue[i] = queue->pBase_queue[queue->front]; //依次取出队列里字符
queue->front = (queue->front + 1) % (string_side + 1);
//循环队列
i++;
}
string_queue[i] = '\0'; //字符串结束
printf("顺序输出为：");
printf("%s\n",string_queue);
}
8. 压栈函数push ()
void push(SeqStack *stack, char *string_get, int string_side)
//压栈
{
int i = 0;
while(string_side--)
{
stack->top++; //top指针先后移一位
stack->pBase_stack[stack->top] = string_get[i];
//一次在栈里添加字符
i++;
}
}
9. 出栈函数 pop()
void pop(SeqStack *stack, char *string_stack, int string_side)
//出栈
{
int i = 0;
while(stack->top != stack->bottom) //栈空时跳出循环
{
string_stack[i] = stack->pBase_stack[stack->top];
//依次取出栈里字符
stack->top--; //top指针前移一位
i++;
}
string_stack[i] = '\0'; //字符串结束
printf("逆序输出为：");
printf("%s\n",string_stack);
}
10. 字符串比较函数contrast()
void contrast(char *string_stack, char *string_queue, int string_side) //字符串比较
{
int i, k;
for(k = 0; k
{
if(string_stack[k] == string_queue[k]) //字符串中各个元素依次比较
i = 1;
else
{
i = 0;
break; //只要有一个不同就跳出循环
}
}
if(i)
printf("输入字符串是回文\n");
else
printf("输入字符串不是回文\n");
}
五、 测试结果
1. 当输入回文字符串时，有如下结果：
2. 当输入不是回文字符串时，结果如下：
六、 总结反思
拿到题目时，想到总体思路是让字符串正序和逆序比较。正好符合队列和栈的操作需求。看来一下队列和栈的算法后，发现不是很难。
在设计程序时，总体思路有，但具体细节实现有些困难。比如队列和栈该定义怎样的结构体。数组有局限性，不能动态地满足字符串的长度。我就定义了指针变量。
以前不怎么使用指针，不怎么熟悉，这次在使用指针时地址没有分配好，导致函数调用时出错。下次在定义指针时要时刻注意地址。平时尽量定义普通变量，如需要再传递变量的地址。
13软工转本1 钱剑滨 实验报告
利用队列和栈判断回文实验报告
信息工程 系 13软工转本1 日期 2016年03月20日 姓名 钱剑滨 学号 13131116 电话 [1**********]
一、 实验内容
编写关于栈和队列操作的C 语言程序，要求能判断输入字符串是否为回文（回文：正序和逆序一样）。
二、 实验步骤
1. 分析栈和队列的实现算法。
2. 编写程序，通过队列来实现字符串正序输出，通过栈来实现字符串逆序输出。
3. 运行程序，纠正错误，对预测结果进行验证。
三、 设计概要
1. 本实验包含了7个函数：
a) 主函数 main()
b) 接收字符串函数get_string ()
c) 初始化队列函数init_queue ()
d) 初始化栈函数 init_stack ()
e) 入队函数 enter_queue ()
f) 出队函数 out_queue()
g) 压栈函数 push ()
h) 出栈函数 pop()
i) 字符串比较函数contrast()
四、 程序设计
1. 函数前包含的头文件名、结点类型定义、全局变量和函数声明 #include
#include
#include
#define N 100 //输入字符串的最大长度
typedef struct SeqQuene //定义循环队列
{
char *pBase_queue;
int front;
int rear;
}SeqQueue;
typedef struct SeqStack //定义栈
{
char *pBase_stack;
int bottom;
int top;
}SeqStack;
/*函数声明*/
void get_string(char *string_get, int *qString_side); //接受字符串
void init_queue(SeqQueue *queue, int string_side); //初始化队列
void init_stack(SeqStack *stack, int string_side); //初始化栈
void enter_queue(SeqQueue *queue, char *string_get, int
string_side); //入队
void out_queue(SeqQueue *queue, char *string_queue, int
string_side); //出队
void push(SeqStack *stack, char *string_get, int string_side); //压栈
void pop(SeqStack *stack, char *string_stack, int string_side);//出栈
void contrast(char *string_stack, char *string_queue, int string_side);
//字符串比较
2. 主函数main()
void main()
{
SeqStack stack; //这里定义普通变量，下面再传地址 SeqQueue queue; //如果定义指针变量会报错 char *string_get, *string_queue, *string_stack;
//定义字符指针，分别存放接收字符串、顺序输出字符串、逆序
输出字符串
int string_side; //定义接收字符串的长度
string_get = (char *)malloc(sizeof (char) * N);
//给字符指针分配空间，必须在声明的函数内部
get_string(string_get, &string_side); //接受字符串
string_queue = (char *)malloc(sizeof (char) * (string_side + 1));
string_stack = (char *)malloc(sizeof (char) * (string_side + 1));
init_queue(&queue, string_side); //初始化队列
init_stack(&stack, string_side); //初始化栈
enter_queue(&queue, string_get, string_side);
out_queue(&queue, string_queue, string_side);
push(&stack, string_get, string_side);
pop(&stack, string_stack, string_side);
contrast(string_stack, string_queue, string_side);
}
3. 接收字符串函数get_string ()
void get_string(char *string_get, int *qString_side) //接收字符串
{
int string_side;
printf("请输入要判断的字符串\n");
scanf("%s", string_get);
string_side = *qString_side = strlen(string_get);
//判断字符串长度
printf("输入的字符串长度为%d\n", string_side);
}
4. 初始化队列函数init_queue ()
void init_queue(SeqQueue *queue, int string_side) //初始化队列
{
queue->pBase_queue = (char *)malloc(sizeof (char) *
(string_side + 1));
queue->front = 0;
queue->rear = 0;
}
5. 初始化栈函数init_stack ()
void init_stack(SeqStack *stack, int string_side) //初始化栈
{
stack->pBase_stack = (char *)malloc(sizeof (char) *
(string_side + 1));
stack->bottom = -1;
stack->top = -1;
}
6. 入队函数enter_queue ()
void enter_queue(SeqQueue *queue, char *string_get, int
string_side) //入队
{
int i = 0;
while((queue->rear+1) % (string_side + 1) != queue->front) //队列满时跳出循环
{
queue->pBase_queue[queue->rear] = string_get[i]; //依次在队列里添加字符
queue->rear = (queue->rear + 1) % (string_side + 1); //循环队列
i++;
}
}
7. 出队函数out_queue()
void out_queue(SeqQueue *queue, char *string_queue, int
string_side) //出队
{
int i = 0;
while(queue->rear != queue->front) //当队列空时跳出循环
{
string_queue[i] = queue->pBase_queue[queue->front]; //依次取出队列里字符
queue->front = (queue->front + 1) % (string_side + 1);
//循环队列
i++;
}
string_queue[i] = '\0'; //字符串结束
printf("顺序输出为：");
printf("%s\n",string_queue);
}
8. 压栈函数push ()
void push(SeqStack *stack, char *string_get, int string_side)
//压栈
{
int i = 0;
while(string_side--)
{
stack->top++; //top指针先后移一位
stack->pBase_stack[stack->top] = string_get[i];
//一次在栈里添加字符
i++;
}
}
9. 出栈函数 pop()
void pop(SeqStack *stack, char *string_stack, int string_side)
//出栈
{
int i = 0;
while(stack->top != stack->bottom) //栈空时跳出循环
{
string_stack[i] = stack->pBase_stack[stack->top];
//依次取出栈里字符
stack->top--; //top指针前移一位
i++;
}
string_stack[i] = '\0'; //字符串结束
printf("逆序输出为：");
printf("%s\n",string_stack);
}
10. 字符串比较函数contrast()
void contrast(char *string_stack, char *string_queue, int string_side) //字符串比较
{
int i, k;
for(k = 0; k
{
if(string_stack[k] == string_queue[k]) //字符串中各个元素依次比较
i = 1;
else
{
i = 0;
break; //只要有一个不同就跳出循环
}
}
if(i)
printf("输入字符串是回文\n");
else
printf("输入字符串不是回文\n");
}
五、 测试结果
1. 当输入回文字符串时，有如下结果：
2. 当输入不是回文字符串时，结果如下：
六、 总结反思
拿到题目时，想到总体思路是让字符串正序和逆序比较。正好符合队列和栈的操作需求。看来一下队列和栈的算法后，发现不是很难。
在设计程序时，总体思路有，但具体细节实现有些困难。比如队列和栈该定义怎样的结构体。数组有局限性，不能动态地满足字符串的长度。我就定义了指针变量。
以前不怎么使用指针，不怎么熟悉，这次在使用指针时地址没有分配好，导致函数调用时出错。下次在定义指针时要时刻注意地址。平时尽量定义普通变量，如需要再传递变量的地址。