단일 체인 시트 설명 (자바 언어 설명)

단일 체인 표 는 후계 노드 를 가리 키 는 지침 을 통 해 그의 노드 를 하나의 체인 으로 연결 하 는 것 이다.선형 표 의 첫 번 째 데이터 요소 의 저장 주 소 를 선형 표 의 헤드 포인터 라 고 하 는데 하나의 단일 체인 표 는 하나의 헤드 포인터 로 유일 하 게 표 시 됩 니 다.단일 체인 표 는 보통 두 가지 표현 형식 이 있 는데 하 나 는 앞장 서 는 노드 의 단일 체인 표 이 고 다른 하 나 는 앞장 서지 않 는 노드 의 단일 체인 표 이다. 다음 에 우리 가 단일 체인 표 에 대한 묘 사 는 앞장 서 는 노드 의 단일 체인 표 이다.먼저 노드 클래스 가 필요 합 니 다. 코드 는 다음 과 같 습 니 다.

public class Node {
	public Object data;//     
	public Node next;//       
	public Node() {
		this(null,null);
	}
	public Node(Object data) {
		this(data,null);
	}
	public Node(Object data,Node next) {
		this.data = data;
		this.next = next;
	}
}

그 다음 에 단일 체인 표를 설명 하려 면 먼저 헤드 포인터 로 표 시 를 해 야 한다. 초기 화 를 할 때 헤드 포인터 에 대해 초기 화 를 하고 데 이 터 를 가리 키 며 후계 노드 는 빈 노드 이 고 이 노드 는 헤드 노드 이다.그리고 기본 적 인 기능 을 실현 합 니 다. 코드 는 다음 과 같 습 니 다.

import java.util.Scanner;

public class LinkList {
	public Node head;//       
	public LinkList() {
		head = new Node();
	}
	public LinkList(int n,boolean Order) throws Exception {//       n    
		this();
		if(Order) {
			create1(n);
		} else {
			create2(n);
		}
	}
	//   
	private void create1(int n) throws Exception {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		System.out.println("   "+n+"   ");
		for(int i = 0; i < n; i++) {
			Object sc = input.next();
			insert(length(),sc);
		}
	}
	//   
	private void create2(int n) throws Exception {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		System.out.println("   "+n+"   ");
		for(int i = 0; i < n; i++) {
			Object sc = input.next();
			insert(0,sc);
		}
	}
	//       
	public void clear() {
		// TODO Auto-generated method stub
		head.data = null;
		head.next = null;
	}
	//      
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return head.next == null;
	}
	//          
	public int length() {
		// TODO Auto-generated method stub
		Node p = head.next;
		int length = 0;
		while(p != null) {
			p = p.next;
			++length;
		}
		return length;
	}
	//     i   
	public Object get(int i) throws Exception {
		// TODO Auto-generated method stub
		Node p = head.next;
		int j = 0;
		while(p != null && j < i) {
			p = p.next;
			++j;
		}
		if(j > i || p == null) {
			throw new Exception(" "+i+"      ");
		}
		return p.data;
	}
	// i    x
	public void insert(int i, Object x) throws Exception {
		// TODO Auto-generated method stub
		Node p = head;
		Node s = new Node(x);
		int j = -1;
		while(p != null && j < i-1) {
			p = p.next;
			++j;
		}
		if (j > i-1 || p == null) {
			throw new Exception("       ");
		}
		s.next = p.next;
		p.next = s;

	}
	//     i   
	public void remove(int i) throws Exception {
		// TODO Auto-generated method stub
		Node p = head;
		int j = -1;
		while(p.next != null && j < i-1) {
			p = p.next;
			++j;
		}
		if(p.next == null || j > i - 1) {
			throw new Exception("       ");
		}
		p.next = p.next.next;
 	}
	//x          
	public int indexOf(Object x) throws Exception {
		// TODO Auto-generated method stub
		Node p = head.next;
		int i = 0;
		while(p != null && !p.data.equals(x)) {
			p = p.next;
			++i;
		}
		if(p == null) {
			throw new Exception("    ");
		}
		return i;
	}
	//        
	public void display() {
		// TODO Auto-generated method stub
		Node p = head.next;
		while(p != null) {
			System.out.print(p.data+" ");
			p = p.next;
		}
		System.out.println();
	}
	//       
	public void deleteRepeat() throws Exception {
		Node p = head.next;
		Node q;
		while(p != null) {
			int Order = indexOf(p.data);
			q = p.next;
			while (q != null) {
				if(p.data.equals(q.data)) {
					remove(++Order);
				} else {
					Order++;
				}
				q = q.next;
			}
			p = p.next;
		}
	}
	//           
	public LinkList combineLink(LinkList l1,LinkList l2) {
		Node p = l1.head;
		Node q = l2.head.next;
		while(p.next != null) {
			p = p.next;
		}
		p.next = q;
		return l1;
	}
}

 
삽입 작업 에 대해 i 위치 에 데 이 터 를 삽입 하려 면 그의 전구 노드 i - 1 을 찾 아야 합 니 다.보기, 삭제 작업 도 마찬가지다.
사실 싱글 체인 시트 의 조작 은 바로 지침 에 대한 조작 에 있 습 니 다. 지침 은 하나의 대상 의 주소 입 니 다. 지침 을 통 해 이 대상 을 찾 을 수 있 고 지침 을 이해 하면 체인 시 계 를 쉽게 이해 할 수 있 습 니 다.