자바스크립트 데이터구조_javascript 스킬의 이중연결리스트 삽입정렬 예시에 대한 자세한 설명-JS 튜토리얼-php.cn

집

웹 프론트엔드

JS 튜토리얼

자바스크립트 데이터구조_javascript 스킬의 이중연결리스트 삽입정렬 예시에 대한 자세한 설명

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 16, 2016 pm 03:29 PM

javascript삽입 정렬

이 글의 예시에서는 자바스크립트 데이터 구조에서 이중 연결 리스트 삽입 정렬을 구현하는 방법을 설명합니다. 참고하실 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

배열 저장을 전제로 하는 삽입 정렬 알고리즘은 최악의 경우 삽입할 대상 요소가 삽입될 삽입 지점에 공간을 남기기 위해 이전 요소를 연속적으로 뒤로 이동해야 합니다.

연결된 목록으로 전환할 때 각 노드의 선행 노드 "포인터"에 따라 이렇게 많은 양의 이동을 수행할 필요는 없습니다. 앞으로 삽입 지점을 찾은 후 대상 값이 에서 직접 제거됩니다. 원래 연결 목록을 삭제하면 삽입 지점에서 대상 값이 제거됩니다. 연결 목록을 두 개로 나눈 다음 대상 지점에 다시 연결하면 됩니다.

<!doctype html>
<html>
<head>
  <title>双链表-插入排序</title>
  <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
  //节点类
  var Node = function (pData) {
    this.next = null; //后继“指针”
    this.prev = null; //前驱"指针"
    this.data = pData;
  }
  //单链表(约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始)
  var DbLinkList = function () {
    this.head = new Node(null); //头节点   
    //插入新元素
    this.insert = function (pNodeValue) {
      var newNode = new Node(pNodeValue);
      //如果只有头节点
      if (this.head.next == null) {
        this.head.next = newNode;
        newNode.prev = this.head;
        return;
      }
      //否则遍历找到尾节点
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = newNode;
      newNode.prev = p;
    }
    //获取第n个元素的数据值
    this.getData = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      while (p.next != null && i <= index) {
        p = p.next;
        i += 1;
      }
      return p.data;
    }
    //取尾节点
    this.getTail = function () {
      if (this.head.next == null) {
        return null;
      }
      var p = this.head.next;
      while (p.next != null) {
        p = p.next;
      }
      return p;
    }
    //删除指定位置的元素
    this.removeAt = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      //从头开始遍历，找到index位置的前一个元素
      while (p.next != null && i < index) {
        p = p.next;
        i += 1;
      }
      p.next = p.next.next; //修改index位置前一个元素的后继指针
      p.next.prev = p;
      return p.data; //返回删除元素的值    
    }
    //打印所有元素
    this.print = function () {
      document.write("<br/>");
      if (this.head.next == null) {
        return;
      }
      var p = this.head.next;
      while (p.next != null) {
        document.write(p.data + " ");
        p = p.next;
      }
      document.write(p.data + " "); //最后一个元素，需要单独打印
      document.write("<br/>");
    }
    //从后打印所有元素
    this.printFromBack = function () {
      document.write("该链表共有" + this.size + "个元素，从后向前分别为:<br/>");
      var tail = this.getTail();
      var p = tail;
      if (p == null) {
        return;
      }
      while (p.prev != null) {
        document.write(p.data + " ");
        p = p.prev;
      }
      document.write("<br/>");
    }
    //插入排序
    this.insertSort = function () {
      if (this.head.next == null || this.head.next.next == null) {
        return;
      }
      var p = this.head.next;
      while (true) {
        if (p == null) {
          return;
        }
        var t = p.prev;
        //向前查找p之前的插入点
        while (t.prev != null && t.data > p.data) {
          t = t.prev;
        }
        //如果插入点就是p的前驱节点，不用调整，
        //忽略，直接进入下一轮
        if (t.next == p) {
          p = p.next;
          continue;
        }
        //将p的后续节点先保护起来，以便下一轮循环时确定起始位置
        var x = p.next;
        //将p从链表上摘下
        if (p.next != null) {
          p.next.prev = p.prev;
        }
        p.prev.next = p.next;
        //p插入到t之后
        t.next.prev = p;
        p.next = t.next;
        t.next = p;
        p.prev = t;
        this.print(); //打印输出，调试用  
        //重新将p定位到下一轮循环的"正确"起始节点
        p = x;
      }
    }
  }
  var linkTest = new DbLinkList();
  linkTest.insert(10);
  linkTest.insert(9);
  linkTest.insert(8);
  linkTest.insert(7);
  linkTest.insert(6);
  linkTest.insert(5);
  linkTest.insert(4);
  linkTest.insert(3);
  linkTest.insert(2);
  linkTest.insert(1);
  document.write("--排序前---<br/>")
  linkTest.print();
  linkTest.insertSort();
  document.write("<br/>--排序后---<br/>")
  linkTest.print();
</script>
</html>

실행 결과는 다음과 같습니다.

 --排序前---

10 9 8 7 6 5 4 3 2 1 

9 10 8 7 6 5 4 3 2 1 

8 9 10 7 6 5 4 3 2 1 

7 8 9 10 6 5 4 3 2 1 

6 7 8 9 10 5 4 3 2 1 

5 6 7 8 9 10 4 3 2 1 

4 5 6 7 8 9 10 3 2 1 

3 4 5 6 7 8 9 10 2 1 

2 3 4 5 6 7 8 9 10 1 

1 2 3 4 5 6 7 8 9 10 

--排序后---

1 2 3 4 5 6 7 8 9 10

