• 数据结构初步（三）- 线性表之顺序表的分析与C语言实现

    目录

    前言

    本节将要介绍线性表里的顺序表，从简单的数据结构开始，慢慢深入。

    1. 线性表

    概念

    线性表是n个具有相同特性的数据元素的有限序列。
    线性表时一种在实际中广泛使用的数据结构。
    线性表的逻辑结构是线性结构，也就是说是连续的。
    线性表的物理结构不一定是连续的，在实际储存时是以数组和链式的形式储存的。

    种类

    线性表包括：顺序表、链表、栈、队列、字符串…
    .png
    .png

    2. 顺序表

    2.1 概念

    顺序表是用一段物理地址连续的储存单元依次储存数据元素的线性结构。
    顺序表的数据一般采用数组类型储存，完成对数据的增删查改等操作。

    2.2 结构

    2.2.1 静态顺序表

    概念

    静态顺序表使用定长数组储存数据元素。
    静态顺序表储存的容量事先就已经确定，不能在程序运行时扩充容量，实际使用时灵活性较差，所以静态顺序表使用较少。

    image.png

    C语言代码实现

    头文件SeqList.h
    进行头文件的包含、动态顺序表结构体的声明、函数声明、#define定义

    #pragma once
#include 
#include 
#include 

#define INITCAPACITY 1000//容量
typedef int SLDataType;

typedef struct SeqList {
	SLDataType data[INITCAPACITY];
	int size;//静态顺序表大小
}SL;

//初始化顺序表
void SLInit(SL* phead);

//输出顺序表
void SLPrint(const SL* phead);

//销毁顺序表
void SLDestroy(SL* phead);


//头插尾插 头删尾删
void SLPushBack(SL* phead, SLDataType x);
void SLPushFront(SL* phead, SLDataType x);
void SLPopBack(SL* phead);
void SLPopFront(SL* phead);

//查找pos位置元素,找到就返回下标，否则返回-1
int SLFind(const SL* phead, SLDataType x);

//修改pos位置元素
void SLModify(SL* phead, size_t pos, SLDataType x);

//在pos位置前增加一个数据元素
void SLInsert(SL* phead, size_t pos, SLDataType x);

//删除pos位置的数据
void SLErase(SL* phead, size_t pos);

//使用接口SLInsert()、SLErase()的头插尾插、头删尾删
void SLPushBack2(SL* phead, SLDataType x);
void SLPushFront2(SL* phead, SLDataType x);
void SLPopBack2(SL* phead);
void SLPopFront2(SL* phead);

    • 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

    函数定义源文件SeqList.c
    函数具体功能实现

    #include "SeqList.h"

//初始化顺序表
void SLInit(SL* phead) {
	assert(phead);
	memset(phead, 0, sizeof(SL));
}

//输出顺序表
void SLPrint(const SL* phead) {
	assert(phead);
	for (int i = 0; i < phead->size; ++i) {
		printf("%d ", phead->data[i]);
	}
	printf("\n");
}

//销毁顺序表
void SLDestroy(SL* phead) {
	assert(phead);
	phead->size = 0;
	memset(phead, 0, sizeof(SL));
}

//头插尾插 头删尾删
void SLPushBack(SL* phead, SLDataType x) {
	assert(phead);
	//暴力检查，当顺序表已经满时，尝试增加数据的操作会导致报错
	assert(phead->size < INITCAPACITY);
	phead->data[phead->size] = x;
	++phead->size;

}

void SLPushFront(SL* phead, SLDataType x) {
	assert(phead);
	//暴力检查，当顺序表已经满时，尝试增加数据的操作会导致报错
	assert(phead->size < INITCAPACITY);
	for (int i = phead->size; i > 0; --i) {
		phead->data[i] = phead->data[i - 1];
	}
	phead->data[0] = x;
	phead->size++;
}

void SLPopBack(SL* phead) {
	assert(phead);
	//暴力检查，当顺序表已经为空时，在尝试进行删除操作将会报错
	assert(phead->size > 0);
	--phead->size;
}

