第二篇：数据结构-实验报告2栈和队列-田媛

数据结构实验报告

一、抄写自己所选择的题目。

1、 称正读和反读都相同的字符序列为“回文”，例如，abcddcba、qwerewq是回文，ashgash不是回文。试写一个算法，判断读入的一个以“@”为结束符的字符序列是否为回文。

2、假设以数组se[m]存放循环队列的元素，同时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首节点前一个位置，写出这样设计的循环队列的入队、出队的算法。

二、写出算法设计思路。

1.  先分配一个含80个字符的数组用于存放输入的字符序列，然后以堆栈的方式将字符序列入栈，接着，出栈并与相应的顺序数组依次进行比较，直到出现不相等的情况，就输出“不是回文”，否则在结束比较后输出“是回文”。

2.  先分配一个用来存放输入的字符串的数组。然后按照用户的长度要求将字符串读入，接着，将此读入的字符串存入循环队列中，并计算所存循环队列的长度，再将字符依次输出到屏幕。实现字符串的入队，出队。

三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）

1./*shiy2.1 回文*/

typedef char SElemType;

#include"c-head.h"

#include"hong.h"

#include"shunxz.c"

#define CHECK 0

     

main()

{

    SqStack s;

    char ch[80],*p,e;         /* 变量声明 */

    int t,i,k=1;

    if(InitStack(&s)) /* 初始化栈成功 */

   {

     printf("请输入以“@”结尾的字符序列: ");

     gets(ch);

     p=ch;

   }

    while(*p)

    if(*p!=64)

    Push(&s,*p++);

    else

    {

    t=StackLength(s);

    printf("您一共输入了%d个字符。\n\n\n",t);

    p++;

    }

    printf("正在比较中：\n");

    printf("正读 反读\n");

    for(i=0;i<t;i++)

    {

    Pop(&s,&e);

    printf(" %c -><- %c\n",ch[i],e);

    if(ch[i]!=e){printf("您输入的字符序列“不是”回文。\n");

    if(CHECK)printf("no."); k=0;break;}

    }

    if(k)

    printf("您输入的字符序列“是”回文。\n");

    if(CHECK){if(k)printf("yes.");}

    getch();

}

/* c-head.h (程序名) */

 #include<string.h>

 #include<ctype.h>

 #include<malloc.h> /* malloc()等 */

 #include<limits.h> /* INT_MAX等 */

 #include<stdio.h> /* EOF(=^Z或F6),NULL */

 #include<stdlib.h> /* atoi() */

 #include<io.h> /* eof() */

 #include<math.h> /* floor(),ceil(),abs() */

 #include<process.h> /* exit() */

 #include<conio.h>

 /* 函数结果状态代码 */

 #define TRUE 1

 #define FALSE 0

 #define OK 1

 #define ERROR 0

 #define INFEASIBLE -1

 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */

 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

/* hong.h 栈的顺序存储表示 */

 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */

 #define STACKINCREMENT 2 /* 存储空间分配增量 */

 typedef struct SqStack

 {

   SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */

   SElemType *top; /* 栈顶指针 */

   int stacksize; /* 当前已分配的存储空间，以元素为单位 */

 }SqStack; /* 顺序栈 */

/* shunxz.c 顺序栈（存储结构由hong.h定义）的基本操作 */

 Status InitStack(SqStack *S)

 { /* 构造一个空栈S */

   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

   if(!(*S).base)

     exit(OVERFLOW); /* 存储分配失败 */

   (*S).top=(*S).base;

   (*S).stacksize=STACK_INIT_SIZE;

   return OK;

 }

 int StackLength(SqStack S)

 { /* 返回S的元素个数，即栈的长度 */

   return S.top-S.base;

 }

Status Push(SqStack *S,SElemType e)

 { /* 插入元素e为新的栈顶元素 */

   if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */

   {

     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));

     if(!(*S).base)

       exit(OVERFLOW); /* 存储分配失败 */

     (*S).top=(*S).base+(*S).stacksize;

     (*S).stacksize+=STACKINCREMENT;

   }

   *((*S).top)++=e;

   return OK;

 }

 Status Pop(SqStack *S,SElemType *e)

 { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

   if((*S).top==(*S).base)

     return ERROR;

   *e=*--(*S).top;

   return OK;

 }

2. /* “shiy2.2.c” 循环列表的入队与出队 */

typedef char QElemType;

#include "c-head.h"

#include "xhdl.h"

#include "xhdl.c"

main()

{

    SqQueue q;

    int m,se[80],i,*p,t;

    char e;

    if(InitQueue(&q)) /* 初始化队列成功 */

    {

    printf("Please input the length of the SqQueue: ");

    scanf("%d",&m);

    }

    printf("Please input your char:");

    for(i=0;i<=m;i++)

    scanf("%c",&se[i]);

    p=se;

    printf("Your char is: ");

    for(i=0;i<=m;i++)

    printf("%c",p[i]);                     

    while(*p)         /*入队*/

    EnQueue(&q,*p++);

    t=QueueLength(q);

    printf("\nThere are %d chars in the SqQueue:",t-1);

    while(t)           /*出队*/

        {     DeQueue(&q,&e);t--;printf("%c",e);        }

    getch();

}

/*  "xunhdl.h"文件—— 循环队列  */

#define MAXQSIZE 100     /*最大队列长度 */

typedef struct SqQueue

{

    QElemType *base;   /*初始化的动态分配空间 */

    int front;         /*头指针*/

    int rear;          /*尾指针*/

}SqQueue;              /*定义循环队列*/

/*  "xhdl.c"——循环队列基本操作 */

Status InitQueue(SqQueue *Q) /* 构造一个空队列Q */

{   (*Q).base=(QElemType *)malloc(MAXQSIZE *sizeof(QElemType));

    if(!(*Q).base)

        exit(OVERFLOW);      /*储存分配失败 */

    (*Q).front=(*Q).rear=0;

    return OK;

}

int QueueLength(SqQueue Q) /*返回Q的元素个数，即队列的长度 */

{       return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}

Status EnQueue(SqQueue *Q,QElemType e)

{   /*插入e为Q的新的队尾元素*/

    if(((*Q).rear+1)%MAXQSIZE==(*Q).front)return ERROR;/*队列满*/

    (*Q).base[(*Q).rear]=e;

    (*Q).rear=((*Q).rear+1)%MAXQSIZE;

    return OK;

}

Status DeQueue(SqQueue *Q,QElemType *e)

{   /*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则返回ERROR*/

    if((*Q).front==(*Q).rear) return ERROR;

    *e=(*Q).base[(*Q).front];

    (*Q).front=((*Q).front+1)%MAXQSIZE;

    return OK;

}

四、写出算法设计、编程和调试运行的体会。

1.         这个问题思路很简单，只需要将栈的有关操作调用即可。编程过程中是一个对旧知识的复习加深和对新知识的应用的过程。关键要注意的是栈的存储方式是：先入后出。

2.         在调试过程中出现了不少问题:

首先是“gets”函数无法正常运行，其次是课本中给的源代码要加指针符号才能用。比如     “Q.rear” 要修改成 “(*Q).rear”。在与同学合作之后，我们终于解决了这些问题。我们用scanf代替gets进行编程从而实现了这个出对入队的程序。开来还有必要多加练习。