• 【数据结构】顺序表

    文章目录

    一. 线性表

    1.什么是线性表

    线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

    2.线性表的结构

    线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

    image-20220811174242793

    二. 顺序表

    1.什么是顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 通俗的说，顺序表就是数组，但是顺序表要求数组里面的元素必须连续存储。

    2.顺序表的分类

    顺序表一般分为两类，静态顺序表和动态顺序表。

    静态顺序表：使用定长数组存储元素。

    //静态的顺序表
#define N 1000
#define int SLDataType;//重命名数据类型
typedef struct SeqList
{
	SLDataType arr[N];//定长数组
	size_t size;//存储数据的个数
}SL;

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

    动态顺序表：使用动态开辟的数组存储元素。

    typedef int SLDataType;//对数据类型进行重命名SLDataType
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	size_t size; //记录存储数据的个数
	size_t capacity; //存储空间的大小
}SL;

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

    顺序表对比：相比较于动态顺序表，静态顺序表存在很大的缺陷，主要就是空间问题，当我们的数据很多的时候，我们开辟的空间不够用；但是当我们的数据很少的时候，我们开辟的空间太大，造成严重的浪费，所以静态顺序表只适用于明确知道需要多少数据的场景。所以现实中，我们基本使用的都是动态顺序表，根据需要动态的分配内存空间的大小，而静态顺序表基本不怎么使用。

    三.动态顺序表实现

    下面我们用C语言实现一个动态顺序表。

    1.结构的定义

    #define DEF_SIZE 4//初始的容量
