论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

数据结构辅导---栈和队列(2)

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:32

3. 把中缀表达式转换为后缀表达式的算法
    设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中,转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知:转换前后,表达式中的数值项的次序不变,而运算符的次序发生了变化,由处在两个运算对象的中间变为处在两个运算对象的后面,同时去掉了所有的括号。为了使转换正确,必须设定一个运算符栈,并在栈底放入一个非凡算符,假定为’@’字符,让它具有最低的运算符优先级,假定为数值0,此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符,待它的两个运算对象都放入到后缀表达式以后,再令其出栈并写入到后缀表达式中。
    把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。若碰到的是空格则认为是分隔符,不需要进行处理;若碰到的是数字或小数点,则直接写入到s2中,并在每个数值的最后写入一个空格;若碰到的是左括号,则应把它压入到运算符栈中,待以它开始的括号内的表达式转换完毕后再出栈;若碰到的是右括号,则表明括号内的中缀表达式已经扫描完毕,把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中;若碰到的是运算符,当该运算符的优先级大于栈顶运算符的优先级(加减运算符的优先级设定为1,乘除运算符的优先级设定为2,在栈中保存的非凡运算符’@’和’(’的优先级设定为0)时,表明该运算符的后一个运算对象还没有被扫描并放入到s2串中,应把它暂存于运算符栈中,待它的后一个运算对象从s1串中读出并写入到s2串中后,再另其出栈并写入s2串中;若碰到的运算符的优先级小于等于栈顶运算符的优先级,这表明栈顶运算符的两个运算对象已经被保存到s2串中,应将栈顶运算符退栈并写入到s2串中,对于新的栈顶运算符仍继续进行比较和处理,直到被处理的运算符的优先级大于栈顶运算符的优先级为止,然后另该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时,把栈中剩余的运算符依次退栈并写入到后缀表达式中,再向s2写入表达式结束符’@’和字符串结束符’\0’,整个转换过程就处理完毕,在s2中就得到了转换成的后缀表达式。
    例如,设中缀算术表达式s1为:10+(18+9*3)/15-6@,使用的运算符栈用R表示,则转换过程如下:
    (1)开始时存放后缀表达式的字符串s2为空,R中压入有’@’算符,它具有最低的优先级0:
   

                    
@                    
  
(2)当扫描到s1中的左括号时,s2和R中的数据变化如下:
1 0                   
@ + (                  

    (3)当扫描到s1中的数值3时,s2和R中的数据变化为:
1 0   1 8  9  3            
@ + ( + *                

    (4)当扫描到s1中的右括号时,s2和R变为:
1 0   1 8  9  3  * +         
@ +                   

    (5)当扫描到s1中的数值15时,s2和R又变为:
1 0   1 8  9  3  * + 1 5       
@ + /                  

    (6)当扫描到s1中的’@’字符时,s2和R为:
1 0   1 8  9  3  * + 1 5  / + 6   
@ -                   

1 0   1 8  9  3  * + 1 5  / + 6  - @ Ù
    (7)当整个处理过程结束后,R栈为空,s2为:

    将中缀算术表达式转换为后缀算术表达式的算法描述如下:
         void Change(char* s1, char* s2)
                //  将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式
        {
         Stack R;  //  定义用于暂存运算符的栈
            InitStack(R);  //  初始化栈
         Push(R,'@');  //  给栈底放入'@'字符,它具有最低优先级0
         int i,j;
         i=0;  //  用于指示扫描s1串中字符的位置,初值为0
         j=0;  //  用于指示s2串中待存字符的位置,初值为0
         char ch=s1[i];  //  ch保存s1串中扫描到的字符,初值为第一个字符
         while(ch!='@')
         {        //  顺序处理中缀表达式中的每个字符
          if(ch==' ')
             //  对于空格字符不做任何处理,顺序读取下一个字符
           ch=s1[++i]; 
          else if(ch=='(')
          {    //  对于左括号,直接进栈
           Push(R,ch);
           ch=s1[++i];
          }
          else if(ch==')')
          {    //  对于右括号,使括号内的仍停留在栈中的运算符依次
            //  出栈并写入到s2中
           while(Peek(R)!='(')
                        s2[j++]=Pop(R);
           Pop(R);  //  删除栈顶的左括号
           ch=s1[++i];
          }
          else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
          {    //  对于四则运算符,使暂存在栈中的不低于ch优先级
            //  的运算符依次出栈并写入到s2中
           char w=Peek(R);
           while(Precedence(w)>=Precedence(ch))
                    {    //   Precedence(w)函数返回运算符形参的优先级
            s2[j++]=w;
            Pop(R); w=Peek(R);
           }
           Push(R,ch);  //  把ch运算符写入栈中
           ch=s1[++i];
          }
                else
                {  //  此处必然为数字或小数点字符
           while(isdigit(ch)||ch=='.')
           {    //  把一个数值中的每一位依次写入到s2串中
            s2[j++]=ch; 
            ch=s1[++i];
           }
           s2[j++]=' '; //  被转换后的每个数值后放入一个空格
          }
         }
          //  把暂存在栈中的运算符依次出栈并写入到s2串中
         ch=Pop(R);
         while(ch!='@') {
          if(ch=='(') {
           cerr<<"expression error!"<<endl;
           exit(1);
          }
          else {
              s2[j++]=ch;
              ch=Pop(R);
          }
         }
          //  在后缀表达式的末尾放入表达式结束符和字符串结束符
         s2[j++]='@';
         s2[j++]='\0';
        }
    求运算符优先级的Precedence函数为:
        int Precedence(char op)
               //  返回运算符op所对应的优先级数值
        {
         switch(op)
         {
          case '+':
                case '-':
           return 1;  //  定义加减运算的优先级为1
                case '*':
          case '/':
           return 2;  //  定义乘除运算的优先级为2
           case '(':
          case '@':
          default:
           return 0;  //  定义在栈中的左括号和栈底字符的优先级为0
         }
        }
    在转换算法中,中缀算术表达式中的 每个字符均需要扫描一遍,对于扫描到的每个运算符,最多需要进行入栈、出栈和写入后缀表达式这三次操作,对于扫描到的数字或小数点,只需要把它直接写入到后缀表达式即可。所以,此算法的时间复杂度为O(n),n为后缀表达式中字符的个数。该算法需要使用一个运算符栈,需要的深度不会超过中缀表达式中运算符的个数,所以此算法的空间复杂度至多也为O(n)。
    利用表达式的后缀表示和堆栈技术只需要两遍扫描就可完成中缀算术表达式的计算,显然比直接进行中缀算术表达式计算的扫描次数要少得多。
    在上述讨论的中缀算术表达式求值的两个算法中,把中缀表示转换为后缀表示的算法需要使用一个字符栈,而进行后缀表达式求值的算法又需要使用一个浮点数栈,这两个栈的元素类型不同,所以栈的类型无法作为全局量来定义,栈运算的函数也无法适应这种要求。为了解决这个问题,必须把Stack栈类型定义为模板类,把栈运算的函数定 义为该类的公用成员函数,通过调用成员函数来实现栈的运算。这里对此不作深入讨论,留给读者作为练习。
    假定采用类模板来定义Stack类和编写计算中缀算术表达式值的程序,若执行下面的主程序:
        void main()
        {
         char a[30];
         char b[30];
         cout<<"请输入一个以'@'字符结束的中缀算术表达式:"<<endl;
         cin.getline(a,sizeof(a));  //  从键盘上输入一行表示中缀算术表达
                  //  式的字符串存入到字符数组a中
         Change(a,b);
         cout<<"对应的后缀算术表达式为:"<<endl;
         cout<<b<<endl;
         cout<<"求值结果为:"<<Compute(b)<<endl;
        }
    则得到的显示结果如下:
          请输入一个以'@'字符结束的中缀算术表达式:
          12+(3*(20/4)-8)*6@
          对应的后缀算术表达式为:
          12 3 20 4 /*8 -6 *+@
          求值结果为:54

三、队列
  
    1. 队列的定义
    队列(Queue)简称队,它也是一种运算受限的线性表,其限制是仅答应在表的一端进行插入,而在表的另一端进行删除。我们把进行插入的一端称作队尾(rear),进行删除的一端称作队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素;从队列中删除元素称为离队或出队,元素离队后,其后继元素就成为队首元素。由于队列的插入和删除操作分别是在各自的一端进行的,每个元素必然按照进入的次序离队,所以又把队列称为先进先出表(First In First Out, 简称FI
FO)。
    在日常生活中,人们为购物或等车时所排的队就是一个队列,新来购物或等车的人接到队尾(即进队),站在队首的人购到物品或上车后离开(即出队),当最后一人离队后,则队列为空。
    例如,假定有a,b,c,d四个元素依次进队,则得到的队列为(a,b,c,d),其中字符a为队首元素,字符d为队尾元素。若从此队中删除一个元素,则字符a出队,字符b成为新的队首元素,此队列变为(b,c,d);若接着向该队列插入一个字符e,则e成为新的队尾元素,此队列变为(b,c,d,e);若接着做三次删除操作,则队列变为(e),此时只有一个元素e,它既是队首元素又是队尾元素,当它被删除后队列变为空。

    2. 队列的存储结构
    队列的存储结构同线性表和栈一样,既可以采用顺序结构,也可以采用链接结构。
    (1) 队列的顺序存储结构
    队列的顺序存储结构需要使用一个数组和两个整型变量来实现,利用数组来顺序存储队列中的所有元素,利用两个整型变量来分别存储队首元素和队尾元素的下标位置,分别称它们为队首指针和队尾指针。假定存储队列的数组用queue[QueueMaxSize]表示,队首和队尾指针分别用front和rear表示,则元素类型为ElemType的队列的顺序存储类型可定义为:
     ElemType queue[QueueMaxSize];
     int front, rear;
    其中QueueMaxSize为一个整型全局常量,需事先通过const语句定义,由它确定顺序队列(即顺序存储的队列)的最大长度,即最多能够存储的元素个数。当然,队列的顺序存储空间也可以采用动态分配,此时用于决定最大长度的量可以为全局常量,也可以为全局或局部变量。如在一个函数的函数体中使用下面语句能够为一个队列分配长度为n的数组空间,该数组名仍用queue表示。
     ElemType* queue=new ElemType[n];
    队列的顺序存储类型同样可以用一个记录类型来表示,假定记录类型名为Queue,则该类型定义为:
        struct Queue {
         ElemType queue[QueueMaxSize];
         int front, rear;
        };
  假定一个队列的当前状态如图4-10(a)所示,此时已经有a,b,c三个元素相继出栈(为了同队列中的元素相区别,把它们分别括了起来),队首指针front的值为3,指向的队首元素为d,队尾指针的值为7,指向的队尾元素为h;若接着插入一个新元素i,则队列的当前状态如图4-10(b)所示;若再接着删除一个元素,则变为图4-10(c)所示。

         0    1    2    3    4    5    6    7    8           QueueMaxSize-1
        (a)  (b)  (c)   d    e     f   g     h
                
                       front                rear
                                 (a)
 
         0    1    2    3    4    5    6    7    8           QueueMaxSize-1
        (a)  (b)  (c)   d     e    f    g    h    i

                       front                     rear
                                 (b)

         0    1    2    3    4    5    6    7    8           QueueMaxSize-1
        (a)  (b)  (c)  (d)   e    f    g    h    i

                            front                rear
                                 (c)

                     图4-10 顺序队列的插入和删除操作示意图

    每次向队列插入一个元素,需要首先使队首指针后移一个位置,然后再向这个位置写入新元素。当队尾指针指向数组空间的最后一个位置QueueMaxSize-1时,若队首元素的前面仍存在空闲的位置,则表明队列未占满整个数组空间,下一个存储位置应是下标为0的空闲位置,因此,首先要使队尾指针指向下标为0的位置,然后再向该位置写入新元素。通过语句rear=(rear+1)%QueueMaxSize可使存储队列的整个数组空间变为首尾相接的一个环(称此为循环队列),当rear指向最后一个存储位置时,下一个所求的位置自动为数组空间的开始位置(即下标为0的位置)。
    同对线性表和栈的插入一样,每次在进行队列插入前,也要判定队列是否已满(即数组空间是否已被用完),若是则停止插入,终止程序运行,否则可向队列中插入新元素。若队尾指针的下一个位置(采用(rear+1)%QueueMaxSize计算出来)恰是队首指针front所指的位置,则表明队列已满,可知判定队满的条件是(rear+1)%QueueMaxSize==front。从另一方面看,若队首指针和队尾指针已经指向了同一个位置,则表明队列中只有一个元素,当删除该元素后,队列为空,队尾指针不变,而队首指针指向了下一个位置,此时队尾指针的下一个位置正好也是队首指针所指的位置,由此可知,当条件(rear+1)%QueueMaxSize==front成立时,可能是队满的情况,也可能是队空的情况。为了区别这两种情况,可设置一个标记,当进行插入操作后,置该标记为1,当进行删除操作后,置该标记为0。在标记为1的情况下,上述条件成立则表明队列已满,在标记为0的情况下,上述条件成立则表明队列为空。为了省去设置一个标记的麻烦,通常采用的处理方法是:让front指针不是指向队首元素的位置,而是指向它的前一个位置,当上述条件成立时队列必然为满,当队首指针等于队尾指针时队列为空,此时整个数组空间只能利用QueueMaxSize-1个存储位置,而不是QueueMaxSize个存储位置。
    在顺序队列中进行插入和删除时,不需要比较和移动任何元素,只需要修改队尾和队首指针,并向队尾写入元素或从队首取出元素,所以其时间复杂性为O(1)。
    (2) 队列的链接存储结构
     队列的链接存储结构也是通过由结点构成的单链表实现的,此时只答应在单链表的表头进行删除和在单链表的表尾进行插入,因此它需要使用两个指针:队首指针front和队尾指针rear。用front指向队首(即表头)结点的存储位置,用rear指向队尾(即表尾)结点的存储位置。用于存储队列的单链表简称链接队列或链队。假定链队中的结点类型仍采用第二章定义的LNode结点类型,那么队首和队尾指针为LNode*指针类型。若把一个链队的队首指针和队尾指针定义在一个记录类型中,并假定该记录类型用标识符LinkQueue表示,则定义如下:
        struct LinkQueue {
         LNode* front;
         LNode* rear;
        };
    其中LNode结点类型重写如下:
        struct LNode {
         ElemType data;
         LNode* next;
        };


                                        4-12 链队的插入和删除操作示意图
  对链队的插入和删除操作同样不需要比较和移动元素,只需要修改个别相关指针和进行结点的动态分配或回收操作,所以其时间复杂度为O(1)。另外,使用链队不存在队满的问题,因为它使用的结点是动态分配的,只要内存中动态存储区仍有可用空间,就可以得到一个新结点,使之插入到链队中;链队也可能为空,此时front和rear指针均为空。
    3. 队列的抽象数据类型
    队列的抽象数据类型中的数据部分为具有ElemType元素类型的一个队列,它可以采用任一种存储结构实现;操作部分包括元素进队、出队、读取队首元素、检查队列是否为空等。下面给出队列的抽象数据类型的具体定义:
ADT QUEUE is
        Data:
            采用顺序或链接方式存储的栈,假定其存储类型
            用QueueType标识符表示。
        Operation:
            void InitQueue(QueueType& Q);
                 file://初始化队列Q,即置Q为空
            void ClearQueue(QueueType& Q);
                 file://清除队列Q中的所有元素,使之成为一个空队
            int QueueEmpty(QueueType& Q);
                file://判定Q是否为空,若是则返回1,否则返回0
            ElemType QFront(QueueType& Q);
                file://返回队首元素,但不改变队列状态
            void QInsert(QueueType& Q, const ElemType& item);
                file://将新元素item的值插入到队尾
            ElemType QDelete(QueueType& Q);
                file://从队列Q中删除队首元素并返回之
            int QueueFull(Queue& Q)
                file://若队列已满则返回1,否则返回0,此函数为顺序
                file://存储的队列所特有
        end QUEUE
    假定队列q的元素类型为整型int,下面给出调用上述操作的一些例子。
     (1) InitQueue(q);  file://把队列置空
     (2) QInsert(q,20);  file://元素20进队
     (3) int x=5; QInsert(q,10*x);  file://元素10*x的值50进队
     (4) cout<<QFront(q)<<endl;  file://输出队首元素20
     (5) QDelete(q);  file://删除队首元素20
     (6) cout<<(x=QDelete(q))<<endl; 
                  file://删除队首元素50,把它赋给x同时输出
     (7) x=QueueEmpty(q);  file://因队列为空,返回1并赋给x
     (8) while(!QueueEmpty(q)) cout<<QDelete(q)<<” ”;  file://依次输出队
                file://列q中的所有元素,因q已经为空,所以不会得到任何输出
    4. 队列运算的实现
    同线性表和栈一样,队列运算(操作)的具体实现取决于队列的存储结构,存储结构不同,其算法描述也不同。下面分别给出队列的运算在顺序和链接两种存储结构上的实现的算法。
    (a) 队列运算在顺序存储结构上的实现
    假定采用Queue记录类型的对象Q来表示顺序存储的队列,则在Q上进行各种队列运算的算法描述如下:
    (1) 初始化队列
        void InitQueue(Queue& Q)
            file://把队首和队尾指针置为同一下标值0,表示队空
        {
         Q.front=Q.rear=0;
        }
    (2) 把一个队列清除为空
        void ClearQueue(Queue& Q)
            file://对于顺序队列,此算法与初始化队列的算法相同
        {
         Q.front=Q.rear=0;
        }
    (3) 检查一个队列是否为空
        int QueueEmpty(Queue& Q)
            file://当队首与队尾指针相同时表示队空,返回1,否则返回0
        {
         return Q.front==Q.rear;
        }
    (4) 读取队首元素
        ElemType QFront(Queue& Q)
            file://返回队首元素,但不改变队列状态
        {
         if(Q.front==Q.rear)
         {    file://队列为空时退出程序运行
          cerr<<"Queue is empty!"<<endl;
          exit(1);
         }
         return Q.queue[(Q.front+1)%QueueMaxSize];
                 file://队首元素是队首指针的下一个位置中的元素
        }
    (5) 向队列插入元素
        void QInsert(Queue& Q, const ElemType& item)
             file://将新元素item的值插入到队尾
        {
         int k=(Q.rear+1)%QueueMaxSize;
             file://求出队尾的下一个位置
         if(k==Q.front)
         {      file://若对列已满则终止程序运行
          cerr<<"Queue overflow!"<<endl;
          exit(1);
         }
         Q.rear=k;  file://修改队尾指针使之指向下一个位置
         Q.queue[k]=item;  file://item的值被赋给新的队尾位置
        }
    (6) 从队列中删除元素
        ElemType QDelete(Queue& Q)
            file://删除队首元素并返回之
        {
         if(Q.front==Q.rear)
         {     file://若队列为空则终止运行
          cerr<<"Queue is empty!"<<endl;
          exit(1);
         }
            Q.front=(Q.front+1)%QueueMaxSize;
                file://修改队首指针使之后移一个位置
         return Q.queue[Q.front];
                file://返回队首元素
        }
    (7) 检查一个队列是否已满
        int QueueFull(Queue& Q)
              file://若队列已满则返回1,否则返回0,此函数为顺序队列所特有
        {
         return (Q.rear+1)%QueueMaxSize==Q.front;
        }
    (b) 队列运算在链接存储结构上的实现
    假定采用LinkQueue类型的对象HQ来表示链接存储的队列,则在HQ上进行各种队列运算的算法描述如下:
    (1) 初始化链队
        void InitQueue(LinkQueue& HQ)
            file://初始化链队,即把队首和队尾指针置为空,则为置队空
        {
         HQ.front=HQ.rear=NULL;
        }
    (2) 清除链队为空
        void ClearQueue(LinkQueue& HQ)
            file://清除链队中的所有结点,使之成为空队
        {
         LNode* p=HQ.front;
         while(p!=NULL) {
          HQ.front=HQ.front->next;
          delete p;
          p=HQ.front;
         }  file://此循环结束后,所有结点被清除,队首指针变为空
         HQ.rear=NULL;  file://置队尾指针为空
        }
    (3) 检查链队是否为空
        int QueueEmpty(LinkQueue& HQ)
            file://若链队为空则返回1,否则返回0
        {
         return HQ.front==NULL;
              file://判定队首或队尾任一个指针是否为空即可
        }
    (4) 读取队首元素
        ElemType QFront(LinkQueue& HQ)
            file://读取链队中的队首元素
        {
         if(HQ.front==NULL)
         {      file://若链队为空则终止执行
          cerr<<"Linked queue is empty!"<<endl;
          exit(1);
         }
         return HQ.front->data;  file://返回队首元素
        }
    (5) 向链队中插入一个元素
        void QInsert(LinkQueue& HQ, const ElemType& item)
            file://使新元素item的值插入链队
        {
         LNode* newptr=new LNode;
             file://得到一个由newptr指针所指向的新结点
         if(newptr==NULL) {  file://若内存动态存储空间用完则终止程序
          cerr<<"Memory allocation failare!"<<endl;
          exit(1);
         }
         newptr->data=item;  file://把item的值赋给新结点的值域
         newptr->next=NULL;  file://把新结点的指针域置空
         if(HQ.rear==NULL)
          HQ.front=HQ.rear=newptr;
                 file://若链队为空,则新结点既是队首结点又是队尾结点
         else
          HQ.rear=HQ.rear->next=newptr;  file://依次修改队尾结点的
                 file://指针域和队尾指针使之指向新的队尾结点
        }
    (6) 从队列中删除一个元素
        ElemType QDelete(LinkQueue& HQ)
            file://从链队中删除队首元素
        {
         if(HQ.front==NULL) {  file://若链队为空则终止运行
          cerr<<"Linked queue is empty!"<<endl;
          exit(1);
         }
            ElemType temp=HQ.front->data;  file://暂存队首元素以便返回
         LNode* p=HQ.front;  file://暂存队首指针以便回收队首结点
         HQ.front=p->next;  file://使队首指针指向下一个结点
         if(HQ.front==NULL) 
          HQ.rear=NULL;  file://若链队变为空,则需同时使队尾指针变为空
         delete p;  file://回收原队首结点
         return temp;  file://返回被删除的队首元素
        }
    5. 使用队列的程序举例
    程序1:
        #include<iostream.h>
        #include<stdlib.h>
        const int QueueMaxSize=6;
        typedef int ElemType;
        struct Queue {
         ElemType queue[QueueMaxSize];
         int front, rear;
        };
        #include"queue.h"  file://该头文件保存着对顺序队列进行各种操作的算法
        void main()
        {
         Queue q;
         InitQueue(q);
         for(int i=0; i<6; i++)
         {
          int x=rand()%100;
          int y=rand()%100;
          if(!QueueFull(q)) {
           QInsert(q,x);
           cout<<x<<" 进队, ";
          }
          if(!QueueFull(q)) {
           QInsert(q,y);
           cout<<y<<" 进队";
          }
                cout<<endl;
          cout<<QDelete(q)<<" 出队"<<endl;
         }
         cout<<endl;
         while(!QueueEmpty(q)) {
             cout<<QDelete(q)<<" 出队"<<endl;
         }
        }
    此程序使用一个长度为6的顺序队列,利用此队列保存由计算机产生的随机数。主函数中的for循环体共执行6次,每次执行时首先产生出两个100以内的随机整数,接着在队列未满时入队,然后进行一次出栈操作,在主函数的最后使队列中的所有元素依次出队。该程序的运行结果为:
          41 进队, 67 进队
          41 出队
          34 进队, 0 进队
          67 出队
          69 进队, 24 进队
          34 出队
          78 进队, 58 进队
          0 出队
          62 进队,
          69 出队
          5 进队,
          24 出队
          78 出队
          58 出队
          62 出队
          5 出队
    程序2:
        #include<iostream.h>
        #include<stdlib.h>
        typedef int ElemType;
        struct LNode {
         ElemType data;
         LNode* next;
        };
        struct LinkQueue {
         LNode* front;
         LNode* rear;
        };
        #include"linkqueue.h"  file://此头文件保存着对链队的各种操作的算法
        void main()
        {
         LinkQueue q1,q2;
         InitQueue(q1);
         InitQueue(q2);
         for(int i=0; i<20; i++)
         {
          int x=rand()%100;
                cout<<x<<" ";
          if(x%2==1)
           QInsert(q1,x);  file://用q1链队存放奇数
          else
           QInsert(q2,x);  file://用q2链队存放偶数
         }
            cout<<endl;
         while(!QueueEmpty(q1)&&!QueueEmpty(q2))
         {    file://每一行输出一个奇数和一个偶数,直到任一队列空为止
          cout<<QDelete(q1)<<" "<<QDelete(q2)<<endl;
         }
        }
    此程序使用了两个链队q1和q2,用来分别存储由计算机随机产生的20个100以内的奇数和偶数,然后每行输出q1和q2中的一个值,即奇数和偶数配对输出,直到任一队列为空时止。该程序的运行结果为:
          41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
          41 34
          67 0
          69 24
          5 78
          45 58
          81 62
          27 64
          61 42
          91 36
    6. 队列的应用简介
    在后面的章节中将会看到队列在具体算法中的应用,这里仅从两个方面来简述队列在计算机科学领域所起的作用。第一个方面是解决主机与外部设备之间速度不匹配的问题,第二个方面是解决由多用户引起的资源竞争问题。对于第一个方面,仅以主机和打印机之
间速度不匹配的问题为例作一下简要说明。主机输出数据给打印机打印,输出数据的速度比打印数据的速度要快得多,若直接把输出的数据送给打印机打印,由于速度不匹配,显然是不行的。所以解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依次写入到这个缓冲区中,写满后就暂停输出,转去做其它的事情;打印机就从缓冲区中按照先进先出的原则依次取出数据并打印,打印完后再向主机发出请求,主机接到请求后再向缓冲区写入打印数据,这样做既保证了打印数据的正确,又使主机提高了效率。由此
可见,打印数据缓冲区中所存储的数据就是一个队列。对于第二个方面,CPU(即中心处理器,它包括运算器和控制器)资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上,有多个用户需要CPU各自运行自己的程序,它们分别通过各自终端向操作系统提出占用CPU的请求,操作系统通常按照每个请求在时间上的先后顺序,把它们排成一个队列,每次把CPU分配给队首请求的用户使用,当相应的程序运行结束或用完规定的时间间隔后,则令其出队,再把CPU分配给新的队首请求的用户使用,这样既满足了每个用户的请求,又使CPU能够正常运行。关于队列在这两个方面应用的具体情况将会在操作系统课程中讨论。
上一篇:{应用}数据结构辅导---栈和队列(1) 人气:8206
下一篇:{应用}迷宫探路II 人气:7043
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程