阅读《数据结构—Java语言描述》一书：打卡第三天
- 💂 个人网站: 路遥叶子
- 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
- 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
- 💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】
目录
第二章：线性表
(一) 单链表
1.定义
2.术语
3. 结点类的描述
4. 单链表类的描述
5. 单链表的具体操作实现
6. 单链表的建立操作
(二) 单链表的应用举例
(三)顺序表与链表的比较
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟
第二章：线性表
(一) 单链表
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 : j = 0 时—— j > i 即 0 > i 即 i < 0 //当j遍历累加到 i-1 有效部分之后，即 j i if(j > i || p == null) { throw new Exception("元素不存在"); } return p.data;//返回数据} 按值查找索引号: 根据结点的数据域值进行对比查找，返回下标索引
//查询给定值的索引号，如果没有返回-1public 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 || 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 ; } } 单链表的删除操作
@Override public void remove(int i) throws Exception { //删除 Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用-1表达头结点的索引 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理: 表长度小于0 或 所获结点为null if (count < 0 || p == null ){ throw new Exception("位置非法"); } //修改链指针，使待删除结点从单链表中脱离出来 p.next = p.next.next ; }-----------------------------------------------------------------------------------------------
6. 单链表的建立操作
单链表是一种动态存储结构，不需要预先分配存储空间。因此，生成单链表的过程是一个结点“逐个插入”的过程。
根据插入位置的不同，可将创建单链表的方法分两种：头插法和尾插法
头插法：从表尾到表头的逆向创建；插入的位置永远是表头0
//用头插法逆位序建立单链表,其中n为单链表中的结点个数 public void create2(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //逆序输入n个结点的数据域值 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表头 insert(0,scanner.next()); } } 尾插法：从表头到表尾的创建；插入的位置永远是表尾【表的当前长度】length()
//用尾插法顺序建立单链表,其中n为单链表中的结点个数 public void create1(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //输入n个结点的数据值域 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表尾 insert(length(),scanner.next()); } }-----------------------------------------------------------------------------------------------
(二) 单链表的应用举例
线性表接口
package data.linear_table;//线性表接口public interface IList { public void clear() ; //清空 public boolean isEmpty(); //判断是否为空 public int length(); // 表的长度 public Object get(int i) throws Exception; //获取元素的值 public void insert(int i , Object x) throws Exception; //在指定位置，插入指定元素 public void remove(int i ) throws Exception; //删除指定元素 public int indexOf(Object x) ; //查找指定元素第一次出现的位置 public void display() ; //输出元素的值} 单链表的结点类
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 ; }} 单链表类
package data.linear_table.linked_list;import data.linear_table.IList;import java.util.Scanner;//单链表类//实现线性表IList接口public class LinkList implements IList { public Node head ; //单链表的头指针 //单链表的构造函数 public LinkList(){ //初始化头结点 head = new Node(); } //构造一个长度为n的单链表 public LinkList(int n ,boolean order) throws Exception { //初始化结点 this(); if (order){ //用尾插法顺序建立单链表 create1(n); }else { //用头插法逆位序建立单链表 create2(n); } } //用尾插法顺序建立单链表,其中n为单链表中的结点个数 public void create1(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //输入n个结点的数据值域 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表尾 insert(length(),scanner.next()); } } //用头插法逆位序建立单链表,其中n为单链表中的结点个数 public void create2(int n ) throws Exception { //构造用于输出的对象 Scanner scanner = new Scanner(System.in); //逆序输入n个结点的数据域值 for( int j = 0 ; j < n ; j++) { //生成新结点，插入到表头 insert(0,scanner.next()); } } //设为空链表 @Override public void clear() { head.data = null ; head.next = null ; } //判断带头结点的单链表是否为空 @Override public boolean isEmpty() { return head.next == null ; } //求带头结点的单链表长度 @Override public int length() { Node p = head.next;// 获得第一个结点 int length = 0;// 定义一个变量记录长度 while(p != null) { length ++;//计数 p = p.next;//p指向下一个结点 } return length; } @Override public Object get(int i) throws Exception { Node p = head.next;//初始化，p指向头结点 int j = 0;//计数器 //链表没有下一个 && 处理有效部分【从首结点开始向后查找，直到p指向第i个结点】 while(p != null && j i : j = 0 时—— j > i 即 0 > i 即 i < 0 //当j遍历累加到 i-1 有效部分之后，即 j i if(j > i || p == null) { throw new Exception("元素不存在"); } return p.data;//返回数据 } @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 || 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 ; } } @Override public void remove(int i) throws Exception { //删除 Node p = head ; // 从头结点head开始移动 int count = -1 ; // 使用-1表达头结点的索引 //循环条件： 结点不为null ， 并且 计数长度小于 i-1前驱的下标。 while (p != null && count < i -1 ) { p = p.next ; count++ ; } //判断位置是否不合理: 表长度小于0 或 所获结点为null if (count < 0 || p == null ){ throw new Exception("位置非法"); } //修改链指针，使待删除结点从单链表中脱离出来 p.next = p.next.next ; } @Override //查询给定值的索引号，如果没有返回-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; } } //输出单链表中所有的结点 @Override public void display() { //取出带头结点的单链表中的首结点 Node node = head.next; while (node != null) { //输出结点的值 System.out.println(node.data+" "); //取出下一个结点 node = node.next ; } //换行 System.out.println(); }} 例1：编程实现查找线性表(0,1,2,3,....., n-1)中第 i（[1,n]）个数据元素的直接前驱，并输出其值。并要求在单链上实现。
package data.linear_table.linked_list;import java.util.Scanner;public class Examp1 { public static void main(String[] args) throws Exception { //例1：编程实现查找线性表(0,1,2,3,....., n-1)中 // 第 i（[1,n]）个数据元素的直接前驱，并输出其值。并要求在单链上实现。 int n = 10 ; //创建一个空的单链表 LinkList L = new LinkList(); //将0，1，2，3.... 到 n-1 依次插入到表尾 for(int i = 0 ; i 0 && i <= n) { System.out.println("第"+i+"个元素的直接前驱是："+L.get(i-1)); }else { System.out.println("第"+i+"个元素的直接前驱不存在！"); } }}—— 所输入i的值必须在{0，n]的范围内。第0个元素为表头，没有前驱。输出结果：
(三)顺序表与链表的比较
链表比较灵活，插入和删除操作效率较高，但空间利用率低，适用于实现动态的线性表；
顺序表实现比较简单，并且空间利用率也较高，可高效的进行随机存取，但顺序表不易扩充，插入和删除操作效率较低，适合于实现相对“稳定”的静态线性表。
-----------------------------------------------------------------------------------------------
章节仅是博主阅读书籍的总结和理解，若有不对或欠妥的地方，还请各位大佬批评指正！！！
如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟
