《2022年实验二栈、队列的实现及应用整理 .pdf》由会员分享，可在线阅读，更多相关《2022年实验二栈、队列的实现及应用整理 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验二栈、队列的实现及应用实验课程名 ：数据结构与算法专业班级：学号：姓名：实验时间：实验地点：指导教师：冯珊一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务任务一：（ 1）实现栈的顺序存储（2）实现栈的链式存储。任务二：实现顺序存储的循环队列，完成键盘缓
2、冲区的功能。四、实验重点、难点1.进栈、出栈栈顶指针都要改变。2.队空、队满的条件及入队、出队时指针的变更。五、操作内容与要求1. 任务一（ 1）：完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为 R，S，Y，F，C，T），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成顺序栈时，从键盘上读取数据元素。（1）源代码：#include #include #defineSTACK_INIT_SIZE 100 #defineSTACKINCREMENT 10 # defineOK 1 # defineERROR 0 typedefchar SElemTyp
3、e ; /* 顺序栈的存储类型 */typedefstruct/define structure SqStack() SElemType *base; SElemType *top; int stacksize; SqStack; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 16 页 - - - - - - - - - /* 构造空顺序栈 */int InitStack(SqStack * S) /InitStack() sub-function S-base = (
4、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-function if ( S-top = S-b
5、ase) printf(栈为空 !n ); /if empty SqStackreturn ( ERROR); *e = *(S-top - 1); return ( OK ); /GetTop() end/* 将元素压入顺序栈 */int Push( SqStack * S) /Push() sub-function SElemType e; if ( S-top - S-baseS-stacksize) S-base = (SElemType *)realloc(S-base, (S-stacksize + STACKINCREMENT*sizeof ( SElemType ); if (
6、! S-base) printf(存储空间分配失败 !n ); return ( ERROR); S-top = S-base + S-stacksize; S-stacksize += STACKINCREMENT; fflush(stdin ); / 清除输入缓冲区，否则原来的输入会默认送给变量x名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 16 页 - - - - - - - - - printf( 请输入要入栈的元素的值: ); e = getchar(); *
7、S-top+ = e; return ( OK ); /Push() end/* 将元素弹出顺序栈 */int Pop( SqStack * S, SElemType * e) /Pop() sub-function if ( 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 ); else while ( s-top != s-base) s-t
8、op = s-top - 1; printf(%c- , *(s-top); printf(n ); int main() int choice; SElemType e; SqStack s; do printf(=n ); printf( 0:退出 n ); printf( 1:初始化栈 n ); printf( 2:入栈 n ); printf( 3:出栈 n ); printf( 4:读取栈顶元素 n ); printf( 5:显示栈中元素 n ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
9、- - - - - 第 3 页，共 16 页 - - - - - - - - - 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(出栈元素的值是 :%
10、cn , e); break; case 4:GetTop(&s, &e); printf( 栈顶元素的值是 :%cn , e); break ; case 5: printf( 栈中元素的值是为：n ); display(&s); break ; while (choice); return 0; （2）运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 16 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - -
11、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 16 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 16 页 - - - - - - - - - （3）结果分析顺序表通过设置栈顶运用线性结构实现先进先出功能。2. 任务一（ 2）：完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为 China，Japan，France ，India ，Australia），
12、依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成链栈时，从键盘上读取数据元素。（1）源代码： #include #include #include # define OK 1 # define ERROR 0 typedef char DataType; /* 链式栈的存储类型 */ typedef struct SNode /define structure LinkStack DataType data20; struct SNode *next; SNode,*LinkStack; void InitStack_L (LinkStack *top) top = (L
13、inkStack)malloc(sizeof(SNode) ; top-next = NULL; printf(nn栈初始化成功！nn); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 16 页 - - - - - - - - - /* 取链式栈顶元素*/ int GetTop_L(LinkStack *top,DataType e) /GetTop_L() sub-function if(!top-next) printf(链栈为空 !n); return (ERRO
14、R); 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);/清除输入缓冲区，否则原来的输入会默认送给变量e printf(n请输入要入栈的元素的值:); gets(e);
15、 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() end 名师资料
16、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 16 页 - - - - - - - - - void display(LinkStack *top) LinkStack p=top-next; if(!p) printf(栈为空 !n); else while(p) printf(%s-,p-data); p=p-next; printf(n); int main() char choice; DataType e20=; LinkStack s=NULL; do printf
17、(=n); printf( 0:退出 n); printf( 1:初始化栈 n); printf( 2:入栈 n); printf( 3:出栈 n); printf( 4:读取栈顶元素 n); printf( 5:显示栈中元素 n); printf(=n); printf(输入操作选择代码(0-5):); fflush(stdin); scanf(%c,&choice); while(choice5) printf(输入有误，请重新输入(0-5):); fflush(stdin); scanf(%c,&choice); switch(choice) case 0:exit(1); case 1
18、: InitStack_L(&s);break; case 2: Push_L(&s);break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 16 页 - - - - - - - - - case 3:Pop_L(&s, e);break; case 4:GetTop_L(&s, e);printf(栈顶元素的值是:%sn,e);break; case 5: printf(栈中元素的值是: );display(&s); while(choice); return
19、0; （2）运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 16 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 16 页 - - - - - - - - - （3）结果分析链表通过设置栈顶运用指针实现先进先出功能3. 任务二： 完成下列程序，该程序实现循环队列的存储和基本操作，构建循环队列，完成键
20、盘缓冲区的功能，每输入一个字符，链入缓冲区队列中；每输出一个字符，将该字符从缓冲区中删除。（1）源代码： #include #include # define MAXQSIZE 100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 16 页 - - - - - - - - - # define OK 1 # define ERROR 0 /* 定义 QElemType 为int 或别的自定义类型 */ typedef char QElemType; /* 顺序队列的存
21、储类型 */ typedef struct SqQueue /define structure SqQueue QElemType *base; int front; int rear; SqQueue; /* 构造空顺序队列*/ int InitQueue(SqQueue *Q) /InitQueue() sub-function Q-base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q-base) printf(分配空间失败 ! n); return (ERROR); Q-front=Q-rear=0; printf(队列初始
22、化成功! n); return (OK); /InitQueue() end /* 求顺序队列长度*/ int QueueLength(SqQueue *Q) /QueueLength() sub-function return (Q-rear-Q-front+MAXQSIZE)%MAXQSIZE); /* 在顺序队列尾插入新元素*/ int EnQueue(SqQueue *Q,QElemType e) /EnQueue() sub-function if(Q-rear+1)%MAXQSIZE=Q-front) printf(队列已满 ! n); return (ERROR); Q-base
23、Q-rear=e; Q-rear=(Q-rear+1)%MAXQSIZE; return (OK); /EnQueue() end /* 在顺序队列头删除旧元素*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 16 页 - - - - - - - - - int DeQueue(SqQueue *Q,QElemType e) /DeQueue() sub-function if(Q-front=Q-rear) printf(队列为空 !n); return (ERR
24、OR); e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return (OK); /DeQueue() end void display(SqQueue *Q) if(Q-front=Q-rear) printf(队列为空 !n); int i=Q-front; while(i+1)%MAXQSIZE!=Q-rear) printf(%c-,Q-basei); i+; printf(n); int main() QElemType e; int choice; SqQueue Q; InitQueue(&Q); printf(=n); print
25、f(0、退出 n); printf(1、入队 n); printf(2、出队 n); printf(3、显示队列元素n); printf(=n); do printf(你操作选择是 (0-3):); scanf(%d,&choice); switch(choice) case 1: fflush(stdin);/清除输入缓冲区名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 16 页 - - - - - - - - - printf(请输入要入队的字符或字符串, 以 #
26、结束 :); while(e=getchar()!=#) EnQueue(&Q,e); break; case 2: DeQueue(&Q,e); break; case 3: display(&Q); while(choice0&choice=3); return 0; （2）运行结果（3）结果分析循环队列通过设置队首和队尾实现先进后出功能实验总结：1.在本次试验中我学会了如何实现的栈的顺序存储以及链式存储。2.以及懂得了栈的基本特性：仅在表尾进行删除和插入操作、先进后出。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 16 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 16 页 - - - - - - - - -