本篇代码位置
代码位置
顺序表和链表
1.线性表
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的 数据结构，常见的线性表：顺序表、链表、栈、队列、字符串······
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性 表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1 概念与结构
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。
顺序表和数组的区别？
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。可以这么理解，我们使用数组来存储数据，并提供了增删查改数据的接口(函数)，这样组织和存储数据的结构我们将它称为顺序表。
2.2分类
2.2.1 静态顺序表
概念：使用定长数组存储元素
- 缺陷：显而易见的，空间一定，给少了不够用，给多了太浪费
2.2.2 动态顺序表
概念：不存储数组，而是存储一个指向一块动态开辟的内存空间的指针
优点：按需开辟，可增容
故我们一般都使用动态顺序表
2.3 动态顺序表的实现
2.3.1动态顺序表的初始化和销毁及打印
创建顺序表，并将其中的指针置为NULL，容量和有效数据个数置为0，销毁大致相同，不过如果arr指针非空，不要忘了释放动态申请的空间
SeqList.h(其中方法会一一讲到)
- 定义顺序表结构
- 将存储数据类型重命名(方便之后替换->例如我们要求顺序表内存储char类型数据，只用改一行代码即可)
- 所写的函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样
#pragma once #include <stdio.h> #include<stdlib.h> #include <assert.h> typedef int sldatatype; typedef struct Seqlist { sldatatype* arr; sldatatype size; sldatatype capacity; } sl; void slinit(sl*);//初始化 void sldestroy(sl*);//销毁 void slprint(sl*);//打印 void checkcapacity(sl*);//判断空间是否足够 void slpushback(sl*, sldatatype);//尾插 void slpushfront(sl*, sldatatype);//头插 void slpopfront(sl*);//头删 void slpopback(sl*);//尾删 //在指定位置插入和删除数据 void slinsert(sl*, sldatatype, int); void slfrase(sl*, int); //查找指定数据 int slfind(sl*, sldatatype);
test.c
- 用来测试我们写的函数(函数的调用)
- 这一部分就是自己写的时候用的测试用例，随便什么都行
最好是写一个方法测试一次，不然找错误的时候会很痛苦😜
sl s; //要改变s结构体之中的内容，别忘了传地址 #define _CRT_SECURE_NO_WARNINGS 1 #include "Seqlist.h" void sltest1() { sl s; slinit(&s); slpushback(&s, 1); slpushback(&s, 2); slpushback(&s, 6); slpushback(&s, 5); int m=slfind(&s, 7); printf("%d\n", m); //slpushfront(&s, 2); //slpushfront(&s, 3); //slinsert(&s, 1, 0); //slinsert(&s, 2, 6); //slinsert(&s, 1,0 ); //slfrase(&s, 1); //slfrase(&s, 0); //slfrase(&s, 1); //slpopback(&s); //slpopback(&s); //slpopback(&s); //slpopback(&s); //slpopback(&s); slpushback(NULL, 6); //slpopfront(&s); //slpopfront(&s); //slpopfront(&s); //slpopfront(&s); //slpopfront(&s); //slpopfront(&s); slprint(&s); sldestroy(&s); } int main() { sltest1(); return 0; }
SeqList.c
函数方法的实现，重点重点！！！
在每一个方法的第一排都使用assert宏来判断ps是否为空（避免使用时传入空指针，后续解引用都会报错）
void slinit(sl* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->size = 0; } void sldestroy(sl*ps) { assert(ps); if (ps->arr) { free(ps->arr); ps->arr = NULL; } ps->capacity = ps->size = 0; }
考虑到每次测试方法时调试会很麻烦，于是先写一个打印顺序表的方法
void slprint(sl* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } }
遍历就行了，和打印数组一样的
2.3.2动态顺序表的插入
插入数据的时候一定要判断空间是否足够，不足要增容，一般2倍或3倍增容！！！
SeqList.c
养成好习惯，不要用arr直接接收动态开辟空间的地址，否则开辟失败arr变为NULL，连原来的内存块都找不到了，这就造成了内存泄漏！！！
void slcheckcapacity(sl* ps) { assert(ps); if (ps->capacity == ps->size) { //增容 //若capacity为0，给个默认值，否则乘以2 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = newcapacity; } }
动态顺序表的尾插
SeqList.c
void slpushback(sl* ps, sldatatype x) { assert(ps); slcheckcapacity(ps); ps->arr[ps->size++] = x; }
- 插入后size++即可了
动态顺序表的头插
SeqList.c
void slpushfront(sl* ps, sldatatype x) { assert(ps); slcheckcapacity(ps); for(int i=ps->size;i>0;i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; }
- 先让每个数据往后一位，注意一定要从后往前挪，否则数据会被覆盖
- 记得size++
动态顺序表的在指定位置插入数据
SeqList.c
void slinsert(sl* ps, sldatatype x, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); slcheckcapacity(ps); for (int i = ps->size; i > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; }
- 类似头插，涉及到pos以及之后数据的向后移动，还是从后往前挪动
- size++
2.3.3动态顺序表的删除
动态顺序表的尾删
删除数据的时候一定要判断顺序表是否为空，即size不能为0！！！
SeqList.c
void slpopback(sl* ps) { assert(ps && ps->size); ps->size--; //ps->arr[ps->size] = 0;多余了，没有必要 }
- 只要让size–即可，不影响后来的插入(数据会被覆盖)
动态顺序表的头删
SeqList.c
void slpopfront(sl* ps) { assert(ps && ps->size); for (int i = 0; i <ps->size-1 ; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; }
- 让每一位向前移动一位，从前往后挪，防止数据覆盖
- 记得size–
动态顺序表的在指定位置删除数据
SeqList.c
void slfrase(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--; }
- 类似头删，让pos以及之后的数据向前一位，从前往后挪
- size–
2.3.4动态顺序表查找指定数据
SeqList.c
int slfind(sl* ps, sldatatype x) { assert(ps); int i = 0; int flag = 0; for (i = 0; i < ps->size; i++) { if(ps->arr[i]==x) { flag = 1; break; } } if (flag) return 1; else { return -1; } }
- 遍历就完事了，相信各位已经熟练掌握了(❁´◡`❁)
- 如果找到返回1，没找到就返回-1（使用bool类型也是可以滴）
SeqList.c(完整版)
#include "Seqlist.h" void slinit(sl* ps) { ps->arr = NULL; ps->capacity = ps->size = 0; } void sldestroy(sl*ps) { assert(ps); if (ps->arr) { free(ps->arr); ps->arr = NULL; } ps->capacity = ps->size = 0; } void slprint(sl* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } } void slcheckcapacity(sl* ps) { assert(ps); if (ps->capacity == ps->size) { //增容 //若capacity为0，给个默认值，否者乘以2 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; sldatatype* tmp = (sldatatype*)realloc(ps->arr, newcapacity * sizeof(sldatatype)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = newcapacity; } } void slpushback(sl* ps, sldatatype x) { assert(ps); slcheckcapacity(ps); ps->arr[ps->size++] = x; } void slpushfront(sl* ps, sldatatype x) { assert(ps); slcheckcapacity(ps); for(int i=ps->size;i>0;i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; } void slpopback(sl* ps) { assert(ps && ps->size); ps->size--; //ps->arr[ps->size] = 0;多余了，没有必要 } void slpopfront(sl* ps) { assert(ps && ps->size); for (int i = 0; i <ps->size-1 ; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; } void slinsert(sl* ps, sldatatype x, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); slcheckcapacity(ps); for (int i = ps->size; i > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; } void slfrase(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]; } } int slfind(sl* ps, sldatatype x) { assert(ps); int i = 0; int flag = 0; for (i = 0; i < ps->size; i++) { if(ps->arr[i]==x) { flag = 1; break; } } if (flag) return 1; else { return -1; } }
