IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 【动态顺序表接口实现-C语言】 -> 正文阅读

[C++知识库]【动态顺序表接口实现-C语言】

请添加图片描述



前言

本文总结学习动态顺序表的各个接口实现。

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

  • 静态顺序表:使用定长数组存储元素
  • 动态顺序表:使用动态开辟的数组存储,本文基于动态顺序表来实现接口。

一、顺序表头文件SeqList.h

本节主要包含:结构体类型创建,函数声明,头文件包含

#pragma once

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <errno.h>

typedef int SLdataType;

typedef struct SeqList
{
	SLdataType* arr;//指向动态开辟的数组
	size_t size;// 有效数据个数
	size_t capicity;// 容量空间的大小

}SeqList;


// 基本增删查改接口

// 顺序表初始化
void SeqListInit(SeqList* psl);

// 顺序表销毁
void SeqListDestory(SeqList* psl);

// 顺序表打印
void SeqListPrint(SeqList* psl);

// 检查空间,如果满了(psl->size == psl->capacity),进行增容(2倍)
void SeqListCheckCapacity(SeqList* psl);

// 顺序表在pos位置(下标)插入x
void SeqListInsert(SeqList* psl, size_t pos, SLdataType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);

// 顺序表查找(按数组元素值)(找到返回对应下标,未找到返回-1)
int SeqListFind(SeqList* psl, SLdataType x);

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLdataType x);

// 顺序表尾删
void SeqListPopBack(SeqList* psl);

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLdataType x);

// 顺序表头删
void SeqListPopFront(SeqList* psl);

// 顺序表修改指定位置元素
void SeqListModify(SeqList* psl, size_t pos, SLdataType x);

二、顺序表各接口具体实现SeqList.c

本节主要包含:顺序表各个接口的实现方法

2.1 顺序表初始化

void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->arr = NULL;
	psl->capicity = 0;
	psl->size = 0;
}

2.2 顺序表销毁

void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->arr);
	(psl->arr) = NULL;
	psl->capicity = psl->size = 0;
}

2.3 顺序表打印

void SeqListPrint(SeqList* psl)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < (psl->size); i++) {
		printf("%d ", (psl->arr)[i]);
	}
	printf("\n");
}

2.4 检查空间,如果满了(psl->size == psl->capacity),进行增容(2倍)

void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	// 注意当psl->capicity起初为0时,不能指向开辟2倍空间,因为0*2仍为0
	int newcapacity = (0 == (psl->capicity)) ? 4 : 2 * (psl->capicity);

	if ((psl->capicity) == (psl->size)) {
		// 先用临时指针接收增容返回的指针,因为realloc如果开辟失败会返回NULL
		SLdataType* tmp = (SLdataType*)realloc(psl->arr, newcapacity * sizeof(SLdataType));
		if (NULL == tmp) {
			printf("%s\n", strerror(errno));
			// 增容失败直接终止程序
			exit(-1);
		}
		else {
			psl->arr = tmp;
			psl->capicity = newcapacity;
		}
	}
}

2.5 顺序表在pos位置(下标)插入元素x

请添加图片描述

void SeqListInsert(SeqList* psl, size_t pos, SLdataType x)
{
	assert(psl);
	// 检查空间容量是否能多出至少一个位置空间
	SeqListCheckCapacity(psl);

	// 检查pos有效性(pos为无符号,本身默认大于等于0)
	if (pos > (psl->size)) { 
		// 当pos == (psl->size)时,psl->size为元素个数,
		// 例如size为5,即5个数,最大下标为4,pos为5则相当于尾插,不算为越界
		printf("pos 越界:%d\n", pos);
		// 这里仅是传入的位置越界,不至于终止程序,结束函数即可
		return;
	}

	// 尾下标
	// 为避免当psl->size为0时,减去1后变为-1,在while(end>=pos)时pos是无符号类型,比较在CPU进行,会发生算术转换出现问题
	// 所以不使用int end = (psl->size) - 1;
	int end = (psl->size);
	while (end > pos) {
		// 从后向前依次向后覆盖一位,直到end 相邻于 pos,该位置也要向后覆盖一位将pos位置处的空间腾出来
		(psl->arr)[end] = (psl->arr)[end - 1];
		end--;// 小心别忘了!!!
	}
	(psl->arr)[pos] = x;
	(psl->size)++;// 小心别忘了!!!
}

2.6 顺序表删除pos位置的值

