新普金娱乐网址


一条祝福短信引发的小程序

【图灵访谈】高德纳:总有一部分东西超越大家的精晓数学

数据结构与算法之线性表数学

  • 二月 06, 2019
  • 数学
  • 没有评论

前言

上一篇《数据结构和算法之时间复杂度和空中复杂度》中牵线了岁月复杂度的概念和宽广的日子复杂度,并分别举例子进行了一一表达。这一篇首要介绍线性表。
线性表属于数据结构中逻辑结构中的线性结构。纪念一下,数据结构分为物理结构和逻辑结构,逻辑结构分为线性结构、几何结构、树形结构和图纸结构四大社团。其中,线性表就属于线性结构。剩余的三大逻辑结构从此会相继介绍。

率先表明一(Wissu)点,本文紧要介绍的是面向对象(OO)的合计,顺便谈下函数式编程,而不是教您怎么着规范地、科学地用java求出函数在少数的导数。

线性表

 

基本概念

线性表(List):由零个或七个数据元素结合的星星点点系列。
注意
1.线性表是一个队列。
2.0个因素结合的线性表是空表。
3.线性表中的第三个因素无后驱,最终一个因素无后继,其余因素有且惟有一个先行者和后继。
4.线性表是有长度的,其长度就是因素个数,且线性表的因素个数是个其余,也就是说,线性表的尺寸是零星的。
如若用数学语言来举行定义,可正如:
若将线性表记为(a1,…,ai-1,ai,ai+1,…an),则表中ai-1当先于ai,ai当先于ai+1,称ai-1是ai的向来后驱元素,ai+1是ai的平昔后继元素。

线性表的定义

一、引子

 

def d(f) :
    def calc(x) :
        dx = 0.000001  # 表示无穷小的Δx
        return (f(x+dx) - f(x)) / dx  # 计算斜率。注意,此处引用了外层作用域的变量 f
    return calc  # 此处用函数作为返回值(也就是函数 f 的导数)
# 计算二次函数 f(x) = x2 + x + 1的导数
f = lambda x : x**2 + x + 1  # 先把二次函数用代码表达出来
f1 = d(f)# 这个f1 就是 f 的一阶导数啦。注意,导数依然是个函数
# 计算x=3的斜率
f1(3)
# 二阶导数
f2 = d(f1)

先是,间接上一段python代码,请我们先分析下方面代码是用什么措施求导的。请不要被那段代码吓到,你无需纠结它的语法,只要精晓它的求导思路。

上述代码引用自《何以俺推荐 Python[4]:作为函数式编程语言的
Python
》,这篇博客是促使自己写篇作品的紧要原因。

博主说“如若不用 FP,改用 OOP,上述须要该怎么落成?俺觉得吧,用 OOP
来求导,那代码写起来多半是又丑又臭。”

本人将信将疑,于是就用面向对象的java试了试,最后也没多少代码。倘若用java8或未来版本,代码更少。

请我们想想一个标题,如何用面向对象的思绪改写这几个程序。请先好好想想,尝试编个程序再持续往下看。

设想到看到这几个标题进来的同桌大多是学过java的,上边我用java,用面向对象的笔触一步步解析这一个难题。

 

线性表基本操作

InitList(L): 初步化操作,建立一个空的线性表L。
ListEmpty(L):
判断线性表是不是为空表,若线性表为空,重临true,否则重临false。
ClearList(
L): 将线性表清空。 GetElem(L,i,e):
将线性表L中的第i个岗位元素值重临给e。
LocateElem(L,e):
在线性表L中寻觅与给定值e相等的元素,倘诺搜索成功,重返该因素在表中序号表示成功;否则,重临0表示战败。
ListInsert(
L,i,e): 在线性表L中第i个职位插入新元素e。
ListDelete(L,i,e): 删除线性表L中第i个岗位元素,并用e再次回到其值。
ListLength(L): 重返线性表L的要素个数。

对于不一样的施用,线性表的基本操作是例外的,上述操作是最基本的。
对于实际难题中关系的有关线性表的更扑朔迷离操作,完全可以用那几个基本操作的重组来贯彻。

二、求导

 

作品开端我已近申明过了,本文不是来谈谈数学的,求导只是我用来表明面向对象的一个例子。

设若您早就忘了起头那段代码的求导思路,请回头再看看,看看用python是怎么着求导的。

深信您倘诺听说过求导,肯定一眼就阅览初阶那段代码是用导数概念求导的。

数学 1

代码中只是将无穷小Δx粗略地算做一个较小的值0.000001。

 

三种分裂的线性表

