当前位置:   article > 正文

数据结构——顺序表的概念和基本操作(超全超详细)_顺序表的基本操作 知识点总结

顺序表的基本操作 知识点总结

1. 线性表

  • 是n个具有相同特性的数据元素的有限序列
  • 当n=0时称为空表
  • 常见的线性表有:顺序表、链表、栈、队列、字符串等

2. 顺序表(Sequence List)

  • 本质上就是数组(静态/动态)

  • 数据必须从头连续存储,不能跳跃间隔

2.1 静态顺序表

  • 即直接在结构体中确定存储数据的数组的大小,之后不能对其进行改变

  • 特点:MAX给小了不够用,MAX大了浪费空间

  • 定义:

#define MAX 1000
typedef int SLDataType;	//定义顺序表存储的元素类型
typedef struct SeqList
{
    SLDataType[MAX];
    int size;	//数组中存储了多少个数据
}SL;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

2.2 动态顺序表

  • 定义:
  • 利用动态管理,对内存进行动态开辟,方便后续调整数组大小
#define MAX 5

typedef int SLDataType;	//定义顺序表存储的元素类型
typedef struct SeqList
{
	SLDataType* data;
	int size;	//用来表示当前存储了多少个数据
	int capacity;	//用来表示最大容量
}SeqList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

3. 基本操作

注:以下都以动态顺序表为例:

3.1 顺序表的初始化

void SeqListInit(SeqList* ps);
  • 1

要使用顺序表,我们首先就先要对其初始化:

  • 确定确定初始最大容量
  • 动态开辟内存
  • size置零
void SeqListInit(SeqList* ps)	//初始化
{
	assert(ps);	//保证指针有效

	ps->capacity = MAX;	//确定初始最大容量
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity);	//动态开辟内存
	if (NULL == ps->data)	//检验
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;	//将`size`置零
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

3.2 顺序表的销毁

void SeqListDestory(SeqList* ps);
  • 1

顺序表使用完后,就要对其进行销毁:

  • 释放动态内存
  • size,和最大容量capacity置零
