数据结构笔记【1】

1919 字

10 分钟

数据结构笔记【1】

2024-10-10

数据结构

数据的三种结构#

逻辑结构#

包含：

集合
线性结构（一对一），如线性表、栈、队列
树形结构一个对多个
图状结构多个对多个

存储结构#

顺序存储：按照逻辑顺序存放于连续空间
链式存储（重点）：放到存储区的不同位置，用地址（指针）方式建立逻辑上的联系
索引存储：建立附加的索引表（电话簿）
散列存储：依据数据元素的特殊字段（关键字key）计算元素的存放地址，然后按地址存放

线性表#

线性表是包含若干数据元素的一个线性序列，记为

L=(a_0,...,a_{i-1},a_i,a_{i+1},...,a_{n-1})

$L$ 为表名， $a_i$ 为数据元素， $n$ 为表长， $n>0$ 时表为非空表，否则为空表

线性表可以用二元组形式描述

L=(D,R)

即线性表 $L$ 包含数据元素集合 $D$ 和关系集合 $R$

关系符< $a_i$ , $a_{i+1}$ >为有序对
表示任意两个相邻元素之间的先后次序

$E.g.$ 有顺序表L={1,2,3,4,5,6}，若使用 $L=(D,R)$ 表示，则 $D={1,2,3,4,5,6}$ , $R=<1,2>,<2,3>,...$

线性表的特征：

表头无前驱
表尾无后继
其余元素仅有一个直接前驱和直接后继

顺序存储结构的特点：

逻辑上相邻，则存储位置也相邻
对元素的存取为随机存取或按地址存储
存储密度高
对表的插入和删除等运算的时间复杂度高

C语言中，可借助一维数组类型来表述线性表的顺序存储结构

1
/*
2
    * @brief:创建新线性表
3
    * @param:无
4
    * @return:线性表指针(sqlink类型)，申请失败返回NULL
5
*/
6
sqlink list_create()
7
{
8
    sqlink L;   //声明sqlink类型的表L
9
    L = (sqlink)malloc(sizeof(sqlist));  // 为空表申请内存，返回分配的内存地址
10

11
    //判断内存是否申请成功
12
    if (L == NULL)
13
    {
14
        printf("memory allocation failed\n");
15
        return NULL;
16
    }
17

18
    memset(L, 0, sizeof(sqlist));   //L指向的sqlist结构体的内存清零
19
    L->last = -1;   //表示线性表为空
20

21
    return L;
22
}
23

24
/*
25
    * @brief:清除线性表内的元素，全部置为零
26
    * @param: L:指向表的指针
27
    * @return:成功返回0，失败返回-1
28
*/
29
int list_clear(sqlink L)
30
{
31
    //判断是否是空表
32
    if (L == NULL)
33
    {
34
        return -1;
35
    }
36

37
    memset(L, 0, sizeof(sqlist));   //L指向的sqlist结构体的内存清零
38
    L->last = -1;   //last置为-1，表示线性表为空
39

40
    return 0;
41
}
42

43
/*
44
    * @brief:判断线性表是否为空表
45
    * @param: L:指向线性表的指针
46
    * @return:空表返回1，非空表返回0
47
*/
48
int list_empty(sqlink L)
49
{
50
    //判断是否为空表
51
    if (L->last == -1)
52
    {
53
        return 1;
54
    }
55
    else
56
    {
57
        return 0;
58
    }
59
}
60

61
/*
62
    * @brief:求线性表的长度(有效元素个数)
63
    * @param: L:指向线性表的指针
64
    * @return:表不存在返回-1，否则返回长度
65
*/
66
int list_length(sqlink L)
67
{
68
    if (L == NULL)
69
    {
70
        return -1;
71
    }
72
    return (L->last + 1);   //长度为表尾下标加1
73
}
74

75
/*
76
    * @brief:向线性表内插入数值，插入后原位置向后的所有元素后移一位
77
    * @param: L:指向线性表的指针
78
    * @param: value:待插入值
79
    * @param: pos:插入位置
80
    * @return:插入成功返回0，失败返回-1
81
*/
82
int list_insert(sqlink L, data_t value, int pos)
83
{
84
    if (L == NULL) return -1;   //表不存在返回-1
85
    //判断线性表是否满
86
    if (L->last == N - 1)
87
    {
88
        printf("table is full\n");
89
        return -1;
90
    }
91
    //检查插入位置是否正确，应属于[0,last]，如果是空表则不检查
92
    if (pos < 0 || pos >= L->last + 1)
93
    {
94
        if (L->last != -1)
95
        {
96
            printf("pos is illegal\n");
97
            return -1;
98
        }
99

100
    }
101
    //向后移动原有元素，从最后一个元素开始
102
    for (int i = L->last; i >= pos; i--)
103
    {
104
        L->data[i+1] = L->data[i];
105
    }
106
    //更新插入值和last
107
    L->data[pos] = value;
108
    L->last++;
109

110
    return 0;
111
}
112

