数据结构---顺序表

2.顺序表

2.1动态顺序表

关于动态顺序表这里我们要定义一个结构体，其中的空间问题不是直接利用数组去开辟（由于定义数组空间是固定的，不利于后面的操作（增删改查））

//定义的结构体 typedef int SLDataType;//方便调整类型 //动态顺序表，按需申请 typedef struct SeqList { SLDataType* arr;//使当前顺序表方便扩容/调整类型 int size; //有效数据个数 int capacity; //空间容量 }SL;

初始化

void SLInit(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; }

销毁

//顺序表的销毁 void SLDestroy(SL* ps) { if (ps->arr) //等价于 if(ps->arr != NULL) { free(ps->arr); } ps->arr = NULL; ps->size = ps->capacity = 0; }

动态顺序表空间是我们自己申请的使用结束的时候都需要进行释放，将空间使用权限归还给操作系统，否则就会导致内存泄漏。

扩容

判断是否扩容这是比静态顺序表多出来的，在动态顺序表中，我们要扩容就要自己进行调节

void SLCheckCapacity(SL* ps) { //插入数据之前先看空间够不够 if (ps->capacity == ps->size) { //申请空间 //malloc calloc realloc int arr[100] --->增容realloc //三目表达式 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity *sizeof(SLDataType)); //要申请多大的空间 if (tmp == NULL) { perror("realloc fail!"); exit(1);//直接退出程序，不再继续执行 } //空间申请成功 ps->arr = tmp; ps->capacity = newCapacity; } }

这样才能插入

尾插

这是很简单的插入，仅判断是否扩容，后面直接插入修改

//尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps);//进行容量检查 //ps->a[ps->size] = x; //ps->size++; ps->arr[ps->size++] = x; }

尾插时需要先判断顺序表是否满了，满了要先进行扩容才能继续进行扩容。size表示有效元素个数，同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size加一。

头插

//头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); //先让顺序表中已有的数据整体往后挪动一位 for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0] } ps->arr[0] = x; ps->size++; }

头插需要先进行容量检查，再把原顺序表中的元素全部往后挪动一位，最后再进行插入。

尾删

//尾删 void SLPopBack(SL* ps) { //assert(ps->size > 0)//暴力检查 if (ps->size == 0)//如果size==0说明顺序表已经没有数据了，也就不用再尾删 { return; } ps->size--; }

头删

void SLPopFront(SL* ps) { assert(ps); assert(ps->size); //数据整体往前挪动一位 for (int i = 0; i < ps->size-1 ; i++) { ps->arr[i] = ps->arr[i + 1]; //arr[size-2] = arr[size-1] } ps->size--; }

头删需要从第二个元素开始把后面的所有元素往前挪动一位。

在指定位置（pos）插入元素

//在pos位置处插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); //把从pos位置开始的所有数据往后挪动一位 int end = ps->size - 1; while (end >= pos) { ps->arr[end + 1] = ps->arr[end]; end--; } ps->arr[pos] = x; ps->size++; }

在指定位置（pos）删除元素

//删除pos位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//size位置不能删，不是顺序表中的有效位置 //把pos位置后面的所有元素往前挪动一位 int str = pos + 1; while (str < ps->size) { ps->arr[str - 1] = ps->arr[str]; str++; } ps->size--; }

查找元素

//查找 int SLFind(SL* ps, SLDataType x) { assert(ps); int str = 0; while (str < ps->size) { if (ps->arr[str] == x) { return str; } str++; } return -1; }

打印

void SLPrint(SL s) { for (int i = 0; i < s.size; i++) { printf("%d ", s.arr[i]); } printf("\n"); }