目录
学习目标
引言
1.什么是线性表？
2.什么是顺序表？
2.1概念及结构
2.2 接口实现
2.2.1顺序表的功能
1.顺序表的初始化
2.打印数据
3.尾插数据
(1)检查空间
(2)插入数据
4.尾删数据
5.头插数据
6.头删数据
7.数据查找
8.指定位置数据修改
9.指定位置数据删除
10.指定位置数据插入
11.销毁顺序表
完整代码
1.SeqList.h
2.SeqList.c
2.3 数组相关面试题
2.4 顺序表的问题及思考
结束语
学习目标
- 1.什么是线性表？
- 什么是顺序表？
- 顺序表的接口实现
引言
在 数据结构——lesson1.基础中我们学习了数据结构的一些基础知识，今天我们接着来学习一种数据结构——顺序表。
在学习顺序表之前，我们首先要知道
1.什么是线性表？
- 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...
- 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。
2.什么是顺序表？
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。
今天我们要学习的是动态顺序表。
它与数组非常类似，但是相比于静态顺序表有一个非常明显的优点——可以动态内存增长空间大小。
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
2.2.1顺序表的功能
顺序表可以大致包含如下几个功能：
1.初始化顺序表中的数据。
2.打印顺序表中的数据。
3.对顺序表进行尾插(末尾插入数据)。
4.对顺序表进行尾删(末尾删除数据)。
5.对顺序表进行头插(开头插入数据)。
6.对顺序表进行头删(开头删除数据)。
7.对顺序表数据进行查找。
8.对顺序表数据进行修改。
9.对指定位置的数据删除。
10.对指定位置的数据插入。
11.销毁顺序表。
1.顺序表的初始化
顺序表的初始化我们可以把空间和有效数据个数都设置为0。
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}2.打印数据
//顺序表的打印
void SLPrint(SL* ps)
{assert(ps);if (ps->size == 0){printf("该顺序表为空\n");return;}for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}3.尾插数据
尾插数据就是在顺序表的末尾插入数据，在插入数据之前需要先检查顺序表的空间够不够，不够的话我们需要进行扩容处理。
(1)检查空间
void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间//malloc calloc realloc int arr[100]--->增容realloc//三目表达式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;}
}(2)插入数据
//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps); //检查空间是否足够//ps->arr[ps->size] = x;//++ps->size;ps->arr[ps->size++] = x; //尾插数据
}4.尾删数据
尾删数据十分容易，只需要size--就可以了。但是，要注意：一定要确保顺序表中有数据。
void SLPopBack(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps->size);ps->size--;
}5.头插数据
头插数据是指在顺序表的起始位置插入数据。
//头插
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]; //即arr[1]=arr[0]以此类推}ps->arr[0] = x;ps->size++;
}6.头删数据
删除头部数据，需要依次往前覆盖。
// 头删
void SLPopFront(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps->size);//数据整体往前移动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}7.数据查找
输入参数，在顺序表找到指定的值并返回下标，找不到则返回-1。
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){//找到if (ps->arr[i] == x){return i;}}//没找到return -1;
}8.指定位置数据修改
//指定位置数据修改
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(ps->size);assert(pos>=0 && pos < ps->size);ps->arr[pos] = x;
}9.指定位置数据删除
//指定位置删除数据
void SLErase(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--; //有效数据-1
}10.指定位置数据插入
//在指定位置之前插入数据
//pos为指定位置
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//先检查空间够不够SLCheckCapacity(ps);//让pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}11.销毁顺序表
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}完整代码
1.SeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义顺序表的结构//define N 100
//静态顺序表
//struct SeqList
//{
// int arr[N];
// int size; //有效数据个数
//}typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{SLDataType* arr;int size; //有效数据个数int capacity; //空间大小
}SL;//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* PS);
//顺序表的打印
void SLPrint(SL s);//尾部插入
void SLPushBack(SL* ps, SLDataType x);
//头部插入
void SLPushFront(SL* ps, SLDataType x);//尾部删除
void SLPopBack(SL* ps);
//头部删除
void SLPopFront(SL* ps);//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除数据
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps, SLDataType x);2.SeqList.c
#include"SeqList.h"void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间//malloc calloc realloc int arr[100]--->增容realloc//三目表达式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)
{/*if (ps == NULL){return;}*/assert(ps);/*ps->arr[ps->size] = x;++ps->size;*/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]; //即arr[1]=arr[0]以此类推}ps->arr[0] = x;ps->size++;
}//顺序表的打印
void SLPrint(SL* ps)
{assert(ps);if (ps->size == 0){printf("该顺序表为空\n");return;}for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLPopBack(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps->size);ps->size--;
}// 头删
void SLPopFront(SL* ps)
{assert(ps);//判断顺序表是否为空assert(ps->size);//数据整体往前移动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//在指定位置之前插入数据
//pos为指定位置
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//先检查空间够不够SLCheckCapacity(ps);//让pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//指定位置删除数据
void SLErase(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--;
}//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){//找到if (ps->arr[i] == x){return i;}}//没找到return -1;
}//指定位置数据修改
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(ps->size);assert(pos>=0 && pos < ps->size);ps->arr[pos] = x;
}2.3 数组相关面试题
- . 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。OJ链接
- 2. 删除排序数组中的重复项。OJ链接
- 3. 合并两个有序数组。OJ链接
2.4 顺序表的问题及思考
问题：
- 1. 中间/头部的插入删除，时间复杂度为O(N)
- 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们 再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下一节内容我们将给出了链表的结构来看看。
结束语
这一节我们了解到了第一个数据结构——顺序表
非常感谢你的点赞关注和收藏！！！
