数据结构——顺序表接口实现(C语言)

骑猪看日落 2022-12-26 09:13 114阅读 0赞

### C语言实现顺序表的增删查改 ###

*  github代码下载
 *  一、概念及结构
 *  二、接口实现
 *   *  2.1 顺序表的两种存储方式与结构图
     *   *  2.1.1 顺序表的静态存储
         *  2.1.3 顺序表的动态存储
     *  2.2 顺序表初始化
     *  2.3 顺序表增容
     *  2.4 顺序表打印
     *  2.5 顺序表尾插
     *  2.6 顺序表尾删
     *  2.7 顺序表头插
     *  2.8 顺序表头删
     *  2.9 顺序表查找
     *  2.10 顺序表在任意位置插入
     *  2.11 顺序表删除任意位置的值
     *  2.12 顺序表销毁
 *  3. 工程化实现
 *   *  3.1 SeqList.h
     *  3.2 SeqList.c
     *  3.3 test.c

# github代码下载 #

代码下载：  
[https://github.com/Kyrie-leon/Data\_Structures/tree/main/SeqList][https_github.com_Kyrie-leon_Data_Structures_tree_main_SeqList]

# 一、概念及结构 #

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

> 顺序表可分为两类：
> 
>  *  静态顺序表：使用定长数组存储。
>  *  动态顺序表：使用动态开辟的数组存储。

# 二、接口实现 #

## 2.1 顺序表的两种存储方式与结构图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

### 2.1.1 顺序表的静态存储 ###

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

### 2.1.3 顺序表的动态存储 ###

typedef int SLDataTpye;
    
    //2.1.2 顺序表的动态存储
    typedef struct SeqList
    {
        
    	SLDataTpye * array;	//指向动态开辟的数组
    	size_t size;		//有效数据的个数
    	size_t capacity;	//容量空间的大小
    };

> typedef int SLDataTpye 代表顺序表数组的类型，使用这种方式方便后续对类型的更改

## 2.2 顺序表初始化 ##

该函数功能将顺序表初始化为空表

> 操作前提：SL为未初始化线性表  
> 操作结果：将SL初始化为空表

//顺序表初始化
    void SeqListInit(SeqList * psl)
    {
        
    	//开辟的大小随机给值
    	psl->array = (SLDataTpye *)malloc(sizeof(SLDataTpye) * 4);
    	if (psl->array == NULL)
    	{
        
    		printf("初始化失败\n");
    		exit(-1);
    	}
    
    	psl->size = 0;	//有效数据为0
    	psl->capacity = 4;	//容量空间大小为4
    }

## 2.3 顺序表增容 ##

该函数一方面可以检查空间是否满了，另一方面可以增容。

> 操作前提：顺序表空间满了，即 capacity==size，需要进行增容  
> 操作结果：顺序表空间扩大原来容量的二倍，即capacity\*=2

//2.3 顺序表增容
    //检查空间，如果满了，进行增容
    void CheckCapacity(SeqList * psl)
    {
        
    	//有效数据与容量空间相等代表空间满了，需要增容！
    	if (psl->size == psl->capacity)
    	{
        
    		//对顺序表容量扩大两倍
    		psl->capacity *= 2;
    		//使用realloc扩展空间
    		psl->array = (SLDataTpye *)realloc(psl->array, sizeof(SLDataTpye)*psl->capacity);
    
    		//判断下是否申请失败
    		if (psl->array == NULL)
    		{
        
    			printf("增容失败\n");
    			exit(-1);
    		}
    	}
    }

## 2.4 顺序表打印 ##

> 操作前提：顺序表存在  
> 操作结果：打印顺序表每个节点的元素值

//2.4 顺序表打印
    void SeqListPrint(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//依次遍历顺序表每个节点，并打印节点中的元素值
    	for (size_t i = 0; i < psl->size; ++i)
    	{
        
    		printf("psl->array[%d]=%d\n", i, psl->array[i]);
    	}
    
    }

## 2.5 顺序表尾插 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

//2.5 顺序表尾插
    void SeqListPushBack(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	psl->array[psl->size] = x;	//将数据x插入到线性表末尾
    	psl->size++;	//有效数据加1
    }

## 2.6 顺序表尾删 ##

数据表尾删只需要对size-1即可，不需要对末尾节点置零。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]

