数据结构之队列数组和表讲述.ppt

第二章?数据结构与算法 队列的主要运算 （1）设置一个空队列； （2）插入一个新的队尾元素，称为进队； （3）删除队头元素，称为出队； （4）读取队头元素； 2. 队列的存储结构 （1）顺序存储结构 ? 求转置矩阵的算法描述为： Status TransposeSMatrix(TSMatrix M, TSMatrix T){ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; // 互换行列数 if (T.tu !=0) { q=1; for(col=1;col=M.nu; ++col) // 对稀疏矩阵的每一列分别处理 for(p=1; p=M.tu; ++p) // 按行扫描三元组表 if(M.data[P].j= =col { T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q } } return OK; }//TransposeSMatrix 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0 M= 2 -4 ∧ ∧ 2 5 15 ∧ ∧ 1 1 -2 ∧ 4 6 21 ∧ ∧ 4 1 7 1 4 -1 ∧ ∧ 3 ^ j e right down i 链式存储结构 表示第3列空 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0 M= 2 -4 ∧ ∧ 2 5 15 ∧ ∧ 1 1 -2 ∧ 4 6 21 ∧ ∧ 4 1 7 1 4 -1 ∧ ∧ 3 ^ j e right down i 链式存储结构 作业： P76 第12、16题 第18、19题 A+B*C-D/E； top1 初态 ; (a) top2 OS NS B A + ; (b) OS * C NS T1=B*C A + ; (c) NS OS T1 T2 ; (d) NS OS T2=A+T1 E D T2 / - ; (e) NS OS T3 T2 - ; (f) T3=D/E NS OS (g) NS OS T4 ； T4=T2-T3 (h) * 10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A B C D E F G (续) 2.3 栈和队列 栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。 (续) 2.3.2 队列 2.3.2.1 队列的定义与运算 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO）表。 a1 , a2 , a3 , a4 , ………… an-1 , an 队 列 示 意 图 队头 队尾 (a) 线性队列 (b) 循环队列 (a)线性队列 3 2 1 0 (a) rear=front=-1(队空） e3 e4 (c) e1,e2出队，e4入队 队 满 rear =4 front e1 e2 e3 (b) rear front (b)e1,e2,e3入队 队空时， 令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置 (b) 循环队列 rear front 0 1 2 3 (3) 队空 队满条件： (Q.rear+1)%MAX=Q.front