【算法与数据结构】顺序表

顺序表

数据结构 = 结构定义+结构操作

顺序表：结构定义

一个数组，添加额外的几个属性：size, count等
size: 数组有多大
count: 数组中当前存储了多少元素
在这里插入图片描述
顺序表三部分：

  1. 一段连续的存储区：顺序表存储元素的地方
  2. 整型的变量size： 标记顺序表的大小
  3. 整型变量count: 标记顺序表中到底存储了多少了元素

代码

结构定义

typedef struct vector{
	int size, count;
	int *data;   // 一段连续的存储区，存储的是整型元素， data指针指向整型的存储区

}vector;

构造函数
首先开辟顺序表本身的空间p， 然后给p的size赋值，p的count赋值，最后给p的data赋值，p的data指向的是顺序表中那段连续的存储区，存储区的大小是n

vector * getNewVector(int n)
{
	vector *p = (vector *)malloc(sizeof(vector));
	p->size = n;
	p->count = 0;
	p->data = (int*)malloc(sizeof(int)* n);
	return p;
}

析构函数
销毁之前先判断一下，如果对象为空，就直接返回；先销毁顺序表中连续的存储区，再销毁顺序表本身的存储空间

void clear(vector* v)
{
	if (v == NULL) return;
	free(v->data);
	free(v);
	return;
}

顺序表：插入

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
size不变
count+1

代码

插入之前先判断一下，插入位置的合法性以及顺序表的地方是否够用，如果存满了，本次插入不成功，返回0；否则没有存满，则可以将所有元素平行向后移动一位，以逆序遍历向后移动，从最后一位(count - 1)开始遍历，递减到插入位置pos，然后将元素插入。
最后，数据结构是包括性质的，还需要维护性质，即count+1

int insert(vector*v, int pos, int val)
{
    if (pos < 0 || pos > v->count) return 0;
	if (v->size == v->count) return 0;
	for (int i = v->count - 1; i >= pos; i--)
	{
		v->data[i + 1] = v->data[i];
	}
	v->data[pos] = val;
	v->count += 1;
	return 1;
}

顺序表：删除

在这里插入图片描述
在这里插入图片描述
size不变
count-1

代码

判断删除位置的合法性，然后后面的元素平行向前移动一个元素

int erase(vector *v, int pos)
{
	if (pos < 0 || pos >= v->count) return 0;
	for (int i = pos + 1; i < v->count; i++)
	{
		v->data[i - 1] = v->data[i];
	}

	v->count -= 1;
	return 1;
}

代码演示

用一组随机操作，对顺序表进行测试
可以在4范围内随机： 0， 1， 2表示插入， 3表示删除
随机插入的位置： 随机数 % （count +2）, 随机出一些非法位置，测试程序返回的结果是否正确。
然后进行插入和删除操作
输出格式：第一行是数组的序号，第二行是小横线，第三行元素

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>


typedef struct vector{
	int size, count;
	int *data;   // 一段连续的存储区，存储的是整型元素， data指针指向整型的存储区

}vector;

vector * getNewVector(int n)
{
	vector *p = (vector *)malloc(sizeof(vector));
	p->size = n;
	p->count = 0;
	p->data = (int*)malloc(sizeof(int)* n);
	return p;
}

int insert(vector*v, int pos, int val)
{
	if (pos < 0 || pos > v->count) return 0;
	if (v->size == v->count) return 0;
	for (int i = v->count - 1; i >= pos; i--)
	{
		v->data[i + 1] = v->data[i];
	}
	v->data[pos] = val;
	v->count += 1;
	return 1;
}

int erase(vector *v, int pos)
{
	if (pos < 0 || pos >= v->count) return 0;
	for (int i = pos + 1; i < v->count; i++)
	{
		v->data[i - 1] = v->data[i];
	}

	v->count -= 1;
	return 1;
}


void clear(vector* v)
{
	if (v == NULL) return;
	free(v->data);
	free(v);
	return;
}

void output_vector(vector  *v)
{
	
	int len = 0;
	for (int i = 0; i < v->size; i++)
	{
		len += printf("%3d", i);   // 控制整型输出的宽度， 累加输出的长度
	}
	printf("\n");
	for (int i = 0; i < len; i++) printf("-");   // 注意输出的长度为len与上面对齐
	printf("\n");
	for (int i = 0; i < v->count; i++)    // 注意输出的长度为count
	{
		printf("%3d", v->data[i]);
	}
	printf("\n");
	printf("\n\n");
	return;
}


