数据结构篇(绪论)

时间:2024-10-06 07:22:03

目录

一、变量

二、数据类型

1. 系统定义的数据类型(基本数据类型)

2. 用户定义的数据类型(引用类型)

三、数据结构

四、抽象数据类型

五、什么是算法

六、算法五特征

七、为什么需要算法分析

七、算法分析目的

八、如何评判一个算法的好坏

1. 复杂度

2. 正确性

3. 可读性

4. 健壮性

九、复杂度分析

十、时间工具类

TimesUtil


一、变量

计算机变量(computer variables)是计算机语言中能储存计算结果或能表示值抽象概念,变量可以通过变量

名访问。

二、数据类型

1. 系统定义的数据类型(基本数据类型)

Java 语言而言,基本类型共有八种,可以分为三类:

  • 字符类型:char
  • 布尔类型:boolean
  • 数值类型:byte、short、int、long、float、double。

2. 用户定义的数据类型(引用类型)

如果系统自定义的数据类型不够,可以自定义数据类型。

例如:Person、Animal、. . .

三、数据结构

一旦变量中有数据,就需要一种操纵这些数据的机制来求解问题。

数据结构(data structure)就是计算机中存储和组织数据的一种特定方式,它将使得数据处理更加有效。

根据元素的组织方式,数据结构可以分为两种类型:

  • 线性结构:可以按线性次序访问元素,但它并不强制将所有元素连续地存储在一起,例如,链表、栈、队列
  • 非线性结构:这种数据结构的元素是以非线性次序来存储和访问的。例如:树和图。

四、抽象数据类型

抽象数据类型( ADT,Abstract Data Type)是指一个数学模型以及定义在此数学模型上的一组操作。

它通常是对数据的某种抽象,定义了数据的取值范围及其结构形式,以及对数据操作的集合。

抽象数据类型的特征是将使用与实现分离,从而实行封装和隐藏信息。

抽象数据类型通过一种特定的数据结构在程序的某个部分得以实现,只关心在这个数据类型上的操作,而

不关心数据结构具体实现。

五、什么是算法

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令。

算法代表着用系统的方法描述解决问题的策略机制。

六、算法五特征

一个算法应该具有以下五个重要的特征:

(1)有穷性(Finiteness)

算法的有穷性是指算法必须能在执行有限个步骤之后终止;

(2)确切性(Definiteness)

算法的每一步骤必须有确切的定义;

(3)输入项(Input)

一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件

(4)输出项(Output)

一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;

(5)可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时

间内完成(也称之为有效性)。

七、为什么需要算法分析

   首先,算法分析与设计直接影响计算机软件的效率和性能,同时也影响到计算机软件的成功与失败。在

计算机软件中,如果使用的算法更加先进和高效,那么它的运行就更加可靠,更加高效。因此,对于计算

机软件的开发者来说,在进行算法分析与设计上花费一定的精力是非常有必要的,这样可以更好地保证计算机软件的可行性和可靠性。

   此外,算法分析与设计还影响着计算机软件的灵活性和安全性。在算法分析与设计中,需要考虑计算机

软件本身的能力,并利用计算机硬件的特性来构建有效的计算机算法,以保证计算机软件的灵活性和安全

性。比如,当计算机软件遇到复杂的数据输入、硬件环境变化或非常庞大的数据处理量时,可以采用特定

的算法解决方案来优化计算机系统的性能,保证计算机系统的可靠性与安全性。

   最后,算法分析与设计还有助于提高计算机软件的可维护性和可重复使用性。现代软件设计师在设计算法

时,注重算法的可重复性,即将算法分解为可重复使用的基础模块,这样无论是开发者还是用户都可以以

较低的成本进行软件的维护。算法可重复使用,一个算法模块可以在多个软件中被复用,而不需要进行改

变,从而节省了开发者的创新精力,同时也提高了软件的可维护性和可重复使用性。

   综上所述,算法分析与设计有其极其重要的作用,对于计算机软件的可靠性、安全性、灵活性以及可维

护性和可重复使用性都有着不可或缺的重要意义。因此,在开发计算机软件的过程中,开发者应该充分重

视算法分析与设计的重要性,确保计算机软件的可行性和可靠性。

七、算法分析目的

算法分析的目标是根据运行时间及其他的一些因素(如内存、开发者的工作流等)来比较算法(或解决方

案)的优劣。

八、如何评判一个算法的好坏

1. 复杂度

(1)时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说,计算机算法是问题规模 n 的函数f(n),算

法的时间复杂度也因此记做。

(2)空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似,一般都用复杂度

的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

2. 正确性

算法的正确性是评价一个算法优劣的最重要的标准.

3. 可读性

算法的可读性是指一个算法可供人们阅读的容易程度

4. 健壮性

健壮性是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性。

九、复杂度分析

十、时间工具类

TimesUtil

public class TimesUtil {
	private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
	
	public interface Task {
		void execute();
	}
	
	public static void test(String title, Task task) {
		if (task == null) return;
		title = (title == null) ? "" : ("【" + title + "】");
		System.out.println(title);
		System.out.println("开始:" + fmt.format(new Date()));
		long begin = System.currentTimeMillis();
		task.execute();
		long end = System.currentTimeMillis();
		System.out.println("结束:" + fmt.format(new Date()));
		double delta = (end - begin) / 1000.0;
		System.out.println("耗时:" + delta + "秒");
		System.out.println("-------------------------------------");
	}
}