10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A BC DE FG 第二章 数据结构与算法 (续) 2.3 栈和队列 栈和队列是两种特殊的线性表，它们是运算时要 受到某些限制的线性表，故也称为限定性的数据 结构。 (续) 队列的主要运算 （1）设置一个空队列； （2）插入一个新的队尾元素，称为进队； （3）删除队头元素，称为出队； （4）读取队头元素； 2.3.2 队列 2.3.2.1 队列的定义与运算 定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表 。此种结构称为先进先出（FIFO） 表。 a1 , a2 , a3 , a4 , an-1 , an 队 列 示 意 图 队头 队尾 2. 队列的存储结构 （1）顺序存储结构 (a) 线性队列 (b) 循环队列 (a)线性队列 3 2 1 0 (a) rear=front=-1(队空） e3 e4 (c) (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 注：实际上为了避免与队空标 志冲突，还留有一个空间。 将头尾连接成一 个环，形成循环 队列。 rear (1)一般情况 front 0 1 2 3 e4 e3 (2) 队满 front e3 e4 0 1 2 3 rear e5 循环队列中加入一个元素的算法： int EnQueue(int Q ,int x, int *pf,int *pr) Qmax已 有的循环 队列 将插入 的值 已有队列 的头指针 已有队列 的尾指针 循环队列中加入一个元素的算法： int EnQueue(int Q ,int x, int *pf,int *pr) int front, rear; front=*pf; rear=*pr; if(rear+1)%MAX= =front) return(0); else rear=(rear+1)%MAX; Qrear=x; *pr=rear; return(1); rear Max=4,Rear+1=4 front 0 1 2 3 e4 e3 rear (Rear+1)%4=0 front 0 1 2 3 e4 e3 rear rear front 0 1 2 3 e4 e3 x 循环队列中删除一个元素的算法： int DeQueue(int Q ，int *py， int *pf，int *pr) 已有的循环 队列 返回删 除的值 的地址 已有队列 的头指针 已有队列 的尾指针 循环队列中删除一个元素的算法： int DeQueue(int Q ，int *py，int *pf，int *pr) int front, rear; front=*pf; rear=*pr; if(rear= =front) return(0); else front=(front+1)%MAX; *py=Qfront; *pf=front; return(1); an a2 a1 an a3 a2 Q.front Q.rear 删 除 一个元素 添加 一个元素 e a1 a2 an Q.front Q.rear （2） 链式存储结构 Q.front Q.rear 队头 队尾 Q.rear Q.front 2.4 数 组 2.4.1 二维数组的定义 a1 a11 a12 a1n a2 a21 a22 a2n am am1 am2 amn . ai=( ai1 , ai2 , , ain ) ( 1=i=n ) （1） 按行优先顺序存放 （2） 按列优先顺序存放 1、 特殊矩阵 （1） 下三角阵 （2） 三对角阵 1、 稀疏矩阵 （1） 顺序存储结构三元组表示法 （2） 顺序存储结构稀疏矩阵的转置运算 （3） 数组的链接存储结构十字链表结构 242 数组的顺序存储结构 243 矩阵的压缩存储 （1） 按行优先顺序存放 （2） 按列优先顺序存放 1、 特殊矩阵 （1） 下三角阵 （2） 三对角阵 1、 稀疏矩阵 （1） 顺序存储结构三元组表示法 （2） 顺序存储结构稀疏矩阵的转置运算 （3） 数组的链接存储结构十字链表结构 242 数组的顺序存储结构 243 矩阵的压缩存储 amn am2 am1 . a2n a22 a21 a1n . a12 a11 a11 a12 a1n a21 a22 a2n am1 am2 amn . loc(aij)=loc(a11)+(i-1)n+(j-1)S 按行优先顺序存放 amn a2n a1n . am2 a22 a12 am1 . a21 a11 a11 a12 a1n a21 a22 a2n am1 am2 amn . loc(aij)=loc(a11)+(j-1)m+(i-1)S 按列优先顺序存放 a11 0 0 0 a21 a22 0 0 an1 an2 an3 ann . 0 A= 按行优先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann 前i-1行非零元素个数 R= i(i-1) 2 loc(aij)=loc(a11)+( +(j-1)S i(i-1) 2 i-1 R=1 下三角阵 a11 a12 0 0 a21 a22 a23 0 . 0 0 0 an-1,n-2 an-1.n-1 an-1,n A= 0 a21 a22 a23 0 0 0 0 .an,n-1 ann. 按行优先存放a11 , a12 , a21 , a22 , a23 , a32 , a34 , an,n-1 , ann loc(aij)=loc(a11)+2(i-1)n+(j-1)S 三对角阵 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= 21 6 4 -2 1 4 -1 4 3 -4 2 2 15 5 1 7 1 1 列行值 顺序存储结构三元组表示法 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0 21 6 4 -1 4 3 -4 2 2 15 5 1 7 1 1 -2 1 4 7 0 0 -2 0 -4 0 0 0 0 -1 0 0 0 0 0 15 0 0 0 0 0 0 21 顺序存储结构稀疏矩阵的转置运算 -1 3 4 7 1 1 -2 4 1 -4 2 2 15 1 5 21 4 6 求转置矩阵的算法描述为： Status TransposeSMatrix(TSMatrix M, TSMatrix T.nu=M.mu; T.tu=M.tu; / 互换行列数 if (T.tu0) q=1; for(col=1;col=M.nu; +col) / 对稀疏矩阵的每一列分别处理 for(p=1; p=M.tu; +p) / 按行扫描三元组表 if(M.dataP.j= =col T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.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 515 1 1-2 4 621 4 171 4-1 3 j e rightdown i 24 数 组 （ 线性表的推广） 241 二维数组的定义 a1 a11 a12 a1n a2 a21 a22 a2n am am1 am2 amn . ai=( ai1 , ai2 , , ain ) ( 1=i=n ) 数组的运算主要是存取元素、修改相应的元素。 （1） 按行优先顺序存放 （2） 按列优先顺序存放 243 矩阵的压缩存储 1、 特殊矩阵：值相同元素或非零元素的分布具有一定规律。 （1） 下三角阵 （2） 三对角阵 2、 稀疏矩阵 ：元素分布无规律。 （1） 顺序存储结构三元组表示法 （2） 顺序存储结构稀疏矩阵的转置运算 （3） 数组的链接存储结构十字链表结构 242 数组的顺序存储结构 a11 a12 . a1n a21 a22 a2n . am1 am2 amn a11 a12 a1n a21 a22 a2n am1 am2 amn . loc(aij)=loc(a11)+(i-1)n+(j-1)S 按行优先顺序存放 a11 a21 . am1 a12 a22 am2 . a1n a2n amn a11 a12 a1n a21 a22 a2n am1 am2 amn . loc(aij)=loc(a11)+(j-1)m+(i-1)S 按列优先顺序存放 a11 0 0 0 a21 a22 0 0 an1 an2 an3 ann . 0 A= 按行优先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann 前i-1行非零元素个数 R= i(i-1) 2 loc(aij)=loc(a11)+(i(i-1)/2 +(j-1)S i-1 R=1 下三角阵 a11 a12 0 0 a21 a22 a23 0 . 0 0 0 an-1,n-2 an-1.n-1 an-1,n A= 0 a32 a33 a34 0 0 0 0 .an,n-1 an,n 按行优先存放a11 , a12 , a2