数据结构（一）顺序表

一、概念

可以更合理使用内存
提高程序的执行效率

C语言本质是操作内存

数据对象、数据元素、数据项

（一）数据结构的三元素

1. 逻辑结构

（1）线性结构

一对一的关系
数据连续

（2）非线性结构

树型：
一对多

图：
多对多

2. 存储结构

数据在计算机尤其是内存中的存储方式

（1）顺序存储

（2）链式存储

（3）索引存储

3. 运算

算法：有限步骤内解决问题的方法
算法不依赖于编程语言
特点：

1. 有穷性
2. 确定性
3. 可行性
4. 有0个或多个输入，有一个或多个输出

标准：

1. 正确性
2. 易读性
3. 健壮性：对非法数据的处理能力
4. 高效性
5. 低存储

（二）时间复杂度

算法的时间复杂度定义为算法中可执行语句的频度之和 记作 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) <O(n^3) <O(2^n) <O(n!) < O(n^n)

可以带一个数测试，如问题规模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);

② 注意点：

1. 参数必须传入二级指针（需要改变main函数中的指针的值）
2. 首先需要判定传入函数的指针是否为一个空指针（因为接下来第一件事是要使用*list来接malloc的返回值，如果传入的是一个空指针，会报段错误，所以需要提前检查）
3. 需要判定申请空间是否成功（申请失败会返回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 <string.h>
void *memset(void *s, int c, size_t n);
//s 要置值的内存首地址
//c 用于置值的值
//n 置值的大小

2. 插入元素（尾插、任意位置插入）

（1）尾插

① 函数声明

int insert_list_by_tail(Ls_t *list,int num);

② 注意点：

1. 需要判定传入的顺序表指针是否是空指针
2. 需要判定顺序表是否已满
3. 插入成功后，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;//顺序表存入数据的数量+1list->count++;return 0;
}

（2）任意位置插入

① 函数声明

int insert_list(Ls_t *list,int pos,int num);

② 注意点：

1. 需要判定传入的顺序表指针是否是空指针
2. 需要判定顺序表是否已满
3. 判定插入位置是否合法，需要大于零，且需要保证顺序表内存空间连续
4. 插入成功后，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;//顺序表存入数据的数量+1list->count++;return 0;
}

3. 删除元素（尾删、任意位置删除）

（1）尾删

① 函数声明

int delete_list_by_tail(Ls_t *list);

② 注意点：

1. 需要判定传入的顺序表指针是否是空指针
2. 需要判定顺序表是否已满
3. 直接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);

② 注意点：

1. 需要判定列表指针是否是空指针
2. 判断表是否为空
3. 判定删除位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；
4. 删除成功后，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;i<list->count;i++){list->listArr[i]=list->listArr[i+1];}list->count--;return 0;
}

4. 修改指定位置

① 函数声明

int modify_list(Ls_t *list,int pos,int num);

② 注意点：

1. 需要判定列表指针是否是空指针
2. 判断表是否为空
3. 判定修改位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；

③代码实现

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);

② 注意点：

1. 需要判定列表指针是否是空指针
2. 判定查询位置是否合法，需要大于零，且小于顺序表当前容纳值的数量；

③代码实现

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);

② 注意点：

1. 需要判定列表指针是否是空指针
2. 只需将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);

② 注意点：

1. 需要先确保传入的指针并非空指针，再去判断*list是否为空
2. 释放完堆区的空间后，再将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);

② 注意点：

1. 先确保传入的指针并非空指针
2. 判断表是否为空
3. 第二个参数为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;i<list->count-1;i++){flag=0;for(int j=0;j<list->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<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;}}}if(0==flag) break;}return 0;
}

9. 翻转

① 函数声明

int overturn_list(Ls_t *list);

② 注意点：

1. 先确保传入的指针并非空指针
2. 判断表是否为空

③代码实现

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(i<j){temp=list->listArr[i];list->listArr[i]=list->listArr[j];list->listArr[j]=temp;i++;j--;}printf("翻转完成\n");return 0;
}

10. 剔重

① 函数声明

int dedup_list(Ls_t *list);

② 注意点：

1. 先确保传入的指针并非空指针
2. 判断表是否为空
3. 两侧遍历，第一层是从第一个元素遍历到倒数第二个元素（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;i<list->count-1;i++){for(j=i+1;j<list->count;j){if(list->listArr[j].data==list->listArr[i].data){for(int k=j;k<list->count-1;k++){list->listArr[k]=list->listArr[k+1];}list->count--;}else{j++;}}}return 0;
}

11. 打印所有元素

① 函数声明

int show_list(Ls_t *list);

② 注意点：

1. 需要判定列表指针是否是空指针

③代码实现

int show_list(Ls_t *list)
{if(NULL == list) {printf("操作的表不存在\n");return -1;}for(int i=0;i<list->count;i++){printf("%d ",list->listArr[i].data);}putchar(10);return 0;
}

（四）使用C语言实现的顺序表的源代码已上传资源