数据结构栈和队列实验报告.docx

《数据结构栈和队列实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构栈和队列实验报告.docx（9页珍藏版）》请在三一办公上搜索。

1、数据结构栈和队列实验报告一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验环境和方法 实验方法： 综合运用课本所学的知识，用不同的算法实现在不同的程序功能。 结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。 根据实验内容，编译程序。 实验环境：Windows xp Visual C+6.

2、0 三、实验内容及过程描述 实验步骤： 进入Visual C+ 6.0集成环境。 输入自己编好的程序。 检查一遍已输入的程序是否有错，如发现有错，及时改正。 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确，应运行多次，分别检查在不同情况下结果是否正确。 实验内容：编译以下题目的程序并调试运行。 1）、编写一个程序algo3-1.cpp，实现顺的各种基本运算，并在此基础上设计一程序并完成如下功能： 初始化栈s； 判

3、断栈s是否非空； 序栈个主依次进栈元素a,b,c,d,e； 判断栈s是否非空； 输出出栈序列； 判断栈s是否非空； 释放栈。 图3.1 Proj3_1 工程组成 本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。 main InitStack DestroyStack StackEmpty PusPop GetTo图3.2 Proj3_1工程的程序结构图 其中包含如下函数： InitStack(SqStack *&s) /初始化栈S DestroyStack(SqStack *&s) /销毁栈s St

4、ackEmpty(SqStack *s) /判断栈空 Push(SqStack *&s,ElemType e) /进栈 Pop(SqStack *&s,ElemType &e) /出栈 GetTop(SqStack *s,ElemType &e) /取栈顶元素 对应的程序如下： /文件名:algo3-1.cpp #include #include #define MaxSize 100 typedef char ElemType; typedef struct ElemType dataMaxSize; int top; /栈顶指针 SqStack; void InitStack(SqStac

5、k *&s) /初始化栈S s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; /栈顶指针置为-1 void DestroyStack(SqStack *&s) /销毁栈s free(s); bool StackEmpty(SqStack *s) /判断栈空 return(s-top=-1); bool Push(SqStack *&s,ElemType e) /进栈 if (s-top=MaxSize-1) /栈满的情况，即栈上溢出 return false; s-top+; /栈顶指针增1 s-datas-top=e; /元素e放在栈顶指针处 re

6、turn true; bool Pop(SqStack *&s,ElemType &e) /出栈 if (s-top=-1) /栈为空的情况，即栈下溢出 return false; e=s-datas-top; /取栈顶指针元素的元素 s-top-; /栈顶指针减1 return true; bool GetTop(SqStack *s,ElemType &e) /取栈顶元素 if (s-top=-1) /栈为空的情况，即栈下溢出 return false; e=s-datas-top; /取栈顶指针元素的元素 return true; 设计exp3-1.cpp程序如下 /文件名:exp3-1

7、.cpp #include #include #define MaxSize 100 typedef char ElemType; typedef struct ElemType dataMaxSize; int 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(SqSt

8、ack *&s,ElemType &e); extern bool GetTop(SqStack *s,ElemType &e); void main ElemType e; SqStack *s; printf(栈s的基本运算如下: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,(Sta

9、ckEmpty(s)?空:非空); printf( (5)出栈序列:); while (!StackEmpty(s) Pop(s,e); printf(%c ,e); printf(n); printf( (6)栈为%sn,(StackEmpty(s)?空:非空); printf( (7)释放栈n); DestroyStack(s); 运行结果如下： 2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能： 初始化链栈s； 判断链栈s是否非空； 依次进栈a，b，c，d，e； 判断链栈s是否非空； 输出链栈长度； 输出从栈底到栈顶元素； 输出出

10、队序列； 判断链栈s是否非空； 图3.3 Proj3_2工程组成 释放队列。 本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。 main InitStack DestroyStack StackEmpty PusPop GetTo 图3.4 Proj3_2工程的程序结构图 其中包含如下函数： InitStack(LiStack *&s) /初始化栈s DestroyStack(LiStack *&s) /销毁栈 StackEmpty(LiStack *s) /判断栈是否为空 Push(LiStack

11、 *&s,ElemType e) /进栈 Pop(LiStack *&s,ElemType &e) /出栈 GetTop(LiStack *s,ElemType &e) /取栈顶元素 对应的程序如下： /文件名:algo3-2.cpp #include #include typedef char ElemType; typedef struct linknode ElemType data; /数据域 ElemType data; /数据域 struct linknode *next; /指针域 LiStack; void InitStack(LiStack *&s) /初始化栈s s=(Li

12、Stack *)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(s-next=NULL); void Push(LiStack *&s,ElemType e) /进栈 LiStack *p; p=(LiStack *)malloc(si

13、zeof(LiStack); p-data=e; /新建元素e对应的节点*p p-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节点 return true; bool GetTop(LiStack *s,ElemType &e) /取栈顶元素 if (s-nex

14、t=NULL) /栈空的情况 return false; e=s-next-data; return true; 设计 exp3-2.cpp 主程序 /文件名:exp3-2.cpp #include #include typedef char ElemType; typedef struct linknode ElemType data; /数据域 struct linknode *next; /指针域 LiStack; extern void InitStack(LiStack *&s); extern void DestroyStack(LiStack *&s); extern bool

15、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,(StackEmpty(s)?空:非空); printf( (3)依次进栈元素a,b

16、,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-3.cpp，实现顺序环形队列的各种基本运

17、算，并在此基础上设计一个主程序并完成如下功能： 初始化队列q； 判断队列q是否非空； 依次进队列a,b,c； 出队一个元素，输出该元素； 输出队列q的元素个数； 依次进队列元素d,e,f； 图3-5 Proj3_3的工程组成 输出队列q的元素个数； 输出出队序列； 释放队列。 本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。 main InitStack DestroyStack StackEmpty PusPop GetTo图3.6 Proj3_3工程的程序结构图 其中包含如下函数： InitQu

18、eue(SqQueue *&q) /初始化队列 /销毁队列 DestroyQueue(SqQueue *&q) QueueEmpty(SqQueue *q) /判断队列空 enQueue(SqQueue *&q,ElemType e) /进队 deQueue(SqQueue *&q,ElemType &e) /出队 对应的程序如下： /文件名:algo3-3.cpp #include #include #define MaxSize 5 typedef char ElemType; typedef struct ElemType dataMaxSize; int front,rear; /队首

19、和队尾指针 SqQueue; void InitQueue(SqQueue *&q) /初始化队列 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 fal

20、se; q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e; return true; bool 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 5 typedef char ElemType; typedef struct ElemTy

21、pe elemMaxSize; int front,rear; /队首和队尾指针 SqQueue; extern void InitQueue(SqQueue *&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(环形队列基本运

22、算如下:n); printf( (1)初始化队列qn); InitQueue(q); printf( (2)依次进队列元素a,b,cn); if (!enQueue(q,a) 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); else printf( (4)出队一个元素%cn,e); pr

23、intf( (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); 程序运行结果如下： 四、总结 从数据结构的定义看，栈和队列也是一种线性表。其与线性表的不同之处在于栈和队列的相关运算具有特殊性，只是线性表相关运算的一个子集。一般线性表的上的插入、删除运算不受限制，而栈和队列上的插入、删除运算受某种特殊限制。因此。栈和队列也称为操作受限的线性表。