资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
. .实验二 栈、队列的实现及应用实验课程名:数据构造与算法专业班级: 学号: :实验时间: 实验地点: 指导教师: 珊 一、实验目的1、掌握栈和队列的顺序存储构造和链式存储构造,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原那么。3、掌握栈和队列的根本操作实现方法。二、实验容一、实验目的及要求1、掌握栈和队列的顺序存储构造和链式存储构造,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原那么。3、掌握栈和队列的根本操作实现方法。二、实验学时2学时三、实验任务任务一:1实现栈的顺序存储2实现栈的链式存储。任务二:实现顺序存储的循环队列,完成键盘缓冲区的功能。四、实验重点、难点1. 进栈、出栈栈顶指针都要改变。2. 队空、队满的条件及入队、出队时指针的变更。五、操作容与要求1.任务一1:完成以下程序,该程序实现栈的顺序存储构造,构建顺序栈栈中的元素依次为R,S,Y,F,C,T,依次进展进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成顺序栈时,从键盘上读取数据元素。1源代码:*include*include*defineSTACK_INIT_SIZE 100*defineSTACKINCREMENT 10* defineOK 1* defineERROR 0typedefcharSElemType;/* 顺序栈的存储类型 */typedefstruct/define structure SqStack()SElemType *base;SElemType *top;int stacksize;SqStack;/*构造空顺序栈*/int InitStack(SqStack *S)/InitStack() sub-functionS-base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if (!S-base)printf(分配空间失败!n);return (ERROR);S-top = S-base;S-stacksize = STACK_INIT_SIZE;printf(栈初始化成功!n);return (OK); /InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e)/GetTop() sub-functionif (S-top = S-base)printf(栈为空!n);/if empty SqStackreturn (ERROR);*e = *(S-top - 1);return (OK); /GetTop() end/*将元素压入顺序栈*/int Push(SqStack *S)/Push() sub-functionSElemType e;if (S-top - S-baseS-stacksize)S-base = (SElemType *)realloc(S-base, (S-stacksize +STACKINCREMENT*sizeof(SElemType);if (!S-base)printf(存储空间分配失败!n);return (ERROR);S-top = S-base + S-stacksize;S-stacksize += STACKINCREMENT;fflush(stdin);/去除输入缓冲区,否那么原来的输入会默认送给变量xprintf(请输入要入栈的元素的值:);e = getchar();*S-top+ = e;return (OK); /Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e)/Pop() sub-functionif (S-top = S-base)printf(栈为空!n);return (ERROR);*e = *-S-top;return (OK); /Pop() endvoid display(SqStack *s)if (s-top = s-base)printf(栈为空!n);elsewhile (s-top != s-base)s-top = s-top - 1;printf(%c-, *(s-top);printf(n);int main()int choice;SElemType e;SqStack s;doprintf(=n);printf( 0:退出n);printf( 1:初始化栈n);printf( 2:入栈n);printf( 3:出栈n);printf( 4:读取栈顶元素n);printf( 5:显示栈中元素n);printf(=n);printf(输入操作选择代码(0-5):);scanf(%d, &choice);while (choice5) printf(输入有误,请重新输入(0-5):); scanf(%d, &choice); switch (choice)case 0:exit(1);case 1:InitStack(&s); break;case 2:printf(2n); Push(&s); break;case 3:Pop(&s, &e); printf(出栈元素的值是:%cn, e); break;case 4:GetTop(&s, &e); printf(栈顶元素的值是:%cn, e); break;case 5: printf(栈中元素的值是为:n); display(&s); break; while (choice);return 0;2运行结果(3) 结果分析 顺序表通过设置栈顶运用线性构造实现先进先出功能。2.任务一2:完成以下程序,该程序实现栈的链式存储构造,构建链栈栈中的元素依次为China,Japan,France,India,Australia,依次进展进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成链栈时,从键盘上读取数据元素。1源代码:*include*include*include* define OK 1* define ERROR 0typedef char DataType;/* 链式栈的存储类型 */typedef struct SNode /define structure LinkStack DataType data20; struct SNode *next;SNode,*LinkStack;void InitStack_L (LinkStack *top)top = (LinkStack)malloc(sizeof(SNode) ; top-next = NULL;printf(nn栈初始化成功!nn);/*取链式栈顶元素*/int GetTop_L(LinkStack *top,DataType e) /GetTop_L() sub-function if(!top-next) printf(链栈为空!n); return (ERROR); else strcpy(e,top-next-data); return (OK); /GetTop_L() end/* 将元素压入链式栈*/int Push_L(LinkStack *top) /Push_L() sub-function SNode *q;DataType e20; q=(LinkStack)malloc(sizeof(SNode); if(!q) printf(存储空间分配失败! n); return (ERROR); fflush(stdin);/去除输入缓冲区,否那么原来的输入会默认送给变量eprintf(n请输入要入栈的元素的值:);gets(e);strcpy(q-data,e); q-next=top-next; top-next=q; return (OK); /Push_L() end/*将元素弹出链式栈*/int Pop_L(LinkStack *top,DataType e) /Pop_L() sub-function SNode *q; if(!top-next) printf(链栈为空! n ); return (ERROR); strcpy(e,top-next-data); q=top-next; top-next=q-next; free(q); return (OK); /Pop_L() endvoid display(LinkStack *top) LinkStack p=top-next; if(!p) printf(栈为空!n); elsewhile(p) printf(%s-,p-data); p=p-next; printf(n); int main()char choice;DataType e20=;LinkStack s=NULL;do printf(=n); printf( 0:退出n)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号