【霍洛维兹数据结构】数组和结构 | ARRAYS AND STRUCTURES | THE SPARSE MATRIX 稀疏矩阵

前言：

最近在读霍罗维兹的《数据结构基础》（Fundamentals of Data Structures in C），本篇博客为阅读笔记和知识总结。（ARRAYS AND STRUCTURES）

Ⅰ. 数组 - ARRAYS

0x00 抽象数据类型 - The Abstract Data Type

📚 通常，数组通常被看作是 "一组连续地内存地址" 。

作为 ADT 的数组是 <索引，值> ，每个被定义的索引都有一个与之相关的值。

除了创建一个新数组外，大多数语言只为数组提供了两种标准操作：

① 检索一个值

② 储存一个值

ADT - 数组

object：一组 <index, value> 对于索引的每个值，都有一个来自集合项的值。索引是一维或多维度的有限集合，

例如： 为一维。

 为二维。

functions：

对于所有

Array Create(j, list)  ::= return an array of j dimensions where list is a j-tuple
                           whose ith element is the size of the ith dimension. Items
                           are undefined.
Item Retrieve(A, i)    ::= if (i ∈ index) return the item associated with index
                           value i in array A
                           else return error.
Array Store(A, i, x)   ::= if (i ∈ index) return an array that is identical to
                           array A except the new pair <i, x> has been inserted
                           else return error.
end Array

0x01 C语言中的数组

C语言中一维数组的声明：

int list[5], *plist[5];

内存分配：

C将 list[i] 解释为一个指向整数的指针。

观察下面声明之间的区别：

int* list1;
int list2[5];

变量 list1 和 list2 都是指向一个整数类型对象的指针。

list2 是一个指向 list2[0] 的指针，list2 + i 是一个指向 list2[i] 的指针。

因此， （list2 + i)  等于 &list2[i]
所以，  *(list2 + i) 等于 list2[i]

0x02 例子

[Program 2.1]

#define MAX_SIZE 100
float sum(float [], int);
float input[MAX_SIZE], answer;
int i;
void main(void)
{
    for (i=0; i<MAX_SIZE; i++)
        input[i] = i;
    answer = sum(input, MAX_SIZE);
    printf("The sum is: %f\n", answer);
}
float sum(float list[], int n)
{
    int i;
    float tempsum = 0;
    for (i=0; i<n; i++)
        tempsum += list[i];
    return tempsum;
}

当 sum 被调用时，input = &input[0]  被复制到一个临时位置，并于正是参数列表相关联起来。

当 list[i] 出现在赋值语句中 " = " 的右侧时，就会触发解引用，并返回 (list + i) 所指向的值。

如果 list[i] 出现在 " = " 的左侧，那么右侧产生的值将被存储在 (list + i) 处。

[一维数组寻址]

int one[] = {0, 1, 2, 3, 4};

打印出 this 的第 i 个元素的地址和在这个地址找到的值

void print1(int *ptr, int rows)
{
    /* 使用指针打印出一个一维数组 */
    int i;
    printf("Address Contents\n");
    for (i=0; i<rows; i++)
        printf("%8u%5d\n", ptr + i, *(ptr + i));
    printf("\n");
}

Ⅱ.  动态分配数组 - DYNAMICALLY ALLOCATED ARRAYS

0x00 一维数组 - ONE-DIMENSIONAL ARRAYS

📚 如果用户向改变数组的大小，我们必须改变 MAX_SIZE 并重新编译程序。

为了解决这种问题，我们可以把这个 "决定" 推迟到运行时再去解决，当我们对所需的数组大小有一个很好地估计时再分配数组。

int i, n, *list;
printf("需要生成的数字数量");
scanf("%d", &n);
if ( n < 1 ) {
    fprintf(stderr, "error! \n");
    exit(EXIT_FAILURE);
}
MALLOC(list, n * sizeof(int));