#define CRE_SIZE 2//每次增容的倍数
typedef int SLDataType;//对数据类型进行重命名SLDataType
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	size_t size; //记录存储数据的个数
	size_t capacity; //存储空间的大小
}SL;

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

    首先，我们利用宏定义定义初始容量为4，每次增容的倍数为2，也就是我们的顺序表满了以后，一次增容后的空间是上一次的二倍。为什么是2倍呢？这是因为2倍比较合适，但不一定必须是它，具体情况具体分析。一次性增容太多容易出现空间浪费严重。一次增容太少容易频繁增容，造成效率低下。

    其次，我们将数据类型进行重命名为SLDataType，这样的好处是以后我们用这个顺序表管理其他类型的数据的时候，只需要修改这一处就可以了。

    最后，对比静态顺序表，我们的结构体多了capacity这个参数，我们用它来记录顺序表空间的大小，当capacity的大小等于size的大小的时候，我们就对顺序表的空间进行增容。并且由于size和capacity的大小不可能小于0，所以我们把它们的数据类型置为size_t(无符号整型)。

    2.顺序表的初始化

    void SeqListInit(SL* psl)
{
	assert(psl);//断言：防止psl为空指针
	psl->size = 0;
	psl->arr = NULL;
	psl->capacity = 0;
}

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

    由于顺序表刚开始为空，我们把size和capacity都置为0，且把指向动态开辟的数组的指针置为空指针。

    3.检查空间容量（增容）

    void CheckSeqList(SL* psl, SLDataType x)
{
	if (psl->capacity == psl->size)
	{
		size_t NewCapacity = 0;
		NewCapacity = psl->capacity == 0 ? DEF_SIZE: psl->capacity * CRE_SIZE;
		SLDataType* tmp = (SLDataType*)realloc(psl->arr, NewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
			//exit(-1);
		}
		psl->arr = tmp;
		psl->capacity = NewCapacity;
	}
}

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

    在检查容量的函数中，当我们结构体中的size和capacity相等时，我们就增容。这里注意第一次检查的时候，由于capacity和size都等于0，增容二倍，但是0的二倍还是0。所以第一次增容时，我们把capacity的值赋成DEF_SIZE，以后增容，就是capacity*CRE_SIZE。为了方便，我们再创建一个新的变量NewCapacity，用条件表达式表示NewCapacity。

    在增容时，我们要注意不要直接用arr指针来接收realloc函数的返回值，避免增容失败返回空指针，导致arr指针找不到之前管理的那空间，从而造成内存泄漏。我们临时创建一个变量tmp，如果它不为空指针，说明增容成功，再把它赋值给arr指针。

    4.顺序表尾插

    void SeqListPushBack(SL* psl, SLDataType x)
{
    assert(psl);
	CheckSeqList(psl, x);
	//法一：
	/*psl->arr[psl->size] = x;
	psl->size++;*/
	//法二：
	SeqListInsert(psl, psl->size, x);
}

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

    在顺序表尾部插入数据很简单，直接插入。不过插入数据前，要检查容量。

    5.顺序表尾删

    void SeqListPopBack(SL* psl)
{
	assert(psl);
	 //温柔的检查
	/*if (psl->size == 0)
	{
	return;
	}*/
	 //暴力的检查
	assert(psl->size > 0);
    //法一：
	psl->size--;
	//法二：
	//SeqListErase(psl, psl->size-1);
}

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

    在顺序表尾部删除数据很简单，我们只需要将size–即可，并不需要缩容和改动，因为我们以后插入数据的时候，会直接将原来空间中的数据覆盖掉。不过为了防止删完数据还在删数据，造成下标越界访问，我们要检查一下存储数据的大小是否大于0，有两种检查方式，暴力的检查方式就是报错会告诉你，错误在哪里。

    6.顺序表头插

    void SeqListPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	CheckSeqList(psl, x);
    //法一：
	int end = psl->size-1;
	while (end >= 0)
	{
		psl->arr[end+1] = psl->arr[end];
		end--;
	}
	psl->arr[0] = x;
	psl->size++;
	//法二：
	//SeqListInsert(psl, 0, x);
}

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

    在顺序表头部插入数据时，我们需要先将顺序表中的数据整体向后挪动一位，然后在顺序表的头部插入，插入完成后，记得size++。

    7.顺序表头删

    void SeqListPopFront(SL* psl)
{
	assert(psl);
	assert(psl->size > 0);
    //法一：
	/*size_t begin = 0;
	while (begin < psl->size-1)
	{
		psl->arr[begin] = psl->arr[begin+1];
		begin++;
	}*/
    //法二：
	size_t begin = 1;
	while (begin < psl->size)
	{
		psl->arr[begin-1] = psl->arr[begin];
		begin++;
	}
	psl->size--;
	//法三：
	//SeqListErase(psl, 0);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    在顺序表头部删除数据时，我们需要先将顺序表中的数据整体向前挪动一位，然后size–即可。

    8.顺序表查找

    int SeqListFind(SL* psl, SLDataType x)
{
	assert(psl);
	size_t i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

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

    遍历顺序表中的元素，但我们找到指定的元素时，返回元素的下标；但该元素不存在时，我们返回一个无意义的值（如-1)。

    9.顺序表在指定位置(pos)插入指定的值(x)

    void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
	CheckSeqList(psl, x);
	//法一：
	//int end = psl->size - 1;
	//while (end >= (int)pos)
	//{
	//	psl->arr[end + 1] = psl->arr[end];
	//	end--;
	//}
	//法二：
	size_t end = psl->size;
	//psl->arr[pos] = x;//位置错误，arr[pos+1] = arr[pos]
	while (end > pos)//pos等于0，存在死循环问题
	{
		psl->arr[end] = psl->arr[end-1];
		end--;
	}
	psl->arr[pos] = x;
	psl->size++;
	//++psl->size;前置后置++均可
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    在指定位置处插入数据，我们需要先将pos及其之后的元素整体向后挪动一位，然后再在pos处插入数据。

    我们发现头插和尾插也可以调用SeqListInsert函数实现，我们可以进行改造，以此简化代码：

    头插

    void SeqListPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	SeqListInsert(psl, 0, x);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    尾插

    void SeqListPushBack(SL* psl, SLDataType x)
{
    assert(psl);
	SeqListInsert(psl, psl->size, x);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    10.顺序表删除指定位置(pos)的值

    void SeqListErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	size_t begin = pos;
	while (begin < psl->size-1)
	{
		psl->arr[begin] = psl->arr[begin + 1];
		begin++;
	}
	psl->size--;
}

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

    删除指定位置数据，我们需要将pos后面数据整体向前挪动一位，然后让size–。

    同上，头删和尾删也可以调用SeqListErase函数实现，我们可以进行改造，以此简化代码：

    头删

    void SeqListPopFront(SL* psl)
{
	assert(psl);
	SeqListErase(psl, 0);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    尾删

    void SeqListPopBack(SL* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size-1);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    11.顺序表销毁

    void SeqListDestory(SL* psl)
{
    //法一：
	assert(psl);
	free(psl->arr);
	psl->arr = NULL;
	psl->size = 0;
	psl->capacity = 0;
    //法二：
    //SeqListInit(psl);
}

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

    在销毁顺序表之前，一定要将前面动态开辟的内存释放掉，防止内存泄漏。

    12.顺序表打印

    void SeqListPrint(SL* psl)
{
	assert(psl);
	size_t i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ",psl->arr[i]);
	}
	printf("\n");
}

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

    遍历一遍顺序表元素，打印出来。

    13.顺序表修改

    void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size > pos);
	psl->arr[pos] = x;
}

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

    找到指定下标的元素，并修改为指定的值。注意检查size的值一定要大于pos。

    重要面试题：删除数据是否需要缩容？

    我们知道，插入数据空间不够时我们要增容，那么删除数据达到一定的数量后我们是否要缩容呢？答案是不用缩容。原因如下：

    第一：我们缩容之后插入数据又需要重新增容，而增容是有代价的，会降低程序的效率。我们知道 realloc 函数扩容分为两种情况，一种是原地扩容，即当原来的空间后面有足够的空闲空间时，操作系统会直接将那一块空间交由我们使用，这种情况对效率影响不大；另一种是异地扩容，即当原来空间后面没有足够的的空间开辟时，操作系统会在另外空间足够的地方为我们开辟一块新的空间，这时操作系统需要先将我们原来空间中的数据拷贝到新空间中，再将原来的空间释放掉，这种情况对效率的影响就比较大了。

    第二：缩容也是有代价的。其实缩容和扩容的过程是一样的，都分为原地和异地，会对程序效率造成影响。

    第三：顺序表申请的是一块连续的空间，而free函数数并不能释放连续空间的一部分，只能全部一起释放，所以这里即使想释放也是做不到的。

    所以综合前面三个因素考虑，顺序表删除数据不会缩容；这是我们典型的以空间换时间的做法。

    四.完整代码

    1.SeqList.h

    #define _CRT_SECURE_NO_WARNINGS 1