113
/*
114
    * @brief:遍历并打印线性表内元素
115
    * @param: L:指向线性表的指针
116
    * @return:成功返回0，失败返回-1
117
*/
118
int list_show(sqlink L)
119
{
120
    if (L == NULL) return -1;   //判断是否为有效表
121
    if (L->last == -1) printf("table is empty\n");  //判断是否为空表
122
    //遍历并打印
123
    for (int i = 0; i <= L->last; i++)  //注意是小于等于，不然不显示表尾
124
    {
125
        printf("%d ",L->data[i]);
126
    }
127

128
    return 0;
129
}
130

131
/*
132
    * @brief:删除全表，包括创建表时所分配的内存
133
    * @param: L:指向线性表的指针
134
    * @return:表不存在返回-1，成功返回0
135
*/
136
int list_delete(sqlink L)
137
{
138
    if (L == NULL) return -1;
139
    free(L);    //释放为表L申请的内存
140
    L = NULL;   //标记表L为无效表
141
    return 0;
142
}
143

144
/*
145
    * @brief:删除表中某一位置的元素
146
    * @param: L：指向线性表的指针
147
    * @param: pos：待删除元素位置
148
    * @return:删除成功返回0，失败返回-1
149
*/
150
int list_delete_single(sqlink L, int pos)
151
{
152
    if (L == NULL) return -1;   //判断是否为无效表
153

154
    //判断pos是否位于有效范围内 应为[0,last]
155
    if (pos < 0 || pos > L->last)
156
    {
157
        printf("pos is illegal\n");
158
        return -1;
159
    }
160

161
    //[pos+1,last]区间内已有元素前移
162
    for (int i = pos + 1; i < L->last + 1; i++)
163
    {
164
       L->data[i-1] = L->data[i];   //数据前移，自动覆盖
165
    }
166

167
    //更新last
168
    L->last--;
169

170
    return 0;
171
}
172

173
/*
174
    * @brief:合并两个线性表，L2全表元素置于L1元素之后
175
    * @param: L1：指向待合并线性表L1的指针
176
    * @param: L1：指向待合并线性表L2的指针
177
    * @return:合并成功返回0，失败返回-1
178
*/
179
int list_merge(sqlink L1, sqlink L2)
180
{
181
    int count = 0;
182
    if (L1 == NULL || L2 == NULL) return -1;
183

184
    //判断合并后L1是否越界
185
    if (L1->last + 1 + L2->last + 1 > N) printf("table is too big\n");
186

187
    //L2的第i位加到L1的last+1+i位置，总共传递L2->last个数
188
    for (int i = 0; i <= L2->last; i++)
189
    {
190
        L1->data[L1->last+1+i] = L2->data[i];
191
        count++;    //计数
192
    }
193

194
    //更新L1->last为原last值+传递完成的元素个数
195
    L1->last = L1->last + count;
196

197
    return 0;
198
}
199

200
/*
201
    * @brief:查询线性表中是否存在某一元素
202
    * @param: L：指向待查询线性表L的指针
203
    * @param: value：待查询值
204
    * @return:值对应的元素存在返回1，不成功返回-1
205
*/
206
int list_locate(sqlink L, data_t value)
207
{
208
    int i = 0;
209

210
    //搜索L中是否有元素等于value
211
    for (i = 0 ; i <=L->last; i++)
212
    {
213
        if (L->data[i] == value) return 1;
214
    }
215

216
    return -1;
217
}
218

219
/*
220
    * @brief:查找L1和L2中是否有相同的元素，将不同的元素存于新表L3
221
    * @param: L1：指向待合并线性表L1的指针
222
    * @param: L2：指向待合并线性表L2的指针
223
    * @return:合并成功返回0，失败返回-1
224
*/
225
sqlink list_mergetonewtable(sqlink L1, sqlink L2)
226
{
227
    sqlink L3 = list_create();  //创建新表L3
228
    int i = 0;
229
    int ret;
230

231
    if (L1 == NULL || L2 == NULL)
232
    {
233
        printf("no such table");
234
        return NULL;
235
    }
236
    //遍历L2内元素
237
    while (i <= L2->last)
238
    {
239
        ret = list_locate(L1, L2->data[i]);   //查找L1中是否有L2中的第i个元素，即判断是否重复
240
        //某元素不重复则向L3插入
241
        if (ret == -1)
242
        {
243
            list_insert(L3, L2->data[i], L3->last+1);   //按顺序向L3插入非重复值
244
        }
245
        i++;    //更新索引
246
    }
247
    return L3;
248
}
249

250
/*
251
    * @brief:清除线性表内的重复元素，清除后所有元素前移补空
252
    * @param: L：指向待合并线性表L1的指针
253
    * @return:操作成功返回0，失败返回-1
254
*/
255
int list_purge(sqlink L)
256
{
257
    if (L == NULL) return -1;
258

259
    for (int i = 0; i <= L->last; i++)  //遍历线性表
260
    {
261
        for (int j = i + 1; j <= L->last; j++)  //从索引i+1开始，如果i+1及之后的元素和data[i]相等，判断为重复
262
        {
263
            if (L->data[i] == L->data[j])
264
            {
265
                printf("The repeated elements are:%d\n",L->data[i]);
266
                list_delete_single(L, j);   //删除重复的第j个元素
267
                j--;    //回退索引，防止跳过未检查的元素
268
            }
269
        }
270
    }
271
    return 0;
272
}