0x01 二维数组 - TWO-DIMENSIONAL ARRAYS

📚 二维数组可以理解为，它的每个元素都是一个一维数组。

举个例子：

int x[3][5];

三维数组可以理解为，它的每个元素本身是一个二维数组。

int** make2dArray(int rows, int cols)
{ /* create a two dimensional rows * cols array */
    int **x, i;
    /* get memory for row pointers */
    MALLOC (x, rows * sizeof (*x));
    /* get memory for each row */
    for (i=0; i < rows; i++)
        MALLOC (x[i], cols * sizeof (**x));
    return x;
}
cf. x = (int **)malloc(rows*sizeof(*x));

void* calloc(elt_count, elt_size)

分配一个足够大的内存区域来容纳一个 elt_count 元素的数组，每个元素的大小为 elt_size，并且将内存区域设为0。

void* realloc(p, s)

将 p 所指向的内存块的大小重新分配，改为 s。

Ⅲ.  结构体和联合体

0x00 结构体

结构体 Structure（在许多其他编程语言中称为 record），是一个数据项的集合，其中每个项目都有类型和名称的标识。

结构体是一些值的集合，这些值称为成员变量。结构的每个成员以是不同类型的变量。

如果说数组是同一类型的变量集合，那么结构体就是各种各样变量的集合。因为结构体支持所有C数据类型，所以结构体内部也可以有数组存在。

💬 举个栗子，如果要保存学生的信息（学号，姓名，年级），想将信息捆绑在一起，作为一个变量来管理会十分便利。像这样把多个数据类型捆绑在一起的，就叫做结构体。

声明结构体

💬 上述举的例子（保存学生信息）：

struct {
    int id;
    char name[26];
    double gradePoints;
} student;

但是，对于有多个学生的情况，需要多个这样的变量。考虑到每次都是用 struct {} 语法来产生变量的方法未免过于繁琐，C语言允许将结构体当作一个数据类型来方便我们更好地使用。如下所示，

ps：tag 表示 结构体标签

struct tag {
    type1 fieldName1;
    ...
    typeN fieldNameN;
};
struct tag variable_identifier1;
struct tag variable_identifier2;

struct student{
    int id;
    char name[26];
    float grade;
};
struct student xiaoming;
struct student xiaohong;

综上所述得出总结：结构体是用户自定义的类型 (user-defined type) 。

结构体初始化

下面将演示结构体变量声明后初始化的过程：

💬 声明变量时允许指定初始值：

为了接近结构体的变量，我们可以使用 "点操作符（·）" 来获取它。值得一提的是，字符串复制时要使用 strcpy。

结构体与 typedef

📚 当然，typedef 还可以作用于结构体。这样可以让结构体用起来更爽，而不用拖着 struct name 又臭又长的玩意来定义变量，使用方法如下：

💬 之前举的学生结构体的例子，我们现在可以升级一下了：

使用 typedef 前

struct student {
    int id;
    char name[26];
    float grade;
};
struct student xiaohong;

使用 typedef 后：

typedef struct {
    int id;
    char name[26];
    float grade;
} stu;
stu s1;

[Program 2.4]

#define FALSE 0
#define TRUE 1
typedef struct {
    char name[10];
    int age;
    float salary;
} humanBeing;
humanBeing person1, person2;
int humans_equal(human_being person1, human_being person2)
{
    /* return TRUE if person1 and person2 are the same human being
    otherwise return FALSE */
    if (strcmp(person1.name, person2.name))
        return FALSE;
    if (person1.age != person2.age)
        return FALSE;
    if (person1.salary != person2.salary)
        return FALSE;
    return TRUE;
}
if (humans_equal(person1, person2))
    printf("The two human beings are the same");
else
    printf("The two human beings are not the same");

结构体嵌套

typedef struct {
    int month;
    int day;
    int year;
} date;
typedef struct human_being {
    char name[10];
    int age;
    float salary;
    date dob;
};
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

