第三章-多维数组和广义表.ppt

第三章

多维数组和广义表谢顺平南京大学地理与海洋科学学院第三章多维数组和广义表数组的两种顺序存储结构以行序为主序（行优先顺序）以列序为主序（列优先顺序）3.2矩阵的压缩存储3.2.1特殊矩阵1.对称矩阵2.下三角矩阵3.2.2特殊矩阵的抽象数据类型ADTSpecialMatrixisData:特殊矩阵线性表Ｍ＝（a1,……an,an+1),Matrix为类型描述符Operations:voidInitMatrix(Matrixm,inttype,intn);//初始化ElemTypeGetMatrix(Matrixm,inti,intj);//取值voidSetMatrix(Matrixm,inti,intj,ElemTypev);//赋值voidClearMatrix(Matrixm);清除特殊矩阵voidPrintMatix(Matrixm);输出特殊矩阵endSpecialMatrix特殊矩阵数据类型描述3.2.3特殊矩阵基本算法描述初始化特殊矩阵voidInitMatrix(Matrixm,inttype,intsize){introw,col,value,n=(type4)?size?(size+1)/2:3?size-2;m.type=type;m.size=size;m.data=newElemType[n+1];for(inti=0;in;i++){cinrowcolvalue;SetMatrix(m,row,col,value);}if(m.type==2||m.type==3){cinvalue;//输入上三角或下三角的相同值SetMatrix(m,m.type-1,4-m.type,value);//三角赋值}}特殊矩阵元素取值ElemTypeGetMatrix(Matrixm,inti,intj){if(m.type==1){//对称矩阵if(i=j)returnm.data[i?(i+1)/2+j];elsereturnm.data[j?(j+1)/2+i];}elseif(m.type==2){//下三角矩阵if(i=j)returnm.data[i?(i+1)/2+j];elsereturnm.data[m.size?(m.size+1)/2];}elseif(m.type==3){//上三角矩阵if(j=i)returnm.data[i?(2?m.size-i+1)/2+j-i];elsereturnm.data[m.size?(m.size+1)/2];}特殊矩阵元素取值特殊矩阵元素赋值voidSetMatrix(Matrixm,inti,intj,ElemTypev){if(m.type==1){//对称矩阵if(i=j)m.data[i?(i+1)/2+j]=v;elsem.data[j?(j+1)/2+i]=v;}elseif(m.type==2){//下三角矩阵if(i=j)m.data[i?(i+1)/2+j)]=v;elsem.data[m.size?(m.size+1)/2]=v;}elseif(m.type==3){//上三角矩阵if(j=i)m.data[i?(2?m.size-i+1)/2+j-i]=v;elsem.data[m.size?(m.size+1)/2]=v;}特殊矩阵元素赋值特殊矩阵输出清除特殊矩阵voidClearMatrix(Mat