第1章 概述
第2章 线性表
第3章 栈和队列
第4章 串、矩阵和广义表
第5章 树和二叉树
第6章 图
第7章 查找
第8章 排序
一.第1章 概述
1. 数据
所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息 )
2. 数据元素
数据元素是数据的基本单位
3. 数据项
数据项是数据的最小单位。
4. 数据对象
具有相同特征的数据元素的集合称为数据对象。
5. 数据结构
相互之间存在一种或多种特定关系的数据元素的集合。
数据元素之间的相互关系称为结构。
数据元素之间的相互关系称为结构
数据结构包括逻辑结构、物理结构(即存储结构)和对数据的操作三个方面
数据结构的形式化定义:
Data_Structure = (D, S)
其中,D是数据元素的有限集合,S是D上关系的有限集合,是数据元素之间的逻辑关系
S=(D, R)
D={ a, b, c, d, e, f }
R={<a,e>, <b,c>, <c,a>, <e,f>, <f,d>}
四种存储结构分别为:顺序、链式、索引、散列
![](https://img-blog.csdnimg.cn/20201205161953114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ5MTc3NjQ1,size_16,color_FFFFFF,t_70)
![](https://img-blog.csdnimg.cn/20201205161413614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ5MTc3NjQ1,size_16,color_FFFFFF,t_70)
![](https://img-blog.csdnimg.cn/20201205162012995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ5MTc3NjQ1,size_16,color_FFFFFF,t_70)
![](https://img-blog.csdnimg.cn/20201205162025348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ5MTc3NjQ1,size_16,color_FFFFFF,t_70)
泛型类是一种所操作的数据的类型尚不明确而临时使用类型参数来表示的自定义数据类型
public class MyList<T>{
T[] arr; //T表示泛型,实例化时需要使用具体的类型
int length;
public MyList(int len)
{
arr= (T[]) new Object[len];
len=0;
}
……
}
实例化:MyList<String> list=new MyList<String>(10);
抽象数据类型(ADT)
定义格式:
ADT 抽象数据类型名{
数据对象:<数据对象的定义> (即:同类型数据元素的集合)
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
} ADT 抽象数据类型名
基本操作的定义格式:<操作名称> (参数列表);
复数抽象数据类型定义:
ADT Complex{
数据对象:D={real,imag,其中real为实部,imag为虚部}
数据关系:R={<real,imag>}
基本操作:
Complex(real,imag); //构造实部和虚部分别为real和imag的复数
add(c);//返回当前复数与复数c的和
sub(c);//返回当前复数与复数c的差
}
抽象数据类型描述数据结构的逻辑特性和操作集合,与其存储结构及实现无关。
//1.定义抽象数据类型:定义相应的接口
public interface 接口名<T>{
//T是泛型参数,可使类或方法操作多种类型的数据对象
public abstract 类型 方法名1(); //每个方法对应抽象数据类型的一个操作
public abstract 类型 方法名2();
……
}
//2、实现抽象数据类型:定义实现接口的类
public class 类名<T> implements 接口名<T>{
//定义成员变量
//实现接口中的方法
}