「干货」数据结构第一讲

  • 日期:08-13
  • 点击:(1435)


  为什么要学习数据结构

  1.语言是相通的

  人们常说,编程语言是相通的,掌握一门,其他语言很容易就能掌握。

件判断这些概念,这似乎能支持上面的观点,但是每门编程语言都有自己的使用范围,都有自己擅长的事情,即便是有了 node.js 这中能够一统前后端的语言,也总有他不能胜任的工作,比如机器学习。像python 这样近乎万能的语言,也会在高性能计算的时候无能为力。

  其实,真正想通的不是语言,而是数据结构与算法。数据结构和算法是脱离编程语言而存在的,不同的语言有不同的实现版本,但是内在逻辑却不会发生变化,所提现的编程思想不会有变化

  2.业务场景

  a、前端通过 websocket 获取数据,数据是具体的坐标,当获取到坐标的时候,在前端的地图上显示一个光圈。但是,后端不定期发送,可能一次推送几个,也可能几秒钟才推送一个,当数据特别频繁的时候,坐标都在地图上显示,地图会非常乱,所以对于前端来说要做一个限制,前端同一个时刻最多显示10个坐标,新坐标需要把最早的坐标挤掉,每个坐标最多显示5秒钟。

  是否可以通过队列的方式,每一个节点都包括,后台传过来的数据坐标和当前的时间,当超过10个坐标的时候,挤掉头部出队列,前端做事件循环每一秒钟,检查一下头部是否超过5s,如果超过,头部出队列。

  b、H5页面翻页场景业务,

  可以添加页面,删除页面,移动页面,翻看页面。我猜想大多数情况应该是对数组进行操作,通过arr,角标index和for循环来渲染页面的.

  换个思路:

  是否可以用双向链表的方式完成这些操作,每一个页节点,包括本页的数据,pre前一页的指向和next后一页的指向,当添加操作的时候其实是在尾节点next指向新页,删除页面的时候其实是把前一页的next指向删除页的next,移动页面其实就是先完成删除页面,在完成添加页面操作,向后翻看页面的时候,就是一直在操作next,向前翻看其实就是一直操作pre。

数据,在存入的时候先读取数据在update数据(这样会增加服务器压力)

  3.学习数据结构的目标

  a) 提高程序设计能力

  b) 提高算法能力,数据结构的精髓在于总结提炼了许多储存管理和使用数据的模式,这些模式的背后是最精华的编程思想,这些思想的领悟会需要一些时间,不是学习了几种数据结构就能在工作中大展伸手,但是学会了数据结构,对自身能力的提升是很有帮助的

  在没有完全参悟这些编程思想和管理方式的时候,我们只需要学习具体的工具和方法。

  4.数据结构和算法都有哪些

  栈 -- 羽毛球、羊肉串

  队列 -- 排队登机,优先队列 -- vip用户、军人、老人、排队优先进入

  链表 -- 猴子捞月,包括单向链表、双向链表

  集合 -- es6中的Set

  字典 -- es6中的Map

  散列集 -- 曾经讨论过,因为数组的长度不固定,角标用哈希表示、循环尽量采取foreach自动过滤调empty的位置输出

  图 -- 迷宫 :深度搜索和广度搜索,这个请参考

  树 -- 学习小组讨论过一个问题,可以用二叉树来解决

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶

  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

  注意:给定 n 是一个正整数。

  示例 1:

  输入: 2

  输出: 2

  解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶

  2. 2 阶

  示例 2:

  输入: 3

  输出: 3

  解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶

  2. 1 阶 + 2 阶

  3. 2 阶 + 1 阶

  function Node(data) {

  // 二叉树节点

  this.data=data;

  this.left=null;

  this.right=null;

  }

  function method(n) {

  let head=new Node(null);

  let num=0;

  function A(node, n, num) {

  if (n return 0;

  } else if (n - node.data==0) {

  return 1;

  }

  n -=node.data;

  if (n==1) {

  node.left=new Node(1);

  return num + A(node.left, n);

  } else if (n >=2) {

  node.left=new Node(1);

  node.right=new Node(2);

  return num + A(node.left, n, num) + A(node.right, n, num);

  }

  }

  if (n==1) {

  head.left=new Node(1);

  return A(head.left, n, num);

  } else if (n >=2) {

  head.left=new Node(1);

  head.right=new Node(2);

  return A(head.left, n, num) + A(head.right, n, num);

  }

  }

  这样在打印head的情况下,会把所有方式的轨迹都打印出来,如果不考虑轨迹路径,建议使用斐波那契数列

  b) 冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索

  5、学习数据结构需要知道哪些知识

  a) 数组

  b) Class 定义类的方法

  数据结构之栈

  1、栈的定义

  栈是一种特殊的线性表,仅能够在栈顶进行操作,有着先进后出(后进先出)的特性,下面展示了栈的工作特点

  t01c7f39af6d5775704.jpg

  2.栈的实现

  从数据储存的角度看,实现栈可以用数组来实现,注意:仅可以用数组实现吗?

  a、栈的几个方法:

  *push 添加一个元素到栈顶

  *pop 弹出栈顶元素

  *top 返回栈顶元素

  *isEmpty 判断栈是否为空

  *size 返回栈里元素的个数

  *clear 清空栈

  3、代码实现

  // push pop top isEmpty size clear 用数组完成

  function Stack() {

  var items=[];

  var min=null;

  // 添加一个元素到栈顶

  this.push=function(item) {

  items.push(item);

  };

  // 弹出栈顶元素

  this.pop=function() {

  return items.pop();

  };

  // 返回栈顶元素,不弹出

  this.top=function() {

  return items[items.length - 1];

  };

  // 判断栈是否为空

  this.isEmpty=function() {

  return items.length==0;

  };

  // 返回栈里元素的个数

  this.size=function() {

  return items.length;

  };

  // 清空栈,不推荐使用items.length=0,学术派讨论,

  // 说法一,赋值更快,length为0影响其他已用,内存

  this.clear=function() {

  items=[];

  };

  }

  4、练习题

  判断(abc),)(bcd),(ab(cd)),括号是否合法

  例如:(abc) 合理

  (bcd)( 不合理

  )() 不合理

  function check(str) {

  let len=str.length;

  let stack=new Stack();

  for (let i=0; i if (str[i]==x27;(x27;) {

  stack.push(x27;(x27;);

  } else if (str[i]==x27;)x27;) {

  if (stack.isEmpty()) {

  return false;

  } else {

  stack.pop();

  }

  }

  }

  return stack.isEmpty();

  }

  赠言:每当你怀疑学习数据结构的必要性和作用时,如果你手里只有锤子,那么目光所及之处都是钉子

  作者:易企秀——王明

达到当天最大量

龙8国际娱城手机版