俺们通晓,数据结构分为逻辑结构和大体构造,逻辑结构分为集合结构、线性结构、树形结构和图纸结构四大类。物理结构分为顺序存储结构和链式存储结构。我在前面写的《数据结构和算法》中早已介绍过。
线性表是线性结构的一种,那么线性表当然也有物理结构,也就是说,线性表有二种,分别是各类结构的线性表(叫做顺序表)和链式结构的线性表(叫做链表)。

三、最初的想法

 

//自定义函数
public class Function {
    //函数:f(x) = 3x^3 + 2x^2 + x + 1
    public double f(double x) {
        return 3 * x * x * x + 2 * x * x + x + 1;
    }
}

//一元函数导函数
public class DerivedFunction {
    //表示无穷小的Δx
    private static final double DELTA_X = 0.000001;
    //待求导的函数
    private Function function;

    public DerivedFunction(Function function) {
        this.function = function;
    }

    /**
     * 获取function在点x处的导数
     * @param x 待求导的点
     * @return 导数
     */
    public double get(double x) {
        return (function.f(x + DELTA_X) - function.f(x)) / DELTA_X;
    }
}

public class Main {
    public static void main(String[] args) {
        //一阶导函数
        DerivedFunction derivative = new DerivedFunction(new Function());
        //打印函数在x=2处的一阶导数
        System.out.println(derivative.get(2));
    }
}

先声澳优(Ausnutria Hyproca)点,考虑到博客篇幅,我利用了不规范的代码注释,希望我们不用被自己误导。

自身想只要大家可以考虑了,应该至少会想到那步吧。代码我就不表达了,我只是用java改写了小说先河的那段python代码,做了一个大约的翻译工作。再请大家着想下以上代码的题材。

刚初始,我思考那几个题材想开的是建一个名为Function的类,类中有一个名为f的方式。但考虑到要每回必要新的函数导数时就得改变那些f方法的兑现,明显不便宜增加,那违背了开闭原则

估计有的同学没听过那些词,我就解释下:”对象(类,模块,函数等)应对扩展开放,但对修改封闭“。

于是乎我就没继续写下去,但为了让我们直观的感想到这一个想法,我写那篇博客时就贯彻了瞬间这么些想法。

请大家想想一下怎么样重构代码以缓解扩充性难题。

 

1.顺序存储结构的线性表

顺序表是指顺序存储结构的线性表,指的是用一段地址接二连三的存储单元依次存储线性表的多少元素。
顺序表表现在物理内存中,也就是大体上的囤积方式,事实上就是在内存中找个开头地址,然后通过占位的款型,把自然的内存空间给占了,然后把相同数据类型的数量元素依次放在这块空地中。注意,那块物理内存的地址空间是一而再的。

个例子,比如C语言中的基本变量的积存就是接连的囤积在内存中的,比如声圣元(Synutra)个整数i,在64位系统中整数i在内存中占8字节,那么系统就会在内存中为那些整型变量分配一个尺寸为8个字节的接连的地点空间,然后把那些i的二进制格局从高地址向低地址存储,长度相差时候,最高位用0补齐。

四、早先的想法

 

估量学过面向对象的同学会想到把Function类改成接口或抽象类,将来每一遍添加新的函数时只要重写这么些接口或抽象类中的f方法,那就是面向接口编程,符合借助于反转原则,下边的代码就是如此做的。

再声贝因美(Beingmate)点,考虑到篇幅的题材,前面的代码我会省去与前边代码重复的笺注,有不了解的地方还请看看上一个设法中的代码。

//一元函数
public interface Function {
    double f(double x);
}

//自定义的函数
public class MyFunction implements Function {
    @Override
    public double f(double x) {
        return 3 * x * x * x + 2 * x * x + x + 1;
    }
}

public class DerivedFunction {
    private static final double DELTA_X = 0.000001;
    private Function function;

    public DerivedFunction(Function function) {
        this.function = function;
    }

    public double get(double x) {
        return (function.f(x + DELTA_X) - function.f(x)) / DELTA_X;
    }
}

public class Main {
    public static void main(String[] args) {
        //一阶导函数:f'(x) = 9x^2 + 4x + 1
        DerivedFunction derivative = new DerivedFunction(new MyFunction());
        System.out.println(derivative.get(2));
    }
}

自家想认真看的同窗可能会意识一个难点,我的翻译做的还不成功,开首那段python代码还能轻松地求出二阶导函数(导数的导数),而我的代码却至极。

实质上只要稍加修改上述代码的一个地点就可以轻松落成求二阶导,请再想想片刻。

 

顺序表的协会体定义

