栈与队列数据结构 课程设计.docx
《栈与队列数据结构 课程设计.docx》由会员分享，可在线阅读，更多相关《栈与队列数据结构 课程设计.docx（15页珍藏版）》请在冰点文库上搜索。
栈与队列数据结构课程设计
实验报告
课程名称数据结构实验及课程设计
实验项目栈和队列的定义及操作
实验仪器PC机一台
系别________信息管理学院____
专业________信息安全_______
班级/学号信安09012009012225
学生姓名郭瑞
实验日期2010-11-19
成绩
指导教师_______林小茶_________
北京信息科技大学
计算机信息管理学院
（课程上机）实验报告
实验课程名称:
数据结构实验及课程设计
专业:
信息安全班级:
信安0901学号:
2009012225姓名:
郭瑞成绩:
实验名称
线性表操作的实现
实验地点
小营机房
实验时间
1.实验目的：
（1）掌握栈的顺序存储和链式存储的概念。
（2）掌握队列的顺序存储和链式存储的概念。
（3）熟练编写相关的程序。
2.实验内容：
编写并调试顺序栈、单链表表示的栈、循环队列、单链表表示的队列的所有操作，并编写主函数对这些函数进行调试。
主函数中要有针对解决实际问题的程序，如回文问题和进制转换问题等。
3.实验要求：
1、预先写好程序。
2、记录调试过程遇到的错误和改正的方法。
3、程序完成后提交到学院的服务器上。
4、源程序代码粘贴到本报告的最后。
4.实验准备：
5.实验过程：
①顺序栈进制转换
#include"stdio.h"
#include"stdlib.h"
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineERROR0
#defineOVERFLOW-2
#defineOK1
typedefintStatus;
typedefintSElemType;
typedefstruct
{int*base;
int*top;
intstacksize;
}SqStack;
intInitStack（SqStack&S）
{
S.base=（（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType）））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush（SqStack&S,SElemTypee）
{
if（S.top-S.base>=S.stacksize）
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*（S.top）=e;
S.top++;
returnOK;
}
StatusPop（SqStack&S,SElemType&e）
{
if（S.top==S.base）returnERROR;
e=*（S.top-1）;
（S.top）--;
returnOK;
}
StatusGetTop（SqStackS,SElemType&e）
{
if（S.top==S.base）returnERROR;
e=*（S.top-1）;
returnOK;
}
StatusStackEmpty（SqStackS）
{
if（S.top==S.base）returnOK;
returnERROR;
}
voidmain（）
{
SqStackS;
intN,e;
InitStack（S）;
printf（"请输入一个数字:
\n"）;
scanf（"%d",&N）;
while（N）{
Push（S,N%16）;
N=N/16;
}
while（!
StackEmpty（S））{
Pop（S,e）;
printf（"%d",e）;
}
printf（"\n"）;
}
②单链表表示的栈
#include"stdio.h"
#include"stdlib.h"
#defineERROR0
#defineOVERFLOW-2
#defineOK1
#defineTRUE1
#defineFALSE0
typedefintStatus;
typedefstructSnode{
intdata;
structSnode*next;
}*LinkStack;
voidInitStack（LinkStack&S）
{
S=NULL;
}
StatusPush（LinkStack&S,inte）
{
LinkStackp;
p=（LinkStack）malloc（sizeof（Snode））;
if（p==NULL）returnERROR;
p->data=e;
p->next=S;
S=p;
returnOK;
}
StatusPop（LinkStack&S,int&e）
{
LinkStackp;
if（S==NULL）returnERROR;
p=S;
e=S->data;
S=S->next;
free（p）;
returnOK;
}
StatusStackEmpty（LinkStackS）
{
if（S==NULL）returnTRUE;
returnFALSE;
}
voidmain（）
{inte;LinkStackS;
inti;
InitStack（S）;
for（i=1;i<=10;i++）
Push（S,i）;
printf（"\n\n"）;
while（!
StackEmpty（S））
{Pop（S,e）;
printf（"%d",e）;
}
printf（"\n"）;
}
③循环队列
#include"stdio.h"
#include"stdlib.h"
#defineERROR0
#defineOVERFLOW-2
#defineOK1
#defineMAXQSIZE100
typedefintStatus;
typedefintQElemType;
typedefstruct
{
int*base;
intfront;
intrear;
}SqQueue;
intInitQueue（SqQueue&Q）
{
Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
if（!
Q.base）exit（OVERFLOW）;
Q.front=Q.rear=0;
returnOK;
}
StatusEnQueue（SqQueue&Q,QElemTypee）
{
if（（Q.rear+1）%MAXQSIZE==Q.front）
returnERROR;
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
returnOK;
}
StatusDeQueue（SqQueue&Q,int&e）
{
if（Q.rear==Q.front）returnERROR;
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
returnOK;
}
voidmain（）
{inte;SqQueueQ;
inti;
InitQueue（Q）;
for（i=1;i<20;i++）
EnQueue（Q,i）;
printf（"\n"）;
for（i=1;i<10;i++）
{
DeQueue（Q,e）;
printf（"%d\t",e）;
}
printf（"\n"）;
}
④单链表表示的队列
#include"stdio.h"
#include"stdlib.h"
#defineERROR0
#defineOVERFLOW-2
#defineOK1
#defineMAXQSIZE100
typedefintStatus;
typedefintQElemType;
typedefstructQnode{
QElemTypedata;
structQnode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;QueuePtrrear;}LinkQueue;
StatusInitQueue（LinkQueue&Q）
{Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）exit（OVERFLOW）;
Q.front->next=NULL;
returnOK;
}
StatusEnQueue（LinkQueue&Q,QElemTypee）
{QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）exit（OVERFLOW）;
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
StatusDeQueue（LinkQueue&Q,QElemType&e）
{QueuePtrp;
if（Q.rear==Q.front）returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）Q.rear=Q.front;
free（p）;returnOK;
}
voidmain（）
{inti;
intx;
LinkQueueQu;
InitQueue（Qu）;
for（i=1;i<20;i++）
EnQueue（Qu,i）;
while（DeQueue（Qu,x）==OK）
printf（"%d\t",x）;
printf（"\n"）;
}
⑤回文
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintboolean;
typedefintSElemType;
typedefintSqQueue;
typedefintQElemType;
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefstruct
{int*base;
int*top;
intstacksize;
}SqStack;
StatusInitStack（SqStack*S）
{/*构造一个空栈S*/
（*S）.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
（*S）.base）
exit（ERROR）;/*存储分配失败*/
（*S）.top=（*S）.base;
（*S）.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush（SqStack*S,SElemTypee）
{/*插入元素e为新的栈顶元素*/
if（（*S）.top-（*S）.base>=（*S）.stacksize）
（*S）.base=（SElemType*）realloc（（*S）.base,（（*S）.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
（*S）.base）
exit（ERROR）;/*存储分配失败*/
（*S）.top=（*S）.base+（*S）.stacksize;
（*S）.stacksize+=STACKINCREMENT;
}
*（（*S）.top）++=e;
returnOK;
}
StatusDestroyStack（SqStack*S）
{/*销毁栈S，S不再存在*/
free（（*S）.base）;
（*S）.base=NULL;
（*S）.top=NULL;
（*S）.stacksize=0;
returnOK;
}
StatusClearStack（SqStack*S）
{/*把S置为空栈*/
（*S）.top=（*S）.base;
returnOK;
}
StatusStackEmpty（SqStackS）
{/*若栈S为空栈，则返回TRUE，否则返回FALSE*/
if（S.top==S.base）
returnTRUE;
else
returnFALSE;
}
StatusGetTop（SqStackS,SElemType*e）
{/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/
if（S.top>S.base）
{
*e=*（S.top-1）;
returnOK;
}
else
returnERROR;
}
StatusPop（SqStack*S,SElemType*e）
{/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
if（（*S）.top==（*S）.base）
returnERROR;
*e=*--（*S）.top;
returnOK;
}
/*
判断一个字符串是否为回文
如果是，返回TRUE.
否则，返回FALSE.
*/
booleancheckHuiWen（char*s）
{
SqStackS;/*定义一个顺5序栈*/
SqQueueQ;/*定义一个顺序队列*/
inti=0;
chare1,e2;
while（s[i]!
='\0'）
{
Push（&S,s[i]）;
EnQueue（&Q,s[i]）;
i++;
}
while（!
StackEmpty（S））
{
Pop（&S,&e1）;
DeQueue（&Q,&e2）;
if（e1!
=e2）
returnFALSE;
}
returnTRUE;
}
voidmain（）
{
chars[30]={"abccba"};
printf（"Pleaseinputastring:
\n"）;
scanf（"%s",s）;
if（checkHuiWen（s））
printf（"%sisaHuiWenString!
\n",s）;
else
printf（"%sisNotaHuiWenString!
\n",s）;
}
6.实验总结：
说明：
1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模版供学生使用；
2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；
5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。
源程序：
升级会员 