Javaによる単一チェーンテーブルの各種操作
50759 ワード
Javaを使用して、単一チェーンテーブルのさまざまな操作を実現します.
単一チェーンテーブルの構造は次のとおりです.
具体的なコードは以下の通りです.
1.チェーンテーブルの末尾に追加
2.i番目の要素を削除
3.チェーンテーブルの長さを計算する
4.チェーンテーブルのソート
5.単一チェーンテーブルの重複要素の削除
6.チェーンテーブルの印刷
7.単一チェーンテーブルの最後からk番目の要素を見つける
8.チェーンテーブルの反転を実現し、反転チェーンテーブル以降のヘッドノードに戻る
9.チェーンテーブルの要素を末尾から出力する方法
10.単一チェーンテーブルの中間ノードを探す
11.チェーンテーブルにループがあるかどうかを検出する方法
12.リングチェーンテーブルのあるリングの入口を探す
13.指定されたポインタを、ヘッダポインタを知らずに削除する方法
14.2つのチェーンテーブルが交差しているかどうかを判断する:ループレスチェーンテーブルのみを考慮する
15.2つのチェーンテーブルが交差している場合、交差するノードを見つける方法
以下、上記の方法についてテストコードを行う
単一チェーンテーブルの構造は次のとおりです.
// ，
private class Node {
private int data;
private Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
}
具体的なコードは以下の通りです.
package lianbiao;
//java LinkedList ，
public class MyLinkedList {
private Node head = null;
// ，
private class Node {
private int data;
private Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
}
1.チェーンテーブルの末尾に追加
public void add(int data) {
Node node = new Node(data);
if(head == null) {
head = node;
return;
}
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = node;
}
2.i番目の要素を削除
public boolean delete(int index) {
if(index < 1 || index > length()) {
System.out.println(" ， ");
return false;
}
if(index == 1) {
head = head.next;
return true;
}
int i = 2;
Node cur = head;
while (cur != null) {
if(i == index) {
cur.next = cur.next.next;
break;
}
i++;
cur = cur.next;
}
return true;
}
3.チェーンテーブルの長さを計算する
//
public int length() {
int count = 0;
Node cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
4.チェーンテーブルのソート
//
public void oderList() {
if(length() <= 1) {
return;
}
Node cur = head;
Node nextNode = null;
int temp = 0;
while (cur.next != null) {
nextNode = cur.next;
while (nextNode != null) {
if(cur.data > nextNode.data) {
temp = cur.data;
cur.data = nextNode.data;
nextNode.data = temp;
}
nextNode = nextNode.next;
}
cur = cur.next;
}
}
5.単一チェーンテーブルの重複要素の削除
//
public void deleteDuplecate() {
Node p = head;
while (p != null) {
Node q = p;
while (q.next != null) {
if (q.data == p.next.data) {
q.next = q.next.next;
}else {
q = q.next;
}
}
p = p.next;
}
}
6.チェーンテーブルの印刷
//
public void printList() {
Node cur = head;
while (cur != null) {
System.out.print(cur.data+",");
cur = cur.next;
}
System.out.println();
}
7.単一チェーンテーブルの最後からk番目の要素を見つける
// k :
// ： ， k-1 ， ， K
public Node findElem(int k) {
if(k < 1) {
return null;
}
Node p1 = head;
Node p2 = head;
for(int i=0; i< k-1 && p1 != null; i++) {
p1 = p1.next;
}
if(p1 == null) {
System.out.println("k ");
return null;
}
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
8.チェーンテーブルの反転を実現し、反転チェーンテーブル以降のヘッドノードに戻る
// , ：
public void reverse() {
Node ReverseHead = head;
Node pNode = head;
Node pPrev = null;
// ：
//Node pNext = pNode.next;
//pNode.next = pPrev;
//pPrev = pNode;
//pNode = pNext;
// pNode，
while (pNode != null) {
Node pNext = pNode.next;
// ， ReverseHead
if(pNext == null) {
ReverseHead = pNode;
}
pNode.next = pPrev;
pPrev = pNode;
pNode = pNext;
}
//
this.head = ReverseHead;
}
9.チェーンテーブルの要素を末尾から出力する方法
//
public void printListReverse(Node head) {
if(head != null) {
printListReverse(head.next);
System.out.println(head.data);
}
}
10.単一チェーンテーブルの中間ノードを探す
// : ，
public Node searchMid() {
Node fast = this.head;
Node slow = this.head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
11.チェーンテーブルにループがあるかどうかを検出する方法
//
public boolean isLoop() {
Node fast = this.head;
Node slow = this.head;
if(fast == null) {
return false;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
12.リングチェーンテーブルのあるリングの入口を探す
//
public Node finLoopPort() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
if(slow == fast) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
// ， ，
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
13.指定されたポインタを、ヘッダポインタを知らずに削除する方法
//
public boolean deleteNode(Node node) {
//
if(node == null || node.next == null) {
return false;
}
int tmp = node.data;
node.data = node.next.data;
node.next = node.next.next;
return true;
}
14.2つのチェーンテーブルが交差しているかどうかを判断する:ループレスチェーンテーブルのみを考慮する
// :
public boolean isIntersect(Node head1, Node head2) {
if(head1 == null || head2 == null) {
return false;
}
// head1
Node tail1 = head1;
while (tail1.next != null) {
tail1 = tail1.next;
}
// head2
Node tail2 = head2;
while (tail2.next != null) {
tail2 = tail2.next;
}
return tail1 == tail2;
}
15.2つのチェーンテーブルが交差している場合、交差するノードを見つける方法
// ，
public Node getFirstMeetNode(Node head1, Node head2) {
if(head1 == null || head2 ==null) {
return null;
}
Node tail1 = head1;
int len1 = 1;
while (tail1.next != null) {
tail1 = tail1.next;
len1++;
}
Node tail2 = head2;
int len2 = 1;
while (tail2.next != null) {
tail2 = tail2.next;
len2++;
}
// ， null
if(tail1 != tail2) {
return null;
}
// ， ， ，
Node t1 = head1;
Node t2 = head2;
//
if(len1 > len2) {
int d = len1-len2;
while (d != 0) {
t1 = t1.next;
d--;
}
}else {
int d = len2-len1;
while (d != 0) {
t2 = t2.next;
d--;
}
}
while (t1 != t2) {
t1 = t1.next;
t2 = t2.next;
}
return t1;
}
以下、上記の方法についてテストコードを行う
//
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.add(5);
list.add(1);
list.add(3);
list.add(6);
list.add(20);
list.add(9);
list.printList();
list.delete(3);
list.delete(3);
list.delete(3);
System.out.println(" ：");
list.printList();
list.oderList();
System.out.println(" ：");
list.printList();
// findElemm(int k)
list.add(10);
list.add(7);
list.add(6);
list.printList();
Node p3 = list.findElem(1);
Node p4 = list.findElem(3);
Node p5 = list.findElem(2);
System.out.println(" ："+p3.data);
System.out.println(" ："+p4.data);
System.out.println(" ："+p5.data);
System.out.println(" ");
list.printList();
list.reverse();
System.out.println(" ");
list.printList();
System.out.println(" ");
list.printListReverse(list.head);
}
}