Eddie Chen


A Front-End Web Developer;

A fakegeek studying at Uestc;

A boy who loves the logic and structure of coding;


Resume

Project List

+

福州金玉堂网站

form 2011 - 2012

福州金玉堂企业网站开发

页面重构, jQuery开发, 基于Ajax的在线聊天子系统, 实时期货价格图表生成(基于Ajax&jsonp)

→ View website

+

diandian.com 数个模板开发

+

中国技术供需在线

form 2011 - 2012

中国技术供需在线-教育部全国高校产学研合作公共服务网络平台

负责一期项目后端开发, 数据库设计

基于PHP, CI框架开发

→ View website

+

电子科技大学校工会新版网站

2011

电子科技大学校工会新版网站

负责后台开发(PHP+CI)以及项目管理

→ View website

+

电子科技大学科技处网站

2010

电子科技大学科技处网站

负责部分页面重构

→ View website

Skill

HTML

80%

CSS & CSS3

70%

Javascript

80%

PHP

60%
*skill scores are based on the test provided by Elance.com.

Blog

恶补基础之数据结构学习笔记--线性表篇


前言


之所以叫恶补基础, 是因为一直以来我都以为, 前端开发, 对数据结构&算法 这一块的需求比较低. 或者说..平时根本用不到, 自以为会点js, 会搞定些用户需求就足够了. 中间虽然屡次意识到基础课的重要性, 但是总是念头一闪而过一忙起来又啥都忘了… 直到昨天面试阿里时, 被彻彻底底的鄙视了. 于是下定决心, 从0开始, 从头系统的学一遍数据结构&算法. 补一下离散数学, 操作系统, 计组, 系统结构等基础课程. 总之一句话…今天的一切痛苦, 都来自于以前的自以为是, 出来混总是要还的.

昨天面试的时候问到, 哈希表在内存中是怎么实现的… 虽然后来看了一下书之后发现非常的简单…但是当时的我真的是除了知道哈希表表现出来是个键值对之外…其他一无所知. 由于平时用到的语言,比如js, 比如php, 都直接有hash表的直接实现, 用的过程中也没有去想其原理, 所以可耻的被鄙视了. 最后面试官说, "看来你的基础确实不怎么样, 我们聊到这儿吧." 着实是被打击了.

今天上午拿到了程杰的 <大话数据结构> 这本书, 埋头看了4章, 准备在接下来的几周中, 陆续往下看, 从头学习, 每天发一篇学习笔记, 记录点滴.

这本书中有一句话很经典: "你的数据结构怎么学的?" 希望从此之后不会再有人对我说同样的话.

线性结构

线性结构是4种基本逻辑结构(集合结构, 线性结构, 树形结构, 图形结构) 中最为简单直白的一种结构, 与之相关的数据结构有线性表, 栈, 队列等.

线性表

线性表, 顾名思义, 其逻辑结构是线性的, 是数据结构中最简单最常用的一种结构.

线性表APT

ADT 线性表 (List)

Data
    {a1, a2, a3, a4, …, an}, 除a1外, 每个元素只有一个前驱, 除an外, 每个元素只有一个后驱.

Operation
    InitList()
    ListEmpty()
    ClearList()
    GetElem()
    LocateElem()

    ListInsert()
    ListDelete()
    ListLength()

endADT

线性表实现方式

  • 顺序存储方式
  • 链表存储方式
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表
顺序存储

线性表顺序存储方式采用数组实现.

优点:

  • 随机访问, 访问开销为O(1).
  • 节省空间.

缺点:

  • 增删操作繁琐, 开销O(n).
  • 空间需要预先分配(数组必须开指定长度的, 内容少了浪费空间, 内容多了没法直接动态增加.)

顺序存贮基本为数组操作, 比较简单, 简单记录到这.

链式存储(单链表为例)

单链表在存储方式上比顺序存储有更好的灵活性, 总结优缺点如下:

优点:

  • 动态分配空间
  • 增删操作方便, 已经找到元素的情况下开销O(1)

缺点:

  • 牺牲了空间来换取存储上的灵活性, 需要额外增加后继结点指针.
  • 访问操作繁琐, 需要从头开始一次找next, 访问开销O(n).
链式存储实现

关键代码 in C, 包含插入节点, 删除节点, 获取节点实现.

//  main.c
//  LinkedList
//
//  Created by Eddie Chen on 5/8/13.
//  Copyright (c) 2013 Dreamfly. All rights reserved.

#include <stdio.h>
#include <stdlib.h>

#define YES 1
#define NO 0
typedef int BOOL;
typedef int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node * next;
} Node;



typedef Node * LinkedList;


LinkedList initList()
{
    LinkedList L = (LinkedList)malloc(sizeof(Node));
    L->next = NULL;
    return L;
}

//getNode at index x, index starts from 1
BOOL getNode(LinkedList L, int index, ElemType *e)
{
    int i = 1;
    Node * n;
    n = L->next;
    while (n != NULL && i < index) {
        n = n->next;
        i++;
    }
    if(n == NULL)
        return NO;
    else
    {
        *e = n->data;
        return YES;
    }
}

//insert Node after position x; position = 0 means inseart right after the head node;
BOOL insertNode(LinkedList L, int position, ElemType value)
{
    int i = 0;
    Node * n, * newNode;
    n = L;
    while (i < position) {
        if(n->next == NULL)
            return NO;
        n = n->next;
        ++i;
    }

    newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = n->next;
    n->next = newNode;

    return YES;
}

BOOL deleteNode(LinkedList L, int position)
{
    int i = 1;
    Node * n, * nn;
    n = L;
    nn = L->next;
    while (i < position && nn != NULL) {
        n = nn;
        nn = nn->next;
        i++;
    }
    if(nn == NULL)
        //node not exists
        return NO;
    else
    {
        n->next = nn->next;
        free(nn);
    }
    return YES;
}

int main(int argc, const char * argv[])
{
    return 1;
}

后续双向链表, 循环链表的原理类似, 就懒得再写一遍了. Ps: 循环链表的判断: 判断循环链表的一种思路: (怎么证明地球是圆的? 能绕一圈就是圆的) 让小明和小红按不同的速度往前走(小红比较快), 如果有一天小明和小红相遇了, 那说明链表是循环的.

静态链表

使用数组来模拟单链表实现(不使用指针),是个比较蛋疼的实现, 这里只记优缺点:

优点:

  • 能够用数组实现单链表的功能

缺点:

  • 还是存在动态空间分配问题
  • 数组的随机存取特性不再有效

Date:

About

This is Eddie Chen, a front-end web developer, a member of Dreamfly Studio of UESTC.
Keep in touch:
haozi[a,t]haozi.name


Powered by Eddie Chen.