实验二 栈和队列的应用

一：实验内容：

实现链队列（带头结点）的各种基本运算，完成如下功能：

（1）初始化并建立链队列

（2）入队列

（3）出队列

二：实验目的：

    掌握栈和队列的定义和实现，学习利用栈和队列解决实际问题。

三：问题的实现

数据结构的抽象数据类型定义和说明：

ADT Queue{

数据对象：D={ai|ai∈Elemset,i=1,2,…n,n>=0}

数据关系：R1={<ai-1,ai>}|ai-1,ai∈D, ,i=1,2,…n}

          约定其中a1端为队列头，an端为队列尾

基本操作：InitQueue(LinkQueue &Q)  //构造一个空队列

EnQueue(LinkQueue &Q,int e) //插入元素e为Q的新的队尾元素

           DeQueue(LinkQueue &Q,int &e) //若队列不空，则删除其队头元素，用e返回其值

           GetHead(LinkQueue &Q,int &e)          //逐个取出队头元素，直到全部

} ADT Queue

 

主要的实现思路：首先定义结点类型，链表类型。根据菜单提示做入队出队的操作。每次入队出队后都会将队中的所有元素输出一遍。

四：主要源程序代码（包含程序备注）

typedef struct QNode{               //定义结点类型

  int data;

  struct QNode *next;

}QNode,*QueuePtr;

 

typedef struct {                    //定义链表指针

  QueuePtr front;

  QueuePtr rear;

}LinkQueue;

 

 

void  InitQueue(LinkQueue &Q)  //构造一个空队列

{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//动态分配内存，生成头结点，使头指针，尾指针都指向它；

     if(!Q.front)

     {

         cout<<"内存分配失败！"<<endl;

         return;

     }

     Q.front->next=NULL;    //头指针指向的头结点的指针域为NULL;

}

 

 

//插入元素e为Q的新的队尾元素

void EnQueue(LinkQueue &Q,int e)

{

  QueuePtr p;

  p=(QueuePtr)malloc(sizeof(QNode));//动态分配内存，生成新结点

  if(!p)

  {

         cout<<"内存分配失败！"<<endl;

         return;

     }

  p->data=e; 

  Q.rear->next=p;     //改变头指针的指针域，使其指向新结点p

  Q.rear=p;         //改变尾指针，使其指向新结点p

  p->next=NULL;       //新结点p作为尾指针，故其指针域为NULL

}

 

//若队列不空，则删除其队头元素，用e返回其值

int DeQueue(LinkQueue &Q,int &e)

{

      QueuePtr p;

     if(Q.front==Q.rear)

     {

         cout<<"队列为空！"<<endl;

         return 0;

     }

     else

     {

         p=Q.front->next;          //令p指向队头元素

         e=p->data;

         Q.front->next=p->next;     //令头结点的指针域指向p后面的元素

         if(Q.rear==p)Q.rear =Q.front;     //考虑除了头结点外，只有一个结点的情况

         free(p);      

         return 1;

     }

}

 

int GetHead(LinkQueue &Q,int &e)          //逐个读出队头元素，直到全部

{

QueuePtr first;

    first=Q.front;

 

     cout<<"当前队列中的元素值："<<endl<<endl;  

     while(first!=Q.rear)           

     {

         first=first->next;

         cout<<"  "<<first->data;

        

     }

     return 1;

}

五：总结

1．            主要问题出在如何看到已经插入的结点的数据域，所以构造了逐个”读取头结点”的操作。

2．            做连续插入操作时，要改变的是尾指针的指向，而不是头指针；虽然初始状态下头指针和尾指针都指向头结点，所以做第一个插入时关系不大，但第二次开始就一定要改变尾指针。

3．            出队操作时，要考虑除了头结点外，只有一个结点的情况。删去一个结点后就剩下一个头结点了。

4．            这次仍然出现了这个错误：“项目 : error PRJ0003 : 生成“cmd.exe”时出错。”在工具=> 选项 => 项目和解决方案-> VC++ 目录，加入下面三项:$(SystemRoot)\System32；$(SystemRoot)；$(SystemRoot)\System32\wbem  就运行成功了。