请添加图片描述

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);

	// 检查pos有效性(pos为无符号,本身默认大于等于0)
	// 也可以暴力检查:assert(pos < (psl->size))
	if (pos >= (psl->size)) { //删除的话最大下标就为(psl->size)-1,与尾插情况不同
		printf("pos 越界:%d\n", pos);
		// 这里仅是传入的位置越界,不至于终止程序,结束函数即可
		return;
	}

	// 删除相当覆盖,从前向后依次向前覆盖才不会将有效数据覆盖
	int end = (psl->size) - 1;// end此时相当于数组的尾元素下标
	while (pos < end) {
		(psl->arr)[pos] = (psl->arr)[pos + 1];
		pos++;
	}
	// 也可以:
	//int start = pos + 1;
	//while (start < (psl->size)) { //start最大为(psl->size)-1
	//	(psl->arr)[start - 1] = (psl->arr)[start];
	//	start++;
	//}

	(psl->size)--;
}

2.7 顺序表查找(按数组元素值)(找到返回对应下标,未找到返回-1)

int SeqListFind(SeqList* psl, SLdataType x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < (psl->size); i++) {
		if (x == (psl->arr)[i]) {
			return i;
		}
	}
	return -1;
}

2.8 顺序表尾插

void SeqListPushBack(SeqList* psl, SLdataType x)
{
	assert(psl);
	// 复用SeqListInsert
	SeqListInsert(psl, (psl->size), x); //(psl->size)即为数组元素最大下标加1
}

2.9 顺序表尾删

void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	// 复用SeqListInsert
	SeqListErase(psl, (psl->size) - 1); //(psl->size) - 1即为数组元素最大下标
}

2.10 顺序表头插

void SeqListPushFront(SeqList* psl, SLdataType x)
{
	assert(psl);
	// 复用SeqListInsert
	SeqListInsert(psl, 0, x);
}

2.10 顺序表头删

void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	// 复用SeqListInsert
	SeqListErase(psl, 0);
}

2.11 顺序表修改指定位置元素

void SeqListModify(SeqList* psl, size_t pos, SLdataType x)
{
	assert(psl);
	// 也可以暴力检查:assert(pos < (psl->size))
	if (pos >= (psl->size)) {
		printf("pos 越界:%d\n", pos);
		// 这里仅是传入的位置越界,不至于终止程序,结束函数即可
		return;
	}

	(psl->arr)[pos] = x;
}

三、顺序表测试test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

int main()
{
	SeqList s = { 0 };

	// 顺序表初始化
	SeqListInit(&s);

	// 顺序表在pos位置(下标)插入x
	int i = 0;
	for (i = 0; i < 10; i++) {
		SeqListInsert(&s, 0, i);
	}

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表删除pos位置(下标)的值
	SeqListErase(&s, 3);

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表查找(按数组元素值)(找到返回对应下标,未找到返回-1)
	int ret = SeqListFind(&s, 4);
	printf("%d\n", ret);

	// 顺序表尾插
	SeqListPushBack(&s, 99);

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表尾删
	SeqListPopBack(&s);

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表头插
	SeqListPushFront(&s, 100);

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表头删
	SeqListPopFront(&s);

	// 顺序表打印
	SeqListPrint(&s);
	
	// 顺序表修改指定位置元素
	SeqListModify(&s, 3, 555);

	// 顺序表打印
	SeqListPrint(&s);

	// 顺序表销毁
	SeqListDestory(&s);

	// 检查空间,如果满了(psl->size == psl->capacity),进行增容(2倍)
	//SeqListCheckCapacity(&s);

	return 0;
}

注意:调用函数时需结构体传址,因为:

1-传值的话,调用函数时,main函数和接口函数分别开辟栈帧,形参是实参的拷贝,改变形参不影响实参,调用函数,形参实例化(本质是给临时变量开辟空间,将拷贝后的形参放入空间),形参是实参的拷贝,二者开辟不同栈帧,占据不同空间,改变形参不影响实参。

2-函数传参时,参数是需要压栈,会有时间和空间上的系统开销。如果传递一个结构体对象时(传值),结构体过大,参数压栈的系统开销比较大,所以会导致性能的下降。


总结

这里对文章进行总结:
以上就是今天总结的内容,本文包括了C语言实现动态顺序表各个接口,分享给大家。
真💙欢迎各位给予我更好的建议,欢迎访问!!!小编创作不易,觉得有用可以一键三连哦,感谢大家。peace
希望大家一起坚持学习,共同进步。梦想一旦被付诸行动,就会变得神圣。

欢迎各位大佬批评建议,分享更好的方法!!!🙊🙊🙊

  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-03-15 22:13:21  更:2022-03-15 22:16:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/24 4:21:22-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码