《数据结构：C语言实现顺序表》

文章目录

- 一、顺序表
- - - 1、静态顺序表
    - 2、动态顺序表
- 二、动态顺序表实现
- - - 1、创建自定义类型
    - 2、完成顺序表的创建，测试功能需求
    - 3、完成顺序表的初始化和销毁功能
    - 4、顺序表插入数据和打印数据
    - 5、删除数据
- 三、顺序表完成最终的代码
- - - test.c文件中的代码：用来测试程序的可行性
    - sequence_list.h头文件:
    - sequence_list.c文件：

一、顺序表

顺序表是线性表的一种，是一种数据结构，用来存放n个具有相同特性的数据元素的有限序列。
顺序表的存储形式的逻辑结构是连续的，物理结构也是连续的底层是数组来完成数据的存放。

1、静态顺序表

静态顺序表的空间是固定的，数组的大小是固定的，存放数据的个数有限，所以给静态数据设置空间会往大了给，给小了不够用，但给大了会产生空间浪费。

2、动态顺序表

动态顺序表根据内存空间需要调整空间大小，很大程度上减少了空间的浪费，所以实现顺序表用动态顺序顺序的形式实现。

二、动态顺序表实现

实现动态顺序表将创建三个文件来完成：

1、squence_list.h 的头文件，声明函数，定义
2、sequence_list.c的源文件实现函数的功能
3、test.c 的源文件用来测试顺序表的功能

在这里插入图片描述

1、创建自定义类型

创建完成就一步步实现
1、在squence_list.h的文件，首先要创建顺序表所要用到的结构体自定义类型

#pragma once
//sequence_list.h文件中#include<stdio.h>//顺序表存放数据的类型
typedef int SLDATETYPE;//顺序表的类型创建
typedef struct SequenceList
{//存放指定类型数据的指针SLDATETYPE* a;//存放数据的有效个数int count;//属性表空间大小int size;
}SL;//重命名一个简单的名字

2、完成顺序表的创建，测试功能需求

2、在test.c文件中创建一个顺序表，然后在看需要什么功能，再来实现个个对应功能的函数。

//在test.c文件中//1、首先包含头文件
#include"sequence_list.h"//3、测试函数test1的任务
void test1()
{//4、创建一个顺序表SL s;//5、顺序表没有初始化需要初始化SLInitialize(&s);//传址调用//6、最后不使用时要完成销毁SLDestroy(&s);
}//2、创建主函数
int main()
{//调用测试函数test1();return 0;
}

3、完成顺序表的初始化和销毁功能

3、根据需求需要对squence_list.h和squence_list.c的头文件完成对应的函数声明和实现

(1)顺序表初始化
(2)顺序表销毁

#pragma once
//sequence_list.h文件中
//包含检查头文件
#include<assert.h>//动态内存开辟函数对应的头文件
#include<stdlib.h>//顺序表的初始化
void SLInitialize(SL* ps);//顺序表的销毁
void SLDestroy(SL* ps);

//在squence_list.c文件中//包含头文件
#include"sequence_list.h"//顺序表的初始化
void SLInitialize(SL* ps)
{//对顺序表检查//要添加对应的<assert.h>头文件//在sequence_list.h头文件包含就可以了assert(ps != NULL);ps->a = NULL;ps->count = ps->size = 0;
}//顺序表的销毁
void SLDestroy(SL* ps)
{assert(ps != NULL);//动态内存开辟的空间要free//动态内存开辟函数要添加头文件<stdlib.h>free(ps->a);ps->a = NULL;ps->count = ps->size = 0;
}

4、顺序表插入数据和打印数据

4、继续对test.c文件进行测试
需要的功能是添加数据的函数
添加数据的方式有三种:

(1)末尾添加
(2)头部添加
(3)任意位置添加

需要观察数据,使用打印函数实现

