提到数据结构,不得不说数据类型,有人将他们比作分子和原子的关系,我们都知道大自然最小的构成单位是原子,数据类型描述的是原子的内部,如质子、中子的情况,而数据结构是分子,由不同的原子以各种各样的结构组成。
先说Java的数据类型,包括八种基本类型以及对象类型,
内置类型 | 八种基本类型 | 值类型 | 传输时传输值本身 | 内存随着值传输而变化 |
---|---|---|---|---|
扩展类型 | 对象类型 | 引用类型 | 传输时仅传递引用 | 对象在内存的位置不发生变化 |
数据结构,是以上这些不同数据类型的数据元素之间以一种或者多种特定关系的集合。
注意关键词:特定关系,集合。
特定关系我们可以理解为数据流动,而集合则是数据以什么样的形式存储。
数据结构之所以是程序语言的基础,是因为它描述了程序如何集合数据,数据如何流动(使用数据和处理数据),而数据流动和集合的方式有很多种,抽象出来最基础的当做砖,然后就像盖大楼一样,不断重用他们,实现更复杂更高级的数据集合和流动的方式,就是算法,所以数据结构和算法是血浓于水的关系。
下面来分析一下可以做砖的,背包,栈,队列是数据结构中数据流动的最佳领路者。
1 front++ 改为 front = (front + 1) % size
2 rear++ 改为 rear = (rear + 1) % size
总结一下,背包、栈、队列都是数据结构中描述数据流动方式的,但是各自访问内部元素的顺序和增删情况不同,他们都是属于基础算法。
再重申一下这三种数据结构在存取顺序上,各自的关注点,
背包是不关注顺序,只存不取;
栈是只关注最顶部元素位置,支持存取;
队列是要同时关注队首和队尾两个位置,支持存取。
下面再分析一下稍微复杂的链表结构。
链表是一种实现起来稍微复杂的数据结构,但这种复杂给链表带来了灵活轻巧,相对于以上三种倾向于数据流动的数据结构,链表更关注自身存储数据的结构,但是他更强大。链表的实现与C语言的指针概念很像,链表不依赖具体的内存顺序,也不一定是连续的位置,而是依赖指针的顺序来连接整个链表。所以链表的单位结构是一个value加一个link。value是该单位存储的内容,link是下一个链表单位对象的引用。链表有三种基本操作,
1 node.link = head.link;
2 head.link = node;
1 Node n = head;
2 while(n.link != null){
3 n = n.link;
4 }
5 n.link = newInsert;
6 newInsert.link = null;
1 head.link = node.link;
2 node.link = null
由此我们可以看出,实现了这三种基本操作,链表可以自己去实现背包,栈和队列的算法。