第二章 线性表

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客

文末附完整测试程序代码

2.2 线性表的顺序表示

顺序表的定义

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储空间来依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点为：表中元素的逻辑顺序与物理顺序相同。

我们顺序表的定义也可以根据数组的分配类型来分为动态分配和静态分配。

2.2.1 顺序表-静态分配内存

存储结构定义：

假定线性表的元素类型为ElemType，则顺序表的静态分配的存储类型描述为：

#define MaxSize 50 // 定义顺序表-顺序实现的最大长度 typedef struct {  ElemType data[MaxSize]; // 定义数组data，用来存储线性表中的元素 数据类型为ElemType int length; // 当前线性表的表长 }SqList;// 顺序表的类型定义 

这是顺序表-静态分配内存的存储类型的定义，这里的数组长度是不可更改的，一旦空间占满，再加入新的数据将会产生溢出，导致程序奔溃，因此我们顺序表一般会采用动态分配内存空间的方法，来提高我们的可用性。

下面我们来实现我们顺序表-静态分配内存的一些基本操作。

（1）初始化操作 InitList(&L);

静态分配内存的初始化操作只需将length赋值为0即可，代码实现为：

// 初始化操作 bool InitList(SqList &L) {  L.length = 0; return true; } 

（2）按值查找操作LocateElem(L,e);

// 按值查找操作 int LocateElem(SqList L, ElemType e) { int i;//记录下标 for (i = 0; i < L.length; i++) { if (L.data[i] == e)//查找到时，返回i+1，因为线性表下标从1开始。 return i + 1; } return 0;//未查找到时，返回0，线性表下标从1开始，所以返回0可以用来表示未查找到 } 

（3）按位查找操作GetElem(L,i);

// 按位查找操作 int GetElem(SqList L, int i){ if (i<1 || i>L.length)// 下标i的数值错误 return -1; return L.data[i-1];//返回该位置的数值 } 

（4）插入操作ListInsert(&L,i,e);

// 插入操作 bool ListInsert(SqList& L, int i, ElemType e) { // 插入操作一般默认为头插法 if (i<1 || i>L.length+1)// 下标i的数值错误 return false; if (L.length >= MaxSize)//当前存储空间已满 return false; for (int j = L.length; j >= i; j--) {//将第i到length个元素后移   L.data[j] = L.data[j - 1]; }  L.data[i - 1] = e;// 为L中第i个元素赋值  L.length++;//L的表长+1 return true; } 

（5）删除操作ListDelete(&L, i);

// 删除操作 bool ListDelete(SqList& L, int i, ElemType &e) { if (i<1 || i>L.length)// 下标i的数值错误 return false;  e = L.data[i - 1];//给e赋值为删除的元素 for (int j = i; j < L.length; j++) {//将第i到length个元素前移   L.data[j-1] = L.data[j]; }  L.length--;//L的表长减一 return true; } 

（6）求表长操作Length(L);

// 求表长操作 int Length(SqList L) { return L.length; } 

（7）判空操作Empty(L);

// 判空操作 bool Empty(SqList L) { if (L.length == 0) return true; return false; } 

（8）输出操作PrintList(L);

// 输出操作 void PrintList(SqList L) {  cout << "L的元素为："; for (int i = 0; i < L.length; i++) {   cout << L.data[i]<<" "; }  cout << endl; } 

（9）销毁操作Destory(&L);

// 销毁操作 bool Destory(SqList& L) { // 这里是静态分配的，不需要手动回收，不使用时会自动进行回收 return true; } 

完整测试运行程序

