資料結構---集合與映射

1.01 集合（Set）

存儲不重複元素的容器

有序集合中的元素具有順序性，基于搜尋樹實作；

無序集合中的元素沒有順序性，基于哈希表實作。

順序性，是指按照元素的大小進行排序，并非指插入的順序 
有序性，是指元素的進場順序和出場順序一緻

應用場合

客戶統計 
詞彙量統計

1.02 Set集合接口定義

資料結構---集合與映射

public interface Set<E>{
	void add(E e);	//向集合中添加元素e（不能添加重複元素）
	void remove(E e);	//删除集合中指定元素e
	boolean contains(E e);	//判斷是否包含指定元素
	int getSize();	//擷取集合中元素的個數
	boolean isEmpty();	//判斷集合是否為空
}

1.03 BSTSet基于二分搜尋樹實作的集合類定義

public class BSTSet<E extends Comparable<E>> implements Set<E>{
	private BinarySearchTree<E> tree;
	public BSTSet(){
		tree=new BinarySearchTree<E>();
	}
	public void add(E e){
		tree.add(e);
	}
	public void remove(E e){
		tree.remove(e);
	}
	public boolean contains(E e){
		return tree.contains(e);
	}
	public int getSize(){
		return tree.size();
	}
	public boolean isEmpty(){
		return tree.isEmpty();
	}
	public void show(){
		tree.inOrder();
	}
}

1.04 LinkedListSet基于連結清單實作的集合類定義

public class LinkedListSet<E> implements Set<E>{
	private LinkedList<E> list;
	public LinkedListSet(){
		list=new LinkedList<E>();
	}
	public void add(E e){
		if(!list.contains(e)){
			list.addHead(e);
		}
	}
	public void remove(E e){
		list.removeElement(e);
	}
	public boolean contains(E e){
		return list.contains(e);
	}
	public int getSize(){
		return list.getSize();
	}
	public boolean isEmpty(){
		return list.isEmpty();
	}
}

1.05 應用：讀取小說中的單詞，對比兩種不同的實作方式（時間複雜度分析）

資料結構---集合與映射

1.06 二分搜尋樹最壞情況

其結構退化成連結清單，用平衡二叉樹解決該問題

資料結構---集合與映射

1.07 Java中對于集合相關的常見内置類

資料結構---集合與映射

1.08 映射（Map）

映射就是存儲（鍵，值）資料對的資料結構（Key，Value）。根據鍵（Key），尋找值（Value）

有序映射中的鍵具有順序性，基于搜尋樹實作

無序映射中的鍵沒有順序性，基于哈希變實作

資料結構---集合與映射

1.09 Map接口定義

資料結構---集合與映射

public interface Map<K,V>{
	void add(K key,V value);	//向集合中添加鍵值對
	V remove(K,key);	//删除元素
	boolean contains(K key);	//是否包含某元素
	V get(K key);	//根據鍵擷取值
	void set(K key,V value);	//修改元素
	int getSize();	//擷取其有效長度
	boolean isEmpty();	//是否為空
}

1.10 LinkedListMap基于連結清單實作的映射類定義

定義類

public class LinkedListMap<K,V> implaments Map<K,V>

定義内部類結點

private class Node{
	public K key;
	public V value;
	public Node next;
	public Node(K key.V value){
		this.key=key;
		this.value=value;
	}
	public Node(){ //虛拟頭結點
		this(null,null);
	}
	public String toString(){
		return key.toString()+":"+value.toString();
	}
}

定義成員變量

private Node head;
private int size;

定義構造函數

public LinkedListMap(){
	head=new Node();
	size=0;
}

實作功能

public void add(K key,V value){
	Node node=getNode(key);
	if(node==null){	//添加元素
		node=new Node(key,value);
		node.next=head.next;
		head.next=node;
		size++;
	}else{	//修改元素
		node.value=value;
	}
}

public V remove(K key){
	Node pre=head;
	while(pre.next!=null){
		if(pre.next.key.equals(key)){
			break;
		}
		pre=pre.next;
	}
	if(pre.next!=null){	//找到要删除的元素後 在連結清單中删除該結點
		Node delNode=pre.next;
		pre.next=delNode.next;
		delNode.next=null;
		size--;
		return delNode.value;
	}
	return null;
}

public boolean contains(K key){
	return getNode(key)!=null;
}

public V get(K key){
	Node node=getNode(key);
	return node==null?null:node.value;
}

