树的遍历

本文最后更新于：2 分钟前

串存储结构及其实现

数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。

严格意义上讲，串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有”一对一”的逻辑关系。只不过串结构只用于存储字符类型的数据。

数据结构中，根据串中存储字符的数量及特点，对一些特殊的串进行了命名，比如说：

空串：存储 0 个字符的串，例如 S = “”（双引号紧挨着）；

空格串：只包含空格字符的串，例如 S = “ “（双引号包含 5 个空格）；

子串和主串：假设有两个串 a 和 b，如果 a 中可以找到几个连续字符组成的串与 b 完全相同，则称 a 是 b 的主串，b 是 a 的子串。例如，若 a = “shujujiegou”，b = “shuju”，由于 a 中也包含 “shuju”，因此串 a 和串 b 是主串和子串的关系；

需要注意的是，空格串和空串不同，空格串中含有字符，只是都是空格而已。另外，只有串 b 整体出现在串 a 中，才能说 b 是 a 的子串，比如 “shujiejugou” 和 “shuju” 就不是主串和子串的关系。

另外，对于具有主串和子串关系的两个串，通常会让你用算法找到子串在主串的位置。子串在主串中的位置，指的是子串首个字符在主串中的位置。

例如，串 a = “shujujiegou”，串 b = “jiegou”，通过观察，可以判断 a 和 b 是主串和子串的关系，同时子串 b 位于主串 a 中第 6 的位置，因为在串 a 中，串 b 首字符 ‘j’ 的位置是 6。

串存储结构的具体实现

存储一个字符串，数据结构包含以下 3 种具体存储结构：

定长顺序存储：实际上就是用普通数组（又称静态数组）存储。例如 C 语言使用普通数据存储字符串的代码为 char a[20] = “data.biancheng.net”；
堆分配存储：用动态数组存储字符串；
块链存储：用链表存储字符串；

定长顺序存储

串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。

使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。

例如，采用定长顺序存储结构存储 “hello world”，通过目测得知此字符串长度为 11（不包含结束符 ‘\0’），因此我们申请的数组空间长度至少为 11，用 C 语言表示为：

char str[11] = "hello world";

使用定长顺序存储结构存储字符串：

1
2
3
4
5
6
#include<stdio.h>
int main(){
    char str[20]="data.biancheng.net";
    printf("%s\n",str);
    return 0;
}

串的堆分配存储结构

串的堆分配存储，其具体实现方式是采用动态数组存储字符串。

在C语言中，程序会将内存分为 4 个区域，分别为堆区、栈区、数据区和代码区，与其他区域不同，堆区的内存空间需要程序员手动使用 malloc 函数申请，并且在不用后要手动通过 free 函数将其释放。

C 语言中使用 malloc 函数最多的场景是给数组分配空间，这类数组称为动态数组。例如：

char * a = (char*)malloc(5*sizeof(char));

此行代码创建了一个动态数组 a，通过使用 malloc 申请了 5 个 char 类型大小的堆存储空间。

动态数组相比普通数组（静态数组）的优势是长度可变，换句话说，根据需要动态数组可额外申请更多的堆空间（使用 relloc 函数）：
a = (char*)realloc(a, 10*sizeof(char));

通过使用这行代码，之前具有 5 个 char 型存储空间的动态数组，其容量扩大为可存储 10 个 char 型数据。

串的块链存储结构

串的块链存储，指的是使用链表结构存储字符串。

单链表中的 “单” 强调的仅仅是链表各个节点只能有一个指针，并没有限制数据域中存储数据的具体个数。因此在设计链表节点的结构时，可以令各节点存储多个数据。

链表各节点存储数据个数的多少可参考以下几个因素：

串的长度和存储空间的大小：若串包含数据量很大，且链表申请的存储空间有限，此时应尽可能的让各节点存储更多的数据，提高空间的利用率（每多一个节点，就要多申请一个指针域的空间）；反之，如果串不是特别长，或者存储空间足够，就需要再结合其他因素综合考虑；

