java 基础数据结构

数据结构, 需要考虑两个方面:

1. 每个元素具体的存储方法 (java中是一个对象)

2. 元素之间的关系如何实现存储 (java中也是一个对象)

另外在java中, 已经可以把跟数据结构有关的一些方法写到一个类里了.

线性表

顺序表

c语言: 借助数组实现

#define INIT_SIZE 100;

typedef struct {

    int elem[INIT_SIZE];    // 用来存储数组元素

    int length;                    // 当前顺序表的长度

} SqList;

// 元素之间的关系隐含在数组这种数据结构中

java语言: 也可以借用数组实现

可以直接借助 ArrayList实现.

链表

c语言:

// 结点

// 结点之间没有明确的关系, 靠一个向后的指针联系

typedef struct LNode {

    int elem;    // 元素

    struct LNode *next;    // 维系关系

} LNode, &LinkList;

java语言:

package DataSturcture;

public class LinkList<T> {

    // node object

    private class Node {

        public Node() {}

        public Node(T data, Node next){

            this.data = data;

            this.next = next;

        }

    /* private instance variable */

        private T data;        // element;

        private Node next;    // pointer, point next Node

    }

    public LinkList() {

        header = null;

        tail = null;

    }

    public LinkList(T element) {

        header = new Node(element, null);

        tail = header;

        size++;

    }

    public int length() {

        return size;

    }

    public T get(int index) {

        return getNodeByIndex(index).data;

    }

    private Node getNodeByIndex(int index) {

        if (index < 0 || index > size -1) {

            throw new IndexOutOfBoundsException("线性表索引越界");

        }

        Node current = header;

        for (int i=0; i<size && current != null; current=current.next) {

            if (i == index) {

                return current;

            }

        }

        return null;

    }

    public int locate(T element) {

        Node current = header;

        for (int i=0; i<size && current != null; i++, current=current.next) {

            if (current.data.equals(element)) {

                return i;

            }

        }

        return -1;

    }

    public void insert(T element, int index) {

        if (index < 0 || index > size -1) {

            throw new IndexOutOfBoundsException("线性表索引越界");

        }

        if (header == null) {

            add(element);

        } else {

            if (index == 0) {

                addAtHeader(element);

            } else {

                Node prev = getNodeByIndex(index - 1);

                prev.next = new Node(element, prev.next);

                size++;

            }

        }

    }

    public void add(T element) {

        if (header == null) {

            header = new Node(element, null);

        } else {

            Node newNode = new Node(element, null);

            tail.next = newNode;

            tail = newNode;

        }

        size++;

    }

    public void addAtHeader(T element) {

        header = new Node(element, header);

        if (tail == null) {

            tail = header;

        }

        size++;

    }

    public T delete(int index) {

        if (index < 0 || index > size -1) {

            throw new IndexOutOfBoundsException("线性表索引越界");

        }

        Node del = null;

        if (index == 0) {

            del = header;

            header = header.next;

        } else {

            Node prev = getNodeByIndex(index - 1);

            del = prev.next;

            prev.next = del.next;

            del.next = null;

        }

        size--;

        return del.data;

    }

    public T remove() {

        return delete(size - 1);

    }

    public boolean isEmpty() {

        return size == 0;

    }

    public void clear() {

        header = null;

        tail = null;

        size = 0;

    }

    public String toString() {

        if (isEmpty()) {

            return "[]";

        } else {

            StringBuilder sb = new StringBuilder("[");

            for (Node current=header; current != null; current=current.next) {

                sb.append(current.data.toString() + ", ");

            }

            int len = sb.length();

            return sb.delete(len-2, len).append("]").toString();

        }

    }

/* private instance variable */

    private Node header;    // header information

    private Node tail;        // tail information

    private int size;        // count node

}

从以上的代码中, 总结几点:

1. 功能能够独立出来的函数要独立出来, 大家一起使用, 就想cs106说得一样, 画火车时, 不要着急一节一节的话, 而是先抽象出一个车厢类, 从车头到车尾的所有车厢, 都利用这个车厢类.

2. 自顶向下得设计原则贯穿始终

双向链表与上边单链表很像, 循环链表也可以利用 tail 和 header 的指向直接进行.

另外, 可以通过线性表List, Java 的 List 接口就代表了线性表, 线性表的两种实现是 ArrayList(数组实现) 和 LinkedList, 其中 LinkedList 是一个双向链表.

对于java 而言, 如果你想使用线性表, 那么就:

顺序表: 使用 ArrayList 直接实现.

双向链表: 使用 LinkeedList 直接实现.

栈

栈也是一种常用的数据结构, 所以java也集成了栈,

顺序栈: java.util.Stack, 普通的顺序栈, 底层是用数组实现, 这个stack是线程安全的, 在多线程环境下也可以放心使用.

链栈: java.util.LinkedList, 它不是线程安全的.

队列

Java 集合框架中提供了一个 Queue接口. 都是线程安全的.

ArrayBlockingQueue: 顺序队列

LinkedBlockingQueue: 链队列

双向队列

ArrayDeque: 代表顺序存储结构的双向队列

LinkedBlockingDeque: 代表链式存储结构的双向队列.

树和二叉树

树的父亲结点表示法

c语言实现:

/* node structure */

typedef struct TreeNode {

    int elem;    // 存储元素信息

    int parent;    // 存储 parrent 结点的指针

} TPN;

/* relation ship structure */

typedef struct TreeParent {

    TreeNode node[MAX_TREE_SIZE];

    int r;    // 根节点指针

    int n;    // 当前树的结点总数

}

java语言实现:

其实原理都使一样的, java通过内部类来存储单个结点, 外部类体现结点间的关系, 即数据结构.

巴特西

java 基础数据结构

数据结构, 需要考虑两个方面:

线性表

顺序表

链表

栈

队列

树和二叉树

树的父亲结点表示法

最新文章

热门文章