菜单

[PHP] 数据结构-线性表的顺序存储结构PHP完结

2019年2月11日 - Java

1.PHP中的数组实际上是有序映射,可以算作数组,列表,散列表,字典,集合,栈,队列,不是定位的长短
2.数组定义中多少个单元都利用了同一个键名,则只使用了最后一个,在此之前的都被遮盖了
3.想要函数的一个参数总是通过引用传递,可以在函数定义中该参数的先头加上记号
&
4.PHP
的引用是别名,就是五个不一样的变量名字指向相同的情节;“默许意况下对象是通过引用传递的”。但实则那不是完全正确的,当对象作为参数传递,作为结果重返,恐怕赋值给别的一个变量,其余一个变量跟原来的不是引用的关联,只是他们都保存着同一个标识符的正片

事先讲了汇聚的顺序存储结构和链式存储结构,今日随着聊下一个主旨的数据结构–线性表,线性表是线性数据结构的一种表现形式

<?php
class Sqlist{
        public $data=array();
        public $length=0;
}
//插入元素
function listInsert(&$sqlist,$i,$e){
        //位置是否超出范围
        if($i<1 && $i>$sqlist->length+1){
                return false;
        }   
        //从插入位置开始,后面的所有元素都退一位
        if($i<=$sqlist->length){//要插入的位置不是在尾部
                for($k=$sqlist->length-1;$k>=$i-1;$k--){
                        $sqlist->data[$k+1]=$sqlist->data[$k];
                }   
        }   
        //新元素插入
        $sqlist->data[$i-1]=$e;
        //长度加1
        $sqlist->length++;
        return true;
}
//获取元素
function getElement($sqlist,$i,&$e){
        if($sqlist->length==0 || $i<1 || $i>$sqlist->length){
                return false;
        }   
        $e=$sqlist->data[$i-1];
        return true;
}
//删除元素
function listDelete($sqlist,$i,&$e){
        if($sqlist->length==0 || $i<1 || $i>$sqlist->length){
                return false;
        }   
        $e=$sqlist->data[$i-1];
        //如果是最后一个元素
        if($i!=$sqlist->length){
                //在删除位置之后的元素,往前移动一位
                for($k=$i-1;$k<=$sqlist->length-1;$k++){
                        $sqlist->data[$k]=$sqlist->data[$k+1];
                }   
        }   

        $sqlist->length--;
}

//插入线性表
$sqlist=new Sqlist();
listInsert($sqlist,1,"Tau");
listInsert($sqlist,1,"Shihan");
//获取元素
$e="";
getElement($sqlist,2,$e);
echo $e."\n";//输出Tau

//删除元素
listDelete($sqlist,1,$e);


var_dump($sqlist);

数据结构之集合的顺序存储结构

  

数据结构之集合的链式存储结构

线性表的概念

线性表是同一类型数据的一个点儿体系,线性表中数据成分之间的关系是一对一的涉嫌,即除去第四个和最终一个数额成分之外,其他数据成分都是首尾相接的。

线性表的顺序存储必要地点空间是延续的,地址必须一个接一个,没办法暂停。如下图为顺序存储结构:

图片 1

顺序存储结构

线性表的顺序存储每种节点只包蕴数据部分,不须要至极包涵数据里面的涉嫌,因为数量里面的涉及通过地点一连来反映,所以格外省空间

它的独到之处访问相当便捷,因为地点是两次三番的,只要知道首地点,任意一个成分的地方都足以算出来。若是各种地点占c个空中,则第i个地点为(i-1)*c。

它的毛病是在插入和删除数据时,大概要运动许多数量,比如一个10000个要素的静止数据,假如本身删除了第三个成分,为了持续保持地址一连,所以要把前面9999个要素都向前移动。

线性表的抽象数据类型定义如下:

ADT Set is

  Data:

        选取任何一种存储方法囤积的一个线性表

    Operation:

      initList() //伊始化集合

      add(obj,pos)//向第pos个职位添新币素

      remove(pos)//删除第pos个职分的成分

      find(obj)//查找成分并赶回其岗位

      value(pos)//再次回到第pos个职位元素的值

      modify(obj,pos)//修改第pos个任务的要素为obj

      size()//获取线性表的长度

      isEmpty//判断线性表是还是不是为空

      clear()//清空线性表

      forward()//正向遍历输出线性表中的所有值

      backward()//反向遍历输出线性表中的所有值

      sort()//依照当前线性表,重回一个排好序的线性表

线性表的顺序存储结构和操作落成

下边把线性表用java达成,首先定义一个线性表操作的接口,List

图片 2

List接口

上边对线性表举行初阶化

图片 3

线性表的伊始化

安顿操作add,时间复杂度O(n)

图片 4

部署成分操作

去除操作remove,时间复杂度O(n)

图片 5

移除某个地方的成分

寻找元素find,时间复杂度O(n)

图片 6

摸索成分

获取第i个职位成分,时间复杂度O(1)

图片 7

取得第i个岗位成分

修改某个地点成分modify,时间复杂度O(1)

图片 8

修改成分

判空isEmpty,清空线性表clear和获取线性表成分长度size,时间复杂度O(1)

图片 9

判空、清空、获取长度

正向遍历forward和反向遍历backward,时间复杂度O(n)

图片 10

正反向遍历

根据近来线性表,再次回到一个排好序的线性表sort,时间复杂度O(n*n)

中间用了插入排序对线性表举行排序,假设插入排序忘记了的话,可以看看我那篇博文

总得明白的各种排序(1-2)–插入排序,希尔排序

图片 11

插入排序,再次回到排好序的线性表

测试及结果

图片 12

测试及结果

好了,明天就到那里了,前面随着讲有序线性表的兑现和线性表的链式存储结构

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图