前言
这是我学习数据结构的第二份笔记，有关顺序表的知识。后期我会继续将数据结构知识的笔记补全。
上一期笔记有关复杂度，没看过的同学可以去看看：
有关复杂度的笔记
线性表的概念
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
动态顺序表的初始化
传数值初始化
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> typedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; int capacity; }SL; void Init_SQL((SL s) { s.arr = NULL; s.size = s.capacity = 0; return 0; } int main() { SL s; Init_SQL(s);//由于传值，所以函数调用完后，形参空间释放，实参无影响，故还是没有初始化 return 0; }
传地址初始化
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> typedef int SLDataType; typedef struct SeqList { SLDataType* arr; int size; int capacity; }SL; void Init_SQL(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; return 0; } int main() { SL s; Init_SQL(&s); return 0; } //ps->相当于*(p.s)
1. 如果直接传值，那么结构体变量s将无法初始化，因为形参初始化完后，就直接释放了内存空间。
2. 如果传地址的话，那么形参和实参共用一块地址，所以结构体变量s就能实现初始化。
动态顺序表的销毁
void Kill_SQL(SL* ps) { if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间 { free(ps->arr);//释放空间 } ps->arr = NULL; ps->size = ps->capacity = 0; return 0; }
1. 顺序表的销毁与初始化很像，多了一个操作：如果结构体变量s1占用了内存，那么先释放内存，再将结构体变量s1赋值为0。
动态顺序表的增容
1. 增容一般成倍数增容，一般2倍或者3倍。
void LargerSQL(SL* ps, SLDataType x) { assert(ps);//防止传入空指针 if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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 End_Add(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;//尾部插入 ps->size++; return 0; }
动态顺序表头插数据
void Head_Add(SL* ps, SLDataType x) { assert(ps);//防止传入空指针 if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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--)//把后size个数据整体向后移动一位 { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0]=x;//在最前面插入新成员 ps->size++; return 0; }
动态顺序表尾删数据
void End_Less(SL* ps) { assert(ps);//防止传入空指针，没有初始化 assert(ps->size);//防止没有有效数据 ps->size--;//有效成员个数减一 return 0; }
动态顺序表头删数据
void Head_Less(SL* ps) { assert(ps); assert(ps->size); for (int i = 1; i < ps->size-1; i++)//除了第一个数组成员，其余的都往前移一位 { ps->arr[i - 1] = ps->arr[i]; } ps->size--;//有效成员个数减一 return 0; }
动态顺序表任意位置增加数据
1. 在第pos个成员之后增加一个数据。
void Free_Add(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos > 0 && pos < ps->size); if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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 > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; return 0; }
动态顺序表任意位置删除数据
2. 在第pos个成员之后删除一个数据。
void Free_Less(SL* ps, int pos) { assert(ps); assert(pos > 0 && pos < ps->size); for (int i = pos; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; return 0; }
动态顺序表的成员查找
int Find_Group(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { printf("找到了\n"); printf("下标是%d\n",x); return x; } } printf("没有找到\n"); return -1;//如果没有找到则返回一个无效的下标 }
动态顺序表的打印
void Print_SQL(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } }
综合示例的代码
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int SLDataType; typedef struct SeqList { SLDataType* arr;//一个指针，所以不需要考虑数组大小 int capacity;//顺序表的容量 int size;//有效数据大小 }SL;//把struct SeqList结构体重命名为SL void Init_SQL(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; return; } void End_Add(SL* ps, SLDataType x) { assert(ps);//防止传入空指针 if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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; } void Print_SQL(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } return; } void Head_Add(SL* ps, SLDataType x) { assert(ps);//防止传入空指针 if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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--)//把后size个数据整体向后移动一位 { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x;//在最前面插入新成员 ps->size++; return; } void End_Less(SL* ps) { assert(ps);//防止传入空指针，没有初始化 assert(ps->size);//防止没有有效数据 ps->size--;//有效成员个数减一 return; } void Head_Less(SL* ps) { assert(ps); assert(ps->size); for (int i = 1; i < ps->size ; i++)//除了第一个数组成员，其余的都往前移一位 { ps->arr[i - 1] = ps->arr[i]; } ps->size--;//有效成员个数减一 return; } void Free_Add(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos > 0 && pos < ps->size); if (ps->size == ps->capacity)//判断后面是否还有剩余空间,如果没有则进入扩容 { int NEWcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tem = (SLDataType*)realloc(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 > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; return 0; } void Free_Less(SL* ps, int pos) { assert(ps); assert(pos > 0 && pos < ps->size); for (int i = pos; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; return 0; } int Find_Group(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { printf("找到了\n"); printf("下标是%d\n",x); return x; } } printf("没有找到\n"); return -1;//如果没有找到则返回一个无效的下标 } void Kill_SQL(SL* ps) { if (ps->arr != NULL)//如果arr不是空指针，则进入去释放arr的空间 { free(ps->arr);//释放空间 } ps->arr = NULL; ps->size = ps->capacity = 0; return 0; } int main() { SL s; //Init_SQL(&s); //Print_SQL(&s); //End_Add(&s,3); //Head_Add(&s, 4); //Print_SQL(&s); //Head_Add(&s, 5); //Print_SQL(&s); //End_Less(&s); //Print_SQL(&s); //Head_Less(&s); //Print_SQL(&s); //Free_Add(&s,1,0); //Print_SQL(&s); //Free_Less(&s, 1); //Print_SQL(&s); //int num=Find_Group(&s,4); //printf("%d", num); //Kill_SQL(&s); //Print_SQL(&s); return 0; }
1. 这是一个包含了顺序表的各种功能函数的综合示例。
2. 当我们需要看看是否符合我们预期时候，可以直接用打印方式进行查看。
致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
