数据驱动型的设计02

本系列从数据结构相关的计算机知识出发,从数据的角度提出一些数据驱动的设计思维模式。

第01期总体介绍数据结构与设计的关系,用数据结构的方式来思考设计,并通过几个案例介绍一些大的思路。

第02期介绍数据结构中的链表结构,并探讨设计中可能的链表数据。

1 何为链表?

1.1 概念

一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的。图示:

来个形象点的图:

1.2 链表有特点呢?

查找某个元素:需要从链表中第一个元素开始,一直找到目标元素的位置。

插入/删除某个元素:只要修改元素中的指针。

2 用代码实现一个链表结构

采用Javascript来实现一个链表结构,加深对链表的理解,Chrome浏览器打开console面板,先实现一个链表的节点。

2.1 节点

此节点保存了数据本身(value的值)及下一个节点的位置(下一个节点),输入:

class LinkedListNode {
 constructor(value,next) {
    this.value = value;
    this.next = next;
 }
}

这里我们需要了解下ES6的class特性,下文的例子定义了一个“类”——Point,可以看到里面有一个constructor方法,这就是构造方法,主要写一些Point对象的属性,例如x和y的坐标值;而传统的方法是通过构造函数,定义并生成新对象,然后通过 prototype 属性向对象添加属性和方法。

class Point {
 constructor(){
    this.x=0;
    this.y=0;    // ...
 }
 toString(){    // ...
 }
 toValue(){    // ...
 }
};
    
    // 等同于

function Point(){
    this.x=0;
    this.y=0;
    //...
};
    
Point.prototype = {
 toString(){},
 toValue(){}
};

2.2 链表的基本结构

主要是有两个属性,head记录的是最开始的节点,tail记录的是结尾的节点。其中由于每个节点都有一个next属性指向下一个节点,所以head记录了整条链表的节点。

class LinkedList{    constructor(){
          this.head = null;    
         this.tail = null;
    }}

初始化一个链表结构:

var ls=new LinkedList();

2.3 添加方法

下面为链表结构的数据添加:增删改查的方法。

添加节点的方法:

append - 在结尾插入节点

prepend - 在开始插入节点

查询节点的方法:

find

删除节点的方法:

delete

2.3.1 prepend方法

添加prepend方法,图示结合代码:

LinkedList.prototype.prepend=function(value) {
    const newNode = new LinkedListNode(value,this.head);
    // 往head添加节点   this.head = newNode; 
    // 如果tail为空,往tail添加此节点
   
    if (!this.tail) { 
         this.tail = newNode;
   }    
         
    return this;  }

实验下prepend方法:

ls.prepend(0);console.log(JSON.stringify(ls,null,2));

打印出来:

{  "head": { 
       "value": 0,
       "next": null
 }, 
   "tail": {
       "value": 0, 
       "next": null
 }
}

继续添加:

ls.prepend(1);
console.log(JSON.stringify(ls,null,2));

结果:

"{
 "head": {
   "value": 1,
   "next": {
     "value": 0,
     "next": null
   }
 },
 "tail": {
   "value": 0,
   "next": null
 }
}"

经过多次实验,会发现,head是个一层层嵌套的结构,通过head可以找到任何一个节点(按顺序),而tail永远是存储的最后一个节点。

2.3.2 append方法

为链表结构添加append方法:

LinkedList.prototype.append=function(value) {
    const newNode = new LinkedListNode(value);
  // 如果head为空,则head设为newNode   if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
        return this;
   }
        
   // 把新的newNode设为tail
   this.tail.next = newNode;
    this.tail = newNode;
    return this;
 }

实验下append方法:

ls.append(10);
console.log(JSON.stringify(ls,null,2));

2.3.3 compare方法

为了实现删除delete,我们得先实现比对两个数值是否相等的功能,相等的话返回0:

LinkedList.prototype.compare=function(a,b){
   
    if (a === b) {
        return 0;
   }
    
    return a < b ? -1 : 1;};

2.3.4 delete方法

根据value值来删除节点,凡是等于目标value的节点都被删除:

LinkedList.prototype.delete=function(value) {
    let deletedNode = null;
    // head节点是否需要被删除   while (this.head && this.compare(this.head.value, value)===0) {
     deletedNode = this.head;
      this.head = this.head.next;
   }
      
      let currentNode = this.head;
      if (currentNode !== null) {      
      // 遍历每一个节点
     while (currentNode.next) {
      if (this.compare(currentNode.next.value, value)===0) {
         deletedNode = currentNode.next;
         currentNode.next = currentNode.next.next;
       } else {
         currentNode = currentNode.next;
       }
     }
   }
        
   // 判断tail节点是否需要删除
   if (this.compare(this.tail.value, value)===0) {
          this.tail = currentNode;
   }    
    
    return deletedNode;
    
 };

