2019-数据结构-数据结构1-绪论

第一章

1. 课程概述

  1. 这门课程主要是学习数据结构而并不倾向于算法结构。
  2. 课程特点:
    1. 关心数据类型和数据处理步骤
    2. 处理更加复杂难以计算的部分
    3. 不依赖于特定的编程语言。

1.1. 课程内容

  1. 一些数据结构
  2. 一些算法实例

1.2. 课程范例

1.2.1. 例一:游戏策略

  1. 无论什么棋的策略都是相似的，以下仅以三子棋为例。
  2. 一共有五种选择，来生成一颗树，即决策树。

1.2.2. 例二:图书馆管理系统

一般使用线性表数据结构。

1.2.3. 例三:交通管理系统

  1. 在每一条道路上有红绿灯，使用图
  2. 数学基础:图论

1.3. 后续课程

1.3.1. 编译原理

  1. 使用栈

1.3.2. 操作系统

  1. 使用队列

1.3.3. 数据库

  1. 使用B+树、B-树。

2. 数据结构的定义

2.1. 数据

  1. 数据是信息的载体，数据是数字、字符和其他符号的集合。
    • 这些符号可以被输入计算机，并且被计算机程序识别和处理。
    • 注:不能是无意义的符号
  2. 数据可以被用来描述客观对象。
  3. 数据分类:
    1. 数值型数据:int,float,complex(复数)…
    2. 非数值型数据:character,string,graph,voice

2.2. 数据结构

  1. 定义:数据结构是描述数据对象和数据对象之间关系的统称。

  1. 数据结构分类:
    1. 线性结构
    2. 非线性结构
  2. 数据结构涉及三个方面:数据结构是分层的。
    1. 数据的逻辑结构——从用户视图看，是面向问题的。
    2. 数据的物理结构——从具体实现视图看，是面向计算机的。
    3. 相关的操作及其实现。

Example1:

  1. 学生表:
  • 逻辑结构–线性表
  • 物理结构–数组，链表
  • 操作–插入，删除，查找

2.3. 层次思想

  1. 在研究讨论一个问题的时候，我们需要明确一个层次究竟是什么，我们要在一个相应的层次上来讨论相应的问题。
  2. 讨论一个具体软件的时候，我们只讨论应该怎么做这个软件的功能层次，而不是实现层次。
  3. 软件是需要分层次的。

3. ADT and OO

  1. ADT(Abstact data types)
  2. OO(object oriented)

3.1. 数据类型

  1. 数据类型的本质在于操作。
  2. 数据按照二进制进行存储。
    • 在内存中读取数据的时候，要注意大端形式。(高位在低地址)
    • float是最大约3*1020，参照IEEE754标准

  1. 对于64位系统，字长word是64Byte
  2. 数据类型分类

3.2. ADT

  1. 是将类型和与这个类型有关的操作集合封装在一起的数据模型。

3.3. OOP

  1. 面向对象编程是一种程序编写思想。
  2. AOP是OOP的延续。
  3. 三个方面:(考研)
    1. 封装
    2. 继承
    3. 多态
  4. 为什么选择OOP:
    1. 最重要的是要保证模块之间的关系越少越好(耦合性低)。
    2. 真正从某种程度上来保证了软件可以做大。
  5. 面向对象的过程中:你的private部分可以进行修改，避免出现修改时候的影响，你的public部分不要随意修改。

3.4. class 类

  1. objects of same attributes and operates. an instance is an object of the class. different object has different attribute value 一些属性和一些操作的对象。实例这个类的一个对象。不同的对象有着不同的类。

3.5. inherit 继承

3.6. 消息和通信

  1. 类之间传递消息。

4. 算法

4.1. 算法定义

  1. 为了解决某个问题的一系列操作。(an operation sequence of soluting a problem)
  2. 特点:
    1. finite(有限的)
    2. deterministic(确定性)
    3. initial action(有初始动作)
    4. sequence ends(有终点)
  3. 程序:是可以用机器处理，并且能够理解程序语言。

5. 数学知识回顾

  1. logA不写底数的情况下，默认底数是2

