数据结构——顺序表（C语言）

目录

一、顺序表概念

二、顺序表分类 

        1.静态顺序表

        2.动态顺序表

三、顺序表的实现 

        1.顺序表的结构体定义

        2. 顺序表初始化

        3.顺序表销毁

        4.顺序表的检验

        5.顺序表打印

        6.顺序表扩容

        7.顺序表尾插与头插

        8.尾删与头删

        9.在pos处插入数据

        10.在pos处删除数据

        11.查找数据

四、全部文件及测试结果

---

一、顺序表概念

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

• 顺序表：可动态增长的数组，要求数据是连续存储的

二、顺序表分类 

        1.静态顺序表

        概念：使⽤定⻓数组存储元素

        2.动态顺序表

        使用动态开辟的数组存储元素

        动态顺序表可根据我们的需要分配空间大小

        size 表示当前顺序表中已存放的数据个数

        capacity 表示顺序表总共能够存放的数据个数

        我们现在是明白了动态顺序表和动态，那我们在用代码实现顺序表时会用那种呢？相信大家此时都已经有了答案，答案很显然是动态顺序表。因为动态顺序表比静态顺序表更加的灵活，不会那么死板，好话不多说，咱们一起来实现吧！

三、顺序表的实现 

        1.顺序表的结构体定义

        这里说明一下：数据结构这方面主要是：数组、指针、结构体这方面内容，因此数据结构可以让我们更好的理解以上内容。

        我们实现顺序表一共会用两个源文件和一个头文件，具体为什么，扫雷里说过可自行查阅。

typedef int seqlist;//大家可想一想把int 命名成seqlist的好处
typedef struct Seqlist
{seqlist* a;int  size;//有效数据个数int capacity;//总容量
}sl;//结构体命名

        2. 顺序表初始化

        当我们拥有了一个顺序表我们必然要对其初始化。

void SLInit(SL* ps)
{ps->a = NULL;//初始化把指针置为空ps->capacity = ps->size = 0;//元素个数均为零
}

        3.顺序表销毁

        既然把顺序表初始化了，必然要对其销毁

void SLDestroy(SL* ps)
{free(ps->a);//顺序表在后续会使用内存函数需free释放ps->a = NULL;ps->capacity = ps->size = 0;
}

        4.顺序表的检验

        记住写出一个函数就要对其进行检验。

void test1()
{void SLInit(SL * ps);void SLDestroy(SL * ps);
}

        当我们写出此代码时会报错，这是为什么呢？答案是test文件中只包含了头文件的，没包含源文件的（源文件相互包含会报错），这时我们添加以下代码即可：

SL ps;

        这个时候我们进行调试即可。

        5.顺序表打印

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

        6.顺序表扩容

        众所周知顺序表有这四大功能：增删查改，要进行第一个功能便要对顺序表经行扩容。

void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size){int newcapacity = ps->capacity > 0 ? 2 * ps->capacity : 4;//这里使用了三目操作符//定义一个变量来接收，出第一次外每次扩容二倍//为什么是二倍这里不过多推理，可自行了解SL* p = (SL *)realloc(ps->a, newcapacity*sizeof(seqlist));if (p == NULL){printf("扩容失败\n");exit(1);}ps->a = p;ps->capacity = newcapacity;}
}

        大家可自行对其检验，这里不再进行。

        7.顺序表尾插与头插

        接下来实现顺序表增这个功能：

        尾插：

void SLPushBack(SL* ps, seqlist x)
{SLCheckCapacity(ps);//检验元素是否满ps->a[ps->size++] = x;//也可采取以下这种//ps->a[pa->size]=x;   //ps->size++;
}

        头插：

void SLPushFront(SL* ps, seqlist x)
{SLCheckCapacity(ps);//检验元素是否满for (int i = ps->size-1; i >0; i--){ps->a[i+1] = ps->a[i];}ps->size++;ps->a[0] = x;
}

        8.尾删与头删

        尾删：

void SLPopBack(SL* ps)
{assert(ps);ps->size--;
}

        头删：

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

        9.在pos处插入数据

void SLInsert(SL* ps, int pos, seqlist x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size-1; i >= pos; i--){ps->a[i+1] = ps->a[i];}ps->a[pos] = x;ps->size++;
}

        10.在pos处删除数据

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

        11.查找数据

int SLFind(SL* ps, seqlist x)
{assert(ps);for (int i = 0; i < ps->size - 1; i++){if (ps->a[i] == x){printf("找到了，下标为: %d \n", i + 1);return i;}}printf("没找到\n");return -1;
}

四、全部文件及测试结果

        seqlist.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int seqlist;//大家可想一想把int 命名成seqlist的好处
