文档章节

数据结构与算法5

沉迷于编程的小菜菜
 沉迷于编程的小菜菜
发布于 2018/07/23 23:54
字数 573
阅读 3
收藏 0

 二分法采用向下取整的方法

使用有序数组的好处是查找的速度比无序数组快的多,不好的方面是因为要将所有靠后的数据移开,所以速度较慢,有序数组和无序数组的删除操作都很慢。

有序数组在查找频繁的情况下十分管用,但不适用于删除和插入操作。所以适用于公司雇员的数据库,查找频繁,修改频繁。

已知范围,求出完成搜索的步骤,已知r,希望有一个方程可以求出s

s = log2(r)


class OrderArray {
private long[] a;
private int nElems;
public OrderArray(int max)
{
	a = new long[max];
	nElems = 0;
}
public int size()
{
return nElems;	
}
public int find(long searchkey)
{
int lowerBound = 0;
int upperBound = nElems - 1;
int curIn;
while(true)
{
	curIn = (lowerBound + upperBound) / 2;
	if(a[curIn] == searchkey)
		return curIn;
	else if(lowerBound > upperBound)
		return nElems;
	else
	{
		if(a[curIn] < searchkey)
		{	
		lowerBound = curIn + 1;
		return curIn;
	}
		else
			upperBound = curIn - 1;
	}
}
}
public void insert(long value)
{
	int j;
	for(j=0;j<nElems;j++)	
		if(a[j] > value)
		break;
	for(int k=nElems;k>j;k--)
		a[k] = a[k-1];
	a[j] = value;
	nElems++;
}
public boolean delete(long value)
{
	int j = find(value);
	if(j == nElems)
		return false;
	else
	{
		for(int k=j;k<nElems;k++)
		a[k] = a[k+1];
		nElems--;
		return true;
	}
	}
	public void display(){
		for(int j=0;j<nElems;j++)
		System.out.print(a[j] + " ");
		System.out.println(" ");
	}
}
class OrderedApp{
	public static void main(String[] args)
	{
		int maxSize = 100;
		OrderArray arr;
		arr = new OrderArray(maxSize);
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);		
		int searchkey = 55;
		if(arr.find(searchkey) != arr.size())
			System.out.println("found" + searchkey);
		else
			System.out.println("no found" + searchkey);
		arr.display();
		arr.delete(00);
		arr.delete(55);
		arr.delete(99);
		arr.display();
	}
}
found55
0 11 22 33 44 55 66 77 88 99  
11 22 33 66 77 88 99  

存储对象:

数据结构中不光存储long类型的简单变量。存储这些变量简化了程序,但是对如何在现实中使用数据结构来说没有代表性。通常我们存储的数据记录是许多字段的结合。例如一条志愿表由姓名,年龄等组成。

© 著作权归作者所有

共有 人打赏支持
沉迷于编程的小菜菜
粉丝 1
博文 46
码字总数 19097
作品 0
杭州
私信 提问
加载中

评论(2)

沉迷于编程的小菜菜
沉迷于编程的小菜菜
到好多好多:bowtie:
影夜Linux
影夜Linux
一直到几呀?
JAVA数据结构的个人见解之绪论

JAVA数据结构的个人见解之绪论 概念 一般来说用计算机解决问题总是围绕以下三个主要步骤: (1) 抽象出所求解问题中需要处理的数据对象的逻辑模型。(逻辑结构) (2) 根据所求解问题需要完...

狂奔啦蜗牛
2012/08/23
0
0
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
0
0
玩转算法面试:(一)什么是算法面试?

前言 对于面试中遇到的大多数问题 都能有一个合理的思考路径 沟通: 边界条件是怎样的? 数据范围如何? 某些术语是具体如何定义的? 基础数据结构 算法设计思想: 递归分治 贪心 动态规划 ...

天涯明月笙
2017/09/19
0
0
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/04/01
0
0
Android OpenGL开发目录

Android OpenGL开发目录 Android OpenGL开发1--VS2017+OpenGL环境的配置 to be continued... 其它目录 Android NDK开发之旅 目录 Android NDK开发之旅1--NDK介绍 Android NDK开发之旅2--C语言...

香沙小熊
2018/01/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spark in action on Kubernetes - Playground搭建与架构浅析

前言 Spark是非常流行的大数据处理引擎,数据科学家们使用Spark以及相关生态的大数据套件完成了大量又丰富场景的数据分析与挖掘。Spark目前已经逐渐成为了业界在数据处理领域的行业标准。但是...

阿里云官方博客
27分钟前
3
0
小白大数据学习路线

学习大数据首先了解大数据技术得板块划分: 数据计算(离线计算):Hadoop、spark 数据计算(实时计算):storm、spartstreaming、flink 其他框架:zookeeper 数据采集:flume、Kafka 数据存...

董黎明
39分钟前
0
0
mariadb 内存占用优化

本文由云+社区发表 作者:工程师小熊 摘要:我们在使用mariadb的时候发现有时候不能启动起来,在使用过程中mariadb占用的内存很大,在这里学习下mariadb与内存相关的配置项,对mariadb进行调...

腾讯云加社区
今天
4
0
spring security 自定义登录认证

spring security 自定义认证登录 1.概要 1.1.简介 spring security是一种基于 Spring AOP 和 Servlet 过滤器的安全框架,以此来管理权限认证等。 1.2.spring security 自定义认证流程 1)认证...

EasyProgramming
今天
2
0
Win下Jenkins-2.138源码编译及填坑笔记

源码编译篇 1、 安装JDK1.8-181,操作系统添加JDK环境变量。Java -version验证一下。 注:Jenkins2.138版本,JDK必须jkd1.8.0-101以上,不支持Java9,Maven必须3.5.3以上。 2、 解压Maven3....

编程SHA
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部