数据结构第二周笔记——线性结构(慕课浙大版本--XiaoYu)下

2.3 队列及实现

队列跟堆栈一样是一种受限制的线性表

什么是队列

队列(Queue)：具有一定操作约束的线性表

1. 插入和删除操作：只能一端插入，而在另一端删除(一般的线性表都可以在任何位置进行插入和删除)
   
2. 跟堆栈相比：堆栈插入和删除都是只能在一端
   
3. 数据插入：入队列(AddQ)
   
4. 数据删除：出队列(DeleteQ)
   
5. 先来先服务(跟堆栈相反)
   
6. 先进先出：FIFO
   

队列的抽象数据类型描述

   类型名称:队列(Queue)

   数据对象集：一个有0个或多个元素的有穷线性表

   操作集：长度为MaxSize的队列Q属于Queue，队列元素item属于ElementType

       

       1.QueueCreateQueue( intMaxSize )：生成长度为MaxSize的空队列；

       2.intIsFullQ(QueueQ,intMaxSize)：判断队列Q是否已满;

       3.voidAddQ(QueueQ,intMaxSize)：将数据元素item插入队列Q中

       4.intIsEmptyQ( QueueQ):判断队列Q是否为空;

       5.ElementTypeDeleteQ( QueueQ):将队头元素从队列中删除并返回

2.3.1 队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成的

   #define MaxSize <储存数据元素的最大个数>

   structQNode{

       ElementTypeData[MaxSize];

       intrear;//指针

       intfront;//指针

   };

typedefstructQNode*Queue;

如果空队列开始时front和rear值都是-1，当插入4个元素并删除2个元素后，front和rear值分别是多少？1和3

顺环队列

1.这种方案：堆栈空和满的判别条件是什么？

根据front rear的相对关系(就是他们的距离)来判别的font rear的取值范围是0 -- n-1

2.为什么会出现空，满无法区分？根本原因？

如果大小是n的话，font跟rear的差距的情况就是n种，队列的装载元素的情况有n+1种

解决方案：

(1)使用额外标记：Size或者tag域

当加入一个元素的时候Szie加1，删除一个元素的时候Size减1，通过Size等于0还是等于n就可以知道空的还是满的

使用标记tag 0 1，当我们插入一个元素的时候tag设为1，删除一个元素的时候tag等于0，当front跟rear相等时不清楚空还是满的时候，观察tag，tag就代表了最后一次操作是插入还是删除，就知道是空还是满

(2)仅使用n-1个数组空间(最多放n-1个元素，留一个空位出来就可以避免front跟rear相等的情况)

(1)入队列

voidAddQ(QueuePtrQ,ElementTypeitem)//item放到队列中 队列使用Queue的结构指针PtrQ来进行表示

{

   if((PtrQ->rear+1)%MaxSize==PtrQ->front){//具体代换：5+1对6求余为0

       printf("队列满");

       return;

   }

   PtrQ->rear= (PtrQ->rear+1)%MaxSize;

   PtrQ->Data[PtrQ->rear] =item;

}

(2)出队列

ElementTypeDeleteQ( QueuePtrQ)

{

   if(PtrQ->front==PtrQ->rear){

       printf("队列空");

       returnERROR;

   }else{

       PtrQ->front= (PtrQ->front+1)%MaxSize;

       returnPtrQ->Data[PtrQ->front];

   }

}

2.3.2 队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front和rear应该分别指向链表的哪一头？

队列的front也可以设在链表的尾？错误，不行的

只能前面做删除(front)，后面做加入(rear)，如果倒过来的话，删掉了就不知道前面一个在哪里了

   

   structNode{

       ElementTypeData;//结点本身的信息

       structNode*Next;//把结点串在一起

   };

structQNode{//链队列结构

   structNode*rear;//指向队尾结点

   structNode*front;//指向队头结点

};

typedefstructQNode*Queue;

QueuePtrQ;

不带头结点的链式队列出队操作的示例

ElementTypeDeleteQ(QueuePtrQ)

{

   structNode*FrontCell;

   ElementTypeFrontElem;

   

   if(PtrQ->front==NULL){

       printf("队列空"); returnERROR;

   }

   FrontCell=PtrQ->front;

   if(PtrQ->front==PtrQ->rear)//若队列只有一个元素

       PtrQ->front=PtrQ->rear=NULL;//删除后队列置为空

   else

       PtrQ->front=PtrQ->front->Next;

   FrontElem=FrontCell->Data;

   free(FrontCell);//释放被删除结点空间

   returnFrontElem;

}

2.4 多项式的加法运算实现

采用不带头结点的单项链表，按照指数递减的顺序排列各项

具体实现代码(数据结构)