//2.6 顺序表尾删
    void SeqListPopBack(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//有效数据-1
    	psl->size--;
    }

## 2.7 顺序表头插 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]

//2.7 顺序表头插
    void SeqListPushFront(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	//头插从后往前拷贝
    	int end = psl->size - 1;	//指向最后一个节点
    	while(end >= 0)
    	{
        
    		psl->array[end + 1] = psl->array[end];	//节点向后移动一个位置
    		--end;
    	}
    
    	
    	psl->array[0] = x;	//插入元素x
    	psl->size++;	//有效数据+1
    
    }

## 2.8 顺序表头删 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]

//2.8 顺序表头删
    void SeqListPopFront(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    
    	size_t start = 0;	//指向第一个节点
    	while (start < psl->size-1)
    	{
        
    		psl->array[start] = psl->array[start+1];
    		++start;
    	}
    
    	psl->size--;	//有效数据-1
    }

## 2.9 顺序表查找 ##

![在这里插入图片描述][20201204161055504.png]

//2.9 顺序表查找
    int SeqListFind(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//从第一个节点开始查找，如果找到就返回该位置的值
    	size_t start = 0;
    	while (start < psl->size)
    	{
        
    		if (x == psl->array[start])
    		{
        
    			return start + 1;
    		}
    		start++;
    	}
    
    	//没有找到返回-1
    	return -1;
    }

## 2.10 顺序表在任意位置插入 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]

//2.10 顺序表在pos位置插入
    void SeqListInsert(SeqList * psl, size_t pos, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//判断位置的合法性
    	assert(pos <= psl->size);
    
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	//end指向最后一个位置
    	size_t end = psl->size - 1;
    	//将pos位置的节点分别向后移动一个位置
    	while (end >= pos - 1)
    	{
        
    		psl->array[end + 1] = psl->array[end];
    		--end;
    	}
    
    	psl->array[pos - 1] = x;	//将x插入到第pos个位置
    	psl->size++;	//有效数据+1
    
    }

## 2.11 顺序表删除任意位置的值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]

//2.11 顺序表删除pos位置的值
    void SeqListErase(SeqList * psl, size_t pos)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//判断位置的合法性，不能小于等于0并且大于size
    	assert(pos && pos < psl->size);
    	
    	size_t start = pos-1;	//指向要删除的位置
    	while (start < psl->size-1)
    	{
        
    		psl->array[start] = psl->array[start + 1];
    		++start;
    	}
    
    	psl->size--;	//有效数据-1
    }

## 2.12 顺序表销毁 ##

//2.12 顺序表销毁
    void SeqListDestory(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//销毁顺序表
    	free(psl->array);
    	psl->array = NULL;
    	psl->size = 0;
    	psl->capacity = 0;
    
    }

# 3. 工程化实现 #

创建三个文件：

*  SeqList.h 用于存放库函数头文件和函数声明等
 *  SeqList.c 用于实现顺序表的增删查改功能
 *  test.c 用于接口测试

## 3.1 SeqList.h ##

