中国容桂品牌网站建设,wordpress分类页置顶信息,河南省建设监理协会网站,做网站用别人的图片1 定义 线性表是零个或多个数据元素的有限序列。
2 抽象数据类型
ADT 线性表(List)Data#xff1a;线性表的数据对象集合为{al,a2,a3,....an}#xff0c;每个元素的类型均为DataType。其中#xff0c;除第一个元素a1外#xff0c;每一个元素有且只有一个直接前驱元素线性表的数据对象集合为{al,a2,a3,....an}每个元素的类型均为DataType。其中除第一个元素a1外每一个元素有且只有一个直接前驱元素除了最后一个元素an外每一个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系。Operationinit(int maxSize)初始化操作建立一个空的线性表isEmpty()若线性表为空返回true否则返回falseclear()清空线性表getElement(int position)获取线性表中第position个元素值locateElement(DataType e)在线性表中查找与给定值e相等的元素如果查找成功返回该元素在表中序号否则返回0表示失败insert(DataType e, int position)在线性表的第position个位置插入元素edelete(int position)删除纯属表中第position个位置的元素length()返回线性表的元素个数
endADT3 顺序存储结构
3.1 概述 线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构的抽象数据类型在标准类型的基础上新增了length和maxSize两个属性
ADT 线性表(List)Data线性表的数据对象集合为{al,a2,a3,....an}每个元素的类型均为DataType。其中除第一个元素a1外每一个元素有且只有一个直接前驱元素除了最后一个元素an外每一个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系。length线性表中实际元素个数应小于等于maxSize。maxSize线性表可以存储的元素个数。Operationinit(int maxSize)初始化操作建立一个空的线性表isEmpty()若线性表为空返回true否则返回falseclear()清空线性表getElement(int position)获取线性表中第position个元素值locateElement(DataType e)在线性表中查找与给定值e相等的元素如果查找成功返回该元素在表中序号否则返回0表示失败insert(DataType e, int position)在线性表的第position个位置插入元素edelete(int position)删除纯属表中第position个位置的元素length()返回线性表的元素个数
endADT3.2 初始化 定义一个空的线性表初始化maxSize和data数组
/*** 初始化线性表** param maxSize 线性表最大长度* author Korbin* date 2023-01-04 18:29:17**/
public void init(int maxSize) {this.maxSize maxSize;data new Object[maxSize];
}3.3 判断是否为空 判断length是否为0即可为避免其他异常使用小于等于如下
/*** 判断线性表是否为空** return 线性表为空返回true非空返回false* author Korbin* date 2023-01-11 15:54:53**/
public boolean isEmpty() {return length 0;
}3.4 清空线性表 把length和data重新初始化即可C语言则需要回收内存
/*** 清空线性表** author Korbin* date 2023-01-11 15:58:15**/
public void clear() {this.length 0;this.data new Object[this.maxSize];
}3.5 获取指定位置元素 线性表长度为0或要获取的位置小于1或大于线性表长度时抛出异常实际位置是索引加1
/*** 获取线性表中的第position个元素** param position 位置* return 获取到的元素* throws RuntimeException 线性表长度为0或要获取的位置小于1或大于线性表长度时抛出异常* author Korbin* date 2023-01-04 18:32:10**/
SuppressWarnings(unchecked)
public T getElement(int position) {if (position 1 || position length) {throw new RuntimeException(error position);} else {return (T) (data[position - 1]);}
}时间复杂度为O(1)。
3.6 在线性表中查找与给定值e相等的元素 使用equals判断是否相等因此DataType需要实现equals方法
/*** 查找element在线性表中的位置** param element 待查找的元素* return 元素在线性表中的位置* author Korbin* date 2023-01-11 15:59:23**/
SuppressWarnings(unchecked)
public int locateElement(T element) {int position -1;for (int i 0; i length; i) {T e (T) (data[i]);if (e.equals(element)) {position i;break;}}return position 1;
}时间复杂度为O(n)。
3.7 插入操作 线性表已满或位置异常时抛出异常插入时其后的所有元素需要往后移实际元素个数要加1
/*** 在线性表中的指定位置position插入一个元素** param position 指定位置* param element 要插入的元素* throws RuntimeException 线性表已满或位置异常时抛出异常* author Korbin* date 2023-01-04 19:22:34**/
public void insert(int position, T element) {if (length maxSize) {throw new RuntimeException(already full);}if (position 1 || position length 1) {throw new RuntimeException(error position);}if (position length) {for (int k length - 1; k position - 1; k--) {data[k 1] data[k];}}data[position - 1] element;length;
}时间复杂度为O(n)。
3.8 删除操作 线性表为空或位置不对时抛出异常实际元素个数要减1
/*** 删除线性表中第position位的元素** param position 位置* throws RuntimeException 线性表为空或位置不对时抛出异常* author Korbin* date 2023-01-05 09:46:58**/
public void delete(int position) {if (length 0) {throw new RuntimeException(empty list);}if (position 1 || position length) {throw new RuntimeException(error position);}if (position length) {for (int k position; k length; k) {data[k - 1] data[k];}}// 如果要删除的位置就是线性表的长度所在的位置的话那直接把长度减1就行了length--;
}时间复杂度为O(n)。
3.9 返回实际元素个数
/*** 获取线性表真实长度** return 线性表长度* author Korbin* date 2023-01-05 10:15:41**/
public int length() {return length;
}3.10 完整代码
/*** 顺序存储线性表** author Korbin* date 2023-01-04 18:19:38**/
public class SequentialListT {/*** 线性表数据**/private Object[] data;/*** 线性表当前长度**/private int length;/*** 线性表最大长度*/private int maxSize 20;/*** 清空线性表** author Korbin* date 2023-01-11 15:58:15**/public void clear() {this.length 0;this.data new Object[this.maxSize];}/*** 删除线性表中第position位的元素** param position 位置* throws RuntimeException 线性表为空或位置不对时抛出异常* author Korbin* date 2023-01-05 09:46:58**/public void delete(int position) {if (length 0) {throw new RuntimeException(empty list);}if (position 1 || position length) {throw new RuntimeException(error position);}if (position length) {for (int k position; k length; k) {data[k - 1] data[k];}}// 如果要删除的位置就是线性表的长度所在的位置的话那直接把长度减1就行了length--;}/*** 获取线性表中的第position个元素** param position 位置* return 获取到的元素* throws RuntimeException 线性表长度为0或要获取的位置小于1或大于线性表长度时抛出异常* author Korbin* date 2023-01-04 18:32:10**/SuppressWarnings(unchecked)public T getElement(int position) {if (position 1 || position length) {throw new RuntimeException(error position);} else {return (T) (data[position - 1]);}}/*** 初始化线性表** param maxSize 线性表最大长度* author Korbin* date 2023-01-04 18:29:17**/public void init(int maxSize) {this.maxSize maxSize;data new Object[maxSize];}/*** 在线性表中的指定位置position插入一个元素** param position 指定位置* param element 要插入的元素* throws RuntimeException 线性表已满或位置异常时抛出异常* author Korbin* date 2023-01-04 19:22:34**/public void insert(int position, T element) {if (length maxSize) {throw new RuntimeException(already full);}if (position 1 || position length 1) {throw new RuntimeException(error position);}if (position length) {for (int k length - 1; k position - 1; k--) {data[k 1] data[k];}}data[position - 1] element;length;}/*** 判断线性表是否为空** return 线性表为空返回true非空返回false* author Korbin* date 2023-01-11 15:54:53**/public boolean isEmpty() {return length 0;}/*** 获取线性表真实长度** return 线性表长度* author Korbin* date 2023-01-05 10:15:41**/public int length() {return length;}/*** 查找element在线性表中的位置** param element 待查找的元素* return 元素在线性表中的位置* author Korbin* date 2023-01-11 15:59:23**/SuppressWarnings(unchecked)public int locateElement(T element) {int position -1;for (int i 0; i length; i) {T e (T) (data[i]);if (e.equals(element)) {position i;break;}}return position 1;}/*** 打印线性表** throws RuntimeException 线性表为空时抛出异常* author Korbin* date 2023-01-05 09:55:55**/Overridepublic String toString() {if (length 0) {throw new RuntimeException(empty list);}StringBuilder result new StringBuilder([);for (int i 0; i length; i) {result.append(i 1).append(:).append(data[i]).append(,);}result.append(]);return result.toString();}}3.11 优缺点 4 链式存储结构
4.1 概述 用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的只是通过数据元素中的后继元素地址来指向后继元素的存储地址即称为链式存储。 在链式存储结构中每个数据元素除了存储其本身的信息外还需存储一个指示其直接后继的信息即直接后继的存储位置存储数据元素信息的域称为数据域存储直接后继位置的域称为指针域指针域中存储的信息称做指针或链。数据域和指针域组成数据元素的存储映像称为结点。 因为每个结点中只包含一个指针域因此这种链表也被称为单链表。 单链表的第一个结点称为头结点头结点不存储数据只存储链表中第一个实际元素的存储位置称为头指针。 单链表的最后一个结点没有后继元素因此其指针域的值是Null。 单链表的抽象存储结构与线性表的顺序存储结构的抽象存储结构略有区别
ADT 线性表(List)Data线性表的数据对象集合为{al,a2,a3,....an}每个元素的类型均为DataType。其中除第一个元素a1外每一个元素有且只有一个直接前驱元素除了最后一个元素an外每一个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系。单链表中只存储头结点对象即可。length线性表中实际元素个数。Operationinit初始化操作建立一个空的线性表isEmpty若线性表为空返回true否则返回falseclear清空线性表getElement(int position)获取线性表中第position个元素值locateElement(DataType e)在线性表中查找与给定值e相等的元素如果查找成功返回该元素在表中序号否则返回0表示失败insert(DataType e, int position)在线性表的第position个位置插入元素edelete(int position)删除纯属表中第position个位置的元素length()返回线性表的元素个数
endADT4.2 结点结构
DataType需要进行特殊定义必须包含后继元素指针如下
import lombok.Data;import java.util.UUID;/*** 单链表** author Korbin* date 2023-01-05 10:58:05**/
Data
public class LinkListNodeT {/*** 数据**/private T data;/*** 设置一个ID已进行equals判断**/private String id UUID.randomUUID().toString();/*** 后继结点**/private LinkListNodeT next;/*** 构造子** author Korbin* date 2023-01-05 12:38:08**/public LinkListNode() {}OverrideSuppressWarnings(unchecked)public boolean equals(Object obj) {if (obj instanceof LinkListNode) {try {LinkListNodeT node (LinkListNodeT) obj;return data.equals(node.getData()) id.equals(node.getId());} catch (ClassCastException e) {return false;}} else {return false;}}Overridepublic String toString() {return {id id , data data.toString() };}}构造子、equals和toString方法可以按需添加一个id的主要目的是用于equals如有其他判断相等的方式也可以不加id。
4.3 初始化和清空 初始化和清除在Java中因为垃圾回收机制因此实现方式相同。 单链表定义的Data不需要是一个数组只需要放置headNode即头结点即可因此初始化和清空时只需要将length置为0将headNode的值和后继结点置为空即可。
/*** 清空* p* 直接调用初始化方法即可** author Korbin* date 2023-01-11 15:58:15**/
public void clear() {init();
}
/*** 初始化** author Korbin* date 2023-01-04 18:29:17**/
public void init() {headNode new LinkListNode();headNode.setData(null);headNode.setNext(null);length 0;
}4.4 获取指定位置的元素 从头结点开始迭代后继结点
/*** 获取单链表中第position位的元素的值** param position 要获取的结点所在的位置* return 指定位置结点的值* throws RuntimeException 未获取到结点时抛出* author Korbin* date 2023-01-05 11:06:01**/
public LinkListNodeT getElement(int position) {if (position 0) {return headNode;}LinkListNodeT result headNode.getNext();int j 1;while (null ! result j position) {result result.getNext();j;}if (null result || j position) {throw new RuntimeException(node not exists);}return result;
}时间复杂度为O(n)。
4.5 插入操作 先获取待插入位置的前驱结点然后让前驱结点指向新结点新结点指向原结点即可
/*** 在单链表的指定位置插入一个结点** param position 要插入的位置* param value 要插入的结点的值* throws RuntimeException 要插入的位置不存在结点时抛出* author Korbin* date 2023-01-05 11:12:05**/
public void insert(int position, T value) {LinkListNodeT positionNode getElement(position - 1);LinkListNodeT newNode new LinkListNode();newNode.setData(value);newNode.setNext(positionNode.getNext());positionNode.setNext(newNode);length;}时间复杂度为O(n)。
4.6 删除操作 先获取待删除结点的前驱结点然后让前驱结点指向其后继的后继即可
/*** 删除单链表中指定位置的元素** param position 要删除结点所在位置* throws RuntimeException 要删除的位置不存在结点时抛出异常* author Korbin* date 2023-01-05 11:15:21**/
public void delete(int position) {LinkListNodeT lastNode getElement(position - 1);lastNode.setNext(lastNode.getNext().getNext());length--;
}删除操作的时间复杂度为O(n)。
4.7 查找与给定值e相等的元素 从头结点开始迭代后继结点直到没有后续结点或者找到的结点等于给定的元素
/*** 查找element在单链表中的位置** param element 待查找的元素* return 元素在单链表中的位置* author Korbin* date 2023-01-11 15:59:23**/
public int locateElement(LinkListNodeT element) {LinkListNodeT result headNode.getNext();int j 1;while (null ! result) {if (result.equals(element)) {break;}result result.getNext();j;}if (null result) {throw new RuntimeException(node not exists);}return j;
}4.8 完整代码
/*** 单链表** author Korbin* date 2023-01-05 16:19:13**/
public class LinkListT {/*** 头结点**/private LinkListNodeT headNode;/*** 结点数量**/private int length;/*** 清空* p* 直接调用初始化方法即可** author Korbin* date 2023-01-11 15:58:15**/public void clear() {init();}/*** 删除单链表中指定位置的元素** param position 要删除结点所在位置* throws RuntimeException 要删除的位置不存在结点时抛出异常* author Korbin* date 2023-01-05 11:15:21**/public void delete(int position) {LinkListNodeT lastNode getElement(position - 1);lastNode.setNext(lastNode.getNext().getNext());length--;}/*** 获取单链表中第position位的元素的值** param position 要获取的结点所在的位置* return 指定位置结点的值* throws RuntimeException 未获取到结点时抛出* author Korbin* date 2023-01-05 11:06:01**/public LinkListNodeT getElement(int position) {if (position 0) {return headNode;}LinkListNodeT result headNode.getNext();int j 1;while (null ! result j position) {result result.getNext();j;}if (null result || j position) {throw new RuntimeException(node not exists);}return result;}/*** 初始化** author Korbin* date 2023-01-04 18:29:17**/public void init() {headNode new LinkListNode();headNode.setData(null);headNode.setNext(null);length 0;}/*** 在单链表的指定位置插入一个结点** param position 要插入的位置* param value 要插入的结点的值* throws RuntimeException 要插入的位置不存在结点时抛出* author Korbin* date 2023-01-05 11:12:05**/public void insert(int position, T value) {LinkListNodeT positionNode getElement(position - 1);LinkListNodeT newNode new LinkListNode();newNode.setData(value);newNode.setNext(positionNode.getNext());positionNode.setNext(newNode);length;}/*** 判断是否为空** return 为空返回true非空返回false* author Korbin* date 2023-01-11 15:54:53**/public boolean isEmpty() {return null headNode.getNext() length 0;}/*** 获取真实长度** return 长度* author Korbin* date 2023-01-05 10:15:41**/public int length() {return length;}/*** 查找element在单链表中的位置** param element 待查找的元素* return 元素在单链表中的位置* author Korbin* date 2023-01-11 15:59:23**/public int locateElement(LinkListNodeT element) {LinkListNodeT result headNode.getNext();int j 1;while (null ! result) {if (result.equals(element)) {break;}result result.getNext();j;}if (null result) {throw new RuntimeException(node not exists);}return j;}Overridepublic String toString() {LinkListNodeT next headNode.getNext();StringBuilder builder new StringBuilder([);while (null ! next) {builder.append(next).append(,);next next.getNext();}builder.append(length).append(length);builder.append(]);return builder.toString();}}4.9 单链表结构与顺序存储结构优缺点 因此通常情况下 (1) 需要频繁查找很少进行插入和删除时建议使用顺序存储结构 (2) 需要频繁插入和删除时建议使用单链表结构实际上如果需要批量插入或删除时单链表的优势才能体现出来即如果需要插入/删除指定位置的10个元素时单链表只需要迭代一次找到待插入/删除位置的元素然后就可以直接对10个元素进行操作了而顺序存储结构则需要将待插入/删除元素之后的元素移动 (3) 元素个数变化较大或根本不知道多大时建议使用单链表否则使用顺序存储结构
5 静态链表
5.1 概述 在一些没有指针也没有引用的语言中用数组来代替指针来描述的单链表称为静态链表。 在静态链表中每一个结点由两个数据域组成data用于存储数据cursor用于存储后继结点的指针数组的索引使用cursor代替单链表中的后继结点。 由于静态链表中存储的数据是一个数组因此静态链表也会定义length和maxSize分别用于表示结点的实际数量和最多可存放的结点数量。 数组的所有元素并不都存储着数据结点未存储数据的元素被称为备用链表而数组的第一个元素即下标为0的元素存储的结点不包含数据只包含cursorcursor存放着备用链表的第一个结点的下标即下一个可存储数据的数组下标。 数组的最后一个元素存储的结点也不存储数据只包含cursorcursor存放着第一个结点的下标即头结点的下标因此数组的最后一个元素起着头指针的作用。 因此静态链表初始化状态会如下所示 下标当然是从0、1、2一直到999而cursor比较特殊 (1) 假设数组为array那么array[0]的cursor值指向下一个可存储结点的元素的下标因此应为1 (2) array[1]还没有存储结点那我们让它的cursor指向下一个结点即array[2]因此array[1]的cursor为2依此类推 (3) 最后一个节点array[999]它应该指向第一个结点的下标此时还没有任何一个结点因此array[999]的cursor应为0 此时假设静态链表中依次存储了甲、乙、丁、戊、己、庚则其结构应如下所示 (1) array[0]不存储数据存储的是下一个可存储数据的下标如图下一个可存储的下标是7因此array[0]的cursor为7 (2) array[1]存储第1个结点甲指向第二个结点乙乙是array[2]因此array[1]的cursor为array[2]的下标即2依此类推 (3) array[6]此时静态链表中的最后一个结点存储的数据是庚因其没有后继结点因此令其cursor为0 (4) array[999]作为数组的最后一个元素其存储的是静态链表中第一个结点的下标我们知道静态链表中的第一个结点是甲存储在array[1]下标是1因此array[999]的cursor是1
5.2 结点定义 与单链表相同添加一个属性id用于判断结点是否相等
import lombok.Data;import java.util.UUID;/*** 静态链表节点** author Korbin* date 2023-01-05 16:25:49**/
Data
public class StaticLinkNodeT {/*** 游标指向下一个节点为0时表示无指向**/private int cursor;/*** 节点值**/private T data;/*** 设置一个ID已进行equals判断**/private String id UUID.randomUUID().toString();OverrideSuppressWarnings(unchecked)public boolean equals(Object obj) {if (obj instanceof StaticLinkNode) {try {StaticLinkNodeT node (StaticLinkNodeT) obj;return data.equals(node.getData()) id.equals(node.getId());} catch (ClassCastException e) {return false;}} else {return false;}}}5.3 初始化和清除 上文有提到初始化过程即初始化maxSize、data并设置数组中每个元素的cursor默认值而清除静态链表和初始化的逻辑是一致的
/*** 判断是否为空** return 为空返回true非空返回false* author Korbin* date 2023-01-11 15:54:53**/
public boolean isEmpty() {return length 0;
}
/*** 初始化静态链表** param maxSize 链表的最大长度* throws RuntimeException 最大长度为0时抛出* author Korbin* date 2023-01-05 16:30:25**/
SuppressWarnings(unchecked)
public void init(int maxSize) {if (maxSize 1) {throw new RuntimeException(error maxSize);}this.maxSize maxSize;data new StaticLinkNode[maxSize];for (int i 0; i maxSize - 1; i) {StaticLinkNodeT node new StaticLinkNode();node.setCursor(i 1);data[i] node;}StaticLinkNodeT node new StaticLinkNode();node.setCursor(0);data[maxSize - 1] node;length 0;
}5.4 插入 插入过程 (1) 先从array[0]中获取到下一个可存放数据的数组元素下标设为nextIndex (2) 然后找到待插入位置的上一个结点先从array[length-1]中获取第1个节点下标然后批第2个节点下标然后找第3个节点下标直到找到待插入位置position - 1个节点的下标设找到的值为lastIndex (3) 我们知道array[0]存储中下一个可存放数据的数组元素下标也知道array[nextIndex]存储着下下个可存放数据的数组元素下标y因此如果array[nextIndex]被使用了那么array[0]应存放的cursor值则为y因此代码中需要对array[0]的cursor值进行修改 (4) 然后设置array[nextIndex]的数据域为待插入的结点cursor则为待插入位置上一个结点的cursor再把待插入位置上一个结点的cursor设置为nextIndex即插入的结点下标那么插入操作就完成了 (5) 最后注意结点数量需要加1
/*** 下一个可插入的索引位** return 下一个可插入的索引位* author Korbin* date 2023-01-05 20:20:14**/
public int getNextIndex() {return data[0].getCursor();
}
/*** 在指定位置插入** param position 位置* param value 要插入的元素* throws RuntimeException 插入到数组的0位或者跳跃进行插入或者数组长度满后插入时抛出异常* author Korbin* date 2023-01-05 19:32:06**/
public void insert(int position, T value) {// 数组的第0个元素存储着数组下一个可存放节点的位置获取到这个位置int nextIndex getNextIndex();if (position 1 || position length 1) {// 插入位置不能小于1,也不能大于链表的实际长度1// 可以为length1的原因是因为允许在最后面插入throw new RuntimeException(error position);}if (length maxSize - 2) {// 如果实际长度等于最大长度时表示链表已满不能再插入throw new RuntimeException(fulled);}// 默认数组的最后一个元素存储的是第一个节点的下标int lastIndex maxSize - 1;// 获取到待插入的节点的上一个节点的游标// 首先通过最后一个节点的游标可以找到第一个节点// 通过第一个节点的游标可以找到第二个节点// 依此类推for (int i 1; i position - 1; i) {lastIndex data[lastIndex].getCursor();}// 设置第0个元素的游标值为待插入节点的游标值初始化时有设置data[0].setCursor(data[nextIndex].getCursor());// 设置这个节点的节点值为待插入值data[nextIndex].setData(value);// 设置这个节点的游标为上一个节点的游标值data[nextIndex].setCursor(data[lastIndex].getCursor());// 设置上一个节点的游标值为这个节点的位置data[lastIndex].setCursor(nextIndex);length;
}时间复杂度为O(position-1)即O(n)。
5.5 删除 (1) 先找到待删除结点的上一个结点寻找方法与插入时一致此时找到了lastNode (2) 然后找到待删除结点即lastNode.getCursor()对应的结点此时找到了toDeleteNode (3) 令lastNode指向toDeleteNode的下一个结点删除操作就完成了 (4) toDeleteNode被删除了那么它所在的数组元素就可以存放新的结点了这时令toDeleteNode的cursor指向array[0]的cursor令array[0]的cursor指向toDeleteNode的下标即让toDeleteNode所在的位置成为下一个可存储数据的下标即备用链表的第一位同时把备用链表的其他可存储结点的下标依次往后挪一位 (5) 最后注意结点数量应减1
/*** 删除指定位置的节点** param position 待删除节点位置* throws RuntimeException 删除第0个节点或者要删除的位置超出节点实际数量时抛出异常* author Korbin* date 2023-01-05 19:34:18**/
public void delete(int position) {// 不得删除第0个元素// 不得删除超出实际节点数量的元素if (position 0 || position length()) {throw new RuntimeException(error position);}// 找到要删除的节点的上一个节点int lastIndex data[maxSize - 1].getCursor();int lastIndex maxSize - 1;// 获取到待插入的节点的上一个节点的游标// 首先通过最后一个节点的游标可以找到第一个节点// 通过第一个节点的游标可以找到第二个节点// 依此类推for (int i 1; i position - 1; i) {lastIndex data[lastIndex].getCursor();}StaticLinkNodeT lastNode data[lastIndex];// 待删除的节点int toDeleteIndex lastNode.getCursor();StaticLinkNodeT toDeleteNode data[toDeleteIndex];// 上一个节点的游标指向下一个节点lastNode.setCursor(toDeleteNode.getCursor());data[lastIndex] lastNode;// 当前节点的值设置为空toDeleteNode.setData(null);// 当前节点的游标设置为0toDeleteNode.setCursor(0);data[toDeleteIndex] toDeleteNode;// 把已删除的节点的索引位置作为下一次插入时的位置data[toDeleteIndex].setCursor(data[0].getCursor());data[0].setCursor(toDeleteIndex);length--;}同样时间复杂度为O(n)。
5.6 获取指定位置的元素 从第一个节点一直往后找即可
/*** 获取指定位置的元素** param position 指定的位置* return 指定位置的元素* throws RuntimeException 当试图获取第0个或超出实际节点数量的元素时抛出异常* author Korbin* date 2023-01-05 19:59:26**/
public StaticLinkNodeT getElement(int position) {// 不得获取第0个元素// 不得获取超出实际节点数量的元素if (position 0 || position length()) {throw new RuntimeException(error position);}// 依次往下迭代即可int positionIndex data[maxSize - 1].getCursor();for (int i 1; i position; i) {positionIndex data[positionIndex].getCursor();}return data[positionIndex];
}5.7 获取指定结点在静态链表中的位置 同样从第一个结点一直往后找
/*** 查找element在单链表中的位置** param element 待查找的元素* return 元素在单链表中的位置* author Korbin* date 2023-01-11 15:59:23**/
public int locateElement(StaticLinkNodeT element) {// 依次往下迭代即可int index data[maxSize - 1].getCursor();for (int i 0; i length; i) {StaticLinkNodeT node data[index];if (node.equals(element)) {break;}index data[index].getCursor();}return index;
}5.8 完整代码
/*** 静态链表** author Korbin* date 2023-01-05 16:27:11**/
public class StaticLinkListT {/*** 节点数据*/private StaticLinkNodeT[] data;/*** 实际节点数量**/private int length;/*** 链表的最大长度*/private int maxSize;/*** 清空** author Korbin* date 2023-01-11 15:58:15**/public void clear() {init(maxSize);}/*** 删除指定位置的节点** param position 待删除节点位置* throws RuntimeException 删除第0个节点或者要删除的位置超出节点实际数量时抛出异常* author Korbin* date 2023-01-05 19:34:18**/public void delete(int position) {// 不得删除第0个元素// 不得删除超出实际节点数量的元素if (position 0 || position length()) {throw new RuntimeException(error position);}// 找到要删除的节点的上一个节点int lastIndex data[maxSize - 1].getCursor();int lastIndex maxSize - 1;// 获取到待插入的节点的上一个节点的游标// 首先通过最后一个节点的游标可以找到第一个节点// 通过第一个节点的游标可以找到第二个节点// 依此类推for (int i 1; i position - 1; i) {lastIndex data[lastIndex].getCursor();}StaticLinkNodeT lastNode data[lastIndex];// 待删除的节点int toDeleteIndex lastNode.getCursor();StaticLinkNodeT toDeleteNode data[toDeleteIndex];// 上一个节点的游标指向下一个节点lastNode.setCursor(toDeleteNode.getCursor());data[lastIndex] lastNode;// 当前节点的值设置为空toDeleteNode.setData(null);// 当前节点的游标设置为0toDeleteNode.setCursor(0);data[toDeleteIndex] toDeleteNode;// 把已删除的节点的索引位置作为下一次插入时的位置data[toDeleteIndex].setCursor(data[0].getCursor());data[0].setCursor(toDeleteIndex);length--;}/*** 返回节点信息**/public StaticLinkNodeT[] getData() {return data;}/*** 获取指定位置的元素** param position 指定的位置* return 指定位置的元素* throws RuntimeException 当试图获取第0个或超出实际节点数量的元素时抛出异常* author Korbin* date 2023-01-05 19:59:26**/public StaticLinkNodeT getElement(int position) {// 不得获取第0个元素// 不得获取超出实际节点数量的元素if (position 0 || position length()) {throw new RuntimeException(error position);}// 依次往下迭代即可int positionIndex data[maxSize - 1].getCursor();for (int i 1; i position; i) {positionIndex data[positionIndex].getCursor();}return data[positionIndex];}/*** 获取首节点索引** return 首节点索引* author Korbin* date 2023-01-05 20:09:43**/public int getFirstNodeIndex() {return data[maxSize - 1].getCursor();}/*** 下一个可插入的索引位** return 下一个可插入的索引位* author Korbin* date 2023-01-05 20:20:14**/public int getNextIndex() {return data[0].getCursor();}/*** 初始化静态链表** param maxSize 链表的最大长度* throws RuntimeException 最大长度为0时抛出* author Korbin* date 2023-01-05 16:30:25**/SuppressWarnings(unchecked)public void init(int maxSize) {if (maxSize 1) {throw new RuntimeException(error maxSize);}this.maxSize maxSize;data new StaticLinkNode[maxSize];for (int i 0; i maxSize - 1; i) {StaticLinkNodeT node new StaticLinkNode();node.setCursor(i 1);data[i] node;}StaticLinkNodeT node new StaticLinkNode();node.setCursor(0);data[maxSize - 1] node;length 0;}/*** 在指定位置插入** param position 位置* param value 要插入的元素* throws RuntimeException 插入到数组的0位或者跳跃进行插入或者数组长度满后插入时抛出异常* author Korbin* date 2023-01-05 19:32:06**/public void insert(int position, T value) {// 数组的第0个元素存储着数组下一个可存放节点的位置获取到这个位置int nextIndex getNextIndex();if (position 1 || position length 1) {// 插入位置不能小于1,也不能大于链表的实际长度1// 可以为length1的原因是因为允许在最后面插入throw new RuntimeException(error position);}if (length maxSize - 2) {// 如果实际长度等于最大长度时表示链表已满不能再插入throw new RuntimeException(fulled);}// 默认数组的最后一个元素存储的是第一个节点的下标int lastIndex maxSize - 1;// 获取到待插入的节点的上一个节点的游标// 首先通过最后一个节点的游标可以找到第一个节点// 通过第一个节点的游标可以找到第二个节点// 依此类推for (int i 1; i position - 1; i) {lastIndex data[lastIndex].getCursor();}// 设置第0个元素的游标值为待插入节点的游标值初始化时有设置data[0].setCursor(data[nextIndex].getCursor());// 设置这个节点的节点值为待插入值data[nextIndex].setData(value);// 设置这个节点的游标为上一个节点的游标值data[nextIndex].setCursor(data[lastIndex].getCursor());// 设置上一个节点的游标值为这个节点的位置data[lastIndex].setCursor(nextIndex);length;}/*** 判断是否为空** return 为空返回true非空返回false* author Korbin* date 2023-01-11 15:54:53**/public boolean isEmpty() {return length 0;}/*** 获取真实长度** return 长度* author Korbin* date 2023-01-05 10:15:41**/public int length() {return length;}/*** 查找element在单链表中的位置** param element 待查找的元素* return 元素在单链表中的位置* author Korbin* date 2023-01-11 15:59:23**/public int locateElement(StaticLinkNodeT element) {// 依次往下迭代即可int index data[maxSize - 1].getCursor();for (int i 0; i length; i) {StaticLinkNodeT node data[index];if (node.equals(element)) {break;}index data[index].getCursor();}return index;}Overridepublic String toString() {int length length();int index data[maxSize - 1].getCursor();StringBuilder builder new StringBuilder([);for (int i 0; i length; i) {StaticLinkNodeT node data[index];builder.append(i 1).append(:).append(node.getData()).append(, );index node.getCursor();if (index 0) {break;}}builder.append(]);return builder.toString();}}5.9 静态链表的优缺点 总的来说静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。
6 其他线性表及总结 单链表还可以继续扩展 (1) 将单链表的终端结点的指针端由空指针改为指向头结点就使单链表形成一个环这种头尾相接的单链表称为单循环链表简称循环链表通过循环链表可以从任何一个结点出发访问到链表中的所有结点; (2) 在单链表的每个结点中再设置一个指针指向其前驱结点的指针域的链表称为双向链表双向链表方便了从某一个结点获取其前、后结点; 总之比较常见的线性表包括以下 注本文为程 杰老师《大话数据结构》的读书笔记其中一些示例和代码是笔者阅读后自行编制的。 文章转载自： http://www.morning.ktcrr.cn.gov.cn.ktcrr.cn http://www.morning.qzsmz.cn.gov.cn.qzsmz.cn http://www.morning.qnyf.cn.gov.cn.qnyf.cn http://www.morning.yrdn.cn.gov.cn.yrdn.cn http://www.morning.dfbeer.com.gov.cn.dfbeer.com http://www.morning.kflpf.cn.gov.cn.kflpf.cn http://www.morning.rrqbm.cn.gov.cn.rrqbm.cn http://www.morning.zqbrw.cn.gov.cn.zqbrw.cn http://www.morning.zryf.cn.gov.cn.zryf.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn http://www.morning.htpjl.cn.gov.cn.htpjl.cn http://www.morning.yzfrh.cn.gov.cn.yzfrh.cn http://www.morning.mzcsp.cn.gov.cn.mzcsp.cn http://www.morning.nzdks.cn.gov.cn.nzdks.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.gwdnl.cn.gov.cn.gwdnl.cn http://www.morning.lrdzb.cn.gov.cn.lrdzb.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn http://www.morning.wtxdp.cn.gov.cn.wtxdp.cn http://www.morning.wyctq.cn.gov.cn.wyctq.cn http://www.morning.wanjia-sd.com.gov.cn.wanjia-sd.com http://www.morning.cjxqx.cn.gov.cn.cjxqx.cn http://www.morning.kkqgf.cn.gov.cn.kkqgf.cn http://www.morning.hmmtx.cn.gov.cn.hmmtx.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.thwhn.cn.gov.cn.thwhn.cn http://www.morning.ghccq.cn.gov.cn.ghccq.cn http://www.morning.bpmfg.cn.gov.cn.bpmfg.cn http://www.morning.qhvah.cn.gov.cn.qhvah.cn http://www.morning.mwhqd.cn.gov.cn.mwhqd.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.hhzdj.cn.gov.cn.hhzdj.cn http://www.morning.lrprj.cn.gov.cn.lrprj.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.knqzd.cn.gov.cn.knqzd.cn http://www.morning.wsgyq.cn.gov.cn.wsgyq.cn http://www.morning.kwfnt.cn.gov.cn.kwfnt.cn http://www.morning.fdxhk.cn.gov.cn.fdxhk.cn http://www.morning.zzfqn.cn.gov.cn.zzfqn.cn http://www.morning.pntzg.cn.gov.cn.pntzg.cn http://www.morning.lmmyl.cn.gov.cn.lmmyl.cn http://www.morning.tkqzr.cn.gov.cn.tkqzr.cn http://www.morning.klzt.cn.gov.cn.klzt.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.qxmnf.cn.gov.cn.qxmnf.cn http://www.morning.lnsnyc.com.gov.cn.lnsnyc.com http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.pnfwd.cn.gov.cn.pnfwd.cn http://www.morning.mwzt.cn.gov.cn.mwzt.cn http://www.morning.dgwrz.cn.gov.cn.dgwrz.cn http://www.morning.rwlns.cn.gov.cn.rwlns.cn http://www.morning.pqryw.cn.gov.cn.pqryw.cn http://www.morning.trzzm.cn.gov.cn.trzzm.cn http://www.morning.mqbdb.cn.gov.cn.mqbdb.cn http://www.morning.24vy.com.gov.cn.24vy.com http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.cndxl.cn.gov.cn.cndxl.cn http://www.morning.jlxqx.cn.gov.cn.jlxqx.cn http://www.morning.rfwkn.cn.gov.cn.rfwkn.cn http://www.morning.tdxnz.cn.gov.cn.tdxnz.cn http://www.morning.tknqr.cn.gov.cn.tknqr.cn http://www.morning.mlwpr.cn.gov.cn.mlwpr.cn http://www.morning.bfcrp.cn.gov.cn.bfcrp.cn http://www.morning.ptmgq.cn.gov.cn.ptmgq.cn http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.pgggs.cn.gov.cn.pgggs.cn http://www.morning.zdxinxi.com.gov.cn.zdxinxi.com http://www.morning.ssmhn.cn.gov.cn.ssmhn.cn http://www.morning.jjtwh.cn.gov.cn.jjtwh.cn http://www.morning.wjhqd.cn.gov.cn.wjhqd.cn http://www.morning.mztyh.cn.gov.cn.mztyh.cn http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.tcsdlbt.cn.gov.cn.tcsdlbt.cn http://www.morning.nqrfd.cn.gov.cn.nqrfd.cn http://www.morning.wqbhx.cn.gov.cn.wqbhx.cn http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.tyrlk.cn.gov.cn.tyrlk.cn