程序实现的功能：如果实际场景中需要对存储的串做大量的插入或删除操作，则应尽可能减少各节点存储数据的数量；反之，就需要再结合其他因素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define linkNum 3//全局设置链表中节点存储数据的个数
typedef struct Link {
    char a[linkNum]; //数据域可存放 linkNum 个数据
    struct Link * next; //代表指针域，指向直接后继元素
}link; // nk为节点名，每个节点都是一个 link 结构体
link * initLink(link * head, char * str);
void displayLink(link * head);
int main()
{
    link * head = NULL;
    head = initLink(head, "hello world");
    displayLink(head);
    return 0;
}
//初始化链表，其中head为头指针，str为存储的字符串
link * initLink(link * head, char * str) {
    int length = strlen(str);
    //根据字符串的长度，计算出链表中使用节点的个数
    int num = length/linkNum;
    if (length%linkNum) {
        num++;
    }
    //创建并初始化首元节点
    head = (link*)malloc(sizeof(link));
    head->next = NULL;
    link *temp = head;
    //初始化链表
    for (int i = 0; i<num; i++)
    {
        int j = 0;
        for (; j<linkNum; j++)
        {
            if (i*linkNum + j < length) {
                temp->a[j] = str[i*linkNum + j];
            }          
            else
                temp->a[j] = '#';
        }
        if (i*linkNum + j < length)
        {
            link * newlink = (link*)malloc(sizeof(link));
            newlink->next = NULL;
            temp->next = newlink;
            temp = newlink;
        }
    }
    return head;
}
//输出链表
void displayLink(link * head) {
    link * temp = head;
    while (temp) {
        for (int i = 0; i < linkNum; i++) {
            printf("%c", temp->a[i]);
        }
        temp = temp->next;
    }
}

程序输出结果为：
hello world

BF算法（串模式匹配算法）

串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有”主串与子串”关系的算法。

主串与子串：如果串 A（如 “shujujiegou”）中包含有串 B（如 “ju”），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 “包含” 另一个串的关系。

实现串的模式匹配的算法主要有以下两种：

普通的模式匹配算法；
快速模式匹配算法；

BF算法原理即普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

