数据结构算法 数组的实现与练习(C语言实现,Java实现)

文章目录

  • 数据结构
  • 数组(顺序表)
    • 特点
    • 使用Java实现更高级的数组
    • C语言实现
    • 总结
      • 优点
      • 缺点
    • 例题
      • [26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)
      • [1. 两数之和](https://leetcode.cn/problems/two-sum/)
      • [27. 移除元素](https://leetcode.cn/problems/remove-element/)
      • [153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/)
      • [485. 最大连续 1 的个数](https://leetcode.cn/problems/max-consecutive-ones/)
      • [414. 第三大的数](https://leetcode.cn/problems/third-maximum-number/)
      • [2656. K 个元素的最大和](https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/)
      • [LCP 06. 拿硬币](https://leetcode.cn/problems/na-ying-bi/)
      • [2057. 值相等的最小索引](https://leetcode.cn/problems/smallest-index-with-equal-value/)
      • [26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)
      • [2125. 银行中的激光束数量](https://leetcode.cn/problems/number-of-laser-beams-in-a-bank/)
      • [27. 移除元素](https://leetcode.cn/problems/remove-element/)
      • [1431. 拥有最多糖果的孩子]

数据结构

数组(顺序表)

  • 一组相同数据类型的集合
  • image-20240530125359725

特点

  1. 数组在内存中是连续分配的 如上图
  2. 创建时要指明数组的大小
  3. 数组名代表首地址,索引从0开始,到数组的长度-1
  4. 数组一旦创建好,大小不可以改变
  5. 使用索引
    1. 获取索引位置的值 arr[index]
    2. 修改 arr[index] = val
    3. 删除 (假删除)就是把目标元素后面的元素向前位移一格
      1. image-20240530125701713
    4. 遍历,将数组中的元素,依次打印出来

使用Java实现更高级的数组

import java.util.Random;

public class MyArr<T> {

    private int capacity = 0;
    private int size = 0;
    private T[] arr;

    public MyArr(int capacity) {
        if (capacity < 0) this.capacity = 10; //if no right input, we will initial capacity 10
        this.capacity = capacity;
        this.arr = (T[]) new Object[capacity];
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    public T[] setCapacity(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("扩大小异常");
        }
        this.capacity = capacity;
        T[] newNum = (T[]) new Object[capacity];
        for (int i = 0; i < this.size; ++i) {
            newNum[i] = this.arr[i];
        }
        return newNum;
    }

    //增加元素
    public void add(T val) {
        if (this.size >= this.capacity) {
            this.arr = setCapacity(2 * this.capacity);
        }
        this.arr[this.size++] = val;
    }

    //删除元素
    public boolean removeByIndex(int index) {
        if (index < 0 || index > this.capacity) {
            throw new RuntimeException("数组越界");
        }
        for (int i = index; i < size - 1; ++i) {
            arr[i] = arr[i + 1];
        }
        size--;
        if (size < this.capacity / 4 && this.capacity > 4) {
            arr = setCapacity(this.capacity / 4);
        }
        return true;
    }

    //修改位置元素
    public void modify(int index, T val) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("数组越界");
        }
        arr[index] = val;
    }

    //获取某元素位置
    public int locateVal(T val) {
        for (int i = 0; i < size; ++i) {
            if (arr[i] == val) {
                return i;//return index
            }
        }
        // if no find return -1
        return -1;
    }
    //打印元素


    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append('[');
        for (int i = 0; i < this.size - 1; ++i) {
            stringBuffer.append(arr[i] + ",");
        }
        if(size>0) stringBuffer.append(arr[size - 1]);
        stringBuffer.append(']');
        return stringBuffer.toString();
    }

}

C语言实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <stdlib.h> // 添加头文件以使用malloc和free函数
#define ERROR 0
#define OK 1
#define MAXLENGTH 20
#define List_Increment 10

typedef int Status;//判断程序是否运行成功 0-失败 1-成功
typedef int Element;
typedef struct {
	Element* location;
	int length;//存储数据结构数组长度
	int listsize;//
}SqList;

//初始化顺序表
Status initiElem(SqList *L) {
	//L->location =  Element stu[20];
	L->location =  (Element*)malloc(MAXLENGTH*sizeof(Element));
	L->length = 0 ;
	L->listsize = 0;
	if (L->location == NULL) {
		return ERROR ;//申请内存失败
	}
	return OK;//申请内存成功


}
//插入元素
Status insertElem(SqList* L, int i, Element e) {
	if (L->length == MAXLENGTH) return ERROR;//表饱和
	if (i<1 || i>L->length + 1) return ERROR;
	if (i <= L->length) {
		for (int j = L->length - 1; j >= i - 1; j--) {
			L->location[j + 1] = L->location[j + 1];
		}
		L->location[i-1] = e;
		L->length++;//长度+1
	}
	//若i在末尾直接插入
	L->location [i - 1] = e;
	L->length++;//长度+1
	return OK;
}

//查找元素
int findElem(SqList L, Element e) {
	for (int i = 0; i < L.length; i++) {
		if (L.location[i] == e) {
			return i + 1;//返回第i个元素
		}
	}
	return ERROR;

}
//获取元素
Status getElem(SqList L, int i, Element* e) {
	if (i < 1 || i>L.length )return ERROR;
	e = L.location[i];//把第i各元素返回给Element类型数据
	return OK;
}
//删除操作
Status deleElem(SqList* L, int i) {
	if (L->length == 0)return ERROR;//此时为空表
	if (i<1 || i>L->length) return ERROR;//位置不合理

	//删除后面元素前移
	for (int j = i; j < L->length;j++) {
		L->location[j - 1] = L->location[j];
	}
	L->length--;
	return OK;//删除成功
}

int main1() {
	SqList L;
	Element element=0;
	int choice;
	int index;//插入位置
	
	while (OK) {
		printf("---欢迎使用链表查询系统-----\n");
		printf("--------1-初始化链表--------\n");
		printf("--------2-插入链表元素------\n");
		printf("--------3-查找元素----------\n");
		printf("--------4-删除元素----------\n");
		printf("--------5-获取元素----------\n");
		printf("--------6-遍历元素----------\n");
		printf("--------7-退出系统----------\n");
		scanf("%1d", &choice);
		switch (choice)
		{
		case 1:
			//调用initiElem函数开始初始化
			if (initiElem(&L) == NULL) {
				printf("初始化失败!\n");
				return ERROR;
			}
			printf("初始化成功!\n");
			break;
		case 2:
			printf("请输入你想插入的元素(整数):\n");
			scanf("%d", &element);
			printf("请输入你想插入的位置:\n");
			scanf("%d", &index);
			if (insertElem(&L, index, element) == 0) {
				printf("插入失败!\n");
				break;
			}
			printf("插入成功!\n");
			break;
		case 3:
			printf("请输入你想查找的元素(整数):\n");
			scanf("%d", &element);
		
			if (findElem(L,element) == 0) {
				printf("查找失败\n");
				break;
			}

			printf("该元素在第%d个位置\n", findElem(L,element));
			break;

		case 4:
			printf("请输入你想删除的元素(位置):\n");
			scanf("%d", &index);
			if (deleElem(&L,index) == 0) {
				printf("删除失败!\n");
				break;
			}
			printf("删除成功!\n");
			break;
		case 5:
			printf("请输入你想获取元素的位置:\n");
			scanf("%d", &index);
			if (getElem(L, index, &element) == 0) {
				printf("获取失败!");
				break;
			}
			printf("第%d的元素为 %d", index + 1, element);
			break;
		case 6:
			if (L.length == 0) {
				printf("为空表,无法遍历");
				break;
			}
			for (int i = 0; i < L.length; i++) {
				printf("%d\n", *(L.location+i));
			}
			break;
		default:
			break;
		}
	}
}

总结

优点

1.由于是根据下表查找数据,则数组(顺序表)查找速度快时间复杂度O(1)

缺点

1.因为每次删除元素,或者插入数组时,每个数据都需要向后或者向前位移则平均时间复杂度为O(n),所以插入或删除速度慢

例题

26. 删除有序数组中的重复项

1. 两数之和

27. 移除元素

153. 寻找旋转排序数组中的最小值

485. 最大连续 1 的个数

414. 第三大的数

2656. K 个元素的最大和

LCP 06. 拿硬币

2057. 值相等的最小索引

26. 删除有序数组中的重复项

2125. 银行中的激光束数量

27. 移除元素

[1431. 拥有最多糖果的孩子]

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

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

相关文章

教育数字展馆助力全球教育传播，科技引领数字化教育潮流

教育数字展馆助力全球教育传播，科技引领数字化教育潮流

一、教育数字展馆助力教育传播 1、提高教育资源的可及性 教育数字展馆通过VR和WEB3D技术&#xff0c;将丰富的教育资源呈现在用户面前。不论是名校的经典课程&#xff0c;还是专家的精彩讲座&#xff0c;均可通过教育数字展馆实现线上展示。用户只需登录平台&#xff0c;即可…
阅读更多...
【解决】Tree prefab at index 8 is missing.

【解决】Tree prefab at index 8 is missing.

开发平台&#xff1a;Unity 2020 版本以上   问题描述 翻译&#xff1a;树预制体集合中第8位预制体丢失。   解决方法&#xff1a;修复丢失树资产 关联 Unity Terrier 组件使用&#xff0c;前往 树绘制工作区&#xff0c;检查 “树资产” 引用是否丢失&#xff1f;删除或重…
阅读更多...
Mysql基础教程（10）：LIMIT

Mysql基础教程（10）：LIMIT

MySQL LIMIT 用法与实例 在 MySQL 中&#xff0c;我们使用 LIMIT 子句来限定 SELECT 语句返回的行的数量。 MySQL LIMIT语法 该 LIMIT 子句可用于限制 SELECT 语句返回的行数。 LIMIT 接受一个或两个非负数正数作为参数。 LIMIT 子句的语法如下&#xff1a; LIMIT [offset,…
阅读更多...
CDH6.3.2集成Flink1.12.2

CDH6.3.2集成Flink1.12.2

一、Linux下载httpd服务并开启 yum install y httpd systemctl start httpd systemctl enable httpd 二、获取已制作好的安装包 flink-1.12.2-bin-scala_2.11.tar ​ FLINK_ON_YARN-1.12.2.jar ​ flink-shaded-hadoop-2-uber-3.0.0-cdh6.3.2-10.0.jar 三、集成CM 1.上传编…
阅读更多...
K210视觉识别模块学习笔记2：固件的下载升级_官方数字识别例程导入方法

K210视觉识别模块学习笔记2：固件的下载升级_官方数字识别例程导入方法

今日开始学习K210视觉识别模块:固件的下载升级_官方数字识别例程导入方法 主要学习如何升级固件库&#xff0c;在哪下载固件库&#xff0c;以及如何在TF卡正确导入官方例程&#xff1a; 亚博智能的K210视觉识别模块...... 本次最终目的是正确导入官方的数字识别例程&#xff0…
阅读更多...
[GESP202306 四级] 幸运数

[GESP202306 四级] 幸运数

按照题目做就OK了&#xff08;本蒟蒻写得太烂了&#xff09; #include<bits/stdc.h> using namespace std; long long w(long long n) {if(n1||n0){return n*7;}n*7;long long tsgn,s0;while(true){s0;while(tsg!0){stsg%10;tsg/10;}if(s<9){return s;}tsgs;} } bool…
阅读更多...
可编程晶体振荡器应用于车载倒车雷达

可编程晶体振荡器应用于车载倒车雷达

倒车雷达&#xff0c;即“倒车防撞雷达”&#xff0c;又称“"停车辅助装置”&#xff0c;是汽车停车或倒车时的安全辅助装置。它主要由超声波传感器、控制器和显示器等组成&#xff0c;可以通过声音或更直观的显示告知驾驶员周围的障碍物&#xff0c;解除驾驶员在停车、倒…
阅读更多...
【软件测试】软件测试概念 | 测试用例 | BUG | 开发模型 | 测试模型 | 生命周期

【软件测试】软件测试概念 | 测试用例 | BUG | 开发模型 | 测试模型 | 生命周期

文章目录 一、什么是软件测试1.什么是软件测试2.软件测试和调试的区别测试人员需要的素养 二、软件测试概念1.需求1.需求的定义2.测试人员眼中的需求 2.测试用例1.测试用例概念 3.BUG 软件错误4、开发模型和测试模型1.软件的生命周期2.开发模型1.瀑布模型2.螺旋模型3.增量、迭代…
阅读更多...
2024年人工智能与机械自动化技术国际会议( ICAIMAT 2024)

2024年人工智能与机械自动化技术国际会议( ICAIMAT 2024)

2024年人工智能与机械自动化技术国际会议( ICAIMAT 2024) 会议简介 随着科技的飞速发展&#xff0c;人工智能和机械化自动化技术已成为全球产业升级和经济发展的重要动力。为了进一步促进国际交流与合作&#xff0c;推动人工智能和机械化自动化技术的创新与应用&#xff0c;我…
阅读更多...
2024年艺术鉴赏与科学教育国际会议（ICAASE 2024）

2024年艺术鉴赏与科学教育国际会议（ICAASE 2024）

2024年艺术鉴赏与科学教育国际会议 2024 International Conference on Art Appreciation and Science Education 【1】会议简介 2024年艺术鉴赏与科学教育国际会议是一场集艺术、科学和教育于一体的国际性学术盛会。本次会议旨在推动艺术鉴赏与科学教育领域的深入交流与合作&am…
阅读更多...
电脑提示缺少vcruntime140_1.dll的解决方法，总结7种有效方法

电脑提示缺少vcruntime140_1.dll的解决方法，总结7种有效方法

vcruntime140_1.dll是Microsoft Visual C 2015运行时库的一部分&#xff0c;它为使用Visual Studio 2015开发的应用程序提供了必要的运行时组件。该文件支持C程序的执行&#xff0c;包括内存管理、输入输出操作以及多线程功能等。缺失或损坏此文件可能导致应用程序无法启动或运…
阅读更多...
Redis实战篇3：优惠券秒杀

Redis实战篇3：优惠券秒杀

说明 该实战篇基于某马的Redis课程中的《某马点评项目》。非常适合有相关经验、缺少企业级解决方案&#xff0c;或者想要复习的人观看&#xff0c;全篇都会一步一步的推导其为什么要这么做&#xff0c;分析其优缺点&#xff0c;达到能够应用的地步。 本实战篇中心思想就是把项目…
阅读更多...
谷歌Material Design设计标准指南

谷歌Material Design设计标准指南

Material Design是谷歌的Android设计规范。虽然这种优秀的设计语言应用于Android&#xff0c;但它的本质被许多设计师借鉴&#xff0c;并用于自己的设计。它是一个广泛的UX、UI设计师必须学习优秀的设计规范。 现在&#xff0c;Material Design设计规范已正式内置为即时设计&a…
阅读更多...
MySQL -- SQL笔试题相关

MySQL -- SQL笔试题相关

1.银行代缴花费bank_bill 字段名描述serno流水号date交易日期accno账号name姓名amount金额brno缴费网点 serno: 一个 BIGINT UNSIGNED 类型的列&#xff0c;作为主键&#xff0c;且不为空。该列是自动增量的&#xff0c;每次插入新行时&#xff0c;都会自动递增生成一个唯一的…
阅读更多...
【AIGC】大型语言模型在人工智能规划领域模型生成中的探索

【AIGC】大型语言模型在人工智能规划领域模型生成中的探索

大型语言模型在人工智能规划领域模型生成中的新应用 一、引言二、LLM在规划领域模型生成中的潜力三、实证分析&#xff1a;LLM在规划领域模型生成中的表现四、代码实例&#xff1a;LLM在规划领域模型生成中的应用五、结论与展望 一、引言 随着人工智能技术的迅猛发展&#xff0…
阅读更多...
String类详解

String类详解

前言&#xff1a;String类是表示字符串的类&#xff0c;String类的内部也提供了非常多的方法来供程序员使用。 String类还有一大特性&#xff0c;就是不可变性。只要使用string创建了字符串&#xff0c;就不可以修改。为string类提供了一层安全性。&#xff08;对于" &qu…
阅读更多...
Android 11.0 系统设置语言和输入法菜单Launage语言列表增加支持多种英语语言功能

Android 11.0 系统设置语言和输入法菜单Launage语言列表增加支持多种英语语言功能

1.前言 在11.0的系统ROM产品定制化开发中，在系统中的语言和输入法菜单中，在添加语言的默认列表中对于同一类型的语言就可以会出现一中语言，比如多种英语类型 就显示的不全，所以要求显示所有的英语类型，这样就需要了解语言列表的加载流程然后加载所有的英语类型，接下来具…
阅读更多...
Qt 5桌面APP开发实战

Qt 5桌面APP开发实战

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 第一节&#xff1a;Qt 5桌面APP开发实战入门 Qt 5的跨平台特性 Qt 5的界面设计工具 Qt 5的…
阅读更多...
硬盘重新分区后数据丢失，如何高效恢复？

硬盘重新分区后数据丢失，如何高效恢复？

在数字化时代&#xff0c;硬盘作为我们存储重要数据的“仓库”&#xff0c;承载着工作文件、家庭照片、视频资料等众多不可替代的信息。然而&#xff0c;有时因为误操作或系统需要&#xff0c;我们可能会对硬盘进行重新分区&#xff0c;结果却发现宝贵的数据不见了。面对这种情…
阅读更多...
vue3学习（五）

vue3学习（五）

前言 接上一篇笔记&#xff0c;继续Router路由相关入门知识学习&#xff0c;笔记与code示例&#xff0c;分享学习&#xff0c;大佬请忽略。 一、Router路由入门知识点 入门知识点就这些&#xff0c;其他心法可以去官网继续深造。 二、code示例 按照前面分享的“webstorm新建v…
阅读更多...
最新文章

Copyright @ 2022~2023