怎么用C语言数组实现顺序表

这篇文章主要讲解了“怎么用C语言数组实现顺序表”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么用C语言数组实现顺序表”吧！

线性表和顺序表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列，这是我们广泛使用的数据结构。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

常见的线性表：顺序表、链表、栈、队列、字符串…

顺序表

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

一般可以分为：

• 静态顺序表：使用定长数组来存储元素

• 动态顺序表：使用动态开辟的数组来储存元素

静态顺序表

//定义静态数组的大小，方便后续修改#define MAX_SIZE 50//重命名数组的数据类型，方便后续修改typedef int SLDataType;//定义结构体//成员变量为数组和记录当前数据个数的变量//重命名结构体数据类型，方便书写typedef struct SeqList {SLDataType arr[MAX_SIZE];int size;}SL;//-----------------------------------------------------------------------------//以下是一些常见的接口的声明//顺序表初始化//利用结构体类型创建一个静态顺序表变量后，可以对其进行初始化void SLInit(SL* psl);//打印顺序表//把顺序表的值按照先后顺序打印出来void SLPrint(SL* psl);//检查顺序表是否已满//每次进行加入数据的操作的时候需要先检查是否已经满了，如果满了就不能够插入了void SLCheck(SL* psl);//顺序表的尾插//在顺序表的尾部在插入一个元素//由于是数组加入数据很方便，直接使用数组下标就可以访问到void SLPushBack(SL* psl, SLDataType data);//顺序表的尾删//删除顺序表尾部的数据void  SLPopBack(SL* psl);//顺序表的头插//在顺序表的开头加入一个数据void SLPushFront(SL* psl, SLDataType data);//顺序表的头删//把顺序表第一位数据删除void SLPopFront(SL* psl);//顺序表查找某个数据//查找顺序表中是否存在某个数据，如果有就返回对应的下标//如果找不到就返回-1int SLFind(SL* psl, SLDataType x);//顺序表在pos位置插入x//在指定下标位置插入数据x，原来x位置的数据以及后面的数据往后移动void SLInsert(SL* psl, size_t pos, SLDataType x);//顺序表删除在pos位置的数据void SLErase(SL* psl, size_t pos);//顺序表某一位置数据的修改void SLModify(SL* psl, size_t pos, SLDataType x);

以下是这些接口的具体实现

//顺序表初始化void SLInit(SL* psl) {psl->arr[0] = 0;//此处只能初始化一个元素psl->size = 0;}//打印顺序表void SLPrint(SL* psl) {int i = 0;if (psl->size) {for (i = 0; i < psl->size; i++) {//输出格式，记得根据SLDataTyped的类型来修改printf("%d ", psl->arr[i]);}printf("\n");}else {printf("Null\n");}}//顺序表的尾插void SLPushBack(SL* psl, SLDataType data) {//插入数据要先检查空间是否已满//实现方法一不够好//实现方法二，简单明了assert(psl->size != MAX_SIZE);psl->arr[psl->size] = data;psl->size++;}//顺序表的尾删void  SLPopBack(SL* psl) {//判断是否还有元素可以删除assert(psl->size);psl->size--;}//顺序表的头插void SLPushFront(SL* psl, SLDataType data) {assert(psl->size != MAX_SIZE);//src用来后移数据int src = psl->size;while (src >= 1) {psl->arr[src] = psl->arr[src - 1];src--;}psl->arr[src] = data;psl->size++;}//顺序表的头删void SLPopFront(SL* psl) {//判断是否还有数据可以删除assert(psl->size);int src = 0;while (src < psl->size - 1) {psl->arr[src] = psl->arr[src + 1];src++;}psl->size--;}//顺序表查找某个数据int SLFind(SL* psl, SLDataType x) {int i = 0;for (i = 0; i < psl->size; i++) {if (psl->arr[i] == x) {//找到了就返回该数据在顺序表中的位置return  i;}}//找不到就返回-1return -1;}//顺序表在pos位置插入xvoid SLInsert(SL* psl, size_t pos, SLDataType x) {assert(psl->size < MAX_SIZE);assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的时候，相当于头插，尾插int end = psl->size;while (end > pos) {psl->arr[end] = psl->arr[end - 1];end--;}psl->arr[pos] = x;psl->size++;}//顺序表删除在pos位置的数据void SLErase(SL* psl, size_t pos) {assert(psl->size);assert(pos >= 0 && pos < psl->size);int start = pos + 1;while (start < psl->size) {psl->arr[start - 1] = psl->arr[start];start++;}psl->size--;}//顺序表某一位置数据的修改void SLModify(SL* psl, size_t pos, SLDataType x) {assert(psl->size);assert(pos >= 0 && pos < psl->size);psl->arr[pos] = x;}

