快捷導航

java實現(xiàn)線性表及其算法

更新時間：2018年06月01日 13:46:07 作者：博弈

線性表是最簡單和最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是有n個體數(shù)據(jù)元素（節(jié)點）組成的有限序列，這篇文章主要介紹了java實現(xiàn)線性表及其算法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

線性表

線性表是最簡單和最常用的一種數(shù)據(jù)結(jié)構(gòu)，它是有n個體數(shù)據(jù)元素（節(jié)點）組成的有限序列。其中，數(shù)據(jù)元素的個數(shù)n為表的長度，當n為零時成為空表，非空的線性表通常記為：

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

一. 線性表的順序存儲及算法

線性表的順序存儲指的是將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組地址連續(xù)的存儲單元里，用這種方法存儲的線性表稱為順序表。

1.順序表的結(jié)構(gòu)定義

public class SeqList { 
 /* 初始空間為10 */
 private static final int LIST_SIZE = 10; 
 /* 數(shù)組data用來存放元素 */
 private int[] data; 
 /* 當前表長，實際存儲元素的個數(shù) */
 private int length; 
}

2.插入運算

順序表的插入運算是指在線性表的第i-1個元素和第i個元素之間插入一個新元素。由于順序表邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰，其物理存儲關(guān)系也要發(fā)生相應(yīng)的變化。除非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.順序表逆置

先以表長的一半為循環(huán)控制次數(shù)，將表中最后一個元素同順序順數(shù)第一個元素交換，將倒數(shù)第二個元素同順數(shù)第二個元素交換，以此類推，直至交換完為止。

/**
 * 順序表逆置
 * @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;
  
}

二. 線性表的鏈式存儲及算法

鏈式存儲結(jié)構(gòu)存儲線性表數(shù)據(jù)元素的存儲空間可能是連續(xù)的，也可能是不連續(xù)的，因而鏈表的節(jié)點是不可以隨機存取的，鏈式存粗是最常見的存儲方式之一。

在使用鏈式存儲結(jié)構(gòu)表示每個數(shù)據(jù)元素時，除了存儲元素本身的信息外，還需要一個存儲指示后繼元素存儲位置的地址，利用這種存儲方式表示的線性表稱為鏈表。

5.單鏈表的結(jié)構(gòu)定義

public class LinkList {

 /* 數(shù)據(jù)域 */
 private char data;

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

}

6.頭插法建表算法

頭插法是從一個空表開始，重復讀入數(shù)據(jù)，生成新節(jié)點，將讀入的數(shù)據(jù)存放到新節(jié)點的數(shù)據(jù)域中，然后將新節(jié)點插入到當前鏈表的表頭上，直到結(jié)束為止。

/**
 * 頭插法創(chuàng)建表
 * @param chars 字符數(shù)組
 * @return 單鏈表
 */
public LinkList createListF(char[] chars) {

 LinkList node;
 LinkList head = null;

 for (char ch : chars) {
  /* 申請新節(jié)點 */
  node = new LinkList();
  node.data = ch;

  /* 指向后繼節(jié)點 */
  node.next = head;
  head = node;
 }

 /* 返回頭節(jié)點 */
 return head;

}

7.尾插法建表算法

頭插法建表中節(jié)點的次序和輸入時的順序相反，若需要和輸入次序一致，則可使用尾插法。

/**
 * 尾插法建表
 * @param chars 字符數(shù)組
 * @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) {
   /* 新節(jié)點為頭節(jié)點 */
   head = node;
  } else {
   /* 上一個節(jié)點指向新節(jié)點 */
   rear.next = node;
  }
  /* 表尾指向新的節(jié)點 */
  rear = node;
 }

 /* 返回頭節(jié)點 */
 return head;
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: