第五章 多维数组和广义表【数据结构与算法】

• 前言
• 版权
• 第5章 多维数组和广义表

• 5.1 应用实例
• 5.2 多维数组
• 5.3 矩阵的压缩存储

• 5.3.1 特殊矩阵
• 5.3.2 稀疏矩阵

• 5.4 广义表

• 5.4.1广义表的概念
• 5.4.2广义表的存储
• 5.4.3 广义表的操作

• 5.5实例分析与实现

• 习题

• 1.单项选择题
• 2.完成题
• 3.算法设计题

• (1)鞍点是指矩阵中的元素A[i][j]是第i行中值最小的元素， 同时又是第j列中值最大的元素。试设计一个算法求矩阵A的所有鞍点。
• (2)设计一个算法，实现将一位数组A(下标从1开始)中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度

• 最后

前言

第5章 多维数组和广义表

5.1 应用实例

5.2 多维数组

多维数组是一维数组的扩展，数组的数组就是多维数组。
为讨论方便，以下实例数组元素都从下标1开始。
1. 一维数组的存储
一维数组的每一个元素只含一个下标，实质就是线性表，存储方法同顺序表。假设一维数组为A=（A₁,A₂,…,A_i,…,A_n）,每个元素占L个存储单元，则元素A[i]的存储地址为
LOC（A[i]）=LOC（A[1]）+(i-1)xL

2. 二维数组的存储
二维数组可以有两种存储方式，行序主序和列序主序。
假设二维数组为A_mxn，每个元素占L个存储单元，则元素A[][j]的存储地址如下。

行序主序:
LOC(A[i][j])=LOC(A[1][1]) + (nx(i-1)+(j-1))xL

列序主序:
LOC(A[i][j])= LOC(A[1][1]) + (mx(j-1) +(i-1))xL

3. 三维数组的存储
假设三维数组A_rxmxn,每个元素占L个存储单元，则元素A[i][i][k]的存储地址为
LOC(A[i][j][k])=LOC(A[1][1][1])+((i-1)xmxn+ (j-1)xn+(k-1))xL

如果以j₁,j₂,j₃代替数组元素下标i,i,k,并且j₁,j₂,j₃的下限分别为c₁,c₂,c₃,上限分别为d₁,d₂,d₃,每个元素占size个存储单元，则A[j₁][j₂][j₃]的存储地址为
LOC(A[j₁][j₂][j₃]=LOC(A[c₁][c₂][c₃])+(j₁-c₁)x(d₂-c2+1)x(d₃-c₃+1)+(j₂-c₂) x (d₃-c₃+1)+(j₃-c₃))xsize

4. n维数组的存储
由以上分析推广到一般情况，在n维数组中，某数据元素存储位置的映象关系为

