数据结构 课件 第6章 数组.pptx

第6章数组1总体要求：熟悉数组的定义及存储熟悉特殊矩阵的定义及存储熟悉数组的抽象数据类型描述中各种操作的含义熟练掌握数组在各种存储结构下算法的实现核心技能点：数组应用于实际问题的能力；特殊矩阵应用于实际问题的能力熟练掌握数组在各种存储结构下算法的实现的能力

第6章数组2扩展技能点：C语言环境下各种算法的实现相关知识点：C语言数组的知识线性代数的知识C语言指针的知识C语言函数的知识学习重点：熟悉数组的定义及存储熟悉特殊矩阵的定义及存储熟悉数组的抽象数据类型描述中各种操作的含义掌握数组在各种存储结构下算法的实现

第6章数组36.1二维数组应用实例及概念数组是我们很熟悉的一种数据类型，很多高级语言都支持这种数据类型。从逻辑结构上看，数组可以看作一般线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。如果说一维数组在逻辑上可看成一个向量，那么二维数组在逻辑上可看成由若干行、列组成的表格或矩阵。如表6.1学生成绩表就对应了一个二维数组。

第6章数组表6.1学生成绩表4表中每一行表示了某个学生的各门课程的成绩。可定义二维数组A存放以上学生成绩intA[4][5]；对线性表A=（A0,A1,A2,…Am-1），如果其中的任意元素Ai（0≤i≤m-1）是简单类型，则A是一个一维数组，如果Ai本身也是一个线性表，即Ai=（ai0，ai1，…，ain-1），则A是一个二维数组。如图6.1所示。

第6章数组5图6.1由线性表推广得到的二维数组

第6章数组6同理，三维数组可以看成是这样的一个线性表，其中每个数据元素均是一个二维数组。依次类推，可以得到多维数组。从数组的特殊结构，我们可以看出，数组中的每一个元素由一个值和一组下标来描述。“值”代表数组中元素的数据信息，一组下标用来描述该元素在数组中的相对位置信息。数组的维数不同，描述其对应位置的下标的个数也不同。例如，在二维数组中，元素a[i][j]由两个下标值i，j来描述，其中i表示该元素所在的行号，j表示该元素所在的列号。同样，我们可以将这个特性推广到多维数组，对于n维数组而言，其元素由n个下标值来描述其在n维数组中的相对位置。

第6章数组76.2数组的顺序存储和实现6.2.1数组的顺序存储对于数组A，一旦给定其维数n及各维长度b，则该数组中元素的个数是固定的，不能对数组做插入和删除操作，不涉及移动数据元素操作，因此对于数组而言，采用顺序存储方式比较合适。我们知道，计算机内存器的结构是一维的，因此对于一维数组按下标顺序分配即可，而对多维数组，就必须按照某种次序，将数据元素排成一个线性序列，然后将这个线性序列存放在存储器中。

第6章数组8数组的顺序存储结构有两种：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。例如，二维数组a[m][n]以行为主序的存储序列为：A[0][0]，a[0][1]，…，a[0][n-1]，a[1][0]，a[1][1]，…，a[1][n-1]，…a[m-1][0]，a[m-1][1]，…a[m-1][n-1]。

第6章数组96.2.2数组的实现数组是各种高级语言中已经实现的数据结构。在高级语言的应用层上，一般不会涉及到数据元素的存储地址的计算，这一计算内存地址的任务是由高级语言的编译系统完成的。当我们使用数组进行程序设计时，只需给出数组的下标范围，编译系统将根据用户提供的必要参数进行地址分配，存取数据元素时，也只要给出下标，而不必考虑其内存情况。例如：定义数组inta[3][4]；引用数组元素printf(“%d”,a[2][3])；这些在学习C语言时都已掌握。用这种方法定义的数组，①必须预先定义，②一经定义不能再改变大小，存在缺陷。下面介绍动态定义数组。

第6章数组10C语言动态存储管理一章介绍过四个函数①void*calloc(intn,intsize)分配n块size大小的空间。②void*malloc(intsize)分配size大小的空间。③void*realloc(*p,intsize)改变p所指存储空间大小为size。④fr