数据结构数组和广义表演示

第4章 数组和广义表

【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（ ）的物理地址相同。设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]

解： 二维数A是一个9行10列的矩阵，即A[9][10]。按行存储时，A[8][5]是第85个元素存储的元素。而按列存储时，第85个存储的元素是A[3][10]。即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（ ）。

A．jii2)1(* B．ijj2)1(* C．jii2)1(* D．ijj2)1(*

解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：

1+2+3+…+（i-1）=i（i-1）/2。同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素aij的存放位置的公式。

解： 如果aij按列存储，那么它的前面有j-1列，共有元素：

n+(n-1)+(n-2)+ …+[n-(j-2)]

=(j-1)*n-2)1)(2(jj

而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中的存储顺序为：

(j-1)*n-2)1)(2(jj+i

【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（ ）。

《数据结构与算法》第五章 数组和广义表

本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组

5.1.1 数组的逻辑结构

数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象

现在来讨论数组在计算机中的存储表示。通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。以行为主序的内存映象如图5.3（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数据结构数组与广义表知识点总结

数组是一种线性数据结构，可以存储多个相同类型的元素。它的特点是元素的大小固定，并且在内存中是连续存储的。数组的访问方式是通过下标来访问，下标从0开始。数组可以在编程中应用于各种情况，比如存储一组数字、一组字符串等。

广义表是一种扩展的线性数据结构，可以存储不同类型的元素。它由元素和表构成，其中表可以是空表、原子或子表。广义表可以递归定义，即子表可以包含更多的子表。广义表的访问方式是通过递归来访问，可以对表的元素进行遍历和操作。

在数据结构中，数组和广义表都有自己的特点和用途，下面对它们的知识点进行总结：

1.数组的特点及应用：

-数组是一种线性数据结构，可以存储多个相同类型的元素。

-数组的内存分配是连续的，可以通过下标来访问元素。

-数组的大小固定，一旦定义后不能改变。 -数组的访问速度快，可以通过下标直接访问元素。

-数组适合用于存储一组相同类型的数据，比如一组数字、一组字符串等。

-数组的应用场景包括但不限于：排序算法、查找算法、图像处理、矩阵运算等。

2.数组的操作和常用算法：

-初始化：可以直接赋值或使用循环初始化数组。

-访问元素：通过下标访问元素，下标从0开始。

-修改元素：直接通过下标修改元素的值。

-插入元素：需要移动插入位置之后的元素。

-删除元素：需要移动删除位置之后的元素。

-查找元素：可以使用线性查找或二分查找等算法。

-排序算法：比如冒泡排序、选择排序、插入排序等。

-数组还有一些常用的属性和方法，比如长度、最大值、最小值等。

3.广义表的特点及应用： -广义表是一种扩展的线性数据结构，可以存储不同类型的元素。

-广义表由元素和表构成，表可以是空表、原子或子表。

-广义表可以递归定义，即子表可以包含更多的子表。

-广义表的访问方式是通过递归遍历和操作。

-广义表适合存储一组不同类型的数据，比如存储学生信息、函数调用栈等。

-广义表的应用场景包括但不限于：函数式编程、树的表示、图的表示等。

1 / 55

十万种考研考证电子书、题库视频学习平台 圣才电子书

第5章 数组和广义表

5.1 复习笔记

一、数组的定义

1．二维数组

类似于线性表，一个二维数组的逻辑结构形式表示为：

2-Array＝（D，R）

其中

D＝{a

ij|i＝c

1，c

1＋1，…，d

l，j＝c

2，c

2＋1，…，d

2，a

ij∈D

0}

R＝{ROW，COL}

ROW＝{

ij，a

i，j＋1>|c

1≤i≤d

1，c

2≤j≤d

2－1，a

ij，a

i，j＋1∈D}

COL＝{

ij，a

i＋1，j>|c

1≤i≤d

1－1，c

2≤j≤d

2，a

ij，a

i＋1，j∈D}

D

0为某个数据对象，c

1，c

2，d

1，d

2均为整数。

【注意】

①二维数组中含有（d

1－c

1＋1）×（d

2－c

2＋1）个数据元素，每个数据元素a

ij都受

行关系、列关系约束。

②a

i，j＋1是a

ij在行关系中的直接后继元素；而a

i＋1，j是a

ij在列关系中的直接后继元素。

③数组中所有的数据元素属于同一数据类型。

2．n维数组

2 /

55

十万种考研考证电子书、题库视频学习平台 圣才电子书

n维数组的逻辑结构形式定义如下：

n-Array＝（D，R）

其中

12

120,1,,,1,2,,(0)

,n

niiii

jjj

jjjiijccdinn

Da

aDcd





且和均为整数

12{,},,

nRRRR

11

111

111

,1

,inin

ininijjjjkkk

jjiii

jjjjjjRaacjdknkcjd

aaD











 且

【注意】

①n维数组含有)1(

1

iin

icd个数据元素，每个数据元素都受n个关系的约

束。

②在每个关系中，数据元素

12(1)

njjjiiiacjd



都有一个直接

后继元素。

二、数组的顺序表示和实现

1．二维数组的两种存储方式