文章目录

前言

一、数组的定义

1、数组

2、数组与线性表的关系

3、数组的抽象数据类型

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

1、引入：

2、一维数组

 3、二维数组的顺序存储

（1）以行序为主序存放

（2） 以列序为主序存放

（3）计算二维数组元素地址的通式：

 4、三维数组

5、n维数组

6、总结

7、练习

三、矩阵的压缩存储

1、矩阵的压缩的出现与定义

 2、特殊矩阵介绍

（1）对称矩阵

 （2）三角矩阵

3、稀疏矩阵的存储结构

（1）三元组顺序表

（2）行逻辑链接的顺序表

（3）十字链表

四、广义表的定义

1、广义表的定义

2、广义表与线性表的区别

3、广义表的特点

4、广义表的类型定义

5、练习 

五、广义表的存储表示

1、头尾链表存储表示（表头表尾分析法）

2、广义表的扩展线性链表存储表示（子表分析法） 

总结

---

前言

本文主要介绍数据结构（C语言版）第五章数组和广义表的内容。主要包括数组的定义、数组的顺序表示和实现、矩阵的压缩存储、广义表的定义、广义表的存储结构。

其中重难点在于数组的两种存储表示方式以及对应的地址计算法、对矩阵进行压缩存储时下表变换公式、广义表的结构特点及其存储表示方法。

---

一、数组的定义

1、数组

由一组名字相同、下标不同的变量构成。
1.按维数分为：一维数组、二维数组、三维数组、……
2.按维数和维界是否可变分为：
    ●定长（/静态）数组
    ●可变长（/动态）数组
3.每维下标的取值范围：
    下标下界（默认0）、下标上界
本节所讨论的数组与高级语言中的数组区别：
高级语言中的数组是顺序结构；
而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。

“数组的处理比其它复杂的结构要简单”，怎么理解？
①数组中各元素具有统一的类型；
②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。
③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。

2、数组与线性表的关系

数组可以看成是线性表的推广，特点是结构中的元素本身可以是具有某种结构的数据，但属于同一类型。
一维数组的特点：1个下标，ai是ai+1的直接前驱；当n=1时，n维数组就退化为定长的线性表。

二维数组的特点：2个下标，每个元素a受到两个关系（行关系和列关系）的约束。
二维数组可以看成数据元素是线性表的线性表  A=(a1,a2,…,ap)(p=m或n)

（1）行向量的一维数组 ai=(ai1,ai2,…,aim) 1≤i≤m
（2）列向量的一维数组 aj=(a1j,a2j,…,amj) 1≤ j≤n

 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。
例：定义一个M行N列的二维数组类型Array2
typedef ElemType Array2[M][N];
等价于：
typedef ElemType Array 1[N];

typedef Array1 Array2[M];
二维数组可看成以定长线性表为元素的特殊定长线性表。

