原创

线性表

> 摘要

>

> - 什么是线性表?

> - 线性表的分类

> - 顺序表,单链表,约瑟夫环,双向链表代码实现

# 线性表

## 什么是线性表?

由0个或多个元素组成的有限序列。

point:

- 序列=有序性

- 多个元素的线性表,第一个元素没有前驱,最后一个元素没有后继,其他元素有且仅有一个前驱,一个后继。

- 0个元素构成的线性表称为空表

<br>

## 线性表的分类

线性表分为顺序表,链表,其中链表又可分为单链表,双向链表

<br>

### 顺序表

- 采用顺序存储方式,其特点是逻辑上相邻的点物理上也相邻,插入删除效率低,查找效率高

- 基于数组实现

- 由于采用顺序存储方式,所以需要连续的存储空间,也就意味着长度必须是固定的。

<br>

### 单链表

- 采用链式方式存储,其特点是逻辑上相邻的点物理上并不一定相邻,插入删除效率高,查找效率低

- 链式存储是采用节点来进行存储的,每个节点包括data域和next域。

- 基于指针实现,但Java中是没有指针的。或者说,是C的变种指针,称为引用。与C不同的是,Java中的引用在考虑安全性的前提下,是不允许修改的。

- <br>

【网上看到了一个关于Java指针和C++的区别比喻】

在java中可以坐飞机到指定的目的地,但是你不能开飞机(安全)。但是在C++中可以自己开飞机(操作飞机)--具有危险性。

换句话说,Java中的指针只能被使用,而不能像C++中可以自由修改。

<br>

【如果Java中指针的引用是不可修改的,那么链表的插入删除操作导致的next域中引用的改变是如何实现的?】

指针应用的粒度过大,解决这个问题得从Java中对象的存储堆栈结构说起。

Java中通过堆栈来存储对象,栈中存放堆中对象的地址,堆中存放具体的对象,而堆的确是不可修改的,但栈中对象地址是可以修改的,而链表节点中next域中存放的正是栈中下个节点的对象地址。

<br>

### 双向链表

- 双向链表基于单链表,区别在于多了一个pre域指向前一个节点

- 单向列表只能从前往后查找,而双向链表可以向前向后查找。

## 一,顺序表代码实现

```

package com.company;

public class Linear_List {

private int[] arr;

private int size;

/**

* 初始化顺序表

* 顺序表基于数组实现,长度不可变,initial_size为初始化值

* @param initial_size

*/

public Linear_List(int initial_size) {

this.arr = new int[initial_size];

this.size = 0;

}

/**

* 判断顺序表是否满了

* @return

*/

public boolean isFull() {

if (this.size == arr.length) {

return true;

} else {

return false;

}

}

/**

* 判断顺序表是否为空

* @return

*/

public boolean isEmpty() {

if (this.size == 0) {

return true;

} else {

return false;

}

}

/**

* 1、增加元素

*

* @param value :要插入的数据

* @param index :插入的位置

*/

public void addData(int value, int index) {

if (isFull()) {

System.out.println("线性表已满");

} else if (index < 0 || index > arr.length) {

System. out.println("插入的下标越界,您要插入的下标为:" + index);

} else {

for (int i = this.size - 1; i >= index; i--) {

arr[i + 1] = arr[i]; //依次后移

}

arr[index] = value;

this.size++; //数组元素下标增加

}

}

/**

* 2、删除元素

*

* @param value :要删除的数

*/

public void deleteData(int value) {

int pos = find(value);

if (pos == -1) {

System.out.println("您要找的 " + value + " 元素不在该线性表中");

} else {

System.out.println("您要删除的 " + value + " 元素下标为:" + pos);

}

for (int j = pos; j <= this.size - 2; j++) { //这里-2,是因为找到的元素下标,要将后一个的冲掉前一个,会增加一个

arr[j] = arr[j + 1];

}

this.size--;

}

/**

* 3、查找元素下标

*

* @param value :所要查找的元素

* @return :返回下标

*/

public int find(int value) {

int pos = -1;

if (isEmpty()) {

System.out.println("线性表已空,没有可删除元素");

} else {

for (int i = 0; i <= this.size - 1; i++) {

if (arr[i] == value) {

pos = i;

}

}

}

return pos;

}

/**

* 打印线性表元素

*/

public void print() {

for (int i = 0; i <= this.size - 1; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}

public static void main(String[] args) {

//初始化顺序表

Linear_List linear_list = new Linear_List(10);

for (int i = 0; i < 10; i++) {

linear_list.addData(i + 1, i);

}

linear_list.print();

//删除

linear_list.deleteData(5);

System.out.println("删除后的线性表:");

linear_list.print();

//增加测试

System.out.println("添加元素:值为5,下标为1");

linear_list.addData(5, 1);

linear_list.print();

//查找元素下标

int find_value = 15;

int pos = linear_list.find(find_value);

if (pos == -1) {

System.out.println("您要找的 " + find_value + " 元素不在该线性表中");

} else {

System.out.println("您要找的 " + find_value + " 元素下标为:" + pos);

}

}

}

```

