实现顺序表（增、删、查、改）

  • 开发
  • 27

引言：顺序表是数据结构中的一种形式，就是存储数据的一种结构。

这里会用到动态内存开辟，指针和结构体的知识

1.什么是数据结构

数据结构就是组织和存储数据的结构。

数据结构的特性：

物理结构：在内存中存储的数据是否连续

逻辑结构:   逻辑上是否连续

2.什么是顺序表

为了更好的实现顺序表，首先的了解其的特性。

顺序表的特性：

物理结构：连续的

逻辑结构：连续的

顺序表也是线性结构的一种

线性结构的特性：

物理结构：不一定连续

逻辑结构：连续的

顺序表的底层是数组。顺序表在数组的基础上能通过调用函数实现数据的增删查改。

数组在内存中开辟的空间是连续的，所以其存储的数据在内存中也是连续的。

3.静态顺序表与动态顺序表哪个更好呢？ 

顺序表又分为静态顺序表，和动态顺序表

那么哪种更好呢？ 

静态顺序表和动态顺序表的结构

//静态顺序表的结构
struct SeqList
{
	int arr[100];//开辟的空间大小已经确定
	int size;//记录当前元素的个数
};
//动态顺序表的结构
struct SeqList
{
	int* arr;
	int size;//记录当前元素的个数
	int capacity;//记录当前能存放元素的个数，如果size=capacity时，扩容
};

动态顺序表的结构图解：

 

比较：

静态顺序表开辟的存放数据的空间：如果开辟过大，则浪费空间；若开辟过小，若想存的数据过多，则有的数据存不进去。

而动态顺序表则更灵活，不够了再开辟就可以了。

所以动态顺序表更好，这里也只会将动态顺序表的实现。

4.动态顺序表的实现

4.1通过多文件的形式实现

文件管理：

test.c 进行各个接口的测试
SeqList.c 实现增删查改函数的实现
SeqLst.h 引用需要使用的头文件，动态顺序表结构体的定义，实现增删查改函数函数的声明，#define 定义的符号

需要实现的函数： 

初始化、销毁 创建完动态顺序表的结构后应对其成员进行初始化，释放开辟的空间，并将结构体的成员初始化
增

有头插，尾插

任意插
删

头删，尾删

任意删
查 查找顺序表中是否有查找的元素

这里直接给出完整的SeqList.h 中的全部代码：

#pragma once//防止头文件多次包含

//用到的库函数
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//如果以后想存储的数据不再是int 只需要改这一出的int改为别的数据类型
#define SLDataType int

//顺序表的结构定义
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;


//以下为需要实现的函数的声明
//初始化
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印
void SLPrint(SL ps);
//尾插，尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//尾删，头删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//任意插，任意删
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps,SLDataType find);

4.2初始化和销毁注意事项

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

 一定要传定义的结构体的地址，这样才能改变所定义的结构体的值。

//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

4.3尾插，头插中的一些注意事项

尾插实现函数：

void SLPushBack(SL* ps, SLData x)
{
    //ps不能为NULL
	assert(ps != NULL);
	//增容：1.capacity和size都为0   2.空间不够用
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLData* tmp = (SLData*)realloc(ps->arr, newcapacity * sizeof(SLData));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
    //将值写入顺序表
	ps->arr[ps->size] = x;
    //插入完顺序表中元素的个数+1
	ps->size++;
}

增容问题：

如果结构体中的size 和capacity 都为0，或size等于capacity（所开辟的空间都被使用完）时，就要增容。

用realloc，malloc还是用calloc开辟空间呢？

考虑到增容的问题所以用realloc开辟空间。

那么增多大呢？

这里不好解释，建议增大当前所开辟空间的2或3倍。如果开辟小了的话，很快就会被用完，就会频繁地开辟，如果是下图中realloc开辟空间中的情况2，拷贝数据很影响程序性能；若开辟过大，则浪费空间。

因为插入会考虑到增容问题所以可以写一个实现增容的函数。

void CheckSLCapacity(SL* ps)
{
    //如果size等于capacity说明开辟的空间已经使用完，得增容
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLData* tmp = (SLData*)realloc(ps->arr, newcapacity * sizeof(SLData));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

头插和尾插实现的代码：

//头插
void SLPushFront(SL* ps, SLData x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);//增容函数，上面的尾插的代码中的实现增容的代码也可以替换为这个函数
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//头插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

 4.4 头删和尾删

实现代码：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	for (int i = 0; i <ps->size-1 ; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}

注意：如果顺序表中没有数据那么就不能继续删除了， assert(ps->size > 0)防止没有数据了继续删。

尾删：只需要将size--就可以，不需要将最后的数据修改（修改也是可以的），但别忘了最后size--

头删：将除头部的其他数据整体向前挪动一位。

头删图解：

4.5 任意删和任意插

实现代码：

//任意插
//pos为想要插入的位置的下标
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
    //若pos小于0，不能插入；若想要插入的位置大于size也不能插入
	assert(pos >= 0 && pos <= ps->size);
    //考虑扩容问题
	CheckSLCapacity(ps);
    //注意赋值的顺序和 i 的范围
	for (int i = ps->size; i>pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}


//任意删
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;

}

注意事项：

任意插入：

对插入位置下标（pos）的限制： pos >= 0 && pos <= ps->size

图解：

通过上图可以用任意插函数实现头插和尾插

 

任意插入后挪动数据的方式：

