栈和队列的基本操作.doc

《栈和队列的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.《数据结构与算法》实验报告专业班级姓名学号实验项目实验二栈和队列的基本操作。实验目的1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。实验内容题目1：进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法提示：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要X不为0重复做下列动作将X%R入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素题目2：利用队列的方式实现杨辉三角的输出。

2、算法设计分析（一）数据结构的定义1、栈的应用实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。栈抽象数据结构描述typedefstructSqStack/*定义顺序栈*/{int*base;/*栈底指针*/int*top;/*栈顶指针*/intstacksize;/*当前已分配存储空间*/}SqStack;2、队列的应用由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成杨辉三角的递归性。即，利用要出队的元素来不断地构造新的

3、进队的元素，即在第N行出队的同时，来构造杨辉三角的第N+1行，从而实现打印杨辉三角的目的。..队列抽象数据结构描述typedefstructSeqQueue{intdata[MAXSIZE];intfront;/*队头指针*/intrear;/*队尾指针*/}SeqQueue;（二）总体设计1、栈（1）主函数：统筹调用各个函数以实现相应功能intmain()（2）空栈建立函数：对栈进行初始化。intStackInit(SqStack*s)（3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。intstackempty(SqStack*s)（4）入栈函数：将元素逐个输

4、入栈中。intPush(SqStack*s,intx)（5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。intPop(SqStack*s,intx)（6）进制转换函数：将十进制数转换为R进制数intconversion(SqStack*s)2、队列（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）空队列建立函数：对队列进行初始化。SeqQueue*InitQueue()（3）返回队头函数：判断队是否为空，若不为空则返回队头元素。intQueueEmpty(SeqQueue*q)（4）入队函数：将元素逐个输入队列中。voidEnQueue(SeqQueue*q,

5、intx)（5）出队函数：若队列不空，则删除队列元素，并用x返回其值。intDeQueue(SeqQueue*q)（6）计算队长函数：计算队列的长度。intQueueEmpty(SeqQueue*q)（7）输出杨辉三角函数：按一定格式输出杨辉三角。voidYangHui(intn)（三）各函数的详细设计：1、栈（1）intmain()主函数定义s为栈类型调用函数建立空栈..调用进制转换函数返回0值（2）intStackInit(SqStack*s)空栈建立函数动态分配内存判断分配成功并返回相应的值若成功，初始化存储空间（3）intstackempty(SqStack*s)判断栈空函数若栈

6、为空，返回0，否则返回1（4）intPush(SqStack*s,intx)入栈函数比较栈中元素所占空间与已分配存储空间若栈满，追加存储空间若存储失败则返回0存储空间不够，添加增量逐个输入数据元素返回x的值（5）intPop(SqStack*s,intx)出栈函数如果栈为空，则返回0若栈不空，则删除栈顶元素，用x返回其值（6）：intconversion(SqStack*s)进制转换函数输入要转化的十进制数输入要转化为几进制运用求余运算改变进制数运用选择结构控制十六进制的输出方式2、队列（1）voidmain()主函数输入杨辉三角的行数调用杨辉三角输出函数输出杨辉三角（2）SeqQueu

7、e*InitQueue()空队列建立函数动态分配内存建立队列并返还该队列（3）intQueueEmpty(SeqQueue*q)返回队头函数判断队列为空，返回0若不空返回队头元素（4）voidEnQueue(SeqQueue*q,intx)入队函数判断队满若不满，逐个添加元素（5）intDeQueue(SeqQueue*q)出队函数若头指针等于尾指针，顺序队列是空的不能做删除操作否则，删除队列用x返回出队的值（6）intQueueE