顺序表

文章目录

一、顺序表的基本概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表分为以下二类：

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

#define N 200
typedef int SLDataType;

// 顺序表的静态存储 -- N太小，可能不够用，N太大，可能浪费空间
typedef struct SeqList
{
	SLDataType a[N]; // 定长数组
	int size;        // 数据个数
} SL;

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

typedef int SLDataType;

// 顺序表的动态存储	
typedef struct SeqList
{
	SLDataType* a; // 指向动态数组指针
	int size;	   // 数据个数
	int capacity;  // 容量空间大小
} SL;

静态顺序表只适合知道确定要存多少数据的场景。对于静态顺序表的定长数组，如果给的空间太大，会造成空间浪费，但如果开的很少，又可能会造成空间不够用的情况。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小， 所以下面我们实现动态顺序表。

二、动态顺序表的具体实现

1. 顺序表初始化

// 顺序表初始化
void SeqListInit(SL* ps)
{
    assert(ps != NULL); // 防止传入空指针
    
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

直接将指针初始化为 NULL, 再将 size 和 capacity 置为 0。

2. 顺序表尾插

// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
    assert(ps != NULL); // 防止传入空指针
    
	// 检察容量空间，满了扩容
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->size] = x;
	ps->size++; 
}

在一般情况下我们直接在 size 所对应的下标下插入既可，插入完成之后同时要记得 size 要加一。

image-20220425180100037

但这样这真的可以了吗？ 如果此时数据已满，既 size == capacity ，我们还能直接插入吗？这时我们就需要扩容了。

扩容应该扩多大呢？可以根据自己喜好而来，这里采用扩大一倍。在扩容的时候，我们还需要注意一下，我们的capacity是被初始化为0的，不能直接对其进行 capacity *= 2;，而是采用一个临时变量来存储，最后再将临时变量的值赋给我们的capacity，第一次这里给capacity开辟了4个容量，以后每次对其扩大一 倍。

image-20220425180732706

3. 顺序表头插

// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps != NULL); // 防止传入空指针
    
	SeqListCheckCapacity(ps);

	// 挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[0] = x;
	ps->size++;
}

在一般情况下，我们直接将所有数据从后往前，依次后移一位。最后再将数据插入到 0 下标处。同样因为是插入元素，size要加一。在这里插入图片描述

此时这里同样也面临着一样的问题，如果数据已经满了，我还怎么头插，所以在插入之前，应先判断是否需要增容。增容的代码我们已经在顺序表的头插中实现了，为了不让同一段代码多次重复出现，我们直接将增容封装成一个函数 SeqListCheckCapacity。头插和尾插直接调用函数就可以了。

image-20220425220553967

// 检察容量
void SeqListCheckCapacity(SL* ps)
{
    assert(ps != NULL); // 防止传入空指针
    
	// 检察容量空间，满了扩容
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

4. 顺序表尾删

// 顺序表尾删
void SeqListPopBack(SL* ps)
{
    assert(ps != NULL); // 防止传入空指针
    
	// 温柔检察
	//if (ps->size == 0)
	//{
	//	printf("SeqList is empty\n");
	//	return;
	//}

	// 暴力检察
	assert(ps->size > 0);

	ps->size--;
}

在正常情况下，直接将 size 减一，我们已经无法访问到这个元素了，和直接将其删除起到了同样的效果。

但是在删除时，我们要判断一下，当前还有没有元素，如果没有元素（size == 0），这时我们再调用尾删，此时 size == -1，这时当我们再插入时，size指向了一个不合法的下标，程序便会发现意想不到的错误。

这里检察我们分为了两种（这里我们采用了暴力检察）：

一种是温柔的检察，如果此时size为0 ，便会向屏幕打印一条提示信息，然后结束本次尾删操作。

一各是暴力的检察，如果此时size为0 ，程序会直接终止，并向屏幕自动打印一条错误信息。

5. 顺序表头删

// 顺序表头删
void SeqListPopFront(SL* ps)
{
    assert(ps != NULL); // 防止传入空指针
	assert(ps->size > 0);

	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

在正常情况下，将首元素后的数据依次往前移一位。最终再将size 减一。

同上，删除前应先判断还有没有元素。

image-20220425232322777

6. 顺序表任意位置插入

// 顺序表任意位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos <= ps->size);

	SeqListCheckCapacity(ps);

	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}

	ps->a[pos] = x;
	ps->size++;

}

在一般情况下，从最后一个元素到 pos所指向的元素，均向后移动一位，最终将数据插入到pos所指向的位置。因为是插入所以size要加一。

在插入之前应先检察容量，看看是否需要扩容。

image-20220425234825490

在设计完在任意位置插入后，这里我们发现我们以前写的头插、尾插其实可以直接复用我们的函数。

// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListInsert(ps, ps->size, x);
}

// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListInsert(ps, 0, x);
}

7. 顺序表任意位置删除

// 顺序表任意位置删除
void SeqListErase(SL* ps, int pos)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;
}

直接将 pos 后的数据依次往进移一位。之后将 size减一。
在这里插入图片描述

同样在设计完在任意位置删除后，此时我们的头删、尾删就可以直接复用我们的函数。

// 顺序表尾删
void SeqListPopBack(SL* ps)
{
	SeqListErase(ps, ps->size - 1);
}

// 顺序表头删
void SeqListPopFront(SL* ps)
{
	SeqListErase(ps, 0);
}

