数据结构与算法1-1 线性表之顺序表_顺序表实验逻辑结构图

作者：代码探险家 | 2024-08-01 19:34:57

踩

顺序表实验逻辑结构图

1.顺序表的概念

顺序表，就是把若干个元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间中。其中，线性表中的第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置的后面，这样元素的存储方式就构成了顺序表。

在这里插入图片描述
图1.顺序表的结构示意图

2.顺序表的特点

顺序表就好像一排房间，只要知道了第一个房间的房间号，就可以找到其他任何一个房间，这就是顺序表的一个重要特性——随机访问特性。所有用于建造房间的的地皮紧挨着(可能有的地皮上没有房间占用)，同时代表这些地皮连续占用了一块内存，且地皮数是确定的，若在地皮上布置新的房间或拆掉老的房间，地皮数不会增加或减少。这就是顺序表的第二个特性，即顺序表要求占用连续的存储空间，且存储分配只能预先进行，一旦分配完成，对其操作的过程中始终不变。
在这里插入图片描述
图2.顺序表的特点示意图

3.参考代码

（1）顺序表的初始化

首先是对顺序表的结构体初始化：

#define MaxSize 100
typedef struct
{
	int Array[MaxSize];
	int ArrayLength;
}SqlList, *PSqlList;
1
2
3
4
5
6

然后对结构体成员进行初始化：

void  InitSqlList(SqlList &L)
{
	for (int i = 0; i < MaxSize; i++)
	{
		L.Array[i] = 0;
	}
	L.ArrayLength = 0;
}
1
2
3
4
5
6
7
8

（2）顺序表的遍历

顺序表的遍历就是从首个元素开始，逐个输出顺序表中的所有元素值：

void  TravelList(SqlList L)
{
	int i = 0;
	for (i = 0; i < L.ArrayLength; i++)
	{
		printf("%d ", L.Array[i]);
	}
	printf("\r\n");
}
1
2
3
4
5
6
7
8
9

（3）查找表中的元素

通过用户给定的元素值，逐步遍历顺序表，查找表中是否有与其相等的元素，如果有，则输出该元素在顺序表中的位置，否则输出查找失败：