int main()
{
	srand(time(0));
    #define MAX_OP 20
	vector *v = getNewVector(MAX_OP);
	for (int i = 0; i < MAX_OP; i++)
	{
		int op = rand() % 4, pos, val;
		switch (op)
		{
		case 0:
		case 1:
		case 2:
			pos = rand() % (v->count + 2);
			val = rand() % 100;
			printf("insert %d at %d to vector = %d\n", val, pos, insert(v, pos, val));
			break;
		case 3:
			pos = rand() % (v->count + 2);
			printf("erase item at %d in vector = %d\n", pos, erase(v, pos));
			break;

		}
		output_vector(v);

	}
	clear(v);

	std::cin.get();
	return 0;

}

输出：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

顺序表：扩容操作

当进行插入操作的时候，发现顺序表已经满了，可以自动扩容，扩容后就可以插入成功。
假设现在已经有了扩容成功了，什么情况下才返回插入不成功？ 答案：顺序表满了，并且扩容操作不成功，才返回0
还是跟前面一样，先判断一下传进来的顺序表的指针合不合法，判断指针是否指向空地址。
扩容策略: 二倍扩容法，如果原来顺序表的大小是size，尝试将size的顺序表扩容到2*size的大小，扩容的是顺序表的data区

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>


typedef struct vector{
	int size, count;
	int *data;   // 一段连续的存储区，存储的是整型元素， data指针指向整型的存储区

}vector;

vector * getNewVector(int n)
{
	vector *p = (vector *)malloc(sizeof(vector));
	p->size = n;
	p->count = 0;
	p->data = (int*)malloc(sizeof(int)* n);
	return p;
}

int expand(vector *v)
{
	if (v == NULL) return 0;
	printf("expand v from %d to %d\n", v->size, 2 * v->size );   // 输出扩容提示信息
	v->data = (int *)realloc(v->data, sizeof(int) * 2 * v->size);  // realloc(重新分配存储区的地址，希望重新分配的内存大小)
	v->size *= 2;   // 更新扩容后的size，2倍
	return 1;
}


int insert(vector*v, int pos, int val)
{
	if (pos < 0 || pos > v->count) return 0;
	if (v->size == v->count && !expand(v)) return 0;  // 如果满了且扩容失败，返回0
	for (int i = v->count - 1; i >= pos; i--)
	{
		v->data[i + 1] = v->data[i];
	}
	v->data[pos] = val;
	v->count += 1;
	return 1;
}

int erase(vector *v, int pos)
{
	if (pos < 0 || pos >= v->count) return 0;
	for (int i = pos + 1; i < v->count; i++)
	{
		v->data[i - 1] = v->data[i];
	}

	v->count -= 1;
	return 1;
}


void clear(vector* v)
{
	if (v == NULL) return;
	free(v->data);
	free(v);
	return;
}

void output_vector(vector  *v)
{
	
	int len = 0;
	for (int i = 0; i < v->size; i++)
	{
		len += printf("%3d", i);   // 控制整型输出的宽度， 累加输出的长度
	}
	printf("\n");
	for (int i = 0; i < len; i++) printf("-");   // 注意输出的长度为len与上面对齐
	printf("\n");
	for (int i = 0; i < v->count; i++)    // 注意输出的长度为count
	{
		printf("%3d", v->data[i]);
	}
	printf("\n");
	printf("\n\n");
	return;
}


int main()
{
	srand(time(0));
    #define MAX_OP 20
	vector *v = getNewVector(2);        // 
	for (int i = 0; i < MAX_OP; i++)
	{
		int op = rand() % 4, pos, val, ret;
		switch (op)
		{
		case 0:    // 注意case要从0开始
		case 1:
		case 2:
			pos = rand() % (v->count + 2);
			val = rand() % 100;
			ret = insert(v, pos, val);
			printf("insert %d at %d to vector = %d\n", val, pos, ret);
			break;
		case 3:
			pos = rand() % (v->count + 2);
			ret = erase(v, pos);
			printf("erase item at %d in vector = %d\n", pos, ret);
			break;

		}
		output_vector(v);

	}
	clear(v);

	std::cin.get();
	return 0;

}

输出：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

进一步分析

其实在重新分配内存（realloc）的时候有bug，realloc的策略：

  1. realloc会在原内存地址上试着向后去进行延展，如果向后扩展成功了，那么返回的地址就会和原内存地址是一样的，但是大小会增加一倍
  2. 找一片新的内存，把原内存的内容拷贝到新内存里面，并且返回新内存的地址。
  3. 以上两种情况都找不到，就会返回NULL