void SeqListDestory(SeqList* ps)	//销毁
{
	assert(ps);//保证指针有效

	free(ps->data);
	ps->size = 0;
	ps->capacity = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3.3 尾插SeqListPushBack()

void SeqListPushBack(SeqList* ps, SLDataType val);
  • 1

在插入之前,我们必须要对存储数据的数组进行检查,如果size已经等于最大容量capacity,那么我们首先就要对其进行增容

3.3.1 判满SeqListFull()
bool SeqListFull(const SeqList* ps)	//判满
{
	assert(ps);

	return ps->capacity == ps->size;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
3.3.2 增容SeqListIncreaseCapacity()
void SeqListIncreaseCapacity(SeqList* ps)	//增容
{
	assert(ps);

	ps->capacity *= 2;	//每次将容量扩大为原来的两倍
	SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity);
	if (NULL == temp)
	{
		perror("realloc");
		exit(-1);
	}
	ps->data = temp;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
3.3.3 SeqListPushBack()

尾插的逻辑十分简单,检查完容量后,直接将新数据插入到最后即可:

提醒:不要忘了将size加一

void SeqListPushBack(SeqList* ps, SLDataType val)	//尾插
{
	assert(ps);	//检验指针有效性
	
    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

    //实现尾插
	ps->data[ps->size++] = val;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

3.4 尾删SeqListPopBack()

void SeqListPopBack(SeqList* ps);
  • 1

注意,在删除数据之前,必须保证顺序表中存放了数据,即size > 0,因此首先要进行判空操作

3.4.1 判空SeqListEmpty()
bool SeqListEmpty(const SeqList* ps)	//判空
{
	assert(ps);

	return ps->size == 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
3.4.2 SeqListPopBack()

尾删操作也十分简单,如果顺序表中存储了数据,那么直接将size减一就可以了,因为这样就访问不到最后一个数据,也就可以看作是删除了。

void SeqListPopBack(SeqList* ps)	//尾删
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//顺序表不能为空

	ps->size--;	//尾删
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3.5 头插SeqListPushFront()

void SeqListPushFront(SeqList* ps, SLDataType val);	
  • 1

和尾插一样,同样首先要对容量进行检查。

要将新数据插入到数组的第一个位置,那么我们就先要将原来的数据全部往后移动一位。

而为了原有数据不被覆盖,必须从后往前挪动数据(如果有疑惑,可以通过画图来理解)

void SeqListPushFront(SeqList* ps, SLDataType val)	//头插
{
	assert(ps);	//检验指针有效性

    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);
	
    //挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
		ps->data[i + 1] = ps->data[i];
    
    //头插
	ps->data[0] = val;
	ps->size++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

3.6 头删SeqListPopFront()

void SeqListPopFront(SeqList* ps)
  • 1

和尾删一样,也先要对顺序表判空,如果为空,就不能进行删除

要实现头删,我们就需要将出第一个元素之外的所有元素向前挪动一位,这样,第一个元素就会被覆盖,从而也就实现了头删

而为了确保原有数据不被覆盖,我们要从前往后挪动数据(有疑惑的可以画图理解)

提醒:删完之后,记得将size减一

void SeqListPopFront(SeqList* ps)	//头删
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//判空

    //挪动数据,实现头删
	for (int i = 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

3.7 在下标pos处插入SeqListInsert()

void SeqListInsert(SeqList* ps, int pos, SLDataType val);	
  • 1

和头插的逻辑类似,要在下标为pos处插入新元素,我们就要将pos和pos之后的元素都向后挪动一位

注意1:同样先要进行容量检查,要注意控制循环边界,防止越界

注意2:由于顺序表要求必须对数据进行连续的存储,因此我们对下标pos也有要求

void SeqListInsert(SeqList* ps, int pos, SLDataType val)	//在pos处插入
{
	assert(ps);	//检验指针有效性
	assert(pos >= 0 && pos <= ps->size);	//检验pos的有效性
	
    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

    //挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
		ps->data[i + 1] = ps->data[i];
    
    //实现插入
	ps->data[pos] = val;
	ps->size++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3.8 删除下标为pos的数据SeqListErase(SeqList* ps, int pos)

void SeqListErase(SeqList* ps, int pos);
  • 1

和头删的逻辑类似,我们只需要将pos后面的所有数据向前挪动一位就可以实现将pos位置的数据删除了

注1:删除之前要判空

注2:要记得检查pos的有效性,防止越界访问

void SeqListErase(SeqList* ps, int pos)	//删除pos处元素
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//判空
	assert(pos < ps->size);	//检验pos有效性
	
    //挪动数据实现删除
	for (int i = pos + 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.9 查找值为val的数据SeqListFind()

int SeqListFind(const SeqList* ps, SLDataType val);	//找到后返回下标,否则返回-1
  • 1

这个操作逻辑十分简单,遍历一遍顺序表,如果找到了,就返回这个下标,否则就返回-1

int SeqListFind(const SeqList* ps, SLDataType val)	//查找值为val的数据
{
	assert(ps);//检验指针有效性

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == val)
		{
			return i;
		}
	}
	return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

3.10 修改下标为pos处的数据

这个操作也十分简单,直接访问下标为pos处的元素就可以了。只是同样需要注意对pos的有效性进行检查

void SeqListModify(SeqList* ps, int pos, int val)	//将下标为pos处的数据修改为val
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->data[pos] = val;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

4. 顺序表的优缺点

4.1 优点

  • 实现尾删和尾插的效率很高
  • 随机访问:由于顺序表使用数组来表示元素,因此可以通过索引快速地随机访问元素。这种特性使得顺序表在查找特定元素时非常高效。
  • 内存连续:顺序表中的元素在内存中是连续存储的,这有助于提高缓存的利用率,从而提高访问效率。
  • 直接存取:相比于其他数据结构,如链表,顺序表的存取操作较为简单,不需要像链表那样处理节点指针,使得存取操作速度更快。
  • 适合小规模数据:对于元素数量较少的情况,顺序表通常比较适用,因为它的内存开销相对较小。

4.2 缺点

  • 插入和删除低效:当需要在顺序表中插入或删除元素时,需要将后续元素移动,以保持连续存储的特性。这样的操作导致插入和删除操作的时间复杂度为O(n),其中n是元素数量。对于频繁的插入和删除操作,顺序表的性能较差。

  • 固定大小:顺序表在创建时需要预先分配一定的存储空间,因此其大小是固定的。如果需要存储的元素数量超过了初始大小,就需要进行扩容操作,这可能导致额外的内存分配和数据搬移开销。

  • 内存浪费:如果实际存储的元素数量远小于顺序表的最大容量,会造成内存空间的浪费。

  • 不易动态调整:由于顺序表的大小固定且内存连续,动态调整其大小较为复杂。在某些场景下,需要频繁调整大小的数据结构时,顺序表可能不是最佳选择。

5. 参考代码

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

#define MAX 5

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* data;
	int size;
	int capacity;
}SeqList;

void SeqListInit(SeqList* ps);	//初始化
void SeqListDestory(SeqList* ps);	//销毁
void SeqListPrint(const SeqList* ps);	//打印
bool SeqListEmpty(const SeqList* ps);	//判空
bool SeqListFull(const SeqList* ps);	//判满
void SeqListIncreaseCapacity(SeqList* ps);	//增容
void SeqListPushBack(SeqList* ps, SLDataType val);	//尾插
void SeqListPopBack(SeqList* ps);	//尾删
void SeqListPushFront(SeqList* ps, SLDataType val);	//头插
void SeqListPopFront(SeqList* ps);	//头删
void SeqListInsert(SeqList* ps, int pos, SLDataType val);	//在pos处插入
void SeqListErase(SeqList* ps, int pos);	//删除pos处元素
int SeqListFind(const SeqList* ps, SLDataType val);	//查找值为val的数据
void SeqListModify(SeqList* ps, int pos, int val);	//将下标为pos处的数据修改为val

void SeqListInit(SeqList* ps)	//初始化
{
	assert(ps);

	ps->capacity = MAX;
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity);
	if (NULL == ps->data)
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;
}

void SeqListDestory(SeqList* ps)	//销毁
{
	assert(ps);

	free(ps->data);
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(const SeqList* ps)	//打印
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);
	printf("\n");
}

bool SeqListEmpty(const SeqList* ps)	//判空
{
	assert(ps);

	return ps->size == 0;
}

bool SeqListFull(const SeqList* ps)	//判满
{
	assert(ps);

	return ps->capacity == ps->size;
}

void SeqListIncreaseCapacity(SeqList* ps)	//增容
{
	assert(ps);

	ps->capacity *= 2;
	SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity);
	if (NULL == temp)
	{
		perror("realloc");
		exit(-1);
	}
	ps->data = temp;
}

void SeqListPushBack(SeqList* ps, SLDataType val)	//尾插
{
	assert(ps);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	ps->data[ps->size++] = val;
}

void SeqListPopBack(SeqList* ps)	//尾删
{
	assert(ps);
	assert(!SeqListEmpty(ps));

	ps->size--;
}

void SeqListPushFront(SeqList* ps, SLDataType val)	//头插
{
	assert(ps);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	for (int i = ps->size - 1; i >= 0; i--)
		ps->data[i + 1] = ps->data[i];
	ps->data[0] = val;

	ps->size++;
}

void SeqListPopFront(SeqList* ps)	//头删
{
	assert(ps);
	assert(!SeqListEmpty(ps));

	for (int i = 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}

void SeqListInsert(SeqList* ps, int pos, SLDataType val)	//在pos处插入
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	for (int i = ps->size - 1; i >= pos; i--)
		ps->data[i + 1] = ps->data[i];
	ps->data[pos] = val;

	ps->size++;
}
void SeqListErase(SeqList* ps, int pos)	//删除pos处元素
{
	assert(ps);
	assert(!SeqListEmpty(ps));
	assert(pos < ps->size);

	for (int i = pos + 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}

int SeqListFind(const SeqList* ps, SLDataType val)	//查找值为val的数据
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == val)
		{
			return i;
		}
	}
	return -1;
}

void SeqListModify(SeqList* ps, int pos, int val)	//将下标为pos处的数据修改为val
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->data[pos] = val;
}

int main()
{
	SeqList* sl;
	sl = (SeqList*)malloc(sizeof(SeqList));
	if (NULL == sl)
	{
		perror("malloc");
		return -1;
	}

	SeqListInit(sl);

    //……………………
    
	SeqListDestory(sl);

	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
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/488764
推荐阅读
相关标签
  

闽ICP备14008679号