目录
- 一、概念
- （一）数据结构的三元素
- 1. 逻辑结构
- （1）线性结构
- （2）非线性结构
- 2. 存储结构
- （1）顺序存储
- （2）链式存储
- （3）索引存储
- 3. 运算
- （二）时间复杂度
- 1. 线性阶
- 2. 常数阶
- 3. 平方阶
- 4. 三次方阶
- 5. 对数阶
- 6. 时间复杂度排序
- 二、顺序表
- （一）逻辑结构
- （二）存储结构
- （三）操作
- 1. 创建顺序表
- （1）返回值是创建的顺序表
- （2）参数传入想要创建的顺序表
- ① 函数声明
- ② 注意点：
- ③代码实现
- 2. 插入元素（尾插、任意位置插入）
- （1）尾插
- ① 函数声明
- ② 注意点：
- ③代码实现
- （2）任意位置插入
- ① 函数声明
- ② 注意点：
- ③代码实现
- 3. 删除元素（尾删、任意位置删除）
- （1）尾删
- ① 函数声明
- ② 注意点：
- ③代码实现
- （2）任意位置删除
- ① 函数声明
- ② 注意点：
- ③代码实现
- 4. 修改指定位置
- ① 函数声明
- ② 注意点：
- ③代码实现
- 5. 查找指定位置
- ① 函数声明
- ② 注意点：
- ③代码实现
- 6. 清空顺序表
- ① 函数声明
- ② 注意点：
- ③代码实现
- 7. 销毁顺序表
- ① 函数声明
- ② 注意点：
- ③代码实现
- 8. 排序
- ① 函数声明
- ② 注意点：
- ③代码实现
- 9. 翻转
- ① 函数声明
- ② 注意点：
- ③代码实现
- 10. 剔重
- ① 函数声明
- ② 注意点：
- ③代码实现
- 11. 打印所有元素
- ① 函数声明
- ② 注意点：
- ③代码实现
- （四）使用C语言实现的顺序表的源代码已上传资源
一、概念
可以更合理使用内存
提高程序的执行效率
C语言本质是操作内存
数据对象、数据元素、数据项
（一）数据结构的三元素
1. 逻辑结构
（1）线性结构
一对一的关系
数据连续
（2）非线性结构
树型：
一对多
图：
多对多
2. 存储结构
数据在计算机尤其是内存中的存储方式
（1）顺序存储
（2）链式存储
（3）索引存储
3. 运算
算法：有限步骤内解决问题的方法
算法不依赖于编程语言
特点：
- 有穷性
- 确定性
- 可行性
- 有0个或多个输入，有一个或多个输出
标准：
- 正确性
- 易读性
- 健壮性：对非法数据的处理能力
- 高效性
- 低存储
（二）时间复杂度
算法的时间复杂度定义为算法中可执行语句的频度之和 记作 T(n)
语句频度是指同一代码执行的次数
T(n)是算法所需时间的一种估值，n 表示问题的规模
算法的时间复杂度的表示方式为：
O(频度); ----------称为 大 O 表示法
假设有三段代码：
a 的时间复杂度为 2
b 的时间复杂度为 2n
c 的时间复杂度为2n^2
如果a、b、c组成一段程序，
那么算法的时间复杂度为
T(n) =T (2+2n+2n^2)
业内表示方法 还需T (2+2n+2n^2)要对进行简化
使用大O表示法的简化流程：
1.去掉运行时间中的所有常数项。
（例如 2+2n+2n^2，直接变为 2n+2n^2）
2.保留最高次幂项。
（2n^2+2n 变成 2n^2）
3.最高项存在但是系数不是1，则把系数置为1。
（2n^2 系数为2 去掉系数 n^2 ）
所以，最终a、b和c合并而成的代码的时间复杂度为O(n^2)。
1. 线性阶
O(n)
2. 常数阶
O(1)
3. 平方阶
O(n^2)
4. 三次方阶
O(n^3)
5. 对数阶
O(logn)
6. 时间复杂度排序
O(1)< O(logn) < O(n) < O(nlogn) < O(n^2)
可以带一个数测试，如问题规模n是16
1 < 4 < 16 < 64 < 256 < 4096 < 65536 < 16! < 16^16
二、顺序表
（一）逻辑结构
线性结构
（二）存储结构
顺序存储
内存中连续的空间
（三）操作
- 目的：封装成函数，供他人使用
- 结构体定义：
//节点结构体定义 typedef struct node { int data; //此处以int为例，可自行添加其他成员 }Nd_t; //列表结构体定义 typedef struct list { int count; //记录当前存入了多少个值 Nd_t listArr[MAX_SIZE]; }Ls_t;1. 创建顺序表
（1）返回值是创建的顺序表
list_t *create_list_1();
（2）参数传入想要创建的顺序表
① 函数声明
int create_list(Ls_t **list);
② 注意点：
- 参数必须传入二级指针（需要改变main函数中的指针的值）
- 首先需要判定传入函数的指针是否为一个空指针（因为接下来第一件事是要使用*list来接malloc的返回值，如果传入的是一个空指针，会报段错误，所以需要提前检查）
- 需要判定申请空间是否成功（申请失败会返回NULL）
③代码实现
//创建顺序表并初始化 int create_list(Ls_t **list) { if(NULL==list)//判定传入的指针是否是一个空指针 { printf("申请空间失败\n"); return -1; } //申请内存空间 *list=(Ls_t *)malloc(sizeof(Ls_t)); if(NULL==*list)//申请空间失败 { printf("申请空间失败\n"); return -1; } //初始化 (*list)->count=0; memset(*list,0,sizeof(Ls_t)); return 0; }- 补充：memset函数
#include
void *memset(void *s, int c, size_t n); //s 要置值的内存首地址 //c 用于置值的值 //n 置值的大小 2. 插入元素（尾插、任意位置插入）
（1）尾插
① 函数声明
int insert_list_by_tail(Ls_t *list,int num);
② 注意点：
- 需要判定传入的顺序表指针是否是空指针
- 需要判定顺序表是否已满
- 插入成功后，count++
③代码实现
//在尾部插入数据 int insert_list_by_tail(Ls_t *list,int num) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(MAX_SIZE == list->count) { printf("顺序表已满\n"); return -1; } //插入数据 list->listArr[list->count].data=num; //顺序表存入数据的数量+1 list->count++; return 0; }（2）任意位置插入
① 函数声明
int insert_list(Ls_t *list,int pos,int num);
② 注意点：
- 需要判定传入的顺序表指针是否是空指针
- 需要判定顺序表是否已满
- 判定插入位置是否合法，需要大于零，且需要保证顺序表内存空间连续
- 插入成功后，count++
③代码实现
int insert_list(Ls_t *list,int pos,int num) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(MAX_SIZE == list->count) { printf("顺序表已满\n"); return -1; } if(pos < 0 || pos > list->count) { printf("插入位置违法\n"); return -1; } //从后往前，依次向后移动一位，直到到达插入位置 int i=list->count; while(i!=pos) { list->listArr[i]=list->listArr[i-1]; i--; } //插入数据 list->listArr[pos].data=num; //顺序表存入数据的数量+1 list->count++; return 0; }3. 删除元素（尾删、任意位置删除）
（1）尾删
① 函数声明
int delete_list_by_tail(Ls_t *list);
② 注意点：
- 需要判定传入的顺序表指针是否是空指针
- 需要判定顺序表是否已满
- 直接count–即可，不必去清空值，此时原来的位置相当于已经声明可以继续写入数据
③代码实现
int delete_list_by_tail(Ls_t *list) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } list->count--; return 0; }（2）任意位置删除
① 函数声明
int delete_list(Ls_t *list,int pos);
② 注意点：
- 需要判定列表指针是否是空指针
- 判断表是否为空
- 判定删除位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；
- 删除成功后，count需要减一
③代码实现
int delete_list(Ls_t *list,int pos) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } if(pos<0||pos>=list->count) { printf("删除位置违法\n"); return -1; } for(int i=pos;icount;i++) { list->listArr[i]=list->listArr[i+1]; } list->count--; return 0; } 4. 修改指定位置
① 函数声明
int modify_list(Ls_t *list,int pos,int num);
② 注意点：
- 需要判定列表指针是否是空指针
- 判断表是否为空
- 判定修改位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；
③代码实现
int modify_list(Ls_t *list,int pos,int num) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } if(pos<0||pos>=list->count) { printf("修改位置违法\n"); return -1; } list->listArr[pos].data=num; return 0; }5. 查找指定位置
① 函数声明
int search_list(Ls_t *list,int pos,int *num);
② 注意点：
- 需要判定列表指针是否是空指针
- 判定查询位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；
③代码实现
int search_list(Ls_t *list,int pos,int *num) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } if(pos<0||pos>=list->count) { printf("查询位置违法\n"); return -1; } *num=list->listArr[pos].data; return 0; }6. 清空顺序表
① 函数声明
int clean_list(Ls_t *list);
② 注意点：
- 需要判定列表指针是否是空指针
- 只需将count置0即可，各函数都是根据count来进行操作，因此即使原来顺序表的值并未清空也不影响
③代码实现
int clean_list(Ls_t *list) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } list->count=0; return 0; }7. 销毁顺序表
① 函数声明
int destroy_list(Ls_t **list);
② 注意点：
- 需要先确保传入的指针并非空指针，再去判断*list是否为空
- 释放完堆区的空间后，再将main函数中的指针置为NULL
③代码实现
int destroy_list(Ls_t **list) { if(NULL == list) { printf("操作的指针不存在\n"); return -1; } if(NULL == *list) { printf("操作的表不存在\n"); return -1; } free(*list); *list=NULL; return 0; }8. 排序
① 函数声明
int sort_list(Ls_t *list,int s);
② 注意点：
- 先确保传入的指针并非空指针
- 判断表是否为空
- 第二个参数为0是正序排序，否则倒序排序
③代码实现
int sort_list(Ls_t *list,int s) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } int flag=0; for(int i=0;icount-1;i++){ flag=0; for(int j=0;j count-1-i;j++){ if(0==s){ //正序排序 if(list->listArr[j].data>list->listArr[j+1].data) { Nd_t temp=list->listArr[j]; list->listArr[j]=list->listArr[j+1]; list->listArr[j+1]=temp; flag=1; } }else{ if(list->listArr[j].data listArr[j+1].data) { Nd_t temp=list->listArr[j]; list->listArr[j]=list->listArr[j+1]; list->listArr[j+1]=temp; flag=1; } } } if(0==flag) break; } return 0; } 9. 翻转
① 函数声明
int overturn_list(Ls_t *list);
② 注意点：
- 先确保传入的指针并非空指针
- 判断表是否为空
③代码实现
int overturn_list(Ls_t *list){ if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } int i=0,j=list->count-1; Nd_t temp; while(i10. 剔重
① 函数声明
int dedup_list(Ls_t *list);
② 注意点：
- 先确保传入的指针并非空指针
- 判断表是否为空
- 两侧遍历，第一层是从第一个元素遍历到倒数第二个元素（j=i+1）；第二层是从第i+1个开始遍历，然后比较与当前第i个元素是否相等，相等就删除第j个元素，后面的元素依次向前移动一个位置，此时j无需再自加1
③代码实现
int dedup_list(Ls_t *list) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } if(0==list->count) { printf("顺序表为空\n"); return -1; } int i,j; for(i=0;icount-1;i++) { for(j=i+1;j count;j) { if(list->listArr[j].data==list->listArr[i].data){ for(int k=j;k count-1;k++) { list->listArr[k]=list->listArr[k+1]; } list->count--; }else{ j++; } } } return 0; } 11. 打印所有元素
① 函数声明
int show_list(Ls_t *list);
② 注意点：
- 需要判定列表指针是否是空指针
③代码实现
int show_list(Ls_t *list) { if(NULL == list) { printf("操作的表不存在\n"); return -1; } for(int i=0;icount;i++) { printf("%d ",list->listArr[i].data); } putchar(10); return 0; } （四）使用C语言实现的顺序表的源代码已上传资源
![[工业自动化-1]：PLC架构与工作原理](https://img-blog.csdnimg.cn/ce10a1471ed14382bc58364cf8bd5209.png)
还没有评论，来说两句吧...