N维数组的特点：n个下标，每个元素受到n个关系约束，一个n维数组可以看成是由若干个n-1维数组组成的线性表。
形如： ElemType A[b1][b2]...[bn];   bi是数组第i维的长度；含有个n数据元素； 每个元素都受n个线性关系的约束，即在每个关系中，元素aj1j2...jn(1≤j≤bi-2）都有一个直接后继元素和一个直接前驱元素。

3、数组的抽象数据类型

ADT Array {
数据对象：
D ={aj1,j2...jn|ji=0,…,bi-1, i=1,2…,n, aj1,j2..jn ∈Elemset}其中，n（n>0）称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标。
数据关系：R={R1,R2,...Rn}
 Ri = { |0≤jk≤bk-1,1≤k≤n目k≠i,0≤ji≤bi-2, i=2,...,n
aj1j2,...ji...jn,aj1,j2,...ji+1...jn∈D}
数组的抽象数据类型
基本操作：
(1)InitArray(&A,n,bound1, boundn)//构造数组A
(2) DestroyArray (&A)//销毁数组A
(3)Value(A,&e,index1,………,indexn)//取数组元素值
(4)Assign(A,&e,index1,………,indexn)//给数组元素赋值
}ADT Array

例如：二维数组定义

数据对象：
D ={aij|0≤i≤b₁-1,0≤j≤b₂-1}
数据关系：
R={ROW,COL}
ROW = { | 0≤i≤b₁-2,0≤j≤b₂-1}COL = {|0≤i≤b₁-1, 0≤j≤b₂-2}
基本操作
InitArray(&A, n, bound1,..., boundn)
操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。


DestroyArray(&A)
操作结果：销毁数组A。
//例如：DestroyArray(B); 销毁前面创建的三维数组B

Value(A, &e, index1, ……, indexn)
初始条件：A是n维数组，e为元素变量，随后是n个下标值。
操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。


Assign(&A, e, index1,., indexn)
初始条件：A是n维数组，e为元素变量，随后是n个下标值。
操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返OK。

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

1、引入：

问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？
解决办法：事先约定按某种次序将数组元素排成一个序列，然后将这个线性序列存入存储器中。
例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。
注意：
●若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；
●约定的次序不同，则计算元素地址的公式也有所不同；
●C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。

2、一维数组

LOC(i)=LOC(i-1)+l=a+i*l
注意：
●这里数组下标默认从0开始；
●若下标从1开始，上式如何修改？i改为i-1 

 3、二维数组的顺序存储

（1）以行序为主序存放

 

以行序为主序的存储映像：

二维数组A中任一元素ai,j的存储位置：LOC(i,j) = LOC(0,0) +(n x i + j) x L （其中LOC(0,0)称为基地址或基址）

（2） 以列序为主序存放

 

以行序为主序的存储映像：

二维数组A中任一元素ai,j的存储位置： LOC(i,j)=LOC(0,0)+(m×j+i)×L

（3）计算二维数组元素地址的通式：

 4、三维数组

按页/行/列存放，页优先的顺序存储

a[m1][m2][m3]各维元素个数为m₁,m₂,m₃

下标为i₁，i₂，i₃的数组元素的存储位置： 

5、n维数组

 各维元素个数为b1,b2,b3,……,bn
下标为j1,j2,j3,……,jn的数组元素的存储位置：

Cn=L,Ci-1=bi×Ci,1

6、总结

 无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）
①开始结点的存放地址（即基地址）

②维数和每维的上、下界；

③每个数组元素所占用的单元数

7、练习

 

三、矩阵的压缩存储

1、矩阵的压缩的出现与定义

以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题：
（1）零值元素占了很大空间；
（2）计算中进行了很多和零值的运算。

解决问题的原则
（1）尽可能少存或不存零值元素；
（2）尽可能减少没有实际意义的运算；
（3）操作方便。即：能尽可能快地找到与下标值（i，j）对应的元素，能尽可能快地找到同一行或同一列的非零值元。

压缩存储——若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。
什么样的矩阵能够压缩——一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
稀疏矩阵——矩阵中非零元素的个数较少（一般小于5%）

假设m行n列的矩阵含t个非零元素，则称δ=t / (mxn)为稀疏因子。通常认为δ≤0.05的矩阵为稀疏矩阵

 2、特殊矩阵介绍

特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。

（1）对称矩阵

【特点】在nxn的矩阵a中，元素满足如下性质：aij=aji(1≤i，j≤n)

【存储方法】只存储下（或者上）三角（包括主对角线）的数据元素。共占用n（n+1）/2个元素空间: sa[0.. n(n+1)/2-1]

数组下标（i,j）确定存储地址
按行序为主序存储对称矩阵的下三角（包括对角线）中的元素

 （2）三角矩阵

【特点】对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c。

【存储方法】重复元素c共享一个元素存储空间，共占用 n(n+1)/2+1个元素空间：sa[0..n(n+1)/2]，即与对称矩阵相同，只需再加一个空间用于存储常数c。

数组下标（i,j）确定存储地址

3、稀疏矩阵的存储结构

（1）三元组顺序表

①存储结构定义

#define MAXSIZE 12500//假设非零元的最大个数
typedef struct {
  int i, j;//该非零元的行下标和列下标
  ElemType e;/∥该非零元的值
}Triple;//三元组类型


typedef struct {
  Triple data[MAXSIZE+1];//data[0]未用;表示非零元的三元组通常以行序为主序存放
  int    mu,nu,tu;//矩阵的行数、列数、非零元个数
}TSMatrix;//稀疏矩阵类型

注意：为更可靠描述，通常再加一行“总体”信息：即总行数、总列数、非零元素总个数
稀疏矩阵压缩存储的缺点：将失去随机存取功能 

② 矩阵的逆置运算

一个m×n的矩阵M，它的转置T是一个n×m的矩阵，且mij=tji, 1≤i≤m, 1≤j≤n
【例】矩阵M转置得到矩阵T

如何求转置矩阵？
用常规的二维数组表示时的算法

for (col=1; col<=nu; ++col)
   for(row=1;row<=mu;++row)
      T[col][row]= M[row][col];

其时间复杂度为：O（mu×nu）

 采用三元组顺序表如何实现？

思考：若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算吗？
答：不正确！
除了：（1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；
还应该：（2）T的总行数mu和总列数nu与M的不同（互换）
（3）重排三元组内元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。
上述（1）和（2）容易实现，难点在（3）。
有两种实现方法——压缩转置和（压缩）快速转置

方法1：压缩转置

思路：反复扫描a.data中的列序，从小到大依次进行转置。

压缩转置算法描述：

Status TransPoseSMatrix(TSMatrix M, TSMatrix &T)
{ //用三元组表存放稀疏矩阵M，求M的转置矩阵T
  T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
  if(T.tu)
  {
    q=1；//q是转置矩阵T的结点编号//外循环处理矩阵M中的各列
    for(col=1;col<=M.nu;col++)//col是扫描M三元表列序的变量
    {  
      for(p=1; p<=M.tu; p++)//p是M三元组表中结点编号
      {
        if (M.data[p].j==col)
        {
           T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
           T.data[q].value=M.data[p].value; q++;
        }//内循环扫描三元组一遍，找到co1列的所有元素
      }
    }
   }
return OK;
}//TranposeSMatrix;

压缩转置算法效率分析
分析：主要时间消耗在查找M.data[p]j=col的元素，由两重循环完成：

for(col=1;col<=M.nu;col++)循环次数=nu

  for(p=1;p<=M.tu;p++)循环次数=tu

所以该算法的时间复杂度为O（nu*tu)——即M的列数与M中非零元素的个数之积
最恶劣情况：M中全是非零元素，此时tu=mu*nu，时间复杂度为O（nu2*mu）
注：若M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是O（nu*mu）
结论：压缩转置算法不能滥用。
前提：仅适用于非零元素个数很少（即tu<