#include<iostream> using namespace std; typedef int ElemType; #define MaxSize 50 // 定义顺序表-顺序实现的最大长度 typedef struct {  ElemType data[MaxSize]; // 定义数组data，用来存储线性表中的元素 数据类型为ElemType int length; // 当前线性表的表长 }SqList;// 顺序表的类型定义 // 初始化操作 bool InitList(SqList &L) {  L.length = 0; return true; } // 按值查找操作 int LocateElem(SqList L, ElemType e) { int i;//记录下标 for (i = 0; i < L.length; i++) { if (L.data[i] == e)//查找到时，返回i+1，因为线性表下标从1开始。 return i + 1; } return 0;//未查找到时，返回0，线性表下标从1开始，所以返回0可以用来表示未查找到 } // 按位查找操作 int GetElem(SqList L, int i){ if (i<1 || i>L.length)// 下标i的数值错误 return -1; return L.data[i-1];//返回该位置的数值 } // 插入操作 bool ListInsert(SqList& L, int i, ElemType e) { // 插入操作一般默认为头插法 if (i<1 || i>L.length+1)// 下标i的数值错误 return false; if (L.length >= MaxSize)//当前存储空间已满 return false; for (int j = L.length; j >= i; j--) {//将第i到length个元素后移   L.data[j] = L.data[j - 1]; }  L.data[i - 1] = e;// 为L中第i个元素赋值  L.length++;//L的表长+1 return true; } // 删除操作 bool ListDelete(SqList& L, int i, ElemType &e) { if (i<1 || i>L.length)// 下标i的数值错误 return false;  e = L.data[i - 1];//给e赋值为删除的元素 for (int j = i; j < L.length; j++) {//将第i到length个元素前移   L.data[j-1] = L.data[j]; }  L.length--;//L的表长减一 return true; } // 求表长操作 int Length(SqList L) { return L.length; } // 判空操作 bool Empty(SqList L) { if (L.length == 0) return true; return false; } // 输出操作 void PrintList(SqList L) {  cout << "L的元素为："; for (int i = 0; i < L.length; i++) {   cout << L.data[i]<<" "; }  cout << endl; } // 销毁操作 bool Destory(SqList& L) { // 这里是静态分配的，不需要手动回收，不使用时会自动进行回收 return true; } int main() {  SqList L;  cout << "初始化顺序表L：" << endl; if (InitList(L)) {   cout << "初始化顺序表L成功！" << endl; } else {   cout << "初始化顺序表L失败！" << endl; }  cout << "现在L的表长为：" << Length(L) << endl;  cout << "为L插入1 2 3 4 5，共5个元素：" << endl; for (int i = 1; i <= 5; i++){ ListInsert(L, i, i); }  cout << "插入成功！" << endl; PrintList(L);  cout << "在L的第2个位置插入元素 66：" << endl; ListInsert(L, 2, 66);  cout << "插入成功！" << endl; PrintList(L);  cout << "删除L中第三个元素：" << endl;  ElemType e; ListDelete(L, 3, e);  cout << "删除的元素为：" << e << endl; PrintList(L);  cout << "线性表中值为5的元素的位置为：" << LocateElem(L, 5) << endl; return 0; } 

程序输出为：

初始化顺序表L： 初始化顺序表L成功！ 现在L的表长为：0 为L插入1 2 3 4 5，共5个元素： 插入成功！ L的元素为：1 2 3 4 5 在L的第2个位置插入元素 66： 插入成功！ L的元素为：1 66 2 3 4 5 删除L中第三个元素： 删除的元素为：2 L的元素为：1 66 3 4 5 线性表中值为5的元素的位置为：5 

2.2.2 顺序表-动态分配内存

静态分配内存的数组长度是不可更改的，一旦空间占满，再加入新的数据将会产生溢出，导致程序奔溃，因此我们顺序表一般会采用动态分配内存空间的方法，来提高我们的可用性。

使用动态分配内存来实现我们的顺序表，存储数组的大小可以根据我们的实际需要，来进行动态的分配。一旦数据空间占满，我们就可以开辟一块更大的空间用来存放我们的数据元素。

顺序表-动态分配内存的存储结构定义为：

#define InitSize 50 // 定义我们初始化时的大小 typedef struct {  ElemType *data; // 定义一个指针data,用来存储数据元素 int length; // 当前线性表的表长 int listsize;// 当前内存空间的长度 }SqList;// 顺序表的类型定义 

下面我们来实现我们的9中基本操作：

