数据结构和算法概述

  • 更新时间:
  • 3953人关注
  • 点击下载

这是一个不错的数据结构类学习资源,由从菊月 提供,主要知识点是关于数据结构、算法、数据结构的内容,已被684人关注,同类资源中评分为8.5分。

资源详情相关推荐
  • 大小:4.92 MB
  • 类别:数据结构
  • 格式:PDF
  • 编辑:浦翔飞
  • 热度:106
  • 数据结构与算法
  • 数据结构与算法(第2版)
  • Python数据结构与算法分析
  • 数据结构与算法详解
  • 数据结构及应用算法教程(修订版)
  • 精选笔记:JS中的算法与数据结构之链表(Linked-list)实例详解

    10小时39分钟前回答

    本文实例讲述了JS中的算法与数据结构之链表(Linked-list)。分享给大家供大家参考,具体如下:

    链表(Linked-list)

    前面我们讨论了如何使用栈、队列进行存数数据,他们其实都是列表的一种,底层存储的数据的数据结构都是数组。

    但是数组不总是最佳的数据结构,因为,在很多编程语言中,数组的长度都是固定的,如果数组已被数据填满,再要加入新的元素是非常困难的。而且,对于数组的删除和添加操作,通常需要将数组中的其他元素向前或者向后平移,这些操作也是十分繁琐的。

    然而,JS中数组却不存在上述问题,主要是因为他们被实现了成了对象,但是与其他语言相比(比如C或Java),那么它的效率会低很多。

    这时候,我们可以考虑使用链表(Linked-list) 来替代它,除了对数据的随机访问,链表几乎可以在任何可以使用一维数组的情况中。如果你正巧在使用C或者Java等高级语言,你会发现链表的表现要优于数组很多。

    链表其实有许多的种类:单向链表、双向链表、单向循环链表和双向循环链表,接下来,我们基于对象来实现一个单向链表,因为它的使用最为广泛。

    链表的定义

    首先,要实现链表,我们先搞懂一些链表的基本东西,因为这很重要!

    链表是一组节点组成的集合,每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链。下面我画了一个简单的链接结构图,方便大家理解。

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    链表结构图

    其中,data中保存着数据,next保存着下一个链表的引用。上图中,我们说 data2 跟在 data1 后面,而不是说 data2 是链表中的第二个元素。上图,值得注意的是,我们将链表的尾元素指向了 null 节点,表示链接结束的位置。

    由于链表的起始点的确定比较麻烦,因此很多链表的实现都会在链表的最前面添加一个特殊的节点,称为 头节点,表示链表的头部。进过改造,链表就成了如下的样子:

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    有头节点的链表

    向链表中插入一个节点的效率很高,需要修改它前面的节点(前驱),使其指向新加入的节点,而将新节点指向原来前驱节点指向的节点即可。下面我将用图片演示如何在 data2 节点 后面插入 data4 节点。

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    插入节点

    同样,从链表中删除一个节点,也很简单。只需将待删节点的前驱节点指向待删节点的,同时将待删节点指向null,那么节点就删除成功了。下面我们用图片演示如何从链表中删除 data4 节点。

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    删除节点

    链表的设计

    我们设计链表包含两个类,一个是 Node 类用来表示节点,另一个事 LinkedList 类提供插入节点、删除节点等一些操作。

    Node类

    Node类包含连个属性: element 用来保存节点上的数据,next 用来保存指向下一个节点的链接,具体实现如下:

    //节点
    function Node(element) {
      this.element = element;  //当前节点的元素
      this.next = null;     //下一个节点链接
    }
    
    
    

    LinkedList类

    LinkedList类提供了对链表进行操作的方法,包括插入删除节点,查找给定的值等。值得注意的是,它只有一个属性,那就是使用一个 Node 对象来保存该链表的头节点。

    它的构造函数的实现如下:

    //链表类
    function LList () {
      this.head = new Node( 'head' );   //头节点
      this.find = find;          //查找节点
      this.insert = insert;        //插入节点
      this.remove = remove;        //删除节点
      this.findPrev = findPrev;      //查找前一个节点
      this.display = display;       //显示链表
    }
    
    
    

    head节点的next属性初始化为 null ,当有新元素插入时,next会指向新的元素。

    接下来,我们来看看具体方法的实现。

    insert:向链表插入一个节点

    我们先分析分析insert方法,想要插入一个节点,我们必须明确要在哪个节点的前面或后面插入。我们先来看看,如何在一个已知节点的后面插入一个节点。

    在一个已知节点后插入新节点,我们首先得找到该节点,为此,我们需要一个 find 方法用来遍历链表,查找给定的数据。如果找到,该方法就返回保存该数据的节点。那么,我们先实现 find 方法。

    find:查找给定节点

    //查找给定节点
    
    function find ( item ) {
      var currNode = this.head;
      while ( currNode.element != item ){
        currNode = currNode.next;
      }
      return currNode;
    }
    
    
    

    find 方法同时展示了如何在链表上移动。首先,创建一个新节点,将链表的头节点赋给这个新创建的节点,然后在链表上循环,如果当前节点的 element 属性和我们要找的信息不符,就将当前节点移动到下一个节点,如果查找成功,该方法返回包含该数据的节点;否则,就会返回null。

    一旦找到了节点,我们就可以将新的节点插入到链表中了,将新节点的 next 属性设置为后面节点的 next 属性对应的值,然后设置后面节点的 next 属性指向新的节点,具体实现如下:

    //插入节点
    
    function insert ( newElement , item ) {
      var newNode = new Node( newElement );
      var currNode = this.find( item );
      newNode.next = currNode.next;
      currNode.next = newNode;
    }
    
    
    

    现在我们可以测试我们的链表了。等等,我们先来定义一个 display 方法显示链表的元素,不然我们怎么知道对不对呢?

    display:显示链表

    //显示链表元素
    
    function display () {
      var currNode = this.head;
      while ( !(currNode.next == null) ){
        console.log( currNode.next.element );
        currNode = currNode.next;
      }
    }
    
    
    

    实现原理同上,将头节点赋给一个新的变量,然后循环链表,直到当前节点的 next 属性为 null 时停止循环,我们循环过程中将每个节点的数据打印出来就好了。

    var fruits = new LList();
    
    fruits.insert('Apple' , 'head');
    fruits.insert('Banana' , 'Apple');
    fruits.insert('Pear' , 'Banana');
    
    console.log(fruits.display());    // Apple
                       // Banana
                       // Pear
    
    
    

    remove:从链表中删除一个节点

    从链表中删除节点时,我们先要找个待删除节点的前一个节点,找到后,我们修改它的 next 属性,使其不在指向待删除的节点,而是待删除节点的下一个节点。那么,我们就得需要定义一个 findPrevious 方法遍历链表,检查每一个节点的下一个节点是否存储待删除的数据。如果找到,返回该节点,这样就可以修改它的 next 属性了。 findPrevious 的实现如下:
    
    //查找带删除节点的前一个节点
    
    function findPrev( item ) {
      var currNode = this.head;
      while ( !( currNode.next == null) && ( currNode.next.element != item )){
        currNode = currNode.next;
      }
      return currNode;
    }
    
    
    

    这样,remove 方法的实现也就迎刃而解了

    //删除节点
    
    function remove ( item ) {
      var prevNode = this.findPrev( item );
      if( !( prevNode.next == null ) ){
        prevNode.next = prevNode.next.next;
      }
    }
    
    
    

    我们接着写一段测试程序,测试一下 remove 方法:

    // 接着上面的代码,我们再添加一个水果
    
    fruits.insert('Grape' , 'Pear');
    console.log(fruits.display());   // Apple
                      // Banana
                      // Pear
                      // Grape
    
    // 我们把香蕉吃掉
    
    fruits.remove('Banana');
    console.log(fruits.display());   // Apple
                      // Pear
                      // Grape
    
    
    

    Great!成功了,现在你已经可以实现一个基本的单向链表了。

    双向链表

    尽管从链表的头节点遍历链表很简单,但是反过来,从后向前遍历却不容易。我们可以通过给Node类增加一个previous属性,让其指向前驱节点的链接,这样就形成了双向链表,如下图:

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    双向链表

    此时,向链表插入一个节点就要更改节点的前驱和后继了,但是删除节点的效率提高了,不再需要寻找待删除节点的前驱节点了。

    双向链表的实现

    要实现双向链表,首先需要给 Node 类增加一个 previous 属性:

    //节点类
    
    function Node(element) {
      this.element = element;  //当前节点的元素
      this.next = null;     //下一个节点链接
      this.previous = null;   //上一个节点链接
    }
    
    
    

    双向链表的 insert 方法与单链表相似,但需要设置新节点的 previous 属性,使其指向该节点的前驱,定义如下:

    //插入节点
    function insert ( newElement , item ) {
      var newNode = new Node( newElement );
      var currNode = this.find( item );
      newNode.next = currNode.next;
      newNode.previous = currNode;
      currNode.next = newNode;
    }
    
    
    

    双向链表的删除 remove 方法比单链表效率高,不需要查找前驱节点,只要找出待删除节点,然后将该节点的前驱 next 属性指向待删除节点的后继,设置该节点后继 previous 属性,指向待删除节点的前驱即可。定义如下:

    //删除节点
    
    function remove ( item ) {
      var currNode = this.find ( item );
      if( !( currNode.next == null ) ){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
      }
    }
    
    
    

    还有一些反向显示链表 dispReverse,查找链表最后一个元素 findLast 等方法,相信你已经有了思路,这里我给出一个基本双向链表的完成代码,供大家参考。

     //节点
     
    function Node(element) {
      this.element = element;  //当前节点的元素
      this.next = null;     //下一个节点链接
      this.previous = null;     //上一个节点链接
    }
    
    //链表类
    
    function LList () {
      this.head = new Node( 'head' );
      this.find = find;
      this.findLast = findLast;
      this.insert = insert;
      this.remove = remove;
      this.display = display;
      this.dispReverse = dispReverse;
    }
    
    //查找元素
    
    function find ( item ) {
      var currNode = this.head;
      while ( currNode.element != item ){
        currNode = currNode.next;
      }
      return currNode;
    }
    
    //查找链表中的最后一个元素
    
    function findLast () {
      var currNode = this.head;
      while ( !( currNode.next == null )){
        currNode = currNode.next;
      }
      return currNode;
    }
    
    
    //插入节点
    
    function insert ( newElement , item ) {
      var newNode = new Node( newElement );
      var currNode = this.find( item );
      newNode.next = currNode.next;
      newNode.previous = currNode;
      currNode.next = newNode;
    }
    
    //显示链表元素
    
    function display () {
      var currNode = this.head;
      while ( !(currNode.next == null) ){
        console.debug( currNode.next.element );
        currNode = currNode.next;
      }
    }
    
    //反向显示链表元素
    
    function dispReverse () {
      var currNode = this.findLast();
      while ( !( currNode.previous == null )){
        console.log( currNode.element );
        currNode = currNode.previous;
      }
    }
    
    //删除节点
    
    function remove ( item ) {
      var currNode = this.find ( item );
      if( !( currNode.next == null ) ){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.next = null;
        currNode.previous = null;
      }
    }
    
    var fruits = new LList();
    
    fruits.insert('Apple' , 'head');
    fruits.insert('Banana' , 'Apple');
    fruits.insert('Pear' , 'Banana');
    fruits.insert('Grape' , 'Pear');
    
    console.log( fruits.display() );    // Apple
                        // Banana
                        // Pear
                        // Grape
                        
    console.log( fruits.dispReverse() );  // Grape
                        // Pear
                        // Banana
                        // Apple
    
    
    

    循环链表

    循环链表和单链表相似,节点类型都是一样,唯一的区别是,在创建循环链表的时候,让其头节点的 next 属性执行它本身,即

    head.next = head;
    
    
    

    这种行为会导致链表中每个节点的 next 属性都指向链表的头节点,换句话说,也就是链表的尾节点指向了头节点,形成了一个循环链表,如下图所示:

    JS中的算法与数据结构之链表(Linked-list)实例详解 
    循环链表

    原理相信你已经懂了,循环链表这里就不贴代码了,相信你自己能独立完成!

    至此,我们对链表有了比较深刻的认识,如果想让我们的链表更加健全,我们还可发挥自己的思维,给链表添加比如向前移动几个节点,向后移动几个节点,显示当前节点等方法,大家一起加油!

    感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

    更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

    希望本文所述对大家JavaScript程序设计有所帮助。

    展开阅读
    精选笔记:JavaScript数据结构之二叉树的计数算法示例

    12小时51分钟前回答

    本文实例讲述了JavaScript数据结构之二叉树的计数算法。分享给大家供大家参考,具体如下:

    二叉查找树的一个用途就是记录一组数据集中数据出现的次数。比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一。

    所以要修改Node对象,添加记录成绩出现次数加一,代码如下:

    function Node(data,left,right){
        this.data=data;
        this.left=left;
        this.right=right;
        this.show=show;
        this.count=1;//记录出现的次数
    }
    
    

    当次数增加时,我们需要一个新的方法来更新二叉树中的节点,将出现次数加一,代码如下:

    function update(data){//更新出现的次数
      var grade=this.find(data);
      grade.count++;
      return grade;
    }
    
    

    更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

    希望本文所述对大家JavaScript程序设计有所帮助。

    展开阅读

    相关资源

    • 数据结构与算法分析:C++语言描述

      数据结构与算法分析:C++语言描述

      数据结构与算法分析:C++语言描述(第四版) 是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排

      大小:115.3 MB数据结构

      立即下载
    • 数据结构及算法习题及详细答案

      (1)线性表是(A )o A,一个有限序列,可以为空 C. 一个无限序列,可以为空 B,一个有限序列,不能为空 D, 一个无限序列,不能为空 (2)关于线性表,下列说法中正确的是(D )。 A.线性表中的每个元素都有一个直接前驱和一个直接后继。 B,线性表中的数据元素可以具有不同的数据类型。 C.线性表中的数据元素类型是确定的。 D,线性表中任意一对相邻的数据元素之间存在序偶关系。

      大小:273 KB数据结构

      立即下载
    • 算法竞赛宝典(第三部):基础数据结构

      算法竞赛宝典(第三部):基础数据结构

      大小:26133 MB M算法

      立即下载
    • 数据结构与算法分析(C++版/第二版)

      数据结构与算法分析(C++版/第二版)

      本书采用程序员最爱用的面向对象C+ +语言来描述数据结构和算法,并把数据结构原理和算法分析技术有机地结合在一起,系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术,并介绍了可计算性理论的一般知识。本版的重要改进在于引入了参数化的模板,从而提高了算法中数据类型的通用性,支持高效的代码重用。

      大小:225 KB数据结构

      立即下载
    • 数据结构 算法与应用 C++语言描述

      数据结构 算法与应用 C++语言描述

      《数据结构、算法与应用:C++语言描述》在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是,《数据结构、算法与应用:C++语言描述》不仅仅介绍了理论知识,还提供了50多个应用实例及600多道练习题。 目录 译者序 前言 第一部分 预备知识 第1章 C++程序设计

      大小:259 KB数据结构

      立即下载
    • 数据结构与算法:Python语言实现

      数据结构与算法:Python语言实现

      这书选用Python語言详细介绍数据结构和优化算法,包含其设计构思、剖析和执行。这书源码简约、确立,面向对象编程的见解围绕自始至终,根据承继*底限地提升编码器重,一起突显不一样抽

      大小:32.9 MB数据结构算法

      立即下载

    学习笔记

    9小时24分钟前回答

    Python cookbook(数据结构与算法)将多个映射合并为单个映射的方法

    本文实例讲述了Python将多个映射合并为单个映射的方法。分享给大家供大家参考,具体如下: 问题: 在逻辑上将多个字典或映射合并为一个单独的映射结构,以此执行某些特定的操作,比如查找值或者检查键是否存在 解决方案: 利用 collections 模块中的 ChainMap 类 ChainMap 可接受多个映射然后在逻辑上使它们表现为一个单独的映射结构。这些映射在字面上并不会合并在一起。相反, ChainMap 只是简单地维护一个记录底层映射关系的列表,然后重定义常见的字典操作来扫描这个列表。 # example.py## Example of combining dicts into a chainmapa = {'x': 1, 'z': 3 }b = {'y': 2, 'z': 4 }# (a) Simple example of combiningfrom collections import Chain……

    3小时6分钟前回答

    数据结构与算法:单向链表实现与封装

    概述 单向链表分为单向有头链表和单线无头链表,本文针对单向有头链表使用C语言来实现并进行封装。 实现 list_head.h文件 #ifndef _LIST_H_#define _LIST_H_typedef int datatype;#define SUCC#define MALLOC_FAIL 1#define NOHEADNODE 2#define INDEXFAIL 3#define LIST_EMPTY 4#define LIST_NOEMPTY 5#define FAIL 10typedef struct List_Node { datatype data; struct List_Node* pNext;}list;list*list_create();int list_insert_at(list* pHead, int i, datatype* pData);int list_order_insert(list* pHead, datatype* pData);int list_delete_at(list* pHead, int index);int list_delete(list* pHead, datatype* pData);int list_isempty(list* pHead);void list_display(list* pHead);void list_destory(list* pHead);#endif // !_LIST_H_ list_head.c文件 /************************************……