《《队列和数组》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《队列和数组》PPT课件.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.2队列队列3.2.1队列的定义队列的定义n队列队列是只能在一端插入、另一端删除的线性表。是只能在一端插入、另一端删除的线性表。a1 a2 a3 an出队出队入队入队队头队头（删除元素）（删除元素）队尾队尾（插入元素）（插入元素）队列的特性：队列的特性：先进先出先进先出FIFO13.2.2 3.2.2 队列的基本运算队列的基本运算n初始化队列：初始化队列：init_queue(Q)n判断队列是否为空：判断队列是否为空：queue_empty(Q)n取队头元素：取队头元素：queue_front(Q,x)n入队：入队：enqueue(Q,x)n出队：出队：outqueue(Q,x)n判断队列是
2、否为满：判断队列是否为满：queue_full(Q)23.2.3顺序队列顺序队列n以顺序存储方式存储的队列叫做以顺序存储方式存储的队列叫做顺序队列顺序队列。ana1 a2 .0123maxsize-1datafrontQrear类型说明：类型说明：typedef struct typedef struct elementtype dataelementtype datamaxsizemaxsize;/;/存放元素的数组存放元素的数组 int front,rear;/int front,rear;/指向队头的前一个位置和队尾指向队头的前一个位置和队尾seqqueueseqqueue；3n顺序队列
3、会产生顺序队列会产生“假溢出假溢出”n循环队列循环队列frontrear210maxsize-1基本操作：入队：rear=(rear+1)%maxsize;datarear=x;出队：front=(front+1)%maxsize;4难题难题：如何区分循环队列的满和空状态？方法一：设置一个标志，以区分最后一次操作是入队还是出队操作。当头尾两个指针相等时，由该标志判断队列为满或空。方法二：保留一个空间不用，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。5循环队列运算的实现循环队列运算的实现n初始化队列：初始化队列：void init_queue(seqqueue
4、*Q)void init_queue(seqqueue*Q)Q-front=0;Q-rear=0;Q-front=0;Q-rear=0;n判断队列是否为空：判断队列是否为空：BOOL queue_empty(seqqueue Q)BOOL queue_empty(seqqueue Q)if(Q.front=Q.rear)return TRUE;if(Q.front=Q.rear)return TRUE;else return FALSE;else return FALSE;n判断队列是否为满：判断队列是否为满：BOOL queue_full(seqqueue Q)BOOL queue_full
5、(seqqueue Q)if(1+Q.rear)%maxsize=Q.front)return TRUE;if(1+Q.rear)%maxsize=Q.front)return TRUE;else return FALSE;else return FALSE;尾指针的下一个尾指针的下一个位置是头指针所位置是头指针所指位置时为满指位置时为满头尾指针相同，头尾指针相同，则肯定为空则肯定为空6n入队入队void Enqueue(seqqueue*void Enqueue(seqqueue*Q Q,elementtype x),elementtype x)if(if(queue_fullqueue_f
6、ull(Q)error(“(Q)error(“溢出溢出”);”);else Q-rear=(1+Q-rear)%maxsize;else Q-rear=(1+Q-rear)%maxsize;Q-data Q-dataQ-rearQ-rear=x=x；n取队头元素：取队头元素：elementtype queue_front(seqqueue Q,elementtype*x)elementtype queue_front(seqqueue Q,elementtype*x)if(queue_empty(Q)error(“if(queue_empty(Q)error(“队空队空”);”);else *
7、x=Q.data else *x=Q.data(Q.front+1)%maxsize(Q.front+1)%maxsize););队头元素在队头元素在frontfront指针所指位置的下指针所指位置的下一个位置一个位置往后移动往后移动尾指针尾指针填进待插填进待插入的元素入的元素n出队出队void Outqueue(seqqueue*void Outqueue(seqqueue*Q Q,elementtype*x),elementtype*x)if if(queue_ queue_ emptyempty(*Q)(*Q)error(“)error(“队队空空，不不能能出出队队”);”);else
8、Q-front=(Q-front+1)%maxsize;else Q-front=(Q-front+1)%maxsize;*x=Q *x=Q-data-dataQ-frontQ-front;73.2.4 3.2.4 链队列链队列a1a2anfrontrearlinkqueue类型说明类型说明typedef struct typedef struct node*front,*rear node*front,*rear；/仅需要头尾指针即可仅需要头尾指针即可 linkqueue linkqueue；8头结点之后的结点中头结点之后的结点中的值为队头元素的值为队头元素链队列运算的实现链队列运算的实现n
9、初始化队列：初始化队列：void init_queue(linkqueue*Q)void init_queue(linkqueue*Q)Q-front=(node*)malloc(sizeof(node);Q-front=(node*)malloc(sizeof(node);Q-rear=Q-front;Q-rear=Q-front;Q-front-next=NULL;Q-front-next=NULL;产生由头指针产生由头指针指示的头结点指示的头结点尾指针也指尾指针也指向该头结点向该头结点尾结点的后继尾结点的后继指针设置为空指针设置为空n取队头元素：取队头元素：void queue_fron
10、t(linkqueue*void queue_front(linkqueue*Q Q,elementtype*,elementtype*x x););if(empty(*Q)error(“if(empty(*Q)error(“队空，不能取元素队空，不能取元素”);”);else else*x*x=Q-front-next-data;=Q-front-next-data;n判断队为空：判断队为空：BOOL queue_empty(linkqueue Q)BOOL queue_empty(linkqueue Q)return Q.front=Q.rear;return Q.front=Q.rear
11、;队头元素的值队头元素的值由由x x返回返回首尾指针相等首尾指针相等9n入队：入队：void Enqueue(linkqueue*Q,elementtype x)void Enqueue(linkqueue*Q,elementtype x)node*P=(node*)malloc(sizeof(node);node*P=(node*)malloc(sizeof(node);P-data=x;P-data=x;P-next=NULL;P-next=NULL;Q-rear-next=P;Q-rear-next=P;Q-rear=P;Q-rear=P;n出队：出队：void Outqueue(lin
12、kqueue*void Outqueue(linkqueue*Q Q,elementtype*,elementtype*x x););if(empty(*Q)error(“if(empty(*Q)error(“队空，不能出队队空，不能出队”);”);else else *x=Q-front-next-data;*x=Q-front-next-data;node*node*u u=Q-front-next;=Q-front-next;Q-front-next=u-next;free(u);Q-front-next=u-next;free(u);if(Q-front-next=NULL)Q-rea
13、r=Q-front;if(Q-front-next=NULL)Q-rear=Q-front;新节点中填入数据新节点中填入数据后继指针置空后继指针置空连到表尾连到表尾尾指针指向新尾指针指向新插入的节点插入的节点取队头元素的值取队头元素的值保存待删节点的保存待删节点的指针指针删除队头节点删除队头节点释放所删除节点的释放所删除节点的存储空间存储空间删除最后一个节点时，删除最后一个节点时，尾指针指向已被删除尾指针指向已被删除的节点，应做调整的节点，应做调整10 3.3 3.3 数组数组3.3.1 3.3.1 数组的定义数组的定义n一维数组是有限个相同类型的变量组成的序列。一维数组是有限个相同类型的变量
14、组成的序列。n若其中每个变量本身是一维数组，则构成二维数组。若其中每个变量本身是一维数组，则构成二维数组。（a1,a2,a3,an)a11a12a13a1na21a22a23a2nam1am2am3amn113.3.2数组的运算数组的运算n通常有如下两个：通常有如下两个：给定一组下标，存取相应的数组元素给定一组下标，存取相应的数组元素给定一组下标，修改相应的元素值给定一组下标，修改相应的元素值n这两个运算在内部实现时都需要计算出给定元素的实际这两个运算在内部实现时都需要计算出给定元素的实际存储地址。存储地址。123.3.3 3.3.3 数组的顺序存储数组的顺序存储n行优先存储方式：逐行地顺序存
15、储各元素。行优先存储方式：逐行地顺序存储各元素。n列优先存储方式：逐列地顺序存储各元素。列优先存储方式：逐列地顺序存储各元素。a11a12a1na21a22a2na31a32a2n am1am2amna11a21am1a12a22am2a13a23am3a1na2namn右边的下标比左右边的下标比左边的下标变化快边的下标变化快左边的下标比右左边的下标比右边的下标变化快边的下标变化快13数组元素地址的计算数组元素地址的计算Ai,jLoc(i,j)=addr0+(Num(i,j)-1)*ci,j=1,2,Num(i,j)=(i-1)*n+jNum(i,j)=(j-1)*m+i行优先行优先列优先列优
16、先Num(i,j)=i*n+j+1Num(i,j)=j*m+i+1行优先行优先列优先列优先i,j=0,1,143.3.4 3.3.4 矩阵的压缩存储矩阵的压缩存储a11a21a22a31a32a33 an1an2ann例，以行优先方式存储下三角例，以行优先方式存储下三角矩阵，矩阵，a aijij的序号：的序号：下三角元素：下三角元素：num(i,j)=1+2+3+(i-1)+j=i(i-1)/2+j上三角元素：上三角元素：num(i,j)=1+2+3+(j-1)+i=j(j-1)/2+i a11a12a13a1na21a22a23a2na31a32a33a3nan1an2an3ann(1)(1
17、)对称矩阵和三角矩阵对称矩阵和三角矩阵 对称矩阵对称矩阵A Anxnnxn满足满足a aijij=a=aji ji(i,j=1,2n)(i,j=1,2n)15a a1 11a1212a a2 21a2222a2323a3232a3333a3434a4343a4444a4545 ann-1ann(2)(2)对角矩阵对角矩阵 （例：三对角矩阵（例：三对角矩阵 ）a11a1212a21a22a2323a32a33a34 ann-1annnum(i,j)=3(i-1)-1+j-i+2=2i+j-2|i-j|=116(3)(3)稀疏矩阵稀疏矩阵0 01200050 0006000 0500307 700
18、10000 0000000 0090000 000000序序行行列列值值1 11 12 212122 21 16 65 53 32 24 46 64 43 32 25 55 53 35 53 36 64 41 17 77 74 44 410108 86 63 39 99 97 76 68 8typedef struct /typedef struct /三元组结构三元组结构/int i,j;elementtype v int i,j;elementtype v；tuple;tuple;struct /struct /三元组表结构三元组表结构 int mu,nu,tu;/int mu,nu,tu;/行数、列数、非行数、列数、非0 0元个数元个数 tuple data tuple datamaxnummaxnum spmatrix;spmatrix;17