알고리즘 시작 1 - 데이터 구조 (배열 과 링크)

글 목록

1. 기초 - = = 배열 과 링크 구분 = =

1. 더 자주 사용 하 는 데이터 구조

'창고, 체인 시계, 가방'

1. 창고

2. 대열

3. 가방

1. 기초 - 배열 과 링크 구분

배열 과 링크 의 장단 점

데이터 구조
장점.
결점.
배열
색인 을 통 해 임의의 요소 에 직접 접근 할 수 있 습 니 다.
초기 화 하려 면 원소 의 수 를 알 아야 합 니 다.
체인 테이블
사용 한 공간 크기 와 원소 수량 은 정비례 한다
인용 을 통 해 임의의 요소 에 접근 해 야 합 니 다.

자주 사용 하 는 데이터 구조 에 대한 예

데이터 구조
추상 데이터 형식
데이터 표시
부모 링크 트 리
UnionFind
정형 배열
이분 탐색 트 리
BST
두 개의 링크 를 포함 하 는 결점
문자열
String
배열, 오프셋, 길이
산 목록 (지퍼 법)
SeparateChainingHashST
링크 배열
산 목록 (선형 탐지 법)
LinearProbingHashST
두 개체 배열
그림 의 인접 링크
Graph
Bag 개체 의 배열
단어 찾기 트 리
TrieST
링크 배열 의 결점 포함
단어 찾기 트 리
TST
세 개의 링크 를 포함 하 는 결점
1. 더 자주 사용 하 는 데이터 구조 ， ，
1. 창고

스 택 은 후진 선 출 이 고 보통 하 압 스 택

이 라 고 할 수 있다.

자바 에서 정 의 된 스 택 을 사용 하거나 자신 에 게 맞 는 문 제 를 실현 할 수 있 는 스 택

을 사용 할 수 있 습 니 다.

스 택 은 링크 와 배열 을 통 해 모두 실현 할 수 있 는데 여 기 는 링크 를 통 해 이 루어 진 것 이다

.

package com.basic.example;

import javax.xml.soap.Node;

/**
 * Created by IntelliJ IDEA.
 *
 * @version : 1.0
 * @auther : Firewine
 * @mail ： [email protected]
 * @Program Name: StackExam .java
 * @Create : 2019-02-23-15:22
 * @Description :       
 */
public class StackExam<Item> {
    //  
    private Node first;

    //    
    private int N;

    private class Node{
        //         
        Item item;
        Node next;
    }

    public boolean isEmpty(){return first == null;}
    public int size(){return  N;}
    public void push(Item item){
        //    
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop(){
        //      
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
}

2. 대열

통상 대열 은 선진 선발

자바 에서 Queue 를 통 해 새 대기 열 을 만 들 수 있 습 니 다

다음은 링크 를 통 해 이 루어 진 대열

package com.basic.example;

import javax.xml.soap.Node;

/**
 * Created by IntelliJ IDEA.
 *
 * @version : 1.0
 * @auther : Firewine
 * @mail ： [email protected]
 * @Program Name: QueueExam .java
 * @Create : 2019-02-23-15:29
 * @Description :
 */
public class QueueExam <Item>{

    //          
    private Node first ;

    //            
    private Node last;

    //         
    private int N;

    private class Node{
        //         
        Item item;
        Node next;

    }
    public boolean isEmpty(){return first == null;}
    public int size(){
        return N;
    }

    public void enqueue(Item item){
        Node oldlast = last;
        last.item = item;
        last.next = null;
        if (isEmpty()){
            first = last;
        }else {
            oldlast.next = last;
        }
    }
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if (isEmpty()){
            last =null;
        }
        N--;
        return item;
    }
}

3. 가방

자바 에서 Bag 을 만 들 수 있 습 니 다

가방 은 앞의 두 개 와 다 르 지만,

우선 그 는 그 중에서 요 소 를 삭제 할 수 없다.

가방 의 목적 은 사례 를 수집 하고 수집 한 모든 요 소 를 반복 하 는 데 도움 을 주 는 것 이다

.

중요 한 가방 은 처리 순서 에 중요 하지 않 습 니 다.

다음은 학습 용 가방 구현

package com.basic.example;


import java.util.Iterator;

/**
 * Created by IntelliJ IDEA.
 *
 * @version : 1.0
 * @auther : Firewine
 * @mail ： [email protected]
 * @Program Name: BagExam .java
 * @Create : 2019-02-23-15:37
 * @Description :
 */
public class BagExam<Item>  implements Iterable<Item> {

    //      
    private Node first;

    private class Node{
        Item item;
        Node next;
    }
    public void add(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator1();
    }
    private class ListIterator1 implements Iterator<Item>{
        private Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }
        @Override
        public void remove(){}

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}