资源描述：
《【精品数据结构】栈和队列（续）.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构第二章 数据结构与算法(续)2.3栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。(续)队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；2.3.2队列2.3.2.1队列的定义与运算定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。a1,a2,a3,a4,…………an-1,
2、an队列示意图队头队尾2.队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列(a)线性队列3210(a)rear=front=-1(队空）e3e4(c)e1,e2出队，e4入队队满rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队队空时，令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置(b)循环队列rearfront0123(3)队空队满条件：(Q.rear+1)%MAX=Q.front注：实
3、际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。rear(1)一般情况front0123e4e3(2)队满fronte3e40123reare5循环队列中加入一个元素的算法：intEnQueue(intQ[],intx,int*pf,int*pr)Q[max]已有的循环队列将插入的值已有队列的头指针已有队列的尾指针循环队列中加入一个元素的算法：intEnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==fron
4、t)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}rearMax=4,Rear+1=4front0123e4e3rear(Rear+1)%4=0front0123e4e3rearrearfront0123e4e3x循环队列中删除一个元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr)已有的循环队列返回删除的值的地址已有队列的头指针已有队列的尾指针循环队列中删除一个元素的算法：intDeQueue(intQ[]，int*py，int*pf
5、，int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}ana2a1ana3a2Q.frontQ.rear删除一个元素添加一个元素e^a1a2anQ.frontQ.rear（2）链式存储结构Q.frontQ.rear队头队尾Q.rearQ.front2.4数组2.4.1二维数组的定义a1a11a12……..a1na2a21a22……..a2namam1am2…
6、…..amn………………….ai=(ai1,ai2,……..,ain)(1<=i<=n)（1）按行优先顺序存放（2）按列优先顺序存放1、特殊矩阵（1）下三角阵（2）三对角阵1、稀疏矩阵（1）顺序存储结构——三元组表示法（2）顺序存储结构稀疏矩阵的转置运算（3）数组的链接存储结构——十字链表结构2．4．2数组的顺序存储结构2．4．3矩阵的压缩存储（1）按行优先顺序存放（2）按列优先顺序存放1、特殊矩阵（1）下三角阵（2）三对角阵1、稀疏矩阵（1）顺序存储结构——三元组表示法（2）顺序存储结构稀疏矩阵的转置运算（3）数组的链接存储结构——十字链表结构2．4．
7、2数组的顺序存储结构2．4．3矩阵的压缩存储amn……..am2am1……….a2n……..a22a21a1n…….a12a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(i-1)n+(j-1)]S按行优先顺序存放amn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(j-1)m+(i-1)]S按列优先顺序
8、存放a1100……..0a21a220……..0an1an2an3……..ann