//在test.c文件中//1、首先包含头文件
#include"sequence_list.h"//3、测试函数test1的任务
void test1()
{//4、创建一个顺序表SL s;//5、顺序表没有初始化需要初始化SLInitialize(&s);//传址调用//添加数据//7、尾部添加数据SLPutEnd(&s, 1);SLPutEnd(&s, 2);SLPutEnd(&s, 3);//8、打印数据SLPrint(&s);//9、头部插入SLPutFirst(&s, 5);SLPutFirst(&s, 4);SLPrint(&s);//10、任意位置前插入数据SLInsert(&s, 0, 3);SLInsert(&s, s.count-1, 6);SLInsert(&s, 1, 6);SLPrint(&s);//6、最后不使用时要完成销毁SLDestroy(&s);
}//2、创建主函数
int main()
{//调用测试函数test1();return 0;
}

//sequence_list.h文件中//判断空间是否足够
void SLEnough(SL* ps)
{//空间满了申请空间if (ps->count == ps->size){int n;n = (ps->size == 0 ? 4 : ps->size * 2);SLDATETYPE* tmp = (SLDATETYPE*)realloc(ps->a,n * sizeof(SLDATETYPE));if (tmp == NULL){//开辟失败退出exit(1);}ps->a = tmp;tmp = NULL;ps->size = n;}
}


