《数据结构栈和队列实验报告.doc》由会员分享,可在线阅读,更多相关《数据结构栈和队列实验报告.doc(11页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、一、实验目得与要求()理解栈与队列得特征以及它们之间得差异,知道在何时使用那种数据结构。(2)重点掌握在顺序栈上与链栈上实现栈得基本运算算法,注意栈满与栈空得条件。()重点掌握在顺序队上与链队上实现队列得基本运算算法,注意循环队队列满与队空得条件。()灵活运用栈与队列这两种数据结构解决一些综合应用问题。二、实验环境与方法实验方法:(一)综合运用课本所学得知识,用不同得算法实现在不同得程序功能。(二)结合指导老师得指导,解决程序中得问题,正确解决实际中存在得异常情况,逐步改善功能.(三)根据实验内容,编译程序。实验环境:inwsxp Viual C+6、0三、实验内容及过程描述实验步骤: 进入V
2、isualC+ 6、集成环境。 输入自己编好得程序。 检查一遍已输入得程序就是否有错(包括输入时输错得与编程中得错误),如发现有错,及时改正. 进行编译与连接。如果在编译与连接过程中发现错误,频幕上会出现“报错信息”,根据提示找到出错位置与原因,加以改正。再进行编译,如此反复直到不出错为止。 运行程序并分析运行结果就是否合理.在运行就是要注意当输入不同得数据时所得结果就是否正确,应运行多次,分别检查在不同情况下结果就是否正确。实验内容:编译以下题目得程序并调试运行.1)、编写一个程序alo3、cp,实现顺序栈得各种基本运算,并在此基础上设计一个主程序并完成如下功能:(1)初始化栈s;()判断栈
3、s就是否非空;()依次进栈元素a,b,c,d,e;(4)判断栈s就是否非空;(5)输出出栈序列;(6)判断栈就是否非空; (7)释放栈。 图3、1 Pro_1 工程组成本工程roj3_得组成结构如图3、所示.本工程得模块结构如图3、2所示.图中方框表示函数,方框中指出函数名,箭头方向表示函数间得调用关系。mainInitStackDestroyStackStackEmptyPushPopGetTop图3、2 Proj3_1工程得程序结构图其中包含如下函数:Inittack(SSt *&s)/初始化栈SDestroyStack(SqStacks)/销毁栈sStackEty(Stac *)/判断栈
4、空Push(SSk &s,ElemTp )/进栈Pop(SqStck *,Eemype &e)/出栈top(SqStac*s,lmTye&e)/取栈顶元素 对应得程序如下: /文件名:algo3-1、cpp#include #include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/栈顶指针 SqStack;void InitStack(SqStack *&s)/初始化栈Ss=(SqStack *)malloc(sizeof(SqStack);s-top=-1;/栈
5、顶指针置为-1void DestroyStack(SqStack *&s)/销毁栈sfree(s);bool StackEmpty(SqStack *s)/判断栈空return(s-top=-1);bool Push(SqStack *&s,ElemType e)/进栈if (s-top=MaxSize-1)/栈满得情况,即栈上溢出return false;s-top+;/栈顶指针增1s-datas-top=e;/元素e放在栈顶指针处return true;bool Pop(SqStack *&s,ElemType &e)/出栈if (s-top=-1)/栈为空得情况,即栈下溢出return
6、false;e=s-datas-top;/取栈顶指针元素得元素s-top-;/栈顶指针减1return true; bool GetTop(SqStack *s,ElemType &e)/取栈顶元素if (s-top=-1)/栈为空得情况,即栈下溢出return false;e=s-datas-top;/取栈顶指针元素得元素return true;设计xp-1、c程序如下/文件名:exp3-1、cpp#include #include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int
7、 top;/栈顶指针 SqStack;extern void InitStack(SqStack *&s);extern void DestroyStack(SqStack *&s);extern bool StackEmpty(SqStack *s);extern bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType &e);extern bool GetTop(SqStack *s,ElemType &e);void main()ElemType e;SqStack *s;printf(栈s得基本运算如
8、下:n);printf( (1)初始化栈sn);InitStack(s);printf( (2)栈为%sn,(StackEmpty(s)?空:非空);printf( (3)依次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空);printf( (5)出栈序列:);while (!StackEmpty(s)Pop(s,e);printf(%c ,e);printf(n);printf( (6)栈为%sn,(StackEmpty(s)?空:非空
9、);printf( (7)释放栈n);DestroyStack(s);运行结果如下:2)、编写一个程序alo32、pp,实现链栈得各种基本运算,并在此基础上设计一个主程序并完成如下功能:(1)初始化链栈s;(2)判断链栈就是否非空;(3)依次进栈,c,d,e;(4)判断链栈就是否非空;(5)输出链栈长度;(6)输出从栈底到栈顶元素;(7)输出出队序列;(8)判断链栈s就是否非空; 图3、3 roj_2工程组成()释放队列。本工程P3_2得组成结构如图、所示。本工程得模块结构如图、4所示。图中方框表示函数,方框中指出函数名,箭头方向表示函数间得调用关系。mainInitStackDestroyS
10、tackStackEmptyPushPopGetTop 图3、 Proj3_2工程得程序结构图其中包含如下函数:nttc(Stak *&s)/初始化栈etroyStack(Litack &)/销毁栈Stackmpy(LiStack*s)/判断栈就是否为空ush(LiSta &s,ElemTye e)/进栈Pp(iStac&s,lemType )/出栈GetTop(iStack*,Eleye)/取栈顶元素对应得程序如下:/文件名:algo3-2、cpp#include #include typedef char ElemType;typedef struct linknodeElemType d
11、ata;/数据域ElemType data;/数据域struct linknode *next;/指针域 LiStack;void InitStack(LiStack *&s)/初始化栈ss=(LiStack *)malloc(sizeof(LiStack);s-next=NULL;void DestroyStack(LiStack *&s)/销毁栈LiStack *p=s,*q=s-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);/此时p指向尾节点,释放其空间bool StackEmpty(LiStack *s)/判断栈就是否为空return
12、(s-next=NULL);void Push(LiStack *&s,ElemType e)/进栈LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;/新建元素e对应得节点*pp-next=s-next;/插入*p节点作为开始节点s-next=p;bool Pop(LiStack *&s,ElemType &e)/出栈LiStack *p;if (s-next=NULL)/栈空得情况return false;p=s-next;/p指向开始节点e=p-data;s-next=p-next;/删除*p节点free(p);/释放*p节点r
13、eturn true;bool GetTop(LiStack *s,ElemType &e)/取栈顶元素if (s-next=NULL)/栈空得情况return false;e=s-next-data;return true;设计 exp3-2、cpp 主程序/文件名:exp3-2、cpp#include #include typedef char ElemType;typedef struct linknodeElemType data;/数据域struct linknode *next;/指针域 LiStack;extern void InitStack(LiStack *&s);exte
14、rn void DestroyStack(LiStack *&s);extern bool StackEmpty(LiStack *s);extern void Push(LiStack *&s,ElemType e);extern bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType &e);void main()ElemType e;LiStack *s;printf(栈s得基本运算如下:n);printf( (1)初始化栈sn);InitStack(s);printf( (2)栈为%sn,(Sta
15、ckEmpty(s)?空:非空);printf( (3)依次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空);printf( (5)出栈序列:);while (!StackEmpty(s)Pop(s,e);printf(%c ,e);printf(n);printf( (6)栈为%sn,(StackEmpty(s)?空:非空);printf( (7)释放栈n);DestroyStack(s);程序运行结果如下:3)、编写一个程序algo3
16、3、p,实现顺序环形队列得各种基本运算,并在此基础上设计一个主程序并完成如下功能:()初始化队列q;()判断队列就是否非空;()依次进队列,c;()出队一个元素,输出该元素;()输出队列q得元素个数;()依次进队列元素d,e,; 图35 roj3_得工程组成(7)输出队列q得元素个数;(8)输出出队序列;()释放队列。本工程Poj得组成结构如图3、所示。本工程得模块结构如图3、6所示。图中方框表示函数,方框中指出函数名,箭头方向表示函数间得调用关系。mainInitStackDestroyStackStackEmptyPushPopGetTop图3、6 roj3_3工程得程序结构图其中包含如下
17、函数:InitQeu(Sqeu)/初始化队列stroyQeue(SQeue )/销毁队列QueeEmpt(SQeu )判断队列空enQuee(Queue q,EeTye e)/进队deeue(SqQuue *q,ElemType e)/出队对应得程序如下:/文件名:algo3-3、cpp#include #include #define MaxSize 5typedef char ElemType;typedef struct ElemType dataMaxSize;int front,rear;/队首与队尾指针 SqQueue;void InitQueue(SqQueue *&q)/初始化
18、队列q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0;void DestroyQueue(SqQueue *&q)/销毁队列free(q);bool QueueEmpty(SqQueue *q)/判断队列空return(q-front=q-rear);bool enQueue(SqQueue *&q,ElemType e)/进队if (q-rear+1)%MaxSize=q-front)/队满上溢出return false;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return true;bool
19、 deQueue(SqQueue *&q,ElemType &e)/出队if (q-front=q-rear)/队空下溢出return false;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return true;设计 exp3-3、cpp 主程序#include #include #define MaxSize 5typedef char ElemType;typedef struct ElemType elemMaxSize;int front,rear;/队首与队尾指针 SqQueue;extern void InitQueue(SqQueu
20、e *&q);extern void DestroyQueue(SqQueue *&q);extern bool QueueEmpty(SqQueue *q);extern bool enQueue(SqQueue *&q,ElemType e);extern bool deQueue(SqQueue *&q,ElemType &e);void main()ElemType e;SqQueue *q;printf(环形队列基本运算如下:n);printf( (1)初始化队列qn);InitQueue(q);printf( (2)依次进队列元素a,b,cn);if (!enQueue(q,a)
21、printf(t提示:队满,不能进队n);if (!enQueue(q,b) printf(t提示:队满,不能进队n);if (!enQueue(q,c) printf(t提示:队满,不能进队n);printf( (3)队列为%sn,(QueueEmpty(q)?空:非空);if (deQueue(q,e)=0) printf(队空,不能出队n);elseprintf( (4)出队一个元素%cn,e);printf( (5)依次进队列元素d,e,fn);if (!enQueue(q,d) printf(t提示:队满,不能进队n);if (!enQueue(q,e) printf(t提示:队满,不能进队n);if (!enQueue(q,f) printf(t提示:队满,不能进队n);printf( (6)出队列序列:);while (!QueueEmpty(q)deQueue(q,e);printf(%c ,e);printf(n);printf( (7)释放队列n);DestroyQueue(q);程序运行结果如下: 四、总结从数据结构得定义瞧,栈与队列也就是一种线性表。其与线性表得不同之处在于栈与队列得相关运算具有特殊性,只就是线性表相关运算得一个子集.一般线性表得上得插入、删除运算不受限制,而栈与队列上得插入、删除运算受某种特殊限制。因此。栈与队列也称为操作受限得线性表.
限制150内