数据结构C语言描述1(图文结合)--顺序表讲解，实现，表达式求值应用，考研可看

前言

  • 这个专栏将会用纯C实现常用的数据结构和简单的算法；
  • 用C基础即可跟着学习，代码均可运行；
  • 准备考研的也可跟着写，个人感觉，如果时间充裕，手写一遍比看书、刷题管用很多，这也是本人采用纯C语言实现的原因之一；
  • 欢迎收藏 + 关注，本人将会持续更新。

顺序表基本概念

什么是线性表？

线性表是一组具有相同特征元素的有序序列，记作：（a1, a2, …, ai-1, a！, ai+1, …, an），当然这有点官方了，但是核心就两个特征：相同特征、有序序列；但我从《大话数据结构中》中看到了另外一个描述，我感觉听通俗易懂的：

  • 线性表的数据对象集合{a1, a2, …, ai-1, a！, ai+1, …, an}，每个元素的类型均为DataType。其中，除了第一个元素a1 外，每一个元素有且只有直接前驱元素，除了最后一个元素an 外，每一个元素有且只有一个直接后驱元素。且数据元素之间关系是一一对应的。

线性表相关概念

  • 直接前驱元素：ai-1 领先于ai ，则称ai-1 是ai 的直接前驱元素；
  • 直接后驱元素：ai+1 领先于ai ，则称ai+1 是ai 的直接后驱元素；
  • 前驱元素：a1,a2,a3,……ai-1, 都是ai 的前驱元素；
  • 后驱元素：ai+1,ai+2,ai+3,……ai+n, 都是ai 的前驱元素；
  • 线性表长度：线性表中包含所有元素的个数；
  • 空线性表：不包含任何元素的线性表；
  • 位序：元素在线性表第几个位置

什么是顺序表？

顺序表就是用一段连续的内存空间依次存储数据，顺序表的存储大概图如下(参考《大话数据结构》)：

在这里插入图片描述

顺序表特点

  • 存储数据内存地址连续
  • 可以支持下标访问
  • 删除、添加中间位置元素麻烦
  • 数据容量固定

顺序表的抽象设计

把顺序表存储的东西，看成是一个集合中存储，从**抽象数据类型(ADT)**角度来看，这个我们需要数据的实现可以有一下几个基本操作：

  • 创建、初始化循序表
  • 插入元素
  • 删除元素
  • 查找元素
  • 判空操作
  • 判满操作

总之一句话：增删改查外加排序。

顺序表程序实现

封装顺序表

  • 对数据类型进行取别名，这样是代码更具有泛化性；
  • 采用结构体进行封装，可以更好描述顺序表
typedef int DataType;

typedef struct SeqList {
	DataType* data;     // 储存数据
	size_t size;	   // 当下储存了多少数
	size_t capacity;   // 当下能够储存数据的最大容量
}SeqList;

创建顺序表

利用calloc函数，他会在申请内存的时候自动初始化为空，这里具体他做了一下几件事情：

  • 事情一块内存空间，大小为sizeof(Seqlist)
  • data = NULL
  • size = 0
  • capacity = 0
SeqList* create_seqlist()
{
	SeqList* new_data = (SeqList*)calloc(1, sizeof(SeqList));
	if (!new_data) {
		printf("顺序表创建失败\n");
		return new_data;
	}

	return new_data;
}

插入元素

这里是向后插入，扩容规则如下(自己定义的，不是一定的)：

  • 如果capacity为0，则赋值为10，当作初始化
  • 否则如果容量不够，则按照两倍扩容

向后插入图示如下(也可以有序插入，这个需要按照具体场景)：

在这里插入图片描述

