当前位置: 首页 > article >正文

03.顺序表实现

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,在数组上完成数据的增删改查。一般见到的顺序表都是在结构体中定义的数组,只是比普通数组多了增删改查等一些其他功能函数。

        上节已经介绍了顺序表有动态顺序表和静态顺序表。动态比静态有很多优点,这节将实现动态顺序表。

一、头文件定义

        1、包含实现动态顺序表所需的头文件。

        2、定义顺序表结构体。

        3、功能函数的声明。

//1、包含头文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//assert()函数的作用:如果()内为假则断言报错终止运行

//2、定义结构体
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;	//指针数组
	int size;		//数据个数
	int capacity;	//容量
}SL;

//3、声明功能函数
//初始化加销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
//检查空间大小,如果空间小了则申请空间
void SLCheckCapacity(SL* ps);
//尾插和头插
void SLBackPush(SL* ps, SLDataType x);
void SLFrontPush(SL* ps, SLDataType x);
//尾删和头删
void SLBackPop(SL* ps);
void SLFrontPop(SL* ps);
//查找数据下标
int SLFind(SL* ps, SLDataType x);
//指定位置插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//打印顺序表
void SLPrint(SL* ps);

二、功能函数实现

#include "SeqList.h"

//初始化加销毁
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//检查空间是否足够
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}
//尾插
void SLBackPush(SL* ps, SLDataType x)
{
	assert(ps);		//断言
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//头插
void SLFrontPush(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}
//尾删
void SLBackPop(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
//头删
void SLFrontPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	for (int i = 0; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查找数据下标
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}
//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}
//在指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->size--;
	for (int i = pos; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
}
//打印顺序表
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

三、主函数测试

#include "SeqList.h"

int main()
{
	SL sl;
	SLInit(&sl);

	SLFrontPush(&sl, 1);
	SLFrontPush(&sl, 2);
	SLFrontPush(&sl, 3);
	SLFrontPush(&sl, 4);
	SLBackPush(&sl, 0);
	printf("插入的数据:");
	SLPrint(&sl);

	SLFrontPop(&sl);
	SLBackPop(&sl);
	printf("删除头和尾后:");
	SLPrint(&sl);

	printf("在下标1处添加数据9后:");
	SLInsert(&sl, 1, 9);
	SLPrint(&sl);
	int pos = SLFind(&sl, 9);
	printf("查找数据为9的下标:%d\n", pos);
	SLErase(&sl, pos);
	printf("删除下标为1的数据:");
	SLPrint(&sl);
	printf("查找数据为9的下标:%d\n", SLFind(&sl, 9));
	SLDestory(&sl);
	return 0;
}

 分别建立名为SeqList.h的头文件和SeqList.c的源文件,和一个主函数文件。运行上述代码:


http://www.kler.cn/a/355005.html

相关文章:

  • LeetCode 209. 长度最小的子数组 (C++实现)
  • 2、光同步数字传送网的特点
  • Java 优化springboot jar 内存 年轻代和老年代的比例 减少垃圾清理耗时 如调整 -XX:NewRatio
  • IntelliJ IDEA 快捷键大全:提升开发效率的利器
  • Tomcat负载均衡全解析
  • unity webgl部署到iis报错
  • JS_用发布订阅模式解耦
  • 云手机:社交平台运营的热门工具
  • 王爽汇编语言第三版实验1
  • 基于springboot的学习平台系统
  • 两种常见的磁盘分区样式及它们的区别总结
  • HttpUtils 详解
  • k8s jenkins 2.421动态创建slave
  • linux 内核如何读取你配置好的.config文件
  • 【CentOS】Shell脚本案例:归档文件
  • C++从入门到起飞之——红黑树 全方位剖析!
  • 【Flutter 面试题】 Flutter如何使用路由、全局错误捕获和自定义组件统一管理错误页面?
  • SpringBoot3响应式编程全套-R2DBC
  • 模板方法设计模式
  • hdfs API操作 hadoop3.3.5
  • java项目技术架构图-样例
  • mysql--表的约束
  • 【Ubuntu】虚拟机共享文件夹启用
  • NFTScan | 10.07~10.13 NFT 市场热点汇总
  • vmware ubuntu根分区扩容
  • 纯前端如何实现批量下载功能呢?