从零开始构建【顺序表】：C语言实现与项目实战准备

---

前言：

对于C语言语法基础，已经更新完了，想必大家都想实现一个小项目，来巩固知识点和激励自己，那么接下来，我们可以试着做个通讯录项目。
在完成这个项目之前，我们还要了解数据结构中的顺序表，才可以完成通讯录项目。
这篇文章我们先来实现顺序表，下篇文章我们再进行通讯录项目的完成。

---

一、数据结构相关概念

考虑到大家可能都是未学习过数据结构，所以我会在对数据结构进行相对应的解释。

1.1、什么是数据结构？

数据结构是由“数据”和“结构”两词组合而来。
什么是数据？
常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据。
什么是结构？
当我们想要使用大量使用同⼀类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在⼀起，结构也可以理解为组织数据的方式。
比如：想要找到草原上名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来。

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么方式构成，以及数据元素之间呈现的结构。
总结：
1）能够存储数据（如顺序表、链表等结构）
2）存储的数据能够方便查找

1.2、为什么需要数据结构？

如图中所示，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。
最基础的数据结构：数组。

那我们就要思考：有了数组，为什么还要学习其他的数据结构？
假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：

求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是否要判断数组是否满了，满了还能继续插入吗）…

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。
结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现，所以就有了其它的数据结构。

二、顺序表

2.1、顺序表的概念及结构

线性表是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合。
对于逻辑结构和物理结构的理解：逻辑结构是"怎么看"，物理结构是"怎么存"。
对于顺序表，它再逻辑结构和物理结构上都是连续的。

2.2、顺序表分类

• 顺序表和数组的区别

  • 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

• 顺序表分类

  • 静态顺序表

  概念：使用定长数组存储元素
  
  静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

  • 动态顺序表

  
  优点在于可以根据使用者的情况进行扩容。

我们主要来进行动态顺序表的实现，动态只要会使用，静态的就很简单了。

2.3、动态顺序表的实现

首先，我们应有三个模块，分别用来实现不同的功能：

SeqList.h中代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//元素类型
typedef int SLDataType;//动态顺序表定义
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间容量
}SL;//顺序表操作//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入
void SLPushFront(SL* ps, SLDataType x);
//尾部插入
void SLPushBack(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);

SeqList.c中代码实现：

#include"SeqList.h"

顺序表的初始化

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

顺序表的销毁

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

顺序表的打印

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

扩容

#define INIT_CAPACITY 4 //初始容量
void SLCheckCapacity(SL* ps)
{assert(ps);//判断容量够不够int newcapacity = 0;if (ps->capacity == ps->size){newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->arr ,sizeof(SLDataType) * newcapacity);if (!tmp ){perror("realloc");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

头部插入

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 SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}

头部删除

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

尾部删除

void SLPopBack(SL* ps)
{assert(ps);//if (!ps->size)//	return;assert(ps->arr);ps->size--;
}

指定位置之前插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);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; i++){ps->arr[i - 1] = ps->arr[i];//ps->arr[size-2] = ps->arr[size-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;
}

test.c中主要是我们用于测试，用来判断代码实现正确与否，读者自行使用。

---

总结

本篇文章主要对于数据结构相关概念和顺序表进行了讲解，旨在让C语言完结者对数据结构有个初步的了解及运用顺序表完成后面通讯录项目。
谢谢学习至此！！！
下篇文章见。

专栏

C语言专栏