BF 算法的实现思想是：将用户指定的两个串 A 和串 B，使用串的定长顺序存储结构存储起来，然后循环实现两个串的模式匹配过程，C 语言实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <string.h>
//串普通模式匹配算法的实现函数，其中 B是伪主串，A是伪子串
int mate(char * B,char *A){
    int i=0,j=0;
    while (i<strlen(B) && j<strlen(A)) {
        if (B[i]==A[j]) {
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
    if (j==strlen(A)) {
        return i-strlen(A)+1;
    }
    //运行到此，为i==strlen(B)的情况
    return 0;
}
int main() {
    int number=mate("ababcabcacbab", "abcac");
    printf("%d",number);
    return 0;
}

程序运行结果：6

注意，在实现过程中，我们借助 i-strlen(A)+1 就可以得到成功模式匹配所用的次数，也就是串 A 移动的总次数。

BF算法时间复杂度

该算法最理想的时间复杂度 O(n)，n 表示串 A 的长度，即第一次匹配就成功。

BF 算法最坏情况的时间复杂度为 O(n*m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 “0000000001”，而串 A 为 “01”，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。

数组和广义表

数组和其他线性存储结构不同，顺序表、链表、栈和队列存储的都是不可再分的数据元素（如数字 5、字符 ‘a’ 等），而数组既可以用来存储不可再分的数据元素，也可以用来存储像顺序表、链表这样的数据结构。

一维数组，指的是存储不可再分数据元素的数组，二维数组，指的存储一维数组的一维数组，n 维数组，指的是存储 n-1 维数组的一维数组；

注意，无论数组的维数是多少，数组中的数据类型都必须一致

数组的顺序存储及（C语言）实现

数组作为一种线性存储结构，对存储的数据通常只做查找和修改操作，因此数组结构的实现使用的是顺序存储结构。

由于数组可以是多维的，而顺序存储结构是一维的，因此数组中数据的存储要制定一个先后次序。通常，数组中数据的存储有两种先后存储方式：

以列序为主（先列后行）：按照行号从小到大的顺序，依次存储每一列的元素
以行序为主（先行后序）：按照列号从小到大的顺序，依次存储每一行的元素。

多维数组查找指定元素

当需要在顺序存储的多维数组中查找某个指定元素时，需知道以下信息：

  • 多维数组的存储方式；
  • 多维数组在内存中存放的起始地址；
  • 该指定元素在原多维数组的坐标（比如说，二维数组中是通过行标和列标来表明数据元素的具体位置的）；
  • 数组中数组的具体类型，即数组中单个数据元素所占内存的大小，通常用字母 L 表示；

根据存储方式的不同，查找目标元素的方式也不同。如果二维数组采用以行序为主的方式，则在二维数组 anm 中查找 aij 存放位置的公式为：
LOC(i,j) = LOC(0,0) + (i*m + j) * L;

其中，LOC(i,j) 为 aij 在内存中的地址，LOC(0,0) 为二维数组在内存中存放的起始位置（也就是 a00 的位置），要注意起始位置不一定是a00，也可能是a11或者其他位置，下同。

而如果采用以列存储的方式，在 anm 中查找 aij 的方式为：
LOC(i,j) = LOC(0,0) + (i*n + j) * L;

以下给出了采用以行序为主的方式存储三维数组 a[3][4][2] 的 C 语言代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<stdarg.h>
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3
#define UNDERFLOW 4
typedef int Status; //Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; //Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8
typedef struct
{
    ElemType *base; //数组元素基址，由InitArray分配
    int dim; //数组维数
    int *bounds; //数组维界基址，由InitArray分配
    int *constants; // 数组映象函数常量基址，由InitArray分配
} Array;
Status InitArray(Array *A,int dim,...)
{
    //若维数dim和各维长度合法，则构造相应的数组A，并返回OK
    int elemtotal=1,i; // elemtotal是元素总值
    va_list ap;
    if(dim<1||dim>MAX_ARRAY_DIM)
        return ERROR;
    (*A).dim=dim;
    (*A).bounds=(int *)malloc(dim*sizeof(int));
    if(!(*A).bounds)
        exit(OVERFLOW);
    va_start(ap,dim);
    for(i=0; i<dim; ++i)
    {
        (*A).bounds[i]=va_arg(ap,int);
        if((*A).bounds[i]<0)
            return UNDERFLOW;
        elemtotal*=(*A).bounds[i];
    }
    va_end(ap);
    (*A).base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
    if(!(*A).base)
        exit(OVERFLOW);
    (*A).constants=(int *)malloc(dim*sizeof(int));
    if(!(*A).constants)
        exit(OVERFLOW);
    (*A).constants[dim-1]=1;
    for(i=dim-2; i>=0; --i)
        (*A).constants[i]=(*A).bounds[i+1]*(*A).constants[i+1];
    return OK;
}
Status DestroyArray(Array *A)
{
    //销毁数组A
    if((*A).base)
    {
        free((*A).base);
        (*A).base=NULL;
    }
    else
        return ERROR;
    if((*A).bounds)
    {
        free((*A).bounds);
        (*A).bounds=NULL;
    }
    else
        return ERROR;
    if((*A).constants)
    {
        free((*A).constants);
        (*A).constants=NULL;
    }
    else
        return ERROR;
    return OK;
}
Status Locate(Array A,va_list ap,int *off) // Value()、Assign()调用此函数 */
{
    //若ap指示的各下标值合法，则求出该元素在A中的相对地址off
    int i,ind;
    *off=0;
    for(i=0; i<A.dim; i++)
    {
        ind=va_arg(ap,int);
        if(ind<0||ind>=A.bounds[i])
            return OVERFLOW;
        *off+=A.constants[i]*ind;
    }
    return OK;
}
Status Value(ElemType *e,Array A,...) //在VC++中，...之前的形参不能是引用类型
{
    //依次为各维的下标值，若各下标合法，则e被赋值为A的相应的元素值
    va_list ap;
    Status result;
    int off;
    va_start(ap,A);
    if((result=Locate(A,ap,&off))==OVERFLOW) //调用Locate()
        return result;
    *e=*(A.base+off);
    return OK;
}
Status Assign(Array *A,ElemType e,...)
{
    //依次为各维的下标值，若各下标合法，则将e的值赋给A的指定的元素
    va_list ap;
    Status result;
    int off;
    va_start(ap,e);
    if((result=Locate(*A,ap,&off))==OVERFLOW) //调用Locate()
        return result;
    *((*A).base+off)=e;
    return OK;
}
int main()
{
    Array A;
    int i,j,k,*p,dim=3,bound1=3,bound2=4,bound3=2; //a[3][4][2]数组
    ElemType e,*p1;
    InitArray(&A,dim,bound1,bound2,bound3); //构造3＊4＊2的3维数组A
    p=A.bounds;
    printf("A.bounds=");
    for(i=0; i<dim; i++) //顺序输出A.bounds
        printf("%d ",*(p+i));
    p=A.constants;
    printf("\nA.constants=");
    for(i=0; i<dim; i++) //顺序输出A.constants
        printf("%d ",*(p+i));
    printf("\n%d页%d行%d列矩阵元素如下:\n",bound1,bound2,bound3);
    for(i=0; i<bound1; i++)
    {
        for(j=0; j<bound2; j++)
        {
            for(k=0; k<bound3; k++)
            {
                Assign(&A,i*100+j*10+k,i,j,k); // 将i*100+j*10+k赋值给A[i][j][k]
                Value(&e,A,i,j,k); //将A[i][j][k]的值赋给e
                printf("A[%d][%d][%d]=%2d ",i,j,k,e); //输出A[i][j][k]
            }
            printf("\n");
        }
        printf("\n");
    }
    p1=A.base;
    printf("A.base=\n");
    for(i=0; i<bound1*bound2*bound3; i++) //顺序输出A.base
    {
        printf("%4d",*(p1+i));
        if(i%(bound2*bound3)==bound2*bound3-1)
            printf("\n");
    }
    DestroyArray(&A);
    return 0;
}

运行结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
A.bounds=3 4 2
A.constants=8 2 1
3页4行2列矩阵元素如下:
A[0][0][0]= 0 A[0][0][1]= 1
A[0][1][0]=10 A[0][1][1]=11
A[0][2][0]=20 A[0][2][1]=21
A[0][3][0]=30 A[0][3][1]=31

A[1][0][0]=100 A[1][0][1]=101
A[1][1][0]=110 A[1][1][1]=111
A[1][2][0]=120 A[1][2][1]=121
A[1][3][0]=130 A[1][3][1]=131

A[2][0][0]=200 A[2][0][1]=201
A[2][1][0]=210 A[2][1][1]=211
A[2][2][0]=220 A[2][2][1]=221
A[2][3][0]=230 A[2][3][1]=231

A.base=
   0   1  10  11  20  21  30  31
100 101 110 111 120 121 130 131
200 201 210 211 220 221 230 231

矩阵（稀疏矩阵）压缩存储

数据结构中，提供针对某些特殊矩阵的压缩存储结构。

这里所说的特殊矩阵，主要分为以下两类：
含有大量相同数据元素的矩阵，比如对称矩阵；
含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

对称矩阵

数据元素沿主对角线对应相等，这类矩阵称为对称矩阵。

矩阵中有两条对角线，其中左上角到右下角的对角线称为主对角线，另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

结合数据结构压缩存储的思想，我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。

对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。

注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。

上（下）三角矩阵

主对角线下的数据元素全部相同的矩阵为上三角矩阵，主对角线上元素全部相同的矩阵为下三角矩阵。

对于这类特殊的矩阵，压缩存储的方式是：上（下）三角矩阵采用对称矩阵的方式存储上（下）三角的数据（元素 0 不用存储）。上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

稀疏矩阵

如果矩阵中分布有大量的元素 0，即非 0 元素非常少，这类矩阵称为稀疏矩阵。

压缩存储稀疏矩阵的方法是：只存储矩阵中的非 0 元素，与前面的存储方法不同，稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。

例如，存储图 5 中的稀疏矩阵，需存储以下信息：
(1,1,1)：数据元素为 1，在矩阵中的位置为 (1,1)；
(3,3,1)：数据元素为 3，在矩阵中的位置为 (3,1)；
(5,2,3)：数据元素为 5，在矩阵中的位置为 (2,3)；
除此之外，还要存储矩阵的行数 3 和列数 3；

由此，可以成功存储一个稀疏矩阵。

矩阵压缩存储的 3 种方式

对于以上 3 种特殊的矩阵，对阵矩阵和上下三角矩阵的实现方法是相同的，且实现过程比较容易，仅需套用上面给出的公式即可。

稀疏矩阵的压缩存储，数据结构提供有 3 种具体实现方式：
三元组顺序表；
行逻辑链接的顺序表；
十字链表；

三元组顺序表，稀疏矩阵的三元组表示及实现

三元组是由 3 部分数据组成的集合，组中数据分别表示（行标，列标，元素值）。

三元组需要用结构体实现，如下所示：

1
2
3
4
5
//三元组结构体
typedef struct {
    int i,j;//行标i，列标j
    int data;//元素值
}triple;

由于稀疏矩阵中非 0 元素有多个，因此需要建立 triple 数组存储各个元素的三元组。除此之外，考虑到还要存储矩阵的总行数和总列数，因此可以采用以下结构表示整个稀疏矩阵：

1
2
3
4
5
6
#define number 20
//矩阵的结构表示
typedef struct {
    triple data[number];//存储该矩阵中所有非0元素的三元组
    int n,m,num;//n和m分别记录矩阵的行数和列数，num记录矩阵中所有的非0元素的个数
}TSMatrix;

可以看到，TSMatrix 是一个结构体，其包含一个三元组数组，以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。

使用TSMatrix存储下列稀疏矩阵：
1 0 0
0 0 5
3 0 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#define number 3
typedef struct {
    int i,j;
    int data;
}triple;
typedef struct {
    triple data[number];
    int n,m,num;
}TSMatrix;
//输出存储的稀疏矩阵
void display(TSMatrix M);
int main() {
    TSMatrix M;
    M.m=3;
    M.n=3;
    M.num=3;
    M.data[0].i=1;
    M.data[0].j=1;
    M.data[0].data=1;
    M.data[1].i=2;
    M.data[1].j=3;
    M.data[1].data=5;
    M.data[2].i=3;
    M.data[2].j=1;
    M.data[2].data=3;
    display(M);
    return 0;
}
void display(TSMatrix M){
    for(int i=1;i<=M.n;i++){
        for(int j=1;j<=M.m;j++){
            int value =0;
            for(int k=0;k<M.num;k++){
                if(i == M.data[k].i && j == M.data[k].j){
                    printf("%d ",M.data[k].data);
                    value =1;
                    break;
                }
            }
            if(value == 0)
                printf("0 ");
        }
        printf("\n");
    }
}

行逻辑链接的顺序表

行逻辑链接的顺序表和三元组顺序表的实现过程类似，它们存储矩阵的过程完全相同，都是将矩阵中非 0 元素的三元组（行标、列标和元素值）存储在一维数组中。他们的区别在于行逻辑链接的顺序表存储矩阵时比三元组顺序表多使用了一个数组，专门记录矩阵中每行第一个非 0 元素在一维数组中的位置，它仅比三元组顺序表多使用了一个 rpos 数组，从而提高了提取数据时遍历数组的效率。

存储下列稀疏矩阵：
0 3 0 5
0 0 1 0
2 0 0 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#define MAXSIZE 12500
#define MAXRC 100
#define ElemType int
typedef struct
{
    int i,j;//行，列
    ElemType e;//元素值
}Triple;
typedef struct
{
    Triple  data[MAXSIZE+1];
    int rpos[MAXRC+1];//每行第一个非零元素在data数组中的位置
    int mu,nu,tu;//行数，列数，元素个数
}RLSMatrix;
//矩阵的输出函数
void display(RLSMatrix M){
    for(int i=1;i<=M.mu;i++){
        for(int j=1;j<=M.nu;j++){
            int value=0;
            if(i+1 <=M.mu){
                for(int k=M.rpos[i];k<M.rpos[i+1];k++){
                    if(i == M.data[k].i && j == M.data[k].j){
                        printf("%d ",M.data[k].e);
                        value=1;
                        break;
                    }
                }
                if(value==0){
                        printf("0 ");
                    }
            }else{
                for(int k=M.rpos[i];k<=M.tu;k++){
                    if(i == M.data[k].i && j == M.data[k].j){
                        printf("%d ",M.data[k].e);
                        value=1;
                        break;
                    }
                }
                if(value==0){
                    printf("0 ");
                }
            }
        }
        printf("\n");
    }
}
int main(int argc, char* argv[])
{
    RLSMatrix M;
    M.tu = 4;
    M.mu = 3;
    M.nu = 4;
    M.rpos[1] = 1;
    M.rpos[2] = 3;
    M.rpos[3] = 4;
    M.data[1].e = 3;
    M.data[1].i = 1;
    M.data[1].j = 2;
    M.data[2].e = 5;
    M.data[2].i = 1;
    M.data[2].j = 4;
    M.data[3].e = 1;
    M.data[3].i = 2;
    M.data[3].j = 3;
    M.data[4].e = 2;
    M.data[4].i = 3;
    M.data[4].j = 1;
    //输出矩阵
    display(M);
    return 0;
}

十字链表法

该存储方式采用的是 “链表+数组” 结构，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。

链表中节点的 C 语言代码表示应为：

1
2
3
4
5
typedef struct OLNode{
    int i,j;//元素的行标和列标
    int data;//元素的值
    struct OLNode * right,*down;//两个指针域
}OLNode;

同时，表示十字链表结构的 C 语言代码应为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<stdio.h>
#include<stdlib.h>
typedef struct OLNode
{
    int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据
    struct OLNode *right, *down; //指针域 右指针 下指针
}OLNode, *OLink;
typedef struct
{
    OLink *rhead, *chead; //行和列链表头指针
    int mu, nu, tu;  //矩阵的行数,列数和非零元的个数
}CrossList;
CrossList CreateMatrix_OL(CrossList M);
void display(CrossList M);
int main()
{
    CrossList M;
    M.rhead = NULL;
    M.chead = NULL;
    M = CreateMatrix_OL(M);
    printf("输出矩阵M:\n");
    display(M);
    return 0;
}
CrossList CreateMatrix_OL(CrossList M)
{
    int m, n, t;
    int i, j, e;
    OLNode *p, *q;
    printf("输入矩阵的行数、列数和非0元素个数：");
    scanf("%d%d%d", &m, &n, &t);
    M.mu = m;
    M.nu = n;
    M.tu = t;
    if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))
    {
        printf("初始化矩阵失败");
        exit(0);
    }
    for (i = 1; i <= m; i++)
    {
        M.rhead[i] = NULL;
    }
    for (j = 1; j <= n; j++)
    {
        M.chead[j] = NULL;
    }
    for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {
        if (!(p = (OLNode*)malloc(sizeof(OLNode))))
        {
            printf("初始化三元组失败");
            exit(0);
        }
        p->i = i;
        p->j = j;
        p->e = e;
        //链接到行的指定位置
        if (NULL == M.rhead[i] || M.rhead[i]->j > j)
        {
            p->right = M.rhead[i];
            M.rhead[i] = p;
        }
        else
        {
            for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);
            p->right = q->right;
            q->right = p;
        }
        //链接到列的指定位置
        if (NULL == M.chead[j] || M.chead[j]->i > i)
        {
            p->down = M.chead[j];
            M.chead[j] = p;
        }
        else
        {
            for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
    return M;
}
void display(CrossList M) {
    for (int i = 1; i <= M.nu; i++)
    {
        if (NULL != M.chead[i])
        {
            OLink p = M.chead[i];
            while (NULL != p)
            {
                printf("%d\t%d\t%d\n", p->i, p->j, p->e);
                p = p->down;
            }
        }
    }
}

运行结果：

1
2
3
4
5
6
7
8
9
输入矩阵的行数、列数和非0元素个数：3 3 3
2 2 3
2 3 4
3 2 5
0 0 0
输出矩阵M:
2       2       3
3       2       5
2       3       4

矩阵（稀疏矩阵）的转置算法

矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中。

矩阵转置的实现过程需完成以下 3 步：

将矩阵的行数和列数互换；
将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
以 j 列为序，重新排列三元组表中存储各三元组的先后顺序；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#define number 10
typedef struct {
    int i,j;
    int data;
}triple;
typedef struct {
    triple data[number];
    int n,m,num;
}TSMatrix;
TSMatrix transposeMatrix(TSMatrix M,TSMatrix T){
    T.m=M.n;
    T.n=M.m;
    T.num=M.num;
    if (T.num) {
        int q=0;
        for (int col=1;col<=M.m; col++) {
            for (int p=0; p<M.num; p++) {
                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].data=M.data[p].data;
                    q++;
                }
            }
        }
    }
    return T;
}
int main() {
    TSMatrix M;
    M.m=2;
    M.n=3;
    M.num=4;
    M.data[0].i=1;
    M.data[0].j=2;
    M.data[0].data=1;
    M.data[1].i=2;
    M.data[1].j=2;
    M.data[1].data=3;
    M.data[2].i=3;
    M.data[2].j=1;
    M.data[2].data=6;
    M.data[3].i=3;
    M.data[3].j=2;
    M.data[3].data=5;
    TSMatrix T;
    T=transposeMatrix(M, T);
    for (int i=0; i<T.num; i++) {
        printf("(%d,%d,%d)\n",T.data[i].i,T.data[i].j,T.data[i].data);
    }
    return 0;
}

