数据结构——使用C语言版(朱战立)数组教学内容.ppt

《数据结构——使用C语言版(朱战立)数组教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——使用C语言版(朱战立)数组相同之处是它们都是若干个相同数据类型的数据元素a0,a1,a2,...,an-1构成的有限序列。不同之处是：（1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；（2）线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；（3）数组的操作主要是向某个下标的数组元素中存数据和取某个下标的数组元素，这和线性表的插入、删除操作不同。数组符合线性结构的定义。数组和线性表相比，线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。可见，数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基

2、础的数据结构。2.数组的实现机制(１)、一维数组（n个元素）中任一元素ai的内存单元地址Loc(ai)=LOC(a０)+i*k(0≤i

3、数据类型数据集合：数组的数据集合可以表示为a0,a1,a2,...,an-1，每个数据元素的数据类型为抽象数据元素类型DataType。操作集合：(1)求数组元素个数ArrayLength(D)(2)取数组元素Get(D,i)(3)存数组元素Storage(D,i,x)5.2动态数组数组有静态存储结构的数组和动态存储结构的数组两种，它们的区别在于：静态数组在定义时就必须给出数组个数；动态数组是在具体申请存储单元空间时才给出数组元素的个数。例5-2定义有3行、4列整数类型的二维数组a，先逐行分别给数组元素赋数据1，2，...，12，然后显示数组中的数值。要求分别把申请二维动态数组的

4、过程和释放二维动态数组的过程编写成函数。int**Make2DArray(introw,intcol){int**a,i;a=(int**)calloc(row,sizeof(int*));for(i=0;i#include#include#inclu

5、de“Array.h”voidmain(void){inti,j,c;introw=3,col=4,**a;a=Make2DArray(row,col);c=1;for(i=0;i

6、数组在物理上是连续的，而全部二维动态数组在物理上不一定是连续的。5.3特殊矩阵特殊矩阵:指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。1.几种特殊矩阵的压缩存储:(1)n阶对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji（1≤i,j≤n）则称A为n阶对称矩阵。如图5.1是一个5阶对称矩阵。15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…annn阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样

7、，能节约近一半的存储空间。在这个下三角矩阵中，第i行恰有i个元素，元素总数为n(n+1)/2，这样就可将n2个数据元素压缩存储在n(n+1)/2个存储单元中。假设以一维数组va作为n阶对称矩阵A的压缩存储单元，k为一维数组va的下标序号，aij为n阶对称矩阵A中i行j列的数据元素(其中1≤i,j≤n），其数学映射关系为：i(i-1)/2+j-1当i≥jj(j-1)/2+i-1当i