void insert_seqlist(SeqList* list, DataType data)
{
	assert(list);   // list为空，则断言

	// 是否需要扩容
	if (list->size >= list->capacity) {
		// 2倍扩容
		if (list->capacity == 0) {
			list->capacity = 10;
		}
		else {
			list->capacity = 2 * list->capacity;
		}
		// 扩容
		DataType* new_data = (DataType*)realloc(list->data, list->capacity * sizeof(DataType));
		assert(new_data);  // 判断内存是否申请失败
		list->data = new_data;
	}

	// 直接在后面插入，但是也可以有序插入，这个要根据业务
	list->data[list->size++] = data;
}

查找–按值查找

  • 目的：通过值找到返回他在顺序表中的存储的下标，规则：如果改顺序表中不存在该元素，则返回-1。
  • 方法：遍历，从第一个遍历到最后，时间复杂度为O(n)
int search_value_seqlist(SeqList* list, DataType data)
{
	// 防止空表
	assert(list);

	for (size_t i = 0; i < list->size; i++) {
		if (list->data[i] == data) {
			return i;
		}
	}
		
	return -1;  
}

查找–按位查找

  • 目的：通过下标找到返回他在顺序表中的存储的元素，规则：如果传递位有误，则返回-1。
DataType search_position_seqlist(SeqList* list, size_t k)
{
	assert(list);

	if (k >= list->size || k < 0) {
		return -1;
	}

	return list->data[k];
}

删除–通过下标

  • 目的：删除下标为k的元素
  • 数组的删除为伪删除，不是真正的删除，将删除的元素移动到最后而已，具体过程图示如下：

在这里插入图片描述

void erase_seqlist_index(SeqList* list, size_t index)
{
	assert(list);

	if (index < 0 || index >= list->size) {
		printf("无效位置\n");
		return;
	}

	for (int i = index; i < list->size - 1; i++) {
		list->data[i] = list->data[i + 1];
	}

	list->size--;
}

删除–通过指定元素

  • 删除第一个符合元素，具体过程如图示(和上图一样)：

在这里插入图片描述

void erase_seqlist_data(SeqList* list, DataType data)
{
	assert(list);

	for (size_t i = 0; i < list->size; i++) {
		if (list->data[i] == data) {
			erase_seqlist_index(list, i);   // 原理一样
		}
	}
}
  • 删除全部符合元素删除，采用双指针算法，最快理解就是通过图示，如下：

在这里插入图片描述

void erase_seqlist_all(SeqList* list, DataType data)
{
	assert(list);

	// 第一种方法：暴力，这里不写

	// 第二种方法: 双指针
	size_t slow = 0, fast = 0;
	int num = 0;
	for (; fast < list->size; fast++) {
		if (list->data[fast] == data) {
			num++;
			continue;
		}
		else {
			list->data[slow++] = list->data[fast];
		}
	}
	list->size -= num;
}

判断是否为空

判断链表是不是没有存储元素，但是要注意，没有存储元素只是代表SeqList->size==0，但不代表数组里没有储存元素，没有内容空间，具体为什么，可以想一想？？？？

bool emtpy_seqlist(SeqList* list) {
	return list->size == 0;
}

查询顺序表大小

查找当前顺序表中储存元素的数量

int size_seqlist(SeqList* list) {
	return list->size;
}

销毁

释放顺序表，将申请的内存空间全部释放：

  • 第一步：释放数据空间
  • 第二步：释放创建的顺序表

注意：释放完毕后，指针需要赋值为NULL

