数据结构-第4章(数组和广义表).ppt

例如：1、二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节；（2）A的第8列和第5行共占（）个字节；（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。供选择的答案：（1）A.90B.180C.240D.270E.540（2）A.108B.114C.54D.60E.150（3）A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]例.三对角矩阵的压缩存储例如：1、设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-12.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。A.198B.195C.1973、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。head（tail（tail（L）））tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）NorthChinaElectricPowerUniversity^(4).修改有关的边结点的adjvex域的内容。华电计算机系为稀疏矩阵的每一行设置一个单独的循环链表，同样为每一列设置一个单独的循环链表。矩阵中每一个非零元素同时包含在两个循环链表中，即包含在它所在的行链表与所在的列链表中,即两个链表的交汇处。十字链表NorthChinaElectricPowerUniversity华电计算机系对于一个m?n的稀疏矩阵，分别建立m个行的循环链表与n个列的循环链表，每个非零元素用一个链结点存储.其中，row,col,value分别表示某个非零元素所在的行号、列号和元素的值；down向下指针,链接同一列中下一个非0元素right向右指针，链接同一行中的下一个非0元素。链结点的构造为：rowcolvaluedownrightNorthChinaElectricPowerUniversity华电计算机系北航计算机系一共设置MAX(m,n)个头结点.00downright对m个行链表，分别设置m个行链表表头结点。表头结点的构造与链表中其他链结点一样，只是令row与col的值分别为0，right域指向相应行链表的第一个结链点。同理，对n个列链表,分别设置n个列链表表头结点。其中,令row和col的值分别为0，down域指向相应列链表的第一个结链点。NorthChinaElectricPowerUniversity华电计算机系另外，再设置一个总的头结点(如下所示),通过value域把所有表头结点也链接成一个循环链表。mnlinkt总头结点:NorthChinaElectricPowerUniversityB=对于如下稀疏矩阵B如下，十字链表表示如下：40020290460-5NorthChinaElectricPowerUniversity华电计算机系347003030300011434200222239000031432634-50001HEAD40020290460-5★广义表一.广义表的定义一个长度为n≥0的广义表是一个数据结构LS