[2018年必威体育精装版整理]06栈与队列.pptVIP

elemtype delqueue(lqueue_type *q) { node_type *p; elemtype x; if(q-front-next==NULL) return(0); else{ p=q-front-next; /*取队头元素结点*/ x=p-data; /*取元素值*/ q-front-next=p-next; /*修改队头指针*/ if(p-next==NULL) /*若队长为一，*/ q-rear=q-front; /*修改尾指针*/ free(p); /*释放结点空间*/ return(x); } } 一维数组是一种顺序表结构，多维数组为线性表的推广。 二维数组： 1.2.3 数组 其行、列关系均是线性关系； 可看成元素为一维数组的顺序表。 a21 a22 …… a2n a11 a12 …… a1n ….…………… am1 am2 ……amn Amn= 给定下标——如何找数据元素的存储位置？ 1、（二维）数组的顺序存储 采用一组连续的内存单元存储数组的数据元素。 两种方法存放： ①.行优先存放 a11 a12 ……a1n a21 a22 …… a2n ….……… am1 am2 ……amn 则aij的存放位置为（设每个元素占s个存储单元） Loc(aij)= Loc(a11)+((i-1)*n+(j-1))*s ②.列优先存放 a11 a21 …… am1 a12 a22 …… am2 ….……… a1n a2n …… amn 则： Loc(aij)= Loc(a11)+((j-1)*m+(i-1))*s 顺序存储方式的特点： 1)可方便的随机存取元素。 2)但对具有许多相同值和零元素的矩阵来说， 则会造成存储单元的浪费。 2、矩阵的压缩存储 目的：节省存储空间。 方法：尽量不为零元素分配存储空间，并使多个值相同的元素只占用一个存储空间。 ①.特殊矩阵，如：对称矩阵、三角矩阵等，其值相 同的元素或零元素的分布具有一定的规律性。 所以只存储上三角或下三角内的元素。 对称矩阵中的元素关于主对角线对称。 只需存储上三角或下三角中的元素，能节约近一半的存储空间。 对称矩阵（An×n）： 0 1 2 3 4 5 1 0 1 2 3 4 2 1 0 1 2 3 3 2 1 0 1 2 4 3 2 1 0 1 5 4 3 2 1 0 对元素aij ： 当i=j时，元素aij位于下三角，其存储位置 Loc(aij)= Loc(a11)+(i*(i-1)/2+(j-1))*s 当ij时，元素aij位于上三角，其存储位置 Loc(aij)= Loc(a11)+(j*(j-1)/2+(i-1))*s (元素aij的对称元素为aji ，且 aij = aji ) 以行主序存放： a11 a21 a22 a31 a32 a33 …………an1 an2 an3 ……ann 第i行有i个元素 对n*n阶矩阵，所需存储的元素总数= n*(n+1)/2 三对角矩阵（An×n）：（带状矩阵） a32 a33 a34 a21 a22 a23 a11 a12 a43 a44 a45 …… … ann 0 0 只有主对角线和直接在主对角线上、下方的元素是非零元，其余元素都为零元素。 以行主序存放： a11 a12 a21 a22 a23 a32 a33 a34………… an(n-1) ann aij的存储位置： Loc(aij) = Loc(a11) +( ((i-1)*3-1)+(j-i+1) )*s ②.稀疏矩阵： ——矩阵中非零元素很少，且分布没有规律。 只存储非零元，采用三元组存储，即存储非零元素的行值（i）、列值（j）、元素值（aij）。 一个三元组（i,j,aij)唯一确定了稀疏矩阵的一个非零元； 对应所有非零元的所有三元组组成一个三元组矩阵； 三元组矩阵可按顺序方式存储——三元顺序表。 三元组矩阵T= 行数 列数 非零元总个数 行值 列值 元素值 行值 列值 元素值 …… …… ……… 第一行：存稀疏矩阵Amn的情况 第二行：存第一个非零元的