![1570940563203](https://img2018.cnblogs.com/blog/1401585/201910/1401585-20191013191251643-1555937346.png)

## 二,单链表代码实现

```

import java.util.Stack;

//定义单个链表节点

class Node

{

public String data; //定义数据节点

public Node next; //定义指向下一个节点的指针

public Node(String data) {

this.data = data;

}

public Node() {

}

public String getData() {

return data;

}

public void setData(String data) {

this.data = data;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

@Override

public String toString() {

return "Note{" +

"data='" + data + '\'' +

'}';

}

}

class Operation

{

//初始化头结点

private static Node head = new Node();

//插入节点(头插)

public void insertToHead(Node node)

{

//定义一个temp节点,保持头结点不动,方便测试

Node temp = head;

//头插法需要设置head.next和node.next的值。其指中nodeNext向headNext,而headNext指向node。

//由于是赋值的关系,二者顺序不可颠倒

node.next=temp.next;

temp.next=node;

}

//插入节点(尾插)

public void insertToLast(Node node)

{

Node temp = head;

while (true)

{

if(temp.next==null)

{break;}

temp=temp.next;

}

temp.next=node;

}

//插入节点(指定位置k之后)

public void insertToK(Node node,int k)

{

Node temp = head;

for(int i=0;i<k;i++)

{

temp=temp.next;

}

node.next=temp.next;

temp.next=node;

}

//删除第m个节点

public void deleteM(int m)

{

Node temp = head;

for(int i=0;i<m-1;i++)

{

temp=temp.next;

}

temp.next=temp.next.next;

}

//修改第n个节点(n)

public void updateN(int n)

{

Node temp = head;

for(int i=0;i<n;i++)

{

temp=temp.next;

}

temp.data="up";

}

public static void main(String[] args)

{

Operation operation = new Operation();

//头插法

operation.insertToHead(new Node("A"));

operation.insertToHead(new Node("B"));

operation.insertToHead(new Node("C"));

//尾插法

operation.insertToLast(new Node("1"));

operation.insertToLast(new Node("2"));

operation.insertToLast(new Node("3"));

Node temp =head;

System.out.println("遍历链表:");

while(true)

{

if(temp.next==null)

{break;}

else

{

temp=temp.next;

System.out.println(temp.toString());

}

}

System.out.println();

/**

* 遍历链表,通过判断temp.next是否为空

*/

System.out.println("1.求单链表中有效节点个数.");

temp=head;

int count=0;

while(true)

{

if(temp.next==null)

{break;}

else

{

temp=temp.next;

count++;

}

}

System.out.println(count);

System.out.println();

/**

* 数学问题,获取链表总长,总长减去2就是倒数第三个的位置

*/

System.out.println("2.查找单链表中倒数第3个节点");

temp=head;

//获取链表总长

int length=0;

while (true)

{

if(temp.next==null)

{break;}

else

{

temp=temp.next;

length++;

}

}

//总长减去2就是倒数第三个的位置

temp=head;

for(int i=0;i<length-2;i++)

{

temp=temp.next;

}

System.out.println(temp.data);

System.out.println();

/**

* 通过栈来实现,将链表节点全部压入栈中,再取出来

*/

System.out.println("3.从尾到头打印链表");

//把链表节点全部压入栈中,然后取出来

Stack<Node> stack = new Stack<>();

Node cur = head.next;

while (cur!=null)

{

stack.push(cur);

cur=cur.next;

}

while (stack.size()>0)

{

System.out.println(stack.pop());

}

System.out.println();

/**

* 定义三个辅助节点,上一个节点,当前节点,下一个节点

*

* 假设原链表结构

* head ---> A ---> B ---> C

*

* 第一次循环后:preNode=head;nextNode,curNode指向A

*

* 原始链表 head ---> A ---> B ---> C

反转链表 NULL<--- head

* preNode nextNode

* curNode

*

* 第二次循环后:preNode=A;nextNode,curNode指向B

*

*原始链表 head ---> A ---> B ---> C

反转链表 NULL<--- head<---A

preNode

* * nextNode

* * curNode

*

* 以此类推

* 最后一次循环

* 原始链表 head ---> A ---> B ---> C

反转链表 NULL<--- head<---A<----- B<---- C

* preNode

* nextNode

* curNode

*

* //preNode变成了表头

*/

System.out.println("4.实现单链表反转");

Node preNode = null;

Node curNode = head;

Node nextNode = null;

while (curNode!=null)

{

nextNode = curNode.next;

curNode.setNext(preNode);

preNode=curNode;

curNode=nextNode;

}

//preNode变成了表头

while(true)

{

if(preNode.next==null)

{break;}

else

{

System.out.println(preNode.toString());

preNode=preNode.next;

}

}

}

}

```

<br>

## 三,单向环形链表输出约瑟夫环

![2019080816052262](https://img2018.cnblogs.com/blog/1401585/201908/1401585-20190810015819566-1788395138.png)

```

package com.company;

//定义单个节点

class Node

{

public String data; //定义数据节点

public Node next; //定义指向下一个节点的指针

public Node() {

}

public Node(String data) {

this.data = data;

}

@Override

public String toString() {

return "Note{" +

"data='" + data + '\'' +

'}';

}

}

public class Operation

{

//初始化头结点

private static Node head = new Node();

//尾插法

public void add(Node node)

{

Node temp = head;

while (true)

{

if(temp.next==null)

{break;}

temp=temp.next;

}

temp.next=node;

}

//创建单向环形链表

public Node createCircle(int n)

{

//创建单链表

for(int i=0;i<n;i++)

{

add(new Node("No:"+(i+1)));

}

System.out.println("遍历链表");

Node temp = head;

while(temp.next!=null)

{

temp=temp.next;

System.out.println(temp);

}

System.out.println();

//此时temp是链表最后一个节点

Node last = temp;

temp.next=head.next; //连接首尾

System.out.println("循环两遍单向环形链表:");

int count=2*n;

while(last!=null)

{

if(count==0)

{

break;

}

System.out.println(last.next);

last=last.next;

count--;

}

System.out.println("last="+last.data);

return last;

}

public static void JosephusProblem(int n, int k, int m, Node last)

{

//定位到第k个节点,输出k+1个节点并删除,并让last定位到第k个节点

Node temp = last;

for(int i=0;i<k;i++) //定位到第k个节点

{

temp=temp.next;

}

System.out.println("第一次输出"+temp.next.data);//输出

temp.next=temp.next.next; //删除第K+1个节点

last=temp.next;

for(int i=0;i<n-1;i++)

{

temp=last;

System.out.println("第二次输出"+temp.next.data);

temp.next=temp.next.next;

last=temp.next;

}

}

public static void main(String[] args)

{

Operation operation = new Operation();

//定义人数

int n=5;

Node last = operation.createCircle(n);

//定义从第几个节点开始数

int k=1;

//定义数的次数

int m=2;

System.out.println();

System.out.println("输出约瑟夫环:");

JosephusProblem(n,k,m,last);

}

}

```

![1570427499655](https://img2018.cnblogs.com/blog/1401585/201910/1401585-20191013191251374-1231161618.png)

## 三,双向链表代码实现

```

import java.util.Stack;

//定义单个节点

class Node

{

public String data; //定义数据节点

public Node next; //定义指向下一个节点的指针

public Node pre; //定义指向上一个节点的指针

public Node() {

}

public Node(String data) {

this.data = data;

}

@Override

public String toString() {

return "Note{" +

"data='" + data + '\'' +

'}';

}

}

public class Operation

{

//初始化头结点

private static Node head = new Node();

//插入节点(尾插法)

public void addNode(Node node)

{

Node temp = head;

while(true)

{

if(temp.next==null)

{

break;

}

temp=temp.next;

}

temp.next=node;

node.pre=temp;

}

//插入节点(头插法)

public void addNodeToHead(Node node)

{

Node temp = head;

node.pre=temp;

node.next=temp.next;

temp.next.pre=node;

temp.next=node;

}

//插入到第k个节点后

public void addToK(Node node,int k)

{

Node temp = head;

for(int i=0;i<k;i++)

{

temp=temp.next;

}

//先建立单链表联系

node.next=temp.next;

temp.next=node;

//建立pre指向

node.pre=temp;

node.next.pre=node;

}

//删除第n个结点

public void deleteNode(int n)

{

Node temp = head;

for(int i=0;i<n;i++)

{

temp=temp.next;

}

temp.next.pre=temp.pre;

temp.pre.next=temp.next;

}

public void list()

{

//遍历链表

Node temp = head;

while(temp.next!=null)

{

temp=temp.next;

System.out.println(temp.toString());

}

System.out.println("=============");

}

//修改第m个结点

public void update(int m)

{

Node temp = head;

for(int i=0;i<m;i++)

{

temp=temp.next;

}

temp.data="up";

}

public static void main(String[] args)

{

Operation operation = new Operation();

operation.addNode(new Node("A"));

operation.addNode(new Node("B"));

operation.addNode(new Node("C"));

operation.addNode(new Node("D"));

operation.addNodeToHead(new Node("head1"));

operation.addNodeToHead(new Node("head2"));

operation.addNodeToHead(new Node("head3"));

//遍历链表

operation.list();

System.out.println("删除第n个节点");

operation.deleteNode(3);

//遍历链表

operation.list();

System.out.println("修改第m个节点");

operation.update(3);

operation.list();

System.out.println("插入到第k个节点后");

operation.addToK(new Node("k" ),3);

operation.list();

}

}

```

<hr>

GitHub文章汇总:[JavaDev-Note](https://github.com/Noneplus/JavaDev-Note)

<br>

个人博客:[zkrun.top](zkrun.top)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • maven引入本地jar包

    但是有些情况,比如需要引入第三方包,如快递鸟,支付宝,微信等jar包(当然有可能直接提供maven依赖)

    陈灬大灬海
  • centos7部署Jenkin

    去jenkins官网https://jenkins.io/index.html下载jenkins安装包

    拓荒者
  • centos上Jenkins搭建

    Jenkins可以提供持续集成服务,它的运行环境(runtime)需要Tomcat和JDK

    拓荒者
  • 程序员,你还不会合理选择Filter、Interceptor、Aspect?

    小伙伴们应该听说过过滤器、拦截器、切面,印象上都能够起到截断拦截的作用,在做一些业务需求时,不知道如何选择,今天老顾就来介绍一下他们之间的区别。

    淡定的蜗牛
  • RabbitMQ 消息确认机制

    消息的确认,是指生产者投递消息后,如果 Broker 收到消息,则会给我们生产者一个应答。生产者进行接收应答,用来确定这条消息是否正常的发送到 Broker ,...

    海向
  • python基础四

    首先思考一个问题,什么类型是可以for循环的。你会说有list,tuput,str,dict,set等等。他们有一个共性,就是都含有__iter__方法。说明他...

    不断折腾
  • RedHat Linux RPM packages for Jenkins

    To use this repository, run the following command:

    拓荒者
  • Django篇(四)

    # 这个设置已经给与静态文件的目录,所以上面的STATIC_URL与我们自己创建的

    不断折腾
  • Python基础---类的内置方法

    __init__(): __init__方法在类的一个对象被建立时,马上运行。这个方法可以用来对你的对象做一些你希望的初始化。注意,这个名称的开始和结尾都是双下...

    我被狗咬了
  • python基础五

    常用print()#输出,input()#交互输入,open()#文件操作等都不说了。

    不断折腾

扫码关注云+社区

领取腾讯云代金券