int FindElement(SqlList L, int Element)
{
	int i = 0;
	for (i = 0; i < L.ArrayLength; i++)
	{
		if (L.Array[i] == Element)
		{
			printf("Find Element %d Success!The Position is %d.\r\n", Element, i);
			return i;
		}
	}
	printf("Find Element %d Fail!\r\n",Element);
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（4）向表中增加元素

顺序表在增加元素时，是一个比较繁琐的过程。我们可以打一个简单的比方，比如说，有10个人正在排队，这时有一个人想要插到第四个和第五个人之间，因此，在保证前四个人位置不变的情况下，后面六个人就需要依次后移一个位置，才能让这个人插进去。顺序表的元素的添加正是这样一个道理。
在增加元素的过程中，我们首先判断用户选择的插入位置是否合法。如果合法，则需要先从插入位置开始，将此后的所有元素依次后移一个位置（注意这里后移元素时要从最后一个元素开始进行，否则会出现元素值覆盖），然后再将元素增加到指定位置。同时顺序表元素个数+1；如果插入位置非法，则返回错误。
下面是参考代码：

BOOL InsertElement(SqlList &L, int Position, int Element)
{
	int i = 0;
	//如果数据已满或者添加数据位置错误 返回错误
	if (L.ArrayLength == MaxSize || Position > L.ArrayLength || Position < 0)
	{
		printf("Insert Element %d Fail!\r\n",Element);
		return FALSE;
	}
	else
	{
		//从后往前 依次将数据后移 注意不能从前往后 防止覆盖数据
		for (i = L.ArrayLength - 1; i >= Position; i--)
		{
			L.Array[i + 1] = L.Array[i];
		}

		//将新数据添加到指定位置 同时顺序表长度+1
		L.Array[Position] = Element;
		L.ArrayLength++;
		printf("Insert Element %d Success!\r\n",Element);
		return TRUE;
	}
}
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）从表中删除元素

与向表中增加元素同理，我们依然可以用排队问题来解释删除元素：有10个人在排队，这时，第四个人突然离开了队伍，在保证前三个人位置不变的情况下，后面六个人则需要依次前移一个位置，以此来保证队伍的连续性。顺序表中元素的删除也正是这个原理。
在进行顺序表元素的删除时，我们直接从待删元素的下一个元素开始，直至最后一个元素，将所有元素依次前移一位（注意，这时需要从待删元素下一元素开始进行，否则会出现元素值的覆盖），同时顺序表元素个数-1。
参考代码：

BOOL DeleteElement(SqlList &L, int Element)
{
	int Position = FindElement(L,Element);
	if (Position == -1)
	{
	    printf("Delete Element %d Fail!\r\n",Elment);
		return FALSE;
	}
	else
	{
		int i = 0;
		for (i = Position; i < L.ArrayLength; i++)
		{
			L.Array[i] = L.Array[i + 1];
		}
		L.ArrayLength--;
		printf("Delete Element %d Success!\r\n",Element);
		return TRUE;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（6）main函数

在main函数里进行了函数的测试：

void  _tmain()
{
	SqlList List;
	InitSqlList(List);
	int v1[] = { 10,25,30,58,6,102,56,73,22,19 };
	int i = 0;
	for (i = 0; i < sizeof(v1)/sizeof(int); i++)
	{
		List.Array[i] = v1[i];
	}
	List.ArrayLength = sizeof(v1)/sizeof(int);


	TravelList(List);
	FindElement(List, 102);
	InsertElement(List, 6, 250);
	TravelList(List);
	InsertElement(List, 3, 999);
	TravelList(List);
	DeleteElement(List, 0);
	TravelList(List);
	DeleteElement(List, 22);
	TravelList(List);

}
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

代码测试结果：
在这里插入图片描述
图3.代码测试结果

（7）完整代码展示

#include<iostream>
using namespace std;

#define MaxSize 100

typedef struct
{
	int Array[MaxSize];
	int ArrayLength;
}SqlList, *PSqlList;

void  InitSqlList(SqlList &L);
void  TravelList(SqlList L);
int FindElement(SqlList L, int Element);
BOOL InsertElement(SqlList &L, int Position, int Element);
BOOL DeleteElement(SqlList &L, int Element);

void  _tmain()
{
	SqlList List;
	InitSqlList(List);
	int v1[] = { 10,25,30,58,6,102,56,73,22,19 };
	int i = 0;
	for (i = 0; i < sizeof(v1)/sizeof(int); i++)
	{
		List.Array[i] = v1[i];
	}
	List.ArrayLength = sizeof(v1)/sizeof(int);


	TravelList(List);
	FindElement(List, 102);
	InsertElement(List, 6, 250);
	TravelList(List);
	InsertElement(List, 3, 999);
	TravelList(List);
	DeleteElement(List, 0);
	TravelList(List);
	DeleteElement(List, 22);
	TravelList(List);

}

//静态初始化函数
void  InitSqlList(SqlList &L)
{
	for (int i = 0; i < MaxSize; i++)
	{
		L.Array[i] = 0;
	}
	L.ArrayLength = 0;
}

//遍历顺序表
void  TravelList(SqlList L)
{
	int i = 0;
	for (i = 0; i < L.ArrayLength; i++)
	{
		printf("%d ", L.Array[i]);
	}
	printf("\r\n");
}

//查找元素
int FindElement(SqlList L, int Element)
{
	int i = 0;
	for (i = 0; i < L.ArrayLength; i++)
	{
		if (L.Array[i] == Element)
		{
			printf("Find Element %d Success!The Position is %d.\r\n",Element, i);
			return i;
		}
	}
	printf("Find Element %d Fail!\r\n",Element);
	return -1;
}


//插入元素
BOOL InsertElement(SqlList &L, int Position, int Element)
{
	int i = 0;
	//如果数据已满或者添加数据位置错误 返回错误
	if (L.ArrayLength == MaxSize || Position > L.ArrayLength)
	{
		printf("Insert Element %d Fail!\r\n",Element);
		return FALSE;
	}
	else
	{
		//从后往前 依次将数据后移 注意不能从前往后 防止覆盖数据
		for (i = L.ArrayLength - 1; i >= Position; i--)
		{
			L.Array[i + 1] = L.Array[i];
		}

		//将新数据添加到指定位置 同时顺序表长度+1
		L.Array[Position] = Element;
		L.ArrayLength++;
		printf("Insert Element %d Success!\r\n",Element);
		return TRUE;
	}
}

//删除元素
BOOL DeleteElement(SqlList &L, int Element)
{
	int Position = FindElement(L,Element);
	if (Position == -1)
	{
		printf("Delete Element %d Fail!\r\n", Element);
		return FALSE;
	}
	else
	{
		int i = 0;
		for (i = Position; i < L.ArrayLength; i++)
		{
			L.Array[i] = L.Array[i + 1];
		}
		L.ArrayLength--;
		printf("Delete Element %d Success!\r\n",Element);
		return TRUE;
	}
}

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

4.结语

以上，就是我所总结的顺序表的所有知识点了。顺序表的操作，大家可以类比于数组的增删查遍等操作，只是顺序表比起数组，多了对数组整体和数组属性的封装，使得我们对表进行操作时更加方便和简单。另外，在主函数中，我只是进行了顺序表元素的一些函数的测试，并没有设计用户界面和菜单等部分，大家可以根据需要自行进行设计和完善。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/915606