이 기사가 JavaScript 프로그래밍에 종사하는 모든 사람에게 도움이 되기를 바랍니다.

성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

관련 기사

C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지Apr 14, 2025 am 12:05 AM

C/C에서 JavaScript로 전환하려면 동적 타이핑, 쓰레기 수집 및 비동기 프로그래밍으로 적응해야합니다. 1) C/C는 수동 메모리 관리가 필요한 정적으로 입력 한 언어이며 JavaScript는 동적으로 입력하고 쓰레기 수집이 자동으로 처리됩니다. 2) C/C를 기계 코드로 컴파일 해야하는 반면 JavaScript는 해석 된 언어입니다. 3) JavaScript는 폐쇄, 프로토 타입 체인 및 약속과 같은 개념을 소개하여 유연성과 비동기 프로그래밍 기능을 향상시킵니다.

JavaScript 엔진 : 구현 비교Apr 13, 2025 am 12:05 AM

각각의 엔진의 구현 원리 및 최적화 전략이 다르기 때문에 JavaScript 엔진은 JavaScript 코드를 구문 분석하고 실행할 때 다른 영향을 미칩니다. 1. 어휘 분석 : 소스 코드를 어휘 단위로 변환합니다. 2. 문법 분석 : 추상 구문 트리를 생성합니다. 3. 최적화 및 컴파일 : JIT 컴파일러를 통해 기계 코드를 생성합니다. 4. 실행 : 기계 코드를 실행하십시오. V8 엔진은 즉각적인 컴파일 및 숨겨진 클래스를 통해 최적화하여 Spidermonkey는 유형 추론 시스템을 사용하여 동일한 코드에서 성능이 다른 성능을 제공합니다.

브라우저 너머 : 실제 세계의 JavaScriptApr 12, 2025 am 12:06 AM

실제 세계에서 JavaScript의 응용 프로그램에는 서버 측 프로그래밍, 모바일 애플리케이션 개발 및 사물 인터넷 제어가 포함됩니다. 1. 서버 측 프로그래밍은 Node.js를 통해 실현되며 동시 요청 처리에 적합합니다. 2. 모바일 애플리케이션 개발은 재교육을 통해 수행되며 크로스 플랫폼 배포를 지원합니다. 3. Johnny-Five 라이브러리를 통한 IoT 장치 제어에 사용되며 하드웨어 상호 작용에 적합합니다.

Next.js (백엔드 통합)로 멀티 테넌트 SAAS 애플리케이션 구축Apr 11, 2025 am 08:23 AM

일상적인 기술 도구를 사용하여 기능적 다중 테넌트 SaaS 응용 프로그램 (Edtech 앱)을 구축했으며 동일한 작업을 수행 할 수 있습니다. 먼저, 다중 테넌트 SaaS 응용 프로그램은 무엇입니까? 멀티 테넌트 SAAS 응용 프로그램은 노래에서 여러 고객에게 서비스를 제공 할 수 있습니다.

Next.js (Frontend Integration)를 사용하여 멀티 테넌트 SaaS 응용 프로그램을 구축하는 방법Apr 11, 2025 am 08:22 AM

이 기사에서는 Contrim에 의해 확보 된 백엔드와의 프론트 엔드 통합을 보여 주며 Next.js를 사용하여 기능적인 Edtech SaaS 응용 프로그램을 구축합니다. Frontend는 UI 가시성을 제어하기 위해 사용자 권한을 가져오고 API가 역할 기반을 준수하도록합니다.

JavaScript : 웹 언어의 다양성 탐색Apr 11, 2025 am 12:01 AM

JavaScript는 현대 웹 개발의 핵심 언어이며 다양성과 유연성에 널리 사용됩니다. 1) 프론트 엔드 개발 : DOM 운영 및 최신 프레임 워크 (예 : React, Vue.js, Angular)를 통해 동적 웹 페이지 및 단일 페이지 응용 프로그램을 구축합니다. 2) 서버 측 개발 : Node.js는 비 차단 I/O 모델을 사용하여 높은 동시성 및 실시간 응용 프로그램을 처리합니다. 3) 모바일 및 데스크탑 애플리케이션 개발 : 크로스 플랫폼 개발은 개발 효율을 향상시키기 위해 반응 및 전자를 통해 실현됩니다.

JavaScript의 진화 : 현재 동향과 미래 전망Apr 10, 2025 am 09:33 AM

JavaScript의 최신 트렌드에는 Typescript의 Rise, 현대 프레임 워크 및 라이브러리의 인기 및 WebAssembly의 적용이 포함됩니다. 향후 전망은보다 강력한 유형 시스템, 서버 측 JavaScript 개발, 인공 지능 및 기계 학습의 확장, IoT 및 Edge 컴퓨팅의 잠재력을 포함합니다.

Demystifying JavaScript : 그것이하는 일과 중요한 이유Apr 09, 2025 am 12:07 AM

JavaScript는 현대 웹 개발의 초석이며 주요 기능에는 이벤트 중심 프로그래밍, 동적 컨텐츠 생성 및 비동기 프로그래밍이 포함됩니다. 1) 이벤트 중심 프로그래밍을 사용하면 사용자 작업에 따라 웹 페이지가 동적으로 변경 될 수 있습니다. 2) 동적 컨텐츠 생성을 사용하면 조건에 따라 페이지 컨텐츠를 조정할 수 있습니다. 3) 비동기 프로그래밍은 사용자 인터페이스가 차단되지 않도록합니다. JavaScript는 웹 상호 작용, 단일 페이지 응용 프로그램 및 서버 측 개발에 널리 사용되며 사용자 경험 및 크로스 플랫폼 개발의 유연성을 크게 향상시킵니다.

See all articles