0x01 联合体（union）

字段共享他们的内存空间，在任何时候只有一个字段的联合是有效的。

typedef struct sex-type {
    enum tag_field {female, male} sex;
    union {
    int children;
    int beard;
    } u;
};
typedef struct human_being {
    char name[10];
    int age;
    float salary;
    date dob;
    sex_type sex_info;
};
human_being person1, person2;
person1.sex_info.sex = male;
person1.sex_info.u.beard = FALSE;
person2.sex_info.sex = female;
person2.sex_info.u.children = 4;

0x02 内部运作结构 -  Internal Implementation of Structures

大多数情况下，我们不需要关心C语言编译器究竟如何在内存中存储结构域。

一般来说，这些值将按照结构定义中指定的顺序使用递增的地址位置以相同的方式存储。

0x03 自律性结构 - Self-Referential Structures

一个或多个组成部分是指向自身的指针。

自律性结构通常需要动态存储管理例程（malloc 和 free）来明确获取和释放内存。

typedef struct list {
    char data;
    list *link;
};
list item1, item2, item3;
item1.data = 'a';
item2.data = 'b';
item3.data = 'c';
item1.link = item2.link = item3.link = NULL;
item1.link = &item2;
item2.link = &item3;

Ⅳ.  多项式 - POLYNOMIALS

0x00 抽象数据类型

数组不仅本身是数据结构，我们还可以用它来实现其他抽象的数据类型。

最简单和最常见的数据结构之一，顺序表和线性表。

例子：

一周七天（周一周二周三周四周五周六周日）

一副牌（A，2，3，4，5，6，7，8，9，10，J，Q，K）

建筑物的层数（地下室、停车场、大厅、第一层、第二层）

对顺序表的可能操作：

寻找某列表长度 n

从左到右（或从右到左）遍历列表中的元素。

从一个列表中检索第 项，

替换列表中的第 个位置的元素，

在一个列表中的第 个位置插入一个新元素，

之前的编号为 的元素变成编号为 的元素。

从一个列表的第 个位置删除一个元素，

之前的编号为 的元素变成编号为 的元素。

实现（表示顺序表的方法）

顺序映射

非顺序映射

多项式（viewed from a mathematical perspective）

从数学角度来看，多项式是项的综合，其中每个都是一个 ，

是一个变量， 是系数， 是指数。

举个例子：

多项式之与乘积的标准数学定义：

[ADT 2.2] ADT - 多项式

0x01 多项式表示法 - Polynomial Representation

[Program 2.5] Initial version of padd function

/* d = a + b, where a, b, and d are polynomials */
d = Zero();
While(!IsZero(a) && ! IsZero(b)) do {
    switch COMPARE(Lead_Exp(a), Lead_Exp(b)) {
        case -1 : d = Attach(d, Coef(b, Lead_Exp(b)), Lead_Exp(b));
                  b = Remove(b, Lead_Exp(b));
                  break;
        case 0 : sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b));
                 if (sum) {
                    Attach(d, sum, Lead_Exp(a));
                    a = Remove(a, Lead_Exp(a));
                    b = Remove(b, Lead_Exp(b));
                 }
                 break;
    case 1 : d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a));
             a = Remove(a, Lead_Exp(a));
    }
}
insert any remaining terms of a or b into d

Representation

指数是按递减顺序唯一排列的。

<Dense Representation>

包括多项式中的所有项：

#define MAX_DEGREE 101
typedef struct {
    int degree;
    float coef[MAX_DEGREE];
} polynomial;

令 是一个多项式类型的遍历，我们可以表示多项式  ，

通过设置    和   。

虽然这种表示方法带来了非常简单的算法，但它浪费了大量的空间。

例如，如果   ，或多项式是稀疏的（Sparse），

例子：   和  

<稀疏表示 - Sparse Representation>

为了保留空间，我们只用一个全局数组来存储我们所有的多项式。

