数据结构学习Day1:顺序表代码

//顺序表模板
#include <iostream>
using namespace std;
#define eleType int
struct SequentialList {
? ? eleType *elements;
? ? int size;
? ? int capacity;

};

//初始化顺序表
void initalizeList(SequentialList* list, int capacity) {
? ? list->elements = new eleType[capacity];
? ? list->size = 0;
? ? list->capacity = capacity;
}

void destoryList(SequentialList* list) {
? ? delete[] list->elements;
}

int size(SequentialList* list)
{
? ??
? ? ? ? return list->size;
}
//判断表是否为空
bool isEmpty(SequentialList* list) {
? ? return list->size == 0;
}
//插入表
void insert(SequentialList* list, int index, eleType element) {
? ? if (index < 0 || index > list->size) {
? ? ? ? throw std::invalid_argument("Invalid index");//如果给出的下标不合法，则抛出异常
? ? }
? ? if (list->size == list->capacity) { ? ? ? //如果表中元素满了，即size == 设置的容量capacity,我们选择扩容
? ? ? ? int newCapacity = list->capacity * 2;//新空间为老空间*2
? ? ? ? eleType* newElements = new eleType[newCapacity];//申请一个新空间
? ? ? ? for (int i = 0; i <list ->size; ++i) { ? //将原来的元素的一个个放到新空间来
? ? ? ? ? ? newElements[i] = list->elements[i];
? ? ? ? }
? ? ? ? delete[] list->elements;//释放内存空间
? ? ? ? list->elements = newElements;//将相应变量指向新空间
? ? ? ? list->capacity = newCapacity;
? ? }
? ? for (int i = list->size; i > index; --i) {//从后往前挪
? ? ? ? list->elements[i] = list->elements[i - 1];//将当前位置的元素赋值给后一位的元素，相当于往后挪一位
? ? }
? ? list -> elements[index] = element;//将像插入的元素放入index位置，element为目标元素
? ? list -> size ++;
}
//删除元素
void deleteElement(SequentialList* list, int index) {
? ? if (index < 0 || index >= list->size) { ? ? ? ? ?//与插入操作不同删除操作index不可等于最后一位，因为实际上是不存在的因此无法删除，而插入不关心存不存在
? ? ? ? throw std::invalid_argument("Invalid index");//如果给出的下标不合法，则抛出异常
? ? }
? ? //缩容，可写可不写
? ? for (int i = index; i < list->size - 1; ++i) {
? ? ? ? list->elements[i] = list->elements[i + 1];//从index开始，将后一位的元素往前挪一个覆盖前一位元素，刚好达成删除的功能
? ? }
? ? list->size--;
}
//查找元素
int findElement(SequentialList* list, eleType element) {
? ? for (int i = 0; i < list->size; ++i) {
? ? ? ? if (list->elements[i] == element) {
? ? ? ? ? ? return i;
? ? ? ? }
? ? }
? ? return -1;
}
//元素索引
eleType getElement(SequentialList* list, int index) {
? ? if (index < 0 || index >= list->size) {
? ? ? ? throw std::invalid_argument("Invalid index");//如果给出的下标不合法，则抛出异常
? ? }
? ? return list->elements[index];
}
//元素修改
void updateElement(SequentialList* list, int index, eleType value) {
? ? if (index < 0 || index >= list->size) {
? ? ? ? throw std::invalid_argument("Invalid index");//如果给出的下标不合法，则抛出异常
? ? }
? ? list->elements[index] = value;
}

int main() {
? ? SequentialList myList;
? ? initalizeList(&myList, 10);
? ? for (int i = 0; i < 10; ++i) {
? ? ? ? insert(&myList, i, i * 10);
? ? }
? ? cout << "Size:" << size(&myList) << endl;
? ? cout << "isEmpty:" << isEmpty(&myList) << endl;

? ? for (int i = 0; i < size(&myList); ++i) {
? ? ? ? cout << getElement(&myList, i) << " ";
? ? }
? ? cout << endl;

? ? deleteElement(&myList, 5 );
? ? updateElement(&myList, 1, 1314);
? ? for (int i = 0; i < size(&myList); ++i) {
? ? ? ? cout << getElement(&myList, i) << " ";
? ? }
? ? cout << endl;

? ? int idx = findElement(&myList, 20);
? ? updateElement(&myList, idx, 520);
? ? for (int i = 0; i < size(&myList); ++i) {
? ? ? ? cout << getElement(&myList, i) << " ";
? ? }
? ? cout << endl;

? ? destoryList(&myList);
? ? system("pause");

? ? return 0;
}