数据结构与算法-东北林业大学 第5章1.ppt

《数据结构与算法-东北林业大学 第5章1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组5.1数组5.2动态数组5.3特殊矩阵的压缩存储5.4稀疏矩阵的压缩存储15.1数组一、数组的定义数组：它是n（n>1)个相同数据类型的数据元素a0,a1,a2,…an-1构成的占用一块地址连续的内存单元的有限序列。数组的下标：数组元素的位置。注意：(1)C语言的数组定义下标从0开始。(2)数组的处理相比其它复杂的结构要简单。①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元

2、素值的操作。(3)一个二维数组可以看作每个数据元素是一个一维数组的一维数组。二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，C语言采用以行序为主序的方法存储。2问题：数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存

3、放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。3二、数组的实现机制１、一维数组（n个元素）中任一元素ai的内存单元地址LOC(ai)=LOC(a０)+i*k(0≤i

4、1,0a1,1…a1,n-1…………am-1,0am-1,1…am-1,n-1Amn=4注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）①开始结点的存放地址（即基地址）；②维数和每维的上、下界；③每个数组元素所占用的单元数例１〖软考题〗：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例２设数组a[０…60,

5、０…70]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为。答：根据行优先公式LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i

6、)65.2动态数组一、动态数组的设计方法1、动态数组的概念动态数组：它是在需要存储单元空间时才给出数组的具体个数。C语言提供的支持函数有：malloc()、calloc()、free()例：编写一个定义和使用二维3行4列动态数组的一个完整程序。7#include#include#includevoidmain(void){inti,j,row=3，col=4,**a;a=(int**)malloc(row*sizeof(int*))；for(i=0;i

7、+)a[i]=(int*)malloc(col*sizeof(int));for(i=0;i

8、eof(int))；returna;}9#include#include#include/*函数已经定义，同前*/voidmain(void){inti,j,c,row=3,col=4,**a;a=Make2DArray(row,col);fo