首页 > 编程语言 >数据结构 顺序表(C语言 与 Java实现)以及部分练习题

数据结构 顺序表(C语言 与 Java实现)以及部分练习题

时间：2024-05-30 13:35:48浏览次数：34  
标签：练习题 Java nums int 元素 C语言 数组 printf return

目录

数据结构

数组(顺序表)

  • 一组相同数据类型的集合
  • 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. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列
int removeDuplicates(int* nums, int numsSize){
    /*
    快慢指针
    */
    int slow = 1;//快指针
    int fast = 1;
    while(fast<numsSize){
      if(nums[fast]!=nums[fast-1]){
          nums[slow]=nums[fast];
          ++slow;
      }
      ++fast;
    }
    return slow;
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int p=0;
        int q = 1;
        //快慢指针 快指针不停地去寻找不同的值,然后替换慢指针的下一个位置
        if(nums==null||nums.length==0)return 0;
        while(q<nums.length){
            if(nums[p]!=nums[q]){
                if(q-p>1)nums[p+1]=nums[q];//判断
                p++;
            }
            q++;
        }
        return p+1;
    }
}

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution {
    public int[] twoSum(int[] nums, int target) {
    int[] numsSum = new int[2];
            if(nums==null||nums.length<2)return numsSum;
            int len = nums.length;
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            for(int i=0;i<nums.length;++i){
                hashMap.put(nums[i],i);
            }
            int temp=0;
            for(int i=0;i<nums.length;++i){
                temp = target - nums[i];
                if(hashMap.containsKey(temp)&&hashMap.get(temp)!=i){
                    numsSum = new int[]{i, hashMap.get(temp)};
                }
            }
            return numsSum;
            
    }    

}

优化

    public int[] twoSum(int[] nums, int target) {
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            for(int i=0;i<nums.length;++i){
                  if(hashMap.containsKey(target - nums[i])){
                    return new int[]{i, hashMap.get(target - nums[i])};
                }
                hashMap.put(nums[i],i);
            }
            return null;
    }    

}

27. 移除元素

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

485. 最大连续 1 的个数

414. 第三大的数

2656. K 个元素的最大和

LCP 06. 拿硬币

2057. 值相等的最小索引

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

2125. 银行中的激光束数量

27. 移除元素

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

标签：练习题,Java,nums,int,元素,C语言,数组,printf,return
From： https://www.cnblogs.com/cwyYYDS/p/18222141

相关文章

  • 基于Java+Vue的园区智能化管理系统：综合管控，推进数字化转型（代码分享）
    前言：智慧园区管理平台是一个集成了多种功能的综合性系统，旨在通过信息化、智能化手段提升园区的管理效率和服务质量。以下是针对系统的各个功能模块的简要描述：一、楼栋管理会务管理：管理园区内的会议预约、会议室使用等。园区信息：展示园区的基本信息，如位置、面积、规划等。楼......
  • Java中Comparable接口和Comparator接口的区别（如果想知道Java中Comparable接口和Compar
        前言：在Java中，Comparable接口和Comparator接口都用于对象之间的比较和排序，但它们在使用和设计上存在一些关键的区别。✨✨✨这里是秋刀鱼不做梦的BLOG✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客        本篇文章主要讲解的是J......
  • JavaSE 面向对象程序设计 文件File 介绍练习加千行代码详解
    介绍在Java中，File类是用于表示文件和目录路径的抽象。它提供了一组方法来创建、删除、重命名、检查文件/目录的存在性、以及查询文件/目录的属性等功能。File类可以用于执行文件系统操作，如创建新文件、删除文件、检查文件是否存在等。目的是把字符串先表示为路径然后转化......
  • Java 五种内部类演示及底层原理详解
    内部类什么是内部类在A类的内部定义B类，B类就被称为内部类发动机类单独存在没有意义发动机为独立个体可以在外部其他类里创建内部类的对象去调用方法类的五大成员属性方法构造方法代码块内部类内部类的访问特点内部类可以直接访问外部类的成员，包括私有外部类要......
  • java+sql企业固定资产管理系统
    摘要：本文主要介绍的是固定资产管理系统的整个设计过程。第1章的绪论包括选题的背景，目的和意义，国内外现状；第2章平台简介包括JBuilder2005和SQLServer数据库的介绍；第3章系统分析，需求分析，数据流与数据字典，功能需求；第4章系统设计部分包括系统总体设计，功能模块设计，数据库设计；第5章......
  • 使用Java API 操作MongoDB
    除了通过启动mongo进程进入Shell环境访问数据库外，MongoDB还提供了其他基于编程语言的数据库访问方法。MongoDB官方提供了编程语言的驱动包，利用这些驱动包可以使用编程方法连接并操作MongoDB数据库。想要使用 Java程序操作 MongoDB，需要确保您的电脑上已经安装了Mong......
  • 为何Java抽象类是代码架构的基石？
    效率工具推荐一个程序员的常用工具网站，效率加倍嘎嘎好用：程序员常用工具云服务器云服务器限时免费领：轻量服务器2核4G腾讯云：2核2G4M云服务器新老同享99元/年，续费同价阿里云：2核2G3M的ECS服务器只需99元/年，续费同价为何Java抽象类是代码架构的基石？Java抽象类是面向对象编......
  • Java毕业设计-基于springboot开发的旅游网站-毕业论文（附毕设源代码）
    文章目录前言一、毕设成果演示（源代码在文末）二、毕设摘要展示1、开发说明2、需求/流程分析3、系统功能结构三、系统实现展示1、用户信息管理2、旅游动态管理3、景点信息管理4、公告信息管理四、毕设内容和源代码获取总结Java毕业设计-基于springboot开发的旅游网站-......
  • Java开发工具|推荐收藏
    Java是一种广泛使用的编程语言，拥有多种开发工具，包括集成开发环境（IDE）和代码编辑器。以下是几种常见的Java开发工具以及它们的比较：Eclipse是一款流行的开源IDE，广泛用于Java开发。它具有强大的代码编辑、调试和性能分析功能，支持插件扩展，可以满足不同开发需求。Eclipse......
  • java泛型基础
    ​ 一、泛型介绍： JDK5除了推出foreach新循环，还推出了一个新特性:泛型泛型作用：在一个类或接口的声明处指定该类中某个属性的类型。或声明方法返回值的类型或方法参数的类型  泛型也称为参数化类型。它允许我们在一个类或接口的声明处指定该类中某个属性的类型或  ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99