#define MAXSIZE 20  // 顺序表的最大存储容量
typedef int ElemType; // 顺序表存储的数据类型 
typedef struct
{ 
    ElemType data[MAXSIZE]; // 用数组表示顺序表 
    int length; // 线性表当前长度
} SqList;

通过上边用结构体定义顺序表,大家得以看到顺序表的卷入需求四个特性:
1.储存空间的序曲地点。数组data的积存地点就是线性表存储空间的积存地点
2.线性表的最大存储容量。数主管度MAXSIZE
3.线性表的脚下长度。length
留神:数组的长短与线性表的当下长度是不平等的。数组的尺寸是存放线性表的储存空间的总长度,一般开首化后不变。而线性表的方今长度是线性表中元素的个数,是会变动的。

五、后来的想法

 

当自己写出位置的代码时,我感觉到完全可以矢口否认“用 OOP
来求导,那代码写起来多半是又丑又臭”的意见。但还不可能求二阶导,我有点不甘心。

于是乎我就动笔,列了一晃用定义求一阶导和求二阶导的架势,想了想三个姿态的界别与联系,突然想到导函数也是函数。

DerivedFunction的get方法和Function的f方法的参数和重临值一样,DerivedFunction可以兑现Function接口,于是发出了下边的代码。

public interface Function {
    double f(double x);
}

public class DerivedFunction implements Function {
    private static final double DELTA_X = 0.000001;
    private Function function;

    public DerivedFunction(Function function) {
        this.function = function;
    }

    @Override
    public double f(double x) {
        return (function.f(x + DELTA_X) - function.f(x)) / DELTA_X;
    }
}

public class Main {
    public static void main(String[] args) {
        Function f1 = new DerivedFunction(new Function() {
            @Override
            public double f(double x) {
                return 3 * x * x * x + 2 * x * x + x + 1;
            }
        });
        System.out.println(f1.f(2));
        //二阶导函数:f''(x) = 18x + 4
        Function f2 = new DerivedFunction(f1);
        //打印函数f(x) = 3x^3 + 2x^2 + x + 1在x=2处的二阶导数
        System.out.println(f2.f(2));
    }
}

设想到有些同学没学过java8或上述版本,以上代码没有利用java8函数式编程的新特色。 

假如您接触过java8,请考虑什么改写以上代码,使其更简明。

 

逐条表查找元素操作

代码落成:

六、最终的想法

 

public class DerivedFunction implements Function<Double, Double> {
    private static final double DELTA_X = 0.000001;
    private Function<Double, Double> function;

    public DerivedFunction(Function<Double, Double> function) {
        this.function = function;
    }

    @Override
    public Double apply(Double x) {
        return (function.apply(x + DELTA_X) - function.apply(x)) / DELTA_X;
    }
}

public class Main {
    public static void main(String[] args) {
        //打印函数在x=2处的二阶导
        System.out.println(new DerivedFunction(new DerivedFunction(x -> 3 * x * x * x + 2 * x * x + x + 1)).apply(2.0));
    }
}

前面多少个想法为了扩展Function接口,使用了表面类、匿名类的方法,其实也得以用其中类。而那在此间,我用了lambda表达式,是否更精简了。

那边用的Function接口用的是jdk自带的,大家不要求自己定义了。因为那是一个函数式接口,大家得以用lambda方便地落实。后来发现,其实那里用UnaryOperator其一接口更方便。

现在大家有没有察觉,用java、用OOP也足以丰裕简单地贯彻求导,并不比开端的那段python代码麻烦很多。

 

逐一表插入元素操作

思路如下:

1.只要插入地点不客观,抛出分外;

2.假若线性表长度当先等于数首席执行官度,则抛出格外或动态增添数组容量;

3.从最后一个因素开端向前遍历到第i个岗位,分别将它们都向后运动一个岗位;

4.即将插入元素填入地方i处;
5.线性表长+1。
代码完成:

七、编程范式

 

在我看来,编程范式简单易行来说就是编程的一种格局,一种风格。

我先介绍其中的四个,你大致就精通它的含义了。

 

顺序表删除元素操作

思路如下:
1.如果剔除元素的地点不创立,抛出尤其。比如用户删除第0个岗位的元素(线性表是从1起来的)、删除元素的职位大于线性表的长度也要抛出很是。
2.删减第i个任务的要素。
3.把第i个岗位的因素前边的具备的因素的职分加一。
4.线性表长度减一。
代码落成:

7.1 面向对象程序设计(OOP)

看来此间的同校应该对面向对象有了更直观的认识。在面向对象编程中,万物皆对象,抽象出类的概念。基本特点是包装、继承、多态,认识不深的同窗可以再去自己前边的代码中找找那四个特点。

