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

  • 开发
  • 21

文章目录

一、顺序表

顺序表是线性表的一种，是一种数据结构，用来存放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);
	}
	else
		printf("没有找到");
	//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;
}
阅读全部

相关推荐

  3. 【数据结构】顺序表的实现（C语言）

    2024-07-12 11:16:02       28 阅读

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

    2024-07-12 11:16:02       43 阅读

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

    2024-07-12 11:16:02       28 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-12 11:16:02       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-12 11:16:02       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-12 11:16:02       58 阅读

  19. Python语言-面向对象

    2024-07-12 11:16:02       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-12 11:16:02       64 阅读

热门阅读

  3. docker-2

    docker-2

    2024-07-12 11:16:02      24 阅读

  6. k8s离线部署芋道源码后端

    2024-07-12 11:16:02       19 阅读

  9. 实时数仓项目需求及架构设计

    2024-07-12 11:16:02       19 阅读

  10. 66、Flink 的 DataStream Connectors 支持的 Formats 详解

    2024-07-12 11:16:02       17 阅读

  15. 从0到1搭建数据中台（3）：flinkcdc实现数据从mysql到doris

    2024-07-12 11:16:02       121 阅读

  18. String的常用方法

    2024-07-12 11:16:02       30 阅读

  20. python字典

    2024-07-12 11:16:02       27 阅读

  22. aws课程，认证，学习方法

    2024-07-12 11:16:02       23 阅读

  27. dockerfile里的copy只能使用相对路径吗？

    2024-07-12 11:16:02       22 阅读