public void set(K key,V newValue){
	Node node=getNode(key);
	if(node==null){
		throw new IllegalArgumentException("doesn't exist!");
	}
	node.value=newValue;
  }
  
  public int getSize(){
  	return size;
  }
  
  public boolean isEmpty(){
  	return size==0;
  }
  
  private Node getNode(K key){
  	Node cur=head.next;
  	while(cur!=null){
  		if(cur.key.equals(key)){
  			return cur;
  		}
  		cur=cur.next;
  	}
  	return null;
  }
  
  public String toString(){
  	if(isEmpty()){
  		return "[]";
  	}
  	StringBuilder sb=new StringBuilder("[");
  	Node p=head;
  	while(p.next!=null){
  		p=p.next;
  		if(p.next!=null){	//如果不是最後一個與元素
  			sb.append("("+p+")"+",");
  		}else{	//如果是最後一個元素
  			sb.append("("+p+")"+"]\n");
  		}
  	}
  	return sb.toString();
  }
}

1.11 BSTMap基于二分搜尋樹實作的映射類定義

定義類

public classBSTMap<K extends Comparable<K>,V> implements Map<K,V>

定義内部類結點

private class Node{
	public K key;
	public V value;
	Node left,right;
	public Node(K key,V value){
		this.key=key;
		this.value=value;
		left=null;
		right=null;
	}
	public String toString(){
		return "("+key+","+value+")";
	}
}

定義成員變量

private Node root;
private int size;

定義構造函數

public BSTMap(){
	root=null;
	size=0;
}

實作功能

public int getSize(){
	return size;
}

public boolean isEmpty(){
	return size==0;
}

public void add(K key,V value){
	root=add(root,key,value);
}
private Node add(Node node,K key,V value){
	if(node==null){
		size++;
		return new Node(key,value);
	}
	if(key.compareTo(node.key)<0){
		node.left=add(node.left,key,value);
	}else if(key.compareTo(node.key)>0){
		node.rigth=add(node.rigth,key,value);
	}else{
		node.value=value;
	}
	return node;
  }
public V get(k key){
	Node node=getNode(root,key);
	return node==null?null:node.value;
}

public void set(K key,V value){
	Node node=getNode(root,key);
	if(node==null){
		throw new IllegalArguamentException("doesn't exist");
	}
	node.value=value;
}

public V remove(K key){
	Node node=getNode(root,key);
	if(node!=null){
		root=remove(root,key);
		return node.value;
	}
	return null;
}
private Node remove(Node node,K key){
	if(node==null){
		return null;
	}
	if(key.compareTo(node.key)<0){	//所找元素小于目前結點
			node.left=remove(node.left,key);
			return node;
	}else if(key.compareTo(node.key)>0){	//所找元素大于目前結點
		node.right=remove(node.right,key);
		return node;
	}else{	//找到所找元素
		if(node.left==null){
			Node rigthNode=node.right;
			node.right=null;
			size--;
			return rightNode;
		}
		if(right==null){
			Node leftNode=node.left;
			node.left=null;
			size--;
			return leftNode;
		}
		Node newcurRoot=minmun(node.right);
		newcurRoot.right=removeMin(node.right);
		newcurRoot.left=node.left;
		node.left=node.right=null;
		return newcurRoot;
	}
}

private Node minmum(Node node){
	if(node==null){
		return null;
	}else{
		return minmum(node.left);
	}
}

private Node removeMin(Node node){
	if(node.left==null){
		Node rightNode=node.right;
		node.right=null;
		size--;
		return rightNode;
	}
	node.left=ewmoveMin(node.left);
	return node;
}

public boolean cotains(k key){
	return getNode(root,key)!=null;	
}

private Node getNode(Node node,K key){
	if(node==null){
		return null;
	}
	if(key.compareTo(node.key)<0){
		return getNode(node.left,key);
	}else if(key.compareTo(node.key)>0){
		return getNode(node.right,key);
	}else{
		return node;
	}
}

對比兩者的時間複雜度

資料結構---集合與映射

資料結構---集合與映射

繼續閱讀

leetcode 454. 四數相加 II c語言

線性表順序存儲

構造二叉樹的三種方法

排序算法總結及Python實作一、冒泡排序、選擇排序和插入排序:O(n*n)二、歸并排序和快速排序:O(nlogn)三、桶排序和基數排序:O(n)

資料結構分類

leetcode 136. 隻出現一次的數字 c語言

LeetCode 02.08. 環路檢測

資料結構——排序算法（選擇排序）

分治算法解決最大子數組問題

資料結構（三）二叉樹二叉樹

資料結構練習--雙向連結清單的實作

資料結構算法---二叉樹

《劍指offer》c++版本 17.列印從1到最大的N位數

二叉樹周遊(zz)

算法學習筆記--貪婪算法算法學習筆記–貪婪算法