前言：
关于源码的几个说明：
编码工具：Xcode
语言：C语言
参考书：《大话数据结构》
为了方便不熟悉的小伙伴们，文中关于代码的部分给出了详细的步骤，只要按照步骤，都可以实现。
另：小编的C语言是自学的，且许久不用，如有疏漏，请指出，不胜感谢。
本节解决问题：
1、什么是线性表？
2、如何定义线性表？
3、如何存储线性表？
4、什么是线性表的顺序存储？
5、如何实现顺序存储的线性表？
6、如何在顺序存储的线性表中实现插入、删除、查找、修改？
7、顺序存储的线性表的优缺点？
思考：
顺序存储的线性表与一维数组的关系是什么？
一、引入
场景一：
今天的最后一节课是体育课，同学们三三俩俩的走向操场。上课铃声响起，体育老师一声哨音，喊一声："排成一队！"，同学们立马整整齐齐的排列好了。那么，同学们是如何确定自己的位置的呢？因为第一节课，老师给同学们排好了位置，排头的同学记得自己是第一个，排尾的同学记得自己是最后一个，中间的同学记得自己的左边，右边的同学，也就能够快速的排好队了。
场景二：
幼儿园的老师们很用心，每次放学的时候，都让小朋友们一个牵着另一个的衣服依次走出教室。这样防止了个别小朋友没有到，老师而不能及时发现的情况。因为每个小朋友记得自己前面和后面的小朋友，如果哪个没到，他前面和后面的小朋友一定会及时发现的。家长接孩子的时候，知道自己家孩子的位置，一眼就能看到，避免了混乱。反观学校外面，孩子找家长就没那么容易了，因为是散乱在一起的。😁。
上面的两个例子都突出了一个特征：排队。这就是我们今天要学习的线性表。
二、什么是线性表
零个或多个数据元素的有限序列。
关键词：
1、序列
也就是有头有尾，中间的元素有且只有一个前驱和后继。
2、有限
也就是说线性表的元素个数是有限的，而不是无穷无尽的。
模型示意图：
线性表的元素个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。
注意：
线性表中的数据元素的类型都是相同的。
三、如何定义线性表？
要想知道如何定义一个线性表，首先我们要了解线性表的抽象数据类型。
要想建立抽象数据类型，我们就不得不了解线性表具有哪些操作。
1、创建和初始化
幼儿园老师为了让小朋友有序的出入，考虑给他们排队，第一次排队就是创建和初始化的过程。
2、重置或置空
幼儿园小朋友身高变化很快，不就发现整个队伍已经参差不齐了，于是考虑重新排序，这就是重置的过程。
3、查找
我们可以随时的叫出某一个位置的小朋友的名字以及他的具体情况，这就是查找。
4、是否存在
有人问，小明在不在这个班级呢？老师回答在呢。这种查找某个元素是否存在的操作也很常见。
5、长度
有人问，向日葵班总共有多少小朋友啊？这种获得线性表长度的操作也很普遍。
6、插入
班里来了新的小朋友，要给他一个位置。这个过程就是插入。
7、删除
班里有个小朋友转学了，要把他的位置去掉。这个过程就是删除。
了解了线性表的常用操作，我们就可以给出线性表的抽象数据类型了。
ADT 线性表(List)
Data
数据对象集合： {a1,a2,a3,······,an}
每个元素类型：DataType
除a1和an外，每个元素都只有一个前驱和后继。
Operation
initList:初始化，建立空表
listEmpty:线性表是否为空，为空返回true，否则返回false
clearList:置空线性表
getElem:获取某个位置的元素
locateElem:查找某个元素的位置
insertList：插入新的元素
deleteList：删除某个元素
listLength：返回线性表的长度（元素个数）
endADT
四、如何存储线性表
我们知道了如何定义线性表，但是在计算机中，是如何存储线性表的呢？学过一门计算机语言的同学们应该知道数组，我们发现数组完全符合线性表的定义，数组就是一种线性表，这种顺序存储的线性表叫做线性表的顺序存储结构。
我们也知道，顺序存储是很耗费存储空间的，所以，还有一种存储方式，叫做链式存储。
计算机存储线性表的方式有两种：顺序存储和链式存储。
五、顺序存储结构
什么是顺序存储结构?
线性表的顺序存储，指的是用一段连续的地址单元依次存储线性表的数据元素。
示意图：
是不是跟数组的存储很像啊？
所以，通常，在程序设计语言中，我们使用一维数组来实现顺序存储结构。把线性表的第一个元素放在数组的第0个位置，接着把相邻的元素依次存放。
数据结构：
// 定义顺序存储线性表
//定义线性表的最大存储空间为20
#define MaxSize 20
//定义元素的数据类型为int
typedef int ElemType;
typedef struct List * PtrToNode;
struct List {
//定义数组data，存储线性表的元素，最大值为MaxSize
ElemType data[MaxSize];
//线性表的当前长度
int length;
};
typedef PtrToNode SqList;
六、顺序线性表的常用操作代码实现（C语言）
编辑器：Xcode
详细步骤（老手跳过）：
1.xcode新建项目
2.点击右下方『Next』，输入项目名字，中英文都可以，建议英文，选择语言为『C』。中间的部分，输入什么都可以，这里不做解释。
3.选个位置保存，这里保存到桌面。
4.点击『Create』，就创建了一个空项目，如下图：
5.创建OrderList文件。
点击Xcode菜单栏的File->New->File,如下图：
在弹出的对话框里选择『C File』，如下图：
点击『Next』，给文件起名字『OrderList』，文件名下方的对勾不要去掉，我们选择建一个header file。
点击『Next』，然后『Create』：
这样，我们的OrderList文件就建成了。
接下来就是我们的编码时间了。
1、定义顺序存储线性表的结构体以及操作声明
在OrderList.h中声明：
//
// OrderList.h
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#ifndef OrderList_h
#define OrderList_h
#include <stdio.h>
// 定义顺序存储线性表
#define True 1
#define False 0
#define Success 1
#define Fail 0
//定义线性表的最大存储空间为20
#define MaxSize 20
//定义元素的数据类型为int
typedef int ElemType;
typedef struct List * PtrToNode;
struct List {
//定义数组data，存储线性表的元素，最大值为MaxSize
ElemType data[MaxSize];
//线性表的当前长度
int length;
};
typedef PtrToNode SqList;
//操作
//初始化线性表
SqList initList(void);
//线性表是否为空
int isListEmpty(SqList L);
//清空线性表
int clearList(SqList L);
//打印线性表
void printList(SqList L);
#endif /* OrderList_h */
在OrderList.c中实现声明的操作。
//
// OrderList.c
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#include "OrderList.h"
//初始化线性表
SqList initList(void){
SqList L = (SqList)malloc(sizeof(struct List));
L->length = 0;
printf("请先输入线性表的长度：");
scanf("%d",&( L->length));
printf("请输入线性表的元素,以空格隔开：\n");
for (int i = 0; i< L->length; i++) {
scanf("%d", &(L->data[i]));
}
return L;
}
//线性表是否为空
int isListEmpty(SqList L){
return L->length > 0 ? False : True;
}
//清空线性表
int clearList(SqList L){
for (int i = 0; i < L->length; i++) {
L->data[i] = 0;
}
L->length = 0;
return True;
}
//打印线性表
void printList(SqList L) {
printf("当前线性表的元素如下：\n");
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[I]);
}
printf("\n");
}
在main.c中，试验代码是否好用。
1.创建
//
// main.c
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#include <stdio.h>
#include "OrderList.h"
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
//1、创建顺序存储的线性表
SqList list1 = initList();
printList(list1);
return 0;
}
打印结果：
2.线性表是否为空
//2、判断线性表是否为空
int isEmpty = isListEmpty(list1);
isEmpty == True ? printf("线性表为空\n") : printf("线性表不为空\n");
打印结果：
3.清空线性表
//3、清空线性表
clearList(list1);
//验证是否为空
printList(list1);
int isEmpty2 = isListEmpty(list1);
isEmpty2 == True ? printf("线性表为空\n") : printf("线性表不为空\n");
打印：
4、插入线性表
实现思路：
1.把index开始，直到最后的每一个元素都向后移动一位；
2.把待插入的元素x插入到index的位置上；
3.线性表的长度加1 。
4.异常情况处理，比如插入位置不合理，线性表已满等。
在OrderList.h中添加如下代码,声明函数insertList：
/**
在线性表中插入元素
L:待插入元素的线性表
x：待插入的元素
index：待插入的位置
*/
int insertList(SqList L, ElemType x, int index );
在OrderList.c中添加如下代码,实现插入功能：
/**
在线性表中插入元素
L:待插入元素的线性表
x：待插入的元素
index：待插入的位置
*/
int insertList(SqList L, ElemType x, int index ){
if (L->length == MaxSize) {
//线性表已满
printf("线性表已满,插入新元素%d失败", x);
return Fail;
}
if (index < 0 || (L->length + 1) > MaxSize) {
printf("您选择插入的位置不正确，插入失败");
return Fail;
}
if (L->length == 0) {
//当前是空表，直接在第一个位置插入
printf("当前是空表，无法插入指定位置，只能插入到第一个位置\n");
L->data[0] = x;
L->length++;
}
if (index <= L->length) {
//先把从index开始到最后的元素后移一个位置，把第index个位置腾出来
for (int k = L->length - 1; k >= index -1; k--) {
L->data[k+1] = L->data[k];
}
L->data[index] = x;
L->length++;
printf("插入成功\n");
}
return Success;
}
在 main.c中验证：
//
// main.c
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#include <stdio.h>
#include "OrderList.h"
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
//1、创建顺序存储的线性表
SqList list1 = initList();
printList(list1);
//2、判断线性表是否为空
int isEmpty = isListEmpty(list1);
isEmpty == True ? printf("线性表为空\n") : printf("线性表不为空\n");
//3、清空线性表
clearList(list1);
//验证是否为空
printList(list1);
int isEmpty2 = isListEmpty(list1);
isEmpty2 == True ? printf("线性表为空\n") : printf("线性表不为空\n");
//4、插入线性表
//空表插入
insertList(list1, 100, 2);
printList(list1);
//插入队尾
insertList(list1, 1, 1);
printList(list1);
//插入队头
insertList(list1, 6, 0);
printList(list1);
//插入中间
insertList(list1, 20, 1);
printList(list1);
return 0;
}
打印结果：
5、查找元素是否存在
OrderList.h添加：
//查找某个元素是否存在于线性表,如果存在返回该元素的位置，否则返回-1.
int isExist(SqList L, ElemType x);
在OrderList.c添加实现：
//查找某个元素是否存在于线性表,如果存在返回该元素的位置，否则返回-1.
int isExist(SqList L, ElemType x) {
for (int i = 0; i<L->length; i++) {
if (L->data[i] == x) {
printf("查找到元素%d的位置是%d \n", x, i);
return I;
}
}
printf("😭元素不存在\n");
return -1;
}
在main.c中测试：
//5.是否存在某元素
isExist(list1, 3);
打印：
6、删除某个元素
删除某个元素有两种删除的方法，一种是给出一个元素删除，另一种是给出一个位置删除。这里把两种方法都给出了。
OrderList.h：
/**
根据元素，在线性表中删除元素
L:待删除元素的线性表
x：待删除的元素
*/
int deleteListWithElem(SqList L, ElemType x);
/**
根据位置，在线性表中删除元素
L:待删除元素的线性表
index：待删除的元素的位置
*/
int deleteListAtIndex(SqList L, int index);
OrderList.c:
/**
在线性表中删除元素
L:待删除元素的线性表
x：待删除的元素
index：待删除的位置
*/
int deleteListWithElem(SqList L, ElemType x){
//1.判断元素x是否存在于线性表
int i = isExist(L, x);
if (i > -1) {
for (int k = i + 1; k <= L->length; k ++) {
L->data[k-1] = L->data[k];
}
L->length--;
printf("删除元素 %d 成功\n", x);
return Success;
} else {
printf("元素%d不存在，无法删除\n",x);
return Fail;
}
}
/**
根据位置，在线性表中删除元素
L:待删除元素的线性表
index：待删除的元素的位置
*/
int deleteListAtIndex(SqList L, int index){
if ((index >=0)&&(index <= L->length)) {
for (int k = index + 1; k <= L->length; k++) {
L->data[k-1] = L->data[k];
}
L->length--;
printf("删除第%d个元素 成功\n", index);
return Success;
}else {
printf("您要删除的元素位置不存在，删除失败\n");
return Fail;
}
}
main.c中：
//6.删除某元素x
deleteListWithElem(list1, 2);
printList(list1);
//7.删除第2个位置上的元素
deleteListAtIndex(list1, 2);
printList(list1);
//8.系统测试删除(按照元素)
SqList list2 = initList();
printList(list2);
int x = 0;
while (x != -1) {
printf("请输入要删除的元素，按「-1」退出\n");
scanf("%d", &x);
deleteListWithElem(list2, x);
printList(list2);
}
//9.系统测试删除(按照位置)
SqList list3 = initList();
printList(list3);
int y = 0;
while (y != -1) {
printf("请输入要删除的元素位置，按「-1」退出\n");
scanf("%d", &y);
deleteListAtIndex(list3, y);
printList(list3);
}
打印结果：
接上：
接上：
说明：这只是测试程序，并没有考虑元素中含有-1的情况，只是为了方便测试而已。
完整程序如下：
OrderList.h:
//
// OrderList.h
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#ifndef OrderList_h
#define OrderList_h
#include <stdio.h>
// 定义顺序存储线性表
#define True 1
#define False 0
#define Success 1
#define Fail 0
//定义线性表的最大存储空间为20
#define MaxSize 20
//定义元素的数据类型为int
typedef int ElemType;
typedef struct List * PtrToNode;
struct List {
//定义数组data，存储线性表的元素，最大值为MaxSize
ElemType data[MaxSize];
//线性表的当前长度
int length;
};
typedef PtrToNode SqList;
//操作
//初始化线性表
SqList initList(void);
//线性表是否为空
int isListEmpty(SqList L);
//清空线性表
int clearList(SqList L);
/**
在线性表中插入元素
L:待插入元素的线性表
x：待插入的元素
index：待插入的位置
*/
int insertList(SqList L, ElemType x, int index );
//查找某个元素是否存在于线性表,如果存在返回该元素的位置，否则返回-1.
int isExist(SqList L, ElemType x);
/**
根据元素，在线性表中删除元素
L:待删除元素的线性表
x：待删除的元素
*/
int deleteListWithElem(SqList L, ElemType x);
/**
根据位置，在线性表中删除元素
L:待删除元素的线性表
index：待删除的元素的位置
*/
int deleteListAtIndex(SqList L, int index);
//打印线性表
void printList(SqList L);
#endif /* OrderList_h */
OrderList.c:
//
// OrderList.c
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#include "OrderList.h"
//初始化线性表
SqList initList(void){
SqList L = (SqList)malloc(sizeof(struct List));
L->length = 0;
printf("请先输入线性表的长度：");
scanf("%d",&( L->length));
printf("请输入线性表的元素,以空格隔开：\n");
for (int i = 0; i< L->length; i++) {
scanf("%d", &(L->data[i]));
}
return L;
}
//线性表是否为空
int isListEmpty(SqList L){
return L->length > 0 ? False : True;
}
//清空线性表
int clearList(SqList L){
for (int i = 0; i < L->length; i++) {
L->data[i] = 0;
}
L->length = 0;
printf("线性表已经被清空了\n");
return True;
}
/**
在线性表中插入元素
L:待插入元素的线性表
x：待插入的元素
index：待插入的位置
*/
int insertList(SqList L, ElemType x, int index ){
if (L->length == MaxSize) {
//线性表已满
printf("线性表已满,插入新元素%d失败", x);
return Fail;
}
if (index < 0 || (L->length + 1) > MaxSize) {
printf("您选择插入的位置不正确，插入失败");
return Fail;
}
if (L->length == 0) {
//当前是空表，直接在第一个位置插入
printf("当前是空表，无法插入指定位置，只能插入到第一个位置\n");
L->data[0] = x;
L->length++;
}
if (index <= L->length) {
//先把从index开始到最后的元素后移一个位置，把第index个位置腾出来
for (int k = L->length - 1; k >= index -1; k--) {
L->data[k+1] = L->data[k];
}
L->data[index] = x;
L->length++;
printf("插入成功\n");
}
return Success;
}
//查找某个元素是否存在于线性表,如果存在返回该元素的位置，否则返回-1.
int isExist(SqList L, ElemType x) {
for (int i = 0; i<L->length; i++) {
if (L->data[i] == x) {
printf("查找到元素%d的位置是%d \n", x, i);
return i;
}
}
printf("😭元素不存在\n");
return -1;
}
/**
在线性表中删除元素
L:待删除元素的线性表
x：待删除的元素
index：待删除的位置
*/
int deleteListWithElem(SqList L, ElemType x){
//1.判断元素x是否存在于线性表
int i = isExist(L, x);
if (i > -1) {
for (int k = i + 1; k <= L->length; k ++) {
L->data[k-1] = L->data[k];
}
L->length--;
printf("删除元素 %d 成功\n", x);
return Success;
} else {
printf("元素%d不存在，无法删除\n",x);
return Fail;
}
}
/**
根据位置，在线性表中删除元素
L:待删除元素的线性表
index：待删除的元素的位置
*/
int deleteListAtIndex(SqList L, int index){
if ((index >=0)&&(index <= L->length)) {
for (int k = index + 1; k <= L->length; k++) {
L->data[k-1] = L->data[k];
}
L->length--;
printf("删除第%d个元素 成功\n", index);
return Success;
}else {
printf("您要删除的元素位置不存在，删除失败\n");
return Fail;
}
}
//打印线性表
void printList(SqList L) {
printf("当前线性表的元素如下：\n");
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\n");
}
main.c:
//
// main.c
// 线性表的顺序存储
//
// Created by wenhuanhuan on 2019/6/28.
// Copyright © 2019 weiman. All rights reserved.
//
#include <stdio.h>
#include "OrderList.h"
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
//1、创建顺序存储的线性表
SqList list1 = initList();
printList(list1);
//2、判断线性表是否为空
int isEmpty = isListEmpty(list1);
isEmpty == True ? printf("线性表为空\n") : printf("线性表不为空\n");
//3、清空线性表
clearList(list1);
//验证是否为空
printList(list1);
int isEmpty2 = isListEmpty(list1);
isEmpty2 == True ? printf("线性表为空\n") : printf("线性表不为空\n");
//4、插入线性表
//空表插入
insertList(list1, 100, 2);
printList(list1);
//插入队尾
insertList(list1, 1, 1);
printList(list1);
//插入队头
insertList(list1, 6, 0);
printList(list1);
//插入中间
insertList(list1, 20, 1);
printList(list1);
//5.是否存在某元素
isExist(list1, 3);
//6.删除某元素x
deleteListWithElem(list1, 2);
printList(list1);
//7.删除第2个位置上的元素
deleteListAtIndex(list1, 2);
printList(list1);
//8.系统测试删除(按照元素)
SqList list2 = initList();
printList(list2);
int x = 0;
while (x != -1) {
printf("请输入要删除的元素，按「-1」退出\n");
scanf("%d", &x);
deleteListWithElem(list2, x);
printList(list2);
}
//9.系统测试删除(按照位置)
SqList list3 = initList();
printList(list3);
int y = 0;
while (y != -1) {
printf("请输入要删除的元素位置，按「-1」退出\n");
scanf("%d", &y);
deleteListAtIndex(list3, y);
printList(list3);
}
return 0;
}
七、顺序存储的线性表的优缺点
我们根据第二章学习的时间复杂度的计算方法，不难得出，顺序存储的线性表的插入和删除的时间复杂度为O(n)，读取的时间复杂度为O(1)。
优点：
1、不存逻辑关系
顺序存储的线性表无须为表中元素之间的逻辑关系而额外的增加存储空间。
2、快速存取
可以快速地取出表中任意位置的元素。
缺点：
1、增删耗时
插入和删除操作需要移动大量的元素。
2、存储空间不定
当线性表长度变化比较大的时候，难以确定存储空间的容量。
3、浪费内存
因为是顺序存储，地址是连续的。就会造成内存中有很多小的空间无法使用或者不能更多的利用，造成空间的浪费。
八、思考：一维数组与顺序存储线性表的关系
从上面的代码中不难看出，在程序设计语言中，我们使用一维数组来实现顺序存储的线性表的数据部分，但是顺序存储的线性表并不就是一维数组。也可以说，顺序存储的数据区域就是用一维数组来表示的。顺序线性表是一种结构，一种概念，具体的实现方式我们使用了一维数组。这是个人理解，如有疏漏，请指出。
纸上得来终觉浅，绝知此事要躬行。有条件的话，一定要自己实现一下试试。
