栈和队列的基本操作实验报告.doc

. . . .数据结构实验报告一软件132201300514211徐蜀实验二 栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容 1回文判断三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。3、严格按照数据结构实验报告模板和规范，及时完成实验报告。 四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。 附流程图与主要代码）、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、栈的初始长度与需要再增加的长度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;/定义SElemType为char型 2、栈的顺序存储表示typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;3、队列的链式表示方法typedef struct QNode SElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;4、初始化栈/* 函数功能：对栈进行初始化 参数：栈（SqStack &S）成功返回1，否则返回0 */int InitStack(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);/申请内存 if(!S.base) /判断有无申请到空间 return ERROR; /没有申请到内存，返回0 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;5、入栈操作/* 函数功能：将元素入栈 参数：栈（SqStack &S）,插入元素e 插入成功返回1，否则返回0 */int Push(SqStack &S, SElemType e) if(S.top - S.base = S.stacksize) /判断栈顶与栈底的差是否大于栈的/容量 S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType); /栈满了，重新申请内存 if(!S.base) /判断是否申请成功 return ERROR; /不成功返回0 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;6、出栈操作/* 函数功能：将栈中的元素弹出参数：栈(SqStack &S),记录元素e */int Pop(SqStack &S, SElemType &e) if(S.top = S.base) /判断栈是否为空 return ERROR; e = *(-S.top) ; return OK;7、初始化队列 /* 函数功能：初始化队列参数：队列（LinkQueue &Q）成功返回1， 否则返回0 */int InitQueue(LinkQueue &Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);/申请结点的内存 if(!Q.front) /判断有无申请到空间 return ERROR; /没有返回0 Q.front -next = NULL; return OK;8.在队列队尾插入元素/* 函数功能：在队列队尾插入元素参数：队列（LinkQueue &Q），插入元素e成功返回1， 否则返回0 */int EnQueue(LinkQueue &Q, QElemType e) p = (QueuePtr)malloc(sizeof(QNode); /申请新的结点 if(!p) return ERROR; p - data = e; p - next = NULL; Q.rear - next = P; Q.rear = p; return OK;9.删除队头元素/* 函数功能：删除对头元素参数：队列（LinkQueue &Q），记录值e成功返回1，否则返回0 */int DeQueue(LinkQueue &Q, QElemType &e) if(Q.front = Q.rear) /判断队列是否为空 return ERROR; p = Q.front - next; e = p - data; Q.front - next = p - next; if(Q.rear = p) Q.rear = Q.front; free(p); return OK;10、主函数int main() SqStack S; /声明一个栈LinkQueue Q; /声明一个队列char m,k,c; int n=0,i,j,t=0,z=0;while(!t)cout 请输入你要判断回文的字符串，输入结束：;InitQueue (Q);InitStack (S);while(c=getchar()!=)/对字符的判断 不断输入字符EnQueue (Q,c);Push (S,c);n+;for( j=1;jn) /如果j n则说明全部相等cout 这个字符串不是回文字符串 endl;elsecout 这个字符串是回文字符串 endl; return 0;说明：通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在110内的函数将结束，否则将继续进行。 程序调试及运行结果分析(应包含多组测试数据) 五、实验总结通过这次试验，我知道自己还有很多不足，还会犯一些细节上的错误，但是也因此对栈和队列的操作有了很好的认识附录 1开始、程序流程图执行主函数main 声明一个栈S和队列Q！t N (c=getchar()!= Y N Y入栈入队列j=1;j=n;j+ N出栈出队列，并判断值是否想等 Y判断是否是回文数，并输出判断语句结束 2、程序清单#include#includeusing namespace std;/栈的表示和实现#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef char SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;/队列的表示和实现typedef struct QNode SElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;/关于栈的函数int InitStack(SqStack &S) S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S.base) return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;int Push(SqStack &S, SElemType e) if(S.top - S.base = S.stacksize) S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType); if(!S.base) return ERROR; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;int Pop(SqStack &S, SElemType &e) if(S.top = S.base) return ERROR; e = *(-S.top) ; return OK;/关于队列的函数int InitQueue(LinkQueue &Q) Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front -next = NULL; return OK;int EnQueue(LinkQueue &Q, SElemType e) QueuePtr p = (QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR; p - data = e; p - next = NULL; Q.rear - next = p; Q.rear = p; return OK;int DeQueue(LinkQueue &Q, SElemType &e) if(Q.front = Q.rear) return ERROR; QueuePtr p = Q.front - next; e = p - data; Q.front - next = p - next; if(Q.rear = p) Q.rear = Q.front; free(p); return OK;/主函数int main() SqStack S;LinkQueue Q;char m,k,c;int n=0,i,j,t=0,z=0;while(!t)cout 请输入你要判断回文的字符串： endl;InitQueue (Q);InitStack (S);while(c=getchar()!=)/对字符的判断 不断输入字符EnQueue (Q,c);Push (S,c);n+;for( j=1;