（一）数据结构和算法、线性结构

文章目录

学习了好几天的数据结构和算法为了半个月之后的蓝桥杯

说实话挺蒙的，但是多敲即便代码把，理解不了旧硬背下来。

课程概述

1.1数据结构概述

1.什么是数据结构：

数据结构是指由相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。

2.数据的存储结构：

  • 顺序存储：顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。

  • 链式存储：链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。

两者之间的区别：

比如看成在食堂打饭

3.数据的逻辑结构：

  • 集合结构：集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。

  • 线性结构：线性结构中的元素存在一对一的相互关系。数据和数据之间是有关系的。

  • 树形结构：树形结构中的元素存在一对多的相互关系。

  • 图形结构：图形结构中的元素存在多对多的相互关系。

1.2算法概述

1.算法的定义：

用来解决问题的思路

是指解题方***而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

2.算法的特性：

  1. 输入
  2. 输出
  3. 有穷性：有限的步骤里，可以执行出结果，不能无限的执行。
  4. 确定性：有一个输入只有一个确定的结果，不能一次结果1，一次结果2。
  5. 可行性：能够解决实际问题。

3.算法的基本要求：

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 时间复杂度：算法占用的时间，运算速度。
  5. 空间复杂度：算法在运行时候占用的内存，占用的资源。

4.demo

从1加到100：没有最好的算法，只有最合适的。

public class AddOneToHandred {
   
	public static void main(String[] args) {
   
		int total=0;
		int end=100;
		//使用FOR循环
		for(int i=1;i<=100;i++) {
   
			total+=i;
		}
		//直接计算
		total=(1+end)*(end/2);
		System.out.println(total);
	}
}

线性结构（一）

2.1数据的基本使用

数组的基本方法

public class TestArray01 {
   
	public static void main(String[] args) {
   
		//创建一个长度为3得数组
		int[] arr1 = new int[3];
		//获取数组长度
		int length1 = arr1.length;
		System.out.println("arrq's length:"+length1);
		//访问数组中的元素：数组名【下标】注意：下标从0开始，最大可以取到长度-1
		int element0 = arr1[0];
		System.out.println("element0:" + element0);
		//为数组中的元素赋值
		arr1[0] = 99;
		System.out.println("element0:"+arr1[0]);
		arr1[1] = 98;
		arr1[2] = 97;
		//遍历数组
		for (int i = 0; i < arr1.length; i++) {
   
			System.out.println("arr1 element"+i+"的值为："+arr1[i]);
		}
		//创建数组的同时为数组中的元素赋值
		int[] arr2 = new int[] {
   23,12,32,34,35};
		System.out.println("arr2 length :"+arr2.length);
	}
}

2.2数元素的添加

import java.util.Arrays;

public class TestOpArray02 {
   
	public static void main(String[] args) {
   
		//解决数组的长度不可变
		int[] arr = new int[] {
   9,8,7};
		//快速查看数组中的元素
		System.out.println("添加元素之前的数组"+Arrays.toString(arr));
		int dst = 6;
		//1.创建一个新数组，长度是原数组+1
		int[] newArr = new int[arr.length+1];
		//2.把原数组中的数据全部复制到新数组中
		for (int i = 0; i < arr.length; i++) {
   
			newArr[i] = arr[i];
		}
		//3.把目标元素放入新数组的最后。新数组最后的下表正好是旧数组的长度
		newArr[arr.length]= dst;
		//4.把新数组替换原数组
	    arr= newArr;
	    System.out.println("添加元素之后的数组"+Arrays.toString(arr));
	}
}

2.3数组元素的删除

import java.util.Arrays;
public class TestOpArray03 {
   
	// 如何删除数组中的元素
	public static void main(String[] args) {
   
		// 目标元素
		int[] arr = new int[] {
    9, 8, 7, 6, 5, 4 };
		System.out.println("删除元素之前" + Arrays.toString(arr));
		// 要删除的元素的下标
		int dst = 0;
		// 创建一个新的数组，长度是原数组元素-1；
		int[] newArr = new int[arr.length - 1];
		// 复制原数组中除了要删除元素以外的其他元素
		for (int i = 0; i < newArr.length; i++) {
   
			// 要删除元素之前的元素
			if (i < dst) {
   
				newArr[i] = arr[i];
			} else {
   
				// 要删除元素之后的元素
				newArr[i] = arr[i + 1];
			}
		}
		// 新数组替换旧数组
		arr = newArr;
		System.out.println("删除元素之后" + Arrays.toString(arr));
	}
}

