(最新)数组广义表

《(最新)数组广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章线性表2.1线性表的抽象数据型2.2线性表的实现2.2.1线性表的数组实现2.2.2线性表的指针实现2.2.3线性表的游标实现2.2.4双向链接表2.2.5环形链表(循环链表)2.2.6多项式的代数运算2.3栈2.4队列2.5串、2.6数组、2.7、广义表12.6数组2.6.1抽象数据型数组数组是由下标和值组成的序对的集合（index,value）操作:(1)CREATE()(2)RETRIEVE(array,index)(3)STORE(array,index,value)22.6、多维数组和线性表的关系1.二维数组(矩阵)：Amn=a11a12a13...a1na21a22a2

2、3...a2n……………..am1am2am3...amn按行划分:A可看成一个线性表A=(a1,a2,…,am)ai=(ai1,ai2,…,ain)按列划分:A可看成一个线性表A=(a1,a2,…,an)aj=(a1j,a2j,…,amj)3一个二维数组类型可以定义为其分量类型为一维数组类型的线性表类型;同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的线性表类型。如：inta[m][n][p]相当于有一个线性表b[m]，其元素为b[0]…b[i]…b[m-1]，这个线性表的第i+1个元素b[i]是什么呢？其中每一元素b[i]是一个二维数组a[i][n][p]。2.6、多维数

3、组和线性表的关系*4顺序表示:2.6.2、数组的表示char*elmelm=(char*)malloc(10*sizeof(char))与charelm[10]一样.52、数组元素的地址关系以二维数组为例说明。对于二维数组有两种存储方式：(1)以行序为主的存储方式;(2)以列序为主的存储方式。a00a01a02a03a10a11a12a13a20a21a22a23a00a01a02a03a10a11a12a13a20a21a22a23第7个位置第8个位置假如a00的起始地址是loc(a00),数组中每一个元素所占空间为L,a12的起始地址怎么计算：行序：loc(a12)=loc(a00)+

4、[(1×4)+2]×L列序：loc(a12)=loc(a00)+[(2×3)+1]×L2.6.2、数组的表示6以行序为主序的存储结构的元素位置确定给定数组A[m1][m2],每个元素所占空间为L,a00的起始地址记为loc(a00),aij的起始地址为：LOC[aij]=LOC[0,0]+(m2i+j)LA[m1][m2][m3]3维数组的数据元素aijk的存储位置：LOC(aijk)=LOC(a000)+(m2m3i+m3j+k)L2.6.2、数组的表示7A[m1][m2]...[mn]n维数组的数据元素存储位置：LOC(aj1,j2,…jn)=LOC(a0,0,…,0)+(m

5、2…mnj1+m3…mnj2+…+mnjn-1+jn)L2.6.2、数组的表示8例：按低下标优先(行优先)存储整数数组A9358时，每个元素占4个字节，第一个元素的地址是100，计算a3125的存储地址。LOC[a3125]=100+(3*5*8*3+5*8*1+8*2+5)*4*2.6.2、数组的表示9下(上)三角矩阵与对称矩阵10002200453036781235224634375678下三角矩阵对称矩阵2.6.2、数组的表示--矩阵的压缩存储用一维数组存储A[n*(n+1)/2]当i>=j时A[i][j]对应存储在A[i(i+1)/2+j]***102.6.2

6、数组的表示--矩阵的压缩存储稀疏矩阵010000002010000((0，1，1)，(1，3，2)，(2，0，1))三元组顺序表的存储表示#defineMAXSIZE12500structnode{inti,j;//非零元素的行下标和列下标datatypev;//非零元素的值};11structspmatrix{nodedata[MAXSIZE];//非零元三元组表;intm,n,t;//矩阵的行数、列数和非零元个数};2.6.2数组的表示--矩阵的压缩存储12数组的链式表示—十字链表2.6.2数组的表示--矩阵的压缩存储010001021000structnode{node*left;/

7、/指向左边非0元素node*up;//指向上边非零元素;introw;intcol;//所在行列；valuetypeval;//元素值};*132.7广义表(董事长、总经理、秘书、人事部、分公司....)(总经理、秘书、人事部、分公司....)14广义表是线性表的推广，也称列表（Lists）。1.定义广义表是n个元素的有限序列，记作A=（a1,a2,……an)其中A是表名，n是广义表的长度，ai是广义表的元素，它可以是单