程序运行结果为：

1
2
3
4
(1,3,6)
(2,1,1)
(2,2,3)
(2,3,5)

由于此算法中嵌套使用了两个 for 循环，时间复杂度为 O(n2)。

广义表

广义表，又称列表，也是一种线性存储结构。

同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表，记作：
LS = (a1,a2,…,an)

其中，LS 代表广义表的名称，an 表示广义表存储的数据。广义表中每个 ai 既可以代表单个元素，也可以代表另一个广义表。

原子和子表

通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。

例如创建一个广义表LS = {1,{1,2,3}}，我们可以这样解释此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。

以下是广义表存储数据的一些常用形式：

A = ()：A 表示一个广义表，只不过表是空的。
B = (e)：广义表 B 中只有一个原子 e。
C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

注意，A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。

广义表的表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为”表头”，剩下的数据构成的新广义表为”表尾”。
强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

例如在广义表中LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。 再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用{} 表示。 ### 广义表的存储结构（两种方式） 由于广义表中可同时存储原子和子表两种形式的数据，因此链表节点的结构也有两种，如图 1 所示： 广义表节点的两种类型 图 1 广义表节点的两种类型 如图 1 所示，表示原子的节点由两部分构成，分别是 tag 标记位和原子的值，表示子表的节点由三部分构成，分别是 tag 标记位、hp 指针和 tp 指针。 tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1。子表节点中的 hp 指针用于连接本子表中存储的原子或子表，tp 指针用于连接广义表中下一个原子或子表。 因此，广义表中两种节点的 C 语言表示代码为： 

