数据结构学习 第一章数组和稀疏矩阵

结构化程序设计的核心就是“自上而下设计”与模块化设计:将整个程序需求从上而下,由大到小分解成小的单元和模块,分别开发。


OO程序设计三个重要的特性:继承,封装,多态;


例如 for i=1 to n  do

               j<-i;

for k=j+1 to n do

x=x+1;

请问 x=x+!执行次数的时间复杂度O(n*n);

先分析内层的循环一共执行1 至n-1次;即为∑(n-i)=∑n-∑i=n*n-n*(n-1)/2=n*(n-1)/2


计算二维数组在内存中的位置(以列为主是java c/c++ pascal语言的数组存放方式,以行为主是Fortran语言存放方式)

数组A(m,n),假设a为数组A在内存中的起始位j置,d为单位空间,那么数组元素A(i,j)在内存的位置:

1)以列为主:Loc(A(i,j))=a+n*(i)*d+(j)*d(存储顺序为 a(0,0),a(0,1)a(0,2),a(1,0).....)

a(0,0) a(1,0) a(2,0)
a(0,1) a(1,1) a(2,1)
a(0,2) a(1,2) a(2,2)


2)以行为主:loc(A(i,j))=a+i*d+m*(j)*d(存储顺序为a(0,0,)a(1,0),a(2,0)...)

a(0,0) a(0,1) a(0,2)
a(1,0) a(1,1) a(1,2)
a(2,0) a(2,1) a(2,2)



范例: 若A(1,1)在位置2,A(2,3)在位置18,A(3,2)在位置28,试求A(4,5)的位置?(此处设矩阵都是按第一个元素为A(1,1))

解析:由LocA(3,2)的位置大于LocA(2,3)可知A数组是按列方式存储;且a=LocA(1,1)=2

由按列保存的公式的:

a+n*(2-1)*d+(3-1)*d=18

a+n*(3-1)*d+(2-1)*d=28

   解之d=2,n=6

LocA(4,5)=2+6*(4-1)*2+(5-1)*2=46



范例: 二维数组A(1:5,1:6),如果以列存放,则A(3,3)在此数组中的第几个位置(a=0,d=1)

LocA(3,3)=0+6*(3-1)*1+(3-1)*1=14,所以在数组的第14个位置;






原文地址:https://www.cnblogs.com/HuaiNianCiSheng/p/3074710.html