//顺序表末尾放置数据
void SLPutEnd(SL* ps, SLDATETYPE x)
{assert(ps != NULL);//判断空间是否足够容纳数据SLEnough(ps);ps->a[ps->count++] = x;
}//打印顺序表中的数据
void SLPrint(SL* ps)
{assert(ps != NULL);int i = 0;for (i = 0; i < ps->count; i++){printf("%d", ps->a[i]);}printf("\n");
}//顺序表头部插入数据
void SLPutFirst(SL* ps, SLDATETYPE x)
{assert(ps != NULL);SLEnough(ps);for (int i = ps->count; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->count++;
}//顺序表任意位置前插入数据
void SLInsert(SL* ps, int pos, SLDATETYPE x)
{assert(ps != NULL);assert(pos >= 0 && pos <= ps->count);SLEnough(ps);for (int i = ps->count; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->count++;
}

5、删除数据

(1)尾部删除
(2)头部删除
(3)任意位置删除
(4)寻找对应数据下标

三、顺序表完成最终的代码

test.c文件中的代码：用来测试程序的可行性

//在test.c文件中//1、首先包含头文件
#include"sequence_list.h"//3、测试函数test1的任务
void test1()
{//4、创建一个顺序表SL s;//5、顺序表没有初始化需要初始化SLInitialize(&s);//传址调用//添加数据//7、尾部添加数据SLPutEnd(&s, 1);SLPutEnd(&s, 2);SLPutEnd(&s, 3);//8、打印数据//SLPrint(&s);//9、头部插入SLPutFirst(&s, 4);//SLPrint(&s);//10、任意位置前插入数据SLInsert(&s, 0, 5);SLInsert(&s, 0, 6);SLPrint(&s);//11、尾部删除数据SLDeleteEnd(&s);//l2、头部删除数据SLDeleteFirst(&s);//13、任意位置删除数据SLDelete(&s, 0);SLPrint(&s);//14、查找数据对应下标int ret=SLFind(&s, 6);if (ret >= 0){printf("找到了,下标为%d\n",ret);}elseprintf("没有找到");//6、最后不使用时要完成销毁SLDestroy(&s);
}//2、创建主函数
int main()
{//调用测试函数test1();return 0;
}

sequence_list.h头文件:

#pragma once
//sequence_list.h文件中#include<stdio.h>//包含检查头文件
#include<assert.h>//动态内存开辟函数对应的头文件
#include<stdlib.h>//顺序表存放数据的类型
typedef int SLDATETYPE;//顺序表的类型创建
typedef struct SequenceList
{//存放指定类型数据的指针SLDATETYPE* a;//存放数据的有效个数int count;//属性表空间大小int size;
}SL;//重命名一个简单的名字//顺序表的初始化
void SLInitialize(SL* ps);//顺序表的销毁
void SLDestroy(SL* ps);//判断空间是否足够
void SLEnough(SL* ps);//顺序表末尾放置数据
void SLPutEnd(SL* ps, SLDATETYPE x);//打印顺序表中的数据
void SLPrint(SL* ps);//顺序表头部插入数据
void SLPutFirst(SL* ps, SLDATETYPE x);//顺序表任意位置前插入数据
void SLInsert(SL* ps, int pos, SLDATETYPE x);//顺序表尾删
void SLDeleteEnd(SL* ps);//顺序表头删
void SLDeleteFirst(SL* ps);//顺序表任意位置删除数据
void SLDelete(SL* ps, int pos);//顺序表中寻找对应数据下标
int SLFind(SL* ps, SLDATETYPE x);

sequence_list.c文件：

#define _CRT_SECURE_NO_WARNINGS 1//在squence_list.c文件中//包含头文件
#include"sequence_list.h"//顺序表的初始化
void SLInitialize(SL* ps)
{//对顺序表检查//要添加对应的<assert.h>头文件//在sequence_list.h头文件包含就可以了assert(ps != NULL);ps->a = NULL;ps->count = ps->size = 0;
}//顺序表的销毁
void SLDestroy(SL* ps)
{assert(ps != NULL);//动态内存开辟的空间要free//动态内存开辟函数要添加头文件<stdlib.h>free(ps->a);ps->a = NULL;ps->count = ps->size = 0;
}//判断空间是否足够
void SLEnough(SL* ps)
{//空间满了申请空间if (ps->count == ps->size){int n;n = (ps->size == 0 ? 4 : ps->size * 2);SLDATETYPE* tmp = (SLDATETYPE*)realloc(ps->a,n * sizeof(SLDATETYPE));if (tmp == NULL){//开辟失败退出exit(1);}ps->a = tmp;tmp = NULL;ps->size = n;}
}//顺序表末尾放置数据
void SLPutEnd(SL* ps, SLDATETYPE x)
{assert(ps != NULL);//判断空间是否足够容纳数据SLEnough(ps);ps->a[ps->count++] = x;
}//打印顺序表中的数据
void SLPrint(SL* ps)
{assert(ps != NULL);int i = 0;for (i = 0; i < ps->count; i++){printf("%d", ps->a[i]);}printf("\n");
}//顺序表头部插入数据
void SLPutFirst(SL* ps, SLDATETYPE x)
{assert(ps != NULL);SLEnough(ps);for (int i = ps->count; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->count++;
}//顺序表任意位置前插入数据
void SLInsert(SL* ps, int pos, SLDATETYPE x)
{assert(ps != NULL);assert(pos >= 0 && pos <= ps->count);SLEnough(ps);for (int i = ps->count; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->count++;
}//顺序表尾删
void SLDeleteEnd(SL* ps)
{assert(ps != NULL);if (ps->count == 0){printf("数据已经删完了\n");}else{ps->count--;printf("删除成功\n");}
}//顺序表头删
void SLDeleteFirst(SL* ps)
{assert(ps != NULL);if (ps->count == 0){printf("数据已经删完了\n");}else{for (int i = 0; i < ps->count - 1; i++){ps->a[i] = ps->a[i + 1];}ps->count--;printf("删除成功\n");}
}//顺序表任意位置删除数据
void SLDelete(SL* ps, int pos)
{assert(ps != NULL);assert(pos >= 0 && pos <= ps->count);if (ps->count == 0){printf("数据已经删完了\n");}else{for (int i = pos; i < ps->count - 1; i++){ps->a[i] = ps->a[i + 1];}ps->count--;printf("删除成功\n");}
}//顺序表中寻找对应数据下标
int SLFind(SL* ps, SLDATETYPE x)
{assert(ps != NULL&&ps->a != NULL);for (int i = 0; i < ps->count; i++){if (ps->a[i] == x){return 1;}}return -1;
}