#ifndef _SEQLIST_H_
    #define _SEQLIST_H_
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    
    #define N 100
    typedef int SLDataTpye;
    
    2.1.1顺序表的静态存储
    //typedef struct SeqList
    //{
        
    //	SLDataTpye arr[N];	//定长数组
    //	size_t size;	    //有效数组的个数
    //}SL,SeqList;
    
    //2.1.2 顺序表的动态存储
    typedef struct SeqList
    {
        
    	SLDataTpye * array;	//指向动态开辟的数组
    	size_t size;		//有效数据的个数
    	size_t capacity;	//容量空间的大小
    }SL, SeqList;
    
    //顺序表基本增删查改接口功能函数声明
    
    
    //顺序表的初始化
    void SeqListInit(SeqList * psl);
    //顺序表销毁
    void SeqListDestory(SeqList * psl);
    //顺序表打印
    void SeqListPrint(SeqList * psl);
    //检查空间，如果满了，进行增容
    void CheckCapacity(SeqList * psl);
    
    
    //顺序表尾插
    void SeqListPushBack(SeqList * psl,SLDataTpye x);
    //顺序表尾删
    void SeqListPopBack(SeqList * psl);
    //顺序表头插
    void SeqListPushFront(SeqList * psl, SLDataTpye x);
    //顺序表头删
    void SeqListPopFront(SeqList * psl);
    
    
    //顺序表查找
    int SeqListFind(SeqList * psl, SLDataTpye x);
    //顺序表在pos位置插入
    void SeqListInsert(SeqList * psl, size_t pos, SLDataTpye x);
    //顺序表删除pos位置的值
    void SeqListErase(SeqList * psl, size_t pos);
    
    #endif

## 3.2 SeqList.c ##

#include "SeqList.h"
    
    
    //2.2 顺序表初始化
    void SeqListInit(SeqList * psl)
    {
        
    	//开辟的大小随机给值
    	psl->array = (SLDataTpye *)malloc(sizeof(SLDataTpye) * 4);
    	if (psl->array == NULL)
    	{
        
    		printf("初始化失败\n");
    		exit(-1);
    	}
    
    	psl->size = 0;	//有效数据为0
    	psl->capacity = 4;	//容量空间大小为4
    }
    
    //2.3 顺序表增容
    //检查空间，如果满了，进行增容
    void CheckCapacity(SeqList * psl)
    {
        
    	//有效数据与容量空间相等代表空间满了，需要增容！
    	if (psl->size == psl->capacity)
    	{
        
    		//对顺序表容量扩大两倍
    		psl->capacity *= 2;
    		//使用realloc扩展空间
    		psl->array = (SLDataTpye *)realloc(psl->array, sizeof(SLDataTpye)*psl->capacity);
    
    		//判断下是否申请失败
    		if (psl->array == NULL)
    		{
        
    			printf("增容失败\n");
    			exit(-1);
    		}
    	}
    }
    
    //2.4 顺序表打印
    void SeqListPrint(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//依次遍历顺序表每个节点，并打印节点中的元素值
    	for (size_t i = 0; i < psl->size; ++i)
    	{
        
    		printf("psl->array[%d]=%d\n", i, psl->array[i]);
    	}
    
    }
    
    //2.5 顺序表尾插
    void SeqListPushBack(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	psl->array[psl->size] = x;	//将数据x插入到线性表末尾
    	psl->size++;	//有效数据加1
    }
    
    //2.6 顺序表尾删
    void SeqListPopBack(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//有效数据-1
    	psl->size--;
    }
    
    //2.7 顺序表头插
    void SeqListPushFront(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	//头插从后往前拷贝
    	int end = psl->size - 1;	//指向最后一个节点
    	while(end >= 0)
    	{
        
    		psl->array[end + 1] = psl->array[end];	//节点向后移动一个位置
    		--end;
    	}
    
    	
    	psl->array[0] = x;	//插入元素x
    	psl->size++;	//有效数据+1
    
    }
    
    //2.8 顺序表头删
    void SeqListPopFront(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    
    	size_t start = 0;	//指向第一个节点
    	while (start < psl->size-1)
    	{
        
    		psl->array[start] = psl->array[start+1];
    		++start;
    	}
    
    	psl->size--;	//有效数据-1
    }
    
    //2.9 顺序表查找
    int SeqListFind(SeqList * psl, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//从第一个节点开始查找，如果找到就返回该位置的值
    	size_t start = 0;
    	while (start < psl->size)
    	{
        
    		if (x == psl->array[start])
    		{
        
    			return start + 1;
    		}
    		start++;
    	}
    
    	//没有找到返回-1
    	return -1;
    }
    
    
    //2.10 顺序表在pos位置插入
    void SeqListInsert(SeqList * psl, size_t pos, SLDataTpye x)
    {
        
    	//判断指针合法性
    	assert(psl);
    	//检查空间，如果满了，进行增容
    	CheckCapacity(psl);
    
    	//end指向最后一个位置
    	size_t end = psl->size - 1;
    	//将pos位置的节点分别向后移动一个位置
    	while (end >= pos - 1)
    	{
        
    		psl->array[end + 1] = psl->array[end];
    		--end;
    	}
    
    	psl->array[pos - 1] = x;	//将x插入到第pos个位置
    	psl->size++;	//有效数据+1
    
    }
    
    
    //2.11 顺序表删除pos位置的值
    void SeqListErase(SeqList * psl, size_t pos)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	size_t start = pos-1;	//指向要删除的位置
    	while (start < psl->size-1)
    	{
        
    		psl->array[start] = psl->array[start + 1];
    		++start;
    	}
    
    	psl->size--;	//有效数据-1
    }
    
    //2.12 顺序表销毁
    void SeqListDestory(SeqList * psl)
    {
        
    	//判断指针合法性
    	assert(psl);
    
    	//销毁顺序表
    	free(psl->array);
    	psl->array = NULL;
    	psl->size = 0;
    	psl->capacity = 0;
    
    }

