`
1140566087
  • 浏览: 559255 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
博客专栏
2c4ae07c-10c2-3bb0-a106-d91fe0a10f37
c/c++ 入门笔记
浏览量:18535
3161ba8d-c410-3ef9-871c-3e48524c5263
Android 学习笔记
浏览量:314146
Group-logo
J2ME 基础学习课程集
浏览量:18750
A98a97d4-eb03-3faf-af96-c7c28f709feb
Spring 学习过程记录...
浏览量:17581
社区版块
存档分类
最新评论

数据结构 数组的介绍

阅读更多
数据结构之 --数组

数组是应用的最广泛的数据存储结构,它被植入到大部分编程语言中;

对象的名字就是该对象对应内存地址的引用,并不是对象的本身;

如何使用面向对象操作数据结构:
首先将数据存储结构从程序需中分离出,程序的其他部分称为使用这个结构的用户;第二部则是改进存储结构和用户之间的通信;

学会将程序划分成类:
解释:数据存储结构本身就是累,程序中使用这个结构的部分也是类,通过将长须划分成两个类,可以使程序的功能清晰,使之更加容易设计和
理解;

抽象的概念:
从what中将how分离出来的过程,即类中的操作如何进行,相对什么事类用户可见的,被称为抽象。抽象是软件工程的重要方面。
把类的功能抽象出来后,可以使程序设计更简单,因为不需要在设计的初期就考虑细节问题;

小贴士:用来存储数据对象的类有时被称为容器类;(container class);

在数组中的查找方式:
线性查找:按顺序,逐一的进行匹配;
二分查找:将数组数据项范围不断对半分割来查找特定的数据项。在有序数组中占有很大的优势;

二分查找的核心代码:

/* 使用二分查找的算法 */
	long[] b = {1,2,3,4,5,6,7};
	public int find(long searchKey){
		int lower = 0;
		int upper = b.length-1;	//
		int current;
		
		while(true){
			current = (lower+upper)/2;
			if(b[current] == searchKey){
				return current;
			}else if(lower>upper){
				return b.length;
			}else{
				if(b[current]<searchKey){
					lower = current+1;
				}else{
					upper = current-1;
				}
			}
		}
		
	}


有序数组:
优点:使用有序数组最大的优点是查找的速度比无序数组快的多了;
不足:插入删除比较慢;

对数:使用对数的一个方程可以求出二分查找中步数对应的范围;
每次对范围加倍可以创建出一个数列,它是2的幂;设s表示步数,r表示范围,则:
r=2^s
如果已知步数s,通过该方程可以得出范围r;例如:s=6;r=64;

大 O 表示法:用来评价计算机算法的效率;(粗略的度量方法被称作"大O 表示法");

算法效率示例:

无序数组的插入:无序数组中的插入是见到的唯一一个 与数组中的数据项个数无关的算法,
新数据项总是被放在下一个有空的地方,a[a.length()],然后该值增加,无论数组中
的数据项个数N有多大,一次插入的总是用相同的时间。那么说明:向一个无序数组中插入一个数据项的
时间T是一个常数K:
                        常数  T=K;

线性查找:与N成正比  (N为数据总数)
寻找特定数据项所需的比较次数平均为数据项总数的一半;因此设N为数据项总数,搜索时间
T与N的一半成正比;
T=K*N/2;
二分查找:
T=K*㏒2(N)
说明:由于所有的对数都和其他对数成比例,那么可以将为底数的常数并入K,不指定底数:
T=K*log(N);


大 O 表示法:
大O表示法在上面表示方法的基础上省去了常数K,当比较算法时,并不在乎具体的微处理芯片或
编译器;真正需要比较的是对应不同的N值,T是如何变化的,而不是具体的数字。因此不需要常数;

大O表示法使用大写字符O,可以认为其含义是"order of"(大约是),我们可以使用大O表示
法来描述线性查找使用了O(N)级时间,二分查找使用了O(log N)级时间,向一个无序数组中的插入
使用O(1),或常数级时间;

大O表示法的实质并不是对运行时间给出实际值,而是表达了运行时间是如何受数据项个数所影响的。
除了实际安装后真正测量一次算法的运行时间之外,这可能是对算法进行比较的最有意义的方法了;

0
4
分享到:
评论

相关推荐

    数据结构数组.ppt

    数据结构的数组相关知识,让你掌握数组的知识,会数据结构的数组,可以完成数据结构的数组大题。让你对数据结构的数组有基础的了解。

    数据结构 数组

    数据结构 数组源代码 程序 数组的使用

    数据结构数组的实验报告

    数据结构中的数组是一种基本且重要的数据组织形式,它在计算机科学中扮演着核心角色。数组是一种线性数据结构,其中的元素按照特定的顺序存储,每个元素都可以通过一个唯一的索引来访问。数组的索引通常从0开始,但...

    数据结构 数组和广义表

    数据结构课程中,对于数组和广义表的讲解。适合本科生使用。

    数据结构之数组

    ### 数据结构之数组 #### 一、数组的基本概念与定义 **数组(Array)**是一种非常重要的基本数据结构之一,它由一系列相同数据类型的元素组成。数组中的每一个元素都可以通过索引或者下标来唯一标识。 ##### 定义 ...

    数据结构-数组

    数据结构数组好资源PPT

    数据结构多维数组课程设计

    ### 数据结构多维数组课程设计知识点解析 #### 一、问题背景与目标 在计算机科学领域,特别是数据结构的学习和应用中,多维数组是一种重要的数据组织方式。它能够有效地处理多维数据,如图像处理、矩阵运算等场景...

    数据结构c++ 数组和矩阵

    数据结构c++ 数组和矩阵 【7】Chapter4 数组和矩阵

    数据结构 C++ 详细注释 结构数组及指针的使用7个例子.rar

    这些例子都是为了帮助开发者掌握C++中结构数组和指针的运用技巧,理解数据结构的基础和复杂性,从而提升程序设计能力。在实际编程中,熟练运用这些技术可以提高代码的可读性和效率,对于理解和解决复杂问题至关重要...

    数据结构中有关多维数组的课程设计

    在数据结构的学习中,多维数组是一个至关重要的概念,它为理解和处理复杂的数据组织提供了基础。多维数组,顾名思义,是数组的一种扩展形式,可以看作是由多个一维数组按照特定规则排列而成的结构。在本课程设计中,...

    数据结构数组的迭代

    ### 数据结构数组的迭代 #### 数组的概念 数组是一种基本的数据结构,用于存储具有相同类型的一组数据元素。每个元素可以通过其索引来访问,索引通常是从0开始的整数。数组的主要优点包括: - **快速访问**:由于...

    数据结构数组和广义表课件

    该课件是数据结构数组和广义表部分的课件,是基于C语言描述的。

    易语言自定义数据类型数组排序

    在易语言中,自定义数据类型是实现复杂数据结构和逻辑的重要手段。本话题聚焦于“易语言自定义数据类型数组排序”,将深入探讨如何在易语言中创建、操作自定义数据类型数组,并实现各种排序算法,如根据产地、类别和...

    Java 选择排序 算法 数据结构 数组 输出

    Java 选择排序 算法 数据结构 数组 输出

    Java 希尔排序 算法 数据结构 数组 输出

    Java 希尔排序 算法 数据结构 数组 输出

    Java 基数排序 排序 算法 数据结构 数组 输出

    Java 基数排序 排序 算法 数据结构 数组 输出

    数据结构数组和稀疏矩阵PPT学习教案.pptx

    "数据结构数组和稀疏矩阵PPT学习教案.pptx" 本资源主要介绍了数据结构中的数组和稀疏矩阵的概念、性质和存储结构。下面是对该资源的详细总结: 一、数组的定义和性质 数组是一种数据结构, 由n(n&gt;1)个相同类型的...

    java 数据结构 数组 向量 字符串

    ### Java 数据结构详解:数组、向量与字符串 在Java编程语言中,数据结构是组织和存储数据的关键组件,能够高效地访问和修改数据。本文将深入探讨三种基本的数据结构——数组、向量和字符串,它们在Java开发中占据...

    结构数组 matlab

    这样的设计使得结构数组成为处理复杂数据结构,如记录、配置设置或具有多个相关属性的对象时的理想选择。 标题"结构数组 matlab"所暗示的,这个压缩包文件可能包含了关于MATLAB中结构数组使用的程序示例。`struct1....

Global site tag (gtag.js) - Google Analytics