void SLPopFront(SL* phead) {
	assert(phead);
	//暴力检查，当顺序表已经为空时，在尝试进行删除操作将会报错
	assert(phead->size > 0);
	for (int i = 0; i < phead->size - 1; ++i) {
		phead->data[i] = phead->data[i + 1];
	}
	--phead->size;
}


//查找元素,找到就返回下标，否则返回-1
int SLFind(const SL* phead, SLDataType x) {
	assert(phead);
	for (int i = 0; i < phead->size; ++i) {
		if (phead->data[i] == x) {
			return i;
		}
	}
	return -1;
}

//修改pos位置元素
void SLModify(SL* phead, size_t pos, SLDataType x) {
	assert(phead);
	//暴力检查，当传入的下标越界时就报错
	assert(pos < phead->size);
	phead->data[pos] = x;
}

//在pos位置前增加一个数据元素
void SLInsert(SL* phead, size_t pos, SLDataType x) {
	assert(phead);
	//暴力检查，当传入的下标越界时就报错
	assert(pos <= phead->size && phead->size < INITCAPACITY);
	for (int i = phead->size; i > pos; --i) {
		phead->data[i] = phead->data[i - 1];
	}
	phead->data[pos] = x;
	++phead->size;
}

//删除pos位置的数据
void SLErase(SL* phead, size_t pos) {
	assert(phead);
	for (int i = pos; i < phead->size - 1; ++i) {
		phead->data[i] = phead->data[i + 1];
	}
	--phead->size;
}

//使用接口SLInsert()、SLErase()的头插尾插、头删尾删

void SLPushBack2(SL* phead, SLDataType x) {
	SLInsert(phead, phead->size, x);
}

void SLPushFront2(SL* phead, SLDataType x) {
	SLInsert(phead, 0, x);
}

void SLPopBack2(SL* phead) {
	SLErase(phead, phead->size - 1);
}

