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

1.顺序表的概述

1.1 顺序表的概念及结构

        在了解顺序表之前，我们要先知道线性表的概念，线性表，顾名思义，就是一个线性的且具有n个相同类型的数据元素的有限序列，常见的线性表有顺序表、链表、栈、队列、字符串等等。线性表的逻辑结构是线性的，也就是一条连续的直线，但它在物理结构上不一定是线性的，比如链表，你可以将它理解为串着很多个珠子的手串，每个珠子都是一个存储数据的节点，但这些珠子在内存中的存储不一定是连续的。

        而我们今天提到的顺序表，它则是逻辑结构和物理结构都是一致的，因为顺序表的底层结构是数组，而数组我们之前提过，它在内存中的存储是连续的。

1.2 顺序表的分类 

        顺序表可以分为静态顺序表和动态顺序表，接下来就让我们通过代码来看看这二者有何区别：

//静态顺序表
struct SeqList
{
  SLDataType a[N]; //定长数组
  int size;        //有效数据个数
};

//动态顺序表
struct SeqList
{
	SLDataType* arr; //存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
};

 从上面的代码我们可以看出，静态顺序表和动态顺序表的最大区别在于他们存储数据的底层结构，静态顺序表是一个定长数组，在存储数据时，我们不好把握这个定长数组的长度，如果给定的长度太小，就不够存放，给定的长度太大，又会造成空间浪费。而动态顺序表是一个动态数组（可以通过malloc或realloc动态申请一块连续空间），这样的好处是我们可以按需申请空间，既不会造成很大的空间浪费，也不会出现不够存放的情况。

那接下来就让我们一起来实现动态顺序表。

2.动态顺序表的实现

首先我们先在头文件中定义好动态顺序表的结构以及声明所需要的函数接口。

//头文件SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1  // scanf函数在vs中是不安全的
#include<stdio.h>
#include<stdlib.h>                 
#include<assert.h>



typedef int SLDataType; //这里是方便后续需要修改顺序表数据类型

//动态顺序表
typedef struct SeqList
{
	SLDataType* arr; //存储数据的底层结构
	int capacity;   //记录顺序表的空间大小
	int size;       //记录顺序表当前有效的数据个数
}SL;



//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(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 x);

接下来我们就需要在.c文件中将这些函数一一实现咯

//SeqList.c文件

#include"SeqList.h"   //首先要包含我们先前创建的头文件



//初始化   数组置空，有效数据个数和顺序表空间容量都置0
//这里的ps是我们创建好的顺序表的指针
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}


//销毁  释放内存，置空，有效数据个数和顺序表空间容量都置0
void SLDestroy(SL* ps) {
	if (ps->arr) {
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}


//判断顺序表当前是否需要扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//如果当前有效数据个数等于顺序表空间容量，则说明需要
	{   
        //三目操作符，如果容量为0，则返回4的初始容量，否则就扩容两倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        //创建一个临时变量来存放新申请的空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        //申请空间失败
		if (tmp == NULL) {
			perror("realloc error!");
			exit(1);
		}
		//扩容成功
		ps->arr = tmp;//新申请到的空间赋值给数组
		ps->capacity = newCapacity;//更新容量
	}
}

//打印顺序表
void SLPrint(SL* ps)
{    
    //遍历数组
	for (int i = 0;i < ps->size;i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//断言
	assert(ps != NULL);
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够，直接插入
	ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	//判断是否扩容
	SLCheckCapacity(ps);

	//旧数据往后挪动一位
	for (int i = ps->size;i > 0;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}


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


//尾删
void SLPopBack(SL* ps)
{
	//无数据
	assert(ps);
	assert(ps->size);
	//有数据
	ps->size--;
}


//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);

	//pos及之后的数据往后挪动一位，pos空出来
	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(ps->size);
	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 x)
{

	assert(ps);
	for (int i = 0;i < ps->size;i++)
	{
		if (ps->arr[i] == x) {
			return i;
		}
	}
	return -1;
}

3.动态顺序表功能测试

 新创建一个main.c文件，用于测试顺序表功能

//main.c文件

#include"SeqList.h"

int main()
{
	//创建一个顺序表
    SL sl;
    //初始化顺序表
    SLInit(&sl);
    //尾插2 3
    SLPushBack(&sl,2);
    SLPushBack(&sl,3);
    SLPushBack(&sl,4);
    //打印顺序表，此时应打印2 3 4
    SLPrint(&sl);

    //头插0 1
    SLPushFront(&sl,1);
    SLPushFront(&sl,0);
    //打印顺序表，此时应打印0 1 2 3 4
    SLPrint(&sl);

    //头删顺序表
    SLPopFront(&sl);
    //打印顺序表，此时应打印1 2 3 4
    SLPrint(&sl);

    //尾删顺序表
    SLPopBack(&sl);
    //打印顺序表，此时应打印1 2 3
    SLPrint(&sl);

    //在2前面插入0
    SLInsert(&sl,SLFind(&sl,2),0);
    //打印顺序表，此时应打印1 0 2 3
    SLPrint(&sl);

    //删掉0
    SLErase(&sl,SLFind(&sl,0));
    //打印顺序表，此时应打印1 2 3
    SLPrint(&sl);

    //销毁顺序表
    SLDestroy(&sl);
	return 0;
}

运行结果：

可以看到，打印的结果和我们预测的一致。

顺序表的实现就讲到这里了，有什么疑问可以在评论区提出，看到一定会回复。

有什么错误的地方欢迎指出。

如果你觉得这篇文章对你有帮助的话，麻烦动动小手点个赞~