所以，再返回来看源代码，第一和第二种情况都没有bug，但是第三种情况，即扩容不成功的情况下，realloc会返回一个空地址，空地址会覆盖掉原来存储的地址，这个时候就会发生我们data中原来存储的地址信息丢失了。
解决方案：新定义一个指针，把realloc的返回值赋值给这个新指针，然后先判断是否为空，不是空地址才将新地址赋值给data

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>


typedef struct vector{
	int size, count;
	int *data;   // 一段连续的存储区，存储的是整型元素， data指针指向整型的存储区

}vector;

vector * getNewVector(int n)
{
	vector *p = (vector *)malloc(sizeof(vector));
	p->size = n;
	p->count = 0;
	p->data = (int*)malloc(sizeof(int)* n);
	return p;
}

int expand(vector *v)
{
	if (v == NULL) return 0;
	printf("expand v from %d to %d\n", v->size, 2 * v->size );   // 输出扩容提示信息
	int *p = (int *)realloc(v->data, sizeof(int)* 2 * v->size);  // realloc(重新分配存储区的地址，希望重新分配的内存大小)
	if (p == NULL) return 0;
	v->data = p;
	v->size *= 2;   // 更新扩容后的size，2倍
	return 1;
}


int insert(vector*v, int pos, int val)
{
	if (pos < 0 || pos > v->count) return 0;
	if (v->size == v->count && !expand(v)) return 0;  // 如果满了且扩容失败，返回0
	for (int i = v->count - 1; i >= pos; i--)
	{
		v->data[i + 1] = v->data[i];
	}
	v->data[pos] = val;
	v->count += 1;
	return 1;
}

int erase(vector *v, int pos)
{
	if (pos < 0 || pos >= v->count) return 0;
	for (int i = pos + 1; i < v->count; i++)
	{
		v->data[i - 1] = v->data[i];
	}

	v->count -= 1;
	return 1;
}


void clear(vector* v)
{
	if (v == NULL) return;
	free(v->data);
	free(v);
	return;
}

void output_vector(vector  *v)
{
	
	int len = 0;
	for (int i = 0; i < v->size; i++)
	{
		len += printf("%3d", i);   // 控制整型输出的宽度， 累加输出的长度
	}
	printf("\n");
	for (int i = 0; i < len; i++) printf("-");   // 注意输出的长度为len与上面对齐
	printf("\n");
	for (int i = 0; i < v->count; i++)    // 注意输出的长度为count
	{
		printf("%3d", v->data[i]);
	}
	printf("\n");
	printf("\n\n");
	return;
}


int main()
{
	srand(time(0));
    #define MAX_OP 20
	vector *v = getNewVector(2);        // 
	for (int i = 0; i < MAX_OP; i++)
	{
		int op = rand() % 4, pos, val, ret;
		switch (op)
		{
		case 0:    // 注意case要从0开始
		case 1:
		case 2:
			pos = rand() % (v->count + 2);
			val = rand() % 100;
			ret = insert(v, pos, val);
			printf("insert %d at %d to vector = %d\n", val, pos, ret);
			break;
		case 3:
			pos = rand() % (v->count + 2);
			ret = erase(v, pos);
			printf("erase item at %d in vector = %d\n", pos, ret);
			break;

		}
		output_vector(v);

	}
	clear(v);

	std::cin.get();
	return 0;

}

总结

相关数据结构到底支持什么操作，是一个不确定性的，非常灵活的，是自己设计的。

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

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

相关文章

利用css实现视差滚动和抖动效果

利用css实现视差滚动和抖动效果

背景&#xff1a; 前端的设计效果&#xff0c;越来越炫酷&#xff0c;而这些炫酷的效果&#xff0c;利用css3的动画效果和js就可以实现&#xff0c;简单的代码就能实现非常炫酷的效果。 原理&#xff1a; 利用 js监控scrollTop的位置&#xff0c;通过 top定位图片的位置&#x…
阅读更多...
HDOJ 1022 Train Problem Ⅰ 模拟栈操作

HDOJ 1022 Train Problem Ⅰ 模拟栈操作

