数据结构之线性表的顺序存储结构

1.PHP中的数组实际上是一动不动映射,可以算作数组,列表,散列表,字典,集合,栈,队列,不是固定的尺寸
2.数组概念manbetx手机网页版着大多单单元都应用了同一个键名,则只有行使了最后一个,之前的还给埋了
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);

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

  

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

线性表的定义

线性表是同一档数据的一个片序列,线性表中数据元素中的涉嫌是一对一底涉嫌,即除去第一单跟结尾一个数码元素之外,其它数据元素都是首尾相接的。

丝性表的顺序存储要求地方空间是连的,地址必须一个连片一个,不能够暂停。如下图也顺序存储结构:

manbetx手机网页版 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

manbetx手机网页版 2

List接口

下面对线性表展开初始化

manbetx手机网页版 3

丝性表的初始化

插入操作add,时间复杂度O(n)

manbetx手机网页版 4

安插元素操作

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

manbetx手机网页版 5

移除某个位置的元素

检索元素find,时间复杂度O(n)

manbetx手机网页版 6

寻找元素

得到第i只位置元素,时间复杂度O(1)

manbetx手机网页版 7

获得第i个职务元素

修改某位置元素modify,时间复杂度O(1)

manbetx手机网页版 8

改元素

判空isEmpty,清空线性表clear和博取线性表元素长度size,时间复杂度O(1)

manbetx手机网页版 9

判空、清空、获取长度

赶巧于所有历forward和反为整个历backward,时间复杂度O(n)

manbetx手机网页版 10

正反向遍历

依据当前线性表,返回一个免去好序的线性表sort,时间复杂度O(n*n)

里用了插入排序对线性表展开排序,如果插入排序忘记了的话,可以省自家立即篇博文

得控制的八种植排序(1-2)–插入排序,希尔排序

manbetx手机网页版 11

插入排序,返回排好序的线性表

测试和结果

manbetx手机网页版 12

测试与结果

好了,今天就是到此地了,后面就说起序线性表的兑现与线性表的链式存储结构

发表评论

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

网站地图xml地图