第5章--数组和稀疏矩阵.ppt

广义表的定义广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。广义表是n(n=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。其中,data域中表示的非零元素通常以行序为主序顺序排列,它是一种下标按行有序的存储结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设data域按行有序存储。(1)从一个二维矩阵创建其三元组表示以行序方式扫描二维矩阵A,将其非零的元素插入到三元组t的后面。算法如下：voidCreatMat(TSMatrixt,ElemTypeA[M][N]){ inti,j; t.rows=M;t.cols=N;t.nums=0; for(i=0;iM;i++) {for(j=0;jN;j++) if(A[i][j]!=0)/*只存储非零元素*/{t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } }}(2)三元组元素赋值先在三元组t中找到适当的位置k,将k～t.nums个元素后移一位,将指定元素x插入到t.data[k]处。算法如下：intValue(TSMatrixt,ElemTypex,intrs,intcs){inti,k=0;if(rs=t.rows||cs=t.cols)return0;while(kt.numsrst.data[k].r)k++; /*查找行*/while(kt.numscst.data[k].c)k++; /*查找列*/if(t.data[k].r==rst.data[k].c==cs) t.data[k].d=x;/*存在这样的元素else/*不存在这样的元素时插入一个元素*/{for(i=t.nums-1;ik;i--)/*元素后移*/{t.data[i+1].r=t.data[i].r;t.data[i+1].c=t.data[i].c;t.data[i+1].d=t.data[i].d; } t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x; t.nums++;}return1;}(3)将指定位置的元素值赋给变量先在三元组t中找到指定的位置,将该处的元素值赋给x。算法如下：intAssign(TSMatrixt,ElemTypex,intrs,intcs){intk=0;if(rs=t.rows||cs=t.cols)return0;while(kt.numsrst.data[k].r)k++;while(kt.numscst.data[k].c)k++;if(t.data[k].r==rst.data[k].c==cs){x=t.data[k].d;return1;}elsereturn0;}(4)输出三元组从头到尾扫描三元组t,依次输出元素值。算法如下：voidDispMat(TSMatrixt){inti; if(t.nums=0)return; printf(“\