当前位置:主页 > java教程 > java实现线性表及算法

java实现线性表及算法详解

发布:2019-06-13 09:19:25 143


我们帮大家精选了相关的编程文章,网友堵新妹根据主题投稿了本篇教程内容,涉及到java、线性表、java实现线性表及算法相关内容,已被521网友关注,内容中涉及的知识点可以在下方直接下载获取。

java实现线性表及算法

线性表

线性表是最简单和最常用的一种数据结构,它是有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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。


参考资料

相关文章

  • Java实现的Base64加密算法知识点总结

    发布:2019-06-04

    这篇文章主要介绍了Java实现的Base64加密算法,结合实例形式分析了Java实现的base64编码转换相关使用方法及操作注意事项,需要的朋友可以参考下


  • Java求质数的几种常用算法总结

    发布:2019-06-11

    这篇文章主要介绍了Java求质数的几种常用算法,结合实例形式分析了三种比较常见的求质数算法原理及相关实现技巧,需要的朋友可以参考下


  • java微信小程序开发中加密解密算法总结

    发布:2019-06-05

    这篇文章主要为大家详细介绍了java实现微信小程序加密数据解密算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


网友讨论