//#pragma once

#include 
#include 
#include 

//#ifndef __SEQLIST_H__
//#define __SEQLIST_H__
...
//#endif

#define DEF_SIZE 4//初始的容量
#define CRE_SIZE 2//一次增容的倍数

//静态的顺序表
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType arr[N];//定长数组
	size_t size;//存储数据的个数
}SL;


typedef int SLDataType;//对数据类型进行重命名SLDataType
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	size_t size; //记录存储数据的个数
	size_t capacity; //存储空间的大小
}SL;

//对数据的管理：基本增删查改接口

// 顺序表初始化
void SeqListInit(SL* psl);
// 检查空间容量，如果满了，进行增容
void CheckCapacity(SL* psl);
// 顺序表尾插
void SeqListPushBack(SL* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头插
void SeqListPushFront(SL* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SL* psl);
// 顺序表打印
void SeqListPrint(SL* psl);
// 顺序表修改
void SeqListModify(SL* psl, size_t pos, SLDataType 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

    2.SeqList.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SeqListInit(SL* psl)
{
	assert(psl);
	psl->size = 0;
	psl->arr = NULL;
	psl->capacity = 0;
}

void CheckSeqList(SL* psl, SLDataType x)
{
	if (psl->capacity == psl->size)
	{
		size_t NewCapacity = 0;
		NewCapacity = psl->capacity == 0 ? DEF_SIZE: psl->capacity * CRE_SIZE;
		SLDataType* tmp = (SLDataType*)realloc(psl->arr, NewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
			//exit(-1);
		}
		psl->arr = tmp;
		psl->capacity = NewCapacity;
	}
}


void SeqListDestory(SL* psl)
{
	assert(psl);
	/*if (psl->arr)
	{*/
	free(psl->arr);//free(psl) error
	psl->arr = NULL;
	psl->size = 0;
	psl->capacity = 0;
	//}
}


void SeqListPushBack(SL* psl, SLDataType x)
{
	//法一：
	/*assert(psl);
	CheckSeqList(psl, x);
	psl->arr[psl->size] = x;
	psl->size++;*/
	//法二：
	SeqListInsert(psl, psl->size, x);
}

void SeqListPushFront(SL* psl, SLDataType x)
{
	//法一：
	/*assert(psl);
	CheckSeqList(psl, x);
	int end = psl->size-1;
	while (end >= 0)
	{
		psl->arr[end+1] = psl->arr[end];
		end--;
	}
	psl->arr[0] = x;
	psl->size++;*/
	//法二：
	SeqListInsert(psl, 0, x);
}

void SeqListPopBack(SL* psl)
{
	//法一：
	assert(psl);
	 //温柔的检查
	/*if (psl->size == 0)
	{
	return;
	}*/

	 //暴力的检查
	assert(psl->size > 0);

	//psl->arr[psl->size-1] = 0; 不太需要
	psl->size--;
	//法二：
	//SeqListErase(psl, psl->size-1);
}

void SeqListPopFront(SL* psl)
{
	//法一：
	assert(psl);
	assert(psl->size > 0);
	/*size_t begin = 0;
	while (begin < psl->size-1)
	{
		psl->arr[begin] = psl->arr[begin+1];
		begin++;
	}*/
	size_t begin = 1;
	while (begin < psl->size)
	{
		psl->arr[begin - 1] = psl->arr[begin];
		begin++;
	}
	psl->size--;
	//法二：
	//SeqListErase(psl, 0);
}

void SeqListPrint(SL* psl)
{
	assert(psl);
	size_t i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ",psl->arr[i]);
	}
	printf("\n");
}

int SeqListFind(SL* psl, SLDataType x)
{
	assert(psl);
	size_t i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
	CheckSeqList(psl, x);
	//法一：
	//int end = psl->size - 1;
	//while (end >= (int)pos)
	//{
	//	psl->arr[end + 1] = psl->arr[end];
	//	end--;
	//}
	//法二：
	size_t end = psl->size;
	//psl->arr[pos] = x;//位置错误，arr[pos+1] = arr[pos]
	while (end > pos)//pos等于0，存在死循环问题
	{
		psl->arr[end] = psl->arr[end-1];
		end--;
	}
	psl->arr[pos] = x;
	psl->size++;
	//++psl->size;
}

void SeqListErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	size_t begin = pos;
	while (begin < psl->size-1)
	{
		psl->arr[begin] = psl->arr[begin + 1];
		begin++;
	}
	psl->size--;
}