structPolyNode{

   intcoef;//系数

   intexpon;//指数

   structPolyNodelink;//指向下一个节点的指针

};

typedefstructPolyNode*Polynomial;

PolynomialP1,P2;

多项式加法运算(算法思路):

两个指针p1和p2分别指向这两个多项式第一个结点，不断循环：

   1.P1->expon==P2->expon(这里比较的其实是指数)：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项

   2.P1->expon>P2->expon：将P1的当前项存入结果多样式，并使P1指向下一项;

   3.P1->expon<P2->expon：将P2的当前项存入结果多样式，并使P2指向下一项;

当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去

演变过程------------------------分割线

接着是=>

函数实现

PolynomialPolyAdd(PolynomialP1.PolynomialP2)

{

   Polynomialfront,rear,temp;//多项式的头是第一个，尾巴第二个，

   intsum;

   rear= (Polynomial) malloc(sizeof(structPolyNode));//临时申请一个空结点作为结果多项式的表头

   front=rear;//由front记录结果多项式链表头结点，申请的空间front都指向它

   while(P1&&P2)//当两个多项式都有非零待处理时(判空)

       switch(Compare(P1->expon,P2->expon)){//比较P1P2这两个项的所指向的当前这个项的指数，第一个值大返回1，第二个值大返回-1，两个值相等返回0

               case1://P1大

                       Attach(P1->coef,P1->expon,&rear);//两个参数分别代表我要拷贝的这一项的系数和指数

                       P1=P1->link;

                       break;//形成的新的项把它接到rear的后面，P1往后挪

               case-1：//P2大

                       Attach(P2->coef,P2->expon,&rear);

                       P2=P2->link;

                       break;

               case0://一样大

                       sum=P1->coef+P2->coef;

                       if(sum)Attach(sum.P1->expon,&rear);//判定，如果为0就不用加到结果多项式里面去，不为零就把sum作为系数跟对于的指数凑在一起，把他接到rear的后面去

                       P1=P1->link;

                       P2=P2->link;

                       break;

       }

   //将未处理完的另一个多项式的所有节点依次复制到结果多项式中去

   for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);//第一个for循环处理P1不空，如果不空就是把P1后面的每一项全部Attach(接到结果多项式的后面的意思)，同时把P1往后挪

   for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);//如果P1不空的话P2肯定就空了，也就把P2后面的每一项一个一个拷贝到rear的后面去

   rear->link=NULL;//指向结果多项式的最后一项

   temp=front;

   front=front->link;//令front指向结果多项式第一个非零项

   free(temp);//释放临时空表头结点  怎么释放？=>将front赋给temp，然后front往后挪，front原来是指向这个临时的表头结点，这个表头结点的下一项就是我们真正的多项式的第一项

   returnfront;//返回结果多样式中这个单项链表的第一个结点

}

问题：如果当前p1指向项的（系数，指数）为（2，4），同时P2指向项为(2，6)，那么循环中的switch是执行哪个case?

case-1

Attach实现

voidAttach(intc,inte,Polynomial*pRear)//传进来的是c跟e的系数跟指数。当前最后一个结点的指针位置传进来的是Polynomial这个类型的指针(Polynomial本身也是指针)，所以pRear实际上是指针的指针

   //C语言是函数常数值传递

{

   PolynomialP;

   

   P= (Polynomial)malloc(sizeof(structPloyNode));//结点类型是struct PolyNode这个类型

   P->coef=c;//对新结点赋值

   P->expon=e;

   P->link=NULL;

   (*pRear)->link=P;//把新申请的结点P插到rear的后面

   *pRear=P;//修改pRear值

}

小白专场

多项式的表示

用链表进行表示

   数据结构设计

   typedefstructPolyNode*Polynomial;//将结构指针定义为一个新的类型叫做Polynomial

structPolyNode{

   intcoef;//系数

   intexpon;//指数

   Polynomiallink;//阈，作为指针指向下一个节点

}

程序框架搭建

intmain()

{

   读入多项式1

   读入多项式2

   乘法运算并输出

   加法运算并输出

       

       return0;

}

需要设计的函数：

   1.读一个多项式

   2.两多项式相乘

   3.两多项式相加

   4.多项式输出

 

   intmain()

{

   PolynomialP1,P2,PP,PS;

   

   P1=ReadPoly();

   P2=ReadPoly();//P1,P2都是链表的结构的指针

   PP=Mult(P1,P2);//Mult是乘法运算，返回的也是一个结构的指针

   PrintPoly(PP);//由PrintPoly来输出多项式

   PS=Add(P1,P2);//加法运算

   PrintPoly(PS);

   

   return0;

}

如何读入多项式

   PolynomialReadPoly()