2.4面向对象的数组

import java.util.Arrays;
public class MyArray04 {
   
	// 创建空数组
	private int[] elements;

	public MyArray04() {
   
		elements = new int[0];
	}

	// 获取数组长度的方法
	public int size() {
   
		return elements.length;
	}

	// 王数组的末尾添加一个元素
	public void add(int element) {
   
		// 创建一个新数组
		int[] newArr = new int[elements.length + 1];
		// 把原数组复制到新数组中的r
		for (int i = 0; i < elements.length; i++) {
   
			newArr[i] = elements[i];
		}
		// 把添加的元素放入新数组中
		newArr[elements.length] = element;
		// 使用新数组替换旧数组
		elements = newArr;
	}


	// 打印所有元素到控制台
	public void show() {
   
		System.out.println(Arrays.toString(elements));
	}

	public void delete(int index) {
   
		// 判断下标是否越界
		if (index < 0 || index > elements.length - 1) {
   
			throw new RuntimeException("下标越界");
		}
		// 创建一个新数组，长度为原数组长度-1
		int[] newArr = new int[elements.length - 1];
		// 复制原有数组到新数组
		for (int i = 0; i < newArr.length; i++) {
   
			// 复制想要删除的元素的前面的元素
			if (i < index) {
   
				newArr[i] = elements[i];
			} else {
   
				// 复制想要删除的后面的元素
				newArr[i] = elements[i + 1];
			}
		}
		// 新数组替换旧数组
		elements = newArr;
	}

	//取出指定位置的元素
	public int get(int index) {
   
		// 判断下标是否越界
		if (index < 0 || index > elements.length - 1) {
   
			throw new RuntimeException("下标越界");
		}
		return elements[index];
	}

	// 如何插入一个元素到指定位置
	public void insert(int index, int element) {
   
		// 创建一个新数组
		int[] newArr = new int[elements.length + 1];
		// 将原数组的元素放入新数组中
		for (int i = 0; i < elements.length; i++) {
   
			// 将原有数组放入新数组中
			// 目标之前的元素
			if (i < index) {
   
				newArr[i] = elements[i];
			} else {
   
				newArr[i + 1] = elements[i];
			}
		}
		// 插入新元素
		newArr[index] = element;
		elements = newArr;

	}
	// 替换指定位置的元素
	public void set(int index, int element) {
   
		// 判断下标是否越界
		if (index < 0 || index > elements.length - 1) {
   
			throw new RuntimeException("下标越界");
		}
		elements[index] = element;
	}
}

测试

import demo01.util.MyArray04;

public class TestMyArray04 {
   
	public static void main(String[] args) {
   
		//创建一个可变的数组
		MyArray04 ma = new MyArray04();
		//王可变元素添加一个元素
		ma.add(99);
		ma.add(98);
		ma.add(97);
		ma.add(96);
		//显示可变数组中的所有元素到控制台
		System.out.println("显示可变数组中的所有元素到控制台");
		ma.show();
		//通过下标删除元素
		System.out.println("通过下标删除元素,删除下标为0的元素");
		ma.delete(0);
		ma.show();
		System.out.println("获取下表元素，获取下标为2的元素");
		//获取下表元素
		int i = ma.get(2);
		System.out.println(i);
		//通过下标添加元素
		System.out.println("添加元素，向下标1的位置添加元素11");
		ma.insert(1,11);
		ma.show();
		//替换指定位置的元素
		System.out.println("替换指定位置的元素,替换下标1的元素为22");
		ma.set(1, 22);
		ma.show();
	}
}

2.5查找算法之线性查找

public class TestSearch05 {
   
	public static void main(String[] args) {
   
		//目标元素
		int a = 10;
		//目标元素所在下标
		int index = -1;
		//目标数组
		int[] arr = new int[] {
   2,3,5,6,8,4,9,0};
		//遍历数组
		for (int i = 0; i < arr.length; i++) {
   
			if(arr[i]==a) {
   
				index = i ;
				break;
			}
		}
		//打印目标元素的下标
		System.out.println("index:"+index);
	}
}

2.6查找二分法之二分法查找

public class TestBinarySearch {
   