void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(psl->size > pos);
	psl->arr[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
    • 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

    3.Test.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void TestSeqList1()
{
	SL s;//初始化
	SeqListInit(&s);
	//尾插
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPrint(&s);//打印
	//头插
	SeqListPushFront(&s, 10);
	SeqListPushFront(&s, 20);
	SeqListPushFront(&s, 30);
	SeqListPrint(&s);
    //尾删
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);
	//头删
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);
	//销毁
	SeqListDestory(&s);
}

void TestSeqList2()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);
	//在指定位置插入指定元素
	SeqListInsert(&s, 1, 10);
	SeqListInsert(&s, 3, 20);
	SeqListInsert(&s, 5, 30);
	SeqListInsert(&s, 7, 40);
	SeqListPrint(&s);
	//在指定位置删除元素 
	//注意元素越来越少
	SeqListErase(&s, 0);
	SeqListErase(&s, 1);
	SeqListErase(&s, 2);
	SeqListErase(&s, 3);
	SeqListPrint(&s);

	/*int* p1 = (int*)malloc(sizeof(int) * 10);
	assert(p1);
	printf("p1:%p\n", p1);

	int* p2 = (int*)realloc(p1, sizeof(int) * 5);
	assert(p2);
	printf("p2:%p\n", p2);*/

	SeqListDestory(&s);
}


void TestSeqList3()
{
	SL s;
	SeqListInit(&s);
	SeqListPushFront(&s, 30);
	SeqListPushFront(&s, 20);
	SeqListPushFront(&s, 10);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 6);
	SeqListPrint(&s);

	int x = 0;
	int y = 0;
	printf("请输入要查找的元素:>\n");
	scanf("%d", &x);//要查找的元素
	printf("请输入要修改的值:>\n");
	scanf("%d", &y);//要修改的值
	//查找该元素是否存在
	int pos = SeqListFind(&s, x);
	if (pos != -1)
	{
		printf("要查找的元素下标存在，并且为：%d\n", pos);
		//存在就修改
		SeqListModify(&s, pos, y);
	}
	printf("修改后的顺序表元素为:\n");
	SeqListPrint(&s);
    
    SeqListDestory(&s);
}

int main()
{
	//TestSeqList1();
	TestSeqList2();
	//TestSeqList3();
	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

    五.顺序表的缺陷

    1. 中间/头部的插入删除需要挪动数据，时间复杂度为O(N)，效率太低。

    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

    为了解决这些问题，我们设计出了链表。

    六.顺序表力扣OJ题

    点👇
    顺序表力扣

  • 相关阅读:
    Mac MySQL初始登录root报错access denied解决方法
    【AWVS破解安装学习】
    【软考 系统架构设计师】案例分析⑧ 数据库索引与视图
    嵌入式仿真测试平台的思考
    Autosar MCAL-ADC详解（一）-基于Tc27x的cfg软件
    CUDA01 - 硬件架构、warp调度、指令流水线和cuda并发流
    密码学基础——加密与哈希，凯撒密码，对称加密与非对称加密以及Diffie-Hellman密码交换协议
    【并发编程十：CompletableFuture的应用】
    Opencv实现图像的基本变换
    牛顿迭代法
  • 原文地址：https://blog.csdn.net/m0_64224788/article/details/126324234