Chapter 2b Arrays and Structures

Objects:P(x)=a1xe1++anxen;asetoforderedpairsofei,aiwhereaiisthecoefficientandeiistheexponent.eiarenonnegativeintegers.Operations:Zero-setzeroofapolynomialIsZero-JudgewhetherapolynomialiszeroCoef-Findingcoefficientofaterminapolynomial.LeadExp-Findingdegree,max{ei},ofapolynomial.Attach-AttachatermwithapolynomialRemove-RemoveatermfromapolynomialSingleMult-SingleMultiplicationofapolynomialwithaterm.Add-Additionoftwopolynomials.Mult-Multiplicationoftwopolynomials.§2.4Polynomials【Representation1】#defineMAX_DEGREE2000typedefstruct{floatcoef[MAX_DEGREE];intdegree;}Polynomial;Ilikeit!It’seasytoimplementmostoftheoperations,suchasAddandMultiplication.Really?WhatisthetimecomplexityforfindingtheproductoftwopolynomialsofdegreeN1andN2?O(N1*N2)What’swrongwiththat?TrytoapplyMultonP1(x)=10x1000+5x14+1andP2(x)=3x19902x1492+11x+5--nowdoyouseemypoint?Given:0101)(eemxaxaxAm.1,,1,0for0and0where021miaeeeimmDeclaration:#defineMAX_TERM100typedefstruct{floatcoef;/*assumecoefficientsarefloats*/intexpon;}polynomial;polynomialterms[MAX_TERMS];/*termssortedbyexponent*/intavail=0;【Representation2】finishAstartAfinishBstartBavail=6termsindexcoefexpon02100011021431034325106〖Example〗ToaddA(x)=5x4+2x24x+1andB(x)=6x3+3x2+4x,wefirststorebothofthemintoterms[]:startafinishastartbCOMPAREavail=7avail=8termsindexcoefexpon054122241310463532641finishbtermsindexcoefexpon7891011121354startaCOMPARE63avail=9startbCOMPARE52avail=10startastartb=finishbCOMPAREstarta=finishafinishbstartb10avail=11startd=availfinishastartafinishd=avail1TheresultingpolynomialD(x)=A(x)+B(x)isstoredinterms[startd]toterms[finishd].TheprogramPaddcanbefoundonp.55-56.AnalysisofPadd:LetmandnbethenumberofnonzerotermsinA(x)andB(x),respectively,thenthetimecomplexityofPaddis:Tpadd(m,n)=O(m+n)Isn’tthatbeautiful?It’salotmoreefficientthanthefirstone!Well...WhatifthepolynomialisNOTsparse?Thenthisrepresentationtakesabouttwiceasmuchspaceasthefirstone!Ohinthatcase...Nobody’sperfect...Aworstcasecouldbe:A(x)=x2m++x4+x2+1andB(x)=x2n+1++x3+xNote:Wecanstoremanypolynomialsinterms[],aslongasthetotalnumberofnonzerotermsisnotgreaterthanMAX_TERMS.IfavailMAX_TERMS,thenwecaneitherquit,orremovesomeunnecessarypolynomialsandcreatealarge,continuousavailablespaceatoneendofthearray.Thatcouldmeanalotofdatamovementswhichtakestime.Inaddition,wealsomustchangethestartandendindicesforeachpolynomialmoved.§2.5SparseMatrixWhatisaSPARSEmatrix?What’swrongwithmysimplerepresentationA[MAX_ROWS][MAX_COLS]?AmatrixisSPARSEifitcontainsmanyzeroentries.Many?Howmanyis“many”?Well,unlikeothermathconcepts,thereisnodefinitelinedrawnhere.Togiveyousomeidea,thinkofa1000by1000matrixwith3000nonzeroentries.Wow!IseehowmuchspaceIcouldhavewasted.But,butdopeoplereallydealwithsuchkindofmatrices?Unfortunatelywedo.It’squitecommontoseesparsematricesinnumericalanalysis.SoI’dbetterfigureoutanotherwaytorepresentit.Hmm.....structureSparseMatrixisobjects:Asetoftriples,row,column,value,whererowandcolumnareintegersandformauniquecombination,andvaluecomesfromthesetitem.functions:foralla,bSparseMatrix,xitem,i,j,maxCol,maxRowindexSparseMatrixCreate(maxRow,maxCol)::=returnaSparseMatrixthatcanholduptomaxItems=maxRowmaxColandwhosemaximumrowsizeismaxRowandwhosemaximumcolumnsizeismaxCol.SparseMatrixTranspose(a)::=returnthematrixproducedbyinterchangingtherowandcolumnvalueofeverytriple.SparseMatrixAdd(a,b)::=ifthedimensionsofaandbarethesamereturnthematrixproducedbyaddingcorrespondingitems,namelythosewithidenticalrowandcolumnvalues.elsereturnerror1.ADTDefinitionrow,column,valuecanuniquelydetermineanelementwithinamatrix.structureSparseMatrixis(continued)SparseMatrixMultiply(a,b)::=ifnumberofcolumnsinaequalsnumberofrowsinbreturnthematrixdproducedbymultiplyingabybaccordingtotheformula:d[i][j]=(a[i][k]b[k][j])whered(i,j)isthe(i,j)thelement.elsereturnerrorendSparseMatrix【Representation1】SparseMatrixCreate(maxRow,maxCol)::=#defineMAX_TERMS101/*maximumnumberofterms+1*/typedefstruct{intcol;introw;intvalue;}term;terma[MAX_TERMS];a[0].row=totalnumberofrowsofthematrix;a[0].col=totalnumberofcolumnsofthematrix;a[0].value=totalnumberofnonzeroentriesinthematrix;a[1]~a[MAX_TERMS]storethenonzeroelements.〖Examples〗p.58Figure2.4(b)andp.60Figure2.5(a)000280000000910000000060000003110150220015col0col1col2col3col4col5row0row1row2row3row4row52825]8[9104]7[632]6[321]5[1111]4[1550]3[2230]2[1500]1[866]0[arowcolvalueNote:Theindicesofrowsandcolumnsareinascendingorder.【Representation2】CompressedRowStorage(CRS)SparseMatrixCreate(maxRow,maxCol,nnz)::=typedefstruct{intn;/*numberofcolumns*/intm;/*numberofrows*/int*col_ind;/*Thecol_indvectorstoresthecolumnindexesoftheelementsinthevaluesvector*/int*row_ptr;/*Therow_ptrvectorstoresthelocationsinthevaluesvectorthatstartarow*/double*values;/*numericalvalue*/}SparseMatrix;SprseMatrixa;a.n=maxRow;sp.m=maxCol;a.col_ind=(int*)malloc(sizeof(int)*nnz);a.row_ptr=(int*)malloc(sizeof(int)*(maxRow+1));a.values=(double*)malloc(sizeof(double*)*nnz);a.n=totalnumberofrowsofthematrix;a.m=totalnumbe