1. 静态链表:用数组描述的链表叫静态链表,通常为方便数据插入,我们会把数组建的大一些。
2. 数组元素(node):由两个数据域组成(data,cursor)。数据域data用来存放数据元素,也就是通常我们要处理的数据;而cursor相当于单链表中的指针,存放该元素的后继在数组中的下标。
3. Java实现静态链表:
// 静态链表
class StaticLinkedList {
private int size;
private Node[] node = new Node[100];
// 用数组初始化静态链表
public StaticLinkedList(int arr[]) {
for (int i = 0; i < 100; i++) {
node[i] = new Node(); // 初始化100个结点对象(感觉性能不会很好)
}
for (int j = 0; j < arr.length; j++) {
node[j + 1].setData(arr[j]); // 第一个结点为头结点,头结点没有数据,只存索引
node[j].setCursor(j + 1);
}
size = arr.length;
}
// 在某位置插入值
public void insert(int index, int value) {
validateIndex(index);
int curIndex = node[index].getCursor(); // 获取待插入结点的前一个结点指针,它记住的是原待插入结点位置
node[size + 1].setData(value); // 第一个结点为头结点,所以新插入的结点为node[size + 1]
node[size + 1].setCursor(curIndex); // 让新插入的结点记住原位置结点角标
node[index].setCursor(size + 1); // 让原位置前一结点记住新插入结点角标
size++;
}
// 删除指定位置的值
public void delete(int index) {
validateIndex(index);
int curIndex = node[index].getCursor(); // 获取待删除节点的前一个结点指针,它记住的是待删除结点角标(注:第一个结点为头结点)
int nextIndex = node[curIndex].getCursor(); // 获取待删除节点指针,它记住的是待删除的下一个结点角标
node[index].setCursor(nextIndex); // 将待删除结点的前一个结点指针指向待删除结点的下一个结点角标
size--;
}
// 验证下标值是否合法,非法时抛出异常。
private void validateIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("无效的下标:" + index);
}
}
// 输出所有元素
public void display() {
int nextIndex = node[0].getCursor(); // node[0] 为头结点,存的是下一个结点角标
int i = 0;
while (i < size) {
System.out.printf("%d\t", node[nextIndex].getData());
nextIndex = node[nextIndex].getCursor();
i++;
}
}
}
// 结点(数组元素)
class Node {
int data; // 记录存入的数据
int cursor; // 记录下一个数据的下标
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getCursor() {
return cursor;
}
public void setCursor(int cursor) {
this.cursor = cursor;
}
}
// 测试类
public class Main {
public static void main(String[] args) {
int arr[] = { 1, 3, 4, 5, 6 };
StaticLinkedList list = new StaticLinkedList(arr);
System.out.print("初始化:\n");
list.display();
System.out.print("\n在角标为1的位置插入2后:\n");
list.insert(1, 2);
list.display();
System.out.print("\n删除角标为5的结点后:\n");
list.delete(5);
list.display();
}
}
4. 静态链表的优越点:
优点:在插入和删除操作时,不需要移动元素,从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。
缺点:没有解决连续存储分配带来表长难以确定的问题。
5. 总的来说,静态链表其实是为了给没有指针的高级语言设计的一种实现单链表的方法,一般很少用。
分享到:
相关推荐
数据结构教学课件:线性表链表.ppt
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
数据结构_线性表的链式存储 实验目的 1. 掌握线性表的链式存储结构。 2. 能熟练地利用链式存储结构实现线性表的基本操作。 3. 能熟练地掌握链式存储结构中算法的实现。 实验内容 1. 分别用头插法和尾插法建立带头...
数据结构实验报告2线性表的链式存储结构.pdf
数据结构:线性表(顺序存储).ppt
数据结构:线性表(链接存储).ppt
数据结构 C语言版 线性表的链式存储 数据结构 C语言版 线性表的链式存储
数据结构与算法:线性表的题库
线性表是一种最简单、最常用的数据结构。 如:到银行取钱时排队;学生花名册;书目顺序……所谓线性是指:在数据元素的非空有限集合中:1、存在唯一的一个被称做“第一个”的数据元素。 2、存在唯一的一个被称做...
数据结构: 线性表讲解实例。针对线性表的深入讲解。
包含数据结构中线性表、链表、队列、栈、串等几种结构的常见操作,以及顺序和链式存储过程
数据结构:线性表求一元多项式的值,用C++实现
实验一:线性表的存储结构定义及基本操作
数据结构线性表的链式存储结构,使用c语言完成。线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。
线性表的链式存储结构.doc 线性表的链式存储结构.doc 线性表的链式存储结构.doc
2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计算法构造三个以循环链表示的线性表,使每一个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的空间。...
学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-11-11 "指导教师" "成绩 " " "实验项目名称"线性表的链式存储结构 " "实"了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法" "验...
数据结构笔记之线性表(-):静态链表表示与实现
给定两个链表,实现他们的递增排序 LA[4]={3,5,8,11}; LB[8]={2,6,8,9,11,15,20};得到LC={2,3,5,6,8,9,11,15,20}
该文档饱含了数据结构课程中关于线性表的十二个基本操作的实现。对于不同的线性表的存储结构,利用C语言分别实现相应的算法