《数据结构之队列数组和表讲述》由会员分享，可在线阅读，更多相关《数据结构之队列数组和表讲述（48页珍藏版）》请在金锄头文库上搜索。
1、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
2、, 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) 循环队列 rea
3、r 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
4、 ,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 ，in
5、t *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 删 除 一个元素 添加 一个元素
6、 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 数
7、组的顺序存储结构 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
8、 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
9、 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
10、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(c
11、ol=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 数 组 （ 线性
12、表的推广） 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
13、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
