1、1、帮助读者复习C+语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容 本次实验提供2个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个 本人由于初学，对数据结构的操作知识欠缺，所以选了2个实验题目中的第1个题目如下:题目一:回文判断（*） 问题描述 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。基本要求 （1）数据从键盘读入;（2）输出要判断的字符串;（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出
2、“Yes”，否则输出“No”。测试数据 由学生任意指定。三、算法设计 1、程序所需头文件已经预处理宏定义如下 #includestdlib.h#define OVERFLOW -1 第 3 页 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType;typedef int Status;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;typedef ch
3、ar QElemType;typedef struct QNode QElemType data;struct QNode *next;QNode,*QNodePtr;typedef struct QNodePtr front;QNodePtr rear;LinkQueue;2、程序中所需的操作栈的POP和PUSH函数 Status Push（SqStack &S,SElemType e） /插入e为新的栈顶元素 if（S.top-S.base=S.stacksize） /栈满，追加存储空间 S.base=（SElemType*）realloc（S.base,（S.stacksize+STAC
4、KINCREMENT）*sizeof（SElemType）;if（!S.base）exit （OVERFLOW）;/存储空间分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT; *S.top+=e;return OK;/Push函数 Status Pop（SqStack &S ,SElemType &e） /若栈不空，删除栈顶元素，并用e返回其值 if（S.top=S.base） return ERROR;第 4 页 数据结构实验报告 计科111 * 201100814* e=*-S.top;/Pop函数 3、程序中所需的操作队列
5、的函数 Status EnQueue（LinkQueue &Q,QElemType e） QNodePtr p;p=（QNodePtr）malloc（sizeof（QNode）; if（!p）exit（OVERFLOW）;p-data=e;next=NULL;Q.rear-next=p;Q.rear=p; Status DeQueue（LinkQueue &Q,QElemType &if（Q.front=Q.rear） return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-if（Q.rear=p） Q.rear=Q.front; free
6、（p）;4、另外，还有创建栈和创建一个空的链式栈 Status CreatStack（SqStack &S） S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType）;S.base）exit（OVERFLOW）; S.top=S.base;S.stacksize=STACK_INIT_SIZE; return OK;/创建栈 Status CreatQueue（LinkQueue &Q） 第 5 页 Q.front=Q.rear=（QNodePtr）malloc（sizeof（QNode）;Q.front）exit（OVERFLOW
7、）;Q.front-/建立一个空的链式栈 5、再就是最重要的判断部分 int Test（） /判别输入的字符串是否回文序列,是则返回1,否则返回0 SqStack S;LinkQueue Q;CreatStack（S）;CreatQueue（Q）;char c;SElemType a,b;while（c=getchar（）!=） Push（S,c）;EnQueue（Q,c）; /同时使用栈和队列两种结构 while（S.top!=S.base） Pop（S,a）;DeQueue（Q,b）;if（a!=b） return ERROR;判断输入的字符串是否回文序列,是则返回1,否则返回0 四、调试
8、与测试 我们开始测试数据:12321，如图:输出结果是YES，说明程序判断出12321是回文 然后我们测试12345，如图 第 6 页 输出结果是NO，所以程序判断12345不是回文 五、总结 通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。六、源代码 #define ST
9、ACK_INIT_SIZE 100 #define STACKINCREMENT 10 第 7 页 S） /创建栈 S,SElemType e） /插入e为新的栈顶元素 =S.stacksize）/栈满，追加存储空间 S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType）;/Push e） /若栈不空，删除栈顶元素，并用e返回其值 e=*-S.top;/Pop Q） /建立一个空的链式栈 第 8 页 Q.rear-int Test（）/判别输入的字符串是否回文序列,是则返回1,否则返回0 char c;） /同时使用栈和队列两种结构 Status main（） printf（请输入要判断的字符串n并请以作为结束符n）; if（Test（）=1） YESn第 9 页 else printf（NOn第 10 页
