数据结构C语言05学习教案.pptx

数据结构(shùjùjiéɡòu)C语言05复习(fùxí)提问复习(fùxí)提问复习(fùxí)提问内容(nèiróng)和要求多维数组的定义(dìngyì)多维数组的定义(dìngyì)多维数组的定义(dìngyì)二维数组的逻辑结构
数组和广义(guǎngyì)表可以看成是线性表在下述含义上的扩展：即线性表中的数据元素本身也是一个数据结构。
类似于线性表，一个二维数组的逻辑结构可形式地表示为
2-Array=(D,R)(5-1)
其中
D={aij|i=c1,c1+1,···,d1，j=c2,c2+1,···,d2,aij∈D0}
R={Row,Col}//行关系，列关系
Row={<aij,ai,j+1>|c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1∈D}
Col={<aij,ai+1,j>|c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j∈D}
D0为某个数据对象，c1,c2,d1,d2均为整数。若c1=1,d1=m,c2=1,d2=n,则有
D={aij|i=1,2,···,m,j=1,2,···,n,∈D0}
R={Row,Col}
Row={<aij,ai,j+1>|i=1,2,···,m,j=1,2,···,n-1,aij,ai,j+1∈D}
Col={<aij,ai+1,j>|i=1,2,···,m-1,j=1,2,···,n,aij,ai+1,j∈D}
记作Am×n，即A为m行n列的二维数组(起始下标(xiàbiāo)为1)。
说明：
1)用于二维数组的抽象可称之为矩阵，它是对向量的推广，其元素个数为m×n个。2)二维数组也可以看作是这样一个线性表：它的每一个数据(shùjù)元素是一个线性表。从而对二维数组可以进行递归定义，即它是数据(shùjù)元素为一维数组的线性表。可把Am×n看成是由m个行向量所组成的向量（线性表），也可以看成是n个列向量所组成的向量。
Am×n=(α1,α2,···,αp)(p=m或n)
若αi为行向量：αi=(ai1,ai2,···,ain)1≤i≤m
若αj为列向量：αj=(a1j,a2j,···,amj)1≤j≤nn(n>2)维数组的逻辑(luójí)结构
n维数组的逻辑(luójí)结构的形式定义N维数组的递归定义(dìngyì)数组的操作
一个数组中所有的数据元素都必须属于同一数据类型。
对于数组，通常只有两种基本操作：
1）给定一组下标，存取相应的数据元素。
2）给定一组下标，修改相应数据元素中的某一个或几个数据项的值。
注.对于二维数组的抽象即矩阵，可包含取值、赋值和初始化等操作。编译程序(biānyìchénɡxù)用线性存储器来实现矩阵。数组的顺序存储结构(jiégòu)数组的顺序存储结构：用一组连续的存储单元顺序地存放数组中的诸数组元素。
数据元素的存放次序问题：解决存储单元是一维结构，而数组是个多维结构的矛盾。
（指多维数组）
二维数组元素间次序的排列方法：行优先与列优先序。
行优先序：按以行序为主序进行(jìnxíng)排列，就是把数组元素按行表次序、第i+1行的元素紧跟在第i行元素后面进行(jìnxíng)存储。示例:w是一个3*4的整数数组（起始(qǐshǐ)下标从1开始）。
设二维数组变量w的诸数据组元素值如下表所示
1234
10-145
2820-3
3-5120同样，对于n维数组也有上述两种不同的顺序存储方式：以左下标为主序的存储方式和以右下标为主序的存储方式。
把n维数组的元素按上述方式顺序存放在存储单元中，则每个元素的存储地址可以(kěyǐ)用一个公式计算出来，这个公式称为“地址公式”。
计算存储地址：对于A[1..m,1..n]，设每个数组元素占L个存储单元。记a11的存储地址为LOC[1,1]，它即是二维数组A的起始存储位置(wèizhi)，或称基地址（首地址）,L为元素所占的单元数。
记aij(1≤i≤m,1≤j≤n)的存储地址为LOC[i,j]，则
LOC[i,j]=LOC[1,1]+[n*(i-1)+(j-1)]*L.
LOC[j1,j2,j3]=LOC[c1,c2,c3]+[(d2-c2+1)(d3-c3+1)(j1-c1)+(d3-c3+1)(j2-c2)+(j3-c3)]*L
上已推导(tuīdǎo)出，对于三维数组A[c1..d1，c2..d2，c3..d3]，
设基地址为LOC[c1,c2,c3]，则计算机如何(rúhé)实现数组元素的随机存取？一维数组
二维数组
三维数组假设数组各维的下界是1,按“行优先顺序”存储,假设每个元素(yuánsù)占用d个存储单元。
二维数组Amn，aij的地址计算函数为：
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
三维数组Amnp，ai