数据结构第5章 数组与广义表第5章 数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构5.6 m元多项式的表示5.7 广义表的递归算法5.1 数组的定义ADT Array 数据对象： Daj1,j2,.,ji ,.jn |ji =0,.,bi-1, i=1,2,.,n, 称 n(0) 为数组的维数， bi为数组第 i 维的长度，ji为 数组元素的第i维下标，aj1,.,jn ElemSet 数据关系： RR1, R2, ., Rn, Ri |0jkbk-1, 1kn 且k matrix;template class matrix public: matrix(int numRows = 1, int numCols = 1, const T vector const vector int rows() const; int cols() const; void resize(int numRows, int numCols); private: int nRows, nCols; vector mat; ;5.2 数组的顺序表示和实现template matrix:matrix(int numRows, int numCols, const Treturn mati; template const vectorreturn mati; 5.2 数组的顺序表示和实现template int matrix:rows() const return nRows; template int matrix:cols() const return nCols; 5.2 数组的顺序表示和实现template void matrix:resize(int numRows, int numCols)int i;/ handle case of no size change with a returnif (numRows = nRows / assign the new matrix sizenRows = numRows;nCols = numCols;/ resize to nRows rowsmat.resize(nRows);/ resize each row to have nCols columnsfor (i=0; i =jk =i(i-1)/2+j-1 ii=i; p-j=j; p-e=e; if(M.rheadi=NULL|M.rheadi-jj) p-right=M.rheadi;M.rheadi=p; else for(q=M.rheadi; (q-right) p-right=q-right;q-right=p; 三、十字链表 if(M.cheadj=NULL|M.cheadj-ii) p-down=M.cheadj;M.cheadj=p; else for(q=M.cheadj; (q-down) p-down=q-down;q-down=p; return OK; 三、十字链表n稀疏矩阵的和 A=A+Bl初始，令pa和pb分别指向A和B的第一行的第一 个非零元素的节点。l每一行，依次处理B在本行中所有节点lpa=NULL | pa-jpb-jlpa!=NULL n=0; ei IN AtomSet 或 ei IN GList, AtomSet 为某个数据对象 R = | ei-1,ei IN D, 2tag=0 （2）maxdh(p)=1 当空表(p-tag=1&p-hp=NULL) （3）maxdh(p)=max(maxdh(p1),.,maxdh(pn)+1 其余情况 其中p=(p1,p2,.,pn)5.7 广义表的递归算法n复制广义表n任何一个非空广义表均可分解成表头和表 尾。n复制的递归实现只需分别复制表头和表尾 即可。