队列和数组课件

3.2队列

3.2.1队列的定义队列是只能在一端插入、另一端删除的线性表。a1

a2

a3……an出队入队队头（删除元素）队尾（插入元素）队列的特性：先进先出FIFO13.2.2队列的基本运算初始化队列：init_queue(Q)判断队列是否为空：queue_empty(Q)取队头元素：queue_front(Q,x)入队：enqueue(Q,x)出队：outqueue(Q,x)判断队列是否为满：queue_full(Q)23.2.3顺序队列以顺序存储方式存储的队列叫做顺序队列。ana1a2.…..0123maxsize-1datafrontQrear类型说明：typedefstruct{elementtypedata［maxsize］;//存放元素的数组intfront,rear;//指向队头的前一个位置和队尾}seqqueue；3难题：如何区分循环队列的满和空状态？方法一：设置一个标志，以区分最后一次操作是入队还是出队操作。当头尾两个指针相等时，由该标志判断队列为满或空。方法二：保留一个空间不用，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。5循环队列运算的实现初始化队列： voidinit_queue(seqqueue*Q) {Q->front=0;Q->rear=0;}判断队列是否为空：

BOOLqueue_empty(seqqueueQ) {if(Q.front==Q.rear)returnTRUE; elsereturnFALSE;}

判断队列是否为满：

BOOLqueue_full(seqqueueQ) {if((1+Q.rear)%maxsize==Q.front)returnTRUE; elsereturnFALSE;}

尾指针的下一个位置是头指针所指位置时为满头尾指针相同，则肯定为空6入队

voidEnqueue(seqqueue*Q,elementtypex) {if(queue_full(Q))error(“溢出”);

else{Q->rear=(1+Q->rear)%maxsize; Q->data［Q->rear］=x；}}

取队头元素：elementtypequeue_front(seqqueueQ,elementtype*x) {if(queue_empty(Q))error(“队空”); else*x=Q.data［(Q.front+1)%maxsize］);}队头元素在front指针所指位置的下一个位置往后移动尾指针填进待插入的元素出队

voidOutqueue(seqqueue*Q,elementtype*x) {if(queue_empty(*Q))error(“队空，不能出队”);

else{Q->front=(Q->front+1)%maxsize;

*x=Q->data［Q->front］;}}7头结点之后的结点中的值为队头元素链队列运算的实现初始化队列： voidinit_queue(linkqueue*Q) {Q->front=(node*)malloc(sizeof(node));Q->rear=Q->front; Q->front->next=NULL;}产生由头指针指示的头结点尾指针也指向该头结点尾结点的后继指针设置为空取队头元素：

voidqueue_front(linkqueue*Q,elementtype*x); {if(empty(*Q))error(“队空，不能取元素”);

else*x=Q->front->next->data;}判断队为空：

BOOLqueue_empty(linkqueueQ) {returnQ.front==Q.rear;}队头元素的值由x返回首尾指针相等9入队： voidEnqueue(linkqueue*Q,elementtypex) {node*P=(node*)malloc(sizeof(node)); P->data=x; P->next=NULL; Q->rear->next=P; Q->rear=P;}出队：

voidOutqueue(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;} }新节点中填入数据后继指针置空连到表尾尾指针指向新插入的节点取队头元素的值保存待删节点的指针删除队头节点释放所删除节点的存储空间删除最后一个节点时，尾指针指向已被删除的节点，应做调整10

3.3数组

3.3.1数组的定义一维数组是有限个相同类型的变量组成的序列。若其中每个变量本身是一维数组，则构成二维数组。（a1,a2,a3,…,an)a11a12a13…a1na21a22a23…a2n…………am1am2am3…amn113.3.3数组的顺序存储行优先存储方式：逐行地顺序存储各元素。列优先存储方式：逐列地顺序存储各元素。a11a12…a1na21a22…a2na31a32…a2n

……am1am2…amna11a21…am1a12a22…am2a13a23…am3…

…a1na2n…amn右边的下标比左边的下标变化快左边的下标比右边的下标变化快13数组元素地址的计算A[i,j]Loc(i,j)=addr0+(Num(i,j)-1)*ci,j=1,2,…Num(i,j)=(i-1)*n+jNum(i,j)=(j-1)*m+i行优先列优先Num(i,j)=i*n+j+1Num(i,j)=j*m+i+1行优先列优先i,j=0,1,…143.3.4矩阵的压缩存储

a11a21a22a31a32a33

………

an1an2…ann例，以行优先方式存储下三角矩阵，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

a11a12a13…a1na21a22a23…a2na31a32a33…a3n

………

an1an2an3…ann

(1)对称矩阵和三角矩阵对称矩阵Anxn满足aij=aji(i,j=1,2…n)15(3)稀疏矩阵01200050006000500307001000000000009000000000序行列值11212216532464325535364