線性表
概念：
線性表是n個具有相同特性的資料元素的有限序列，線性表表示一種廣泛應用在實際中的資料結構，線性表中資料元素的關系的一對一的關系，大多數線性表除了第一個和最后一個資料元素之外，其他資料元素都是首尾相接的，
常見的線性表有順序表，鏈表，堆疊，佇列，字串，
線性表在邏輯上是線性結構，也就是說是一條直線，但是在物理上并不以一定是連續的，線性表在物理上存盤時，通常以陣列和鏈表結構的形式存盤，
順序表
順序表的概念及結構
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的資料結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪改查，
順序表一般可分為
靜態順序表:使用定長陣列存盤，
動態順序表：使用動態開辟的陣列存盤，
靜態順序表適用于知道需要存盤多少資料的場景，（開多了浪費，開少了不夠用）
實作動態順序表
MyArrayList
/*
物件具備的一致性問題（前提）
1，size<=array.length
2,真正有用的元素下標[0,size)做洗掉操作size處不進行操作，因左閉右開，size處無有效值
3,可以插入元素的位置[0,size] size處也可插入，因有容量
4，[size,array.length）設定為無效的元素long.MIN_VALUE，便于觀察
*/
/*
時間復雜度
當尾插，尾刪時(暫不考慮擴容），時間復雜度為O(1)
根據下標插入洗掉時(包括頭插),時間復雜度是O（n）
get(index)/set(index,e） 時間復雜度是O(1),順序表支持隨機訪問
查找：indexOf,contains時間復雜度是O(n)
*/
import java.util.Arrays;
public class MyArrayList {
//兩個需要的屬性
private long[] array;//存放資料的空間即空間的容量
private int size;//有效元素的個數
public MyArrayList() {
//將屬性初始化，此時未插入有效元素，故將陣列中全部填充為無效值Long.MIN_VALUE
array = new long[2];
size = 0;
Arrays.fill(array, Long.MIN_VALUE);
}
/*
放入元素
1，指定位置放入
2,在最后放入元素，即尾插操作
*/
public long get(int index) {
//用來得到對應下標的值，便于檢查操作的正確性
//檢查下標合法性
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException(index + ":" + size);
}
return array[index];
}
public int size() {
return size;
}
//尾插操作，即在末端插入值
public void add(long e) {
ensureCapacity();//呼叫方法確保容量足夠
// 1,將元素放在size下標處
array[size] = e;
// 2，size++
size++;
}
//確保容量足夠的方法
private void ensureCapacity() {
if (size < array.length) {
return;
}
//放不下了，進行擴容
//建立新陣列
int newLength = array.length * 2;
long[] newArray = new long[newLength];
//復制內容到新陣列
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
Arrays.fill(newArray, size, newArray.length, Long.MIN_VALUE);//把[size,length]填充為無效值
this.array = newArray;
}
//檢查物件的正確性
//如果物件不正確，拋例外
public void check() {
if (array == null) {
throw new RuntimeException();
}
if (array.length == 0) {
throw new RuntimeException();
}
if (size < 0) {
throw new RuntimeException();
}
if (size > array.length) {
throw new RuntimeException();
}
//[0,size)是有效元素
for (int i = 0; i < size; i++) {
if (array[i] == Long.MIN_VALUE) {
throw new RuntimeException();
}
}
//[size,array.length-1)是無效值
for (int i = size; i < array.length; i++) {
if (array[i] != Long.MIN_VALUE) {
throw new RuntimeException();
}
}
}
//指定下標進行插入
public void add(int index, long e) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException(index + ":" + size);
}
ensureCapacity();
//TODO
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = e;
size++;
}
//指定下標進行洗掉
public void delete(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException(index + ":" + size);
}
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
array[size] = Long.MIN_VALUE;
}
//指定元素進行洗掉，從前往后遍歷，只刪一個
public void removeFromHead(long e) {
int index;
for (index = 0; index < size; index++) {
if (array[index] == e) {
break;
}
}
if (index == size) {
return;
}
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
array[size] = Long.MIN_VALUE;
}
//指定元素進行洗掉，從后往前遍歷，只刪一個
public void removeFromLast(long e) {
int index;
for ( index = size-1; index >=0; index--) {
if (array[index] == e) {
break;
}
}
if (index <0) {
return;
}
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
array[size] = Long.MIN_VALUE;
}
//下邊三種均為洗掉順序表中值為e的方法，性能略有不同
//初級解法，性能較差
public void removeAll(long e) {
int index=0;
while(true){
if(array[index]==e){
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
array[size] = Long.MIN_VALUE;
}
else{
index++;
}
if(index==size){
break;
}
}
}
//開辟新陣列，稍有優化
public void removeAllNEW(long e) {
//把不是e的元素搬到新的陣列中，時間復雜度為O(n)
int newLength=array.length;
long[]newArray=new long[newLength];
int j=0;
for (int i = 0; i <size ; i++) {
if (array[i]!=e){
newArray[j]=array[i];
j++;
}
else{
}
}
size=j;
Arrays.fill(newArray,j,newLength,Long.MIN_VALUE);
this.array=newArray;
}
//優化版，在原有的陣列中完成任務
public void removeAllNEWNEW(long e) {
int from=0;
int to=0;
for (int i = 0; i <size ; i++) {
if (array[i]!=e){
array[to]=array[from];
from++;
to++;
}
else{
from++;
}
}
size=to;
Arrays.fill(array,to,array.length,Long.MIN_VALUE);
}
}
https://gitee.com/aba1iaba1i/pycharm-activation-code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/376846.html
標籤：Python