首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >线性表

线性表

原创
作者头像
Noneplus
修改2019-10-14 11:29:53
3630
修改2019-10-14 11:29:53
举报
文章被收录于专栏:开发笔记开发笔记

> 摘要

>

> - 什么是线性表?

> - 线性表的分类

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

# 线性表

## 什么是线性表?

由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)

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
数据库一体机 TData
数据库一体机 TData 是融合了高性能计算、热插拔闪存、Infiniband 网络、RDMA 远程直接存取数据的数据库解决方案,为用户提供高可用、易扩展、高性能的数据库服务,适用于 OLAP、 OLTP 以及混合负载等各种应用场景下的极限性能需求,支持 Oracle、SQL Server、MySQL 和 PostgreSQL 等各种主流数据库。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档