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

前言

2023-11-6 16:19:57

以下内容源自《【数据结构与算法】【精致版】》

仅供学习交流使用

第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])+Σ \SigmaΣⁿ_i=1α_ix(j_i-c_i),1≤i≤n

其中: α_I=size x ∏ n \prod^n∏n_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

我们都有光明的未来

不必感谢我，也不必记得我

祝大家考研上岸

祝大家工作顺利

祝大家得偿所愿

祝大家如愿以偿

点赞收藏关注哦