Skip to content

Latest commit

 

History

History
183 lines (151 loc) · 8.19 KB

数组和链表.md

File metadata and controls

183 lines (151 loc) · 8.19 KB
Raw

:数据结构线性表之数组和链表

吴亲库里 库里的深夜食堂

​

✏️一.线性结构的特点

在数据元素的非空有限集中，存在唯一一个被称为'第一个'的数据元素；存在唯一一个被称为'最后一个'的数据元素；除第一个元素之外，每一个元素都有一个前驱元素；除最后一个元素以外，每一个元素都有一个被称为后继的元素。线性表是最简单并且最常见的数据结构

（A,B,C,D......Z）
(2001，2002，2003，2004....)

**如上所示，线性表n个数据组成的有序数列，数列中数据的含义在具体不同的场景有不同的含义，比如可以表示为英文字母数列，也可以表示为年份数列。在稍微复杂的线性表中，一个数据元素也可以由若干的数据项组成，这种情况下通常称之为记录。

比如说公司员工信息，每一个员工的信息是由多项信息数据组成的，这个时候，每一个员工就是一个数据元素。综上所说，同一个线性表中的元素必然有相同的特型，相邻元素之间存在顺序的关系。**

(a1,a2,a3,a4,a5...ai-1..ai..ai+1....an)

则线性结构中，a1领先于a2,a1是a2的前驱，a2是a1的直接后继。

✏️二.线性结构的顺序表示和实现

顺序存储表示指的是以一组连续的存储单元依次存储线性表中的元素。如果线性表中每一个元素占位L个存储单元，如果把它所占的第一个单元作为它存储的位置，那么线性表中第i+1个元素存储位置LOC(ai+1)和第i个数据元素存储的位置LOC(ai)之间的关系满足:

LOC(ai+1)=LOC(ai)+L      //申明 这里的i,i+1是下标

线性结构的顺序表示以元素在计算机中的物理位置相邻来表示逻辑位置相邻，相邻两个元素之间的位置以物理位置的角度分析就是相差一位，只要确定了存储线性表的起始位，那么我们就能任意存储线性表中元素，下图具体表示

​

我们通常使用数组这样的数组结构来实现线性表的顺序存储。

数组的下标是从0开始的，如随机取数组中的第i个元素，那么需要注意的是下标应该是i-1。通过数组来实现线性表顺序的插入和删除。

要在数组中第i-1和第i个元素之间插入一个新的数据，就是要使n长度的数组变成n+1，数据元素a1-1和ai之间的逻辑顺序也发生了改变。必须移动元素才能反映逻辑之间的变化。如下图所示，在元素57和16之间插入一个新的元素50，那么16(包括16）元素之后的都必须向后挪动一个位置，长度+1，如果是删除，那么删除的元素后面元素向前挪动一个位置。长度-1。所以对于顺序存储和删除来说，由于我们的增加和删除会影响到之后的元素，最坏的情况下我们需要移动n个元素，使用大O来表示的话它的时间复杂度就是0(n),但是查询的话由于是连续的存储空间，所以大O时间就是O(n)。

​

对于其他语言来说，使用数组之前需要定义数组的存储的类型和大小，一旦长度不够了，那么就需要重新申请一个更多的存储空间。php不受此约束。下面是我用php实现的两个顺序结构表合并为新的非递减顺序结构表的伪代码

         
 <?php
class First{
    private $a;
    private $b;
    public function __construct($a,$b)
   {
        $this->a=$a;
        $this->b=$b;
    }

    public function merge()
{
        $c=[];
        $i=0;
        $j=0;
        while($i<=count($this->a)-1 && $j<=count($this->b)-1){
            if($this->a[$i]<$this->b[$j]){
                array_push($c,$this->a[$i]);
                $i++;
            }else{
                array_push($c,$this->b[$j]);
                $j++;
            }
        }
        while($i<=count($this->a)-1){
            array_push($c,$this->a[$i]);
            $i++;
        }
        while ($j<count($this->b)-1){
            array_push($c,$this->b[$j]);
            $j++;
        }
        return $c;
    }
}
$a=[2,5,7,9,66];
$b=[0,1,3,6,23,24];
$first=new First($a,$b);
var_dump($first->merge());

✏️三.线性结构的链式表示和实现

线性结构的顺序特点是逻辑上相邻的两个元素物理位置上也是相邻的。它的查找很方便，但是删除和增加需要移动大量的元素，这是他的弱点。链式存储，由于他不需要逻辑上相邻的数据物理地址也相邻，因此在增加和删除的时候并不需要移动数据，但是同时，它也就失去了快速查找的优点。 链式存储的特点就是用一组任意的存储单元存储线性表的数据(存储单元可以是连续的也可以不连续)。因此，为了表现出他们的逻辑关系，对于任意一个元素来说，除了存储他自身的信息之外，还要存储下一个元素（后继结点）的地址，这两个部分组成的数据元素就叫做结点。所以结点包含两个域。一个存储自身的信息，称之为数据域。另一个存储后继地址信息称之为指针域。每一个结点只包含一个指针域，所以又叫做单链表。

(a1,a2,a3......an)

整个链表的存储必须从头指针开始，头指针指向链表中的第一个结点，由于最后一个元素没有后继元素了，所以它指向的指针域就是空的。

​

用线性链表来表示线性结构时，数据元素之间的逻辑关系是由结点的指针来表示的，逻辑上相邻的两个数据元素物理存储的位置不要求相邻。下面是我用php实现在链表中的插入操作，至于删除什么的，可以自己跟着实现。

<?php

class Node
{
    public $data; //节点数据
    public $next; //下一个节点

    public function __construct($data)
{
        $this->data = $data;
        $this->next = null;
    }
}

class LinkList
{
    private $header;

    function __construct($data)
{
        $this->header = new Node($data);
    }

    //节点查找
    public function find($item)
{
        $current = $this->header;
        while ( $current->next !==null && $current->data !== $item) {
            $current = $current->next;
        }
        return $current;
    }

    //在item之后插入
    public function insert($item, $new)
{
        $Node=new Node($new);
        $current = $this->find($item);
        $Node->next = $current->next;
        $current->next = $Node;
        return true;
     }

    // 显示链表中的元素
    public function display()
    {
        $current = $this->header;
        if ($current->next == null) {
            echo "链表为空！";
            return;
        }
        while ($current->next != null) {
            $list=$current->data . "->";
            if($current->next->next==null){
                $list=$current->data.'->null';
            }
            echo $list;
            $current = $current->next;
         }
      }
}
$linkList=new LinkList('header');
$linkList->insert('header','1');
$linkList->insert('1','5');
$linkList->insert('5','7');
$linkList->insert('1','2');
$linkList->display();

当然了，链表的操作远不止这些，并且还有循环链表，双向链表等等。日常开发中需要我们具体根据业务场景来实现不一样的链表。

联系

​