线性表及其算法（java实现）

IntMain 发布于2019-08-15 18:05 / 2848人阅读

摘要：其中，数据元素的个数为表的长度，当为零时成为空表，非空的线性表通常记为，，，，，，，一线性表的顺序存储及算法线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。

线性表

线性表是最简单和最常用的一种数据结构，它是有n个数据元素（节点）组成的有限序列。其中，数据元素的个数n为表的长度，当n为零时成为空表，非空的线性表通常记为：

（a1，a2，… ，ai-1，ai， ai+1，…，an）

一. 线性表的顺序存储及算法

线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。

1.顺序表的结构定义

public class SeqList {
    
    /* 初始空间为10 */
    private static final int LIST_SIZE = 10;
    
    /* 数组data用来存放元素 */
    private int[] data;
    
    /* 当前表长，实际存储元素的个数 */
    private int length;
    
}

2.插入运算

顺序表的插入运算是指在线性表的第i-1个元素和第i个元素之间插入一个新元素。由于顺序表逻辑上相邻的元素在物理结构上也相邻，其物理存储关系也要发生相应的变化。除非i=n+1，否则必须将原顺序表的第i个元素开始的所有元素分别向后移动1个位置。

/**
 * 在顺序表list中第i个位置之前插入一个新元素node
 * @param list 顺序表
 * @param i 插入位置
 * @param node 新元素
 */
public void insertList(SeqList list, int i, int node) {
        
    if (i < 1 || i > list.length + 1) {
        System.out.println("position error");
        return;
    }
        
    if (list.length >= LIST_SIZE) {
        System.out.println("overflow");
        return;
    }
        
    for (int j = list.length - 1; j >= i - 1; j --) {
        /* 从最后一个元素开始逐一后移 */
        list.data[j+1] = list.data[j];
    }
    /* 插入新元素 */
    list.data[i-1] = node;
    /* 表长加1 */
    list.length ++;
        
}

3.删除运算

顺序表的删除运算指的是将表中第i个元素删除，与插入运算相反，插入是向后移动元素，删除运算则是向前移动元素。

/**
 * 在顺序表list中删除第i个元素，并返回被删除的元素
 * @param list 顺序表
 * @param i 元素位置
 * @return node
 */
public int deleteList(SeqList list, int i) {

    int node = 0;

    if (i < 0 || i > list.length) {
        System.out.println("position error");
        return node;
    }

    node = list.data[i-1];
    for (int j = i; j < list.length; j ++) {
        /* 元素前移 */
        list.data[j-1] = list.data[j];
    }

    list.length --;

    return node;

}

4.顺序表逆置

先以表长的一半为循环控制次数，将表中最后一个元素同顺序顺数第一个元素交换，将倒数第二个元素同顺数第二个元素交换，以此类推，直至交换完为止。

/**
 * 顺序表逆置
 * @param list 原始顺序表
 * @return 逆置后的顺序表
 */
public SeqList converts(SeqList list) {
        
    int node;
    int length = list.length/2;
    for (int i = 0; i < length; i ++) {
        /* 对称交换元素 */
        int j = list.length - 1 - i;
        node = list.data[i];
        list.data[i] = list.data[j];
        list.data[j] = node;
    }
    return list;
        
}

二. 线性表的链式存储及算法

链式存储结构存储线性表数据元素的存储空间可能是连续的，也可能是不连续的，因而链表的节点是不可以随机存取的，链式存粗是最常见的存储方式之一。

在使用链式存储结构表示每个数据元素时，除了存储元素本身的信息外，还需要一个存储指示后继元素存储位置的地址，利用这种存储方式表示的线性表称为链表。

5.单链表的结构定义

public class LinkList {

    /* 数据域 */
    private char data;

    /* 后继元素 */
    private LinkList next;

}

6.头插法建表算法

头插法是从一个空表开始，重复读入数据，生成新节点，将读入的数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头上，直到结束为止。

/**
 * 头插法创建表
 * @param chars 字符数组
 * @return 单链表
 */