2.3.5 find方法

实现一个简单的查找方法,找到一个值等于value的节点,并返回,代码如下:

LinkedList.prototype.find=function(value) {
    let currentNode = this.head;
    
    while (currentNode) {
    
    if (value && this.compare(currentNode.value, value)===0) {
        return currentNode;
     }     currentNode = currentNode.next;
   }
        
    return null; }

2.3.6 toArray方法

链表结构的数据转化为数组数据:

  LinkedList.prototype.toArray=function() {
      const nodes = [];
      let currentNode = this.head;
      while (currentNode) {
         nodes.push(currentNode);
         currentNode = currentNode.next;
       }
      return nodes;
 }

至此,我们对链表结构的数据应该已经理解得比较深刻了。接下来,我们探讨下在设计中,有哪些是可以被链表结构的数据所表示的?

赞赏的方式可以是点广告~

3 设计中的链表结构

思考下设计里,哪些元素/手法是可以被链表结构的数据表示的?我们先了解下链表结构的几种基本类型。

3.1 链表结构的几种基本类型

Singly linked list 这是最简单的链表结构:

Double Linked List 双向链表的结构:

Circular linked list循环链表的结构:

3.2 设计中的链表结构

链表本身的特点是一个节点连接着下一个节点,非常适合描述流程性,有前后关系的数据。

1)用户体验的流线

室内设计中,不同空间游线之间的关系;

展览馆的游线设计;

UX设计中页面的跳转流线;

2)设计思路的解构

景观设计中,一层层的关系,地面铺装,树池花台,乔木灌木,亭廊构架;

平面设计中,背景,主体内容,配色,布局,构图等;

更多跟设计的结合,欢迎留言补充。

参考资料:

https://en.wikipedia.org/wiki/Linked_list

本文分享自微信公众号 - 无界社区mixlab(mix-lab),作者:shadow chi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 哈利波特AR游戏-巫师联盟 深度解析

    今年AR技术的进展,及相关应用值得我们关注。给大家推荐一个AR游戏,应该会超越Pokemon Go。

    mixlab
  • ​用expo,从0到1 轻松学react native

    题图由 小程序 ACELAND 人工智能制作 我们在学习一门语言或新入门一套框架时,往往会被繁琐的配置环境所困扰。 回想我刚接触rn的时候,用的是mac,配...

    mixlab
  • 技能之AR技术入门

    AR真真假假,分不清~ 今天继续技能篇。往期技能文章有兴趣可以查阅: 5个用法,关于Gif。 技能之用iMovie制作预告片 AR跟VR都可以达到真假难辨的目...

    mixlab
  • HMD 回应 Nokia 7 Plus 事件:从未向第三方共享用户数据

    日前有诺基亚手机的非中国用户发现,手机会向域名 http://zzhc.vnet.cn 发送未加密的数据包。数据包含了地理位置、IMEI、SIM 卡号和 MAC...

    周俊辉
  • 开源 | CVPR2020 | 结构化的知识蒸馏算法,有效应用于语义分割、深度估计和目标检测

    论文地址:http://arxiv.org/pdf/1903.04197v5.pdf

    CNNer
  • 全球超150家车企停产的时候,特斯拉还在整AR的幺蛾子?

    (VRPinea5月6日讯)近日,据央媒报道,全球汽车产业正遭遇史上最大规模的危机。全球五大车展的日内瓦车展和底特律车展相继取消。3月,自法拉利跑车宣布停产后,...

    VRPinea
  • nginx0.1.0之event模块初始化源码分析(1)

    nginx模块初始化的流程在下面的代码中,核心模块的初始化,各核心模块首先在create_conf中创建保存配置的数据结构,然后在ngx_conf_parse中...

    theanarkh
  • 用 :key 管理可复用元素

    我们会发现,在点击按钮切换登录方式后,输入框中已有的内容没有被清除,这是为什么呢?

    Chor
  • AI技术三大应用领域:智能医疗、自动驾驶、智慧营销产业发展现状分析

    “So tomorrow, if AI can shape healthcare, it has to work through the regulations...

    SIGAI学习与实践平台
  • Nginx防盗链,Nginx访问控制,Nginx解析php相关配置, Nginx代理

    叶瑾

扫码关注云+社区

领取腾讯云代金券