重庆大学数据结构ppt12_Array(seminar)

DataStructureDataStructureCollegeofComputerScience,CQUSeminar：FastMatrixTransposingDataStructureDataStructureArrays_02Arrays_02FastMatrixTransposingDiscussion:comparedwith2Discussion:comparedwith2--DarrayrepresentationDarrayrepresentationO(columns*elements)vs.O(columns*rows)O(columns*elements)vs.O(columns*rows)elementselements----columns*rowswhennoncolumns*rowswhennon--sparse,sparse,O(columnsO(columns22*rows)*rows)Problem:ScanthearrayProblem:Scanthearray““columnscolumns””times.times.HowcanHowcanwetransposeamatrixrepresentedasawetransposeamatrixrepresentedasasequenceoftriplesinO(columns+elements)sequenceoftriplesinO(columns+elements)timetime？？DataStructureDataStructureArrays_02Arrays_02FastMatrixTransposingSolution:Solution:First,determinethenumberofelementsineachFirst,determinethenumberofelementsineachcolumnoftheoriginalmatrix.columnoftheoriginalmatrix.Second,determinethestartingpositionsofeachrowSecond,determinethestartingpositionsofeachrowinthetransposematrix.inthetransposematrix.DataStructureDataStructureArrays_02Arrays_02FastMatrixTransposingYouaretocreateprogramstotransposeamatrixtransposeamatrixrepresentedasasequenceoftriplesinO(columns+representedasasequenceoftriplesinO(columns+elements)elements)DataStructureDataStructureArrays_02Arrays_02Reference《数据结构（C语言版）》，严蔚敏，吴伟民编著，清华大学出版社，1997年第1版,P91-99DataStructureDataStructureArrays_02Arrays_02-End-