void SLPopFront2(SL* phead) {
	SLErase(phead, 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

    2.2.2 动态顺序表

    概念

    动态顺序表借助指针使用动态开辟的数组储存数据元素。
    由于动态顺序表的结构可以借助指针指向开辟在堆区的连续的一片内存空间，在程序运行过程中开辟的空间不够了容量不够时便可以通过realloc()函数重新开辟一块空间使顺序表的容量增大。在实际使用中相比静态顺序表来说非常方便，不用再受到顺序表容量的限制，需要熟练掌握。
    但是频繁的开辟空间是有系统开销的，并且由于顺序表的数据在物理结构上必须是连续的，每次开辟空间都要开辟至少是整个顺序表的大小的空间，所带来的系统开销也会较大。

    image.png

    功能分析
    防止头文件被重复多次包含
    #ifndef __SEQLIST__H__
#define __SEQLIST__H__
//内容
#endif

    • 1
    • 2
    • 3
    • 4

    #idndef、#define、#endif都是条件编译指令，作用是防止头文件被重复多次包含。

    #pragma once

    • 1

    单独的pragma once也可以达到预防头文件被多次重复包含的作用，并且比条件编译指令简洁。

    头文件的包含
    #include 
#include 
#include 

    • 1
    • 2
    • 3

    程序将要使用到的头文件。

    定义封装的储存数据的基本类型
    //封装顺序表结构体类型
typedef struct SeqList{
	SLDataType *data;
	int size;
	int capacity;
}SL;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    动态顺序表要解决的问题是静态顺序表无法实时扩容。也就是说顺序表的空间需要动态开辟。
    基本结构体类型成员包括指针成员、顺序表当前大小、顺序表容量，其中指针将要指向动态开辟的空间。
    为了能够灵活储存不同的数据类型的元素，减少我们多次修改数据类型的次数，我们直接在程序起始就为把将要储存的数据类型重定义为一个新名字SLDataType。
    为了我们在写代码时使用的方便，我们把比较长的struct SeqList重定义了一个新名字SL。

    顺序表初始化
    //初始化
void SLInit(SL* psl) {
	assert(psl);//断言
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在定义好顺序表后，顺序表一定有这有效的地址，SLInit()接受的顺序表的地址也一定不为NULL，所以需要断言检查assert()，如果地址为NULL说明传错顺序表的地址了，此时程序将报错。
    初始化顺序表没有数据，顺序表指针指向NULL，大小psl->size置为0，容量psl->capacity置为0。

    顺序表输出到控制台
    //打印
void SLPrint(const SL* psl) {
	assert(psl);//断言
	for (int i = 0; i < psl->size; ++i) {
		printf("%d ", psl->data[i]);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    循环输出顺序表内容。

    顺序表销毁
    //销毁
void SLDestroy(SL* psl) {
	assert(psl);//断言
	free(psl->data);
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    程序退出前需要销毁顺序表，使用free()释放指针psl->data所指向的动态开辟的内存空间，为了防止pal->data是野指针，把pal->data置为NULL。
    把顺序表大小和容量赋值为0。

    检查顺序表的容量并扩容
    //检查容量并扩容
void SLCheckCapacity(SL* psl) {
	if (psl->size == psl->capacity) {
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->data, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL) {
			return;
		}
		psl->data = tmp;
		psl->capacity = newcapacity;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在往顺序表中添加数据前需要先判断顺序表当前大小psl->size与容量psl->capacity是否相等，如果当前大小小于容量说明添加数据前不需要扩容，否则需要为顺序表进行扩容操作。
    我们需要计算顺序表新容量的大小，并用临时变量psl->newcapacity储存，如果是空表psl->capacity==0就为psl->newcapacity赋一个合适的初始值（这里我用4赋值）；如果不是空表顺序表容量就扩大（这里每次扩大2倍）。
    创建一个临时SLDataType*的指针tmp存放realloc()开辟的内存空间的起始地址或空指针。如果tmp的值是NULL，说明realloc()开辟内存失败，扩容失败，需要让程序直接返回；如果tmp的值不为NULL，说明扩容成功，接下来就把新开辟空间的起始地址赋给顺序表指针成员psl->data。
    储存顺序表新容量的newcapacity赋值给顺序表容量成员psl->capacity。

    image.png

    尾插数据
    //尾插数据
void SLPushBack(SL* psl, SLDataType x) {
	assert(psl);
	//检查容量并扩容
	SLCheckCapacity(psl);
	psl->data[psl->size] = x;
	++psl->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    尾插数据

    image.png

    头插数据
    //头插数据
void SLPushFront(SL* psl, SLDataType x) {
	assert(psl);
    //检查容量并扩容
	SLCheckCapacity(psl);
	for (int i = psl->size; i > 0; --i) {
		psl->data[i] = psl->data[i - 1];
	}
	psl->data[0] = x;
	++psl->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    头插数据

    image.png

    尾删数据
    //尾删一个数据
void SLPopBack(SL* psl) {
	assert(psl);
    //暴力检查,顺序表为空就报错
	assert(psl->size > 0);
	//温柔检查，顺序表为空函数直接返回
	/*if (psl->size == 0) {
		return;
	}*/
	--psl->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    尾删数据,psl->size控制的是整个顺序表的大小，被删除位置的值并不需要做出多余的改变，因为被删除位置不再属于顺序表的有效位置了。
    当顺序表为空，即psl->size == 0时，不能继续进行删除操作并对此情况做出反应：

    1. 暴力检查：使用assert进行断言检查，当调用删除函数时，先检查顺序表是否为空，若为空就报错提醒。
    2. 温柔检查：使用ifelse语句进行检查，当顺序表为空时此函数就返回。

    image.png

    头删数据
    //头删数据
void SLPopFront(SL* psl) {
	assert(psl);
	assert(psl->size > 0);//暴力检查,顺序表为空就报错
    //温柔检查，顺序表为空函数直接返回
	/*
	if(psl->size == 0){
		return;
	}
	*/
	for (int i = 0; i < psl->size - 1; ++i) {
		psl->data[i] = psl->data[i + 1];
	}
	--psl->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    头删数据

    image.png

    查找数据
    //查找，找到返回下标，否则返回-1
int SLFind(SL* psl, SLDataType x) {
	assert(psl);
	
	for (int i = 0; i < psl->size; ++i) {
		if (psl->data[i] == x) {
			return i;
		}
	}
	return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    遍历顺序表即可，找到返回下标；找不到返回-1（下标不可能为负值）。

    修改指定位置处的数据
    //指定pos位置并修改数据
void SLModify(SL* psl, size_t pos, SLDataType x) {
	assert(psl);
	assert(pos < psl->size);
	psl->data[pos] = x;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    在指定位置（下标）前插入数据
    //指定pos位置插入数据x
void SLInsert(SL* psl, size_t pos, SLDataType x){
	assert(psl);
	assert(pos <= psl->size);
	SLCheckCapacity(psl);

	for(int i=psl->size; i > pos; --i){
		psl->data[i] = psl->data[i - 1];
	}
	psl->data[pos] = x;
	++psl->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在插入数据之前，需要对传入的pos位置（下标）进行判断
    一般在pos位置前插入数据需要：

    1. 检查顺序表容量；
    2. 依次移动从顺序表末尾位置到pos位置的数据，此操作完成后pos位置就空了出来；
    3. 在pos位置插入数据。
    4. 删除成功，顺序表的大小-1。

    考虑到当pos == psl->size时是在顺序表尾部插入数据虽然是特殊情况，但是插入数据后其与前面的数据仍是连续的，所以这种情况时可以进行数据的插入。

    image.png

    在指定位置处（下标）删除数据
    //指定pos位置删除数据x
void SLErase(SL* psl, size_t pos) {
	assert(psl);
	assert(pos < psl->size);

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    删除某个位置的数据，要求下标pos在有效下标内即psl->pos < psl->size。
    操作：

    1. 检查下标pos是否在有效下标内；
    2. 删除pos位置数据直接把pos位置数据覆盖掉就可以了，从pos的下一个位置开始，每个数据依次向左移动一位，覆盖pos位置数据并保持顺序表的连续。
    3. 删除成功，顺序表大小-1。

    image.png

    借助插入函数实现头插、尾插操作
    //尾插
void SLPushBack(SL* psl, SLDataType x) {
	SLInsert(psl, psl->size, x);
}

    • 1
    • 2
    • 3
    • 4
    //头插
void SLPushFront(SL* psl, SLDataType x) {
	SLInsert(psl, 0, x);
}

    • 1
    • 2
    • 3
    • 4
    借助删除函数实现头删、尾删操作
    //尾删
void SLPopBack(SL* psl) {
	SLErase(psl, psl->size - 1);
}

    • 1
    • 2
    • 3
    • 4
    //头删
void SLPopFront(SL* psl) {
	SLErase(psl, 0);
}

    • 1
    • 2
    • 3
    • 4
    完整C语言代码实现

    头文件SeqList.h
    进行头文件的包含、动态顺序表结构体的声明、函数声明、#define定义

    #ifndef __SEQLIST__H__
#define __SEQLIST__H__
//条件编译指令，防止头文件被重复多次包含
#include 
#include 
#include 

typedef int SLDataType;

//封装顺序表结构体类型
typedef struct SeqList{
	SLDataType *data;
	int size;
	int capacity;
}SL;

//初始化
void SLInit(SL* psl);

//打印
void SLPrint(const SL* psl);

//销毁
void SLDestroy(SL* psl);

//检查容量并扩容
void SLCheckCapacity(SL* psl);

//头插尾插 头删尾删
void SLPushBack(SL* psl, SLDataType x);
void SLPushFront(SL* psl, SLDataType x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);

//查找，找到返回下标，否则返回-1
int SLFind(SL* psl, size_t pos);

//指定pos位置插入数据x
void SLInsert(SL* psl, size_t pos, SLDataType x);

//指定pos位置删除数据x
void SLErase(SL* psl, size_t pos);

//指定pos位置并修改数据
void SLModify(SL* psl, size_t pos, SLDataType x);

#endif


    • 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

    函数定义源文件SeqList.c
    函数具体功能实现

    #include "SeqList.h"

//初始化
void SLInit(SL* psl) {
	assert(psl);
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

//打印
void SLPrint(const SL* psl) {
	assert(psl);
	for (int i = 0; i < psl->size; ++i) {
		printf("%d ", psl->data[i]);
	}
	printf("\n");
}

//销毁
void SLDestroy(SL* psl) {
	assert(psl);
	free(psl->data);
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

//检查容量并扩容
void SLCheckCapacity(SL* psl) {
	if (psl->size == psl->capacity) {
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->data, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL) {
			return;
		}
		psl->data = tmp;
		psl->capacity = newcapacity;
	}
}

//头插尾插 头删尾删
void SLPushBack(SL* psl, SLDataType x) {
	//assert(psl);
	检查容量并扩容
	//SLCheckCapacity(psl);
	//psl->data[psl->size] = x;
	//++psl->size;
	SLInsert(psl, psl->size, x);
}

void SLPushFront(SL* psl, SLDataType x) {
	/*assert(psl);
	SLCheckCapacity(psl);

	for (int i = psl->size; i > 0; --i) {
		psl->data[i] = psl->data[i - 1];
	}
	psl->data[0] = x;
	++psl->size;*/
	SLInsert(psl, 0, x);
}

void SLPopBack(SL* psl) {
	assert(psl);
	assert(psl->size > 0);
	//
	/*if (psl->size == 0) {
		return;
	}*/
	--psl->size;
}

void SLPopFront(SL* psl) {
	assert(psl);
	assert(psl->size > 0);
	/*
	if(psl->size == 0){
		return;
	}
	*/
	for (int i = 0; i < psl->size - 1; ++i) {
		psl->data[i] = psl->data[i + 1];
	}
	--psl->size;
}

//查找，找到返回下标，否则返回-1
int SLFind(SL* psl, SLDataType x) {
	assert(psl);
	
	for (int i = 0; i < psl->size; ++i) {
		if (psl->data[i] == x) {
			return i;
		}
	}
	return -1;
}

//指定pos位置插入数据x
void SLInsert(SL* psl, size_t pos, SLDataType x){
	assert(psl);
	assert(pos <= psl->size);
	SLCheckCapacity(psl);

	for(int i=psl->size; i > pos; --i){
		psl->data[i] = psl->data[i - 1];
	}
	psl->data[pos] = x;
	++psl->size;
}

//指定pos位置删除数据x
void SLErase(SL* psl, size_t pos) {
	assert(psl);
	assert(pos < psl->size);

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

//指定pos位置并修改数据
void SLModify(SL* psl, size_t pos, SLDataType x) {
	assert(psl);
	assert(pos < psl->size);
	psl->data[pos] = x;
}

    • 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

    3. 顺序表优点与缺点

    优点

    1. 尾插、尾删效率较高,是O(1)；
    2. 可以实现对数据元素的随机访问（通过下标）；
    3. 在数据一定的情况下，动态顺序表向内存单次申请的空间较大，申请的次数就少，一定程度上减少了内存碎片的产生。
    4. cpu高速缓存命中较高，相同的算法使用顺序表进行储存实现相比即将到来的链表进行储存实现的效率更有优势，其中一个原因是数组是连续存放的。

    缺点

    1. 头插、头删等操作（遍历数组）效率较低,是O(n)；
    2. 动态顺序表在容量不够时，单次申请空间时的系统开销较大。
    3. 如果开辟的空间不合理，会存在严重的空间浪费。

    结语

    本节介绍了线性表中的顺序表相关的概念与一种代码实现，顺序表与接下来学习到的链表都是基本的数据结构，它们虽然简单，但是使用广泛，并且常常作为复杂数据结构的子结构，我们应该熟练掌握。

    END

  • 相关阅读:
    扭蛋机小程序开发，互联网下的发展形式
    学计算机必参加的含金量赛事！
    网页设计与制作项目三“网上花店”
    深入了解视觉语言模型
    客服快捷回复语
    胆囊结石危害具体是什么？
    【算法基础】基础算法（三）--（双指针算法、位运算、离散化、区间合并）
    pytest集成allure报告（allure安装及配置以及如何实现集成）
    数据分析 - matplotlib示例代码
    获得文件夹下所有文件目录
  • 原文地址：https://blog.csdn.net/weixin_64904163/article/details/126712214