	public static void main(String[] args) {
   
		//目标数组
		int[] arr = new int[] {
   1,2,3,4,5,6,7,8,9};
		//目标元素
		int target = 9;
		//记录开始位置
		int begin = 0;
		//记录结束位置
		int end = arr.length-1;
		//记录中间位置
		int mid = (begin+end)/2;
		//记录目标位置
		int index = -1;
		//循环查找
		while(true) {
   
			//判断中间的元素是不是要查找的元素
			if(arr[mid]==target) {
   
				index= mid;
				break;
				//中间这个元素不是要查找的元素
			}else {
   
				//判断中间这个元素是不是比目标元素大
				if(arr[mid]>target) {
   
					//把结束位置调整到中间位置的前一个文位置
					end = mid-1;
					//判断中间这个元素是不是比目标元素大
				}else {
   
					//把开始位置调整到中间位置的后一个位置
					begin = mid +1;
				}
				//取出新的中间位置
				mid = (end+begin)/2;
			}
			
		}
		System.out.println("index:"+index);
	}
}

2.7查找算法整合

import java.util.Arrays;

public class MyArray04 {
   
	// 创建空数组
	private int[] elements;

	public MyArray04() {
   
		elements = new int[0];
	}

	// 获取数组长度的方法
	public int size() {
   
		return elements.length;
	}
	// 线性查找
	public int search(int target) {
   
		for (int i = 0; i < elements.length; i++) {
   
			if (elements[i] == target) {
   
				return i;
			}
		}
		// 没有找到对应的元素
		return -1;
	}
	public int binarySearch(int target) {
   
		int begin = 0;
		// 记录结束位置
		int end = elements.length - 1;
		// 记录中间位置
		int mid = (begin + end) / 2;
		// 循环查找
		while (true) {
   
			// 什么情况下没有这个元素?
			// 开始在结束位置之后或者重合
			if (begin >= end) {
   
				return -1;
			}

			// 判断中间的元素是不是要查找的元素
			if (elements[mid] == target) {
   
				return mid;
				// 中间这个元素不是要查找的元素
			} else {
   
				// 判断中间这个元素是不是比目标元素大
				if (elements[mid] > target) {
   
					// 把结束位置调整到中间位置的前一个文位置
					end = mid - 1;
					// 判断中间这个元素是不是比目标元素大
				} else {
   
					// 把开始位置调整到中间位置的后一个位置
					begin = mid + 1;
				}
				// 取出新的中间位置
				mid = (end + begin) / 2;
			}
		}
	}
}

import demo01.util.MyArray04;
public class TestMyArraySearch0408 {
   
	public static void main(String[] args) {
   
		MyArray04 arr = new MyArray04();
		arr.add(1);
		arr.add(2);
		arr.add(3);
		arr.add(4);
		arr.add(5);

		
		int search = arr.search(3);
		System.out.println("index:"+search);
		
		//调用二分法查找
		int search2 = arr.binarySearch(4);
		System.out.println(search2);
	}
}

2.8栈

<mark>栈的方法</mark>

package demo02;

import javax.management.RuntimeErrorException;

public class MyStack {
   

	//栈的底层使用数组类存储数据
	int[] elements;
	public MyStack() {
   
		elements = new int[0];
	}
	
	//压入元素
	public void push(int element) {
   
		int[] newArr = new int[elements.length+1] ;
		for (int i = 0; i < elements.length; i++) {
   
			newArr[i] = elements[i];
		}
		newArr[elements.length] = element;
		elements = newArr;
	}
	
	//取出站点元素
	public int pop() {
   
		//栈中没有元素
		if(elements.length==0){
   
			throw new RuntimeException("栈是空的");
		}
		//取出数组的最后一个元素
		int element = elements[elements.length-1];
		//创建新数组
		int[] newArr = new int[elements.length-1];
		//原数组中除了最后一个元素的其他元素都放入新的数组中
		for (int i = 0; i < elements.length-1; i++) {
   
			newArr[i] = elements[i];
		}
		//替换数组
		elements =newArr;
		return element;
	}
	//查看栈顶元素
	public int peek() {
   
		if(elements.length==0){
   
			throw new RuntimeException("栈是空的");
		}
		return elements[elements.length-1];
	}
	
	//判断栈是否为空
	public boolean isEmpty() {
   
		return elements.length==0;
	}
	
}

<mark>使用</mark>

package demo02.test;
import demo02.MyStack;
public class TestMyStack {
   
	public static void main(String[] args) {
   
		//创建一个栈
		MyStack  ms = new MyStack();
		System.out.println(ms.isEmpty());
		//压入数据
		ms.push(9);
		ms.push(8);
		ms.push(7);
		ms.push(6);
		//取除栈点元素
		System.out.println(ms.peek());
		System.out.println(ms.pop());
		System.out.println(ms.peek());
		System.out.println(ms.isEmpty());
	}
}

true
6
6
7
false

2.9队列

<mark>队列的方法</mark>