&#x1f351; OJ专栏 &#x1f351; HDOJ 1022 Train Problem Ⅰ 输入 3 123 321 3 123 312输出 Yes. in in in out out out FINISH No. FINISH&#x1f351; 思路 &#x1f364; 栈顶元素与目标元素不匹配就进栈&#xff0c;匹配就出栈 &#x1f364; 匹配完&#xff1a;y…
阅读更多...
『python爬虫』10. 数据解析之xpath解析（保姆级图文）

『python爬虫』10. 数据解析之xpath解析（保姆级图文）

目录 安装库xpath入门怎么快速得到xpath路径xpath节点的关系xpath方法小型实战总结 欢迎关注 『python爬虫』 专栏&#xff0c;持续更新中 欢迎关注 『python爬虫』 专栏&#xff0c;持续更新中 安装库 pip install lxmlxpath入门 怎么快速得到xpath路径 &#xff08;相对路…
阅读更多...
webpack plugin原理以及自定义plugin

webpack plugin原理以及自定义plugin

通过插件我们可以拓展webpack&#xff0c;加入自定义的构建行为&#xff0c;使webpack可以执行更广泛的任务。 plugin工作原理&#xff1a; webpack工作就像是生产流水线&#xff0c;要通过一系列处理流程后才能将源文件转为输出结果&#xff0c;在不同阶段做不同的事&#x…
阅读更多...
二、PEMFC基础之电化学与反应动力学

二、PEMFC基础之电化学与反应动力学