{

   ....//先读整数再一对一的读入系数跟指数

       scanf("%d",&N);

   ....

       while(N--){//这是读入系数跟指数，放到c跟e里面

       scanf("%d %d",&c,&e);

       Attach(c,e,&Rear);//读的时候是通过指数递降的顺序来读取的，Rear是可以被改变的，Rear是指向目前为止多项式的最后一项

       }

}

//注意：我们是从左到右读入的，而且先读的是指数高的一项，要插到一个链表里面去，然后再读一对数再插进去，再形成一个节点

//再读一对系数指数，再插到多项式里面去，在链表里面也是指数递降的，应该插到原来结果的后面

Rear初始值是多少？

   两种处理方法：

   1.Rear初值为NULL(说明是刚开始的一个节点，这个时候需要申请节点，然后把Rear用NULL改为指向这个节点)

   在Attach函数中根据Rear是否为NULL做不同处理

   如果值不为NULL，因为从第二项开始Rear值就不为NULL了。这个时候直接把新的节点插到Rear的后面。这样的一种处理方式在Attach函数里面他必须判别Rear是NULL还是说不是NULL，因为这两者处理的程序是不一样的

   2.Rear指向一个空结点(程序时更简单)

   需要注意在最后的时候记得把这个空结点释放掉

   

   处理方法2的具体代码：

   voidAttach (intc,inte,Polynomial*pRear)//Polynomial本身也是指针，所以这里的pRear实际是指针的指针(为什么这么做是因为C语言是函数常数直传递)

{

   PolynomialP;

   P= (Polynomial)malloc(sizeof(structPolyNode));

   P->coef=c;//对新结点赋值

   P->expon=e;

   P->link=NULL;

   (*pRear)->link=P;//指针指过去了

   *pRear=P;//修改pRear值，指到P那里去了

}

处理方法2

读入多项式的完整程序

PolynomialReadPoly()

{

   PolynomialP,Rear,t;

   intc,e,N;

   

   scanf("%d",&N);

   P= (Polynomial)malloc(sizeof(structPolyNode));//链表头空结点

   P->link=NULL;

   Rear=P;

   while(N--){

       scanf("%d %d",&c,&e);

       Attach(c,e,&Rear)//将当前项插入多项式尾部

   }

   t=P;P=P->link;free(t);//删除临时生成的头结点  t指向P，P指向P的link  

   returnP;

}

如何将两个多项式相乘

1. 将当前乘法运算转换为加法运算
   

将P1当前项(ci,ei)乘P2多项式，再加到结果多项式里

t1=P1;t2=P2;

P= (Polynomial)malloc(sizeof(structPolyNode));P->link=NULL;//指向空结点的操作

Rear=P;

while(t2){

   Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);

   t2=t2->link;

}

2.逐项插入

将P1当前项(c1i,e1i)乘P2当前项(c2i,e2i)，并插入到结果多项式中。关键是要找到插入位置

初始结果多项式可以由P1第一项乘P2获得(如上)

   

   具体代码如下

   PolynomialMult(PolynomialP1,PolynomialP2)

{

   .......

   t1=P1；t2=P2;

   .......

   while(2){

       //先用P1的第一项乘以P2,得到P

       ........

   }

   t1=t1->link;

   while(t1){

       t2=P2;Rear=P;

       while(t2){

           e=t1->expon+t2->expon;//指数相加

           c=t1->coef*t2->coef;//系数相乘

           ......

           t2=t2->link;

       }

       t1=t1-<link;

   }

   ......

}

以上代码块中有三项省略号的地方需要解释，单独分别列出来在下方进行标记

第一处省略

PolynomialP,Rear,t1,t2,t;

intc,e;

if(!P1||!P2) returnNULL;

t1=P1;t2=P2;

P= (Polynomial)malloc(sizeof(structPolyNode));P->link=NULL;

Rear=P;

第二处

while(t1){

   t2=P2;Rear=P;

   while(t2){

       e=t1->expon+t2->expon;

       c=t1->coef*t2->coef;

   while(Rear->link&&Rear->link->expon>e)

       Rear=Rear->link;

   if(Rear->link&&Rear->link->expon==e){

      if(Rear->link->coef+c)//判别一下加完是否为0，若不为0则直接加进去，若为0就删掉把内存空间释放

          Rear->link->coef+=c;

       else{

           t=Rear->link;

           Rear->link=t->link;

           free(t);

       }

   }else{//不相等就是小于的情况，就需要申请一个结点，然后把c跟e赋给这个结点

       t= (Polynomial)malloc(sizeof(structPolyNode));

       t->coef=c;t->expon=e;

       t->link=Rear->link;

       Rear->link=t;Rear=Rear->link;

   }

       t2=t2->link

   }

   t1=t1->link

}

........

第三处省略

t2 = P; P = P->link;free(t2);

return P;