1. 首页
  2. 文章中心
  3. 数据结构

手把手带你入门--线性表的顺序存储（大话数据结构）

112 阅读 0 评论
我是靠谱客的博主 忐忑百合，这篇文章主要介绍手把手带你入门--线性表的顺序存储（大话数据结构），现在分享给大家，希望可以做个参考。

C语言简单实现线性表的顺序存储

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构，实际上就是在内存中找一块连续的存储空间，然后将相同数据类型的数据元素存储在这块存储空间中。所以用C语言中的一维数组就可以实现顺序存储结构。

线性表的顺序存储结构优点在于可以快速随机访问表中任意位置的元素，并且因为其占用的一段连续的存储空间，所以不需要为表示元素之间的逻辑关系来增加额外的存储空间节省空间（相对） 。

而线性表的顺序存储结构的缺点就在于插入和删除操作需要移动大量元素，执行效率低，并且数组的容量需要提前确定，因此可能造成空间浪费。

线性表的基本结构：

  • 要存储的数据
  • 线性表长度
  • 数组的最大值
复制代码
1
2
3
4
5
typedef struct{
ElemType data[MAX];
int length;
}SqList;

准备工作：

复制代码
1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#define MAX 20
//数组的最大长度
#define OK 1
#define error 0
//OK和error代表函数状态，分别为1（函数成功运行），0（函数出错）
typedef int Status;
//Status是函数类型，其值是函数结果状态代码，如OK代表成功，error代表出错。
typedef int ElemType;
//ElemType代表数组类型，根据实际情况确定，这里假设为int型

线性表的顺序存储结构的8种基本操作：

  • 初始化
  • 判断线性表是否为空
  • 清空线性表
  • 返回线性表的给定位置元素值
  • 插入元素
  • 删除元素
  • 查找元素
  • 合并线性表

下面给出具体分析：

线性表的初始化：

即将线性表的长度赋值为0

复制代码
1
2
3
4
5
Status initList(SqList *L){
L->length = 0;
return OK;
}

判断线性表是否为空:

这里我稍微做了一点改进，直接用bool返回线性表为空的真假：

长度为真，返回 true。

长度为假，返回 false。

复制代码
1
2
3
4
5
6
7
8
//判断线性表是否为空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}

清空线性表：

与初始化一样，将线性表的长度置为0。

复制代码
1
2
3
4
5
Status ClearList(SqList *L){
L->length = 0;
return OK;
}

返回线性表的给定位置元素值：

1.首先判断该元素是否合理

  • 最小位置不能小于1
  • 最大位置不能大于线性表的长度
  • 线性表的长度不能为0

2.然后将该位置元素的值赋值给e。

（因为要保留e的值，不能使e所占内存空间在函数调用完成后自动释放，所以这里采用指针）

复制代码
1
2
3
4
5
6
7
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}

插入元素：

1.判断限制条件，如果线性表已满，插入位置不合理，则插入失败。

2.如果是在最后一个位置，直接赋值即可

3.如果不在最后一个位置，从最后一个位置开始，全部后移一位。

4.长度加一，给即将插入的元素赋值

PS：因为数组是从0开始计数的，所以对应线性表的位置，永远减一
线性表改变，所以需要传指针。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//插入操作：在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L.length == MAX)
return error;
//判断线性表长度是否大于数组长度 
if(i < 1 || i > L.length + 1)
return error;
//判断插入位置是否合理 
if(i <= L.length){
for(int k = L.length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾，则从线性表的最后一个位置开始，所有元素向后移动一位
//一直到插入位置的前一个元素

}
L.length++;
L->data[i-1] = e;
//长度加一，为新插入的元素赋值 
}

删除元素：

1.先判断删除位置是否合理，具体如上。

2.将要删除的元素的值赋值给e。

3.如果是在最后一个位置，直接删除即可

4.如果不在最后一个位置，从该位置的后一位开始，全部前移一位。

4.长度减一，给即将插入的元素赋值

PS：因为数组是从0开始计数的，所以对应线性表的位置，永远减一。线性表改变，所以需要传指针。需要获得e的值，e也要传指针。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除操作：删除 L 的第一个数据元素，并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}

查找元素：

1.线性表长度为0，查找失败

2.遍历数组，成功则返回其在线性表中的位置

复制代码
1
2
3
4
5
6
7
8
9
10
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}

合并两个线性表（将Lb中的元素插入La）：

1.遍历Lb中数组，得到第i个位置对应元素的值，赋与e。

2.如果La中没有对应的元素，将e的值插入到La的最后一个位置。