本人事先还介绍了面向对象的几个规格:开闭原则依傍反转原则。其余还有单纯职责规范里氏替换原则接口隔离原则。那是面向对象的5个基本原则,合称SOLID)。

 

顺序表优缺点

由以上代码可以见见:
线性表的顺序存储结构,在存、读取数据时,不管是在哪些岗位,时间复杂度都是O(1)。而在插入或者去除时,时间复杂度都是O(n)。
那也就是线性表的顺序存储结构相比较适合存取数据,不合乎常常插入和删除数据的选取。

7.2 函数编程语言(FP)

本文先河那段代码用的就是python函数式编程的语法,后来我又用java8函数式编程的语法翻译了那段代码。

相信您曾经直观地感受到它的简单,以函数为着力,几行代码就缓解了求导的难点。

 

优点:

1.无需为了表示表中元素之间的逻辑关系而充实额外的存储空间(相对于链式存储而言)。
2.方可高速的存取表中肆意地点的元素。

7.3 进度式编程(Procedural programming)

大致学过编程都学过C,C语言就是一种进度式编程语言。在我看来,进程式编程几乎就是为着形成一个急需,像记流水帐一样,平铺直叙下去。 

       

缺点:

1.插入和删除操作必要活动大批量的要素。
2.当线性表长度变化较大时,难以确定存储空间的容量。
3.便于造成存储空间的“碎片”(因为线性表的顺序存储结构申请的内存空间都以接二连三的,要是因为一些操作(比如删除操作)导致某个部分出现了一小块的不总是内存空间,因为这一小块内存空间太小不能再一次被选取/分配,那么就导致了内存浪费,也就是“碎片”)
PS:windows系统有磁盘碎片整理工具,而Linux系统没有,因为Linux系统内核优化的很好,几乎是没有磁盘碎片的。

八、结尾

 

由于自己初学java,近期只能想到这么多。假使我们有更好的想法如故觉的我上边说的有难题,欢迎评论,望各位不吝赐教。

那是本身的第一篇技术博客,但愿我说驾驭了面向对象。若是对你有扶持,请点个赞或者评论下,给本人点持续创作的动力。

2.链式存储结构的线性表

眼前大家讲的线性表的顺序存储结构,它最大的老毛病就是插入和删除时索要活动多量要素,那显明就须求消耗时间。
那大家能或不能够针对这一个毛病或者说遗憾指出解决的点子呢?要缓解那个难点,大家就得考虑一下导致那个题材的缘由!
何以当插入和删除时,就要移动多量的要素?
缘由就在于相邻两元素的存储地方也富有邻居关系,它们在内存中的地方是紧挨着的,中间没有空闲,当然就不能急迅插入和删除。
线性表的链式存储结构的性状是用一组自由的存储单元存储线性表的数目元素,那组存储单元可以存在内存中未被占据的任性地点。
也就是说,链式存储结构的线性表由一个(能够使零)或者七个结点(Node)组成。每个节点内部又分为数据域和指针域(链)。数据域存储了数额元素的音信。指针域存储了现阶段结点指向的第一手后继的指针地址。
因为各种结点只包罗一个指针域,所以称为单链表。顾名思义,当然还有双链表。

单链表

链式存储结构中,除了要存储数据元素音讯外,还要存储它的后继元素的贮存地方(指针)。
也就是说除了存储其自我的新闻外,还需贮存一个指令其直接后继的储存地点的音讯。
大家把仓储数据元素音讯的域称为数据域,把囤积直接后继地方的域称为指针域。

指针域中贮存的音讯称为指针或链。
那两部分音信整合数据元素称为存储印象,或称为结点(Node)。
n个结点链接成一个链表,即为线性表(a1, a2, a3, …, an)的链式存储结构。

因为此链表的每个结点中只含有一个指针域,所以称为单链表。

线性表的链式存储结构

对此线性表来说,总得有身材有个尾,链表也不例外。咱们把链表中的第三个结点的蕴藏地点叫做头指针,最终一个结点指针为空(NULL)。
单链表是线性表中最具代表性的一种,下一篇作品中,本人将会拿出一章来介绍单链表,敬请期待!
图片源于参考自:鱼C工作室。感谢鱼C工作室进献出了那样好的图形。
PS:本篇小说在虎扑也有一齐更新,大家也得以运动微博关切自我,后续会更新越多精品作品!*
新浪地址:http://home.cnblogs.com/u/wsnb/

如非尤其表达,作者有着文章都是原创小说。如若你喜爱那篇作品,转发请申明出处。即使你对数据结构感兴趣,请关怀自我,后续会更新多量精品小说供我们参考!

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图