1.2 基本的数据结构
（8课时机上8课时）
目录
第一课时 (2)
教学目标 (2)
1.2.1.1什么是数据结构 (2)
1.2.1.2基本的数据结构及其优缺点 (3)
1.2.1.3关于数据结构的一些概念 (3)
第二课时 (4)
教学目标 (4)
1.2.2.1引言 (5)
1.2.2.2一维数组的创建 (5)
1.2.2.3一维数组的初始化 (5)
1.2.2.4一维数组数据项的访问 (6)
第三-四课时 (6)
教学目标 (6)
1.2.3-4.1引言 (6)
1.2.3-4.2多维数组声明 (7)
1.2.3-4.3多维数组初始化 (7)
1.2.3-4.4引用多维数组元素 (8)
1.2.3-4.5锯齿数组 (9)
第五课时 (9)
教学目标 (9)
1.2.5.1枚举类型 (9)
1.2.5.2枚举类型的定义 (10)
1.2.5.3枚举的使用 (10)
1.2.5.4枚举具有的核心功能 (10)
第六-七课时 (12)
教学目标 (12)
1.2.6-7.1引用型数据类型 (12)
1.2.6-7.2引用类型的赋值 (13)
1.2.6-7.3按值传递和还是按引用传递 (13)
第八课时 (18)
教学目标 (18)
1.2.8.1类 (18)
1.2.8.2对象 (18)
1.2.8.3成员变量 (19)
1.2.8.4成员方法 (21)
1.2基本的数据结构（8课时）
第一课时
教学目标
数据结构的概念，基本的数据结构及其优缺点，和数据结构相关的几个定义（数据库，字段，关键字）。
1.2.1.1什么是数据结构
数据结构是对在计算机内存中（有时在磁盘中）的数据的一种安排。数据结构包括数组，表，栈，二叉树，哈希表等。数据结构可以解决哪些方面的问题呢？粗略的估计一下，可以用于以下三类情况：
·现实世界数据存储
·程序员的工具
·建模
现实世界数据存储——现实世界数据值得是哪些描述处于计算机外部的物理实体的数据。看几个例子：一条人事档案记录描述了一位真实人的记录，一条存货记录描述了一个真实存在的汽车部件或杂货店里的一种商品，一条财务交易记录描述了一笔支付电费实际填写的支票。
举一个非计算机的现实世界数据存储的例子，有一叠3x5的索引卡片，这些卡片可以被用在不同的场合。如果每张卡片上写有某人的姓名，地址和电话号码，那么折叠卡片一定是一本地址簿。如果每一张卡片上写有家庭拥有物的名称，位置和价值，那么这一定是一本家庭财产清单。
当然索引卡片并不能代表现在的科技发展水平。几乎索引以前用索引卡片处理的事务现在都可以用计算机来处理。如果想将旧式的所以卡片系统更新为计算机程序，边有可能会发现会被如下问题所困扰：
·如何在计算机内存中安放数据？
·所用方法适用于100张卡片吗？那1000张呢？10000000张呢？
·所用方法能够快速的插入新卡片和删除老卡片吗？
·它能快速的查找一张特定的卡片吗？
·若想将卡片按照字母顺序排列，又应该如何去排呢？
然而，大多数程序比所以卡片要复杂得多。想象一下机动车管理部门的数据库，这个库被用来记录驾驶员的执照的情况；或者看一个航班预定系统，这个系统存储了旅客和航班的各种信息。这些系统由许多数据结构组成。
程序员的工具——并不是所有的数据结构都用来存储现实世界的数据。通常情况下，现
Android初级培训教材
实世界的数据或多或少会由程序的用户直接存取。但是有些数据存储结构并不打算让用户接触，它们仅被程序本身所使用。程序员经常将诸如栈，队列和优先级队列等结构当作结构来简化另一些操作，这些数据结构就是程序员的工具了。
现实世界的建模——有些数据结构能直接对现实世界的情况构造建模。其中最重要的数据结构是图。图可以用来表示城市之间的航线。电路中的连接线和连接点，或者是某一工程中的任务安排关系。其它诸如栈和队列等数据结构也会应用在时间的建模中。例如，一个队列可以模拟顾客在银行中排队等待的模型，还可以模拟汽车在收费站前面等待缴费的模型等等。
1.2.1.2基本的数据结构及其优缺点
知道了数据结构的概念及基本用途，那么到底有哪些数据结构，以及它们各自的优点和
知道了这些基本的数据结构及其优缺点，那么我们再平平时的编程中选择正确的数据结构将会大大提高程序的运行效率。
1.2.1.3关于数据结构的一些概念
数据库（database）——我们将会使用数据库这个术语来表示在某一特定情况下所有要查阅的数据，数据库中的每一条数据都被认为是同样格式的，这种存储数据的统一格式就是我们前面所说的数据结构。例如：如果使用索引卡片来做一本地址簿，其中所有的卡片便构成了一个数据库，没一张卡片就是一条数据，而卡片本身就是数据结构。
记录（record）——记录是指数据库中划分成的单元。它们为存储信息提供了一个结构
3/ 24
格式。在索引卡片的模拟系统中，每一张卡片就代表一条记录。当有许多类似的实体时，一条记录包含了某一个实体的所有信息。一条记录可能应对与人事档案中的某一个人，汽车供应存货目录中的某一个零部件，或是烹调书中的某一道菜谱。
字段（field）——一条记录经常被划分为几个字段。一个字段保存某一种特定的数据。在地址簿中的一张索引卡片上，一个人的名字，地址或电话号码都是一个独立的字段。更复杂的数据库程序使用带有更多字段的记录。如下图显示了一条记录，其中每一行代表了一个
在java语言（和其它面向对象语言）中，记录经常被表示为一个相应类的对象。一个实例中各个变量表示不同的数据字段（data field）。
关键字——在数据库中查找一条记录，需要指定记录的某一个字段位关键字（或查找关键字）。通过这个特定的关键字来进行查找。例如，在一个地址簿的程序中，可以再每条记录的姓名字段中查找关键字“Brown”。当找到具有该关键字的记录时，便可以访问它的所有字段，而不仅仅是关键字了，可以说是关键字释放了整个记录。还可以通过电话号码字段或地址字段在整个文件中再次查找。上图中任何字段都可以被用作查找关键字。
第二课时
教学目标
一维数组的概念，一维数组的创建，一维数组的初始化，一维数组数据项的访问。
Android初级培训教材
1.2.2.1引言
数组（array）是相同类型变量的集合，可以使用共同的名字引用它。它是应用最广泛的数据结构，被植入到大部分变成语言中。由于数组十分易懂，所以它被用来作为介绍数据结构的起步点，并展示面向对象变成和数据结构之间的关系。数组可以被定义为任何类型，可以是一维的也可以是多维的。数组中的一个特别要素是通过下标来访问他。数组提供了一种将有联系的信息分组的便利方法。下面我们来详细介绍一维数组。
1.2.2.2一维数组的创建
一维数组（one-dimensional array）实质上市相同类型变量列表。
正如第一章所提到的，java中有两种数据类型：基本类型（如int，double等）和引用类型在许多编程语言中（甚至有些面向对象语言，如C++），数组也是基本类型，但在java 中把它当作对象类型来对待，因此在创建数组时必须使用new操作符。
要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：Type var-name[];
获得一个数组需要两步。第一步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样java中的数组被动态地分配。如下所示：
Int[] intArray; //声明一个数组变量
intArray = new int[100] //给数组变量分配内存空间
或者使用等价的但语句声明方法：
Int[] intArray = new int[100];
[]操作符对于编译器来说是一个标志，它说明正在命名的是数组对象而不是普通的变量。当然还可以通过另一种语法来使用这个操作符，将它放在变量名的后面而不是类型的后面：
Int intArray[] = new int[100];
但是将[]放在int后面会清楚的说明[]是数据类型的一部分，而不是变量名的一部分。
由于数组是一个对象，所以它的名字（前面程序中的intArray）是数组的一个引用：它并不是数组本身。数组存储在内存中的其它地址中，而intArray仅仅保存着这个地址。
数组有一个length字段，通过它可以得知当前数组大小（数据项的个数）；
Int arraylength = intArray.length; //取得数组长度
数组一旦被创建，其大小不可改变。
1.2.2.3一维数组的初始化
当创建整型数组后，如果不另行指定，那么整型数组会自动初始化成空。与C++不同的是，即使通过方法（函数）来定义数组也是这样的。常见一个对象数组如下：autoData[] varArray = new autoData[4000];
除非将特定的值赋给数组数据项，否则它们一直是特殊的null对象。如果尝试访问一个含有null的数组数据项，程序会出项Null Pointer Assignment（空指针赋值）的运行错误。这主要是为了保证在读取某个数据项之前要先对其赋值。
5/ 24
使用下面的语法可以对一个基本类型的数组初始化，赋入非空值：
int[] intArray = {0,3,6,9,12,15,18,21,24,27};
上面的语句可能简单的令人惊讶，它同时取代了引用声明和使用new来创建数组。在大括号中的数据被称为数据列表。数组大小由列表中数据项的个数决定。
1.2.2.4一维数组数据项的访问
数组数据项通过使用方括号中的下标数来访问。这与其它语言类似：
Temp = intArray[3]; //定义一个有四个数据项的数组
intArray[7] = 66; //给第八个数组元素赋值为66
请注意无论是C，C++，还是java中，第一个数据项的下标都是0，所以，一个有10个数据项的数组小标是0至9.
如果访问小于0或者比数组大小大的数据项，程序会出现Array Index Out Of Bounds（数组小标越界）的运行错误。
第三-四课时
教学目标
多维数组概念，多维数组的声明，多维数组的初始化，多维数组长度的取得，锯齿数组的简单介绍。
1.2.3-4.1引言
在学校里，由于一个班的人数不多，所以按照顺序编号即可，当人数增多时，例如对于学校里的人，在编号时就要增加层次，例如XX班XX号。在部队中也是这样，XX师XX团XX营XX连XX排XX班，这里的层次就比较深了。为了管理数据的方便，一般要加深管理的层次，这就是多维数组的由来。
多维数组，指二维以及二维以上的数组。二维数组有两个层次，三维数组有三个层次，依次类推。每个层次对应一个下标。
在实际使用中，为了使结构清晰，一般对于复杂的数据都是用多维数组。关于多维数组的理解，最终的是理解数组的数组这个概念，因为数组本身就是一种复合数据类型，所以数组也可以作为数组元素存在。这样二维数组就可以理解成内部每个元素都是一维数组类型的一个一维数组。三维数组可以理解成一个一维数组，内部的每个元素都是二维数组。无论在逻辑上还是语法上都支持“数组的数组”这种理解方式。
通常情况下，一般用二维数组的第一维代表行，第二维代表列，这种逻辑结构和现实中的结构一致。和一维数组类似，因为多维数组有多个下标，那么引用数组中的元素时，需要指定多个下标。下面以二维数组为例，来介绍多维数组的语法。
Android初级培训教材
1.2.3-4.2多维数组声明
多维数组的声明如下：
数据类型[][] 数组名称;
数据类型[] 数组名称[];
数据类型数组名称[][];
以上三种语法在声明二维数组时的功能是等价的。同理，声明三维数组时需要三对中括号，中括号的位置可以在数据类型的后面，也可以在数组名称的后面，其它的依次类推。例如:
int[][] map;
char c[][];
和一维数组一样，数组声明以后在内存中没有分配具体的存储空间，也没有设定数组的长度。
1.2.3-4.3多维数组初始化
和一维数组一样，多维数组的初始化也可以分为静态初始化(整体赋值)和动态初始化两种，其语法格式如下。
静态初始化——以二维数组的静态初始化为例，来说明多维数组静态初始化的语法格式。示例代码如下：
int[][] m = {
{1,2,3},
{2,3,4}
};
在二维数组静态初始化时，也必须和数组的声明写在一起。数值书写时，使用两个大括号嵌套实现，在最里层的大括号内部书写数字的值。数值和数值之间使用逗号分隔，内部的大括号之间也使用逗号分隔。
由该语法可以看出，内部的大括号其实就是一个一维数组的静态初始化，二维数组只是把多个一维数组的静态初始化组合起来。
同理，三维数组的静态初始化语法格式如下：
int[][][] b = {
{
{1,2,3},
{1,2,3}
},
{
{3,4,1},
{2,3,4}
}
};
说明：这里只是演示语法格式，数值本身没有意义。
动态初始化——二维数组动态初始化的语法格式：
数据类型[][] 数组名称= new 数据类型[第一维的长度][第二维的长度];
7/ 24
数据类型[][] 数组名称;
数组名称= new 数据类型[第一维的长度][第二维的长度];
示例代码：
byte[][] b = new byte[2][3];
int m[][];
m = new int[4][4];
和一维数组一样，动态初始化可以和数组的声明分开，动态初始化只指定数组的长度，数组中每个元素的初始化是数组声明时数据类型的默认值。例如上面初始化了长度为2X3的数组b，和4X4的数组m。
使用这种方法，初始化出的第二维的长度都是相同的，如果需要初始化第二维长度不一样的二维数组，则可以使用如下的格式：
int n[][];
n = new int[2][]; //只初始化第一维的长度
//分别初始化后续的元素
n[0] = new int[4];
n[1] = new int[3];
这里的语法就体现了数组的数组概念，在初始化第一维的长度时，其实就是把数组n 看成了一个一维数组，初始化其长度为2，则数组n中包含的2个元素分别是n[0]和n[1]，而这两个元素分别是一个一维数组。后面使用一维数组动态初始化的语法分别初始化n[0]和n[1]。
1.2.3-4.4引用多维数组元素
对于二维数组来说，由于其有两个下标，所以引用数组元素值的格式为：
数组名称[第一维下标][第二维下标]
该表达式的类型和声明数组时的数据类型相同。例如引用二维数组m中的元素时，使用m[0][0]引用数组中第一维下标是0，第二维下标也是0的元素。这里第一维下标的区间是0到第一维的长度减1，第二维下标的区间是0到第二维的长度减1。
四、获得多维数组长度
对于多维数组来说，也可以获得数组的长度。但是使用数组名.length获得的是数组第一维的长度。如果需要获得二维数组中总的元素个数，可以使用如下代码：
int[][] m = {
{1,2,3,1},
{1,3},
{3,4,2}
};
int sum = 0;
for(int i = 0; i < m.length; i++){ //循环第一维下标
sum += m[i].length; //第二维的长度相加
}
在该代码中，m.length代表m数组第一维的长度，内部的m[i]指每个一维数组元素，m[i].length是m[i]数组的长度，把这些长度相加就是数组m中总的元素个数
Android初级培训教材
1.2.3-4.5锯齿数组
下面我们要介绍一种比较特殊的二维数组，可能大家也已经注意到了，在前面我们所举的例子中就有这么一种数组，它的第二维的长度是不一样的，我们把这种第二维长度不同的二维数组叫做锯齿数组。
锯齿数组直接初始化——锯齿数据直接初始化的格式形如下面：
int[][] a = {{1,2},{3,4,5,6,7,8},{9},{0,1,2}};
锯齿数组的动态初始化如下：
int[][] a ;
a = new int[4][];
a[0] = new int[2];
a[1] = new int[6];
a[2] = new int[1];
a[3] = new int[3];
第五课时
教学目标
枚举类型的概念，枚举类型的使用，枚举类型的特点。
1.2.5.1枚举类型
我们已经知道，Java代码的两个基本的构造块是类和接口。现在又引入了枚举，一般简称它为enum。那么什么是枚举呢，枚举其实就是一种类型，跟int, char 这种差不多，就是定义变量时限制输入的，你只能够赋enum里面规定的值。这个新类型允许您表示特定的数据点，这些数据点只接受分配时预先定义的值集合。
当然，熟练的程序员可以使用静态常量实现这项功能，就是我们常说的public static final 代码。如下所示：
Public class OldGrade{
public static final int A = 1;
public static final int B = 2;
public static final int C = 3;
public static final int D = 4;
public static final int F = 5;
public static final int INCOMPLETE = 6;
}
但是在这样做的时候，请记住这类常量是Java 中int 类型的常量，这意味着该方法可以接受任何int 类型的值，即使它和OldGrade 中定的所有级别都不对应。因此，您需要
9/ 24
检测上界和下界，在出现无效值的时候，可能还要包含一个IllegalArgumentException。而且，如果后来又添加另外一个级别（例如OldGrade.WITHDREW_PASSING），那么必须改变所有代码中的上界，才能够接受现在的这个值。换句话说，在使用这类带有整型常量的类时，该解决方案也许可行，但并不是非常有效。幸运的是，枚举提供了更好的方法。
1.2.5.2枚举类型的定义
枚举类型在定义时要使用一个关键字enum，为enum 提供了一个名称，并指定了允许的值。形如下面的例子：
Public enum Grade{
A,B,C,D,F,INCOMPLETE
}；
1.2.5.3枚举的使用
枚举类型最经常的用法，是使用枚举类型，在各个枚举值之间切换做各种分歧处理，及常用的switch语句。把枚举的各个值，作为switch语句的各个case来进行所需要的处理。当然必须切记的是这时候的switch语句中一定要在处理完所有的case后在加上default处理块，以免枚举类型被程序员修改后，我们在不知情的情况下，对这种新的枚举值漏处理，而且还发现不了错误。
1.2.5.4枚举具有的核心功能
类型安全：
枚举的申明创建了一个新的类型。它不同于其他的已有类型，包括原始类型（整数，浮点数等等）和当前作用域（Scope）内的其它的枚举类型。当你对函数的参数进行赋值操作的时候，整数类型和枚举类型是不能互换的（除非是你进行显式的类型转换），编译器将强制这一点。比如说，用下面申明的枚举定义这样一个函数：
枚举定义：
enum Day {SUNDAY, MONDAY, TUESDAY,
WEDNESDAY, THURSDAY, FRIDAY, SATURDAY};
函数定义：
Public void fun(Day);
如果你用整数作为参数来调用这个函数，那么，编译器肯定会报错。
fun(4); //错误
要调用这个函数，参数必须严格使用上面枚举中所列举出来的值。
紧凑有效的枚举数值定义：
定义枚举的程序应该很简单，虽然java中也有类似于public static final的“准枚举”的定义，但这种枚举似乎很不简洁。如果有大量的数据要定义，这一点就尤为重要，你也就会感受更深。虽然这一点不如其他另外3点重要，但我们总是希望申明能尽可能的简洁。
Android初级培训教材
无缝的和程序其它部分的交互操作：
语言的运算符，如赋值，相等/大于/小于判断都应该支持枚举。枚举还应该支持数组下标以及switch/case语句中用来控制流程的操作。比如：
for (Day d = SUNDAY; d <= SATURDAY; ++d) {
switch(d) {
case MONDAY: ...;
break;
case TUESDAY: ...;
break;
case WEDNESDAY: ...;
break;
case THURSDAY: ...;
break;
case FRIDAY: ...;
break;
case SATURDAY:
case SUNDAY: ...;
}
}
要想让这段程序工作，那么枚举必须是整数常数，而不能是对象（objects）。Java中你可以用equals() 或是compareTo() 函数来进行对象的比较操作，但是它们都不支持数组下标和switch语句。
运行的高效率：
枚举的运行效率应该和原始类型的整数一样高。在运行时不应该由于使用了枚举而导致性能比使用整数有下降。
11/ 24
第六-七课时
教学目标
引用型数据类型的概念，值传递，引用传递。
1.2.6-7.1引用型数据类型
早些时候的编程语言和初级程序员将每个变量看作相互无关的实体。例如，如果一个程序需处理某个日期，则要声明三个单独的整数：
int day, month, year;
上述语句作了两件事，一是当程序需要日、月或年的有关信息时，它将操作一个整数；二是为那些整数分配存储器。尽管这种作法很容易理解，但它存在两个重大缺陷。首先，如果程序需同时记录几个日期，则需要三个不同的声明。例如，要记录两个生日，你可能使用：int myBirthDay, myBirthMonth, myBirthYear;
int yourBirthDay, yourBirthMonth, yourBirthYear;
这种方法很快就会引起混乱，因为需要的名称很多。
第二个缺陷是这种方法忽视了日、月和年之间的联系并把每个变量都作为一个独立的值，每个变量都是一个独立单元。为了解决这个问题，Java引入了引用类型，允许程序员自己定义类型。
引用类型（reference type）指向一个对象，不是原始值，指向对象的变量是引用变量。在Java 里面除去基本数据类型的其它类型都是引用数据类型，自己定义的class类都是引用类型，可以像基本类型一样使用。在Java 程序运行时，会为引用类型分配一定量的存储空间并解释该存储空间的内容。示例如下：
public class MyDate {
private int day = 8;
private int month = 8;
private int year = 2008;
public MyDate(int day, int month, int year){…}
public void print(){…}
}
public class TestMyDate {
public static void main(String args[]) {
// 这个today 变量就是一个引用类型的变量
MyDate today = new MyDate(23, 7, 2008);
}
}
Android 初级培训教材
13 / 24
1.2.6-7.2引用类型的赋值
在 Java
编程语言中，用类的一个类型声明的变量被指定为引用类型，这是因为它正在引用一个非原始类型，这对赋值具有重要的意义。请看下列代码片段： int x = 7; int y = x;
String s = "Hello"; String t = s;
四个变量被创建：两个原始类型 int 和两个引用类型String 。x 的值是 7，而这个值被 复制到y ；x 和y 是两个独立的变量且其中任何一个的进一步的变化都不对另外一个构成影响。至于变量s 和t ，只有一个 String 对象存在,它包含了文本“Hello ”，s 和t 均引用这个单一 的对象。
将变量 t 重新定义为：String t=”World ”; 则新的对象 World 被创建，而t 引用这个对象。上述过程被描述如下：
1.2.6-7.3按值传递和还是按引用传递
这个在 Java 里面是经常被提起的问题，也有一些争论，似乎最后还有一个所谓的结论：“在 Java 里面参数传递都是按值传递”。事实上，这很容易让人迷惑，下面先分别看看什么是按值传递，什么是按引用传递，只要能正确理解，至于称作按什么传递就不是个大问题了。
按值传递——指的是在方法调用时，传递的参数是按值的拷贝传递。示例如下： 1. public class TempTest { 2. private void test1(int a) { 3. // 做点事情 4. a++; 5. } 6.
7. public static void main(String[] args) { 8. TempTest t = new TempTest();
9. int a = 3;
10. t.test1(a);// 这里传递的参数a就是按值传递。
11. System.out.println("main方法中的a===" + a);
12. }
13. }
按值传递重要特点：传递的是值的拷贝，也就是说传递后就互不相关了。第9行的a和第2行的a是两个变量，当改变第2行a的值，第9行a的值是不变的，所以打印结果是3。
我们把第9行的a称之为实参，第2行的a称之为形参；对于基本数据类型，形参数据的改变，不影响实参的数据。
按引用传递——指的是在方法调用时，传递的参数是按引用进行传递，其实传递的引用的地址，也就是变量所对应的内存空间的地址。示例如下：
1. public class TempTest {
2. private void test1(A a) {
3. a.age = 20;
4. System.out.println("test1方法中的age="+a.age);
5. }
6. public static void main(String[] args) {
7. TempTest t = new TempTest();
8. A a = new A();
9. a.age = 10;
10. t.test1(a); // 这里传递的参数a就是按引用传递
11. System.out.println("main方法中的age="+a.age);
12. }
13. }
14. class A {
15. public int age = 0;
16. }
运行结果如下：test1方法中的age=20 main 方法中的age=20
按引用传递的重要特点：传递的是值的引用，也就是说传递前和传递后都指向同一个引用（也就是同一个内存空间）。
要想正确理解按引用传递的过程，就必须学会理解内存分配的过程，内存分配示意图可以辅助我们去理解这个过程。用上面的例子来进行分析：
（1）运行开始，运行第8 行，创建了一个A 的实例，内存分配示意图如下：
Android 初级培训教材
15 / 24
（2） 运行第 9 行，是修改 A 实例里面的
age 的值，运行后内存分配示意图如下：
（3）运行第10行，是把main 方法中的变量a 所引用的内存空间地址，按引用传递给test1 方法中的 a 变量。请注意：这两个a 变量是完全不同的，不要被名称相同所蒙蔽，但它们
指向了同一个A 实例。内存分配示意图如下：
（4）运行第 3 行，为 test1 方法中的变量 a 指向的 A 实例的 age 进行赋值，完成后形 成新的内存示意图如下：
此时 A 实例的 age 值的变化是由 test1 方法引起的。
（5）运行第4行，根据此时的内存示意图，输出test1方法中的age=20
（6）运行第 11 行，根据此时的内存示意图，输出 main 方法中的 age=20
理解了上面的例子，可能有人会问，那么能不能让按照引用传递的值，相互不影响呢？ 就是 test1 方法里面的修改不影响到 main 方法里面呢？方法是在 test1 方法里面新 new 一个实例就可以了。改变成下面的例子，其中第3行为新加的： 1. public class TempTest { 2. private void test1(A a) {
3. a = new A();// 新加的一行
4. a.age = 20;
5. System.out.println("test1方法中的age=" + a.age);
6. }
7. public static void main(String[] args) { 8. TempTest t = new TempTest(); 9. A a = new A(); 10. a.age = 10; 11. t.test1(a);
12. System.out.println("main 方法中的age=" + a.age); 13. } 14. }
15. class A {
16. public int age = 0;
17. }
运行结果为：test1方法中的age=20 main 方法中的age=10
为什么这次的运行结果和前面的例子不一样呢，还是使用内存示意图来理解一下：
（1）运行开始，运行第9 行，创建了一个A 的实例，内存分配示意图如下：
（2）运行第10 行，是修改 A 实例里面的age 的值，运行后内存分配示意图如下：
（3）运行第11 行，是把main 方法中的变量a 所引用的内存空间地址，按引用传递给test1方法中的a 变量。请注意：这两个a 变量是完全不同的，不要被名称相同所蒙蔽。
也就是说：是两个变量都指向同一个空间。
（4）运行第3 行，为test1 方法中的变量a 重新生成了新的A 实例的，完成后形成的新的内存示意图如下：
（5）运行第 4 行，为 test1 方法中的变量 a 指向的新的 A 实例的 age 进行赋值，完成后形成的新的内存示意图如下：
注意：这个时候 test1 方法中的变量 a 的 age 被改变，而 main 方法中的是没有改变的。（6）运行第5行，根据此时的内存示意图，输出test1方法中的age=20
（7）运行第 12 行，根据此时的内存示意图，输出 main 方法中的 age=10 最后有两点说明：
○1“在 Java 里面参数传递都是按值传递”这句话的意思是：按值传递是传递的值的
Android初级培训教材
拷贝，按引用传递其实传递的是引用的地址值，所以统称按值传递。
○2在 Java 里面只有基本类型和直接使用双引号定义字符串（String str = "Java "）方式的 String 是按值传递，其它的都是按引用传递。
17/ 24
第八课时
教学目标
类和对象。
1.2.8.1类
在面向对象的语言中，类是个很重要的概念。面向对象的方法把所有的处理对象进行归类。具有相同性质的对象归为一类。例如学校里有很多学生，每个学生都是一个对象，而“学生”则是一个类，它包含了所有在学校学习的人。在Java语言里，对象是一组描述对象的属性和操作方法的集合，其中属性表明对象的状态，方法表明对象的行为。类是对象的定义。一个对象具有哪些属性和方法，由类来决定。从编程角度看，类是一种复合数据类型，它封装了一组变量和方法（函数）。
声明一个类的一般形式如下所示：
其中修饰符说明了类的属性，可以是public、abstract、final等。这些修饰符的含意将会在后继的章节中介绍。类体就是类的成员变量和成员方法的声明。修饰符和类体的声明都是可以选的。下面是一个“人”的类的声明，虽然类体是空的：
1.2.8.2对象
对象与类是不同但是又紧密相联的概念。类是对象的定义，对象由类来生成。类与对象的关系好比铸造车间里模具与产品的关系。模具只有一个，但是用这个模具可以浇铸出很多成型的产品出来，模具的形状决定了浇铸出来的产品的外形。在Java语言里用new关键字来生成对象，通常的格式为：
这里的对象名可以是任意合法的Java标识符。new关键字后带小括号的类名称为构造方法（函数）。默认的、也是最简单的构造方法是不带参数的，也可以自定义不同形式的构造
Android初级培训教材
方法以供不时之需。下例利用刚才的Person类来生成两个Person对象Mike和John：
用new Person()生成一个对象时不仅分配了内存空间还进行了一些初始化的工作，对象所包含的不仅只是各个属性名了，而是属性的具体值。如果没有给属性赋值，虚拟机会自动给它们赋于相应数据类型默认的初值。生成一个对象的过程也称为实例化，所以一个对象就是一个实例。Mike和John是对象名，对象名是用来引用对象的，对象里的变量和方法可以通过对象名来引用，所以对象名也称为引用（Reference）。引用类似于C/C++中指针的概念，与指针不同，引用不是直接指向对象所在的内存位置，但是它包含了内存地址的信息。Java中并没有指针，以指针进行内存操作常造成不可预知的错误，还可能破坏安全性，也正是因为如此，Java被认为是“安全的”编程语言。
在某些特殊的情况下，可能生成实例但不需要引用，那可以直接用new来实例化。如下所示：
上面两行程序生成两个Person对象，但是每次生成的对象分别占用不同的内存空间，改变其中一个对象的状态不会影响其它对象的状态。就像每次用模具倒出一个毛坯一样，尽管两个毛坯看起来很像，但它们绝对是两个不同的毛坯。
1.2.8.3成员变量
在面向对象的思想中，通常用属性来描述对象的特征。在编程语言里，这一组从属于某类对象的属性是用变量来表示的，例如前文提到用来表示人的特征的身高、体重、姓名等等，就可以分别用不同类型的变量：double型的height、float型的weight、String型的name来表示。这些属于类的变量，称为类的成员变量。声明成员变量的一般形式如下：
其中修饰符说明了类的成员变量的属性，可以是public、protected、private、static、transient、final、volatile等等。成员变量的类型可以是Java内置的或者是自定义的复杂数据类型，包括简单类型、类、接口、数组。例如，描述一个人有一座房产可以用House类型的变量house来表示，这里的House是用户自定义的类（复杂数据类型）。调用成员变量的一般形式是：
下面是一个“人”的类的声明，类名是Person。描述“人”的成员变量有：height、weight、sex、name、age等，还有房产house的声明。
19/ 24
Person类有6个成员变量，其中5个是简单数据类型，1个是复合数据类型House。在类E4_1的main函数里生成了一个引用名为p_Bill的对象。通过这个p_Bill这个引用可以访问到这个人的年龄、身高、体重等属性。上例的程序可以在全部放在一个源文件中，源文件名为必须为E4_1。Java的一个源文件允许多个类的存在，但是文件名必须和public类一致，一个源文件中只也能有一个public类。成员变量不需要显式初始化可以直接使用。其实，它们还是有被初始化过的，称为隐式的初始化。没有显式初始化的成员变量是在为对象分配存储空间时自动被初始化，各种类型的变量被赋于默认的初始化值，如下所示：
下例打印了隐式初始化的Person类成员变量。
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
实用标准文档 文案大全第1章数据结构基础 结构之美无处不在： 说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子，还有看不见却也存在的化学中的分子、原子。可见，一件事物只要存在，就一定会有自己的结构。一幅画的生成，作家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规划、谋篇布局。一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服。还有教育管理系统的结构、通用技术的学科结构和课堂教学结构等。试想一下，管理大量数据是否也需要用到数据结构呢？ 本章知识要点： 数据结构的基本概念 数据类型和抽象数据类型 算法和算法分析 1.1 数据结构的基本概念 计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算，还是数据处理、过程控制、对文件的存储和检索以及数据库技术等计算机应用，都是对数据进行加工处理的过程。因此，要设计出一个结构良好而且效率较高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。 计算机在发展的初期，其应用围是数值计算，所处理的数据都是整型、实型和布尔型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。随着计算技术的发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中。与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音和视频等复杂的数据。这些复杂的数据不仅量大，而且具有一定的结构。例如，一幅图像是一个由简单数值组成的矩阵，一个图形中的几何坐标可以组成表。此外，语言编译过程
第二章基本数据结构及其运算 一、单项选择题 1．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的
8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素
数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
《数据结构》基本概念
基本概念 ?数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 ?数据元素 数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 ?数据项 数据项是构成数据元素的不可分割的最小单位。?数据对象 数据对象是具有相同性质的数据元素的集合，是数据的子集。 注意：在不产生混淆的情况下，将数据对象简称为数据。 ?数据结构 数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D, R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 ?数据的逻辑结构 数据的逻辑结构是指数据元素之间逻辑关系的整体。
根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵线性结构：数据元素之间存在着一对一的线性关系； ⑶树结构：数据元素之间存在着一对多的层次关系； ⑷图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 ?抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上
/** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环，
基本概念 数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号 集合。 数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项 数据项是构成数据元素的不可分割的最小单位。 数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。 数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = （D, R），其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴ 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在着一对多的层次关系； ⑷ 图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。 数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。 算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法的特性 ⑴ 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 ⑵ 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 ⑶ 有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。 线性表的逻辑关系 在一个非空表L= (a i, a2, , a n)中，任意一对相邻的数据元素和a i之间(1< i < n)存在序偶 关系(a i-i，a i)，且a i-i称为a i的前驱，a i称为的后继。在这个序列中，a i无前驱，a n无后继，其它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义 用MaxSize 表示数组的长度,顺序表的存储结构定义如下： #define MaxSize i00 typedef struct { ElemType data[MaxSize]; // ElemType 表示不确定的数据类型 int length; //length 表示线性表的长度
第1章绪论 知识点归纳 一、数据结构概述 1.数据结构的定义 （1）基本概念 数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。 （2）相关术语 ① 数据元素 数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。 ② 数据项 数据项又称字段或域，它是具有独立含义的最小数据单位。 ③ 数据对象 数据对象是性质相同的数据元素的集合，它是数据的子集。 （3）数据结构的内容 ① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。 ② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。 ③ 施加在数据上的操作，即数据的运算。 （4）逻辑结构 数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 （5）存储结构 数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。 数据的运算最终需在对应的存储结构上用算法实现。 总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。 （6）数据结构的表示 对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。 描述数据结构通常采用二元组表示：
第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构基础知识 数据结构的知识繁杂，但根据数据元素之间关系的不同特性，通常可以归类为下列四类基本结构： （1）集合：数据元素间的关系仅仅是同属一个集合。 （2）线性结构：数据元素间存在一对一的关系。 （3）树形结构：结构中的元素间的关系是一对多的关系。 （4）图结构（网状结构）：结构中的元素间的关系是多对多的任意关系。 集合结构线性结构树形结构图结构（网状结构）一、线性结构 线性结构是N个数据元素构成的有限序列。线性结构存储方式分为顺序存储结构和链式存储结构两种。 1、顺序存储结构 平时使用的数组就是这种结构，比如Pascal：a:[1..100] of longint; C++：int a[100]。（1）（2）（3）（4）（5）（6）（7）（8） 12 13 15 22 34 38 43 20 当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？ 2. 链式存储结构 为了更好了解顺序存储结构和链式存储结构，建议读者看看下列的flash，形象的演示应该比文字说明更好懂。 flash地址：https://www.doczj.com/doc/ba10902452.html,/fine/resources/index.asp第二章“表”中所有flash。 二维数组与线性表 如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。二维数组的一个形象比喻：多个纵队形成的方块m * n 数组地址计算问题 题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij (i>=j ,j=1,2,…,,n)存于b[k]中，问：k,i,j之间的关系如何表示？ 答案：K=i*(i-1)/2+j 栈（略，见1.3） 队列 先进先出。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。 循环队列 头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。 (R-F+N) mod N 二、树型结构 基本概念：根、叶子、子树。 结点的度：结点拥有的子树数 实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图 主函数main 四、实验步骤与算法实现 #in clude 数据结构基本知识 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括： 整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 数据项是具有独立含义的最小标识单位。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的 检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。2、 C 的运算符运算意义、优先级、结合方向。3、算术运算符和算术表达式，各类数值型数据间的混合运算。4、赋值运算符和赋值表达式。5、逗号运算符和逗号表达式。 1 、程序的三种基本结构。2、数据输入输出的概念及在C 语言中的实现。字符数据的输入输出，格式输入与输出。 1 、关系运算符及其优先级，关系运算和关系表达式。2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。3、if语句。if语句的三种形式，if语句的嵌套，条件运算符。4、switch 语句. 1 、while 语句。2、do/while 语句。3、for 语句。4、循环的嵌套。5、break 语句和continue 语句。1 、一维数组的定义和引用。2、二维数组的定义和引用。3、字符数组。4、字符串与字符数组。5、字符数组的输入输出。6、字符串处理函数1 、函数的定义。2、函数参数和函数的值，形式参数和实际参数。3、函数的返回值。4、函数调用的方式，函数的声明和函数原型。5、函数的嵌套调用。 6、函数的递归调用。 7、数组作为函数参数。 8、局部变量、全局变量的作用域。 9、变量的存储类别，自动变星，静态变量。1 、带参数的宏定义。2、“文件包含”处理。1 、地址和指针的概念。2、变量的指针和指向变量的指针变量。3、指针变量的定义 和引用。4、指针变量作为函数参数。5、数组的指针和指向数组的指针变量。6、指向数组元素的指针。7、通过指针引用数组元素。8、数组名作函数参数。9、二维数组与指针。 1 0、指向字符串的指针变星。字符串的指针表示形式，字符串指针作为函数参数。11 、字符指针变量和字符数组的异同。1 2、返回指针值的函数。1 3、指针数组。1 、定义结构体类型变星的方法。2、结构体变量的引用。3、结构体变量的初始化。4、结构体数组5、指向结构体类型数据的指针。6、共用体的概念，共用体变量的定义和引用，共用体类型数据的特点。typedef 1 、数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。2、数据结构的两大类逻辑结构和常用的存储表示方法。3、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 1 、线性表的逻辑结构特征。2、线性表上定义的基本运算。3、顺序表的特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、顺序表上的插入、删除操作及其平均时间性能分析。5、链表如何表示线性表中元素之间的逻辑关系。6、链表中头指针和头结点的使用。7、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。8、顺序表和链表的主要优缺点。9、针对线性表上所需的主要操作，选择时空性能优越的存储结构。 1 、栈的逻辑结构特点．栈与线性表的异同。2、顺序栈和链栈实现的进栈、退栈等基本算法。3、栈的空和栈满的概念及其判定条件。4、队列的逻辑结构特点，队列与线性表的异同。5、顺序队列(主要是循 数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计） 物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度 算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。存储位置：LOC(i ,j)=LOC(0,0)+(b2*i+j)L 结点:包含一个数据元素及若干指向其子树的分支；结点的度: 结点拥有的子树； 树的度:树中所有结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点 树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的树的集合。 二叉树的性质： 性质1：在二叉树的第i 层上至多有2i-1 个结点。(i≥1) 性质2：深度为k 的二叉树上至多含2k-1 个结点。（k≥1） 性质3: 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为2 的结点， 则必存在关系式：n0 = n2+1。 性质4: 具有n 个结点的完全二叉树的深度为?log2n? +1。 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的n 个结点和满二叉树中编号为1 至n 的结点一一对应。 路径长度：路径上分支的数目。树的路径长度：树根到每个结点的路径长度之和。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL(T) =∑w k l k 带权路径长度最小的二叉树，称为最优树二叉树或赫夫曼树。 关键路径：路径长度最长的路径。 目录 目录 (1) 第一章绪论 (5) 一、内容提要 (6) 二、学习重点 (6) 三、例题解析 (6) 第二章线性表 (10) 一、内容提要 (10) 二、学习重点 (11) 三、例题解析 (13) 第三章栈和队列 (21) 一、内容提要 (21) 二、学习重点 (22) 三、例题解析 (24) 第四章串 (36) 一、内容提要 (36) 二、学习重点 (37) 三、例题解析 (37) 第五章数组和广义表 (43) 一、内容提要 (43) 二、学习重点 (44) 三、例题解析 (44) 第六章树和二叉树 (48) 一、内容提要 (49) 二、学习重点 (49) 三、例题及分析 (51) 第七章图 (58) 一、内容提要 (58) 二、学习重点 (59) 三、例题解析 (61) 第八章动态存储治理 (70) 一、内容提要 (70) 二、学习重点 (71) 三、例题解析 (71) 第九章查找 (77) 一、内容提要 (77) 二、学习重点 (78) 三、例题解析 (79) 第十章内部排序 (87) 一、内容提要 (87) 二、学习要点 (88) 二、例题解析 (89) 第十一章外部排序 (98) 一、内容提要 (98) 二、学习要点 (99) 三、习题解析 (99) 第十二章文件 (105) 一、内容提要 (105) 二、学习重点 (106) 第一章绪论 一、内容提要 1 数据结构研究的内容。 2 差不多概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。 3 算法的定义及五个特征。 4 算法描述：类PASCAL语言。 5 算法设计要求。 6 算法分析。 二、学习重点 1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。 2 抽象数据类型的定义、表示和实现方法。 3 类PASCAL书写规范，过程（函数）中值参和变参的差不，过程调用规则。 4 用计算语句频度来估算算法的时刻复杂度。 三、例题解析 #include"iostream" #include"LGraph.h" #include"seqqueue.h" #include"MGraph.h" #define INFTY 1000 template数据结构基础知识整理
数据结构复习提纲(整理)
(9分)基本数据结构
数据结构实现顺序表的各种基本运算(20210215233821)
数据结构基本知识.
数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系
数据结构概念名词解释大全
数据结构对象的基本概念
数据结构 图的基本运算代码
相关主题
文本预览