void destory_seqlist(SeqList* list)
{
	assert(list);

	// 释放数据
	if (list->data != NULL) {
		free(list->data);
		list->data = NULL;
	}
	// 释放链表
	free(list);
	list = NULL;
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

// 增删改查外加排序

typedef int DataType;

typedef struct SeqList {
	DataType* data;
	size_t size;
	size_t capacity;
}SeqList;

// 创建顺序表
SeqList* create_seqlist();

// 插入
void insert_seqlist(SeqList* list, DataType data);

// 查找--按值查找，找得到则返回下标(0开始)，找不到就返回-1
int search_value_seqlist(SeqList* list, DataType data);
// 查找--按位查找，越界：-1，正常：下标
DataType search_position_seqlist(SeqList* list, size_t k);

// 删除--通过下标(位置), index从0开始
void erase_seqlist_index(SeqList* list, size_t index);
// 删除--通过指定元素
void erase_seqlist_data(SeqList* list, DataType data);  // 删除一个
void erase_seqlist_all(SeqList* list, DataType data);   // 删除全部

// 万金油函数
bool emtpy_seqlist(SeqList* list) {
	return list->size == 0;
}
int size_seqlist(SeqList* list) {
	return list->size;
}

// 打印
void print_seqlist(SeqList* list);

// 销毁
void destory_seqlist(SeqList* list);

int main()
{
	SeqList* list = create_seqlist();

	for (int i = 0; i < 15; i++) {
		insert_seqlist(list, i);
	}
	insert_seqlist(list, 8);
	printf("插入测试：\n");
	print_seqlist(list);
	printf("查找测试：\n");
	DataType value = search_value_seqlist(list, 8);
	int pos = search_position_seqlist(list, 2);
	printf("from_value: %d, from_pos: %d\n", value, pos);
	printf("删除测试: \n");
	erase_seqlist_index(list, 5);  
	print_seqlist(list);
	erase_seqlist_data(list, 9);
	print_seqlist(list);
	erase_seqlist_all(list, 8);
	print_seqlist(list);
	printf("万金油函数: \n");
	printf("是否为空：%d\n", emtpy_seqlist(list));
	printf("大小: %d\n", size_seqlist(list));
	// 销毁
	destory_seqlist(list);

	return 0;
}

SeqList* create_seqlist()
{
	SeqList* new_data = (SeqList*)calloc(1, sizeof(SeqList));
	if (!new_data) {
		printf("顺序表创建失败\n");
		return new_data;
	}

	return new_data;
}

void insert_seqlist(SeqList* list, DataType data)
{
	assert(list);   // list为空，则断言

	// 是否需要扩容
	if (list->size >= list->capacity) {
		// 2倍扩容
		if (list->capacity == 0) {
			list->capacity = 10;
		}
		else {
			list->capacity = 2 * list->capacity;
		}
		// 扩容
		DataType* new_data = (DataType*)realloc(list->data, list->capacity * sizeof(DataType));
		assert(new_data);  // 判断内存是否申请失败
		list->data = new_data;
	}

	// 直接在后面插入，但是也可以有序插入，这个要根据业务
	list->data[list->size++] = data;
}

void print_seqlist(SeqList* list)
{
	for (size_t i = 0; i < list->size; i++) {
		printf("%d ", list->data[i]);
	}
	puts("\n");
}

int search_value_seqlist(SeqList* list, DataType data)
{
	// 防止空表
	assert(list);

	for (size_t i = 0; i < list->size; i++) {
		if (list->data[i] == data) {
			return i;
		}
	}
		
	return -1;  
}

DataType search_position_seqlist(SeqList* list, size_t k)
{
	assert(list);

	if (k >= list->size || k < 0) {
		return -1;
	}

	return list->data[k];
}

void erase_seqlist_index(SeqList* list, size_t index)
{
	assert(list);

	if (index < 0 || index >= list->size) {
		printf("无效位置\n");
		return;
	}

	for (int i = index; i < list->size - 1; i++) {
		list->data[i] = list->data[i + 1];
	}

	list->size--;
}

void erase_seqlist_data(SeqList* list, DataType data)
{
	assert(list);

	for (size_t i = 0; i < list->size; i++) {
		if (list->data[i] == data) {
			erase_seqlist_index(list, i);   // 原理一样
		}
	}
}

void erase_seqlist_all(SeqList* list, DataType data)
{
	assert(list);

	// 第一种方法：暴力，这里不写

	// 第二种方法: 双指针
	size_t slow = 0, fast = 0;
	int num = 0;
	for (; fast < list->size; fast++) {
		if (list->data[fast] == data) {
			num++;
			continue;
		}
		else {
			list->data[slow++] = list->data[fast];
		}
	}
	list->size -= num;
}

void destory_seqlist(SeqList* list)
{
	assert(list);

	// 释放数据
	if (list->data != NULL) {
		free(list->data);
		list->data = NULL;
	}
	// 释放链表
	free(list);
	list = NULL;
}

顺序表案例

顺序表应用常见有很多， 比如说：储存数据(管理系统等)，这里我们做一个多项式合并，多项式次数存储有序，次数从高到低。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define max_num 100

typedef struct Node {
	int data;   // 底数
	int exp;    // 指数
}Node;

typedef struct SeqList {
	Node data[max_num];
	int count;
}SeqList;

void add(SeqList* A, SeqList* B, SeqList* C)
{
	if (A == NULL || B == NULL || C == NULL) {
		return;
	}

	int i = 0, j = 0, k = 0;
	while (i < A->count && j < B->count) {
		// 次数对比
		if (A->data[i].exp > B->data[j].exp) {
			C->data[k++] = A->data[i++];
		}
		else if (A->data[i].exp < B->data[j].exp) {
			C->data[k++] = B->data[j++];
		}
		else {  // 次数相同
			Node t;
			if (A->data[i].data + B->data[j].data == 0) {
				continue;
			}
			t.exp = A->data[i].exp;
			t.data = A->data[i++].data + B->data[j++].data;
			C->data[k++] = t;
		}
		C->count++;
	}

	while (i < A->count) {
		C->data[k++] = A->data[i++];
	}

	while (j < B->count) {
		C->data[k++] = B->data[j++];
	}

}

int main()
{
	// y = 3 * x^2 + 5 * x + 2
	SeqList A = { {{3, 2},{5,1},{2, 0}}, 3 };
	// y = -1 * x^3 + 4 * x^2 + 4
	SeqList B = { {{-1,3},{4, 2},{4, 0}}, 3 };

	SeqList C = { 0 };  // 答案

	add(&A, &B, &C);

	int i = 0;
	while (i < C.count) {
		if (C.data[i].exp == 0) {
			printf("%d ", C.data[i].data);
		}
		else {
			printf("%d * x^%d ", C.data[i].data, C.data[i].exp);
		}

		if (i != C.count - 1) {
			printf("+ ");
		}
		i++;
	}


	return 0;
}

// 输出：
/*
-1 * x^3 + 7 * x^2 + 5 * x^1 + 6
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/906968.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Oracle视频基础1.3.7练习

Oracle视频基础1.3.7练习

1.3.7 看oracle是否启动构造一个pfile:boobooke.ora看spfilewilson内容修改alert log file里拷贝的参数内容&#xff0c;创建一个pfile boobooke.ora用新创建的pfile启动数据库&#xff0c;并创建新的spfile:spfilebbk.ora启动数据库&#xff0c;监听&#xff0c;看新的进程解…
阅读更多...
数据转换 | Matlab基于SP符号递归图（Symbolic recurrence plots）一维数据转二维图像方法

数据转换 | Matlab基于SP符号递归图（Symbolic recurrence plots）一维数据转二维图像方法

目录 基本介绍程序设计参考资料获取方式 基本介绍 Matlab基于SP符号递归图&#xff08;Symbolic recurrence plots&#xff09;一维数据转二维图像方法 符号递归图(Symbolic recurrence plots)是一种一维时间序列转图像的技术&#xff0c;可用于平稳和非平稳数据集;对噪声具有…
阅读更多...
将android studio3.4.1改为as 2024的方法

将android studio3.4.1改为as 2024的方法

将android studio3.4.1改为as 2024的方法 先正常的open项目&#xff0c;不用等gradle build完&#xff0c;就先改这2个地方&#xff1a; 1.替换as2024新建一个空的正常的项目的build.gradle和config.gradle 2.在build.gradle(app)中 删除3处kotlin相关的提示&#xff08;2个…
阅读更多...
【温酒笔记】DMA

【温酒笔记】DMA

参考文档&#xff1a;野火STM32F103 网友资料整理 1. Direct Memory Access-直接内存访问 DMA控制器独立于内核 是一个单独的外设 DMA1有7个通道DMA2有5个通道DMA有四个等级&#xff0c;非常高&#xff0c;高&#xff0c;中&#xff0c;低四个优先级如果优先等级相同&#xf…
阅读更多...
Stable Diffusion Web UI 1.9.4常用插件扩展-WD14-tagger

Stable Diffusion Web UI 1.9.4常用插件扩展-WD14-tagger

Stable Diffusion Web UI 1.9.4 运行在 WSL 中的 Docker 容器中 tagger 插件的作用是&#xff0c;上传一张图片&#xff0c;反推这张图片可能的提示词。 使用场景就是&#xff0c;想要得到类似的图片内容时使用。 WD14-tagger 安装 Stable Diffusion WebUI WD14-tagger GitH…
阅读更多...
VS 中使用c#高版本语言方法

VS 中使用c#高版本语言方法

方法如下&#xff0c;打开项目工程文件&#xff08;记事本&#xff09;&#xff0c;然后添加如下语句&#xff1a;保存&#xff0c;重新加载即可使用最新C#语法。
阅读更多...
Golang--DOS命令、变量、基本数据类型、标识符

Golang--DOS命令、变量、基本数据类型、标识符

1、DOS命令 切换盘符&#xff08;大小写没有区别&#xff09;&#xff1a; c: //切换到c盘 d: //切换到d盘 e: //切换到e盘 显示文件内信息&#xff1a; 指令&#xff1a;dir 切换路径&#xff1a; 指令&#xff1a;cd 绝对路径 / 相对路径 . 表示当前…
阅读更多...
正反向滤波的简述和MATLAB代码

正反向滤波的简述和MATLAB代码

文章目录 MATLAB 例程：卡尔曼滤波与反向滤波运行结果代码说明总结P.S. 相关公式1. 正向滤波（Forward Filtering）2. 反向滤波（Backward Filtering）3. 总结以下是一个简单的MATLAB例程，演示如何使用卡尔曼滤波进行状态估计，包括正向滤波和反向滤波的实现。这个例程模拟了一…
阅读更多...
Django目录结构最佳实践

Django目录结构最佳实践

Django项目目录结构 项目目录结构配置文件引用修改创建自定义子应用方法修改自定义注册目录从apps目录开始 项目目录结构 └── backend # 后端项目目录&#xff08;项目名称&#xff09;├── __init__.py├── logs # 项目日志目录├── manage.py #…
阅读更多...
KVM 使用主机 GPU

KVM 使用主机 GPU

KVM 如何使用主机的 GPU&#xff0c;首先安装 KVM。 配置Grub vi /etc//etc/default/grub GRUB_CMDLINE_LINUX"amd_iommuon iommupt videoefifb:off vfio_pci.ids10de:1e07,10de:10f7,10de:1ad6,10de:1ad7"查看主机显卡信息 lspci -nnk | grep -A 3 VGA 找到GP…
阅读更多...
b站小土堆PyTorch视频学习笔记（二）

b站小土堆PyTorch视频学习笔记（二）

Dataloader:提供不同类型的数据集&#xff1b;为后面的网络提供不同的数据形式 Dataset&#xff1a;提供一种方式去获取数据及其label&#xff08;标签&#xff09; 主要实现以下两个功能&#xff1a; {如何获取每一个数据及其lable&#xff1b;告诉我们总共有多少数据} fr…
阅读更多...
nginx的proxy_next_upstream使用中的一个坑

nginx的proxy_next_upstream使用中的一个坑

今天线上系统出了点问题&#xff0c;机房的电信出口突然不通了&#xff0c;原本以为能自动切换的nginx配置&#xff0c;居然没有生效&#xff0c;导致了业务告警&#xff0c;手工紧急处理了才解决了。 当时的设想是&#xff0c;如果这个服务的访问&#xff0c;出现了500或者超…
阅读更多...
【Git】SSH密钥

【Git】SSH密钥

目录 1 前言2 SSH密钥2.1 生成密钥2.2 查看密钥2.3 关联Git服务器 3 小结 1 前言 许多Git服务器都使用SSH公钥进行认证&#xff0c;为了向Git服务器提供SSH公钥&#xff0c;如果某系统用户尚未拥有密钥&#xff0c;必须事先为其生成一份。 2 SSH密钥 2.1 生成密钥 在Window…
阅读更多...
【Seed-Labs】SQL Injection Attack Lab

【Seed-Labs】SQL Injection Attack Lab

Overview SQL 注入是一种代码注入技术&#xff0c;利用的是网络应用程序与数据库服务器之间接口的漏洞。当用户输入的信息在发送到后端数据库服务器之前没有在网络应用程序中进行正确检查时&#xff0c;就会出现这种漏洞。 许多网络应用程序从用户那里获取输入&#xff0c;然…
阅读更多...
ClkLog企业版（CDP）预售开启，更有鸿蒙SDK前来助力

ClkLog企业版（CDP）预售开启，更有鸿蒙SDK前来助力

新版本发布 ClkLog在上线近1年后&#xff0c;获得了客户的一致肯定与好评&#xff0c;并收到了不少客户对功能需求的反馈。根据客户的反馈&#xff0c;我们在今年三季度对ClkLog的版本进行了重新的规划与调整&#xff0c;简化了原有的版本类型&#xff0c;方便客户进行选择。 与…
阅读更多...
T矩阵其实就是pauli基的乘，S矩阵中hv是体散射分量

T矩阵其实就是pauli基的乘，S矩阵中hv是体散射分量

注意什么是面散射&#xff0c;二次散射和体散射。 ShhSvv表示单次散射的电压&#xff0c;|ShhSvv|^2是功率
阅读更多...
群控系统服务端开发模式-应用开发-上传配置功能开发

群控系统服务端开发模式-应用开发-上传配置功能开发

下面直接进入上传配置功能开发&#xff0c;废话不多说。 一、创建表 1、语句 CREATE TABLE cluster_control.nc_param_upload (id int(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 编号,upload_type tinyint(1) UNSIGNED NOT NULL COMMENT 上传类型 1&#xff1a;本站 2&a…
阅读更多...
HarmonyOS NEXT 应用开发实战（九、知乎日报项目详情页实现详细介绍）

HarmonyOS NEXT 应用开发实战（九、知乎日报项目详情页实现详细介绍）

在本篇博文中&#xff0c;我们将探讨如何使用 HarmonyOS Next 框架开发一个知乎日报的详情页&#xff0c;逐步介绍所用到的组件及代码实现。知乎日报是个小巧完整的小项目&#xff0c;这是一个循序渐进的过程&#xff0c;适合初学者和有一定开发经验的工程师参考。 1. 项目背景…
阅读更多...
数据结构之链式结构二叉树的实现（初级版）

数据结构之链式结构二叉树的实现（初级版）

本文内容将主会多次用到函数递归知识&#xff01;&#xff01;&#xff01; 本节内容需要借助画图才能更好理解&#xff01;&#xff01;&#xff01; 和往常一样&#xff0c;还是创建三个文件 这是tree.h #pragma once #include<stdio.h> #include<stdlib.h> …
阅读更多...
数据结构（Java）—— 认识泛型

数据结构（Java）—— 认识泛型

1. 包装类 在学习泛型前我们需要先了解一下包装类 在 Java 中&#xff0c;由于基本类型不是继承自 Object &#xff0c;为了在泛型代码中可以支持基本类型&#xff0c; Java 给每个基本类型都对应了一个包装类型。 1.1 基本数据类型和对应的包装类 基本数据类型包装类byteByt…
阅读更多...
最新文章

Copyright @ 2022~2023