前言
文章目的在于记录学习数据结构这门课程中遇到的知识点以及难点，为解决或优化实际代码问题打好基础
一、线性表是什么？
线性结构
想要理解线性表，首先明确一个概念：线性结构
线性结构有以下特点：
1. 存在唯一的首元素（被称为第一个的数据元素）
2. 存在唯一的末元素（被称为最后一个的数据元素）
3. 除第一个元素之外，集合中的每个数据元素均只有一个前驱
4. 除最后一个元素之外，集合中的每个数据元素均只有一个后继
我们要讨论的线性表便是线性结构的一员，除此，栈、队列、串也是常见的线性结构。
线性表
线性表是一种最常用也最简单的数据结构，它是n个数据元素的有限序列。这里的数据元素不能狭隘地理解为数字，它在不同的应用场景下有不同的具体含义
- 在稍复杂的线性表中，一个数据元素可以由若干个数据项（item） 组成。这种情况下，我们把数据元素称为记录（record） ，含有大量记录的线性表又称为文件（file）
二、线性表的顺序表示和实现
1.什么是线性表的顺序表示
- 概念：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素
这是什么意思呢？
这里的重点也是顺序表的特点：
数据元素的次序排列在逻辑层面与物理层面的统一性，也就是数据元素在线性表中的次序与其存储地址次序的统一。
设线性表的每个元素需要占l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储地址 ，则线性表的第i+1个数据元素的存储位置 LOC(a_i+1) 和第i个数据元素的存储位置 LOC(a_i) 满足以下关系
LOC(a_i+1) = LOC(a_i) + l
打个不太有趣的比方，森林里七个小矮人各有一间小木屋，老大的小木屋叫一号木屋，老二的小木屋叫二号木屋，一直到老七的小木屋叫七号木屋，同时这七间小木屋也是按照从东往西依次排列的。每个木屋就是一个数据元素，这七间木屋看做一个顺序表，从东向西第一间就是一号木屋，第五间就是五号木屋。倘若老二和老三换了个房间，那这个线性表便不再是顺序的表示。
2.代码实现
1、线性表的常用操作
（1） InitList(& L)
//构造一个空的线性表
（2） DestroyList(& L)
//线性表存在了，消耗一个线性表
（3） ClearList（&L ）
//清空线性表中的内容
（4） ListEmpty（L）
//判断线性表是否为空
（5） ListLength（L）
//返回线性表的长度
（6） GetElem（L，i，& e）
//返回线性表i位置上的元素值，通过e返回
（7） PriorElem（L，cur_e,&pre_e）
//如果cur_e是线性表中的元素，而且不是第一个，那么我们就可以返回该元素前一个元素的值
（8） NextElem（L，cur_e,&next_e）
//如果cur_e是线性表中的元素，而且不是最后一个，就返回它下一个元素的值
（9） Listinsert(&L,i,e)
//如果线性表存在了，而且i符合条件，则在i位置插入一个元素
（10）ListDelete（&L,i）
//删除i位置上的元素
（11） ListDelete_data(&L,e,order)
//删除指定的元素e，order决定是删除一个，还是全部。
（12） Connect_two_List(L_a,L_b,& L_c)
//连接两个线性表，除去重复的内容
（13）print(L)
//打印线性表
2、线性表的动态分配顺序存储结构：
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct
{
ElemType elem; // 存储空间基址
int length; // 顺序表当前长度
int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位）
}SqList; // 顺序表类型
3、线性表顺序表示实现–initList函数
创建空表、分配内存
//创建一个空的线性表
void InitList(List & newList) {
//初始容量为startsize
newList.size = startsize;
//首先开辟空间
newList.data = new Elemtype[newList.size];
//空表，长度是0
newList.length = 0;
}
4、线性表顺序表示实现–DestroyList函数
//线性表存在了，现在要销毁线性表
void DestroyList(List & newList) {
newList.length = 0;
newList.data = 0;
//一定要先释放堆内存
delete[] newList.data;
//没此释放堆内存后，并将对应的指针赋予NULL是一个良好的习惯
newList.data = NULL;
}
5、线性表顺序表示实现–ClearList函数
//线性表存在了，但是现在想清空整个线性表
void ClearList(List & newList) {
newList.length = 0;
//一定要先释放堆内存
delete[] newList.data;
//没此释放堆内存后，并将对应的指针赋予NULL是一个良好的习惯
newList.data = NULL;
//重新为存放元素的变量开辟一个新的堆内存
newList.data = new Elemtype[newList.size];
}
6、线性表顺序表示实现–ListEmpty函数
//判读线性表是否为空
bool ListEmpty(List newList) {
return newList.length;
}
7、线性表顺序表示实现–ListLength函数
//返回线性表的长度
int ListLength(List newList) {
return newList.length;
}
8、线性表顺序表示实现–GetElem函数
//返回线性表上某个位置上的元素的值,记住我们的位置是从1开始计算的。
void GetElem(List newList, int i, Elemtype &e) {
if (ListEmpty(newList)) {
cout << "当前线性表是空表" << endl;
return;
}
if (i<1 || i>newList.length) {
cout << "当前位置超出了线性表的范围" << endl;
return;
}
e = newList.data[i - 1];
}
因为我们是通过下标进行查找对应的元素的，所以它的时间复杂度为：O(1),这个和我们后边说的链式结构的查找比起来，是占了很大优势的
9、线性表顺序表示实现–PriorElem函数
//判读元素的位置的函数
//我们这里直接返回该元素的下标
int LocationElem(List newList, Elemtype e){
int i;
for (i = 0; i < newList.length; i++) {
if (newList.data[i] == e) {
return i;
}
}
return -1;
}
这个函数的时间复杂为：假定我们有n个元素，那么它的查找时间复杂为O(n),但是因为我们使用的是顺序结构，所以我们可以很方便的使用其他可以减低时间复杂的查找算法，例如二分查找，它的时间复杂度为：O(logn)
//获取前驱的元素
void PriorElem(List newList, Elemtype cur_e, Elemtype & pre_e) {
int location = 0;
location = LocationElem(newList, cur_e);
//如果Location是-1，说明cur_e不在线性表中
if (location == -1) {
cout <<cur_e<< "不在线性表中" << endl;
return;
}
//如果Location是0，说明cur_e在线性表第一个位置，没有前一个元素
if (location == 0)
{
cout << cur_e << "是线性表的第一个元素，没有前驱" << endl;
return;
}
pre_e = newList.data[location - 1];
}
10、线性表顺序表示实现–NextElem函数
//获取后驱元素
void NextElem(List newList, Elemtype cur_e, Elemtype & next_e) {
int location = 0;
location = LocationElem(newList, cur_e);
//如果Location是-1，说明cur_e不在线性表中
if (location == -1) {
cout << cur_e << "不在线性表中" << endl;
return;
}
//如果Location是0，说明cur_e在线性表最后一个位置，没有后一个元素
if (location == newList.length-1)
{
cout << cur_e << "是线性表的最后一个元素，没有后驱" << endl;
return;
}
next_e = newList.data[location - 1];
}
11、线性表顺序表示实现–Listinsert函数
//向线性表中插入一个元素，这里我们需要判断插入位置是否合法
//除此之外，我们还需要检测元素的容量是否已经到达了最大值
void Listinsert(List & newList, int i, Elemtype e) {
//插入的位置不合法
if (i<1 || i>newList.length+1) {
cout << "请检查插入位置是否正确" << endl;
return;
}
int j = 0;
//此时达到了线性表的最大容量，我们需要重新为线性表分配新的内存。
if (newList.length == newList.size) {
//先保存之前的内容。
Elemtype * p =new Elemtype[newList.length];
for (j = 0; j < newList.length; j++) {
p[j] = newList.data[j];
}
//扩大容量
newList.size += sizestep;
delete[] newList.data;
//重新分配内存
newList.data = new Elemtype[newList.size];
//恢复之前内容
for (j = 0; j < newList.length; j++) {
newList.data[j] = p[j];
}
}
//插入内容
for (int k = newList.length; k >i-1; k-- ){
newList.data[k]=newList.data[k-1];
}
newList.data[i - 1] = e;
++newList.length;
}
12、线性表顺序表示实现–Listdelete函数
//线性表删除一个元素，我们需要判断删除的位置是否合法
void Listdelete(List & newList, int i) {
//删除的位置不合法
if (i<1 || i>newList.length) {
cout << "请检查插入位置是否正确" << endl;
return;
}
for (int j = i - 1; j < newList.length; j++) {
newList.data[j] = newList.data[j + 1];
}
--newList.length;
}
对于顺序存储结构的线性表，要想在表中某个位置插入或删除一个数据元素的时候，时间主要耗费在移动元素上，且移动元素的个数取决于插入或删除元素的位置。若表长为n，该算法的时间复杂度为O(n)
13、线性表顺序表示实现–Listdelete_data函数
//按照元素的值，来删除对应元素的内容，
//这个时候我们通过传个参数，来决定我们是删除第一个该元素，
//0,删除一个，1，删除所有
//还是把所有的元素都给删除了
//如果不存在该元素，就直接返回
void Listdelete_data(List & newList, Elemtype e,int order) {
int flag=0;
for (int i = 0; i < newList.length; i++) {
if (newList.data[i] == e) {
flag=1;
//删除对应的位置上的元素，而且i也要减少一个
Listdelete(newList, i + 1);
--i;
if (order == 0) {
return;
}
}
}
if(flag==1)
return ;
cout << e << "不在线性表中" << endl;
}
14、线性表顺序结构表示实现–Connect_two_List函数
//连接两个线性表
void Connect_two_List(List a, List b, List & c) {
//对c进行一些数据初始化
c.length = c.size = a.length + b.length;
c.data = new Elemtype[c.size];
//这里采用指针的方式进行数据的移动,我们先把a和b数据第一个和最后一个元素的位置找出来
int i = 0;
int j = 0;
int k = 0;
while (i <= a.length-1 && j<= b.length-1) {
if (a.data[i] < b.data[j])
{
c.data[k++] = a.data[i++];
}
else if(a.data[i] > b.data[j]) c.data[k++] = b.data[j++];
else {
c.data[k++] = b.data[j++]; i++; --c.length;
}
}
while (i <= a.length - 1)
{
c.data[k++] = a.data[i++];
}
while (j <= b.length - 1)
{
c.data[k++] = b.data[j++];
}
}
15、线性表顺序结构表示实现–print函数
void print(List & L) {
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
}
总结
本文记录了线性表的一些基本概念和常见操作，总体来说是比较简单的。下一篇文章将记录链表的有关知识。
参考资料
- 《数据结构（C语言版）》 清华大学出版社
- 数据结构-线性表详解 @Ouyang_Lianjun
再次感谢
