《队列和数组》PPT课件.ppt
1,3.2 队列3.2.1 队列的定义,队列是只能在一端插入、另一端删除的线性表。,2,3.2.2 队列的基本运算,初始化队列：init_queue(Q)判断队列是否为空：queue_empty(Q)取队头元素：queue_front(Q,x)入队：enqueue(Q,x)出队：outqueue(Q,x)判断队列是否为满：queue_full(Q),3,3.2.3 顺序队列,以顺序存储方式存储的队列叫做顺序队列。,类型说明：typedef struct elementtype datamaxsize;/存放元素的数组 int front,rear;/指向队头的前一个位置和队尾seqqueue；,4,顺序队列会产生“假溢出”循环队列,基本操作：入队：rear=(rear+1)%maxsize;datarear=x;出队：front=(front+1)%maxsize;,5,难题：如何区分循环队列的满和空状态？,方法一：设置一个标志，以区分最后一次操作是入队还是出队操作。当头尾两个指针相等时，由该标志判断队列为满或空。,方法二：保留一个空间不用，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。,6,循环队列运算的实现,初始化队列：void init_queue(seqqueue*Q)Q-front=0;Q-rear=0;,判断队列是否为空：BOOL queue_empty(seqqueue Q)if(Q.front=Q.rear)return TRUE;else return FALSE;,判断队列是否为满：BOOL queue_full(seqqueue Q)if(1+Q.rear)%maxsize=Q.front)return TRUE;else return FALSE;,尾指针的下一个位置是头指针所指位置时为满,头尾指针相同，则肯定为空,7,入队void Enqueue(seqqueue*Q,elementtype x)if(queue_full(Q)error(“溢出”);else Q-rear=(1+Q-rear)%maxsize;Q-dataQ-rear=x；,取队头元素：elementtype queue_front(seqqueue Q,elementtype*x)if(queue_empty(Q)error(“队空”);else*x=Q.data(Q.front+1)%maxsize);,队头元素在front指针所指位置的下一个位置,往后移动尾指针,填进待插入的元素,出队void Outqueue(seqqueue*Q,elementtype*x)if(queue_ empty(*Q)error(“队空，不能出队”);else Q-front=(Q-front+1)%maxsize;*x=Q-dataQ-front;,8,3.2.4 链队列,类型说明typedef struct node*front,*rear；/仅需要头尾指针即可 linkqueue；,9,头结点之后的结点中的值为队头元素,链队列运算的实现,初始化队列：void init_queue(linkqueue*Q)Q-front=(node*)malloc(sizeof(node);Q-rear=Q-front;Q-front-next=NULL;,产生由头指针指示的头结点,尾指针也指向该头结点,尾结点的后继指针设置为空,取队头元素：void queue_front(linkqueue*Q,elementtype*x);if(empty(*Q)error(“队空，不能取元素”);else*x=Q-front-next-data;,判断队为空：BOOL queue_empty(linkqueue Q)return Q.front=Q.rear;,队头元素的值由x返回,首尾指针相等,10,入队：void Enqueue(linkqueue*Q,elementtype x)node*P=(node*)malloc(sizeof(node);P-data=x;P-next=NULL;Q-rear-next=P;Q-rear=P;,出队：void Outqueue(linkqueue*Q,elementtype*x);if(empty(*Q)error(“队空，不能出队”);else*x=Q-front-next-data;node*u=Q-front-next;Q-front-next=u-next;free(u);if(Q-front-next=NULL)Q-rear=Q-front;,新节点中填入数据,后继指针置空,连到表尾,尾指针指向新插入的节点,取队头元素的值,保存待删节点的指针,删除队头节点,释放所删除节点的存储空间,删除最后一个节点时，尾指针指向已被删除的节点，应做调整,11,3.3 数组3.3.1 数组的定义,一维数组是有限个相同类型的变量组成的序列。若其中每个变量本身是一维数组，则构成二维数组。,（a1,a2,a3,an),12,3.3.2 数组的运算,通常有如下两个：给定一组下标，存取相应的数组元素给定一组下标，修改相应的元素值这两个运算在内部实现时都需要计算出给定元素的实际存储地址。,13,3.3.3 数组的顺序存储,行优先存储方式：逐行地顺序存储各元素。,列优先存储方式：逐列地顺序存储各元素。,右边的下标比左边的下标变化快,左边的下标比右边的下标变化快,14,数组元素地址的计算,Ai,j,15,3.3.4 矩阵的压缩存储,例，以行优先方式存储下三角矩阵，aij的序号：下三角元素：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,a11 a12 a13 a1na21 a22 a23 a2n a31 a32 a33 a3n an1 an2 an3 ann,(1)对称矩阵和三角矩阵 对称矩阵Anxn满足aij=aji(i,j=1,2n),16,a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 ann-1 ann,(2)对角矩阵（例：三对角矩阵）,num(i,j)=3(i-1)-1+j-i+2=2i+j-2|i-j|=1,17,(3)稀疏矩阵,0 12 0 0 0 50 0 0 6 0 00 5 0 0 3 07 0 0 10 0 00 0 0 0 0 00 0 9 0 0 00 0 0 0 0 0,typedef struct/三元组结构/int i,j;elementtype v；tuple;struct/三元组表结构 int mu,nu,tu;/行数、列数、非0元个数 tuple datamaxnum spmatrix;,
