数据结构——lesson2线性表和顺序表

//顺序表的动态存储
typedef struct SeqList
{SLDataType* arry;//指向动态开辟的数组size_t size;//有效数据个数size_t capacity;//容量空间的大小
}SeqList;//空间不够则增容

二、接口实现

1.动态顺序表存储

注：相较于静态顺序表动态顺序表arry表示的指针数据，不再是定长数组，从而可以使用mallo，realloc函数开辟动态内存空间，此外还增加了capacity变量来记录容量大小

typedef struct SeqList
{SLDataType* arry;//指向动态开辟的数组size_t size;//有效数据个数size_t capacity;//容量空间的大小
}SeqList;//空间不够则增容

①SLDataType：其实是int被typedef的

typedef int SLDataType;//防止数组类型改变时麻烦

②size_t：无符号位的整型

2.基本增删查改接口

(1)初始化顺序表

注：（1）asert断言防止传入指针为空；

       （2）使用malloc函数给数组开4个SLDataType（typedef为int，避免修改数据的麻烦）大小的空间；

void SeqListInit(SeqList* psl)//顺序表初始化
{assert(psl);//asert断言防止传入指针为空psl->arry = (SLDataType*)malloc(sizeof(SLDataType) * 4);//给数组开4个SLDataType大小的空间if (psl == NULL){perror("malloc fail");//如果开辟没成功则返回错误return;}psl->size = 0;psl->capacity = 4;
}

(2)顺序表摧毁

注：使用动态内存函数（malloc、realloc等函数）后记得要用free释放空间；

void SeqListDestory(SeqList* psl)//顺序表销毁
{assert(psl);//assert断言free(psl->arry);//使用动态内存函数后记得要用free释放空间psl->arry = NULL;//指针置空psl->capacity = 0;psl->size = 0;
}

(3)检查空间

注：①如果空间满了使用realloc函数来增加空间；

        ②需要人为的将capacity增加到相应的容量（只是内存容量增加了，我们要将capacity与内存链接需要自己动手）；

void CheckCapacity(SeqList* psl)
{assert(psl);//断言if (psl->size == psl->capacity)//判断空间是否满了{SLDataType* tmp = realloc(psl->arry, sizeof(SLDataType) * 2 * (psl->capacity));//增容每次扩展为上一次的2倍if (tmp == NULL)//判断是否开辟成功{perror("realloc fail");return;}psl->arry = tmp;psl->capacity *= 2;//开辟成功指示容量的capacity要相应的增加}
}

(4)顺序表打印

for循环逐一打印即可；

void SeqListPrint(SeqList* psl)
{assert(psl);for (int i = 0; i < psl->size; i++){printf("%d ", psl->arry[i]);}printf("\n");
}

(5)顺序表尾插

注：①尾插数据也是增加数据所以要用检查容量函数（CheckCapacity）检查容量；

        ②相应元素加进去后，顺序表指向有效数据个数（size）要增加（类似于增加容量时capacity也要增加）；

        ③后续等学习了在特定位置（pos）插入相应元素后即可使用SeqListInsert函数，能大大提高代码的利用率，此时应该在顺序表的尾端也就是下标为size的地方插入x；

void SeqListPushBack(SeqList* psl, SLDataType x)
{assert(psl);//断言CheckCapacity(psl);//检查容量psl->arry[psl->size] = x;psl->size++;//顺序表个数要相应增加//SeqListInsert(psl,ps->size,x);//在特定位置插入元素x
}

(6)顺序表尾删

注：①要先判断顺序表中是否储存了元素，如果没有则没有继续的必要；

        ②因为顺序表是通过数组下标访问，所以只要将最大的下标减一即可，这样就访问不到最后的元素了，可以看成删掉了一个元素；

        ③后续等学习了在特定位置（pos）删除相应元素后即可使用SeqListErase函数，能大大提高代码的利用率，此时应该在顺序表的尾端也就是下标为size-1的地方删除；

void SeqListPopBack(SeqList* psl)
{assert(psl);//断言if (psl->size == 0)//判断顺序表是否有元素{return;//没有直接返回}psl->size--;//顺序表个数-1//SeqListErase(ps,ps->size-1);//在顺序表末尾删除元素
}

(7)顺序表头插

注：①头插数据也是增加数据所以要用检查容量函数（CheckCapacity）检查容量；

        ②头插数据之前的数据下标要整体+1；顺序表个数也要+1；

        ③后续等学习了在特定位置（pos）插入相应元素后即可使用SeqListErase函数，能大大提高代码的利用率，此时应该在顺序表的首端也就是下标为0的地方插入x；

void SeqListPushFront(SeqList* psl, SLDataType x)//顺序表头插
{assert(psl);CheckCapacity(psl);//检查容量for (int i = psl->size-1; i >= 0; i--)//顺序表整体向后移{psl->arry[i + 1] = psl->arry[i];}psl->size++; //顺序表个数+1psl->arry[0] = x;//SeqListInsert(ps,0,x);//在下标为0的位置插入x
}

(8)顺序表头删

注：①要先判断顺序表中是否储存了元素，如果没有则没有继续的必要；

        ②删除第一个元素，顺序表下标都要-1；

        ③顺序表元素个数（size）也要-1；

        ④后续等学习了在特定位置（pos）删除相应元素后即可使用SeqListErase函数，能大大提高代码的利用率，此时应该在顺序表的尾端也就是下标为0的地方删除；

void SeqListPopFront(SeqList* psl)//顺序表头删
{assert(psl);//断言if (psl->size == 0)//判断是否为空return;for (int i = 1; i < psl->size; i++)//顺序表数据整体都要前移{psl->arry[i - 1] = psl->arry[i];}psl->size--;//顺序表个数-1//SeqListErase(ps,0);//在下标为0位置删除
}

(9)顺序表在pos位置插入x

注：①在特定位置插入数据也是增加数据所以要用检查容量函数（CheckCapacity）检查容量；

        ②判断插入下标pos是否合理（要小于size）；

        ③插入pos位置的数据，其后的数据下标都要整体+1；

        ④顺序表元素个数（size）要+1；

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)//在pos位置插入x
{assert(psl);//断言assert(pos <= psl->size);//判断pos是否小于最大的下标CheckCapacity(psl);//检查容量for (int i = psl->size - 1; i >= pos; i--)//下标在pos之后的要整体+1{psl->arry[i + 1] = psl->arry[i];}psl->arry[pos] = x;//将x插入pos位置psl->size++;//顺序表元素个数+1
}

(10)顺序表在pos位置删除x

注：①删除元素size要-1；

        ②在pos位置删除元素，pos之后的下标都要-1；

void SeqListErase(SeqList* psl, size_t pos)//在特定位置删除元素
{assert(psl);//断言for (int i = pos + 1; i < psl->size; i++)//pos之后下标-1{psl->arry[i - 1] = psl->arry[i];}psl->size--;//顺序表元素个数-1；
}

(11)顺序表查找

int SeqListFind(SeqList* psl, SLDataType x)//顺序表查找
{assert(psl);//断言if (psl->size == 0)//判断是否为空return -1;for (int i = 0; i < psl->size; i++)//循环逐一查找{if (psl->arry[i] == x){printf("%d\n", i);return i;//找到了返回下标}}printf("没找到\n");return -1
}

3.代码运行结果如下：