您的位置: 网站首页 > 程序开发 > 数据结构 > 第3章 栈和队列 > 【3.7 上 机 实 验】

3.7 上 机 实 验

 

3.7 

3.7.1  实验内容

1)如果用一个数组qu[0..MaxSize-1]表示循环队列时,该队列只有一个尾指针rear,不设队头指针front,而设置计数器count用以记录队列中节点的个数。设计实现队列的4个基本运算算法,即初始化队列、判断队空、进队和出队4个算法。

2)在顺序栈的pushpop操作上,有一个很重要的变量top,当栈为空时将top设为-1,若将它改为0,试问push函数可如何修改?

3)用C语言编写一个完整的程序来处理线性队列的插入和删除。

3.7.2  实验指导

1)设计本题的队列类型如下。

typedef struct

{  

   ElemType data[MaxSize];

   int rear,count;

} QType1;  

则有如下条件:

·    队列为空  rear=0count=0

·    队列为满  count=MaxSize

·    队尾元素前一位置  rear

·    队头元素位置  (rear-count+1+MaxSize) % MaxSize

由此得到队列的4个基本运算算法如下:

void InitQueue(QType1 *&qu)                     /*置队列qu为空*/

{

    qu=(QType1 *)malloc(sizeof(QType1));

    qu->rear=0;

    qu->count=0;

}

int QueueEmpty(QType1 *qu)                          /*判定队列qu是否为空*/

{

    if(qu->count==0)

        return(1);

    else

        return(0);

}

int EnQueue(QType1 *&qu,ElemType x)                 /*将元素x入队列*/

{

    if(qu->count==MaxSize)                          /*队列上溢出*/

        return 0;                                   /*返回出错信息*/

    else

    {

        qu->rear++;

        qu->data[qu->rear]=x;

        qu->count++;

        return 1;                                   /*返回成功信息*/

    }

}

int DeQueue(QType1 *&qu,ElemType &x)                /*删除队列头元素*/

{

    int place;

    if(qu->count==0)                                    /*队列下溢出*/

        return 0;                                       /*返回出错信息*/

    else

    {

        place=(qu->rear-qu->count+1+MaxSize) % MaxSize;/*求头指针位置*/

        x=qu->data[place];

        qu->count--;

        return 1;                                       /*返回成功信息*/

    }

}

2)以程序段中top为一个索引,MAX为栈的最大容量,修改的push函数参考程序段如下:

/*top=0*/

void push(void)

{

    if(top>MAX)

        printf("n\n\Stack is full !/n");

    else{

        printf("\nplease enter an item to stack");

        gets(item[top]);

    top++;}

}

3)用C语言编写完整的处理线性队列插入和删除操作的程序如下:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define Max 20

void enqueue_f(void)                                /*新增函数*/

void dequeue_f(void)                                /*删除函数*/

void list_f(void)                                   /*输出函数*/

 

char item[MAX][20];

int front=0,rear=-1;

 

void main(void)

{

    char option;

    while(1)

    {

        printf("\n*************************");

        printf("\n     <1> insert (enqueue)\n");

        printf("\n     <2> delete (delqueue)\n");

        printf("\n     <3> list\n");

        printf("\n     <4> quitn");

        printf("\n*************************");

        printf("please enter your choice...");

        option=getche();

        switch(option)

        {

            case '1':

                enqueue_f();

                break;

            case '2':

                delqueue_f();

                break;

            case '3':

                list_f();

                break;

            case '4':

                exit(0);

        }

    }

}

 

void enqueue(void)

{

    if(rear>=MAX-1)                         /*当队列已满时,则显示错误*/

        printf("\n\nQueue is full \n");

    else

    {

         rear++;

        printf("\n\nplease enter  item to queue: ");

        gets(item[rear]);

    }

}

 

void dequeue(void)

{

    if(front>rear)                          /*当数据不存在时,则显示错误*/

        printf("\n\nNo item,queue is empty !\n");

    else

    {

        printf("\n\n Item %s deleted\n",item[front]);

        front ++;

    }

}

 

void list_f(void)

{

    int count=0,i;

    if(front>rear)

        printf("\n\nNo item,queue is empty !\n");

    else

    {

        printf("\n\n Item \n");

        printf("--------------");

        for(i=frontli<=rearli++)

        {

            printf("%-20s\n",item[i]);

            count++;

            if(count%20==0) getcha();

        }

        printf("--------------");

        printf("Total item:%d\n",count);

        getch();

    }

}