12免费建站网站,山东网站建设哪里好,代理公司韩剧在线观看免费,资源网搭建源码链表分为单链表#xff0c;循环链表#xff0c;双向链表。 1#xff0c;链表 采用链式方式储存的线性表称为链表#xff0c;链表是用若干地址分散的存储单元存储数据元素。必须采用附加信息表示数据元素之间的逻辑关系#xff08;逻辑上相邻结点地址-指针域#xff09;。…链表分为单链表循环链表双向链表。 1链表 采用链式方式储存的线性表称为链表链表是用若干地址分散的存储单元存储数据元素。必须采用附加信息表示数据元素之间的逻辑关系逻辑上相邻结点地址-指针域。还包含元素本身的信息-数据域。 2单链表 指结点中只包含一个指针域的链表。单链表的头指针是线性表的起始地址是线性表中第一个数据元素的存储地址是单链表的唯一标识。单链表的尾结点没有后继节点指针域为null。 单链表的结点的存储空间是在插入和删除过程中动态申请和释放的不需要预先分配从而避免了顺序表因空间不足要扩充空间或者复制元素的过程避免了顺序表因容量过大造成的资源浪费的问题提高了运行效率和存储空间的利用率。 Java代码描述
/*** 2020年3月31日下午5:43:19* 线性表的抽线数据Java接口 --线性表储存结构*/
package com.lovely.linearList;/*** author echo lovely**/
public interface IList {void clear();boolean isEmpty();int length();Object get(int i) throws Exception; // 返回线性表数据中第i个元素void insert(int i, Object x) throws Exception; // 把x插入第i个位置void remove(int i) throws Exception;int indexOf(Object x);void display(); // 输出线性表各个元素的值}
package com.lovely.linearList;/** * 2020年4月1日下午8:25:10* * author echo lovely** category 节点类 用于存数据 和 后继节点*/public class Node {public Object data; // 存放节点数据值public Node next; // 存放后继节点public Node() {this(null, null);}// 只有节点值的构造函数public Node(Object data) {this(data, null);}// 带有节点值和后继节点的构造函数public Node(Object data, Node next) {this.data data;this.next next;}
}
实现链表功能
package com.lovely.linearList;import java.util.Scanner;/*** author echo lovely** 2020年4月1日下午8:32:46* * 单链表的一系列操作*/public class LinkedList implements IList {public Node head; // 单链表的头指针public LinkedList() {this.head new Node(); // 初始化 头节点}// 构造长度为n的单链表public LinkedList(int n, boolean order) {this();if (order) create1(n);elsecreate2(n);}public void create1(int n) {// 用尾插法顺序建立单链表 n为单链表长度Scanner sc new Scanner(System.in);for (int i 0; i n; i ) {try {insert(0, sc.nextInt());} catch (Exception e) {e.printStackTrace();sc.close();}}}public void create2(int n) {// 用头插法逆序建立单链表Scanner sc new Scanner(System.in);for (int i 0; i n; i ) {try {insert(length(), sc.nextInt());} catch (Exception e) {e.printStackTrace();sc.close();}}}Overridepublic void clear() {// 将链表置空head.data null;head.next null; // 后继节点置空}Overridepublic boolean isEmpty() {// 判断链表是否 是 空return head.next null;}Overridepublic int length() {// 链表长度Node p head.next; // p 指向单链表的首结点int length 0;while (p ! null) {p p.next; // 下个节点length ;}return length;}Overridepublic Object get(int i) throws Exception {Node p head.next; // p指向单链表的首结点int j;// 从首结点开始向后查找 直到p指向第i个节点 或者结点为 nullfor (j 0; j i p ! null; j ) {p p.next;}if (j i || p null)throw new Exception(第 i 数据元素不存在);return p.data;}Overridepublic void insert(int i, Object x) throws Exception {Node p head; // 头指针int j -1;// 寻找第i个节点的前驱while (p ! null j i - 1) {p p.next;j ;}if (j i - 1 || p null)throw new Exception(插入位置不合法);// 创建结点Node s new Node(x);s.next p.next;p.next s;}Overridepublic void remove(int i) throws Exception {Node p head;int j -1;// 寻找第i个结点的前驱结点while (p ! null j i - 1) {p p.next;j ;}if (j i - 1 || p.next null)throw new Exception(删除位置不合法);p.next p.next.next;}Overridepublic int indexOf(Object x) {Node p head.next; int j 0;while (p ! null !p.data.equals(x)) { // 数据元素存在没查找到下个结点继续找p p.next;j ;}if (p null)return -1;return j;}Overridepublic void display() {Node p head.next;while (p ! null) {System.out.print(p.data );p p.next;}System.out.println();}}
测试
package com.lovely.linearList;import java.util.Scanner;public class TestLinkedList {public static void main(String[] args) {LinkedList list new LinkedList(5, true);int i list.indexOf(3);System.out.println(i);list.display();}static void showInsert() {int n,val;Scanner sc new Scanner(System.in);System.out.println(请输入元素数组的个数);n sc.nextInt();LinkedList l new LinkedList(); // 声明单链表for (int i 0; i n; i) {Node q l.head;System.out.print(输入 (i 1) 个元素的值: );val sc.nextInt();Node p new Node(val);while (q ! null q.next ! null Integer.valueOf(q.next.data.toString()) val) {q q.next; }p.next q.next; // 插入操作q.next p;}Node k l.head;for (int i 0; i n; i) {k k.next;System.out.println(k.data);}sc.close();}}
3循环链表 链表首尾相连尾结点的指针域指向头节点环状的链表。 4双向链表 有两个指针域一个指针指向前驱结点一个指针指向后继结点查找快。 比较顺序表和链表 顺序表查找快捷靠下标。插入删除效率低需要移动很多数据。 链表插入删除效率高动态对储存空间分配。储存密度低不可按照下标存取。查找遍历慢。
