菜单

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

2018年11月16日 - Php

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地图