public LinkList createListF(char[] chars) {

    LinkList node;
    LinkList head = null;

    for (char ch : chars) {
        /* 申请新节点 */
        node = new LinkList();
        node.data = ch;

        /* 指向后继节点 */
        node.next = head;
        head = node;
    }

    /* 返回头节点 */
    return head;

}

7.尾插法建表算法

头插法建表中节点的次序和输入时的顺序相反，若需要和输入次序一致，则可使用尾插法。

/**
 * 尾插法建表
 * @param chars 字符数组
 * @return 单链表
 */
public LinkList createListR(char[] chars) {

    LinkList node;
    LinkList head = null;
    LinkList rear = null;

    for (char ch : chars) {
        node = new LinkList();
        node.data = ch;

        if (head == null) {
            /* 新节点为头节点 */
            head = node;
        } else {
            /* 上一个节点指向新节点 */
            rear.next = node;
        }
        /* 表尾指向新的节点 */
        rear = node;
    }

    /* 返回头节点 */
    return head;

}

GPU云服务器云服务器线性表顺序实现c语言线性表符号表算法 java 顺序线性表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69617.html

数据结构分析及其实现(Stack、Queue、Tree、LinkedList)

摘要：常见数据结构分析及实现说明本文中的代码是参考编程思想某培训机构。同时还要分析这些数据结构在时间和空间上的开销。这种专门研究应用程序中的数据之间的逻辑关系，存储方式及其操作的学问就是数据结构。常见数据结构分析及实现说明本文中的代码是参考《Java编程思想》、某培训机构。文中的代码放Github了，有兴趣的可以看看，点歌star鼓励下我。代码在Sublime中敲的，坑爹的GBK...

Richard_Gao 2019-08-15 14:34 评论0 收藏0
数据结构与算法——常用数据结构及其Java实现

摘要：亦即总结常见的的数据结构，以及在中相应的实现方法，务求理论与实践一步总结到位。中，使用链表作为其基础实现。其限制是仅允许在表的一端进行插入和删除运算。前言仿佛一下子，2017年就快过去一半了，研一马上就要成为过去式了，我打算抓住研一的尾巴，好好梳理一下数据结构与算法，毕竟这些基础知识是很重要的嘛。所以准备在这里搞一个系列的文章，以期透彻。本系列将采用Java语言来进行描述。亦即总...

RiverLi 2019-08-16 10:37 评论0 收藏0
数据结构与算法——常用高级数据结构及其Java实现

摘要：前文数据结构与算法常用数据结构及其实现总结了基本的数据结构，类似的，本文准备总结一下一些常见的高级的数据结构及其常见算法和对应的实现以及应用场景，务求理论与实践一步到位。前文数据结构与算法——常用数据结构及其Java实现总结了基本的数据结构，类似的，本文准备总结一下一些常见的高级的数据结构及其常见算法和对应的Java实现以及应用场景，务求理论与实践一步到位。跳跃表跳跃列表是对...

itvincent 2019-08-15 14:33 评论0 收藏0
数据结构于算法—线性表详解

摘要：前言通过前面数据结构与算法前导我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。基本结构对于线性表，我们只需要一个数组和就能表示基本信息。前言通过前面数据结构与算法前导我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解解分享给大家。其实说实话，可能很多人依然分不清线性表，顺序表，和链表之间的区别和联系！线性...

Freelander 2019-08-19 10:29 评论0 收藏0
后端好书阅读与推荐（续四）

摘要：后端好书阅读与推荐系列文章后端好书阅读与推荐后端好书阅读与推荐续后端好书阅读与推荐续二后端好书阅读与推荐续三后端好书阅读与推荐续四这里依然记录一下每本书的亮点与自己读书心得和体会，分享并求拍砖。后端好书阅读与推荐系列文章：后端好书阅读与推荐后端好书阅读与推荐（续）后端好书阅读与推荐（续二）后端好书阅读与推荐（续三）后端好书阅读与推荐（续四）这里依然记录一下每本书的亮点与自己读书心得...

phodal 2019-06-28 17:55 评论0 收藏0