顺序存储
和链式存储
两种存储结构来表示。
顺序存储
的线性表称为顺序表,也称为静态线性表。
链式存储
的线性表称为链表,也称为动态线性表。
数组
来描述数据结构中的顺序存储结构。
public class Node{
public Object data; //数据域
public Node next; //指针域
}
public int length() {
Node p = head.next; // 获得第一个结点
int length = 0; // 定义一个变量记录长度
while(p != null) {
length ++; //计数
p = p.next; //p指向下一个结点
}
return length;
}
public Object get(int i) {
Node p = head.next; //获得头结点
int j = 0; //已经处理的结点数
while(p != null && j < i) { //链表没有下一个 && 处理有效部分
p = p.next;
j++;
}
if(i < 0 || p == null) {
throw new Exception("元素不存在");
}
return p.data; //返回数据
}
//查询给定值的索引号,如果没有返回-1
public int indexOf(Object x) {
Node p = head.next; // 获得头结点
int j = 0; // 不匹配元素的个数
while(p != null && !p.data.equals(x)) { // 循环依次找【不匹配】元素
p = p.next;
j++;
}
// 返回匹配索引,如果没有返回-1
if(p != null) {
return j;
} else {
return -1;
}
}
public void insert(int i , Object x) {
Node p = ...; // 获得i前驱,结点p
Node s = new Node(x); //创建新结点s
s.next = p.next; //必须先执行
p.next = s; //然后再执行
}
public void remove(int i) {
// 获得i的前驱结点p
p.next = p.next.next;
}
// i最小值0,表示获得头结点head
// 算法内部,使用-1表示头结点head,结点移动从头结点head开始。
public void previous(int i) {
Node p = head; //从头结点head开始移动
int j = -1; //使用-1表示头结点的索引
while(p != null && j < i-1 ) { // i-1前驱的下标
p = p.next;
j++;
}
if(p == null || i < 0) { // i-1 < j
throw new RuntimeException("i不合法");
}
//p就是需要获得前驱
}
// p结点是尾结点
p.next = head;
/* 变量
a尾: taila
a头:taila.next
b尾:tailb
b头:tailb.next
*/
// 先将b尾指向a的头,需要定义p记录b尾原来的值
// 再将a的尾指向b的头
Node p = tailb.next; //记录b尾的指向,也就是b头
tailb.next = taila.next; //b尾指向a头
taila.next = p.next; //a尾执行b头
/* 变量
结点a:p.prior
*/
p.prior.next = s; //结点a指向结点s
s.prior = p.prior; // 结点s指向结点a
p.prior = s; //结点p指向结点s
s.next = p; //结点s执行结点p
//注意:必须先处理结点a,否则无法获得结点a
// a.next = b
p.prior.next = p.next;
// b.prior = a
p.next.prior = p.prior