[理学]算法设计与分析基础知识.ppt

文档介绍：算法设计与分析基础知识
汤德佑华南理工大学软件学院
******@scut.
**********
作为抽象数据类型的数组
一维数组
一维数组的示例
一维数组的特点
连续存储的线性聚集(别名向量)
除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。
二维数组三维数组
行向量下标 i 页向量下标 i
列向量下标 j 行向量下标 j
列向量下标 k
数组的连续存储方式
一维数组
LOC ( i ) = LOC ( i -1 ) + l =α+ i*l
二维数组
行优先 LOC ( j, k ) = j * m + k
n维数组
各维元素个数为 m1, m2, m3, …, mn
下标为 i1, i2, i3, …, in 的数组元素的存储地址:
顺序表(Sequential List)
顺序表的定义和特点
定义 n(  0)个表项的有限序列
(a1, a2, …, an)
ai是表项,n是表长度。
特点顺序存取
遍历逐项访问
从前向后从后向前从两端向中间
顺序搜索图示
x = 48 x = 50
搜索成功 若搜索概率相等,则
搜索不成功数据比较 n 次