【計理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");
}
}