从pos位置开始集体往后挪

 任意删除后的数据挪动方式：

从size-1 开始往前挪直到pos+1 的位置。

用任意插入和任意删除的函数实现 头插，尾插和头删，尾删

//头插、尾插
void SLPushBack1(SL* ps, SLDataType x)
{
	SLInsert(ps, ps->size, x);
}
void SLPushFront1(SL* ps, SLDataType x)
{
	SLInsert(ps, 0, x);
}
//尾删，头删
void SLPopFront1(SL* ps)
{
	SLErase(ps, 0);
}
void SLPopBack1(SL* ps) 
{
	SLErase(ps, ps->size-1);

}

4.6查找 

实现函数：

int SLFind(SL* ps,SLDataType find)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
        //如果找到返回下标
		if (ps->arr[i] == find)
			return i;
	}
    //没找到返回小于0 的数
	return -1;
}

查找函数的使用：

	int find = SLFind(&s, 6);
	if (find < 0)
		printf("找不到\n");
	else
		printf("%d\n", find);

为什么没找到返回小于0的数？

因为存储的数据的下标都大于等于0。

 

 5.完整代码来喽！

test.c：（这就是我自己写代码使用的一些测试用例，大家可以自己写测试用例，自己测试，则一块不是很重要）

#include "SeqList.h"
void SLTest()
{
	SL s;
	SLInit(&s);
	//SLPrint(s);
	//SLPushBack(&s, 1);
	//SLPrint(s);
	//SLPushBack(&s, 2);
	//SLPrint(s);	
	//SLPushBack(&s, 3);
	//SLPrint(s);
	//SLPushBack(&s, 4);
	//SLPrint(s);
	SLPushBack(&s, 5);
	SLPrint(s);
	/*SLPushBack(NULL, 5);*/
	SLPushFront(&s, 6);
	SLPrint(s);
	SLPushFront(&s, 7);
	SLPrint(s);
	/*SLPushFront(NULL, 7);*/
	SLPopFront(&s);
	SLPrint(s);
	SLPopBack(&s);
	SLPrint(s);
	//SLPopFront(&s);
	//SLPrint(s);
	SLPopFront(&s);
	SLPrint(s);
	SLDestory(&s);
}
void SLTest1()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPrint(s);
	SLInsert(&s, 0, 4);
	SLPrint(s);
	SLInsert(&s,4,5);
	SLInsert(&s,3,6);
	SLPrint(s);
	SLErase(&s, 4);
	SLPrint(s);
	SLErase(&s, 0);
	SLPrint(s);
	int find = SLFind(&s, 6);
	if (find < 0)
		printf("找不到\n");
	else
		printf("%d\n", find);
	SLDestory(&s);
}
int main()
{
	/*SLTest();*/
	SLTest1();
	return 0;
}

SeqList.h

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

#define SLDataType int
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;

//初始化
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印
void SLPrint(SL ps);
//尾插，尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//尾删，头删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//任意插，任意删
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps,SLDataType find);

 

SeqList.c：

#include "SeqList.h"

void CheckSLCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
		printf("%d ", s.arr[i]);
	printf("\n");
}


void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);

	CheckSLCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}


void SLPopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	ps->size--;
}

void SLPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	for (int i = 0; i <ps->size-1 ; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckSLCapacity(ps);
	for (int i = ps->size; i>pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;

}

int SLFind(SL* ps,SLDataType find)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == find)
			return i;
	}
	return -1;
}

结语：

头次写数据结构，放平心态 ，一定要写完一个接口调试一个接口，不要都写完了再去调试，若有一堆问题容易心态爆炸（boom）。

 拜拜，下一期。目标项目：通讯录。

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-04 01:46:02       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-04 01:46:02       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-04 01:46:02       87 阅读

  19. Python语言-面向对象

    2024-04-04 01:46:02       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-04 01:46:02       91 阅读

热门阅读

  7. [ RV1108_LINUX] 关于如何调整cpu中vdd_core的电压

    2024-04-04 01:46:02       35 阅读

  11. uniapp 打开抖音小程序

    2024-04-04 01:46:02       35 阅读

  12. 使用的sql

    2024-04-04 01:46:02       40 阅读

  13. go中结构体标签：omitempty、json꞉“name“、 gorm꞉“column꞉name“、yaml꞉“name“

    2024-04-04 01:46:02       42 阅读

  14. 网络安全：筑牢防线，抵御恶意攻击

    2024-04-04 01:46:02       40 阅读

  15. springboot

    2024-04-04 01:46:02       41 阅读

  17. Oracle控制文件管理

    2024-04-04 01:46:02       30 阅读

  19. Oracle联机日志文件管理

    2024-04-04 01:46:02       35 阅读

  20. dlib中rectangle与opencv的rect的区别

    2024-04-04 01:46:02       33 阅读

  21. 0基础如何进入IT行业？

    2024-04-04 01:46:02       31 阅读

  24. 伯俊ERP对接打通金蝶云星空表头表体组合查询接口与销售出库新增接口

    2024-04-04 01:46:02       40 阅读

  25. os模块篇（十一）

    2024-04-04 01:46:02       32 阅读

  26. 借助ChatGPT写作：打造学术论文中的亮点与互动

    2024-04-04 01:46:02       45 阅读

  30. 零基础入门多媒体音频（6）-alsa(2)

    2024-04-04 01:46:02       34 阅读