数据结构之 --数组
数组是应用的最广泛的数据存储结构,它被植入到大部分编程语言中;
对象的名字就是该对象对应内存地址的引用,并不是对象的本身;
如何使用面向对象操作数据结构:
首先将数据存储结构从程序需中分离出,程序的其他部分称为使用这个结构的用户;第二部则是改进存储结构和用户之间的通信;
学会将程序划分成类:
解释:数据存储结构本身就是累,程序中使用这个结构的部分也是类,通过将长须划分成两个类,可以使程序的功能清晰,使之更加容易设计和
理解;
抽象的概念:
从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开始,但...
数据结构课程中,对于数组和广义表的讲解。适合本科生使用。
### 数据结构之数组 #### 一、数组的基本概念与定义 **数组(Array)**是一种非常重要的基本数据结构之一,它由一系列相同数据类型的元素组成。数组中的每一个元素都可以通过索引或者下标来唯一标识。 ##### 定义 ...
数据结构数组好资源PPT
### 数据结构多维数组课程设计知识点解析 #### 一、问题背景与目标 在计算机科学领域,特别是数据结构的学习和应用中,多维数组是一种重要的数据组织方式。它能够有效地处理多维数据,如图像处理、矩阵运算等场景...
数据结构c++ 数组和矩阵 【7】Chapter4 数组和矩阵
这些例子都是为了帮助开发者掌握C++中结构数组和指针的运用技巧,理解数据结构的基础和复杂性,从而提升程序设计能力。在实际编程中,熟练运用这些技术可以提高代码的可读性和效率,对于理解和解决复杂问题至关重要...
在数据结构的学习中,多维数组是一个至关重要的概念,它为理解和处理复杂的数据组织提供了基础。多维数组,顾名思义,是数组的一种扩展形式,可以看作是由多个一维数组按照特定规则排列而成的结构。在本课程设计中,...
### 数据结构数组的迭代 #### 数组的概念 数组是一种基本的数据结构,用于存储具有相同类型的一组数据元素。每个元素可以通过其索引来访问,索引通常是从0开始的整数。数组的主要优点包括: - **快速访问**:由于...
该课件是数据结构数组和广义表部分的课件,是基于C语言描述的。
在易语言中,自定义数据类型是实现复杂数据结构和逻辑的重要手段。本话题聚焦于“易语言自定义数据类型数组排序”,将深入探讨如何在易语言中创建、操作自定义数据类型数组,并实现各种排序算法,如根据产地、类别和...
Java 希尔排序 算法 数据结构 数组 输出
Java 选择排序 算法 数据结构 数组 输出
Java 基数排序 排序 算法 数据结构 数组 输出
"数据结构数组和稀疏矩阵PPT学习教案.pptx" 本资源主要介绍了数据结构中的数组和稀疏矩阵的概念、性质和存储结构。下面是对该资源的详细总结: 一、数组的定义和性质 数组是一种数据结构, 由n(n>1)个相同类型的...
### Java 数据结构详解:数组、向量与字符串 在Java编程语言中,数据结构是组织和存储数据的关键组件,能够高效地访问和修改数据。本文将深入探讨三种基本的数据结构——数组、向量和字符串,它们在Java开发中占据...
这样的设计使得结构数组成为处理复杂数据结构,如记录、配置设置或具有多个相关属性的对象时的理想选择。 标题"结构数组 matlab"所暗示的,这个压缩包文件可能包含了关于MATLAB中结构数组使用的程序示例。`struct1....