方法2：快速转置
思路：依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。

关键：怎样寻找b.data的“恰当”位置？

设计思路：
如果能预知M矩阵每一列（即T的每一行）的非零元素个数，又能预知第一个非零元素在b.data中的位置，则扫描a.data时便可以将每个元素准确定位（因为已知若干参考点）。
请注意a.data特征：每列首个非零元素必定先被扫描到。
实现：
设两个数组
num[col]：表示矩阵M中第col列中非零元个数
cpot[col]：指示M中第col列第一个非零元在T.data中位置cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]; (2≤col ≤M.nu)

令：M中的列变量用col表示；
num[col]：存放M中第col列中非0元素个数，
cpot[ col]：存放M中第col列的第一个非O元素的位置，（即b.data中待计算的“恰当”位置所需参考点）

讨论：按列优先的辅助向量求出后，下一步该如何操作？
由a.data中每个元素的列信息，即可直接查出b.data中的重要参考点之位置，进而可确定当前元素之位置！

 

快速转置算法描述：

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{  //M用顺序存储表示，求M的转置矩阵T
   T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
   if(T.tu)
  {
     for(col=1;col<=M.nu;++col)  num[col]=0;//初始化M中各列元素个数为0
     for(t=1;t<=M.tu；++t)   ++num[M.data[t].j]；//求M中每一列非零元个数
     cpot[1]=1；//再生成每列首元位置辅助向量表
     for (col=2; col<=M.nu; ++col)
         cpot[col]= cpot[col-1]+ num[col-1];
     for(p=1;p<=M.tu;++p)//转置矩阵元素。p指向a.data
    { 
       col=M.data[p].j； q=cpot[col];//查辅助向量表得q,即T中位置
       T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i;
       T.data[q].e =M.data[p].e; 
       ++cpot[col];//重要语句！修改向量表中列坐标值，供同一列下一非零元素定位之用！
    }

  }
  return OK;
}// FastTransposeSMatrix

 快速转置算法效率分析

1.与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组（num[]和cpos[]）
2.从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。

for(col=1;col<=M.nu;col++)  循环次数=nu;

for( i = 1; i <=M.tu; i ++)循环次数=tu；

for(col=2;col<=M.nu;col++)循环次数=nu;

for(p =1;p <=M.tu;p ++)循环次数=tu；

