顺序表

基于顺序结构（数组）实现的线性表

• 优点：可以随机访问，存储密度高
• 缺点：插入删除操作时间复杂度高
• 适合没有大量插入删除操作的表

结构

• 数组大小capacity
• 有效数据个数size，即表长

struct ArrayList{int *data;int capacity;int size;
};

创建和回收

ArrayList* createArrayList(int capacity){Array *a=new ArrayList;if(!a)return nullptr;a->data=new int[capacity];if(!a->data)return nullptr;a->size=0;a->capacity=capacity;return a;
}ArrayList* RecycleArrayList(Array **a){if(*a){if((*a)->data){delete[] (*a)->data;}delete (*a);*a=nullptr;}return *a;
}

追加插入

//追加
void appendArrayList(Array *a,int key){if(a->size==a->capacity){cout<<"表满"<<endl;return;}a->data[a->size++]=key;
}//指定位置插入
void insertArrayList(ArrayList *a,int index,int key){if(size==capacity){cout<<"表满"<<endl;return;}for(int i=a->size-1;i>=index;i--){a[i+1]=a[i];}a[i]=key;a->size++;
}

查找

//按值查找
int findArrayList(const ArrayList *a,int key){for(int i=0;i<a->size;i++){if(a->data[i]==key)return i;}return -1;
}

删除

int deleteArrayList(Array *a,int key){int i=findArrayList(a,key);if(i==-1)return i;for(int j=i+1;j<a->size;j++){a->data[j-1]=a->data[j];}a->size--;return i;
}