第二章：线性表
(一) 单链表
1.定义
采用链式存储方式存储的线性表称为链表。
链表中每一个结点包含存放数据元素值的数据域和存放逻辑上相邻节点的指针域。
数据域 data：用于存放数据元素的值。
指针域 next：用于存放后继结点的地址。
2.术语
非空表 ：
空表：若线性表为空，则头结点的指针域为空
3. 结点类的描述
单链表是由若干个结点连接而成。
数据域 data：用于存放数据元素的值。
指针域 next：用于存放后继结点的地址
package data.linear_table.linked_list; //单链表：结点类 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 ; } }
4. 单链表类的描述
只需一个头指针就能唯一标识它。所以单链表类只需设置一个头指针即可。
package data.linear_table.linked_list; import data.linear_table.IList; //单链表类 //实现线性表IList接口 public class LinkList implements IList { public Node head ; //单链表的头指针 //单链表的构造函数 public LinkList(){ //初始化头结点 head = new Node(); } //构造一个长度为n的单链表 public LinkList(int n ,boolean order) { //初始化结点 this(); if (order){ //用尾插法顺序建立单链表 create1(n); }else { //用头插法逆位序建立单链表 create2(n); } } //用尾插法顺序建立单链表,其中n为单链表中的结点个数 public void create1(int n ) { //{...} } //用头插法逆位序建立单链表,其中n为单链表中的结点个数 public void create2(int n ) { //{...} } //设为空链表 @Override public void clear() { head.data = null ; head.next = null ; } //判断带头结点的单链表是否为空 @Override public boolean isEmpty() { return head.next == null ; } //输出单链表中所有的结点 @Override public void display() { //取出带头结点的单链表中的首结点 Node node = head.next; while (node != null) { //输出结点的值 System.out.println(node.data+" "); //取出下一个结点 node = node.next ; } //换行 System.out.println(); } //求带头结点的单链表长度 @Override public int length() { //{...} return 0 ; } @Override public Object get(int i) throws Exception { //{...} return null; } @Override public void insert(int i, Object x) throws Exception { //{...} } @Override public void remove(int i) throws Exception { //{...} } @Override public int indexOf(Object x) { //{...} return 0; } }
注：单链表类中的“//{...}”中的代码将在后续的具体操作中实现
-----------------------------------------------------------------------------------------------
5. 单链表的具体操作实现
单链表的长度
public int length() { Node p = head.next; // 获得第一个结点 int length = 0; // 定义一个变量记录长度 while(p != null) { length ++; //计数 p = p.next; //p指向下一个结点 } return length; }
单链表的查找操作
按位序号查找操作：i 结点的限制长度为[0,n-1]之间(n为单链表的当前长度)
public Object get(int i) { Node p = head.next; //初始化，p指向头结点 int j = 0; //计数器 //链表没有下一个 && 处理有效部分【从首结点开始向后查找，直到p指向第i个结点】 while(p != null && j < i) { //指向后继结点 p = p.next; j++; } //i 小于0 或者i 大于表长度减一时，即不合法 //解析 j > i : j = 0 时—— j > i 即 0 > i 即 i < 0 //当j遍历累加到 i-1 有效部分之后，即 j < i 即要使位置不合法，则需 j > i if(j > i || p == null) { throw new Exception("元素不存在"); } return p.data; //返回数据 }
按值查找索引号: 根据结点的数据域值进行对比查找，返回下标索引
//查询给定值的索引号，如果没有返回-1 public int indexOf(Object x) { Node p = head.next; // 初始化，p指向头结点 int j = 0; // 不匹配元素的个数，计数器 while(p != null && !p.data.equals(x)) { // 循环依次找【不匹配】元素 p = p.next; j++; } // 返回匹配索引，如果没有返回-1 if(p != null) { return j; } else { return -1; } }
单链表的插入操作
需求：向索引i前面插入一个新结点s
思路：获得i的前驱，结点P
—— 带头结点的单链表上插入操作算法
@Override //在带头结点的单链表的第i个结点之前插入一个数据域值为x的新结点 public void insert(int i, Object x) throws Exception { //获得i前驱，结点p Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用 -1 表达头结点的索引 //请用 i= -1/0/1 去测试 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理 if (count < 0 || p == null ){ throw new Exception("位置非法"); } //创建一个结点，存入数据x Node s = new Node(x); //插入位置为表的中间或表尾时 s.next = p.next ; p.next = s ; }
注意：指向结点的顺序不可变
//创建一个结点，存入数据x
Node s = new Node(x);
//插入位置为表的中间或表尾时
s.next = p.next ; // 第1步
p.next = s ; // 第2 步
两步的顺序不可调换
原因：
如若调换位置：如下图
若位置顺序不变：如下图
—— 不带头结点的单链表上插入操作算法：考虑到在表
@Override //在不带头结点的单链表的第i个结点之前插入一个数据域值为x的新结点 public void insert(int i, Object x) throws Exception { //获得i前驱，结点p Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用 -1 表达头结点的索引 //请用 i= -1/0/1 去测试 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理 if (count > i || p == null ){ throw new Exception("位置非法"); } //创建一个结点，存入数据x Node s = new Node(x); //判断： 插入位置为表头时 if( i == 0 ){ s.next = head ; head = s ; }else { //插入位置为表的中间或表尾时 s.next = p.next ; p.next = s ; } }
头插入节点的情况
