算法开头1--数据结构(数组和链表) - 好文

文章目录

* 1. 基础-==区分数组和链表==
<https://blog.csdn.net/xyjworkgame/article/details/87893582#1__1>
* 1. 更常用的数据结构了
<https://blog.csdn.net/xyjworkgame/article/details/87893582#1__24>
* `栈，链表，包` <https://blog.csdn.net/xyjworkgame/article/details/87893582#_25>
* 1. 栈 <https://blog.csdn.net/xyjworkgame/article/details/87893582#1__26>
* 2. 队列 <https://blog.csdn.net/xyjworkgame/article/details/87893582#2__77>
* 3. 背包 <https://blog.csdn.net/xyjworkgame/article/details/87893582#3__141>

<>1. 基础-区分数组和链表

* 对数组和链表的优缺点
数据结构优点缺点
数组通过索引可以直接访问任意元素在初始化就需要知道元素的数量
链表使用的空间大小和元素数量成正比需要通过引用访问任意元素
* 对于常用的数据结构的举例
数据结构抽象数据类型数据表示
父链接树 UnionFind 整形数组
二分查找树 BST 含有两个链接的结点
字符串 String 数组、偏移量和长度
散列表(拉链法) SeparateChainingHashST 链表数组
散列表(线性探测法) LinearProbingHashST 两个对象数组
图的邻接链表 Graph Bag对象的数组
单词查找树 TrieST 含有链接数组的结点
三向单词查找树 TST 含有三个链接的结点
<>1. 更常用的数据结构了

<>栈，链表，包

<>1. 栈

* 栈是后进先出通常也是可说下压栈
* 在java中可以使用定义好的栈Stack，或者你自己可以实现适合自己的问题的栈
* 栈可以通过链表和数组都可以实现，这里是通过链表实现的 package com.basic.example; import javax.xml.soap.
Node; /** * Created by IntelliJ IDEA. * * @version : 1.0 * @auther : Firewine *
@mail ： [email protected] * @Program Name: StackExam .java * @Create :
2019-02-23-15:22 * @Description : 利用链表实现 */ public class StackExam<Item> { //栈顶
private Node first; //元素数量 private int N; private class Node{ //定义了节点的嵌套类 Item
item; Node next; } public boolean isEmpty(){return first == null;} public int
size(){return N;} public void push(Item item){ //添加元素 Node oldfirst = first;
first= new Node(); first.item = item; first.next = oldfirst; N++; } public Item
pop(){ //栈顶删除元素 Item item = first.item; first = first.next; N--; return item; }
}
<>2. 队列

* 通常队列是先进先出
* 在java中可以通过Queue来进行新建一个队列
* 下面是通过链表实现的队列 package com.basic.example; import javax.xml.soap.Node; /** *
Created by IntelliJ IDEA. * * @version : 1.0 * @auther : Firewine * @mail ：
[email protected] * @Program Name: QueueExam .java * @Create : 2019-02-23-15:29
* @Description : */ public class QueueExam <Item>{ //最早添加的结点的连接 private Node
first; //指向最近添加的结点的连接 private Node last; // 队列中的元素数量 private int N; private
class Node{ //定义了节点的嵌套类 Item item; Node next; } public boolean isEmpty(){return
first== null;} public int size(){ return N; } public void enqueue(Item item){
Node oldlast= last; last.item = item; last.next = null; if (isEmpty()){ first =
last; }else { oldlast.next = last; } } public Item dequeue(){ Item item = first.
item; first = first.next; if (isEmpty()){ last =null; } N--; return item; } }
<>3. 背包

* 在java中Bag可以创建
* 背包与前面两个不太一样，
* 首先他不能够从中删除元素，
* 背包的目的是：帮助用例收集并迭代遍历所有收集到的元素
* 重要的背包对于处理顺序是不重要的。，
* 下面是实现背包供学习使用 package com.basic.example; import java.util.Iterator; /** *
Created by IntelliJ IDEA. * * @version : 1.0 * @auther : Firewine * @mail ：
[email protected] * @Program Name: BagExam .java * @Create : 2019-02-23-15:37 *
@Description : */ public class BagExam<Item> implements Iterable<Item> {
//链表的首节点 private Node first; private class Node{ Item item; Node next; } public
void add(Item item){ Node oldfirst = first; first = new Node(); first.item =
item; first.next = oldfirst; } @Override public Iterator<Item> iterator() {
return new ListIterator1(); } private class ListIterator1 implements Iterator<
Item>{ private Node current = first; @Override public boolean hasNext() { return
current!= null; } @Override public void remove(){} @Override public Item next()
{ Item item = current.item; current = current.next; return item; } } }

热门工具换一换