3.La长度加一。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}

完整代码实现（加入测试）：

复制代码
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
#include<stdio.h>
#define MAX 20
//数组的最大长度
#define OK 1
#define error 0
typedef int Status;
//Status是函数类型，其值是函数结果状态代码，如OK代表成功，error代表出错。
typedef int ElemType;
//ElemType代表数组类型，根据实际情况确定，这里假设为int型
typedef struct{
ElemType data[MAX];
int length;
}SqList;
//初始化线性表 
Status initList(SqList *L){
L->length = 0;
return OK;
}
//判断线性表是否为空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}
//输出数组数据 
void ListTraverse(SqList L){
for(int i = 0; i < L.length; i++)
printf("%d ",L.data[i]);
printf("n");
}
//清空线性表
Status ClearList(SqList *L){
L->length = 0;
return OK;
}
//用e返回L中第 i个数据元素的值
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}
//查找元素 e 
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}
//插入操作：在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L->length == MAX)
return error;
//判断线性表长度是否大于数组长度 
if(i < 1 || i > L->length + 1)
return error;
//判断插入位置是否合理 
if(i <= L->length){
for(int k = L->length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾，则从线性表的最后一个位置开始，所有元素向后移动一位
//一直到插入位置的前一个元素

}
L->length++;
L->data[i-1] = e;
//长度加一，为新插入的元素赋值 
}
//删除操作：删除 L 的第一个数据元素，并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > L->length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,La_len++,e);
}
}
int main(){
SqList L,Lb;
ElemType e;
Status r;
r = initList(&L);
int k;
printf("初始化L后,L.length = %dn",L.length);
for(int i = 1; i <= 5 ; i++){
r = ListInsert(&L,1,i);
}
printf("在L的表头依次插入1-5后：L.data = ");
ListTraverse(L);
printf("L.length = %dn",L.length);
if(ListEmpty(L))
printf("L为空n");
else
printf("L不为空n");
r = ClearList(&L);
printf("清空L后,L.length = %dn",L.length);
if(ListEmpty(L))
printf("L为空n");
else
printf("L不为空n");
for(int i = 1; i <= 10 ; i++){
ListInsert(&L,i,i);
}
printf("在L的表头插入1-10后，L.data = ");
ListTraverse(L);
printf("L.length = %dn",L.length);
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data= ");
ListTraverse(L);
printf("L.length=%dn",L.length);
GetElem(L,5,&e);
printf("第5个元素的值为:%dn",e);
for(int i = 3;i <= 4; i++){
r = LocateElem(L,i);
if(r == 0)
printf("没有值为%d的元素n",r);
else
printf("第%d个元素的值为:%dn",r,i);
}
k = L.length;
for(int i = k + 1 ; i >= k ;i--){
r = ListDelete(&L,i,&e);
if(r == error)
printf("删除第%d个元素失败！n",i);
else
printf("删除第%d个元素的值为%dn",i,e);
}
printf("依次输出L的元素: ");
ListTraverse(L);
r = 5;
ListDelete(&L,r,&e);
printf("删除第%d个元素的值为%dn",r,e);
printf("依次输出L的元素: ");
ListTraverse(L);
r = initList(&Lb);
for(int i = 6;i <= 15; i++){
r = ListInsert(&Lb,1,i);
}
ListUnion(&L,Lb);
printf("依次输出合并了Lb的L的元素：");
ListTraverse(L);
return 0;
}

第一次发布博客，有问题还望大家指出。
（水平菜的一批，哈哈）

最后

以上就是忐忑百合最近收集整理的关于手把手带你入门--线性表的顺序存储（大话数据结构）的全部内容，更多相关手把手带你入门--线性表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(74)

相关文章

数据结构C++ 实现单链表
数据结构C++ 实现单链表
顺序表创建和就地逆置
顺序表创建和就地逆置
线性表
线性表
数据结构实验1_顺序表的操作
数据结构实验1_顺序表的操作
手把手带你入门--线性表的顺序存储（大话数据结构）
手把手带你入门--线性表的顺序存储（大话数据结构）
关于被调函数形参：SqList L、SqList &L、SqList *L 的区别
关于被调函数形参：SqList L、SqList &L、SqList *L 的区别
实验一 顺序表、单链表基本操作的实现
实验一 顺序表、单链表基本操作的实现
数据结构之顺序表与链表的基本操作前言一、基本功能   二、模块代码完整代码
数据结构之顺序表与链表的基本操作前言一、基本功能   二、模块代码完整代码

评论列表共有 0 条评论

立即
投稿
返回
顶部