Please enable Javascript to view the contents

Java-算法 「一」

 ·  ☕ 5 分钟  ·  🤣 lin

Chapter 1

What is algorithm?

算法可以理解为一个完整的解题步骤,由一些基本运算和规定的运算顺序构成。通过这样的解题步骤可以解决特定的问题。从计算机程序设计的角度看,算法由一系列求解问题的指令构成,能够根据规范的输入,在有限的时间内获得有效的输出结果。它代表了用系统的方法来描述解决问题的一种策略机制

The Features

有穷性 确切性 输入 输出 可行性

The Classification

应用领域 结果确定性 算法思路

The Differentiation

算法与公式的关系

公式是一种高度精简的计算方法,可以认为就是一种算法,它属于人类的结晶。而算法不一定是公式,算法的形式可以比公式更复杂,解决的的问题更加广泛

算法与程序的关系

程序设计语言是算法实现的一种形式,也是一种工具。学习一门程序语言是比较容易的,难点在于如何正确合理地运用算法来编写求解问题。

算法与数据结构的关系

Nikklaus Wirth 曾提出一个著名的公式: 数据结构+算法=程序。数据结构往往表示的是处理的对象,算法是计算和处理的核心方法,程序设计语言是算法的实现方法。这几者的综合便构成一个实实在在的程序。

The Representation

自然语言表示

流程图表示

N-S图表示

伪代码表示

The Performance

时间复杂度

空间复杂度

– Sample 1.1 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class main{
    static int N = 8;
    public static void main(String inkhin[]){
        int arr[] = new int[N];
   // 生成随机数
        String value = "";
        for(int i =0; i<N;i++) {
            arr[i] = new Random().nextInt(100);
            value = value + arr[i] + "   "; }
   // 输入欲搜索数字
        Scanner input = new Scanner(System.in);
        System.out.println(value + "\n");
        System.out.println("请输入查找数字:");
        int c =  input.nextInt();
   // 查找内容
        for(int i = 0; i<N; i++) {
            if (arr[i] == c) {
                System.out.println("查找成功: i=" + i); //返回成功信号
                break; } else{ if(i == N-1)System.out.println("所查询的内容貌似不在这里哦。");/**返回失败信号**/}
        }
    }
}

Chapter 2

What is data structure?

数据结构是计算机程序设计的产物。事实上,至今为止,计算机技术领域并没有一个统一的定义。不同的专家往往对数据结构有不同的描述,以下就是几种典型的定义。

​ 1.「数据结构是数据对象、存在于该对象的实例以及组成实例的数据元素之间的各种关系,并且这种关系可以通过定义相关的函数来给出。」 ——《数据结构、算法与应用》

​ 2.「数据结构是抽象数据类型ADT对的物理实现。」 ——《数据结构与算法分析》

「数据结构」作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计(特别是非数值性程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

Data Structure - Content:

–Logical Structure & Data:

​ 数据的逻辑结构即数据元素之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据的,与数据在计算机中如何存储无关,也就是独立于计算机的抽象概念。从数学分析的角度来看,数据的逻辑结构可以看做从具体问题抽象出来的数学模型。

–Storage Structure & Data:

​ 数据的存储结构即数据元素及其逻辑关系在计算机存储器中的表示形式。数据的存储结构依赖于计算机语言,是逻辑结构用计算机语言的实现。一般来说,只有高级语言的层次上才会讨论存储结构,在低级语言中,存储结构应当是具体的。

–Data Operation:

​ 即对能够对数据施加的操作。数据运算的基础为数据的逻辑结构,每种逻辑结构都可以归纳为一个运算的集合。在数据结构的范畴内,常用的运算包括检索、插入、删除、更新、排序等。

–Sample :

学 号 姓 名 数 学 物 理 英 语 语 文
1001 张三 5 1 9 9
1002 李四 0 1 1 0
1003 王五 1 2 3 8
1004 赵六 6 6 6 6
1005 吴七 5 7 7 9
….
1099 林可爱 10 10 10 5

​ 在表中,每行可以看做一个数据元素,也可以成为记录或者结点。这个数据元素分别由学号、姓名、数学评分、物理评分、英语评分、语文评分等数据项构成。

​ 由这个表首先可以看出数据元素之间的逻辑关系。

–Immediate Predecessor:

​ 对于表中任意一结点,直接前趋结点最多只有一个。直接前趋结点即与它相邻且在它前面的结点。

–Immediate Successor:

​ 对于表中任意一结点,直接后继结点最多只有一个。直接后继结点即与它相邻且在后面的结点。

–Begin

​ 表中只有第一个结点没有直接前趋,即开始结点。//如表中张三

–End

​ 表中只有最后一个结点没有直接后继,即终端结点。//如表中林可爱

–Whole:

​ 数据的逻辑结构、数据的存储结构和数据的运算是一个整体,孤立地去理解这三者的任何一个都是不全面的。主要表现在如下方面:

  1. 相同的逻辑结构可以有不同的存储结构。例如线性表,假设其使用顺序方式存储,则这种数据结构就是顺序表;使用链式方式存储,则是链表,使用散列方式存储,则是散列表。
  2. 相同的逻辑结构可以有不同的数据运算集合。一个相同的数据逻辑结构和存储结构采用不同的运算集合及运算性质,将导致全新的数据结构。例如,假设将线性表的插入运算限制在表的一端,而删除操作限制在表另一端,则它的数据结构是队列;假设线性表的插入和删除操作都限制在表的同一端,则这种数据结构就是栈。

​ 在这三方面,数据结构是一个有机的整体,缺一不可,任何一个方面发生变化都将导致一个全新的数据结构出现。

Data Structure - Classification:

数据结构有很多种,一般按照数据的逻辑结构来对其进行简单地分类,可分为线性结构与非线性结构两类。

–Linear Structure:

​ 线性结构即表中各个结点都具有线性关系,如果从数据结构的语言来描述,应该包括如下内容。

  1. 线性结构是非空集。

  2. 线性结构有且仅有一个开始结点和一个终端结点;

  3. 线性结构所有结点最多只有一个直接前趋和一个直接后继结点。

    前面所举例的线性表即为典型的线性结构,还有栈、队列和串都属于线性结构。

–Nonlinear Structure:

​ 非线性结构即表中各个结点之间具有对个对应的关系。如果从数据结构的语言来描述,应该包括如下内容。

  1. 非线性结构是非空集。
  2. 非线性结构的一个结点可能有多个直接前趋结点和直接后继结点。

​ 在实际应用中,数组、广义表、树结构和图结构等数据结构都是非线性结构。

分享

风陵
作者
lin
A Student | Java Dev