文档介绍：算法设计与分析基础知识汤德佑华南理工大学软件学院 ******@scut. ********** 作为抽象数据类型的数组作为抽象数据类型的数组??一维数组一维数组––一维数组的示例一维数组的示例一维数组的特点一维数组的特点??连续存储的线性聚集(别名连续存储的线性聚集(别名向量向量) ) ??除第一个元素外,其他每一个元素有除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。一个且仅有一个直接前驱。??除最后一个元素外,其他每一个元素除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。有一个且仅有一个直接后继。二维数组二维数组三维数组三维数组行向量行向量下标下标 i i 页向量页向量下标下标 i i 列向量列向量下标下标 j j 行向量行向量下标下标 j j列向量列向量下标下标 k k 数组的连续存储方式数组的连续存储方式??一维数组一维数组????????时 0,)( 时 0 α,)(ili LOC i i LOC 1 LOC ( i ) = LOC ( i - 1 ) + l =α+ i*l ??二维数组二维数组?????????????????????????] ][[] ][[] ][[] ][[ ] ][[] ][[] ][[] ][[ ] ][[] ][[] ][[] ][[ ] ][[] ][[] ][[] ][[ 11211101 12221202 11211101 10201000mnananana maaaa maaaa maaaaa ?????????行优先行优先 LOC LOC ( ( j j, , k k ) = ) = j j * * m + k m + k n n维数组维数组??各维元素个数为各维元素个数为 m 1, m 2, m 3, …, m n ??下标为下标为 i i 1 1, i , i 2 2, i , i 3 3, , ……, i , i n n的数组元素的存的数组元素的存储地址: 储地址: n nj njk k j nnn n n nim i imim mmi m mmiiii LOC ????????????????????????????????? 111 1 432 321 21),,,(?????顺序表顺序表( ( Sequential List Sequential List ) )??顺序表的定义和特点顺序表的定义和特点––定义定义 n n( (??0 0) )个表项的有限序列个表项的有限序列( (a a 1 1, a a 2 2, …, a a n n) ) a a i i是表项, 是表项, n n是表长度。是表长度。––特点特点顺序存取顺序存取––遍历遍历逐项访问逐项访问从前向后从前向后从后向前从后向前从两端向中间从两端向中间顺序搜索图示 x = 48 x = 50 搜索成功搜索成功若搜索概率相等,则若搜索概率相等,则搜索不成功搜索不成功数据比较数据比较 n次次 i ni icp ACN ???? 10=2 12 ) (11 )2 (1 1 1)( 1= 10nnnn n n in ACN ni????????????????