typedef struct Seqlist
{seqlist* a;int  size;//有效数据个数int capacity;//总容量
}SL;
void SLInit(SL* ps);//顺序表初始化
void SLDestroy(SL* ps);//顺序表销毁
void SLPrint(SL* ps);//顺序表打印
void SLCheckCapacity(SL* ps);//顺序表扩容
void SLPushBack(SL* ps, seqlist x);//尾插
void SLPopBack(SL* ps);//尾删
void SLPushFront(SL* ps, seqlist x);//头插
void SLPopFront(SL* ps);//头删
void SLInsert(SL* ps, int pos, seqlist x);//特定位置插入数据
void SLErase(SL* ps, int pos); //特定位置删除数据
int SLFind(SL* ps, seqlist x);//查找数据

        seqlist.c：

#include"seqlist.h"
void SLInit(SL* ps)
{ps->a = NULL;//初始化把指针置为空ps->capacity = ps->size = 0;//元素个数均为零
}
void SLDestroy(SL* ps)
{free(ps->a);//顺序表在后续会使用内存函数需free释放ps->a = NULL;ps->capacity = ps->size = 0;
}
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d", ps->a[i]);}peintf("\n");
}
void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size){int newcapacity = ps->capacity > 0 ? 2 * ps->capacity : 4;//这里使用了三目操作符//定义一个变量来接收，出第一次外每次扩容二倍//为什么是二倍这里不过多推理，可自行了解SL* p = (SL *)realloc(ps->a, newcapacity*sizeof(seqlist));if (p == NULL){printf("扩容失败\n");exit(1);}ps->a = p;ps->capacity = newcapacity;}
}
void SLPushBack(SL* ps, seqlist x)
{SLCheckCapacity(ps);//检验元素是否满ps->a[ps->size++] = x;//也可采取以下这种//ps->a[pa->size]=x;   //ps->size++;
}
void SLPushFront(SL* ps, seqlist x)
{SLCheckCapacity(ps);//检验元素是否满for (int i = ps->size-1; i >0; i--){ps->a[i+1] = ps->a[i];}ps->size++;ps->a[0] = x;
}
void SLPopBack(SL* ps)
{assert(ps);ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps);for (int i =  1; i <ps->size; i--){ps->a[i-1] = ps->a[i];}ps->size--;
}
void SLInsert(SL* ps, int pos, seqlist x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size-1; i >= pos; i--){ps->a[i+1] = ps->a[i];}ps->a[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)
{assert(pos >= 0 && pos < ps->size && ps);for (int i = pos+1; i < ps->size-1; i++){ps->a[i-1] = ps->a[i];}ps->size--;
}
int SLFind(SL* ps, seqlist x)
{assert(ps);for (int i = 0; i < ps->size - 1; i++){if (ps->a[i] == x){printf("找到了，下标为: %d \n", i + 1);return i;}}printf("没找到\n");return -1;
}

        test.c：

#include"seqlist.h"
void menu()
{printf("***********************\n");printf("**1.尾插     2.尾删****\n");printf("**3.头插     4.头删****\n");printf("**5.固定插入 6.固定删除\n");printf("**7.查找     0.删除顺序表\n");printf("**0.销毁并退出*********\n");
}
int main()
{SL ps;SeqListInit(&ps);SeqListPushBack(&ps, 4);SeqListPushBack(&ps, 5);SeqListPushBack(&ps, 6);SeqListPushFront(&ps, 3);SeqListPushFront(&ps, 2);SeqListPushFront(&ps, 1);SeqListPrint(&ps);//顺序表初始化int input;do {menu();printf("please input your choice:");scanf("%d", &input);Seqlist x;int pos;int find;int getfind;switch (input)//顺序表输入测试{case 0:SeqListDestroy(&ps);break;case 1:scanf("%d", &x);SeqListPushBack(&ps, x);SeqListPrint(&ps);break;case 2:SeqListPopBack(&ps);SeqListPrint(&ps);break;case 3:scanf("%d", &x);SeqListPushFront(&ps, x);SeqListPrint(&ps);break;case 4:SeqListPopFront(&ps);SeqListPrint(&ps);break;case 5:scanf("%d", &pos);scanf("%d", &x);SeqListInsert(&ps, pos, x);SeqListPrint(&ps);break;case 6:scanf("%d", &pos);SeqListErase(&ps, pos);SeqListPrint(&ps);break;case 7:scanf("%d", &find);getfind = SeqListFind(&ps, find);printf("%d", getfind);printf("\n");break;default:printf("error input\n");break;}} while (input);return 0;
}

        完！