## 3.3 test.c ##

#include "SeqList.h"
    
    //测试头尾插入删除
    void TestSeqList1()
    {
        
    	//首先定义一个顺序表
    	SeqList s;
    	//顺序表初始化接口测试
    	SeqListInit(&s);
    	//顺序表尾插尾删接口测试
    	SeqListPushBack(&s, 1);
    	SeqListPushBack(&s, 2);
    	SeqListPushBack(&s, 3);
    	SeqListPushBack(&s, 4);
    	SeqListPushBack(&s, 5);
    	SeqListPushBack(&s, 6);
    	SeqListPushBack(&s, 7);
    	SeqListPushBack(&s, 8);
    	SeqListPopBack(&s);
    	SeqListPrint(&s);
    
    	//头插头删接口测试
    	//SeqListPushFront(&s, -1);
    	//SeqListPrint(&s);
    	SeqListPopFront(&s);
    	SeqListPrint(&s);
    
    	//查找接口测试
    	printf("%d\n",SeqListFind(&s, 4));
    	//任意位置插入接口测试
    	SeqListInsert(&s, 3, 30);
    	SeqListPrint(&s);
    
    	//任意位置删除
    	SeqListErase(&s, 3);
    	SeqListPrint(&s);
    
    	//顺序表销毁
    	SeqListDestory(&s);
    
    
    }
    
    
    int main()
    {
        
    	TestSeqList1();
    
    	return 0;
    }

[https_github.com_Kyrie-leon_Data_Structures_tree_main_SeqList]: https://github.com/Kyrie-leon/Data_Structures/tree/main/SeqList
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221120/905bc82b29cb4dc39204106f60486296.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221120/ea6fa2439a934676be1a0ed192624846.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]: /images/20221120/d56553cc91f148adbf242def1c33e01e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]: /images/20221120/2e152e0fe78f4e4f82f2dd02a0ec1237.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]: /images/20221120/8464907237924f76affe30c6a1adb106.png
[20201204161055504.png]: /images/20221120/acfce3f236bc40b2858bdfeade19d440.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]: /images/20221120/69935ba701c841068d2a7372fb384bb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]: /images/20221120/42d8b6a57aba4b54af343dd395cd1961.png