8. 顺序表查找

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i; // 找到了，返回下标
	}

	return -1; // 未找到
}

用于查找某个元素是否存在，找到了返回对应下标，找不到返回-1。

用于配合其它函数使用。如：查找某个数将其删除或在前方插入一个数，或修改这个数。

9. 顺序表修改

// 顺序表修改
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos < ps->size);

	ps->a[pos] = x;
}

用于修改指定位置的值。

用于配合其它函数使用。

10. 顺序表打印

// 顺序表打印
void SeqListPrint(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

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

打印顺序表中的所有元素。

11. 顺序表销毁

// 顺序表销毁
void SeqListDestory(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

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

释放动态申请的内存，将指针置为空，同时将 size 和 capacity 置为 0。

以上顺序表的基本功能已经全部实现。

这里我们提供了三个文件

SeqList.h ： 函数声明，头文件引用，类型定义等。

SeqList.c： 顺序表的具体代码实现。

Test.c ：用于测试程序。

三、完整代码

SeqList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//#define N 200
//typedef int SLDataType;
//
 顺序表的静态存储 -- N太小，可能不够用，N太大，可能浪费空间
//struct SeqList
//{
//	SLDataType a[N]; // 定长数组
//	int size;        // 数据个数
//};


typedef int SLDataType;

// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* a; // 指向动态数组指针
	int size;	   // 数据个数
	int capacity;  // 容量空间大小
} SL;


// 顺序表初始化
void SeqListInit(SL* ps);

// 检察容量
void SeqListCheckCapacity(SL* ps);

// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x);

// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x);

// 顺序表尾删
void SeqListPopBack(SL* ps);

// 顺序表头删
void SeqListPopFront(SL* ps);

// 顺序表任意位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);

// 顺序表任意位置删除
void SeqListErase(SL* ps, int pos);

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);

// 顺序表修改
void SeqListModify(SL* ps, int pos, SLDataType x);

// 顺序表打印
void SeqListPrint(SL* ps);

// 顺序表销毁
void SeqListDestory(SL* ps);

SeqList.c

#include "SeqList.h"

// 顺序表初始化
void SeqListInit(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

// 检察容量
void SeqListCheckCapacity(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

	// 检察容量空间，满了扩容
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	//assert(ps != NULL); // 防止传入空指针

	//SeqListCheckCapacity(ps);

	//ps->a[ps->size] = x;
	//ps->size++; 

	SeqListInsert(ps, ps->size, x);
}

// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	//assert(ps != NULL); // 防止传入空指针

	//SeqListCheckCapacity(ps);

	 挪动数据
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}

	//ps->a[0] = x;
	//ps->size++;

	SeqListInsert(ps, 0, x);
}

// 顺序表尾删
void SeqListPopBack(SL* ps)
{
	//assert(ps != NULL); // 防止传入空指针

	 温柔检察
	if (ps->size == 0)
	{
		printf("SeqList is empty\n");
		return;
	}

	 暴力检察
	//assert(ps->size > 0);

	//ps->size--;

	SeqListErase(ps, ps->size - 1);
}

// 顺序表头删
void SeqListPopFront(SL* ps)
{
	//assert(ps != NULL); // 防止传入空指针
	//assert(ps->size > 0);

	//for (int i = 0; i < ps->size - 1; i++)
	//{
	//	ps->a[i] = ps->a[i + 1];
	//}

	//ps->size--;

	SeqListErase(ps, 0);
}

// 顺序表任意位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos <= ps->size);

	SeqListCheckCapacity(ps);

	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}

	ps->a[pos] = x;
	ps->size++;

}

// 顺序表任意位置删除
void SeqListErase(SL* ps, int pos)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;
}

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i; // 找到了，返回下标
	}

	return -1; // 未找到
}

// 顺序表修改
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps != NULL); // 防止传入空指针
	assert(pos >= 0 && pos < ps->size);

	ps->a[pos] = x;
}


// 顺序表打印
void SeqListPrint(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

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

// 顺序表销毁
void SeqListDestory(SL* ps)
{
	assert(ps != NULL); // 防止传入空指针

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

Test.c

#include "SeqList.h"

void TestSeqList()
{
	SL sl;

	SeqListInit(&sl);

	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPrint(&sl);

	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	SeqListPrint(&sl);

	SeqListPopBack(&sl);
	SeqListPrint(&sl);

	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	SeqListInsert(&sl, 0, 3);
	SeqListInsert(&sl, 0, 2);
	SeqListPrint(&sl);

	SeqListErase(&sl, 1);
	SeqListPrint(&sl);

	int pos = SeqListFind(&sl, 3);
	if (pos != -1)
	{
		SeqListModify(&sl, pos, 5);
	}
	SeqListPrint(&sl);

	SeqListDestory(&sl);
}

int main()
{
	
	TestSeqList();

	return 0;
}
# 数据结构
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

avatar 开放原子开发者工作坊

开发者谈开源：洞悉协作创新背后的机遇与挑战

近日，在2024开放原子开发者大会暨首届开源技术学术大会开幕式上，开放原子开源基金会与openKylin、EasyAda、KWDB开源项目举行捐赠签约仪式。 一场捐赠签约仪式，让三个开源项目及其背后的开发者们受到瞩目。本次，我们与“龘”（EasyAda）核心维护者王伶卓开启了对话。

avatar 开放原子开发者工作坊