第一章 基础
这一章是本书的开始部分，主要介绍了以下几部分的类容：
- Java的基础语法知识
- 数据的抽象以及定义抽象数据类型（ADT）以进行模块化编程
- 学习三种典型抽象数据类型：背包，队列，和栈
- 研究算法的性能
首先我们看第一部分，java的基本程序结构
原始数据类型：它们在计算机程序中精确地定义整数、浮点数和布尔值等。它们的定义包括取值范围和能够对相应的值进行的操作，它们能够被组合为类似于数学公式定义的表达式。
语句：语句通过创建变量并对其赋值、控制运行流程或者引发副作用来进行计算。我们会使用六种语句：声明、赋值、条件、循环、调用和返回。
数组：数组是多个同种数据类型的值的集合。
静态方法：静态方法可以封装并重用代码，使我们可以用独立的模块开发程序。
字符串：字符串是一连串的字符，Java内置了对它们的一些操作。
标准输入/输出：标准输入输出是程序与外界联系的桥梁。
数据抽象：数据抽象封装和重用代码，使我们可以定义非原始数据类型，进而支持面向对象编程。
Java程序是由语句组成的。语句能够通过创建和操作变量、对变量赋值并控制这些操作的执行流程来描述运算。语句通常会被组织成代码段，即花括号中的一系列语句。
声明语句：创建某种类型的变量并用标识符为其命名。
赋值语句：将（由表达式产生的）某种类型的数值赋予一个变量。Java还有一些隐式赋值的语法可以使某个变量的值相对于当前值发生变化，例如将一个整型值加1。
条件语句：能够简单地改变执行流程——根据指定的条件执行两个代码段之一。
循环语句：更彻底地改变执行流程—一只要条件为真就不断地反复执行代码段中的语句。
调用和返回语句：和静态方法有关，是改变执行流程和代码组织的另一种方式。
关于数组
数组，在Java程序中创建一个数组需要三步：
声明数组的名字和类型；
创建数组；
初始化数组元素。
常见的对于数组处理的代码：
静态方法
方法封装了由一系列语句所描述的运算。方法需要参数（某种数据类型的值）并根据参数计算出某种数据类型的返回值（例如数学函数的结果）或者产生某种副作用（例如打印一个值）。
抽象数据类型
抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型。用Java类来实现抽象数据类型和用一组静态方法实现一个函数库并没有什么不同。抽象数据类型的主要不同之处在于它将数据和函数的实现关联，并将数据的表示方式隐藏起来。在使用抽象数据类型时，我们的注意力集中在API描述的操作上而不会去关心数据的表示；在实现抽象数据类型时，我们的注意力集中在数据本身并将实现对该数据的各种操作。
背包、队列和栈
泛型
集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java机制能够做到这一点，它被称为泛型，也叫做参数化类型。泛型对编程语言的影响非常深刻，许多语言并没有这种机制
背包
背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关。
先进先出队列
先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型，按照任务产生的顺序完成它们的策略我们每天都会遇到：在剧院门前排队的人们、在收费站前排队的汽车或是计算机上某种软件中等待处理的任务。任何服务性策略的基本原则都是公平。在提到公平时大多数人的第一个想法就是应该优先服务等待最久的人，这正是先进先出策略的准则。
下压栈
下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型，当你的邮件在桌上放成一叠时，使用的就是栈。新邮件来到时你将它们放在最上面，当你有空时你会一封一封地从上到下阅读它们。
算法分析
对于大多数程序，得到其运行时间的数学模型所需的步骤如下：
确定输入模型，定义问题的规模；
识别内循环；口根据内循环中的操作确定成本模型；
对于给定的输入，判断这些操作的执行频率。这可能需要进行数学分析——我们在本书中会在学习具体的算法时给出一些例子。
京公网安备 11010502036488号