顺序表的基本操作（及动态扩容）

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。

基本操作

编写一个完整的程序，实现顺序表的建立、插入、删除、输出等基本运算。 1.顺序表的初始化 2.在pos位置插入val值 3.查找key值 4.删除pos位置的值 5.删除key值 6.得到pos下标的值 7.得到顺序表长度 8.清除顺序表 9.打印顺序表 在对顺序表操作之前，我们应先定义一个结构体来得到该顺序表Sqlist。

#define SIZE 10 typedef struct Sqlist { int elem[SIZE];//定义结构体 int length;//有效数据个数 }Sqlist, * PSqlist;

1初始化顺序表

void InitSqlist(PSqlist Psq)//初始化 { assert(Psq != NULL); if (Psq == NULL) { return; } Psq->length = 0; } static bool IsFULL(PSqlist Psq)//判断顺序表是否满 { if (Psq->length == SIZE) { return true; } return false; }

2.在pos位置插入val值

bool Insert(PSqlist Psq, int pos, int val)//在pos位置插入val值 { if (IsFULL(Psq))//判断顺序表是否满 { return false; } if (pos<0 || pos>Psq->length) { return false; } for (int i = Psq->length - 1; i >= pos; i--) { Psq->elem[i + 1] = Psq->elem[i]; } Psq->elem[pos] = val; Psq->length++; return true; }

3.查找key值

int Search(PSqlist Psq, int pos, int key)//查找key值 返回下标 { if (pos < 0 || pos >= Psq->length) { return -1; } for (int i = pos; i < Psq->length; i++) { if (Psq->elem[i] == key) { return i; } } return -1; }

4.删除pos位置的值

bool DeletePos(PSqlist Psq, int pos, int* rtv)//删除pos位置的值 { if (pos < 0 || pos >= Psq->length) { return false; } if (rtv != NULL) { *rtv = Psq->elem[pos]; } for (int i = pos; i < Psq->length - 1; i++) { Psq->elem[i] = Psq->elem[i + 1]; } Psq->length--; return true; }

5.删除key值

//pos:从pos位置开始的第一个key值 bool Delete(PSqlist Psq, int pos, int key)//删除key值 { //1 查找是否有key值 int index = Search(Psq, pos, key); if (index < 0) { return false; } //2 删除pos位置的值 return DeletePos(Psq, index, NULL); }

6.得到pos下标的值

bool GetElem(PSqlist Psq, int pos, int* rtv)//得到pos下标的值 { if (pos < 0 || pos >= Psq->length) { return false; } if (rtv != NULL) { *rtv = Psq->elem[pos]; } return true; }

7.得到顺序表长度

int GetLength(PSqlist Psq)//得到顺序表长度 { return Psq->length; }

8.清除以及摧毁顺序表

void Clear(PSqlist Psq)//清除 { Psq->length = 0; } void Destory(PSqlist Psq)//摧毁 { Clear(Psq); }

9.打印顺序表

void Show(PSqlist Psq)//打印 { for (int i = 0; i < Psq->length; i++) { printf("%d",Psq->elem[i]); } printf("\n"); }

动态扩容

在此顺序表中有一个很大的缺点，那就是限定了该顺序表的大小为10，也就是只能顺序存储十个数据，想要存储超过十个数据就需要对该顺序表进行优化，使之可以进行动态扩容。 1.在定义该结构体时加入一个元素记录已使用数据个数。

#define INIT_SIZE 10//初始大小 typedef struct Sqlist { int* elem;//存储数据的内存 int usedsize;//有效数据个数 int size;//总单元个数 }DSqlist, * PDSqlist;

当有效数据个数usedsize达到总单元个数size时，使用realloc函数进行动态扩容。到这样会存在内存块泄漏问题，需要我们对内存块泄漏进行处理。

void Inc(PDSqlist psq) { //psq->elem 扩容对象 psq->size * sizeof(int)* 2 扩容2倍 assert(psq != NULL); psq->elem = (int*)realloc(psq->elem , psq->size * 2 * sizeof(int));//(内存块泄露) assert(psq->elem != NULL); psq->size *= 2; }