（C语言）顺序表

基础概念

顺序表

1）静态顺序表

2）动态顺序表

顺序表功能的基本实现

1）顺序表的初始化

2）顺序表的销毁

3）顺序表的打印

4）给顺序表申请空间（扩容）

5）尾插

6）头插

7）尾删

8）头删

9）下标查找

10）指定下标插入

11）指定下标删除

总结

基础概念

数据结构：计算机存储，组织数据的方式；数组是最基本的数据结构。

线性表：具有相同性质的数据集合，其在物理（位置，地址）上不一定连续，但是在逻辑（由上一个元素找到的是下一个元素）上是一定连续的；就好比：一本书的目录上有不同章节，在书本中章与章之间有内容间隔，所以其在物理上是不连续的，但是可以通过第一章找到第二章，他在逻辑上是连续的；

顺序表是线性表的一种；顺序表的底层就是数组；所以顺序表在物理和逻辑上都是连续的；

顺序表

1）静态顺序表

静态顺序表是由一个定长数组和一个存储该顺序表中有效数据个数的变量；

静态顺序表的形式较为简单，不再过多赘述。因为静态顺序表存储数据个数有限且不能调整，所以我们更多的使用动态顺序表。

2）动态顺序表

动态顺序表与静态顺序表相比，将定长数组改成了指针，还增加了当前空间的大小；

typedef int SqlistDateType;//静态顺序表
struct Sqlist
{SqlistDateType arr[100];  //一个定长数组int size;   //顺序表中有效元素个数
};

顺序表功能的基本实现

1）顺序表的初始化

typedef int SqlistDateType;
//动态顺序表的定义
typedef struct Sqlist
{SqlistDateType* arr;   //指针int size;            //顺序表中有效数据的个数int capacity;       //当前空间的大小
}SL;

注意：此处传的是一级指针；因为我们在函数中直接定义了一个结构体（SL p；），而不是一个地址，此处要区别于链表；

2）顺序表的销毁

释放ps->arr的空间，将数组地址置为空，将size和capacity置为0；

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

3）顺序表的打印

此处只是整形打印；

//打印顺序表
void SLprint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++)printf("%d ", ps->arr[i]);printf("\n");
}

4）给顺序表申请空间（扩容）

再对顺序表的数据进行插入的时候，首先要判断空间够不够，不够要先申请空间；

在扩容的时候，我们通常是对空间进行成倍的增加，而不是缺了就加一个，不够再加一个；因为relloc再开辟空间的时候，如果后面的空间不够开辟，他就会重新找一块空间重新开辟，释放原来空间，如果频繁这样就会导致程序运行效率大大降低；

//顺序表扩容
void SLBuyplace(SL* ps)
{//先检查指针的有效性assert(ps);//判断顺序表的空间是否位空，如果是空开辟4个直接的空间，不是空对空间进行翻倍//运用三目操作符int newcapacity =( ps->capacity==0  ? 4 : (ps->capacity) * 2);//开辟空间SqlistDateType* arr_copy;   //此处创建一个临时指针是为了防止空间开辟失败，导致ps->arr变成空arr_copy = (SqlistDateType*)realloc(ps->arr, newcapacity*sizeof(SqlistDateType));if (arr_copy == NULL)perror("realloc fail");//将顺序表中的数组地址，空间大小进行更新ps->arr = arr_copy;ps->capacity = newcapacity;
}

5）尾插

将数据x插入到顺序表的尾部；

//顺序表尾插
void SLpushback(SL* ps, SqlistDateType x)
{//先检查指针assert(ps);//判断空间是否够用if (ps->capacity == ps->size)SLBuyplace(ps);//插入新的数据*((ps->arr) + ps->size) = x;//更新顺序表的有效数据ps->size++;
}

6）头插

头插与尾插相似，只不过要先对数组元素整体先后移动；

//顺序表的头插
void SLpushfront(SL* ps, SqlistDateType x)
{assert(ps);if (ps->capacity == ps->size)SLBuyplace(ps);//对数组元素进行平移for (int i = ps->size; i > 0; i--)ps->arr[i] = ps->arr[i-1];//重新定义数组第一个元素ps->arr[0] = x;ps->size++;
}

7）尾删

尾删比较简单，只需要对顺序表中的实际存储元素-1即可；

//顺序表的尾删
void SLDelback(SL* ps)
{//检查指针有效性；//顺序表有效数据个数不能是0assert(ps);assert(ps->size);ps->size--;
}

8）头删

头删与尾删相比还是多了一步：对数组元素向前整体移动一位；

//顺序表的头删
void SLDelfront(SL* ps)
{assert(ps);assert(ps->size);//判断空间够不够if (ps->size == ps->capacity)SLBuyplace(ps);//对数组元素向前平移for (int i = 0; i<ps->size; i++)ps->arr[i] = ps->arr[i + 1];  //最后一组：arr[size-1]=arr[size];ps->size--;
}

9）下标查找

下标查找是指定位置插入和删除中，不可缺少的一部分；

运用循环，遍历顺序表找到数组下标；

//顺序表的查找
int SLFind(SL* ps,SqlistDateType x)
{assert(ps);assert(ps->size);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}//没有找到，则返回一个无效下标return -1;
}

10）指定下标插入

与头插相比，此时我们只需要对，指定下标之后的元素向后移动就可以了；


//指定下标插入
void SLInsert(SL* ps, int pos, SqlistDateType x)
{assert(ps);//判断空间够不够if (ps->size == ps->capacity)SLBuyplace(ps);//对pos下标之后的元素向后移动for (int i = ps->size; i > pos; i--)ps->arr[i] = ps->arr[i-1];//最后一组是：arr[pos+1]=arr[pos];ps->arr[pos] = x;//对顺序表有小元素个数进行调整ps->size++;
}

11）指定下标删除

指定下标删除与头删的区别在于，其是将下标之后的元素整体先前移动，而不是将所有的元素都向前移动；

//指定下标删除
void SLDEL(SL* ps, int pos)
{assert(ps);assert(ps->size);//将pos后的数据全部向前移动for (int i = pos; i<ps->size-1; i++)ps->arr[i] = ps->arr[i + 1];//最后一组是：arr[size-2]=arr[size-1]ps->size--;
}