1
2
3
4
5
6
7
8
9
typedef struct GLNode{
    int tag;//标志域
    union{
        char atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;
        }ptr;//子表结点的指针域，hp指向表头；tp指向表尾
    };
}*Glist;
这里用到了 union 共用体，因为同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。 例如，广义表 {a,{b,c,d}} 是由一个原子 a 和子表 {b,c,d} 构成，而子表 {b,c,d} 又是由原子 b、c 和 d 构成，用链表存储该广义表如图 2 所示：

广义表 {a,{b,c,d}} 的结构示意图
图 2 广义表 {a,{b,c,d}} 的结构示意图

图 2 可以看到，存储原子 a、b、c、d 时都是用子表包裹着表示的，因为原子 a 和子表 {b,c,d} 在广义表中同属一级，而原子 b、c、d 也同属一级。

图 2 中链表存储的广义表用 C 语言代码表示为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Glist creatGlist(Glist C){
    //广义表C
    C=(Glist)malloc(sizeof(Glist));
    C->tag=1;
    //表头原子‘a’
    C->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.hp->tag=0;
    C->ptr.hp->atom='a';
    //表尾子表（b,c,d）,是一个整体
    C->ptr.tp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.tp=NULL;
    //开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）
    C->ptr.tp->ptr.hp->tag=1;
    C->ptr.tp->ptr.hp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.hp->atom='b';
    C->ptr.tp->ptr.hp->ptr.tp=(Glist)malloc(sizeof(Glist));
    //存放子表(c,d)，表头为c，表尾为d
    C->ptr.tp->ptr.hp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom='c';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp=(Glist)malloc(sizeof(Glist));
    //存放表尾d
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom='d';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp=NULL;
    return C;
}

