《栈和队列的基本操作实验报告》由会员分享，可在线阅读，更多相关《栈和队列的基本操作实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告一软件 132201300514211徐蜀实验二 栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容1回文判断三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。3、严格按照数据结构实验报告模板和规范，及时完成实验报告。 四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据
2、类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。 附流程图与主要代码）、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、栈的初始长度与需要再增加的长度#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef char SElemType;/定义 SElemType 为 char 型 2、栈的顺序存储表示typedef structSElemType *base;SElemType *top;int stacksize;SqStack;3、队列的
3、链式表示方法typedef struct QNodeSElemType data;struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr 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) /判断有无申请到空
4、间return ERROR; /没有申请到内存，返回 0S.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) * s
5、izeof(SElemType); /栈满了，重新申请内存if(!S.base) /判断是否申请成功return ERROR; /不成功返回 0S.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
6、;7、初始化队列 /* 函数功能：初始化队列参数：队列（LinkQueue &Q）成功返回 1， 否则返回 0 */int InitQueue(LinkQueue &Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);/申请结点的内存if(!Q.front) /判断有无申请到空间return ERROR; /没有返回 0Q.front -next = NULL; return OK;8.在队列队尾插入元素/* 函数功能：在队列队尾插入元素参数：队列（LinkQueue &Q） ，插入元素 e成功返回 1， 否则返回 0 */int EnQue
7、ue(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
8、 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 n) /如果 j n 则说明全部相等cout #includeusing namespace std;/栈的表示和实现#define STACK_INIT_SIZE 100#
9、define STACKINCREMENT 10#define ERROR 0#define OK 1typedef char SElemType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;/队列的表示和实现typedef struct QNodeSElemType data;struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/关于栈的函数int InitStack(SqSt
10、ack &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(SElem
11、Type);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)ret
12、urn 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 n)cout 这个字符串是回文字符串 endl;elsecout 这个字符串不是回文字符串 endl;return 0;
