数据结构实验4顺序栈的基本操作及应用.doc

实验3 顺序栈的基本操作及应用 实验目的 帮助学生理解栈结构的特点即后进先出。 2．掌握栈的顺序存储结构和基本操作，重点掌握入栈和弹栈操作。验证所学的算法和数据结构完成该程序并上机运行测试。给定的字符回文是指正读反读均相同的字符序列，如abba和ab db a均是回文，但good不是回文。 alindrome(char *str) /*判别字符 sqstack S; } 注：题目1程序清单 /*****************sqstack.h***********************/ /************顺序栈类型定义***********/ #define INITSIZE 100 typedef int ElemType; typedef struct { ElemType *base;/*栈顶指针，又是存储元素的一维数组*/ int top; /*栈顶指针，记录栈顶的下一个位置*/ int stacksize; /* 记录存储空间的尺寸*/ }sqstack; /***********函数声明**************/ void initstack(sqstack *S); int getlen(sqstack S); int gettop(sqstack S,ElemType *e); int push(sqstack *S, ElemType x); int pop(sqstack *S, ElemType *e); int emptystack(sqstack S); void print(sqstack S); /*************函数定义***********/ /**构造空栈**/ void initstack(sqstack *S) {/*构造一个空栈由指针S指出。*/ S-base= __(1)___; if (!S-base) {printf(OVERFLOW!); exit(1);} S-top=__(2)__; S-stacksize = INITSIZE; } /**求栈长操作**/ int getlen(sqstack S) { return (__(3)___); } /**取栈顶元素操作**/ int gettop(sqstack S,ElemType *e) { if(S.top == 0) return 0; _____(4)____________; return 1; } /**压栈**/ int push(sqstack *S, ElemType x) {/*向栈顶插入元素x，成功返回１，失败返回０*/ if(S-top == S-stacksize) /*栈已满*/ { S-base = ___(5)______; if(!S-base) { printf(OVERFLOW!); return 0;} S-stacksize ++; } /*插入*/ ____(6)_______; ____(7)___________; return(1); } /**弹栈**/ int pop(sqstack *S, ElemType *e) {/*若栈空, 则返回０*/ if(S-top==0) return 0; /*删除*/ ______(8)___________; ______(9)____________; return 1; } /**判栈空**/ int emptystack(sqstack S) /*判栈S为空栈时返回值为1， 反之为0*/ { return(____(10)____); } /**输出栈元素**/ void list(sqstack S) {/*从栈底元素输出到栈顶元素*/ int i = 0; if(emptystack(S)) {printf(none!\n); return;} while(iS.top) { printf(%4d,S.base[i]); i++; } printf(\n); } /***************** sqstack.c文件*************** **/ ______(11)___________ void menu() { printf(******************menu***************\n); printf( 0: