likes
comments
collection
share

数据结构-线性表的顺序存储和链式存储结构php实现

作者站长头像
站长
· 阅读数 18

大话数据结构

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

绪论

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关注的问题。 逻辑结构分为以下四种

  • 集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系
  • 线性结构：线性结构中的数据元素之间是一对一的关系
  • 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系
  • 图形结构：图形结构的数据元素是多对多的关系

物理结构

也叫作存储结构 物理结构：是指数据的逻辑结构在计算机中的存储形式。 存储结构有两种：

  • 顺序存储：是把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和屋里关系是一致的
  • 链式存储：是把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法定义

比如求1+2+3+。。。+100等于多少，一般用程序写出来是这样的

let sum =0
let n = 100
foreach (let i = 1;i<=n;i++){
    sum += i;
}

但是还有别的方法可以求出来，比如高斯小时候用的方法，1+100、2+99、。。。50+51，那么我们用程序可以这样写

let sum =0
let n = 100
sum = (1+n)*n/2

这样我们就不会像上面那样循环100次才能算出结果。

算法的特性

  • 输入
  • 输出
  • 有穷性
  • 确定性
  • 可行性

函数的渐进增长

给定两个函数f(n) 和 g(n)，如果存在一个整数N,是的对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)

算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

推导大O阶方法

推导大O阶：

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中，只保留最高阶项。
  • 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
  • 得到的结果就是大O阶
算法复杂度
常数阶O(1) < 对数阶O(logn) < 线性阶O(n) <  O(n logn) < 平方阶O(n 2) < 立方阶O(n 3) < 指数阶O(2 n) < 阶乘O(n!) < O(n n)

最坏情况和平均情况

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n /2次后发现这个目标元素。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。

一般在没有特殊说明的情况下，都是指最坏时间复杂度

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间时间，算法空间复杂度的计算公式记作： S(n) = O(f(n)), 其中， n为问题的规模，f(n)为语句关于n所占存储空间的函数

线性表

零个或多个数据元素的有限序列

线性表的顺序存储结构

假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）

LOC(ai+1) = LOC(ai) + c

所以对于第i个数据元素ai的存储位置可以由a1推算得出：

LOC(ai) = LOC(a1) + (i -1) * c

比如i = 5在数组中（数组下标从0开始）:

ai = 0 + (5 - 1) * 1 = 4

那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

线性表顺序存储结构php版本实现

插入操作

  • 判断下标
  • 把从最后一个元素到要插入的位置的元素全部向后移动一位，把位置空出来让新元素插入
  • 表长加一

/**
     * 在线性表指定位置添加元素
     */
    function insert($index, $value) {
        if ($this->checkLen() == false) {
            return '表满了';
        }
        if ($index < 1 || $index > $this->dataLen) {
            return '出错啦';
        }
        /**
         * 如果$data = [1,2,3];
         * 要在2号位置添加4, $index = 2, $value=4, $this->len = 3
         * 把从最后一个元素到要插入的$index - 1的位置的元素全部向后移动一位，把$index - 1的位置空出来让新元素插入
         */
        if ($index <= $this->len) {
            for ($i = $this->len - 1; $i >= $index - 1; $i--) { //$i = 2; $i >= 1; $i--
                /**
                 * 第一遍 $this->data = [1,2,3,3]; $i = 2;
                 * 第二遍 $this->data = [1,2,2,3];$i = 1;
                 */
                $this->data[$i + 1] = $this->data[$i];
            }
        }
        $this->data[$index - 1] = $value; // $this->data = [1,4,2,3]
        $this->len++;
        return true;
    }

删除操作

  • 判断下标
  • 把要删除的位置的元素取出来
  • 把从要删除的位置到最后一个位置的元素全部向前移动一位，把最后的元素删除
  • 表长减一

/**
     * 删除线性表指定位置的元素
     */
    function remove($index) {
        if ($this->len == 0) {
            return '空表';
        }
        if ($this->checkLen() == false) {
            return '表满了';
        }
        if ($index < 1 || $index > $this->len) {
            return '出错啦';
        }
        /**
         * 如果$data = [1,4,2,3];
         * 要把2号位置4删除, $index = 2, $value=4, $this->len = 4
         * 把从要删除的$index - 1的位置到最后一个位置的元素全部向前移动一位，把最后的元素删除
         */
        $elem = $this->data[$index - 1]; //取出要删除的元素
        if ($index <= $this->len) {
            for ($i = $index - 1; $i < $this->len - 1; $i++) { //$i = 1; $i < 3; $i--
                /**
                 * 第一遍 $this->data = [1,2,2,3]; $i = 1;
                 * 第二遍 $this->data = [1,2,3,3];$i = 2;
                 */
                $this->data[$i] = $this->data[$i + 1];
            }
            //删除最后一个元素 $this->data = [1,2,3];
            unset($this->data[$this->len - 1]);
        }
        $this->len--;
        return $elem;
    }

完整代码


<?php
namespace App\Http\Models;
/**
 * 顺序存储
 * 线性表
 */
class ListTable {
    private $data = [];
    private $len = 0; //数据大小
    private $dataLen = 0; //线性表大小
    function __construct($dataLen, $data = [])
    {
        $this->dataLen = $dataLen;
        $this->data = $data;
        $this->len = count($data);
    }
    /**
     * 在线性表末尾添加元素
     */
    function add($value) {
        if ($this->checkLen() == false) {
            return '表满了';
        }
        $this->data[] = $value;
        $this->len++;
    }
    /**
     * 在线性表指定位置添加元素
     */
    function insert($index, $value) {
        if ($this->checkLen() == false) {
            return '表满了';
        }
        if ($index < 1 || $index > $this->dataLen) {
            return '出错啦';
        }
        /**
         * 如果$data = [1,2,3];
         * 要在2号位置添加4, $index = 2, $value=4, $this->len = 3
         * 把从最后一个元素到要插入的$index - 1的位置的元素全部向后移动一位，把$index - 1的位置空出来让新元素插入
         */
        if ($index <= $this->len) {
            for ($i = $this->len - 1; $i >= $index - 1; $i--) { //$i = 2; $i >= 1; $i--
                /**
                 * 第一遍 $this->data = [1,2,3,3]; $i = 2;
                 * 第二遍 $this->data = [1,2,2,3];$i = 1;
                 */
                $this->data[$i + 1] = $this->data[$i];
            }
        }
        $this->data[$index - 1] = $value; // $this->data = [1,4,2,3]
        $this->len++;
        return true;
    }
    private function checkLen() {
        if ($this->len >= $this->dataLen) {
            return false;
        }
        return true;
    }
    function list() {
        return $this->data;
    }
    /**
     * 删除线性表指定位置的元素
     */
    function remove($index) {
        if ($this->len == 0) {
            return '空表';
        }
        if ($this->checkLen() == false) {
            return '表满了';
        }
        if ($index < 1 || $index > $this->len) {
            return '出错啦';
        }
        /**
         * 如果$data = [1,4,2,3];
         * 要把2号位置4删除, $index = 2, $value=4, $this->len = 4
         * 把从要删除的$index - 1的位置到最后一个位置的元素全部向前移动一位，把最后的元素删除
         */
        $elem = $this->data[$index - 1]; //取出要删除的元素
        if ($index <= $this->len) {
            for ($i = $index - 1; $i < $this->len - 1; $i++) { //$i = 1; $i < 3; $i--
                /**
                 * 第一遍 $this->data = [1,2,2,3]; $i = 1;
                 * 第二遍 $this->data = [1,2,3,3];$i = 2;
                 */
                $this->data[$i] = $this->data[$i + 1];
            }
            //删除最后一个元素 $this->data = [1,2,3];
            unset($this->data[$this->len - 1]);
        }
        $this->len--;
        return $elem;
    }
    function getIndex($value) {
        if (in_array($value, $this->data)) {
            return array_search($value, $this->data) + 1;
        } else {
            return 0;
        }
    }
    function getElem($index) {
        if (empty($this->data) || $index < 1 || $index > $this->dataLen) {
            return '出错啦';
        }
        return $this->data[$index - 1];
    }
}

从上面可以看出，线性表顺序存储结构的插入和删除的时间复杂度都是O(n)，读数据的时间复杂度则是O(1)

线性表顺序存储结构优缺点

优点

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素

缺点

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的碎片

线性表的链式存储结构

为了表示每个数据元素ai 与其直接后继数据元素ai + 1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域，把存直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为节点。

n个节点链接成一个链表，即为线性表的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单链表。

链表中第一个节点的存储位置叫做头指针

线性链表的最后一个节点指针为空

头指针与头结点的异同

头指针

  • 头指针是指链表指向第一个节点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标识作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点

  • 头结点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（也可以存放链表的长度）
  • 有了头结点，对在第一元素节点前插入节点和删除第一节点，其操作与其它节点的操作就统一了
  • 头结点不一定是链表必须要素
单链表节点

<?php
namespace App\Http\Models\LinkList;
/**
 *
 * 单链表节点
 */
class Node {
    public $data;
    public $next; //指向下个元素的指针
    function __construct($data = null)
    {
        $this->data = $data;
        $this->next = null;
    }
    function __toString()
    {
        dump($this->data);
    }
}
单链表的读取
  • 声明一个节点p指向链表第一个节点，初始化j从1开始；
  • 当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1
  • 若到链表末尾p为空，则说明第i个元素不存在；
  • 否则查找成功，返回节点p的数据

    /**
     * 查找元素
     */
    function getElem($index) {
        $current = $this->head;
        $i = 1;
        //找到要查找位置的节点
        while($i < $index) {
            $current = $current->next;
            $i++;
        }
        return $current;
    }
单链表的插入
    /**
     * 在线性表末尾添加元素
     */
    function add($data) {
        $current = $this->head;
        //如果有后继节点就接着往后遍历，直到查找到最后一个节点
        while(!empty($current->next)) {
            $current = $current->next;
        }
        $current->next = new Node($data);
        $this->len++;
    }
单链表的删除

    /**
     * 删除线性表指定位置的元素
     */
    function remove($index) {
        if ($this->isEmpty()) {
            return '空表';
        }
        $current = $this->getElem($index);
        $elem = $current->next;
        $current->next = $elem->next;
        $this->len--;
        return $elem;
    }
单链表php完整实现

<?php
namespace App\Http\Models\LinkList;
/**
 * 链式存储
 * 线性表
 * 单链表
 */
class LinkTable {
    private $head; //头结点
    private $len = 0;  //链表长度
    function __construct()
    {
        $this->head = new Node();
    }
    /**
     * 在线性表末尾添加元素
     */
    function add($data) {
        $current = $this->head;
        //如果有后继节点就接着往后遍历，直到查找到最后一个节点
        while(!empty($current->next)) {
            $current = $current->next;
        }
        $current->next = new Node($data);
        $this->len++;
    }
    /**
     * 在线性表指定位置添加元素
     */
    function insert($index, $data) {
        $current = $this->getElem($index);
        $node = new Node($data);  //新建节点
        $node->next = $current->next; //把新节点的后继节点设置为之前这个位置节点的后继节点
        $current->next = $node; //把之前这个位置的后继节点设置成新节点
        $this->len++;
        return true;
    }
    function isEmpty() {
        if ($this->len == 0) {
            return true;
        }
        return false;
    }
    /**
     * 删除线性表指定位置的元素
     */
    function remove($index) {
        if ($this->isEmpty()) {
            return '空表';
        }
        $current = $this->getElem($index);
        $elem = $current->next;
        $current->next = $elem->next;
        $this->len--;
        return $elem;
    }
    /**
     * 查找元素
     */
    function getElem($index) {
        $current = $this->head;
        $i = 1;
        //找到要查找位置的节点
        while($i < $index) {
            $current = $current->next;
            $i++;
        }
        return $current;
    }
    
    
    /**
     * 用头插法插入$count个节点创建一个单链表
     */
    function createListHead($count) {
        for ($i = 0; $i < $count; $i++) {
            $this->insert(1, rand(0, 100));
        }
        $this->len = $count;
    }
    /**
     * 用尾插法插入$count个节点创建一个单链表
     */
    function createListTail($count) {
        $current = $this->head;
        for ($i = 0; $i < $count; $i++) {
            $current->next = new Node(rand(0, 100));
            $current = $current->next;
        }
        $this->len = $count;
    }

    
    /**
     * 清空整个单链表
     */
    function clearList() {
        if ($this->isEmpty()) {
            return '空表';
        }
        $current = $this->head->next;
        while($current) {
            $temp = $current->next;
            unset($current);
            $current = $temp;
        }
        $this->head->next = null;
        $this->len = 0;
        return true;
    }



}

单链表和顺序存储结构优缺点

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

  • 查找：顺序存储O(1), 单链表O(n)
  • 插入和删除：顺序存储O(n)，单链表在找到某位置的指针后，为O(1)

空间性能

  • 顺序存储结构需要预先分配存储空间，分大了，浪费，分小了容易溢出
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

静态链表

静态链表就是用二维组来实现链表，在数组里面存上data和next

循环链表

将单链表中终端节点的指针由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

双向链表

为了克服单向性这一缺点，设计出了双向链表。双向链表是在单链表的每个节点中，在设置一个指向其前驱节点的指针域。所以在双向链表中的节点都有两个指针域，一个指向直接后继，另一个指向直接前驱。