数据结构：计算机存储、组织数据的方式，它用来反映一个数据的内部构成。
数据：信息的载体，是能够被计算机识别、存储、计算（处理）的符号集合，是计算机处理对象的总称。
数据含义在计算机语言中，十分广泛，除了通常使用的数字、字符串以外，任何能输入到并能被计算机处理的符号都可称为数据。
例如，声音，图片等。
数据元素：也称节点，组成数据的基本单位。可以由若干个数据项（也称字段、域、属性）组成。
例如，短信箱中的一条短信。
数据项：数据的最小单位，具有原子性，不可分割。
例如，一个联系人中的姓名和手机号等。
数据对象：具有相同特征的数据元素的集合，是数据的子集。
例如，短信箱，通讯录等
数据结构：逻辑结构 + 存储结构 + 数据运算
1.逻辑结构：从逻辑关系上描述数据，与数据的存储（内存中的存储位置，存储方式等）无关，且独立于语言。
2.存储结构：也称物理结构，指数据元素及其关系在计算机存储式如何表示，依赖语言。
3.数据运算：通常定义在逻辑结构上，每种逻辑结构都有一个运算的集合，但运算的具体实现要在存储结构上进行。
例如，数据对象的增删改查。
逻辑结构按数据元素之间的相互关系分为线性结构和非线性结构
1.线性结构
有且只有一个开始节点和一个终端节点，并且所有节点最多只有一个直接前驱和一个直接后继节点。
2.非线性结构
一个节点可能有多个直接前驱和直接后继节点。常见的非线性结构，树和图。
算法：为求解一个问题需要遵循的、被清晰地指定的简单指令的集合。通常以某一个数据集合作为输入，执行完一组特定的指令后，返回唯一的数据集合作为输出。
特点：
1.用待处理问题的信息作为输入数据。
2.对一个既定的合法输入，多次执行同一算法，总是返回同一个结果（出随机算法除外）。
3.算法中的指令都是可行的，即每个指令都可实现，并在有限的时间内完成。
4.算法中的指令数量有限，即在有限的时间内，算法可以正确结束。
5.算法执行完毕，能够输出正确的数据集合
算法是一个指令集和，包括控制结构指令和操作指令。即，算法是循环、跳转、判断指令、和数据的操作指令的集合。
算法分析：判断算法的执行效率。复杂度是判断算法优劣的标准，分为时间复杂度和空间复杂度。
1.时间复杂度：算法执行的时间长短
2.空间复杂度：算法在执行过程中所要占用的存储空间。它是额外消耗的存储空间，并不包括算法加载占用的存储空间。越复杂，算法越差。
线性数据结构：线性表、栈、队列等
非线性数据结构：树、图等
============线性表============
线性表：
1.数据元素之间是一对一关系
2.以字符串、数组、栈、队列等形式使用
特点：
1.有且只有一个开始节点和一个终端节点
2.内部节点均有且一个直接前驱和直接后继节点
3.均匀性：不同线性表的数据元素可以多样，但是同一个线性表的数据元素必定是相同的类型
4.有序性：数据元素在线性表中的位置只取决于序列，数据元素间的相对位置是线性的
5.线性表具有增删改查操作。如果需要自定义线性表操作，那么一定要先定义线性表操作的接口，然后在接口中定义线性表的基本操作
线性表的存储的数据在结构中的相对位置是随机的，即和数据的关键字不存在确定的关系，在结构中查找一条数据时，需要进行一系列和关键字做比较的动作。
范例：
1 public interface LinearList { 2 // 判断线性表是否为空 3 public boolean isEmpty(); 4 // 返回线性表的长度 5 public int size(); 6 // 返回指定索引为index的对象 7 public Object get(int index); 8 // 用指定元素替换线性表中指定位置的元素 9 public void set(int index,Object element); 10 // 在线性表的指定位置插入指定元素 11 public Boolean add(int index,Object element); 12 // 在线性表的末尾插入指定元素 13 public Boolean add(Object element); 14 // 删除线性表中指定位置的元素 15 public Object remove(int index); 16 // 清空线性表 17 public void clear(); 18 }
存储方式：
1.顺序存储：用一组连续的内存单元依次存放数据元素，数据元素在内存中的物理储存次序和在线性表中的逻辑次序相同。（数组）
优点：存储密度大。因为存储单位的位置是连续的，几乎不浪费空间。
缺点：插入，删除等不方便。
2.链式存储：用一组地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置不一定相邻。（单链表）
特点：
1.每个元素节点都有一个指针。（产生原因：存储单元地址是分散的，逻辑关系是连续的。它需要一个指针指向元素的后续节点的地址位置）
分类：
a.单链表：也称线性链表，有一个个节点链接而成。每个节点都有一个数据域(nodeValue)和指针域(next)。指针域指向下一个节点的内存存储地址。
b.循环链表：在单链表的基础上，将表尾节点的指针域指向表头节点，整个链表形成环状结构。
c.双链表：可同时向前和向后查找数据元素的单链表。每个节点都有一个数据域和previous和next指针域，分别指向直接前驱节点和直接后继节点。
范例：
1.顺序存储，实现线性表操作的接口LinearList - SequenceList
1 public class SequenceList implements LinearList { 2 3 // 声明对象数组 4 private Object[] slist; 5 // 声明线性表的长度 6 private int size; 7 8 /** 9 * 调用带参构造方法 10 */ 11 public SequenceList() { 12 this(10); 13 } 14 15 public SequenceList(int length) { 16 if (length <= 0) { 17 this.slist = new Object[10]; 18 } 19 this.slist = new Object[length]; 20 size = 0; 21 } 22 23 @Override 24 public boolean isEmpty() { 25 if (size == 0) { 26 return true; 27 } else { 28 return false; 29 } 30 31 } 32 33 @Override 34 public int size() { 35 return size; 36 } 37 38 @Override 39 public Object get(int index) { 40 checkIndex(index); 41 return (Object)slist[index]; 42 } 43 44 @Override 45 public void set(int index, Object element) { 46 checkIndex(index); 47 slist[index] = element; 48 49 } 50 51 @Override 52 public Boolean add(int index, Object element) { 53 checkIndex(index); 54 if (size == slist.length) { 55 Object[] temp = slist; 56 this.slist = new Object[temp.length * 2]; 57 for (int j = 0; j < temp.length; j++) { 58 slist[j] = temp[j]; 59 } 60 } 61 for (int i = size - 1; i >= index; i--) { 62 slist[i + 1] = slist[i]; 63 } 64 slist[index] = element; 65 size++; 66 return true; 67 } 68 69 @Override 70 public Boolean add(Object element) { 71 return add(size,element); 72 } 73 74 @Override 75 public Object remove(int index) { 76 checkIndex(index); 77 Object old = (Object)slist[index]; 78 for (int i = index; i < size - 1; i++) { 79 slist[i] = slist[i + 1]; 80 } 81 slist[size--] = null; 82 return old; 83 } 84 85 @Override 86 public void clear() { 87 if (size != 0) { 88 for (int i = 0; i < size; i++) { 89 slist[i] = null; 90 } 91 size = 0; 92 } 93 94 } 95 96 /** 97 * @Description: 判断传入的索引值对于当前的线性表是否合法 98 * @param index 99 */ 100 public void checkIndex(int index) { 101 if (index >= size || index < 0) { 102 throw new IndexOutOfBoundsException("index" + index + "size" + size); 103 } 104 } 105 106 }
2.单链表
a.节点类 - Node
1 public class Node { 2 // 节点值 3 private Object nodeValue; 4 // 指针 5 private Node next; 6 7 public Node() { 8 nodeValue = null; 9 next = null; 10 } 11 12 /** 13 * 初始化节点值 14 * @param item 15 */ 16 public Node(Object item) { 17 nodeValue = item; 18 next = null; 19 } 20 21 /** 22 * 初始化节点值和指针 23 * @param item 24 * @param next 25 */ 26 public Node(Object item,Node next) { 27 nodeValue = item; 28 this.next = next; 29 } 30 31 public Object getNodeValue() { 32 return nodeValue; 33 } 34 35 public void setNodeValue(Object nodeValue) { 36 this.nodeValue = nodeValue; 37 } 38 39 public Node getNext() { 40 return next; 41 } 42 43 public void setNext(Node next) { 44 this.next = next; 45 } 46 }
b.SingleLinkedList
1 public class SingleLinkedList implements LinearList { 2 3 private Node head; 4 5 /** 6 * 初始化head为空 7 */ 8 public SingleLinkedList(){ 9 head = null; 10 } 11 12 /** 13 * 初始化head 14 */ 15 public SingleLinkedList(Node head){ 16 this.head = head; 17 } 18 19 @Override 20 public boolean isEmpty() { 21 return head == null; 22 } 23 24 @Override 25 public int size() { 26 int size = 0; 27 Node p = this.head; 28 while (p != null) { 29 size++; 30 p = p.getNext(); 31 } 32 return size; 33 } 34 35 @Override 36 public Object get(int index) { 37 checkIndex(index); 38 Node p = this.head; 39 for (int i = 0; i < index; i++) { 40 p = p.getNext(); 41 } 42 return (Object)p.getNodeValue(); 43 } 44 45 @Override 46 public void set(int index, Object element) { 47 checkIndex(index); 48 Node p = this.head; 49 for (int i = 0; i < index; i++) { 50 p = p.getNext(); 51 } 52 p.setNodeValue(element); 53 54 } 55 56 @Override 57 public Boolean add(int index, Object element) { 58 if (index < 0) { 59 throw new IndexOutOfBoundsException("index" + index); 60 } 61 if (head == null) { 62 head = new Node(element); 63 } else { 64 Node p = this.head; 65 if (index == 0) { 66 this.head = new Node(element,p); 67 } else { 68 int i = 0; 69 while (p.getNext() != null && i < index - 1) { 70 i++; 71 p = p.getNext(); 72 } 73 p.setNext(new Node(element,p.getNext())); 74 } 75 } 76 return false; 77 } 78 79 @Override 80 public Boolean add(Object element) { 81 return add(Integer.MAX_VALUE, element); 82 } 83 84 @Override 85 public Object remove(int index) { 86 checkIndex(index); 87 Object old = null; 88 Node p = this.head; 89 if (index == 0) { 90 old = (Object)this.head.getNodeValue(); 91 head = p.getNext(); 92 p = null; 93 } else { 94 int i = 0; 95 while (p.getNext() != null && i < index - 1) { 96 i++; 97 p = p.getNext(); 98 } 99 Node temp = p.getNext(); 100 old = (Object)temp.getNodeValue(); 101 p.setNext(temp.getNext()); 102 temp = null; 103 } 104 return old; 105 } 106 107 @Override 108 public void clear() { 109 head = null; 110 111 } 112 113 public void checkIndex(int index) { 114 if (index < 0 || index > this.size() - 1) { 115 throw new IndexOutOfBoundsException("index" + index); 116 } 117 } 118 119 }
线性表的顺序查找
除了增删查改等基本操作外，还有一些常见的操作，例如从线性表中获取数据的位置
范例：有一个线性表，表中数据域存储A-G7个大写英文字母，查找“F”的位置。
1.查找类
1 /** 2 * @Description: 查找类 3 * @author Ivy 4 */ 5 public class Search { 6 public static int search_seq(LinearList ST,String key) { 7 int i = 0; 8 while (!ST.get(i).equals(key)) { 9 i++; 10 } 11 return i; 12 } 13 }
2.测试类
1 public class Test { 2 public static void main(String[] args) { 3 LinearList ST = new SequenceList(); 4 String key = "F"; 5 ST.add("A"); 6 ST.add("B"); 7 ST.add("C"); 8 ST.add("D"); 9 ST.add("E"); 10 ST.add("F"); 11 ST.add("G"); 12 int i = Search.search_seq(ST, key); 13 System.out.println("关键字F的位置：" + i); 14 } 15 }