My Little World

线性表顺序存储结构

发表于

顺序存储结构

结构struct{
数据类型 数组名data[数组最大长度MAXSIZE]；
Int length;(线性表当前长度/数组当前数据个数)
}

封装3个属性
1.存储空间起始位置，数组data,它的存储位置就是线性表存储空间的存储位置
2.线性表最大存储容量：maxsize ,初始化后一般不变
3.线性表当前长度：length，时刻改变

地址计算方法

假设每个元素占C个存储单元（字节），LOC表示获得存储位置的函数
LOC( )= loc( )+C
LOC( )= loc( )+(i-1)*C
假设,线性表最大长度设置为10；当前长度为4；如下
var maxsize = 10;
var list ={
data:[1,2,3,4],
length:4
}

获取线性表第i个位置的元素

1
2
3
4
5
6
7
8
9
10
11
function getitem(list,i){
  if(i<1 || i >list.length || list.length == 0){   //线性表位置从1 开始
    console.log("input is error")
    return
  }
  var item;
  item = list[i-1]; //数组下标从0 开始，与线性表差1
  return item;
}
var ff = getitem(list.data,0);
console.log(ff);

在线性表第i个位置插入元素item

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertitem(list,i,item){
  if(list.data.length == maxsize){
    console.log("the list is full");
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  if(i<list.data.length){
    for(var j = list.data.length -1;j>=i-1;j--){
      list.data[j+1] = list.data[j];
    }
  }
  list.data[i-1] = item; 
  list.length = list.length+1;
}
insertitem(list,2,5);
console.log(list);

删除线性表第i个位置的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function deleteitem(list,i){
  if(list.data.length == 0){
    console.log("the list is empty")
    return
  }
  if(i<1 || i >list.data.length){
    console.log("the position is not in the range")
    return
  }
  var temp = list.data[i-1];//被删除的元素
  if(i<list.data.length){
    for(var j = i ;j<list.data.length;j++){
      list.data[j-1] = list.data[j];
    }
    
  }
  list.data.splice(list.data.length-1,1);//删除最后一个
  list.length = list.length-1;
}
deleteitem(list,3);
console.log(list);

小结

在存、读数据时，不管是那个位置,时间复杂度都是O(1).
而在插入或删除时，时间复杂度都是O(n);
比较适合元素个数稳定，不经常插入和删除元素，而更多操作是存取数据的应用。
优点：
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间
2.可以快速存取表中任意位置元素
缺点
1.插入和删除操作需要移动大量元素
2.当线性表长度变化较大时，难以确定存储空间的容量
3.容易造成存储空间的碎片