java 단일 체인 테이블의 삭제 및 정렬 실현
4366 단어 데이터 구조와 알고리즘
package LinkList;
class Node{
public Node next;
public int data;
public Node(int data){
this.data=data;
}
}
public class LinkList{
public Node head;
public int length=0;
//
public void printLinkList()
{
Node p=head;
while(p!=null)
{
System.out.println(p.data);
p=p.next;
}
System.out.println(" :"+length);
}
//
public Boolean isEmpty()
{
if(head==null)
return true;
return false;
}
//
public void addLastNode(int data)
{
Node x=new Node(data);
if(head==null)
{
head=x;length++;
return;
}
Node q=head;
while(q.next!=null)
q=q.next;
q.next=x;
length++;
}
//
public void addHeadNode(int data)
{
Node x=new Node(data);
if(head==null){
head =x;length++;
return;
}
x.next=head;
head=x;
length++;
}
//
public Boolean deleteNode(int index)
{
if(index<1||index>length)
return false;
int i=1;
Node p=head;
while(i!=(index-1))
{
p=p.next;
i++;
}
(p.next)=(p.next.next);
length--;
return true;
}
//
public Boolean updateNode(int index,int data)
{
if(index<1||index>length)
return false;
int i=1;
Node p=head;
while(iq.data)
{
int t=p.data;
p.data=q.data;
q.data=t;
flag=true;
}
q=q.next;
}
if(flag==false)
break;
flag=false;
p=p.next;
}
}
}
테스트:
package LinkList;
public class MyLinkedList {
public LinkList linkList=new LinkList();
public void testaddLastNode(){
linkList.addLastNode(1);
linkList.addLastNode(2);
linkList.addLastNode(3);
linkList.addLastNode(4);
linkList.printLinkList();
}
public void testaddHeadNode()
{
linkList.addHeadNode(1);
linkList.addHeadNode(2);
linkList.addHeadNode(3);
linkList.addHeadNode(4);
linkList.printLinkList();
}
public void testdaleteNode()
{
if(linkList.deleteNode(3)==false)
System.out.println(" ");
linkList.printLinkList();
}
public void testUpateNode()
{
if(linkList.updateNode(2, 10)==false)
System.out.println(" ");
linkList.printLinkList();
}
public void testSortLinkList()
{
linkList.SortLinkList();
linkList.printLinkList();
}
public static void main(String[] args) {
MyLinkedList main=new MyLinkedList();
main.testaddHeadNode();
System.out.println("================================");
main.testSortLinkList();
}
}
보충: 거품이 생기는 순서에 대해 서로 인접한 두 사람을 비교한 것이기 때문에 한 번의 순환 검색에서 순서가 바뀌지 않은 것을 발견하면 서열에 이미 순서가 있음을 판단할 수 있다.
결점 삭제에 있어 자바와 c/c++의 가장 큰 차이점은 자바가 수동으로 결점을 삭제하지 않는 방출 공간이다. 이것은 자바가 자동으로 쓰레기를 처리하는 메커니즘 gc가 있기 때문이다.
여기서 Java의 GC 처리 메커니즘을 보완합니다.
대상에 대해 어떤 변수도 인용하지 않으면 프로그램에 접근할 수 없기 때문에 스팸 정보라고 볼 수 있고 회수할 수 있으며 한 개 이상의 변수가 대상을 인용하면 그 대상은 회수되지 않는다.그러니까 여기서 왜 내가 수동으로 공간을 놓지 않는지 설명하기 쉬워.
쓰레기 수거는 모두 일정한 알고리즘에 의거하여 진행된 것이다. 다음은 그 중 몇 가지 자주 사용하는 쓰레기 수거 알고리즘을 소개한다.
(1) 참조 계수(Reference Counting Collerctor)
인용 계수는 간단하지만 효율이 낮은 방법으로 그 주요 원리는 다음과 같다. 무더기 안에 모든 대상에 대해 계수기가 있다.대상이 인용될 때 인용 계수기 +1;인용이 비어 있거나 작용역을 떠날 때 인용 계수 -1은 서로 인용하는 문제를 해결할 수 없기 때문에 JVM은 이 알고리즘을 사용하지 않았다
(2) 추적 회수 알고리즘(Tracing Collector)
추적 회수 알고리즘은 JVM이 유지하는 대상 인용도를 이용하여 루트 노드부터 대상의 응용도를 옮겨다니며 옮겨다니는 대상을 표시한다. 옮겨다니기가 끝난 후에 표시되지 않은 대상은 현재 사용되지 않는 대상이고 회수할 수 있다.
(3) 압축 회수 알고리즘(Compacting Collector)
압축 회수 알고리즘의 사고방식은 다음과 같다. 더미에서 활동하는 대상을 더미의 한쪽으로 이동하면 더미의 다른 한쪽에 매우 큰 빈 구간을 남기고 더미의 조각을 처리하는 것과 같다.이런 방법은 조각을 쌓는 작업을 크게 해소할 수 있지만 매번 처리할 때마다 성능의 손실을 가져온다.
(4) 복제 재활용 알고리즘(Coping Collector)
복제 회수 알고리즘의 사고방식: 두 개의 크기가 같은 구역으로 나뉘어 언제든지 그 중 한 구역만 사용되고 이 구역이 소모될 때까지 쓰레기 회수 기간은 프로그램의 실행을 중단하며 반복적인 방식으로 모든 활동의 대상을 다른 구역으로 복제한다. 복제하는 과정에서 이들은 서로 바짝 붙어 배치되어 메모리 파편을 없앨 수 있다.복제 과정이 끝난 후에 프로그램은 계속해서 실행될 것이다. 이 구역이 사용된 것을 알고 위의 방법으로 쓰레기 회수를 계속할 것이다.
(5) 세대별 회수 알고리즘(Generational Collector)
복제 회수 알고리즘의 주요 단점은 다음과 같다. 매번 알고리즘이 실행될 때마다 활동 상태에서 나온 모든 대상이 복제되어야 하기 때문에 효율이 매우 낮다.프로그램은 생명주기의 길이와 길이의 구분이 있기 때문에 대부분이 생명주기가 비교적 짧기 때문에 이 특징에 따라 알고리즘을 최적화할 수 있다.세대별 회수 알고리즘의 주요 사고방식은 다음과 같다. 더미를 두 개 또는 여러 개의 더미로 나누고 한 개의 더미는 한 세대로 간주된다.알고리즘은 운행 과정에서'어린'대상을 우선적으로 수집하고 만약에 한 대상이 여러 번 수집을 거쳐도'생존'하면 이 대상을 높은 등급의 무더기로 옮겨 스캐닝 횟수를 줄일 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.