二、PEMFC基础之电化学与反应动力学 1.电流、电流密度2.反应速率常数3.交换电流密度4.电化学动力学奠基石B-V方程5.活化损失计算Tafel公式6.计算案例 1.电流、电流密度 由法拉第定律 i d Q d t n F d N d t i\frac{dQ}{dt}\frac{nFdN}{dt} idtdQ​dtnFdN​ j i A j\frac{…
阅读更多...
【五一创作】ERP实施-委外业务-委外采购业务

【五一创作】ERP实施-委外业务-委外采购业务

委外业务主要有两种业务形态&#xff1a;委外采购和工序外协&#xff0c;委外采购主要是在MM模块中实现&#xff0c;工序外协主要由PP模块实现&#xff0c;工序外协中的采购订单创建和采购收货由MM模块实现。 委外采购概念 委外采购&#xff0c;有些企业也称为带料委外或者分包…
阅读更多...
牛客刷SQL题Day5

牛客刷SQL题Day5

SQL69 返回产品并且按照价格排序 select prod_name , prod_price from Products where prod_price between 3 and 6 select prod_name , prod_price from Products where 6>prod_price and prod_price >3 踩坑1&#xff1a; between......and.......包括边界。 踩坑2&am…
阅读更多...
网卡丢失导致集群异常

网卡丢失导致集群异常

假期晚上有个电话&#xff0c;说集群故障&#xff0c;应用无法连接&#xff0c;节点一可以ssh登录&#xff0c;节点二已无法正常登录了&#xff0c;在节点一上需要ssh 私网ip地址才可以登录节点二&#xff0c;虽不是重点客户&#xff0c;有问题还是需要积极处理。 首先看集群状…
阅读更多...
Cartesi 2023 年 4 月回顾

Cartesi 2023 年 4 月回顾

查看你不想错过的更新 2023年5月1日&#xff0c;感谢Cartesi生态系统中所有了不起的构建者&#xff01; 在一个激动人心的旅程之后&#xff0c;我们的首届全球线上黑客马拉松正式结束了&#xff01;有超过200名注册建造者参加&#xff0c;见证了所有参与者展示的巨大才华和奉献…
阅读更多...
有必要给孩子买台灯吗？分享四款高品质的护眼台灯

有必要给孩子买台灯吗？分享四款高品质的护眼台灯

有必要使用护眼台灯&#xff0c;尤其是有近视现象的孩子们。 现在很多孩子小学就开始近视了&#xff0c;保护视力刻不容缓呀! 很多人不知道&#xff0c;其实劣质光线是最大的眼睛杀手 给孩子随便买便宜的台灯&#xff0c;看着一样能用&#xff0c;其实时间久了 对孩子眼睛的…
阅读更多...
SpringCloud：ElasticSearch之RestClient查询文档

SpringCloud：ElasticSearch之RestClient查询文档

文档的查询同样适用RestHighLevelClient对象&#xff0c;基本步骤包括&#xff1a; 1&#xff09;准备Request对象2&#xff09;准备请求参数3&#xff09;发起请求4&#xff09;解析响应 1.快速入门 我们以match_all查询为例 1.1.发起查询请求 代码解读&#xff1a; 第一步…
阅读更多...
【《中国工业经济》数据复现】数字化转型与企业分工：专业化还是纵向一体化

【《中国工业经济》数据复现】数字化转型与企业分工：专业化还是纵向一体化

一.研究内容 本文使用机器学习方法刻画微观企业数字化水平&#xff0c;并在构建数理模型的基础上实证考察了企业数字化转型对企业分工的影响及其机理。结果表明&#xff0c;企业数字化转型显著提升了中国上市企业专业化分工水平。机制分析表明&#xff0c;数字化转型对企业专业…
阅读更多...
ReentrantLock原理剖析

ReentrantLock原理剖析

前言 本文主要讲解底层逻辑&#xff0c;基本不会贴代码&#xff0c;目的是让大家能够真正的知晓原理&#xff0c;对照着逻辑去理解代码看代码也会很快就能看懂。 在讲ReentrantLock原理之前&#xff0c;我们先回顾下ReentrantLock的基本用法。ReentrantLock是一个锁编程api&am…
阅读更多...
考研机试刷题第二天：任意进制转任意进制【高进度短除法】

考研机试刷题第二天：任意进制转任意进制【高进度短除法】

理一下思路&#xff1a; 看了y总的视频之后我觉得这道题其实只需要对上次写的进制转换微微做一下调整即可。 于是我写出了下面的代码 #include <iostream> #include <vector> #include <algorithm> #include <cstring>using namespace std;vector<…
阅读更多...
Moonbeam操作指南｜如何使用Gelato创建自动化任务

Moonbeam操作指南｜如何使用Gelato创建自动化任务

Gelato是一个Web3去中心化自动化网络&#xff0c;允许开发者横跨多个基于EVM兼容区块链上自动化和连接任意的智能合约执行。&#x1f4d1;阅读中文版详细操作教程 举例来说&#xff0c;我们将使用MetaMask作为钱包。同时&#xff0c;您的钱包余额中需要有一些GLMR用于支付自动…
阅读更多...
基于海洋捕食者算法的极限学习机(ELM)回归预测-附代码

基于海洋捕食者算法的极限学习机(ELM)回归预测-附代码

基于海洋捕食者算法的极限学习机(ELM)回归预测 文章目录 基于海洋捕食者算法的极限学习机(ELM)回归预测1.极限学习机原理概述2.ELM学习算法3.回归问题数据处理4.基于海洋捕食者算法优化的ELM5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;本文利用海洋捕食者算法对极限学习…
阅读更多...
深度学习笔记--本地部署Mini-GPT4

深度学习笔记--本地部署Mini-GPT4

目录 1--前言 2--配置环境依赖 3--下载权重 4--生成 Vicuna 权重 5--测试 6--可能出现的问题 1--前言 本机环境&#xff1a; System: Ubuntu 18.04 GPU: Tesla V100 (32G) CUDA: 10.0 项目地址&#xff1a;https://github.com/Vision-CAIR/MiniGPT-4 2--配置环境依赖 …
阅读更多...
python面试题

python面试题

文章目录 赋值、深拷贝和浅拷贝有什么区别&#xff1f;元组和列表有什么不同&#xff1f;和is有什么不同&#xff1f;集合怎么转字典&#xff1f;字典怎么遍历&#xff1f;如何在Python中实现多线程&#xff1f;如何实现tuple和list的转换&#xff1f;实现删除一个list里面的重…
阅读更多...
智能无人蜂群作战系统适应性进化模型仿真研究

智能无人蜂群作战系统适应性进化模型仿真研究

源自&#xff1a;系统仿真学报 作者&#xff1a;李志强, 李元龙, 殷来祥, 马向平 摘 要 智能无人蜂群作战系统主要由有限行为能力的大规模作战个体组成&#xff0c;一般不具备应对复杂战场环境和作战对手变化的适应能力。采用遗传算法与增强学习相结合的方法探索构建基于个体…
阅读更多...
Tre靶场通关过程（linpeas使用+启动项编辑器提权）

Tre靶场通关过程（linpeas使用+启动项编辑器提权）

Tre靶场通关 通过信息收集获得到了普通用户账号密码&#xff0c;利用PEASS-ng的linpeas脚本进行提权的信息收集&#xff0c;根据已有信息进行提权。 靶机下载地址&#xff1a; https://download.vulnhub.com/tre/Tre.zip 信息收集 靶机IP探测&#xff1a;192.168.0.129 a…
阅读更多...
最新文章

Copyright @ 2022~2023