数据结构（顺序表）

目录

线性表的概念

顺序表的概念

顺序表的分类

静态顺序表

动态顺序表

动态顺序表的初始化

动态顺序表的销毁

动态顺序表的增容 

动态顺序表尾插数据

动态顺序表头插数据

动态顺序表尾删数据

动态顺序表头删数据

---

线性表的概念

1.线性表是n个具有相同特性的数据元素的有限序列。

2.线性表在逻辑上是线性结构，但是在物理结构上并不⼀定是连续的。

3.线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表的概念

1. 顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构.

2. ⼀般情况下采⽤数组存储，即顺序表是对数组的封装,实现了常⽤的增删改查等接口。

3. 顺序表的底层是数组，但是在数组基础上，添加了很多其他的功能。

顺序表的分类

静态顺序表

1. 使⽤定⻓数组存储元素。

2. 空间给少了不够⽤，给多了造成空间浪费。

3. 一般不用静态顺序表。

#define N 7 //方便后期修改成其他数字大小,一键替换
typedef int SLDataType; //方便后期修改成其他类型,一键替换
typedef struct SeqList
{SLDataType a[N];//定长数组int size;//有效的数据个数
}SL;//把struct SeqList结构体重命名为SL

动态顺序表

1. 结构体成员变量声明时不能初始化。（但可以宏定义）

typedef int SLDataType;//方便后期修改成其他类型,一键替换
typedef struct SeqList
{SLDataType* arr;int capacity;//顺序表的容量int size;//有效数据大小
}SL;//把struct SeqList结构体重命名为SL

动态顺序表的初始化

1. 不能直接传值给形参来实现初始化。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;
void test(SL s)
{s.arr = NULL;s.size = s.capacity = 0;return 0;
}
int main()
{SL s1;test(s1);//由于传值，所以函数调用完后，形参空间释放，实参无影响，故还是没有初始化return 0;
}

2. 可以通过传地址给形参来实现初始化。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;
void test(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;return 0;
}
int main()
{SL s1;test(&s1);return 0;
}
//ps->相当于*(p.s)

动态顺序表的销毁

void test2(SL* ps)
{if (ps->arr!=NULL)//如果arr不是NULL，则进入{free(ps->arr);//释放空间}ps->arr = NULL;ps->size = ps->capacity = 0;return 0;
}

动态顺序表的增容 

1. 增容一般成倍数增容，一般2倍或者3倍。

void test3(SL* ps)
{assert(ps);//防止传入空指针if (ps->size== ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容{int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//防止capacity为0SLDataType* tem = (SLDataType*)relloc(ps->arr, NEWcapacity  * sizeof(SLDataType);if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序{perror("relloc fail");//显示增容错误exit(1);//退出程序}ps->arr = tem;ps->capacity = NEWcapacity;//更新成员内容}return 0;
}

动态顺序表尾插数据

void test3(SL* ps, SLDataType x)
{assert(ps);//防止传入空指针if (ps->size== ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容{int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tem = (SLDataType*)relloc(ps->arr, NEWcapacity  * sizeof(SLDataType);if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序{perror("relloc fail");//显示增容错误exit(1);//退出程序}ps->arr = tem;ps->capacity = NEWcapacity;}ps->arr[ps->size++] = x;//尾部插入return 0;
}

动态顺序表头插数据

void test3(SL* ps, SLDataType x)
{assert(ps);//防止传入空指针if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容{int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tem = (SLDataType*)relloc(ps->arr, NEWcapacity * sizeof(SLDataType);if (tem == NULL)//判断是否扩容失败，如果失败则进入退出程序{perror("relloc fail");//显示增容错误exit(1);//退出程序}ps->arr = tem;ps->capacity = NEWcapacity;}for (int i = ps->size;i>0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0]=x;return 0;
}

动态顺序表尾删数据

void test5(SL* ps)
{assert(ps->arr);assert(ps->size);ps->size--;return 0;
}

动态顺序表头删数据

void test6(SL* ps)
{assert(ps->arr);assert(ps->size);for (int i = 1; i < ps->size-1; i++){ps->arr[i - 1] = ps->arr[i];}ps->size--;return 0;
}