文档章节

数据结构与算法5

沉迷于编程的小菜菜
 沉迷于编程的小菜菜
发布于 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
博文 41
码字总数 18062
作品 0
杭州
加载中

评论(2)

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

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

狂奔啦蜗牛
2012/08/23
0
0
Android OpenGL开发目录

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

香沙小熊
01/07
0
0
玩转算法面试:(一)什么是算法面试?

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

天涯明月笙
2017/09/19
0
0
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

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

Tim_JX
2014/03/24
0
0
【程序猿必备】数据结构与算法精选面试题

有很多计算机科学技术专业的毕业生和程序员申请在Uber和Netflix这样的初创公司、谷歌和阿里巴巴这样的大公司以及Infosys或Luxsoft等以服务为基础的公司从事编程、编码和软件开发工作,但他们...

【方向】
10/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

IDEA中Maven打包时如何跳过测试

方法1:直接使用IDEA提供的方式 Maven命令栏的工具栏有下图中的图标,上面就写着 Skip Tests 按下图标后,如下图,test就不可用了 直接使用package命令即可。 方法2:自己编辑maven命令 进入...

karma123
24分钟前
2
0
Device eth0 does not seem to be present,delaying initialization.

场景:在进行linux 主机克隆的时候,网卡初始化一般都会有问题,最常见的“Device eth0 does not seem to be present,delaying initialization.”,从字面意思 说eth0没有固化,延迟启动。由...

hnairdb
24分钟前
2
0
国内首个区块链试验区在海南成立

据新华社报道,10月8日,海南自贸区(港)区块链试验区正式在海南生态软件园授牌设立,这也是目前为止国内第一个区块链试验区。 该试验区位于海南生态软件园,与试验区同一天成立还有2家研究...

linuxCool
36分钟前
1
0
Java日期和时间获取问题

获取年月日时分秒 Calendar cal = Calendar.getInstance();//获取年int year = cal.get(Calendar.YEAR);//获取月,范围是0-11,最后使用需+1int month = cal.get(Cal...

lanyu96
55分钟前
12
0
Ceph学习笔记2-在Kolla-Ansible中使用Ceph后端存储

环境说明 使用Kolla-Ansible请参考《使用Kolla-Ansible在CentOS 7单节点上部署OpenStack Pike》; 部署Ceph服务请参考《Ceph学习笔记1-Mimic版本多节点部署》。 配置Ceph 以osdev用户登录: ...

LastRitter
59分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部