Java配列とチェーンテーブルの違いとシーンの使用
7112 ワード
[color=brown][b]配列[/b]:要素をメモリに連続的に格納する;その利点:データは連続的に格納され、メモリアドレスが連続しているため、データを検索する際に効率が高い.その欠点:ストレージの前に、連続したメモリスペースを申請する必要があり、コンパイル時にそのスペースのサイズを決定する必要があります.実行時にスペースの大きさは、必要に応じて増加や減少することはできません.データが大きい場合は、境界を越えたり、データが小さい場合は、メモリスペースを無駄にしたりする可能性があります.データ個数を変更する場合、データの増加、挿入、削除の効率は比較的低い.
[color=brown][b]チェーンテーブル[/b][/b]:動的にメモリを申請するスペースであり、配列のようにメモリのサイズを事前に申請する必要はなく、チェーンテーブルは使用時に申請すればよいだけで、必要に応じてメモリ空間を動的に申請したり削除したりして、データの増加や削除、挿入比配列に柔軟である.また、チェーンテーブルのデータは、メモリ内の任意の場所で、アプリケーションによってデータを関連付けることができます(つまり、要素が存在するポインタによって関連付けることができます).
配列とチェーンテーブルは増加データを持って、配列の中で1つの要素を増加して、大量の要素を移動する必要があって、メモリの中で1つの要素の空間を空けて、それから増加した要素を空の空間の中に置きます;チェーンテーブルは、チェーンテーブルの最後の要素のポインタを新しい要素に指し、新しい要素が末尾要素であることを指摘すればよい.
配列適用シーン:
1、データが少ない;
2、よくする演算はシーケンス番号でデータ要素にアクセスする.
3、配列はより実現しやすく、いかなる高級言語もサポートする.
4、構築した線形表は安定している.
チェーンテーブル適用シーン:
1、線形表の長さまたは規模を推定するのは難しい.
2、頻繁に挿入削除操作を行うことができる;
3、ダイナミックな線形テーブルを構築する.
[color=brown][b]チェーンテーブル[/b][/b]:動的にメモリを申請するスペースであり、配列のようにメモリのサイズを事前に申請する必要はなく、チェーンテーブルは使用時に申請すればよいだけで、必要に応じてメモリ空間を動的に申請したり削除したりして、データの増加や削除、挿入比配列に柔軟である.また、チェーンテーブルのデータは、メモリ内の任意の場所で、アプリケーションによってデータを関連付けることができます(つまり、要素が存在するポインタによって関連付けることができます).
配列とチェーンテーブルは増加データを持って、配列の中で1つの要素を増加して、大量の要素を移動する必要があって、メモリの中で1つの要素の空間を空けて、それから増加した要素を空の空間の中に置きます;チェーンテーブルは、チェーンテーブルの最後の要素のポインタを新しい要素に指し、新しい要素が末尾要素であることを指摘すればよい.
配列適用シーン:
1、データが少ない;
2、よくする演算はシーケンス番号でデータ要素にアクセスする.
3、配列はより実現しやすく、いかなる高級言語もサポートする.
4、構築した線形表は安定している.
/**
* [ ]
* @author Administrator
*/
public class my {
// 0
private String[] src = new String[0];
/**
*
* @param s
*/
public void add(String s) {
// +1
String[] dest = new String[src.length + 1];
//
System.arraycopy(src, 0, dest, 0, src.length);
//
dest[dest.length - 1] = s;
//
src = dest;
}
/**
*
* @param index
*/
public String get(int index) {
String s = src[index];
return s;
}
/**
*
* @param index
*/
public void delete(int index) {
String[] dest=new String[src.length-1];
// index
System.arraycopy(src,0,dest,0,index);
// index -1
System.arraycopy(src,index+1,dest,index,src.length-index-1);
// src
src=dest;
}
/**
*
* @param s ， ，
*/
public void delete(String s) {
int t=-1;
for(int i=0;i if(s.equals(src[i])){
t=i;
break;
}
}
// s ，t 0
if(t>=0){
delete(t);
}
}
/**
*
* @param index
* @param s
*/
public void insert(int index,String s){
String[] dest = new String[src.length+1];
//
dest[index]=s;
// index
System.arraycopy(src,0,dest,0,index);
// index +1
System.arraycopy(src, index, dest,index+1, src.length-index);
src=dest;
}
/**
*
* @param index
* @param s
*/
public void update(int index, String s) {
src[index] = s;
}
/**
*
*/
public int size() {
return src.length;
}
} /**
*
*
* @author Administrator
*
*/
public static void main(String[] args) {
//
my arr = new my();
//
arr.add("AA");
arr.add("BB");
arr.add("CC");
arr.add("DD");
arr.add("EE");
arr.add("FF");
//
arr.delete(3);
//
arr.delete("BB");
//
arr.insert(0,"on");
//
arr.update(2, "up");
//
arr.size();
//
for (int i = 0; i < arr.size(); i++) {
String s = arr.get(i);
System.out.println(s);
}
}
}
//
// on
// AA
// up
// EE
// FFチェーンテーブル適用シーン:
1、線形表の長さまたは規模を推定するのは難しい.
2、頻繁に挿入削除操作を行うことができる;
3、ダイナミックな線形テーブルを構築する.
/**
* 【 】
*
* @author Administrator
*
*/
public class MyLinkList {
// ， ， null, null
private Node head = null;
private Node last = null;
private int num = 0;//
//
public void add(E e) {
//
Node node = new Node(e);
// ， node last
if (last != null) {
last.next = node;
node.front = last;
last = node;
} else {
// ，node
// ，
head = node;
last = node;
}
num++;
}
//
public void insert(int index, E e) {
//
Node node = new Node(e);
// index
Node n1 = getNode(index);
// n1
Node n2 = n1.front;
n2.next = node;
node.front = n2;
node.next = n1;
n1.front = node;
num++;
}
public void delete(int index) {
}
public void delete(E e) {
}
public void update(int index, E e) {
Node n1 = getNode(index);
n1.data = e;
}
public E get(int index) {
Node node = getNode(index);
return node.data;
}
//
private int getIndex(E e){
int index=-1;
Node n = head;
while(n!=null){
index++;
if(n.data.equals(e)){
break;
}
n=n.next;
}
return index;
}
public int getIndex2(E e){
for(int i=0;i E e2 = get(i);
if(e2.equals(e)){
return i;
}
}
return -1;
}
//
private Node getNode(int index) {
int t = -1;
if (index >= 0 && index < num) {
Node n = head;
while (n != null) {
t++;
if (t == index) {
break;
}
n = n.next;
}
return n;
} else {
//
throw new IndexOutOfBoundsException(" !index:" + index
+ ",size:" + num);
}
}
public int size() {
return num;
}
}
// ， MyLinkList
class Node {
//
E data;
//
Node next;
//
Node front;
//
public Node(E e) {
data = e;
}
} public class Main {
public static void main(String[] args){
myLinkList mm=new myLinkList();
mm.add("AA");
mm.add("BB");
mm.add("CC");
mm.add("DD");
mm.add("EE");
mm.insert(2," ");
mm.update(3, " ");
for(int i=0;i String s=mm.get(i);
System.out.println(s);
}
}
}
//
// AA
// BB
//
//
// DD
// EE