java 실현 선형표 및 알고리즘

선형 테이블
선형표는 가장 간단하고 자주 사용하는 데이터 구조로 n 개체 데이터 요소(노드)로 구성된 유한한 서열이다.그 중에서 데이터 요소의 개수 n은 표의 길이이고 n이 0일 때 빈 표가 되며 비빈 선형 표는 일반적으로 다음과 같이 기록된다.
(a1,a2,… ,ai-1,ai, ai+1,…,an)
하나.선형표의 순서 저장 및 알고리즘
선형표의 순서 저장은 선형표의 데이터 요소를 논리적 순서에 따라 한 조의 주소가 연속된 저장 단원에 순서대로 저장하는 것을 말한다. 이런 방법으로 저장된 선형표를 순서표라고 한다.
1. 순서표의 구조 정의

public class SeqList { 
 /*  10 */
 private static final int LIST_SIZE = 10; 
 /*  data  */
 private int[] data; 
 /*  ，  */
 private int length; 
}

2. 삽입 연산
순서표의 삽입 연산은 선형 표의 i-1번째 요소와 i번째 요소 사이에 새로운 요소를 삽입하는 것을 가리킨다.순서표 논리적으로 인접한 원소가 물리 구조에서도 인접하기 때문에 그 물리적 저장 관계도 상응하는 변화가 발생해야 한다.i=n+1을 제외하고는 원래 순서표의 i번째 원소에서 시작된 모든 원소를 각각 뒤로 한 위치로 이동해야 합니다.

/**
 *  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. 순서표 역치
먼저 표 길이의 절반을 순환 제어 횟수로 하고 표의 마지막 원소를 순서대로 첫 번째 원소를 교환하고 꼴찌에서 두 번째 원소를 순서대로 두 번째 원소와 교환한다. 이런 식으로 미루어 교환이 끝날 때까지.

/**
 *  
 * @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;
  
}

2.선형표의 체인식 저장 및 알고리즘
체인식 저장 구조는 선형표 데이터 요소를 저장하는 저장 공간이 연속적일 수도 있고 연속적이지 않을 수도 있기 때문에 체인표의 노드는 무작위로 접근할 수 없고 체인식 저장 굵기는 가장 흔히 볼 수 있는 저장 방식 중의 하나이다.
체인식 저장 구조를 사용하여 모든 데이터 요소를 표시할 때 요소 자체의 정보를 저장하는 것 외에 후속 요소의 저장 위치를 표시하는 주소를 저장해야 한다. 이런 저장 방식을 이용하여 표시하는 선형표를 체인표라고 한다.
5. 단일 체인 테이블의 구조 정의

public class LinkList {

 /*   */
 private char data;

 /*   */
 private LinkList next;

}

6. 헤드 삽입법 테이블 작성 알고리즘
플러그인은 빈 테이블부터 데이터를 반복적으로 읽고 새 노드를 생성하며 읽은 데이터를 새 노드의 데이터 필드에 저장한 다음 새 노드를 현재 체인 테이블의 헤더에 삽입하여 끝날 때까지 삽입하는 것이다.

/**
 *  
 * @param chars  
 * @return  
 */
public LinkList createListF(char[] chars) {

 LinkList node;
 LinkList head = null;

 for (char ch : chars) {
  /*   */
  node = new LinkList();
  node.data = ch;

  /*   */
  node.next = head;
  head = node;
 }

 /*   */
 return head;

}

7. 꼬리 삽입법 표 작성 알고리즘
플러그법은 테이블에서 노드의 순서와 입력할 때의 순서가 상반되며, 입력 순서와 일치해야 한다면 플러그법을 사용할 수 있다.

/**
 *  
 * @param chars  
 * @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) {
   /*   */
   head = node;
  } else {
   /*   */
   rear.next = node;
  }
  /*   */
  rear = node;
 }

 /*   */
 return head;
}

이상은 본문의 전체 내용입니다. 여러분의 학습에 도움이 되고 저희를 많이 응원해 주십시오.