데이터 구조 - JS 선형 표 조작 실현

32410 단어 데이터 구조선형 표JS 구현 순서 표JS 단일 체인 테이블 구현
순차 저장, 체인 저장.
선형 표 는 임의의 위치 에 데 이 터 를 삽입 하고 삭제 할 수 있다.
개념 정의
첫 번 째 와 마지막 요 소 를 제외 하고 모든 데 이 터 는 전구 데이터 요소 와 후계 데이터 요소 만 있 습 니 다.
동작:
  • List (len) 초기 화;
  • 현재 선형 표 요소 의 개 수 를 되 돌려 줍 니 다.
  • 데이터 요소 삽입 Insert (i, val): 선형 표 List 의 제 i 위치 에 데이터 삽입 val.
  • 데이터 요소 Delete (i): 선형 표 List 의 제 i 요 소 를 삭제 합 니 다.
  • 데이터 요소 Get (i, x): 선형 표 List 의 제 i 각 요 소 를 취한 다.

    • 순서 표
    설명:
  • 최대 저장 소 len 를 지정 합 니 다.
  • 현재 데이터 요소 의 개 수 를 기록 합 니 다 size.
  • 데 이 터 를 삽입 할 때 순서대로 삽입 합 니 다. 즉, 0<=i<=size.시간 복잡 도 O (n)
  • 데이터 삭제 시 불가 i<0 || i>size-1;시간 복잡 도 O (n)
  • 값 을 추출 할 때 무효 한 하 표 값, 즉 0<=i
    • 을 제거 할 수 없습니다.
    코드 구현:
    function queueList(len){
    //     
    this.MaxSize = len;
    //            
    this.list = new Array(len);
    //         
    this.size = 0;
}
queueList.prototype = {
    getLen(){
        return this.size;
    },
    insert(i,val){
        //     
        if(this.size>=this.MaxSize){
            console.error("     ，    !");
            return false;
        }else if(i<0 || i>this.size){
            console.error("  i   !");
            return false;
        }else{
            //       ， >i        。
            for(let j=this.size;j>i;j--){
                this.list[j] = this.list[j-1];
            }
            this.list[i] = val;
            this.size++;
            return true;
        }
    },
    delete(i){
        //     
        if(this.size<=0){
            console.error("        !");
            return false;
        }else if(i<0 || i>this.size-1){
            console.error("  i   !");
            return false;
        }else{
            for(let j=i+1;j<this.size - 1;j++){
                this.list[j -1] = this.list[j];
            }
            this.size--;
            return true;
        }
    },
    getVal(i){
        //            
        if(i<0 || i>this.size-1){
            console.error("  i   !");
            return false;
        }
        return this.list[i];
    }
}

    체인 메모리
    데이터 요 소 를 저장 하 는 노드 를 포인터 영역 으로 체인 으로 구성 합 니 다.
    단일 체인 테이블 저장 소
    링크 를 구성 하 는 노드 는 직접 후계 노드 를 가리 키 는 포인터 필드 만 있 습 니 다.설명:
  • 기본 헤드 노드 head 를 키 0 로 정의 하고 헤드 노드 는 데 이 터 를 저장 하지 않 습 니 다.가리 키 는 다음 노드 는 데이터 0 입 니 다.
  • 각 노드 의 데이터 대상 
    {
	val:null,      //    
	next:null,     //       
}
  • 데이터 키 Symbol 를 사용 하여 키 의 유일 성 을 확보 했다.
  • 데이터 삽입 과 삭 제 는 모두 찾 아서 처리 해 야 하기 때문에 시간 복잡 도 는 O (n) 이다.
    • var MyLinkedList = function() {
    //             ，     
    //      ‘0’  head
    this.list = {
        '0':{
            next:null
        }
    };
    //     
    this.attr = {
        val:null,
        next:null
    }
};
MyLinkedList.prototype.get = function(index) {
    let head = this.list["0"];
    let j = -1;
    //    
    while(head && head.next!==null && j<index){
        head = this.list[head.next];
        j++;
    }
    if(j!=index){
       console.error("       !");
        return -1;
       }
    return head.val;
};
MyLinkedList.prototype.addAtHead = function(val) {
    let obj = Object.assign({},this.attr);
    //  
    let head = this.list["0"];
    obj.val = val;
    let time = Symbol();
    if(head.next!=null){
        obj.next = head.next
    }
    head.next = time;
    this.list[time] = obj;
    return true;
};
MyLinkedList.prototype.addAtTail = function(val) {
    let obj = Object.assign({},this.attr);
    // 
    obj.val = val;
    let tail = this.list["0"];
    while(tail.next!==null){
        tail = this.list[tail.next];
    }
    let time = Symbol();
    tail.next = time;
    this.list[time] = obj;
    return true;
};
MyLinkedList.prototype.addAtIndex = function(index, val) {
    let obj = Object.assign({},this.attr);
    //  /          
    let head = this.list["0"];
    //   index      
    let j = -1;
    while(head.next!==null && j<index-1){
        head = this.list[head.next];
        j++;
    }
    if(j!==index-1){
       console.error("        !");
        return -1;
    }
    obj.val = val;
    let time = Symbol();
    obj.next = head.next;
    head.next = time;
    this.list[time] = obj;
    return true;
};
MyLinkedList.prototype.deleteAtIndex = function(index) {
    let head = this.list["0"];
    let j = -1;
    while(head.next!==null &&this.list[head.next].next!=null && j<index-1){
          head = this.list[head.next];
            j++; 
    }
    if(j!==index-1){
       console.error("        !");
        return false;
    }
    //     
    let id = head.next;
    head.next = this.list[head.next].next;
    //     
    Reflect.deleteProperty(this.list,id);
    return true;
};

    순환 목록
    단일 체인 테이블 의 마지막 노드 next 는 헤드 노드 head 를 가리 키 고, 단일 체인 테이블 의 예시 0 키 값 을 가리킨다.구별 설명:
  • 초기 화 시 두 결점 지향 
    '0':{
	next:'0'
}
  • 다른 함수 비교 에서.head.next!=null 에서 head.next!='0' 로 변경;

    • 양 방향 링크
    차이 점 과 단일 체인 표: 각 노드 에 전구 지침 이 있 고 이전 노드 를 가리킨다.순환 과 비 순환 양 방향 링크 로 나 뉜 다.설명:
  • 링크 헤드 노드 변경 
    '0'{
	prior:'0',
	next:'0'
}
//       
{
	prior:null,
	val:null,
	next:null
}
  • 그 중의 데이터 조작 은 전구 노드, 후 구 노드 의 앞 지침 과 뒤 지침 의 방향 을 여러 번 교환 하 는 것 과 구별 된다.
    • 간단 한 이 진 트 리 의 이해 와 실현
    다중 스레드 단순 응용 장면

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage