网站建设洛阳,惠州网站建设排名,word怎么做网站导航栏,wordpress清理无用缩略图线性表是多个具有相同特征的数据的有限序列。
前驱元素#xff1a;A在B前面#xff0c;称A为B的前驱元素。
后继元素#xff1a;B在A后面#xff0c;称B为A的后继元素。
线性表特征#xff1a;
1.一个元素没有前驱元素#xff0c;就是头结点#xff1b;
2.最后一个…线性表是多个具有相同特征的数据的有限序列。
前驱元素A在B前面称A为B的前驱元素。
后继元素B在A后面称B为A的后继元素。
线性表特征
1.一个元素没有前驱元素就是头结点
2.最后一个元素没有后继元素就是尾结点
3.除了头结点和尾结点都具有前驱和后继
线性表分为顺序表和链表。
1.顺序表
顺序表是以数组形式保存在内存一组地址连续的存储单元上数组之间的逻辑关系代表了物理存储的相邻关系。 顺序表容量可变
1.扩容数组太小创建两倍容量容纳新元素。
2.缩小数组元素小于1/4创建一个原数组容量1/2的新数组存储元素。
顺序表遍历
遍历一般使用foreach循环如需支持需要
1.实现Iterable重写iterator方法
2.内部再实现一个SIterator实现Iterator接口重写hasnext和next方法。
顺序表底层使用数组实现数组长度固定因此设计到了扩容操作当扩容时耗时增加元素越多越明显。
2.链表
顺序表查询很快但是更新效率低每一个更新都伴随着大量数据的移动。
链表是在物理上非连续、非顺序的存储结构物理结构不能直观的表示数据元素的逻辑顺序数据的逻辑顺序由链表中的指针连接实现的。
链表由一系列结点组成结点可以在运行时动态生成。
结点类
public class NodeT {
//存储元素
public T item;
//指向下一个结点
public Node next;
public Node(T item, Node next) {
this.item item;
this.next next;
}
}
3.单向链表
单向链表由多个结点组成每个结点由一个数据和指针组成头结点不存粗数据指针指向第一个真正存储数据的结点。 4. 双向链表
双向链表由多个结点组成每个结点由数据和两个指针组成一个指针指向前驱结点一个指针指向后继结点。头结点数据和前驱指针为null后继结点指向第一个真正存储数据的结点。
private class Node{
public Node(T item, Node pre, Node next) {
this.item item;
this.pre pre;
this.next next;
}
//存储数据
public T item;
//指向上一个结点
public Node pre;
//指向下一个结点
public Node next;
}
链表在插入和删除的时间复杂度上和顺序表一样但也有优势在物理地址上的不连续代表不需要扩容也没有元素之间的交换。
实际程序查询多使用顺序表。增删多使用链表。
5.栈
一种先进后出FILO的数据结构。一种只能在一端进行插入和删除操作的特殊线性表。
数据进入栈是压栈数据出栈是弹栈。 6.逆波兰表达式
中缀表达式13*2,2-(13)
特点二元运算符总是在两个操作数中间。
逆波兰表达式后缀表达式abc-*d 对应着a*(b-c)d
运算符总书放在操作数后面。
7.队列
队列是基于先进先出FIFO的数据结构是一段插入另一端删除的特殊线性表。先进入的数据先读取。