该算法的时间复杂度=（nu*2)+（tu*2)=O（nu+tu)
讨论：最恶劣情况是tu=nu*mu（即矩阵中全部是非零元素），而此时的时间复杂度也只是O（mu*nu），并未超过传统转置算法的时间复杂度。

小结：传统转置：O（mu*nu) 压缩转置：O（mu*tu）
压缩快速转置：O（nu+tu）——牺牲空间效率换时间效率。

 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。

（2）行逻辑链接的顺序表

行逻辑链接的顺序表——三元组顺序表中，增加指示“行”信息的辅助数组rpos。
●行逻辑链接的顺序表的存储表示：

#define MAXRC 500 //假设矩阵的最大行数为500
typedef struct {
  Triple data[MAXSIZE＋1];//非零元三元组表
  int rpos[MAXRC+1]；//各行第一个非零元位置表
  int mu, nu, tu;
}RLSMatrix；∥行逻辑链接顺序表类型

 矩阵的乘法运算

设M是m1×n1矩阵，N是m2×n2矩阵，当n1=m2时有Q=M×N是m1×n2矩阵，且

 

矩阵乘法的经典算法：

for (i=1;i<=m1; ++i)
  for (j=1; j<=n2; ++j)
  {
     Q[i][j]= 0;
     for(k=1;k<=nl;++k)
       Q[i][i] += M[i][k]* N[k][i]; 
  }

经典算法中，不论Mik和Nkj的值是否为0，都要进行一次乘法运算，多余。
其时间复杂度为：O（m1×n2×n1），不适用于三元组表压缩存储的稀疏矩阵

在对稀疏矩阵进行乘法运算时，应免去这种无效操作只需在M.data和N.data中找到相应的各对元素（即M.Data中j值和N.data中的i值相等的各对元素）相乘即可。

①算法思想：

【步骤1】（并行地）求矩阵Q中第行的各个元素，

只需找到M.data中第i行的各个非零元，将它与N.data中第k行的各个非零元对应相乘，并累加到相应的累加和变量上。（稀疏矩阵的行逻辑链接顺序表中M.rpos和N.rpos提供了该信息。）
【步骤2】挑出Q中第i行的非零元，压缩存储到Q.data中。

②稀疏矩阵相乘的算法基本操作是：
对于M中的每个元素M.data[p](p=1,2,…,m.tu),找到N中所有满足条件M.data[p].j=N.data[q].i
的元素N.data[q]，求得M.data[p].v和N.data[q].v的乘积，乘积矩阵Q中的每个元素的值是一个累加和，这个乘积是Q[i][j]的一部分。

为便于操作，应对每个元素设一累计和的变量，其初值为0，然后扫描数组M，求得相应元素的乘积累加到适当的求累计和的变量上。

③具体算法描述

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q)
{
   if (M.nu != N.mu) return ERROR;
   Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//初始化
   if（M.tu*N.tu！=0)
   { //Q是非零矩阵
     for (arow=1; arow<=M.mu; ++arow)
    { //处理M的每一行
      ctemp[] = 0;//当前行各元素累加器清零
      Q.rpos[arow]= Q.tu+1;
      if (arow MAXSIZE) return ERROR;
         Q.data[Q.tu] = {arow, ccol, ctemp[ccol]};
       }
   }
   return OK;
}// MultSMatrix

 ④分析上述算法的时间复杂度：
累加器ctemp初始化的时间复杂度为O(M.muxN.nu),
求Q的所有非零元的时间复杂度为O(M.tuxN.tu/N.mu),
进行压缩存储的时间复杂度为O(M.muxN.nu),
总的时间复杂度就是O(M.muxN.nu+M.tuxN.tu/N.mu)。

若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数M.tu=δM×mxn,
N中非零元的个数N.tu=δnxnxp,相乘算法的时间复杂度就是O（mxp×（1+nδMδN))，
当δM<0.05和δN<0.05及n<1000时，相乘算法的时间复杂度就相当于O（m×p）。

（3）十字链表

用途：方便稀疏矩阵的加减运算；
方法：每个非0元素占用5个域。
十字链表的特点：
每个非零元素用一个含五个域的结点表示：
●i，j，e分别表示其所在行、列和值；
●向右域right用以链接同一行中的下一个非零元素；
●向下域down用以链接同一列中的下一个非零元素

 

四、广义表的定义

1、广义表的定义