5.1. 同余

  1. A≡B(mod N)

5.2. 数学归纳法

  1. 格式:
    1. basis
    2. inductive(归纳的) hypothesis
    3. inductive proof

5.3. 反证法

6. 递归

  1. 参考另一个文件

7. 部分java知识

7.1. java泛型

  1. IntCell(放整数的盒子) —— 不是泛型类。
  2. MomoryCell(放任何类型的盒子) —— 泛型类。

7.2. java的private和public

7.3. 构造器

7.4. This关键字

  1. java: This.
  2. C++:
    1. *This.:在C++中This是指针，所以要用*变为引用。
    2. This->:C++

7.5. 类的创建

  1. java: intCell a = new intCell();
  2. C++：
    1. intCell *b = new intCell();
    2. intcell b = intCell(params[])

7.6. 静态关键字

7.7. 泛型

  1. java:
  2. C++: 用templete

  1. 能合在一起的所有的东西，都尽量分离出来，想办法解耦。
    • 出现bug比较好进行修改。

7.7.1. 泛型的编译运行

  1. C++形式:
    1. 首先确定T的具体类型。
    2. 根据相应的类型，生成相应类型的源代码。
  2. Java形式:
    1. 所有的对象都由基类object派生出来，没有写继承，默认继承自Object。
    2. 不能使用基本类型。

解决类型混乱问题

7.8. 接口

  1. 接口十分重要
  2. 比较: 接口(compare):实现lessThan方法。

7.9. 异常处理

7.9.1. 三类错误

  1. 语法error, 语义error, 逻辑 error
  2. 语法error
    • 通常在编译时发现，又称编译错。
    • 如：标识符未声明，类型不匹配，缺少分号等。
  3. 语义error
    • 只有到程序运行时才发现，又称运行错。
    • 如：除数为0, 数组下标越界等。 打开的文件不存在，网络连接中断等。
    • java中的异常处理提供对运行时错误的语言级处理机制，主要是针对这类错误。
  4. 逻辑error
    • 运行结果与期望值不符。这类错误最难确定与排除。

7.9.2. 运行时错误

7.9.3. java异常处理

1
2
3
4
5
6
7
try{

}catch{

}finally{

}

  1. 抛出异常

7.10. 实例

  1. 寻找最大值算法:纯白色255，纯黑色000，所以可以用这个算法来找最亮或者最暗的图片。

7.11. 输入输出

  1. 可以通过不同的流来进行控制即可。

7.11.1. 输入

7.11.2. StringTokenizer对象

  1. Sometimes we have several items on a line. For instance, suppose each line has two ints. Java provides the StringTokenizer object to separate a String into tokens. 有时我们在一条线上有几样东西。例如，假设每一行有两个int。Java提供StringTokenizer对象来将字符串分隔成标记。
  2. 需要import java.util.*;
  3. By default, tokens are separated by white space. 默认情况下，词被空格分隔开。
  4. 一个一个单词往下碰。

7.12. Sequential Files

7.13. main函数的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
public class ListFiles {
        public static void main( String [] args ) {
            if( args.length = = 0 )
                System.out.println( ―No files specified‖ );
            for( int i = 0; i < args.length; i++ )
                listFile( args[ i ] ); 
        } 
        public static void listFile( String fileName ){
            FileReader theFile;
            BufferedReader fileIn = null;
            String oneLine;
            
            Systnm.out.println( ―FILE: ― + fileName );
            try {
                theFile = new FileReader( fileName );
                fileIn = new BufferedReader( theFile );
                while( ( oneLine = fineIn.readLine( ) ) != null ) 
                    System.out.println( oneLine ); 
            }catch(exception e ){
               System.out.println( e );
            }
        }
}

8. Code Organization

  1. package
2019-数据结构
#课程笔记 #数据结构
2019-数据结构-数据结构1-绪论
https://spricoder.github.io/2020/01/17/2019-Data-Structure/2019-Data-Structure-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%841-%E7%BB%AA%E8%AE%BA/
作者
SpriCoder
发布于
2020年1月17日
许可协议