#define MAX_TERMS 100
typedef struct {
    float coef;
    int expon;
} polynomial;
polynomial terms[MAX_TERMS];
int avail = 0;

例子：

为了表示零多项式 ，设   .

0x02 多项式加法 - Polynomial Addition

[Program 2.6] : Function to add two polynomials

void padd(int starta, int finisha, int startb, int finishb, int* startd, int* finishd)
{
  /* add A(x) and B(x) to obtain D(x) */
  float coefficient;
  *startd = avail;
  while (starta <= finisha && startb <= finishb)
    switch (COMPARE(terms[starta].expon, terms[startb].expon)) {
    case -1: /* a expon < b expon */
      attach(terms[startb].coef, terms[startb].expon);
      startb++;
      break;
    case 0: /* equal exponents */
      coefficient = terms[starta].coef + terms[startb].coef;
      if (coefficient)
        attach(coefficient, terms[starta].expon);
      starta++; startb++;
      break;
    case 1: /* a expon > b expon */
      attach(terms[starta].coef, terms[starta].expon);
      starta++;
    }
  /* add in remaining terms of A(x) */
  for (; starta <= finisha; starta++)
    attach(terms[starta].coef, terms[starta].expon);
  /* add in remaining terms of B(x) */
  for (; startb <= finishb; startb++)
    attach(terms[startb].coef, terms[startb].expon);
  *finishd = avail - 1;
}

[Program 2.7] : Function to add a new term

void attach(float coefficient, int exponent)
{
  /* add a new term to the polynomial */
  if (avail >= MAX_TERMS) {
    fprintf(stderr, "Too many terms in the polynomial");
    exit(1);
  }
  terms[avail].coef = coefficient;
  terms[avail++].expon = exponent;
}

对 padd 的分析

时间复杂度为 ，其中 和 分别为 和 的项数。

Ⅴ. 稀疏矩阵（THE SPARSE MATRIX）

0x00 ADT

稀疏矩阵：若矩阵 中 非零元素的个数远小于零元素的个数，我们称 为稀疏矩阵

如果用一个二维数组来表示稀疏矩阵，就要用大量的空间来存储相同的值（0），不仅如此，当矩阵很大时，这种实现方式是行不通的，因为大多数编译器对数组的大小都有限制的。

0x01 ADT - 稀疏矩阵

0x02 稀疏矩阵的表示

我们可以唯一地表示矩阵中的任何元素，我们可以利用 row，col，value 的方式存储和定位稀疏矩阵中的非零元素，这种存储稀疏矩阵的方式称为三元组 Triple。

by a triple <row, col, value>.

我们组织三元组，使行指数按升序排列，在具有相同行指数的三元组中，按列指数的升序排列。

为了确保操作能够停止，我们必须知道行和列的数量，以及矩阵中的非零元素的数量。

// Sparse_Matrix Create(max_row, max_col) ::=
#define Max_TERMS 101 /* maximum number of terms +1*/
typedef struct {
    int col;
    int row;
    int value;
} term;
term a[MAX_TERMS];

0x03 矩阵的转置 - Transposing A Matrix

<一个简单的算法>

对于每一行的

       取元素 并储存它

       作为转置的元素

在我们处理完前面的所有元素之前，我们不会确切的知道在转置中吧元素

放在了哪里，比如：

需要连续的插入。我们必须移动元素以保持顺序正确。

我们可以通过通过使用列的索引来确定元素在矩阵中的位置，来避免这种数据移动。

对于第 列的所有元素，将元素 放在元素 中。

[Program 2.8]

时间复杂度：  

如果   ， 变为 。

一个使用密集表示的转置算法

for (j = 0; j < columns; j++)
    for (i = 0; i < rows; i++)
        b[j][i] = a[i][j];

时间复杂度：

通过使用更多一点的存储空间来实现更好的算法

fast_transpose

该算法，首先确定原始矩阵每一列的元素数量。

