数据结构笔记
线性表
一、顺序表（线性表的顺序存储结构）
1.顺序表的存储结构
#define MaxSize 100
struct List{
ElemType data[MaxSize]; // 顺序表的元素
int len; // 顺序表的长度
}List;
2.节点的插入（在顺序表的L的第i个位置插入元素e）：O(n)
// 1 <= i <= L.len+1
bool ListInsert(List &L, int i, ElemType e){
// defend
if(i < 1 || i > L.len+1){
return false;
}
if(L.len >= MaxSize){
return false;
}
// Insert
for(int j = L.len; j >= i; j--){ // 调整 i 号开始的后继元素
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; // 赋值，插入
L.len += 1;
return L;
}
最好情况（表尾插入，不需要移动元素）：O(1)
最坏情况（表头插入，需移动所有元素）：O(n)
平均情况：O(n/2)
3.节点的删除（删除顺序表L的第i个位置的元素，并将其值返回）：O(n)
bool ListDelete(List &L, int i, ElemType &e){
// defend
if(i<1 || i>L.len){
return false;
}
e = L.data[i-1];
for(int j = i; j < L.len; j++){
L.data[j-1] = L.data[j];
}
L.len -= 1;
return true;
}
最好情况（表尾删除，无需移动元素）：O(1)
最坏情况（表头删除，需移动所有元素）：O(n)
平均情况：O((n-1)/2)
4.按值查找（在顺序表L中查找值为e的元素，并返回其位序）：O(n)
int LocateElem(List L, ElemType e){
for(int i = 0; i < L.len; i++){
if(L.data[i] == e){
return i+1;
}
}
return 0;
}
最坏情况（待查找元素在表头，比较一次即可）：O(1)
最好情况（待查找元素在表尾，比较整个列表）：O(n)
平均情况：O((n+1)/2)
二、单链表（顺序表的链式存储结构）
1.单链表的存储结构
struct LNode{
ElemType data; // 数据域
struct LNode * next; // 指针域
}LNode, *LinkList;
2.链表的构建（头插法）
LinkeList CreateList(LinkList &L){
// 头指针的构造
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
// 获取后续插入节点的数值
int x;
scanf("%d",&x);
LinkList s; // 创建插入节点
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
3.链表的构建（尾插法）
LinkList CreateList(LinkList &L){
// 头指针的构造，并让尾指针指向当前头指针位置
L = (LinkList)malloc(sizeof(LNode));
LinkList r = L;
int x;
scanf("%d", &x);
LinkList s;
while(x != 9999){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &X);
}
r->next = NULL;
return L;
}
4.按序号查找（查找单链表L中的第i个元素）
LinkList GetElem(LinkList L, int index){
LinkList p = L->next; // 头节点指针赋值给p
int j = 1; // 头节点的序号
if(index == 0){ // index = 0，即返回头节点
return L;
}
if(index < 1){ // index 无效
return NULL;
}
while(p && j < index){
p = p->next;
j++;
}
return p;
}
5.按值查找（查找单链表中值为e的元素）
LinkList LocateElem(LinkeList L, ElemType e){
LinkList p = L->next;
while(p && p->data != e){
p = p->next;
}
return p;
}
6.节点的插入（将值为x的节点插入到L的i号位置上）
p = GetElem(L, i-1);
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
7.节点的删除（将单链表L中i号位置的元素删除）
p = GetElem(L, i-1);
q = p->next;
p->next = q->next;
free(q)
三、双链表（在单链表的基础上添加前驱指针）
1.双链表的存储结构
struct DLNode{
ElemType data; // 数据域
struct DLNode *prior, *next; // 前驱和后继节点
}DLNode, *DLinkList;
2.节点的插入（在双链表L中p节点之后插入节点s）
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
3.节点的删除（删除双链表p节点的后继节点q）
p->next = q->next;
q->next->prior = p;
free(q);
四、静态链表
1.静态链表的存储结构
#define MaxSize 100
struct SLink{
ElemType data;
int next; // 下一个元素的数组下标
}SLink[MaxSize];
基本结构
- 1、集合：数据元素同属一个集合
- 2、线性结构：数据元素间存在一对一的关系
- 3、树形结构：结构中元素间是一对多的关系
- 4、图状结构：结构中元素间是多对多的关系
逻辑结构:数据元素之家存在的关系称为数据的逻辑结构
物理结构:树蕨结构在计算机的表示称为数据的物理结构
数据结构在计算机中表示称为数据的物理结构
队列接口：
interface Queue{
void add(Object obj); //向队尾插入元素
Object remove(); //从队头删除元素
int size(); //查看队列的长度
}
可以通过实现这个接口，将数据存储到这个数据结构中，以方便存取。
例：
import java.util.*;
public class DataStructureInterface {
public static void main(String args[]){
ArrayList al=new ArrayList();
al.add("zzz");
al.add("zst");
al.add("cxk");
for(int i=0;i<al.size();i++){
System.out.println(al.get(i));
}
}
}
1、Collection集合接口
Collection接口是数据集合接口，它位于数据结构API的最上部。构成Collection的单位，被称之为元素。接口提供了添加、删除元素等管理数据的功能。根据数据管理的方法不同，可将Collection接口分成为3个部分，分别是：Map接口、Set接口、List接口
所有实现Collection接口的类都必须提供两个标准的构造函数：
*无参数的构造函数，用于创建一个空的Collection
*带Collection参数的构造函数，用于创建一个新的Collection。
这个新的Collection与传入的Collection拥有相同的元素。
（带参数的构造函数主要用来实现复制一个Collection）
如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持iterator()方法，该方法返回迭代器。使用该迭代器即可访问Collection中的每一个元素。
如：
Iterator it=collection.iterator(); //获得一个迭代器
while(it.hasnext()){
Object obj=it.next(); //得到下一个元素
}
List接口和Set接口是两个非常有用的集合接口，数组和列表等数据结构，基本上都是从这两个接口实现而来。
1、List接口：
List接口是有序的Collection，使用此接口能够精确地控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于数组。除了具有Collection接口必备的iterator()方法外，List还提供listIterator()方法，其返回ListIterator接口。和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加、删除、设定元素，还能向前和向后遍历。
实现List接口的常用类有LinkedList和ArrayList。
2、LinkedList链表类
LinkedList实现了List接口，允许null元素。此外LinkedList在首部或尾部提供额外的get()、remove()、insert()等方法。LinkedList没有同步方法，如果多个线程同时访问一个List，则必须自己实现访问同步，一种解决方法是在创建List时构造一个同步的List。
List list=Collection.synchronizedList(new LinkedList(…));
3、ArrayList 数据列表类
ArrayList实现了可变大小的数组，它允许存储所有元素，包括null。ArrayList没有同步。每个ArrayList实例都拥有一个容量(Capacity)属性，即存储元素的数组的大小，这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可调用ensureCapacity()方法来增加ArrayList的容量，以提高插入效率。和LinkedList一样，ArrayList也是非同步的。
2、Set接口
Set是一种不包含重复元素的Collection，即任意的两个元素e1和e2比较，结果都不相等。Set最多有一个null元素。实现Set接口的常用类有HashSet和TreeSet
1、HashSet集合类
HashSet类实现了Set接口，允许null元素。在具体使用该类时，要特别注意其不保证集合的迭代顺序，即不保证该顺序恒久不变。关于该集合类的基本操作包括add()、remove()、contains()、size()等方法。
TreeSet集合类
TreeSet类实现了Set接口，与HashSet类相比，该类实现了排序功能。存储在该集合中的元素默认按照升序排序元素，或者根据使用的构造方法不同，可能会按照元素的自然顺序进行排序，或者按照在创建Set集合时所提供的比较器进行排序。
3、Map映射接口
Map没有继承Collection接口，其提供key到value的映射。Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合、一组value集合或一组key-value映射。
1、Hashtable散列表类
Hashtable继承Map接口，实现一个key-value映射的散列表。任何非空(non-null)的对象都可作为key或value。添加数据使用put(key,value)方法，取出数据使用get(key)方法，这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常默认的load factor 0.75较好地实现了时间和空间的均衡，增大load factor可以节省时间，但相应的查找时间将增大，这会影响像get和put这样的操作。
例：
Hashtable numbers=new Hashtable();
numbers.put("one",new Integer(1));
numbers.put("two",new Integer(2));
numbers.put("three",new Integer(3));
//如果想取出2，可以用相应的key
Integer n=(Integer)numbers.get("two");
System.out.println("two="+n);
作为key的对象，将通过计算其散列函数确定与之对应的value位置，因此任何key的对象都必须实现hashCode()和equals()方法。hashCode()和equals()方法继承于根类Object。如果用自定义的类当作key，则要相当小心。按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true,则它们的hashCode必须相同。但如果两个对象不同，则它们的hashCode不一定不同。如果两个不同对象的hashCode相同，这种现象称为冲突。冲突会导致操作散列表的时间开销增大，所以尽量定义好的hashCode()方法，能加快散列表的操作。
所以注意：要同时复写equals()方法和hashCode()方法，而不要只写其中的一个。Hashtable是同步的。
2、HashMap散列映射类
HashMap和Hashtable类似，但是HashMap是非同步的，并且允许null，即null value和null key。如将HashMap视为Collection时(values()方法可以返回Collection)，其迭代器操作时间开销和HashMap的容量成比例。因此，迭代操作的性能相当重要，切记不要将HashMap的初始容量设得过高，或者将load factor设得过低。
4、Lterator迭代器接口
什么是迭代器？迭代器指向两个元素中间的位置，当调用hasNext()方法时，如果返回true，此时调用next()方法返回下一元素。迭代器指向下两个元素之间的位置，如果要删除下一个元素，必须先调用next()方法，再调用remove()方法。
Iterator接口中定义了以下3个方法：
hasNext()：是否还有下一个元素
next():返回下一个元素
remove():删除当前元素
1、迭代器作用
有些接口类没有提供get()操作，这时可用迭代器来获得信息。所有Collection接口的子类、子接口都支持Iterator迭代器。迭代器模式又称为游标模式。
官方定义：提供一种方法访问一个容器对象中各个元素，而又不需暴露该对象的内部细节，这就是迭代器。
2、迭代器模式：由以下角色组成
（1）迭代器角色：负责定义访问和遍历元素的接口迭代器角色定义了遍历的接口，但是没有规定由谁来控制迭代。在JavaCollection的应用中，由客户程序来控制遍历的进程，被称为外部迭代器。还有一种实现方式是由迭代器自身来控制迭代，被称为内部迭代器。外部迭代器要比内部迭代器灵活，强大，而且内部迭代器在Java中，可用性很弱
（2）具体迭代器角色：实现迭代器接口，并记录遍历中的当前位置
（3）容器角色：负责提供创建具体迭代器角色的接口
（4）具体容器角色：实现创建具体迭代器角色的接口————这个具体迭代器角色与该容器的结构相关
注：在迭代器模式中，没有规定谁来实现遍历算法。因为既可以在一个容器上使用不同的遍历算法，也可以将一种遍历算法应用于不同的容器。这样就破坏了容器的封装————容器角色就要公开自己的私有属性。那把它放入容器角色里实现，这样迭代器角色被架空，仅仅具备存放一个遍历当前位置的功能，但是遍历算法和特定的容器紧紧绑在一起。而在Java Collection的应用中，提供的具体迭代器角色是定义在容器角色中的内部类，这样便保护了容器的封装。同时容器也提供遍历算法接口，用户可以扩展自己的迭代器。
容器角色，以List为例。它也仅仅是一个接口，不罗列具体容器角色，是实现了List接口的ArrayList等类。这里只介绍和迭代器相关的内容，具体迭代器角色是以内部类的形式表现出来的。AbstractList是为了将各个具体容器角色的公共部分提取出来而存在的。
设计代码如下：
//迭代器角色，仅仅定义了遍历接口
public interface Iterator{
//声明方法
boolean hasNext();
Object next();
void remove();
}
public abstract class AbstractList implements List{
······
//这个便是负责创建具体迭代器角色的工厂方法
public Iterator iterator(){
return new Itr();
}
}
//作为内部类的具体迭代器角色
private class Itr implements Iterator{ //实现接口
//创建成员变量
int cursor=0;
int lastRet=-1;
int expectedModCount=modCount;
public boolean hasNext(){
return cursor!=size();
}
public Object next(){
checkForComodification();
try{
Object next=get(cursor);
lastRet=cursor++;
return next;
}catch(IndexOutOfBoundsException e){
checkForComodification():
throw new NoSuchElementException():
}
}
public void remove(){
if(lastRet==-1)
throw new IllegalStateException();
checkForComodification();
try{
AbstractList.this.remove(lastRet);
if(lastRet<cursor)
cursor--;
lastRet=-1;
expectedModeCount=modCount;
}catch(IndexOutofBoundsException e){
throw new ConcurrentModificationException();
}
}
//设计方法checkForComodification()
final void checkForComodification(){
if(modCount!=expectedModCount)
throw new ConcurrentModificationException();
}
}
至于迭代器模式的使用，要先得到具体容器角色，然后再通过具体容器角色，得到具体迭代器角色。这样就可以使用具体迭代器角色来遍历容器。上述代码不是完整程序，只是演示各个角色的创建过程。
3、迭代器模式优势
（1）支持以不同的方式遍历一个容器角色，根据实现方式的不同，效果上会有差别。
（2）简化了容器的接口，但是在java Collection中为了提高可扩展性，容器还是提供了遍历的接口。
（3）对同一个容器对象，可以同时进行多个遍历，因为遍历状态保存在每一个迭代器对象中。
4、杂项
1、Collection集合接口与Collections集合类的区别
Collections是java.util下的类，它包含各种有关集合操作的静态方法。
Collection是java.util下的接口，它是各种集合结构的父接口。
*List、Set继承自Collection接口，Map不继承Collection接口。
2、ArrayList数组列表类和Vector存储类的区别
同步性：Vector是线程安全的，是同步的。而ArrayList是线程不安全的，不是同步的。
数据增长：当需要增长时，Vector默认增长为原来一倍，而ArrayList却是原来的一半。
3、HashMap散列映射和Hashtable散列表的区别
二者都属于Map接口的类，作用都是将唯一键映射到特定的值上。
而HashMap类没有分类或排序，它允许一个null键和多个null键。
而Hashtable类似于HashMap，但是不允许有null键和null值，它也比HashMap慢，因为它是同步的。
4、数据结构的种类
数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构包括：线性表、栈、队列、串、数组和文件；非线性数据结构包括：树、图。
5、List接口和Set接口的区别
List:是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。这里的有序就是指有顺序的排放，并不是排序。
相关资料
https://blog.csdn.net/snvjd/article/details/103284531