另一种广义表存储结构

如果你觉得图 2 这种存储广义表的方式不合理，可以使用另一套表示广义表中原子和子表结构的节点，如图 3 所示：

广义表的另一套节点结构
图 3 广义表的另一套节点结构

如图 3 所示，表示原子的节点构成由 tag 标记位、原子值和 tp 指针构成，表示子表的节点还是由 tag 标记位、hp 指针和 tp 指针构成。

图 3 的节点结构用 C 语言代码表示为：

1
2
3
4
5
6
7
8
typedef struct GLNode{
    int tag;//标志域
    union{
        int atom;//原子结点的值域
        struct GLNode *hp;//子表结点的指针域，hp指向表头
    };
    struct GLNode * tp;//这里的tp相当于链表的next指针，用于指向下一个数据元素
}*Glist;

采用图 3 中的节点结构存储广义表 {a,{b,c,d}} 的示意图如图 4 所示：

图 4 存储广义表对应的 C 语言代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Glist creatGlist(Glist C){
    C=(Glist)malloc(sizeof(Glist));
    C->tag=1;
    C->hp=(Glist)malloc(sizeof(Glist));
    C->tp=NULL;
    //表头原子a
    C->hp->tag=0;
    C->atom='a';
    C->hp->tp=(Glist)malloc(sizeof(Glist));
    C->hp->tp->tag=1;
    C->hp->tp->hp=(Glist)malloc(sizeof(Glist));
    C->hp->tp->tp=NULL;
    //原子b
    C->hp->tp->hp->tag=0;
    C->hp->tp->hp->atom='b';
    C->hp->tp->hp->tp=(Glist)malloc(sizeof(Glist));
    //原子c
    C->hp->tp->hp->tp->tag=0;
    C->hp->tp->hp->tp->atom='c';
    C->hp->tp->hp->tp->tp=(Glist)malloc(sizeof(Glist));
    //原子d
    C->hp->tp->hp->tp->tp->tag=0;
    C->hp->tp->hp->tp->tp->atom='d';
    C->hp->tp->hp->tp->tp->tp=NULL;
    return C;
}

广义表的复制

对于任意一个非空广义表来说，都是由两部分组成：表头和表尾。反之，只要确定的一个广义表的表头和表尾，那么这个广义表就可以唯一确定下来。

复制一个广义表，也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表，依旧复制其表头和表尾。

所以，复制广义表的过程，其实就是不断的递归，复制广义表中表头和表尾的过程。

递归的出口有两个：

如果当前遍历的数据元素为空表，则直接返回空表。
如果当前遍历的数据元素为该表的一个原子，那么直接复制，返回即可。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
typedef struct GLNode{
    int tag;//标志域
    union{
        char atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;
        }ptr;//子表结点的指针域，hp指向表头；tp指向表尾
    };
}*Glist,GNode;
Glist creatGlist(Glist C){
    //广义表C
    C=(Glist)malloc(sizeof(GNode));
    C->tag=1;
    //表头原子‘a’
    C->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.hp->tag=0;
    C->ptr.hp->atom='a';
    //表尾子表（b,c,d）,是一个整体
    C->ptr.tp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.tp=NULL;
    //开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）
    C->ptr.tp->ptr.hp->tag=1;
    C->ptr.tp->ptr.hp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.hp->atom='b';
    C->ptr.tp->ptr.hp->ptr.tp=(Glist)malloc(sizeof(GNode));
    //存放子表(c,d)，表头为c，表尾为d
    C->ptr.tp->ptr.hp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom='c';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp=(Glist)malloc(sizeof(GNode));
    //存放表尾d
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(GNode));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom='d';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp=NULL;
    return C;
}
void copyGlist(Glist C, Glist *T){
    //如果C为空表，那么复制表直接为空表 
    if (!C) {
        *T=NULL;
    }
    else{
        *T=(Glist)malloc(sizeof(GNode));//C不是空表，给T申请内存空间
        //申请失败，程序停止
        if (!*T) {
            exit(0);
        }
        (*T)->tag=C->tag;//复制表C的tag值
        //判断当前表元素是否为原子，如果是，直接复制
        if (C->tag==0) {
            (*T)->atom=C->atom;
        }else{//运行到这，说明复制的是子表
            copyGlist(C->ptr.hp, &((*T)->ptr.hp));//复制表头
            copyGlist(C->ptr.tp, &((*T)->ptr.tp));//复制表尾
        }
    }
}
int main(int argc, const char * argv[]) {
    Glist C=NULL;
    C=creatGlist(C);
    Glist T=NULL;
    copyGlist(C,&T);
    printf("%c",T->ptr.hp->atom);
    return 0;
}

运行结果：a

总结

在实现复制广义表的过程中，实现函数为：

void copyGlist(Glist C, Glist *T);

其中，Glist *T，等同于: struct GLNode* *T，此为二级指针，不是一级指针。在主函数中，调用此函数时，传入的是指针 T 的地址，而不是 T 。

这里使用的是地址传递，而不是值传递。如果在这里使用值传递，会导致广义表 T 丢失结点，复制失败。

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！