（1）初始化操作 InitList((&L);

// 初始化操作 bool InitList(SqList &L) {  L.data = (ElemType*)malloc(InitSize * sizeof(ElemType)); // C++也可以使用L.data = new ElemType[InitSize];来进行分配内存空间 if (!L.data) { // 当L.data为空时，即分配内存空间失败，返回false return false; }  L.length = 0; // 表长初始化为0  L.listsize = InitSize;//为listsize赋值为当前申请的内存空间的大小。 return true; } 

（2）按值查找操作LocateElem(L,e);

// 按值查找操作 int LocateElem(SqList L, ElemType e) { int i;//记录下标 for (i = 0; i < L.length; i++) { if (L.data[i] == e)//查找到时，返回i+1，因为线性表下标从1开始。 return i + 1; } return 0;//未查找到时，返回0，线性表下标从1开始，所以返回0可以用来表示未查找到 } 

（3）按位查找操作GetElem(L,i);

// 按位查找操作 int GetElem(SqList L, int i){ if (i<1 || i>L.length)// 下标i的数值错误 return -1; return L.data[i-1];//返回该位置的数值 } 

（4）插入操作ListInsert(&L,i,e);

// 插入操作 bool ListInsert(SqList& L, int i, ElemType e) { // 插入操作一般默认为头插法 if (i<1 || i>L.length+1)// 下标i的数值错误 return false; if (L.length >= L.listsize) { //当前存储空间已满，分配更大的一块空间。 // 这里新分配的内存空间是之前的内存空间的2倍   ElemType* newbase = (ElemType*)realloc(L.data,L.listsize * 2 * sizeof(ElemType)); if (!newbase) { // 分配内存空间失败 return false; }   L.data = newbase;   L.listsize = L.listsize * 2; } for (int j = L.length; j >= i; j--) {//将第i到length个元素后移   L.data[j] = L.data[j - 1]; }  L.data[i - 1] = e;// 为L中第i个元素赋值  L.length++;//L的表长+1 return true; } 

（5）删除操作ListDelete(&L, i,e);

// 删除操作 bool ListDelete(SqList& L, int i, ElemType &e) { if (i<1 || i>L.length)// 下标i的数值错误 return false;  e = L.data[i - 1];//给e赋值为删除的元素 for (int j = i; j < L.length; j++) {//将第i到length个元素前移   L.data[j-1] = L.data[j]; }  L.length--;//L的表长减一 return true; } 

（6）求表长操作Length(L);

// 求表长操作 int Length(SqList L) { return L.length; } 

（7）判空操作Empty(L);

// 判空操作 bool Empty(SqList L) { if (L.length == 0) return true; return false; } 

（8）输出操作PrintList(L);

// 输出操作 void PrintList(SqList L) {  cout << "L的元素为："; for (int i = 0; i < L.length; i++) {   cout << L.data[i]<<" "; }  cout << endl; } 

（9）销毁操作Destory(&L);

// 销毁操作 bool Destory(SqList& L) { free(L.data); if (!L.data) return true; else return false; } 

完整测试程序为：

#include<iostream> #include<cstdlib> using namespace std; typedef int ElemType; #define InitSize 50 // 定义我们初始化时的大小 typedef struct {  ElemType *data; // 定义一个指针data,用来存储数据元素 int length; // 当前线性表的表长 int listsize;// 当前内存空间的长度 }SqList;// 顺序表的类型定义 // 初始化操作 bool InitList(SqList &L) {  L.data = (ElemType*)malloc(InitSize * sizeof(ElemType)); // C++也可以使用L.data = new ElemType[InitSize];来进行分配内存空间 if (!L.data) { // 当L.data为空时，即分配内存空间失败，返回false return false; }  L.length = 0; // 表长初始化为0  L.listsize = InitSize;//为listsize赋值为当前申请的内存空间的大小。 return true; } // 按值查找操作 int LocateElem(SqList L, ElemType e) { int i;//记录下标 for (i = 0; i < L.length; i++) { if (L.data[i] == e)//查找到时，返回i+1，因为线性表下标从1开始。 return i + 1; } return 0;//未查找到时，返回0，线性表下标从1开始，所以返回0可以用来表示未查找到 } // 按位查找操作 int GetElem(SqList L, int i){ if (i<1 || i>L.length)// 下标i的数值错误 return -1; return L.data[i-1];//返回该位置的数值 } // 插入操作 bool ListInsert(SqList& L, int i, ElemType e) { // 插入操作一般默认为头插法 if (i<1 || i>L.length+1)// 下标i的数值错误 return false; if (L.length >= L.listsize) { //当前存储空间已满，分配更大的一块空间。 // 这里新分配的内存空间是之前的内存空间的2倍   ElemType* newbase = (ElemType*)realloc(L.data,L.listsize * 2 * sizeof(ElemType)); if (!newbase) { // 分配内存空间失败 return false; }   L.data = newbase;   L.listsize = L.listsize * 2; } for (int j = L.length; j >= i; j--) {//将第i到length个元素后移   L.data[j] = L.data[j - 1]; }  L.data[i - 1] = e;// 为L中第i个元素赋值  L.length++;//L的表长+1 return true; } // 删除操作 bool ListDelete(SqList& L, int i, ElemType &e) { if (i<1 || i>L.length)// 下标i的数值错误 return false;  e = L.data[i - 1];//给e赋值为删除的元素 for (int j = i; j < L.length; j++) {//将第i到length个元素前移   L.data[j-1] = L.data[j]; }  L.length--;//L的表长减一 return true; } // 求表长操作 int Length(SqList L) { return L.length; } // 判空操作 bool Empty(SqList L) { if (L.length == 0) return true; return false; } // 输出操作 void PrintList(SqList L) {  cout << "L的元素为："; for (int i = 0; i < L.length; i++) {   cout << L.data[i]<<" "; }  cout << endl; } // 销毁操作 bool Destory(SqList& L) { free(L.data); if (!L.data) return true; else return false; } int main() {  SqList L;  cout << "初始化顺序表L：" << endl; if (InitList(L)) {   cout << "初始化顺序表L成功！" << endl; } else {   cout << "初始化顺序表L失败！" << endl; }  cout << "现在L的表长为：" << Length(L) << endl;  cout << "为L插入1-55，共55个元素：" << endl; for (int i = 1; i <= 55; i++){ ListInsert(L, i, i); }  cout << "插入成功！" << endl; PrintList(L);  cout << "在L的第2个位置插入元素 66：" << endl; ListInsert(L, 2, 66);  cout << "插入成功！" << endl; PrintList(L);  cout << "删除L中第三个元素：" << endl;  ElemType e; ListDelete(L, 3, e);  cout << "删除的元素为：" << e << endl; PrintList(L);  cout << "线性表中值为5的元素的位置为：" << LocateElem(L, 5) << endl; return 0; } 

程序输出为：

初始化顺序表L： 初始化顺序表L成功！ 现在L的表长为：0 为L插入1-55，共55个元素： 插入成功！ L的元素为：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 在L的第2个位置插入元素 66： 插入成功！ L的元素为：1 66 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 删除L中第三个元素： 删除的元素为：2 L的元素为：1 66 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 线性表中值为5的元素的位置为：5 

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客