该数字给出了转置矩阵中每一行的元素数。

时间复杂度：

如果 ，

那么 变为

使用了额外的数组，row_terms 和 starting_pos 。

如果我们把起始位置放到 row_terms 使用的空间里，我们就可以把空间减少到一个数组。

0x04 矩阵乘法

给出两个矩阵 和 ，其中 是 ， 是

乘积矩阵 为 ，它的 元素为：

<使用密集表示法的矩阵乘法算法>

for (i = 0; i < rows_a; i++) {
    for (j = 0; j < cols_b; j++) {
        sum = 0;
        for (k = 0; k < cols_a; k++)
            sum += a[i][k]*b[k][j];
        d[i][j] = sum;
    }
}

时间复杂度：

注意，两个稀疏矩阵的乘积可能就不再是稀疏的了。例如：

[Program 2.10]

矩阵 分别存储在数组 中， 的转置存储在 new_b 中。

使用变的变量：

row - 目前正在与B的列相乘的A的行
row_begin - 当前行的第一个元素在a中的位置
column - 目前正在与A的某一行相乘的B的列
totald - 乘积矩阵D的当前元素数
i, j - 用于连续检查A行和B列中的元素的指针

void mmult(term a[], term b[], term d[])
/* multiply two sparse matrices */
{
    int i, j, column, totalb = b[0].value, totald = 0;
    int rows_a = a[0].row, cols_a = a[0].col, totala = a[0].value;
    int cols_b = b[0].col;
    int row_begin = 1, row = a[1].row, sum = 0;
    term new_b[MAX_TERMS];
    if (col_a != b[0].row) {
        fprintf(stderr, “Incompatible matrices\n”);
        exit(1);
    }
    fast_transpose(b, new_b);
    /* set boundary condition */
    a[totala+1].row = rows_a;
    new_b[totalb+1].row = cols_b; new_b[totalb+1].col = -1;
    for (i = 1; i <= totala; ) {
        column = new_b[1].row;
        for (j = 1; j <= totalb+1; ) {
        /* multiply row of a by column of b */
            if (a[i].row != row) {
                storesum(d, &totald, row, column, &sum);
                i = row_begin;
                for ( ; new_b[j].row == column; j++)
                                ;
                column = new_b[j].row;
            }
            else if (new_b[j].row != column) {
                storesum(d, &totald, row, column, &sum);
                i = row_begin;
                column = new_b[j].row;
            }
            else switch (COMPARE(a[i].col, new_b[j].col)) {
                case –1 : /* go to next term in a */
                    i++; break;
                case 0 : /* add terms, go to next term in a and b */
                    sum += (a[i++].value * new_b[j++].value);
                    break;
                case 1 : /* go to next term in b */
                    j++;
            }
        } /* end of for j <= totalb+1 */
        for ( ; a[i].row == row; i++)
                ;
        row_begin = i; row = a[i].row;
    } /* end of for i <= totala */
    d[0].row = row_a; d[0].col = cols_b;
    d[0].value = totald;
}

注意，我们在 a 和 new_b 中都引入了一个附加项：

a[totala+1].row = rows_a;
new_b[totalb+1].row = cols_b;
new_b[totalb+1].col = -1;

时间复杂度

for 循环前：

fast transpose - O(cols_b + totalb) time.

外层 for 循环被迭代了rows_a 次：

在每次迭代中，乘积矩阵D的一行由内部 for 循环计算，在每个迭代中，i或者j两者都增加1，或者i被重置到 row_begin

j 的最大总增量为 totalb+1。 那么当第k行被处理时，i最多可以增加几次，i最多被重置到row_begin的cols_b次。 因此，i的最大总增量是cols_b-。 内层for循环需要 时间，列被重置。 因此外部 for 循环需要

值得注意的是，如果 且 ，那么他的时间复杂度会变为 。

参考资料：

Fundamentals of Data Structures in C

本章完。