定义:
线性表全名线性存储构造是最根本、最简略、也是最罕用的一种数据结构,专门用于存储逻辑关系为 "一对一" 的数据。
个性:
- 数据类型统一
- 数据的逻辑关系都具备一对一关系
- 数据元素无限 (专业术语为:存在惟一一个被称为“第一个”的数据元素,存在惟一一个被称为“最初一个”的数据元素)
- 是有序序列(专业术语为:除第一个元素外,每个元素都有惟一的一个”间接前驱“。除最初一个元素外,每一个元素都有惟一的”间接后继“)
存储形式:
线性表,基于数据在理论物理空间中的存储状态,又可细分为 ** 程序表(顺序存储构造)** 和 ** 链表(链式存储构造)**。
程序表(顺序存储构造):
定义:
程序表,个别应用数组实现。也就是在内存中找个初始地址,而后数据元素顺次排队,数组大小有两种形式指定——动态调配和是动静扩大。
特点:
- 随机拜访:可通过首地址和元素序号在单位工夫 O(1) 内找到指定的元素。
- 存储密度高:存储密度高是因为每个结点存储空间指用来存储数据元素,没有别的额定开销。
-
物理地位相邻:物理地位和逻辑地位一样,放弃相邻,因而插入和删除元素须要挪动大量元素,比拟耗时。这是物理构造相邻的所有数据结构的通病,尽管拜访快,然而如果有频繁的增删挪动操作,就会效率很低。
长处:
- 空间利用率高(理由:间断寄存)
- 存取速度高效,通过下标间接进行存储和读取。(想想排队哈)
- 顺序存储,随机读取(不算是长处,算是特点)
毛病:
- 插入和删除比较慢。(想想插队,前面的全副须要往后移一个位)
- 程序表开始时就要定义一个长度,因而是存在空间限度的。当须要存储的元素个数可能多于程序表元素时,可能呈现“溢出”问题。
链式存储构造:
定义:
用一组任意的存储单元存储线性表的数据元素(这组存储单元能够是间断的,也能够是不间断的),包含数据域和指针域,数据域存数据,指针域批示其后继的信息。
特点:
随机存储、程序读取:物理地位和逻辑地位不同,物理地位随机存储,但都通过指针域连成线,能够按逻辑程序读取
长处:
- 插入和删除的速度快,保留原有的物理程序(只扭转下指针。想想上述的插队问题就明确了)。
- 没有空间限度,根本只与内存空间大小无关。(满天飞)
- 随机存储,程序读取(算是特点)
毛病:
- 查找元素比较慢(不能进行索引拜访,只能从头结点开始程序查找)
- 占用额定的空间用来存储指针(不是间断寄存的(满天飞理解下),空间碎片多)
造成空间节约。
实操 :
创立线性表接口类
/**
* 线性表接口
* @author gxw
* @date 2021/11/1 早晨 21:50
*/
public interface LinearList {
/**
* 查找办法
*/
// 查找,是否蕴含 g 元素
boolean contains(Object g);
// 查找,返回 g 元素所在位置
int indexOf(Object g);
// 查找,返回第 i 地位的元素
Object getByIndex(int i);
/**
* 增加办法
*/
// 将元素插入到第 i 个地位
void add(int i, Object g) throws Exception ;
// 将元素插入到最初
void add(Object g) throws Exception ;
// 将 g 元素插入到 x 元素之前
boolean addBefore(Object x, Object g) throws Exception;
// 将 g 元素插入到 x 元素之后
boolean addAfter(Object x, Object g) throws Exception;
/**
* 删除办法
*/
// 删除第 i 个元素
void remove(int i) throws Exception ;
// 删除第一个为 g 的元素
void remove(Object g) throws Exception ;
/**
* 批改办法
*/
// 将第 i 个元素替换为 g
boolean replace(int i, Object g);
// 将 x 元素全副替换为 g
boolean replaceAll(Object x, Object g);
/**
* 返回线性表大小
*/
int getSize();
/**
* 判断线性表是否为空
*/
boolean isEmpty();
/**
* 输入线性表
*/
void display();}
程序表:
第一步:创立程序表实现类
/**
* 线性表之程序表(顺序存储构造)* @author gxw
* @date 2021/11/1 早晨 21:51
*/
public class SequenceList implements LinearList {
// 申明大小为 maxSize 的程序表
private Object[] myList;// 程序表的存储空间
private int size;// 程序表以后的长度
private int maxSize;// 程序表最大的长度
// 构造方法来初始化程序表
public SequenceList(int maxSizeParam){
// 设置程序表的初始长度为 0
size = 0;
// 设置程序表的最大长度
maxSize = maxSizeParam;
// 实例化程序表
myList = new Object[maxSize];
}
// 是否蕴含 g 元素
@Override
public boolean contains(Object g) {// 工夫复杂度 O(n)
for (Object x : myList) {if(x.equals(g))
return true;
}
return false;
}
// 获取 g 元素在第几个地位
@Override
public int indexOf(Object g) {// 工夫复杂度 O(n)
for(int i = 0;i < size;i++){if(myList[i].equals(g))
return i;
}
return -1;
}
// 获取第 i 地位的元素
@Override
public Object getByIndex(int i) {// 工夫复杂度 O(1)
// 判断是否合乎现有长度
if(i < 0 || i > size)
return null;
return myList[i];
}
@Override
public void add(int i, Object g) throws Exception {// 工夫复杂度 O(n)
// 判断程序表是否曾经满员
if(size == maxSize)
throw new Exception("程序表已满员,不可插入!");// 手动抛出异样
// 判断 i 是否在正确范畴内
if(i < 0 || i > size)
throw new Exception("插入地位不合理,不可插入!");// 手动抛出异样
// 筹备执行插入,在插入之前,将要插入地位的元素往后移
for(int j = size;j > i;j--){myList[j] = myList[j - 1];
}
// 执行插入
myList[i] = g;
// 现有程序表长度减少 1
size++;
}
@Override
public void add(Object g) throws Exception {// 工夫复杂度 O(1)
// 判断程序表是否曾经满员
if(size == maxSize)
throw new Exception("程序表已满员,不可插入!");// 手动抛出异样
// 执行插入,插入到最初
myList[size] = g;
// 现有长度加一
size++;
}
@Override
public boolean addBefore(Object x, Object g) throws Exception {// 工夫复杂度 O(n)
// 判断程序表是否曾经满员
if(size == maxSize)
return false;
// 先获取 x 元素所在位置
int index = indexOf(x);
if(index < 0)
return false;
// 将 x 元素以及后继元素往后移
add(index, g);
return true;
}
@Override
public boolean addAfter(Object x, Object g) throws Exception {// 工夫复杂度 O(n)
// 判断程序表是否曾经满员
if(size == maxSize)
return false;
// 先获取 x 元素所在位置
int index = indexOf(x);
if (index < 0)
return false;
// 将 x 元素的后继元素往后移
add(index + 1, g);
return true;
}
@Override
public void remove(int i) throws Exception {// 工夫复杂度 O(n)
// 判断程序表是否曾经为空
if(size == 0)
throw new Exception("程序表已空,无奈删除!");// 手动抛出异样
// 判断 i 元素是否在 0 -size 范畴内
if(i < 0 || i > size)
throw new Exception("角标超出范围,无奈删除!");// 手动抛出异样
// 将 i 元素之后后继元素往前移
for(int j = i;j < size;j++){myList[j] = myList[j + 1];
}
// 程序表长度减一
size--;
}
@Override
public void remove(Object g) throws Exception {// 工夫复杂度 O(n)
// 判断程序表是否曾经为空
if(size == 0)
throw new Exception("程序表已空,无奈删除!");// 手动抛出异样
// 查找元素的地位
int index = indexOf(g);
if(index >= 0){
// 删除元素,并将后继元素往前移
remove(index);
}else{throw new Exception("程序表无此元素,无奈删除!");// 手动抛出异样
}
}
@Override
public boolean replace(int i, Object g) {// 工夫复杂度 O(1)
// 判断程序表是否曾经为空
if(size == 0)
return false;
// 判断 i 是否在 0 -size 范畴内
if(i < 0 || i > size)
return false;
// 执行替换,将 i 元素的值替换为 g
myList[i] = g;
return true;
}
@Override
public boolean replaceAll(Object x, Object g) {// 工夫复杂度 O(n)
// 判断程序表是否曾经为空
if(size == 0)
return false;
// 暂存角标字符串
String indexStr = "";
// 取出元素为 x 的所有角标
for (int i = 0;i < size;i++){if(myList[i].equals(x)){indexStr += i + ",";}
}
indexStr = indexStr.substring(0, indexStr.length() - 1);
String[] indexArr = indexStr.split(",");
// 将取出的所有角标全替换为 g 元素
for (int i = 0;i < indexStr.split(",").length;i++){int index = Integer.parseInt(indexArr[i]);
// 设置值
myList[index] = g;
}
return true;
}
@Override
public int getSize() {return size;}
@Override
public boolean isEmpty() {return size == 0;}
@Override
public void display() {for (int i = 0;i < size;i++){System.out.print(myList[i] + " ");
}
System.out.println("展现程序表完结:一共长度为:" + size);
}
}
第二步:测试
public static void main(String[] args) throws Exception {
/**
* 程序表
*/
SequenceList sequenceList = new SequenceList(10);
// 增加
sequenceList.add("sequence");
sequenceList.add("hello");
sequenceList.add("world!");
sequenceList.add("hello");
sequenceList.display();
// 指定角标增加
sequenceList.add(1, "哈哈");
sequenceList.display();
// 在指定元素之前增加
sequenceList.addBefore("哈哈", "呼呼");
sequenceList.display();
// 在指定元素之后增加
sequenceList.addAfter("哈哈", "嘿嘿");
sequenceList.display();
// 替换
sequenceList.replace(1, "略略");
sequenceList.display();
// 将指定元素值全都替换成设置元素值
sequenceList.replaceAll("hello", "HELLO");
sequenceList.display();
// 删除
sequenceList.remove(1);
sequenceList.display();
// 指定元素删除
sequenceList.remove("HELLO");
sequenceList.display();}
后果:
链表:
第一步:因为单链表依赖于 Node,所以创立 Node 类
/**
* 单链表采纳了结点,所以须要以下定义
* 次要两个属性,一个是数据域 (存放数据内容),一个是指针域 (寄存下一个的结点的地址)
*/
public class Node {
// 数据域
private Object data;
// 指针域
private Node next;
public Node(){this.data = new Object();
this.next = null;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Node(Object data){this.data = data;}
public Object getData() {return data;}
public void setData(Object data) {this.data = data;}
public Node getNext() {return next;}
public void setNext(Node next) {this.next = next;}
}
第二步:创立单链表实现类
/**
* 线性表之链表(链式存储构造)* @author gxw
* @date 2021/11/1 早晨 21:53
*/
public class LinkedList implements LinearList {private Node headNode = new Node();// 定义一个头空结点
private int size;// 定义一共有几个结点
@Override
public boolean contains(Object g) {
Node node = headNode;// 从头结点开始
for(int i = 0;i < size;i++){if(node.getData().equals(g)){return true;}
// 拜访下一个结点
node = node.getNext();}
return false;
}
@Override
public int indexOf(Object g) {
Node node = headNode;// 从头结点开始
// 因为头结点不存数据,所以间接获取子结点数据
node = node.getNext();
for(int i = 0;i < size;i++){if(node.getData().equals(g)){return i;}
// 拜访下一个结点
node = node.getNext();}
return -1;
}
@Override
public Object getByIndex(int i) {
Node node = headNode;// 从头结点开始
for(int j = 0;j < i;j++){
// 拜访下一个结点, 直到拜访的第 i 个地位
node = node.getNext();}
return node.getData();}
@Override
public void add(int i, Object g) throws Exception {
// 如果 i 不在 0 -size 范畴
if(i < 0 || i > size)
throw new Exception("角标超出失常范畴 i:" + i);
// 获取到第 i 个后面的结点,只须要让后面的结点指针域指到新要增加的结点上,// 本人的指针域指到第 i 个前面的结点上,就能够实现增加了
Node node = headNode;
for(int j = 0;j < i;j++){node = node.getNext();// 继续拜访指针域,直到拜访到第 i 个结点
}
// 创立新要增加的结点
Node newNode = new Node();
// 设置新结点的数据域
newNode.setData(g);
// 设置新结点的指针域,将后面获取到的结点的指针域的值,赋值给新要增加的结点
newNode.setNext(node.getNext());
// 而后让后面取得的结点的指针域指向新增加的指针,即可胜利增加
node.setNext(newNode);
// 结点数加一
size++;
}
@Override
public void add(Object g) throws Exception {
// 在最初增加结点
add(size, g);
}
@Override
public boolean addBefore(Object x, Object g) throws Exception {
// 获取结点所在位置
int index = indexOf(x);
// 如果没有匹配的结点
if(index < 0)
return false;
// 在 x 结点前增加结点,相当于就是查找到结点地位以后地位
add(index, g);
return true;
}
@Override
public boolean addAfter(Object x, Object g) throws Exception {
// 获取结点所在位置
int index = indexOf(x);
// 如果没有匹配的结点
if(index < 0)
return false;
// 在 x 结点后增加结点
add(index + 1, g);
return true;
}
@Override
public void remove(int i) throws Exception {
// 如果 i 不在 0 -size 范畴
if(i < 0 || i > size)
throw new Exception("角标超出失常范畴 i:" + i);
// 删除结点,原理就是让此结点的前一个结点的指针域,指到此结点的下一个结点
Node node = headNode;
for (int j = 0;j < i;j++){node = node.getNext();
}
// 将前一个结点的指针域,指到此结点的下一个结点
node.setNext(node.getNext().getNext());
// 结点数减 1
size--;
}
@Override
public void remove(Object g) throws Exception {
// 查找元素所在位置
int index = indexOf(g);
// 执行删除
remove(index);
}
@Override
public boolean replace(int i, Object g) {
// 如果 i 不在 0 -size 范畴
if(i < 0 || i > size)
return false;
// 找到第 i 个结点
Node node = headNode;
for (int j = 0;j < i + 1;j++){ // 因为头结点是空结点,所以须要略过,就 i + 1
node = node.getNext();}
// 而后将第 i 个结点的数据域更换为 g
node.setData(g);
return true;
}
@Override
public boolean replaceAll(Object x, Object g) {return false;}
@Override
public int getSize() {return size;}
@Override
public boolean isEmpty() {return size == 0;}
@Override
public void display() {
Node node = headNode;
for (int i = 0;i < size;i++){node = node.getNext();
System.out.print(node.getData() + " ");
}
System.out.println("展现实现,结点长度为:" + size);
}
}
第三步:测试
public static void main(String[] args) throws Exception {
/**
* 单链表
*/
LinkedList linkedList = new LinkedList();
// 增加
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
linkedList.display();
// 在 2 之前增加
linkedList.addBefore("2", "4");
linkedList.display();
// 在 2 之后增加
linkedList.addAfter("2", "5");
linkedList.display();
// 查找地位
System.out.println(linkedList.indexOf("1"));
System.out.println(linkedList.indexOf("2"));
System.out.println(linkedList.indexOf("3"));
// 替换
linkedList.replace(1, "22");
linkedList.display();
// 删除
linkedList.remove("3");
linkedList.display();}
后果:
其它补充:
前驱:
数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。
间接前驱:
某一元素的左侧相邻元素称为“间接前驱”
前驱元素:
位于此元素左侧的所有元素都统称为“前驱元素”
后继
间接后继:
某一元素的右侧相邻元素称为“间接后继”
后继元素:
位于此元素右侧的所有元素都统称为“后继元素”
————————————END—————————————
数据结构之线性表篇,在此完结,学习中的总结,心愿能够帮忙认真学习的你,如果总结有问题,也心愿贵人忘请斧正,谢谢!