CosmosNing的个人博客

探索·好奇

0%

数据结构复习笔记4-数组和广义表

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 13 分钟
整理一下数组和广义表的知识

5．数组和广义表

数组的顺序存储表示

  • 存储
1
2
3
4
5
6
7
8
9
10
11
12
// 数组的顺序存储表示

#include<stdarg.h>      // 标准头文件，提供宏 va_start、va_arg、va_end
                        // 用于存储变长参数表
#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为 8

typedef struct{
    ElemType *base;     // 数组元素基址，由 InitArray 分配
    int      dim;       // 数组维数
    int      *bounds;   // 数组维界地址，由 InitArray 分配
    int      *constants;// 数组映像函数常量基址，由 InitArray 分配
}Array;
  • 操作
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
// 构造数组
// 若维数 dim 和各维长度合法，则构造相应的数组 A，并返回 OK

Status InitArray(Array &A, int dim, ...)
{
    if(dim < 1 || dim > MAX_ARRAY_DIM)
        return ERROR;
    
    A.dim = dim;
    A.bounds = (int *)malloc(dim * sizeof(int));
    
    if(! A.bounds)
        exit(OVERFLOW);
    
    // 若各维度长度合法，则存入 A.bounds,并求出 A 的元素总数 elemtotal
    elemtotal = 1;
    va_start(ap, dim);  // ap 为 va_list类型，是存放变长参数表信息的数组
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 数组销毁
// 销毁数组 A

Status DestroyArray(Array &A)
{
    if(! A.base)	return ERROR;
    free(A.base);	A.base = NULL;
    
    if(! A.bounds)	return ERROR;
    free(A.bounds);	A.bounds = NULL;
    
    if(! A.constants)	return ERROR;
    free(A.constants);	A.constants = NULL;
    
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 定位元素的相对地址
// 若 ap 指示的各下标合法，则求出该元素在 A 中的相对地址 off

Status Locate(Array A, va_list ap, int &off)
{
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 取给定下标元素的值
// A 是 n 维数组，e 为元素变量，随后是 n 个下标值
// 若各下标不越界，则 e 赋值为所指定 A 的元素值，并返回 OK

Status Value(Array A, ElemType &e, ...)
{
    va_start(ap, e);
    
    if((result = Locate(A, ap, off)) <= 0)	return result; // 失败
    
    e = *(A.base + off);
    
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 给指定下标的元素赋值
// A 是 n 维数组，e 为元素变量，随后是 n 个下标值
// 若各下标不越界，则将 e 赋给所指定 A 的元素值，并返回 OK

Status Assign(Array & A, Elemtype e, ...)
{
    va_start(ap, e);
    
    if((result = Locate(A, ap, off)) <= 0)	return result;
    
    *(A.base + off) = e;
    
    return OK;
}

矩阵的压缩存储：特殊矩阵、稀疏矩阵

特殊矩阵

（以下推导请见王道 3.4.3 节）

注意下标（以下推导基于矩阵元素 a 从 (1, 1) 开始，但存储从 0 号开始）（题目会以此设置陷阱）

对称矩阵

  • 存储结构：一维数组 sa[n*(n+1)/2]，（行序为主序，仅仅存储下三角）

  • 存储下标 k 与矩阵逻辑位置 (i, j) 的关系 \[ k = \left \{ \begin{aligned} & \frac{i(i-1)}{2}+j-1, &i \ge j\\ & \frac{j(j-1)}{2}+i-1, &i < j \\ \end{aligned} \right. \]

下三角矩阵

  • 存储结构：一维数组 sa[n*(n+1)/2 + 1]，（行序为主序，存储下三角及上三角的常量【存储在数组最后一个位置】）

  • 存储下标 k 与矩阵逻辑位置 (i, j) 的关系

\[ k = \left \{ \begin{aligned} & \frac{i(i-1)}{2}+j-1, &i \ge j &(存储下三角和主对角线)\\ & \frac{n(n+1)}{2}, &i < j &(存储常量的位置)\\ \end{aligned} \right. \]

上三角矩阵

  • 存储结构：一维数组 sa[n*(n+1)/2 + 1]，（行序为主序，存储上三角及下三角的常量【存储在数组最后一个位置】）

  • 存储下标 k 与矩阵逻辑位置 (i, j) 的关系

\[ k = \left \{ \begin{aligned} & \frac{(i-1)(2n-i+2)}{2}+j-i, &i \le j &(存储上三角和主对角线)\\ & \frac{n(n+1)}{2}, &i > j &(存储常量的位置)\\ \end{aligned} \right. \]

三对角矩阵

  • 描述：所有非 0 元素都集中在以主对角线为中心的 3 条对角线区域，其余元素为 0

  • 存储结构：一维数组 sa[3n-2]，（按行优先，依次存入一维数组中）

  • 存储下标 k 与矩阵逻辑位置 (i, j) 的关系

\[ k = 2i + j -3 \]

\[ \begin{align} & i = \lfloor(k+1)/3+1\rfloor \\ & j = k-2i+3 \end{align} \]

稀疏矩阵

三元组顺序表

  • 存储
1
2
3
4
5
6
7
8
9
10
11
12
13
// 稀疏矩阵的三元组顺序表存储表示

#define MAXSIZE 12500                // 非零元个数的最大值

typedef struct{
    int i, j;                        // 非零元的行下标和列下标
    ElemType e;
}Triple;

typedef struct{
    Triple data[MAXSIZE + 1];        // 非零元三元组表，data[0]未用
    int mu, nu, tu;                  // 矩阵的行数、列数、非零元个数
}TSMatrix;
  • 操作
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
// 算法 5.1
// 矩阵的转置
// 采用三元组表存储表示，求稀疏矩阵 M 的转置矩阵
// 时间复杂度 O(nu·tu)，适用于【tu 远小于 mu × nu】的情况

Status TransposeSMatrix(TSMatrix M, TSMatrix &T)
{
    T.mu = M.mu; T.nu = M.nu; T.tu = M.tu;
    
    if(T.tu)
    {
        q = 1;
        
        for(col = 1; col < M.nu; col++)
            for(p = 1; p < M.tu; 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].e = M.data[p].e;
                    ++q;
                }
    }
    
    return OK;
}
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
// 算法 5.2
// 更快的转置算法

Status FastTransposeMatrix(TSMatrix M, TSMatrix &T)
{
    T.mu = M.mu; T.nu = M.nu; T.tu = M.tu;
    
    if(T.tu)
    {
        for(col = 1; col <= M.nu; ++col)	num[col] = 1;
        for(t = 1; t <= M.tu; ++t)	++num[M.data[t].j];
        
        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++)
        {
            col = M.data[p].j;	q = cpot[col];
            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;
}

行逻辑连接顺序表

  • 存储
1
2
3
4
5
6
7
// 行逻辑连接顺序表

typedef struct{
    Triple data[MAXSIZE + 1];
    int rpos[MAXRC + 1];
    int mu, nu, tu;
}RLSMatrix;
  • 操作
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
// 算法 5.3
// 矩阵乘法

Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{
    int arow,brow,p,q,ccol,ctemp[MAXRC+1];
    if(M.nu!=N.mu) /* 矩阵M的列数应和矩阵N的行数相等 */
        return ERROR;
    (*Q).mu=M.mu; /* Q初始化 */
    (*Q).nu=N.nu;
    (*Q).tu=0;
    M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */
    N.rpos[N.mu+1]=N.tu+1;
    if(M.tu*N.tu!=0) /* M和N都是非零矩阵 */
    {
        for(arow=1;arow<=M.mu;++arow)
        { /* 从M的第一行开始，到最后一行，arow是M的当前行 */
            for(ccol=1;ccol<=(*Q).nu;++ccol)
                ctemp[ccol]=0; /* Q的当前行的各列元素累加器清零 */
            (*Q).rpos[arow]=(*Q).tu+1; /* Q当前行的第1个元素位于上1行最后1个元素之后 */
            for(p=M.rpos[arow];p<M.rpos[arow+1];++p)
            { /* 对M当前行中每一个非零元 */
                brow=M.data[p].j; /* 找到对应元在N中的行号(M当前元的列号) */
                for(q=N.rpos[brow];q<N.rpos[brow+1];++q)
                {
                    ccol=N.data[q].j; /* 乘积元素在Q中列号 */
                    ctemp[ccol]+=M.data[p].e*N.data[q].e;
                }
            } /* 求得Q中第arow行的非零元 */
            for(ccol=1;ccol<=(*Q).nu;++ccol) /* 压缩存储该行非零元 */
                if(ctemp[ccol])
                {
                    if(++(*Q).tu>MAXSIZE)
                        return ERROR;
                    (*Q).data[(*Q).tu].i=arow;
                    (*Q).data[(*Q).tu].j=ccol;
                    (*Q).data[(*Q).tu].e=ctemp[ccol];
                }
        }
    }
    return OK;
}

十字链表存储

  • 存储
1
2
3
4
5
6
7
8
9
10
11
// 稀疏矩阵的十字链表存储表示
typedef struct OLNode{
    int i,j; /* 该非零元的行和列下标 */
    ElemType e; /* 非零元素值 */
    struct OLNode *right,*down; /* 该非零元所在行表和列表的后继链域 */
}OLNode,*OLink;

typedef struct{
    OLink *rhead,*chead; /* 行和列链表头指针向量基址,由CreatSMatrix_OL()分配 */
    int mu,nu,tu; /* 稀疏矩阵的行数、列数和非零元个数 */
}CrossList;
  • 操作
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
// 算法 5.4
// 创建稀疏矩阵，十字链表存储表示

Status CreateSMatrix(CrossList *M)
{ /* 创建稀疏矩阵M,采用十字链表存储表示。算法5.4 */
    int i,j,k,m,n,t;
    ElemType e;
    OLNode *p,*q;
    if((*M).rhead)
        DestroySMatrix(M);
    printf("请输入稀疏矩阵的行数 列数 非零元个数: ");
    scanf("%d%d%d",&m,&n,&t);
    (*M).mu=m;
    (*M).nu=n;
    (*M).tu=t;
    (*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));
    if(!(*M).rhead)
        exit(OVERFLOW);
    (*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));
    if(!(*M).chead)
        exit(OVERFLOW);
    for(k=1;k<=m;k++) /* 初始化行头指针向量;各行链表为空链表 */
        (*M).rhead[k]=NULL;
    for(k=1;k<=n;k++) /* 初始化列头指针向量;各列链表为空链表 */
        (*M).chead[k]=NULL;
    printf("请按任意次序输入%d个非零元的行 列 元素值:\n",(*M).tu);
    for(k=0;k<t;k++)
    {
        scanf("%d%d%d",&i,&j,&e);
        p=(OLNode*)malloc(sizeof(OLNode));
        if(!p)
            exit(OVERFLOW);
        p->i=i; /* 生成结点 */
        p->j=j;
        p->e=e;
        if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j) /* p插在该行的第一个结点处 */
        {
            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((*M).chead[j]==NULL||(*M).chead[j]->i>i) /* p插在该列的第一个结点处 */
        {
            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 OK;
}
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
// 矩阵加法

Status AddSMatrix(CrossList M,CrossList N,CrossList *Q)
{ /* 初始条件: 稀疏矩阵M与N的行数和列数对应相等。 */
    /* 操作结果: 求稀疏矩阵的和Q=M+N */
    int i,k;
    OLink p,pq,pm,pn;
    OLink *col;
    if(M.mu!=N.mu||M.nu!=N.nu)
    {
        printf("两个矩阵不是同类型的,不能相加\n");
        exit(OVERFLOW);
    }
    (*Q).mu=M.mu; /* 初始化Q矩阵 */
    (*Q).nu=M.nu;
    (*Q).tu=0; /* 元素个数的初值 */
    (*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));
    if(!(*Q).rhead)
        exit(OVERFLOW);
    (*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));
    if(!(*Q).chead)
        exit(OVERFLOW);
    for(k=1;k<=(*Q).mu;k++) /* 初始化Q的行头指针向量;各行链表为空链表 */
        (*Q).rhead[k]=NULL;
    for(k=1;k<=(*Q).nu;k++) /* 初始化Q的列头指针向量;各列链表为空链表 */
        (*Q).chead[k]=NULL;
    col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink)); /* 生成指向列的最后结点的数组 */
    if(!col)
        exit(OVERFLOW);
    for(k=1;k<=(*Q).nu;k++) /* 赋初值 */
        col[k]=NULL;
    for(i=1;i<=M.mu;i++) /* 按行的顺序相加 */
    {
        pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */
        pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */
        while(pm&&pn) /* pm和pn均不空 */
        {
            if(pm->j<pn->j) /* 矩阵M当前结点的列小于矩阵N当前结点的列 */
            {
                p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
                if(!p)
                    exit(OVERFLOW);
                (*Q).tu++; /* 非零元素数加1 */
                p->i=i; /* 给结点赋值 */
                p->j=pm->j;
                p->e=pm->e;
                p->right=NULL;
                pm=pm->right; /* pm指针向右移 */
            }
            else if(pm->j>pn->j) /* 矩阵M当前结点的列大于矩阵N当前结点的列 */
            {
                p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
                if(!p)
                    exit(OVERFLOW);
                (*Q).tu++; /* 非零元素数加1 */
                p->i=i; /* 给结点赋值 */
                p->j=pn->j;
                p->e=pn->e;
                p->right=NULL;
                pn=pn->right; /* pn指针向右移 */
            }
            else if(pm->e+pn->e) /* 矩阵M、N当前结点的列相等且两元素之和不为0 */
            {
                p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
                if(!p)
                    exit(OVERFLOW);
                (*Q).tu++; /* 非零元素数加1 */
                p->i=i; /* 给结点赋值 */
                p->j=pn->j;
                p->e=pm->e+pn->e;
                p->right=NULL;
                pm=pm->right; /* pm指针向右移 */
                pn=pn->right; /* pn指针向右移 */
            }
            else /* 矩阵M、N当前结点的列相等且两元素之和为0 */
            {
                pm=pm->right; /* pm指针向右移 */
                pn=pn->right; /* pn指针向右移 */
                continue;
            }
            if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
                (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
            else /* 插在pq所指结点之后 */
            {
                pq->right=p; /* 完成行插入 */
                pq=pq->right; /* pq指向该行的最后一个结点 */
            }
            if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
                (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
            else /* 插在col[p->]所指结点之后 */
            {
                col[p->j]->down=p; /* 完成列插入 */
                col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
            }
        }
        while(pm) /* 将矩阵M该行的剩余元素插入矩阵Q */
        {
            p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
            if(!p)
                exit(OVERFLOW);
            (*Q).tu++; /* 非零元素数加1 */
            p->i=i; /* 给结点赋值 */
            p->j=pm->j;
            p->e=pm->e;
            p->right=NULL;
            pm=pm->right; /* pm指针向右移 */
            if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
                (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
            else /* 插在pq所指结点之后 */
            {
                pq->right=p; /* 完成行插入 */
                pq=pq->right; /* pq指向该行的最后一个结点 */
            }
            if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
                (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
            else /* 插在col[p->j]所指结点之后 */
            {
                col[p->j]->down=p; /* 完成列插入 */
                col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
            }
        }
        while(pn) /* 将矩阵N该行的剩余元素插入矩阵Q */
        {
            p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
            if(!p)
                exit(OVERFLOW);
            (*Q).tu++; /* 非零元素数加1 */
            p->i=i; /* 给结点赋值 */
            p->j=pn->j;
            p->e=pn->e;
            p->right=NULL;
            pn=pn->right; /* pm指针向右移 */
            if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
                (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
            else /* 插在pq所指结点之后 */
            {
                pq->right=p; /* 完成行插入 */
                pq=pq->right; /* pq指向该行的最后一个结点 */
            }
            if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
                (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
            else /* 插在col[p->j]所指结点之后 */
            {
                col[p->j]->down=p; /* 完成列插入 */
                col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
            }
        }
    }
    for(k=1;k<=(*Q).nu;k++)
        if(col[k]) /* k列有结点 */
            col[k]->down=NULL; /*  令该列最后一个结点的down指针为空 */
    free(col);
    return OK;
}

广义表的定义和存储结构

  • 存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 /* 广义表的头尾链表存储表示 */
typedef enum{ATOM,LIST}ElemTag; /* ATOM==0:原子,LIST==1:子表 */
typedef struct GLNode
{
    ElemTag tag; /* 公共部分,用于区分原子结点和表结点 */
    union /* 原子结点和表结点的联合部分 */
    {
        AtomType atom; /* atom是原子结点的值域,AtomType由用户定义 */
        struct
        {
            struct GLNode *hp,*tp;
        }ptr; /* ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 */
    }a;
}*GList,GLNode; /* 广义表类型 */
1
2
3
4
5
6
7
8
9
10
11
12
/* 广义表的扩展线性链表存储表示 */
typedef enum{ATOM,LIST}ElemTag; /* ATOM==0:原子,LIST==1:子表 */
typedef struct GLNode
{
    ElemTag tag; /* 公共部分,用于区分原子结点和表结点 */
    union /* 原子结点和表结点的联合部分 */
    {
        AtomType atom; /* 原子结点的值域 */
        struct GLNode *hp; /* 表结点的表头指针 */
    }a;
    struct GLNode *tp; /* 相当于线性链表的next,指向下一个元素结点 */
}*GList,GLNode; /* 广义表类型GList是一种扩展的线性链表 */
  • 操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 算法 5.5

int GListDepth(GList L)
{ /* 采用头尾链表存储结构,求广义表L的深度。算法5.5 */
    int max,dep;
    GList pp;
    if(!L)
        return 1; /* 空表深度为1 */
    if(L->tag==ATOM)
        return 0; /* 原子深度为0 */
    for(max=0,pp=L;pp;pp=pp->a.ptr.tp)
    {
        dep=GListDepth(pp->a.ptr.hp); /* 求以pp->a.ptr.hp为头指针的子表深度 */
        if(dep>max)
            max=dep;
    }
    return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 算法 5.6

Status CopyGList(GList *T,GList L)
{ /* 采用头尾链表存储结构,由广义表L复制得到广义表T。算法5.6 */
    if(!L) /* 复制空表 */
        *T=NULL;
    else
    {
        *T=(GList)malloc(sizeof(GLNode)); /* 建表结点 */
        if(!*T)
            exit(OVERFLOW);
        (*T)->tag=L->tag;
        if(L->tag==ATOM)
            (*T)->a.atom=L->a.atom; /* 复制单原子 */
        else
        {
            CopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp);
            /* 复制广义表L->ptr.hp的一个副本T->ptr.hp */
            CopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);
            /* 复制广义表L->ptr.tp的一个副本T->ptr.tp */
        }
    }
    return OK;
}
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
// 算法 5.7

Status CreateGList(GList *L,SString S) /* 算法5.7 */
{ /* 采用头尾链表存储结构,由广义表的书写形式串S创建广义表L。设emp="()" */
    SString sub,hsub,emp;
    GList p,q;
    StrAssign(emp,"()");
    if(!StrCompare(S,emp))
        *L=NULL; /* 创建空表 */
    else
    {
        *L=(GList)malloc(sizeof(GLNode));
        if(!*L) /* 建表结点 */
            exit(OVERFLOW);
        if(StrLength(S)==1) /* S为单原子 */
        {
            (*L)->tag=ATOM;
            (*L)->a.atom=S[1]; /* 创建单原子广义表 */
        }
        else
        {
            (*L)->tag=LIST;
            p=*L;
            SubString(sub,S,2,StrLength(S)-2); /* 脱外层括号 */
            do
            { /* 重复建n个子表 */
                sever(sub,hsub); /* 从sub中分离出表头串hsub */
                CreateGList(&p->a.ptr.hp,hsub);
                q=p;
                if(!StrEmpty(sub)) /* 表尾不空 */
                {
                    p=(GLNode *)malloc(sizeof(GLNode));
                    if(!p)
                        exit(OVERFLOW);
                    p->tag=LIST;
                    q->a.ptr.tp=p;
                }
            }while(!StrEmpty(sub));
            q->a.ptr.tp=NULL;
        }
    }
    return OK;
}
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
// 算法 5.8

void sever(SString str,SString hstr)
{ /* 将非空串str分割成两部分:hsub为第一个','之前的子串,str为之后的子串 */
    int n,k,i; /* k记尚未配对的左括号个数 */
    SString ch,c1,c2,c3;
    n=StrLength(str);
    StrAssign(c1,",");
    StrAssign(c2,"(");
    StrAssign(c3,")");
    SubString(ch,str,1,1);
    for(i=1,k=0;i<=n&&StrCompare(ch,c1)||k!=0;++i)
    { /* 搜索最外层的第一个逗号 */
        SubString(ch,str,i,1);
        if(!StrCompare(ch,c2))
            ++k;
        else if(!StrCompare(ch,c3))
            --k;
    }
    if(i<=n)
    {
        SubString(hstr,str,1,i-2);
        SubString(str,str,i,n-i+1);
    }
    else
    {
        StrCopy(hstr,str);
        ClearString(str);
    }
}

参考资料

  1. 数据结构（C语言版）.严蔚敏
  2. 2020年数据结构考研复习指导.王道论坛