java基础复习（二）

一、数据结构
1、概述

数据结构（data structure）：是计算机专业一门独立学科，主要研究数据的逻辑结构、存贮结构以及数据之间的关系

什么是数据：

    在计算机系统中，各种字母和数字符号的组合、语音、图形、图像等统称为数据
    又指所有能输入计算机并且被计算机程序处理的符号的总称，是用于输入计算机进行处理，具有一定意义的数字、字母、符号和模拟量的统称

2、数据结构
1.逻辑结构

    集合

一个存放数据的容器，数据元素间没有任何关系

    线性结构

数据元素间有线性关系，分为线性表、队列、栈和串

线型关系：除第一个元素外，其他元素有且只有一个前驱，除最后一个元素外，其他元素有且只有一个后继

    树结构

数据元素间有层状关系，例如二叉树

    图结构

数据元素间有网状关系
2.存储结构

    顺序存储结构

数据存放在磁盘连续的空间中

    链式存储结构

数据存放在磁盘的任何位置，单向链式存贮（单链表）、双向链式存贮（双链表）、循环链式存贮（循环链表）
3、线性结构
1、线性表

基于数组实现线性结构 ，用数组存放数据，并保持元素之间是一个线性关系

编写线性结构的数据结构：
public void insert(int i,Object data);  // 添加到线性表指定的位置;
public void append(Object data);  // 追加到线性表的末尾;
public void remove(int i);  // 移除元素
public void update(int i,Object data);  // i为下标 ；
public Object get(int i);  // 获取元素
public Object[] list();
public int size();  // 线性表元素数量;
public boolean isEmpty();  // 线性表是否为空;

public void insert(int i,Object data);  // 添加到线性表指定的位置;
public void append(Object data);  // 追加到线性表的末尾;
public void remove(int i);  // 移除元素
public void update(int i,Object data);  // i为下标 ；
public Object get(int i);  // 获取元素
public Object[] list();
public int size();  // 线性表元素数量;
public boolean isEmpty();  // 线性表是否为空;

public void insert(int i,Object data);  // 添加到线性表指定的位置;
public void append(Object data);  // 追加到线性表的末尾;
public void remove(int i);  // 移除元素
public void update(int i,Object data);  // i为下标 ；
public Object get(int i);  // 获取元素
public Object[] list();
public int size();  // 线性表元素数量;
public boolean isEmpty();  // 线性表是否为空;

boolean offer(E e);  // 添加数据
Object poll();   // 删除出队
Object peek();  // 返回队列第一次元素（不删）
int size();  // 元素数量
boolean isEmpty();  // 判断队列是否为空

4、串

串：即字符串（String），是由零个或多个字符组成的有限序列。一般表示为s=“c1,c2,c3...cn”

子串：串中任意个连续的字符组成的子序列

主串：包含子串的串

空串：n=0的串

空格串：值为空格的串
4、树结构

树是一种非线性的数据结构，由n（n>0）个有限结点组成的具有层次关系的集合。

树有一个特殊的结点，叫根结点，根结点没有前驱结点。

树形结构中，子树之间不能有交集。

树的性质如下：

    每个子树有且只有一个前驱结点
    每个子树的根结点可以有0或多个后继结点
    数是递归的
    一个n个结点的数有n-1条边

5、图结构

图结构是比线性表和树结构更为复杂的数据结构。

树结构中，子树之间不能有交集，但在图结构中，是可以有交集的。

图结构中有顶点和边

顶点：图中的数据元素

边：图中连接顶点的线

所有的顶点组成一个顶点集合，所有的边组成一个边集合，组合在一起就是一个图结构

无向图：在一个图中，如果所有的边都没有方向，则称之为无向图

有向图：在一个图中，边有方向，则称之为有向图

混合图：一个图中，边同时有有向和无向的图