上面代码的测试，我放在了gitee上，需要的小伙伴可以参考一下

动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

//重命名SL的数据类型，方便后续修改typedef int SLDataType;//定义结构体//成员变量为指向动态顺序表的指针，数据的个数，顺序表的容量//capacity用来管理数组的总大小，如果size与capacity相等了，就表示数组已经满了需要扩容//重定义结构体类型名称，方便操作typedef struct SeqList {SLDataType* p;int size;int capacity;}SL;//----------------------------------------------------------------------//一下是一些常用的接口，与静态顺序表差不多//SL初始化void SLInit(SL* ps);//SL空间检查//如若size与capacity相等表示数组已经满了，需要扩容void SLCheckCapacity(SL* ps);//SL打印void SLPrint(SL* ps);//SL销毁//因为数组是动态开辟的，所以在最后不使用的数组的时候要释放空间void SLDestory(SL* ps);//SL尾插void SLPushBack(SL* ps,SLDataType x);//SL尾删void SLPopBack(SL* ps);//SL头插void SLPushFront(SL* ps, SLDataType x);//SL头删void SLPopFront(SL* ps);//SL查找某个数据//如果能找到，返回该数据在顺序表中下标int SLFind(SL* ps, SLDataType x);//SL在pos位置插入xvoid SLInsert(SL* ps, size_t pos, SLDataType x);//SL删除pos位置的值void SLErase(SL* ps, size_t pos);//SL修改某一位置的数据void SLModity(SL* ps, size_t pos, SLDataType x);

以下是具体的实现

//动态顺序表的实现#include"DynamicSeqList.h"//SL初始化void SLInit(SL* ps) {ps->p = NULL;ps->capacity = 0;ps->size = 0;}//SL空间检查void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType));if (tmp == NULL) {printf("realloc fail\n");exit(-1);}ps->p = tmp;}}//SL打印void SLPrint(SL* ps) {if (ps->size == 0) {printf("顺序表为空\n");}else {int i = 0;for (i = 0; i < ps->size; i++) {//打印格式记得根据SLDataType的类型来修改printf("%d ", ps->p[i]);}printf("\n");}}//SL销毁//这里并没有完全销毁结构体s，只是把成员变量都赋值为0void SLDestory(SL* ps) {free(ps->p);ps->p = NULL;ps->size = ps->capacity = 0;}//SL尾插void SLPushBack(SL* ps, SLDataType x) {SLCheckCapacity(ps);ps->p[ps->size] = x;ps->size++;}//SL尾删void SLPopBack(SL* ps) {//删除数据需要判断一下顺序表是否为空assert(ps->size > 0);ps->size--;}//SL头插void SLPushFront(SL* ps, SLDataType x) {SLCheckCapacity(ps);int end = ps->size;while (end > 0) {ps->p[end] = ps->p[end - 1];end--;}ps->p[end] = x;ps->size++;}//SL头删void SLPopFront(SL* ps) {//删除数据需要判断一下顺序表是否为空assert(ps->size > 0);int start = 0;while (start < ps->size - 1) {ps->p[start] = ps->p[start + 1];start++;}ps->size--;}//SL查找某个数据int  SLFind(SL* ps, SLDataType x) {//需要判断顺序表是否为空，可以用assert，也可以用if判断assert(ps->size);int i = 0;for (i = 0; i < ps->size; i++) {if (x == ps->p[i]) {return i;}}return -1;}//SL在pos位置插入x//当pos为0或者pos为size时，相当于头插、尾插void SLInsert(SL* ps, size_t pos, SLDataType x) {SLCheckCapacity(ps);assert(pos >= 0 && pos <= ps->size);int end = ps->size;while (end > pos) {ps->p[end] = ps->p[end - 1];end--;}ps->p[end] = x;ps->size++;}//SL删除pos位置的值void SLErase(SL* ps, size_t pos) {//判断要删除的位置是否在size之内assert(pos >= 0 && pos < ps->size);int start = pos + 1;while (start < ps->size) {ps->p[start - 1] = ps->p[start];start++;}ps->size--;}//SL修改某一位置的数据void SLModity(SL* ps, size_t pos, SLDataType x) {//判断要修改的位置是否在size之内assert(pos >= 0 && pos < ps->size);ps->p[pos] = x;}

感谢各位的阅读，以上就是“怎么用C语言数组实现顺序表”的内容了，经过本文的学习后，相信大家对怎么用C语言数组实现顺序表这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！