LOC(A[j₁][j₂]…[j_n]=LOC(A[c₁][c₂]…[c_n])+ⁿ_i=1α_ix(j_i-c_i),1≤i≤n
其中: α_I=size x _k=i+1(d_k-c_k+1),(1≤i≤n)

可以看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，c_i就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。满足这一特点的存储结构被称为随机存储结构。显然，数组具备随机存储的特征。

【例5.1】设有二维数组A[10][20]，其中每个元素占2个字节，第一个元素A[1][1]的存储地址为100，计算按行优先顺序存储元素A[4][6]的存储地址，以及按列优先顺序存储时元素A[5][8]的存储地址。
解:
按行优先:A[4][6]=100+[(4-1)x20+(6-1)]x2=230
按列优先:A[5][8]=100+[(8-1)x10+(5-1)]x2=248

5.3 矩阵的压缩存储

5.3.1 特殊矩阵

5.3.2 稀疏矩阵

5.4 广义表

5.4.1广义表的概念

线性表要求它的每一个数据元素必须是结构不可再分的单个元素，而广义表中的数据元素可以是单个元素,也可以又是一个广义表。因此,广义可以认为是线性表的推广。
广义表是m(n≥0)个元素的有限序列,记作LS=(d₁,d₂,d_n)
其中，d_i或者为原子项(原子,一般用小写字母表示),或者为广义表(子表,一般用大写字母表 ），n为广义表的长度。
原子:是作为结构上不可分割的成分,它可以是一个数或一个结构。
子表:若广义表LS中的某个元素d,本身也是一个广义表,则称d,为广义表LS的子表
长度:广义表LS中元素的个数为LS的长度(length),注意只计算LS中直接元素的个数即 d的个数
空表;表内没有元素,即长度为0的广义表称为“空表”。
表头与表尾:S不为空时,称d,为表头(head)，称其余元素组成的子表(d,d-.d.)为表尾（tail)。显然,广义表的表尾一定是广义表,但表头不一定。
深度:广文表LS的深度Depth(LS)递归地定义为

{	0	(若IS为原子项)
Depth(LS)=      {	1	(若LS为空表)
						 {	1+max,(Depth(d~i~))(其他情况)

可以看出,广义表的深度相当于广义表中表达式括号的最大嵌套层数。
遵归表:著广义表LS中某元素包含其自身,则称LS为递归表。
例如:
①A=()空表,Length=0,Depth=1。
②F=(d.(e)).Length=2,Depth=2,head(F)=d,tail(F)=((e))
③D=((a,(b,c)),F),Length=2,Depth=3,head(D)=(a,(b,c)),tail(D)=(F)。
④C=(A,D,F),Length=3,Depth=4,head©=A,tail©=(D,F)
⑤B=(a,B)=(a,(a,(a,…,)),Length=2,Depth=a,head(B)=a,tail(B)=(B)递归表.
广义表其实是一种特殊的结构,若不考虑其元素的内部结构,它是一个线性表,即元素之间的关系是线性关系;但是如果从元素的分层方面讲,广义表是类似树的层次结构;如果从元素的递归性和共享性等方面讲,它又具有图结构的特点。特别是元素的递归性,使得广义表具有强有力的语言表达能力,这也是广义表最重要的特性。

5.4.2广义表的存储

5.4.3 广义表的操作

5.5实例分析与实现

习题

参考来自研究生学长的细腻讲解

1.单项选择题

(1)假设整型数组A[1…8,-2…6,0…6]按行优先存储，第一个元素的首地址是78，每个数组元素占4个存储单元，那么元素A[4,2,3]的存储首地址为B.958
A.955
B.958
C.950
D.900
解析:首先这个数组可以表示为A[8][9][7]={1…8,-2…6,0…6}; 所求的元素A[4,2,3]对应在数组中则为A[4][5][4];
可以把它看成是一本书，则对应书中的第四页第五行的第四个字。
前三页是满的:3x9x7=189
第四页的前四行是满的:4x7=28
第五行的元素:3个
LOC(A[3][4][3])= 78+(189+28+3)x4=958

(2)将一个A[1…100,1…100]的三对角矩阵按行优先存入一维数组B[1…298]中，A中元素A_66,65在B数组中的位置k为(D.195)
A.198
B.197
C.196
D.195
解析:三对角矩阵除第一行与最后一行为两个元素外其余行均为三个元素。
k=(66-2)x3+2+1= 195

(3)若对n阶对称矩阵A，以行序为主序方式将其下三角形的 元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中，则在B中确定a_ij(i<j)的位置k的关系为B.jx(j-1)/2+i
A.ix(i-1)/2+j
B.jx(j-1)/2+i
C.ix(i+1)/2+j
D.jx(j+1)/2+i
解析:由题知，第i行上方的三角形区域都已经存满:
第i行上方的元素个数为:i(i-1)/2;
第i行的元素个数为:j;
即k=ix(i-1)/2+j;

(4)设A是nxn的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1…(n(n+1))/2]中，对上述任一元素a_ij(1≤i,j≤n，且i≤j)在B中的位置为(B.j(j-1)/2+i)
A.i(i-1)/2+j
B.j(j-1)/2+i
C.j(j-1)/2+i-1
D.i(i-1)/2+j-1
解析:由题知，元素a;左上方的三角形区域都已存满: 该区域的元素个数为:j(j-1)/2;
第列存放的元素个数为:i;
综上答案选B。

(5)tail(head(((a,b,c,e))))=D.(b,c,d,e)

A.a
B.b,c
C.0
D.(b,c,d,e)
解析: head(((a,b,c,d,e)))=(a,b,c,d,e); tail(head(((a,b,c,d,e))))= tail((a,b,c,d,e))=(b,c,d,e)

2.完成题

(1)已知数组A[3…8,2…6]以列序为主顺序存储，起始地址为 1000，且每个元素占4个存储单元，求:
①数组A的元素总数。
②分别计算A[4][5]和A[6][3]的地址。
③表示元素A[i][j]的地址计算公式。

(2)写出n维数组按列序为主序进行存储的地址计算公式。
解析: A[i][j] = LOC(1,1)+((j-1)xn+(i-1))xsize

(3)一个n阶对称矩阵A，其上三角个元素按行序为主序存放 于一维数组B中，请给出B[k]和A[i][j]的关系(k的下标从1开始)。
解析:
k=n(i-1)-(0+(i-2))(i-1)/2+(j-i+1)
k=(i-1)(2n-i+2)/2+(j-i+1)
(4)设有三对角矩阵Anxn，将其三条对角线上的元素逐行压 缩存储到一个大小为3n-2的一维数组B中(下标从1开始)， 使得B[k]=A[i][j],求:
①用i;j表示k的下标变换公式。
②用k表示i,j的下标变换公式。
解析:
①因为仅有第一行和最后一行元素个数为2，其余都是3个，
所以k=3(i-2)+2+j-i+1+1即k=2(i-1)+j
②i=k/3+1
j= k/3+k%3

3.算法设计题

(1)鞍点是指矩阵中的元素A[i][j]是第i行中值最小的元素， 同时又是第j列中值最大的元素。试设计一个算法求矩阵A的所有鞍点。

#include<stdio.h>
#define N 20
int main()
{
	int a, b;
	puts("输入矩阵的行数，列数");
	scanf("%d %d", &a, &b);					//输入矩阵行、列
	int s[N][N], i, j;
	puts("输入矩阵元素");
	for (i = 0; i < a; i++)
		for (j = 0; j < b; j++)
			scanf("%d", &s[i][j]);            //输入矩阵
	int k, column, min, max, flag = 0;
	for (i = 0; i < a; i++) {
		max = s[i][0];						
		for (j = 0; j < b; j++) {			//找出每一行中最小的元素
			if (s[i][j] > max) {
				max = s[i][j];
				column = j;
			}
		}
		min = s[i][column];					//将每行最大的元素定义为min
		for (k = 0; k < a; k++) {			//将min与当前列的元素比较
			if (s[k][column] < min) {
				min = s[k][column];
			}
		}
		if (min == max) {					//若当前列最小的数等于max 则找到鞍点
			printf("%d是鞍点", s[i][column]);
			flag = 1;
		}
	}
	if (flag == 0) printf("没有鞍点");       
	return 0;
}

(2)设计一个算法，实现将一位数组A(下标从1开始)中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度

#define N 100
#include <stdio.h>
typedef int Type ; 
void ror(Type* num,int n,int k){
	int len=n+1;//数组所占 
	k=k%len;
	Type temp;
	int i,j;
    for(i = 1; i <= k; i++)			//右旋 次数 
    {       
        temp = num[len-1];					//最后一项num[n-1] 
        
        for(j = len-1; j >=1 ; j--)      //右旋一位 
            num[j] = num[j-1];			//后移一位     [1,n)<<[0,n-1)
        num[1] = temp;               //第1项num[0]变成最后1项num[n-1] 
        
    }
}

int main(){
	Type num[N];
	int n,k,i,j;
	printf("输入数组长度\n");
	scanf("%d",&n); 
	printf("输入数组\n") ;
	for(i=1;i<=n;i++){
		scanf("%d",&num[i]);
	}
	
	printf("输入右移位数k\n") ; 
	scanf("%d",&k);
				 
	printf("输出原数组\n") ;
	for(i=1;i<=n;i++){
		printf("%d ",num[i]);
	}
	printf("\n");

	ror(num,n,k);
	printf("输出移位后数组\n") ;
	for(i=1;i<=n;i++){
		printf("%d",num[i]);
	}
	
}

最后

2023-11-6 16:20:21

我们都有光明的未来
不必感谢我，也不必记得我

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