【计理02组05号】线性表的顺序存储
- 2021 年 12 月 28 日
- 笔记
- 【计理02组】算法与数据结构
结构介绍
线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到计算机的内存单元中指定存储位置开始的一块连续的存储空间中,称为顺序表。顺序表用一组连续的内存单元依次存放数据元素,元素在内存中的物理存储次序和它们在线性表中的逻辑次序一致,即元素a;与其前驱元素a;-和后继元素a;+1的存储位置相邻
又因为数据表中的所有数据元素具有相同的数据类型,所以只要知道顺序表的基地址和数据元素所占存储空间的大小即可计算出第i个数据元素的地址
(1)在线性表中逻辑上相邻的元素在物理存储位置上也同样相邻。
(2)可按照数据元素的位序号进行随机存取。
(3)进行插人、删除操作需要移动大量的数据元素。
(4)需要进行存储空间的预先分配,可能会造成空间浪费,但存储密度较高。
结构实现
插入操作
查看代码
public void insert(int i, Object x)throws Exception{
if(curLen==maxSize)
throw new Exception("The list is full");
if(i<0||i>curLen)
throw new Exception("The id is illegal");
for(int j = curLen; j>i;j--)
listItem[j]=listItem[j-1];
listItem[i]=x;
curLen++;
}删除操作
查看代码
public void remove(int i)throws Exception{
if(i<0||i>curLen-1)
throw new Exception("The id is illegal");
for(int j=i;i<curLen-1;i++)
listItem[j]=listItem[j+1];
curLen--;
}查询操作
查看代码
public int indexOf(Object x) {
for(int i=0;i<=curLen-1;i++) {
if(listItem[i].equals(x))
return i;
}
return -1;
}结果运行
建立一个顺序表,表中数据为 5个学生的成绩(89,93,92,90,100),然后查找成绩为90的数据元素,并输出其在顺序表中的位置
查看代码
public static void main(String[] args) throws Exception {
Main L = new Main(26);
L.insert(0, 89);
L.insert(1, 93);
L.insert(2, 92);
L.insert(3, 90);
L.insert(4, 100);
int res=L.indexOf(90);
if(res!=-1) {
System.out.println("The id of 90 is "+ res);
}else {
System.out.println("The id of 90 is not exist");
}
}