广义表（列表）：n（≥0）个表元素组成的有限序列，记作LS=(a0,a1,a2,……,an-1)

LS是表名，ai是表元素，ai或者是原子（基本的可处理的数据单位）或者是广义表。若ai是广义表，则称它为Ls的子表。n为表的长度。n=0的广义表为空表。

其中a1为表头(Head),剩余部分为表尾(Tail)

显然，广义表是一个递归的定义LS = ( a1, a2, …, an )
其中：ai或为原子或为广义表
表头（Head）表尾（Tail)

在广义表中约定：
①第一个元素是表头，而其余元素组成的表称为表尾；
②用小写字母表示原子类型，用大写字母表示列表。
任何一个非空广义表LS=（a1,a2,……,an）均可分解为：
表头Head(LS)=a1
表尾Tail(LS)=(a2,……,an)两部分。

特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。

2、广义表与线性表的区别

●线性表的成分都是结构上不可分的单元素
●广义表的成分可以是单元素，也可以是有结构的表
●线性表是一种特殊的广义表
●广义表不一定是线性表，也不一定是线性结构

3、广义表的特点

1）广义表中的数据元素有相对次序；
2）广义表的长度定义为最外层包含元素个数；
3）广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0；“空表”的深度为1
4）广义表可以共享；
5）广义表可以是一个递归的表。   递归表的深度是无穷值，长度是有限值。

举例：求下列广义表的长度

4、广义表的类型定义

ADT Glist{
数据对象：D={ei|i=1,2,…,n；n≥0；ei∈AtomSet或ei∈EGList,AtomSet为某个数据对象}
数据关系：LR={|ei1,ei∈D,2≤i≤n}
基本操作：
//结构的创建和销毁
InitGList(&L);
DestroyGList(&L);
CreateGList(&L,S); CopyGList(&T,L);
//状态函数
GListLength(L); GListDepth(L);
GListEmpty(L); GetHead(L); GetTail(L);
//插入和删除操作
InsertFirst_GL(&L,e);DeleteFirst_GL(&L, &e);
//遍历
Traverse_GL(L, Visit(O);
} ADT Glist

关于GetHead(L)和GetTail(L)

5、练习 

  

五、广义表的存储表示

由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。
注意：列表的“元素”还可以是列表，所以结点可能有两种形式：表结点和原子结点
按原子结点的结构不同，有两种实现方案：头尾链表存储表示（表头表尾分析法）和扩展线性链表存储表示（子表分析法）。

1、头尾链表存储表示（表头表尾分析法）

表结点：由标志域、指示表头的指针域和指示表尾的指针域组成
原子结点：由标志域和值域组成

头尾链表的存储表示：

typedef enum{ATOM,LIST}ElemTag;//0:原子,1:子表
typedef struct GLNode {
  ElemTag tag；/∥公共部分，标志域，用于区分原子结点和表结点
  union{∥原子结点和表结点的联合部分
  AtomType atom;/∥原子结点的数据域
  struct {struct GLNode *hp, *tp;} ptr;//表结点的表头和表尾指针域
  }
}*GList；∥广义表类型

 表头表尾分析法

2、广义表的扩展线性链表存储表示（子表分析法） 

表结点：由标志域、指示表头的指针域和指示下一元素的指针域组成。
原子结点：由标志域、值域和指示下一元素的指针域组成

 

 广义表的扩展线性链表存储表示

typedef enum{ATOM,LIST}ElemTag;//0:原子,1:子表
typedef struct GLNode {
  ElemTag tag;//公共部分，用于区分原子结点和表结点
  union{//原子结点和表结点的联合部分
  AtomType atom;//原子结点的值域
  struct GLNode*hp;∥表结点的表头指针
  }
  struct GLNode*tp;//相当于线性链表的next,指向下一个元素结点
}*GList;/∥广义表类型

 子表分析法

---

总结

以上主要介绍数据结构（C语言版）第五章数组和广义表的内容。主要包括数组的定义、数组的顺序表示和实现、矩阵的压缩存储、广义表的定义、广义表的存储结构。

希望你在阅读完后能够掌握数组的定义、数组与线性表的关系、数组的顺序存储数与顺序存储结构、数组元素存储位置的计算、特殊矩阵的压缩存储。掌握广义表的定义、性质及其GetHead和
GetTail的操作。理解广义表的存储结构——头尾链表和扩展线性链表。