package demo02;

public class MyQueue {
   
	int[] elements ;
	//构造方法
	public MyQueue() {
   
		elements = new int[0];
	}
	//入队
	public void add(int element) {
   
		//创建新数组
		int[] newArr = new int[elements.length+1];
		//把原有数组中的元素复制到新的数组当中
		for (int i = 0; i < elements.length; i++) {
   
			newArr[i] = elements[i];
		}
		//把添加的元素放到新数组中
		newArr[elements.length] = element;
		//使用新数组替换旧数组
		elements = newArr;
	} 
	
	//出队
	public int pool() {
   
		//把数组中的第0个元素取出来
		int element = elements[0];
		//创建一个新的数组
		int[] newArr = new int [elements.length-1];
		//复制原数组中的元素到新数组中
		for (int i = 0; i < newArr.length; i++) {
   
			newArr[i] = elements[i+1];
		}
		elements = newArr;
		return element;
	}
	//判断队列是否为空
	public boolean isEmpty() {
   
		return elements.length==0;
	}
}

<mark>使用</mark>

package demo02.test;

import demo02.MyQueue;

public class TestMyQueue {
   
	public static void main(String[] args) {
   
		//创建队列
		MyQueue mq = new MyQueue();
		//判断是否为空
		System.out.println(mq.isEmpty());
		//入队
		mq.add(9);
		mq.add(8);
		mq.add(7);
		//出队
		System.out.println(mq.pool());
		System.out.println(mq.pool());
		//判断是否为空
		System.out.println(mq.isEmpty());
	}
}
全部评论

相关推荐

11-25 19:36
华北电力大学（保定） Java
点赞 评论 收藏
分享
11-08 16:53
门头沟学院 C++
投票
之前签了个保底三方，只能违约一次，最近有些新offer，想问问牛友的看法
滑模小马达：第三个如果是qfqc感觉还行，我签的qfkj搞电机的，违约金也很高，但公司感觉还可以，听说之前开过一个试用转正的应届生，仅供参考。
点赞 评论 收藏
分享
头像
昨天 17:23
武汉大学 C++
华为（算法工程师）
时间线7.29&nbsp;--&nbsp;投递8.28&nbsp;--&nbsp;笔试（200+/600飘过）8.31&nbsp;--&nbsp;测评9.14&nbsp;--&nbsp;一面9.26&nbsp;--&nbsp;线下二三面最终结果：应该是寄了，对接人主动降温，建议我签一个保底。只能说大概率是一面面评抽象了，无缘华为了一面（50min左右）抽象至极的一面，面试官感觉完全不懂SLAM，我说我是图优化框架，面试官问我图是怎么处理的呢。我说是指图有哪些节点么，面试官说“就是你的图是怎么处理的，图像处理”；然后线上手撕要求白纸写，复盘笔试不告诉你题让你自己想，讲了半天说你做的都是开发，真的有被抽象到，不过就这样都不挂，看来华子一面真不挂人二面（50min左右）二面线下面，明显感受好多了回...
查看6道真题和解析 华为求职进展汇总
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
230996次浏览 2026人参与
# 哪些公司校招卡第一学历 #
32393次浏览 101人参与
# 阿里云管培生offer #
57457次浏览 1739人参与
# 25届秋招总结 #
391552次浏览 3906人参与
# 在职场上，你最讨厌什么样的同事 #
5505次浏览 80人参与
# 地方国企笔面经互助 #
6400次浏览 16人参与
# 北方华创开奖 #
65628次浏览 545人参与
# ai智能作图 #
18991次浏览 239人参与
# 硬件兄弟们 甩出你的华为奖状 #
77679次浏览 624人参与
# 实习，投递多份简历没人回复怎么办 #
2433899次浏览 34693人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4621次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722009次浏览 8545人参与
# 我的实习求职记录 #
6116391次浏览 83923人参与
# 如果再来一次，你还会选择这个工作吗？ #
108228次浏览 1088人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9688次浏览 202人参与
# 游戏求职进展汇总 #
52487次浏览 343人参与
# 夸夸我的求职搭子 #
131875次浏览 1360人参与
# 腾讯求职进展汇总 #
207098次浏览 1693人参与
# 实习想申请秋招offer，能不能argue薪资 #
35662次浏览 308人参与
# 签了三方后想毁约怎么办 #
18381次浏览 110人参与
# 牛客租房专区 #
4428次浏览 120人参与
# 25届机械人为了秋招做了哪些准备？ #
24758次浏览 351人参与
牛客网
牛客企业服务