数据结构实验队列操作程序设计与调试(验证性实验).docVIP

PAGE PAGE 3 实验一 队列操作程序设计与调试 一、实验目的 1．掌握栈和队列的存储结构。 掌握栈和队列的特点。 掌握栈和队列的基本运算。 二、实验条件 硬件：一台微机 软件：操作系统和C语言（或VC++）环境 三、实验原理 栈和队列是两种特殊的线性表，它们是运算要受到某些限制的线性表，因此也称为限定性的数据结构。 2．栈是限定只有在表的一端进行插入和删除的线性表，允许插入和删除的一端叫栈顶（top），不允许插入和删除的一端为栈底（bottom）。由于只能在一端进行，因此后进入的元素只能先退出，这种结构也叫做“后进先出(Last In First Out ,LIFO)”表。 3. 队列是一种先进先出(First In First Out, FIFO)的线性表，只允许在表的一端进行插入，而在另一端删除元素。 四、实验内容 设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，给出队Q的状态，用程序实现，并显示结果。 （1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。 （2）依次将栈S中的元素插入队Q，直到栈S为空。 五、预习要求 实验前学生必须明确实验内容及实验目的，须持实验预习报告后（提前编制好程序），方可进入实验室进行实验。 六、实验步骤 根据实验内容设计程序流程图； 根据流程图完成主程序设计； 完成入队子程序设计； 完成出队子程序设计； 完成进栈子程序设计； 完成出栈子程序设计； 调试程序； 给出运行结果。 七、实验报告要求 1. 按要求设计程序流程图； 根据流程图编写程序； 写出程序运行结果。 八、思考题 1．队列出队和入队的位置有什么不同？ 2. 如何实现循环队列? 参考程序： #define stacksize 10 #define MAX 6 void main() { int S[stacksize], Q[MAX]={a,b,c,d,e}; /*栈数组S，队列数组Q*/ int top=0, front=MAX-1, rear=4; /*栈顶指针, 队头指针, 队尾指针*/ int py; int i; for (i=0; i5; i++) { DeQueue(Q, py, front, rear); /*出队*/ push(S, py, top); /*入栈*/ } for (i=0; i5; i++) { pop(S, top, py); /*出栈*/ EnQueue(Q, py, front, rear); /*入队*/ } printf(\nThe queue is : ); { /*队中数据循环存储*/ for (i=front+1; iMAX; i++) printf(%c , Q[i]); for (i=0; i=rear; i++) printf(%c , Q[i]); } } int EnQueue(int Q[ ],int x, int *pf, int *pr) /*入队*/ { int front,rear; front=*pf; rear=*pr; if((rear+1)%MAX==front) return(0); else { rear=(rear+1)%MAX; Q[rear]=x; *pr=rear; return(0); } } int DeQueue(int Q[ ], int *py, int *pf, int *pr) /*出队*/ { int front, rear; front=*pf; rear=*pr; if(rear==front) return(0); else { front=(front+1)%MAX; *py=Q[front]; *pf=front; return(0); } }