【数据结构】栈、队列和数组

栈

初始化

#define MaxSize 50//栈中元素的最大个数
typedef char ElemType;

//数据结构
typedef struct{
    int top;//栈顶指针
    ElemType data[MaxSize];//存放栈中的元素
}SqStack;

//初始化栈，给top赋值为-1
void InitStack(SqStack *stack){
    stack->top = -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

判断是否为空

//判断栈是否为空,空返回true，反之即返回false
bool StackEmpty(SqStack stack){
    if(stack.top==-1) return true;
    return false;
}
1
2
3
4
5

---

进栈

//进栈
bool Push(SqStack *stack,ElemType e){
    //判断是否满栈
    if(stack->top==MaxSize-1) return false;
    //指针先加1，再入栈
    stack->data[++stack->top]=e;
    return true;
}
1
2
3
4
5
6
7
8

---

出栈

//出栈
ElemType Pop(SqStack *stack){
    //判断是否为空栈
    if(stack->top==-1) return false;
    //先取值，再自减
    return stack->data[stack->top--];
}
1
2
3
4
5
6
7

---

读取栈顶元素

//读取栈顶元素
ElemType GetTop(SqStack stack){
    //判断是否为空栈
    if(stack.top==-1) return false;
    return stack.data[stack.top];
}
1
2
3
4
5
6

---

队列

初始化

#define MaxSize 5
typedef char ElemType;

typedef struct 
{
    ElemType data[MaxSize];
    int rear,front;
}SqQueue;

//初始化
void InitQueue(SqQueue *queue){
    queue->front = queue->rear=0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

判断空

//判断是否为空，即判断首尾指针是否相等
bool QueueEmpty(SqQueue queue){
    if(queue.front==queue.rear) return true;
    return false;
}
1
2
3
4
5

---

入队

//入队
bool EnQueue(SqQueue *queue,ElemType e){
    //判断是否是满队，即尾指针的下一个指向首指针
    if((queue->rear+1)%MaxSize==queue->front) return false;
    queue->data[queue->rear]=e;//赋值
    //尾指针+1取模
    queue->rear = (queue->rear+1)%MaxSize;
    return true;
}
1
2
3
4
5
6
7
8
9

---

出队

//出队
ElemType DeQueue(SqQueue *queue){
    //判断是否为空
    if(queue->front==queue->rear) return false;
    //先取值，首指针再+1取模
    ElemType e = queue->data[queue->front];
    queue->front++;
    return e;
}
1
2
3
4
5
6
7
8
9

---

数组

提到数组，大家首先会想到的是：很多编程语言中都提供有数组这种数据类型，比如 C/C++、Java、Go、C# 等。但本节我要讲解的不是作为数据类型的数组，而是数据结构中提供的一种叫数组的存储结构。

和线性存储结构相比，数组最大的不同是：它存储的数据可以包含多种“一对一”的逻辑关系。举个简单的例子：

上图中，{a1, a2, a3, a4}、{b1, b2, b3, b4}、{c1, c2, c3, c4}、{d1, d2, d3, d4} 中各自包含的元素具有“一对一”的逻辑关系，同时 a、b、c、d 这 4 个序列也具有“一对一”的逻辑关系。

这样存储不止一种“一对一”逻辑关系的数据，数据结构就推荐使用数组存储结构。

---

对于数组存储结构，我们可以这样理解它：数组是对线性表的扩展，是一种“特殊”的线性存储结构，用来存储具有多种“一对一”逻辑关系的数据。

实际场景中，存储具有 N 种“一对一”逻辑关系的数据，通常会建立 N 维数组：

• 一维数组和其它线性存储结构很类似，用来存储只有一种“一对一”逻辑关系的数据：

• 二维数组用来存储包含两种“一对一”逻辑关系的数据。二维数组可以看作是存储一维数组的一维数组
  
• n 维数组用来存储包含 n 种“一对一”逻辑关系的数据，可以看作是存储 n-1 维数组的一维数组；

---

数组存储结构还具有一些其它的特性，包括：

• 无论数组的维度是多少，数组中的数据类型都必须一致；
• 数组一旦建立，它的维度将不再改变；
• 数组存储结构不会对内部的元素做插入和删除操作，常见的操作有 4 种，分别是初始化数组、销毁数组、取数组中的元素和修改数组中的元素。

---

数组的顺序表示和实现

数组可以是多维的，而顺序表只能是一维的线性空间。要想将 N 维的数组存储到顺序表中，可以采用以下两种方案：

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

多维数组中，最常用的是二维数组，接下里就以二维数组为例，讲解数组的顺序存储结构。

所示的二维数组按照“列序为主”的方案存储时，数组中的元素在顺序表中的存储状态如下图所示：

同样的道理，按照“行序为主”的方案存储数组时，各个元素在顺序表中的存储状态如图

---

顺序表中查找和修改数组元素

注意，只有在顺序表内查找到数组中的目标元素之后，才能对该元素执行读取和修改操作。

在 N 维数组中查找目标元素，需知道以下信息：

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

根据存储方式的不同，查找目标元素的方式也不同。仍以二维数组为例，如果数组采用“行序为主”的存储方式，则在二维数组 anm 中查找 aij 位置的公式为：

LOC(i, j) = LOC(0, 0) + (i * m + j) * L;
1

其中，LOC(i, j) 为 aij 在内存中的地址，LOC(0, 0) 为二维数组在内存中存放的起始位置（也就是 a00 的位置）。

而如果采用以列存储的方式，在 anm 中查找 aij 的方式为：

LOC(i, j) = LOC(0, 0) + (j * n + i) * L;
1

根据以上两个公式，就可以在顺序表中找到目标元素，自然也就可以进行读取和修改操作了。

---

代码实现

#include
#include
#include
#include // atoi()
#include // eof()
#include

#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
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
160
161
162
163
164
165
166
167

矩阵的压缩存储

特殊矩阵

这里所说的特殊矩阵，主要分为以下两类：

• 含有大量相同数据元素的矩阵，比如对称矩阵；
• 含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

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

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

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

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

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

例如，在数组 skr[6] 中存储图 1 中的对称矩阵，则矩阵的压缩存储状态如图所示（存储上三角和下三角的结果相同）：

注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。例如，如果想从图中的数组提取矩阵中位于 (3,1) 处的元素，由于该元素位于下三角，需用下三角公式获取元素在数组中的位置，即：

---

稀疏矩阵

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

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

例如，存储上图中的稀疏矩阵，需存储以下信息：

• (1,1,1)：数据元素为 1，在矩阵中的位置为 (1,1)；
• (3,3,1)：数据元素为 3，在矩阵中的位置为 (3,1)；
• (5,2,3)：数据元素为 5，在矩阵中的位置为 (2,3)；
• 除此之外，还要存储矩阵的行数 3 和列数 3；

---

**若对其进行压缩存储，矩阵中各非 0 元素的存储状态如图 **

三元组的结构体

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

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

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

#include
#define NUM 3
//存储三元组的结构体
typedef struct {
    int i, j;
    int data;
}triple;
//存储稀疏矩阵的结构体
typedef struct {
    triple data[NUM];
    int mu, nu, tu;
}TSMatrix;
//输出存储的稀疏矩阵
void display(TSMatrix M);
int main() {
    TSMatrix M;
    M.mu = 3;
    M.nu = 3;
    M.tu = 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) {
    int i, j, k;
    for (i = 1; i <= M.mu; i++) {
        for (j = 1; j <= M.nu; j++) {
            int value = 0;
            for (k = 0; k < M.tu; 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");
    }
}
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

---