顺序表
数组描述方法将元素存储在一个数组中，用一个数学公式来确定每个元素存储的位置，即在数组中的索引。这是最简单的一种存储方式，所有元素依次存储在一片连续的存储空间中，这就是通常所说的顺序表。 --- 数据结构、算法与应用
顺序表的实现
线性表动态分配顺序存储结构
ps：为了方便修改数据元素的类型，使用了模板，可以方便修改线性表中的数据元素的类型；
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTNCREMENT 10 // 线性表存储空间的分配增量 templatestruct SeqList { T* element; // 存储空间的基质 int capacity; // 线性表的当前分配的存储容量 int listSize;; // 线性表的当前长度 };
顺序表的基本操作
void initMenu(); // 初始化菜单 SeqList* initList(); // 初始化线性表 bool distroyList(SeqList *&); // 销毁线性表 bool clearList(SeqList *&); // 清空线性表 bool isEmpty(SeqList *&); // 判断是否为空 int getLength(SeqList *&); // 得到线性表的当前长度 int getElement(SeqList *&, int); // 得到指定位置的元素 int getIndex(SeqList *&, int); // 得到元素的下标 int getPreElement(SeqList *&, int); // 得到元素的前驱 int getSeqElement(SeqList *&, int); // 得到元素的后继 bool insertElement(SeqList *&, int, int); // 插入元素 bool deleteElement(SeqList *&, int); // 删除元素 void showElement(SeqList *&); // 遍历表中的所有元素 void megerList(SeqList *&, SeqList *&); // 合并两个线性表
自定义函数的实现
void initMenu() // 初始化菜单界面
{
cout << "*************************" << endl;
cout << "1---初始化线性表" << endl;
cout << "2---销毁线性表" << endl;
cout << "3---清空线性表" << endl;
cout << "4---判断线性表是否为空" << endl;
cout << "5---求线性表的长度" << endl;
cout << "6---获取线性表中指定位置的元素" << endl;
cout << "7---获取线性表元素的位置" << endl;
cout << "8---求前驱" << endl;
cout << "9---求后继" << endl;
cout << "10---在线性表指定位置插入元素" << endl;
cout << "11---删除线性表指定位置的元素" << endl;
cout << "12---显示线性表" << endl;
cout << "13---合并两个非递减有序的线性表" << endl;
cout << "14---退出程序(输入负数)" << endl;
cout << "*************************" << endl;
}
（1）线性表的初始化
初始化线性表，是指初始化一个空的线性表，里面的元素个数是0
SeqList* initList() // 初始化线性表 { SeqList * MyList = new SeqList (); try { MyList->element = new int[LIST_INIT_SIZE]; MyList->capacity = LIST_INIT_SIZE; MyList->listSize = 0; } catch (bad_alloc) { cerr << "初始化失败！" << endl; exit(1); } cout << "初始化成功!" << endl; return MyList; }
（2）销毁线性表 、清空线性表、判断是否为空、返回线性表的长度
销毁线性表：释放线性表的基地址，将capacity与listSize赋值为0
清空线性表：只需将listSize赋值为0
判断是否为空：只需判断listSize的值是否为0
返回线性表的长度：只需将listSize的值返回
bool distroyList(SeqList*& arrayList) // 销毁线性表 { bool isDistory = false; delete arrayList->element; arrayList->element = nullptr; arrayList->capacity = 0; arrayList->listSize = 0; if (arrayList->element == nullptr) { isDistory = true; } return isDistory; } bool clearList(SeqList *& arrayList) // 清空线性表 { bool isClear = false; arrayList->listSize = 0; if (arrayList->listSize == 0) { isClear = true; } return isClear; } bool isEmpty(SeqList *& arrayList) // 判断线性表是否为空 { if (arrayList->listSize > 0) { return false; } return true; } int getLength(SeqList *& arrayList) // 得到线性表的当前长度 { return arrayList->listSize; }
（3）获得对应位置的元素
int getElement(SeqList*& arrayList, int index) // 得到对应位置的元素 { if (index > arrayList->listSize || index < 0) // 判断用户输入的下标是否合法 { return -1; } return arrayList->element[index - 1]; }
（4）获得线性表元素的下标
int getIndex(SeqList*& arrayList, int num) // 得到元素的下标 { for (int i = 0; i < arrayList->listSize; i++) { if (arrayList->element[i] == num) { return i; } } return -1; }
（5）获得前驱
遍历顺序表找到与用户输入元素相同的元素的下标，将该下标-1得到前驱，但要注意特殊情况即当该元素为第一个元素时，没有前驱。
int getPreElement(SeqList*& arrayList, int num) // 得到元素的前驱 { int temp = -2; // 用来记录元素前驱的下标 for (int i = 0; i < arrayList->listSize; i++) { if (arrayList->element[i] == num && i == 0) {// 顺序表的第一个元素，没有前驱 return -1; } if (arrayList->element[i] == num) {// 找到前驱 temp = i - 1; break; } } if (temp == -2) {// 没有该元素 return -2; } return arrayList->element[temp]; }
（6）获得后继
遍历顺序表找到与用户输入元素相同的元素的下标，将该下标+1得到后继，但要注意特殊情况即当该元素为最后一个元素时，没有后继。
int getSeqElement(SeqList*& arrayList, int num) // 得到元素的后继 { int temp = -2; // 用来记录元素前驱的下标 for (int i = 0; i < arrayList->listSize; i++) { if (arrayList->element[i] == num && i == arrayList->listSize - 1) {// 顺序表的最后一个元素，没有后继 return -1; } if (arrayList->element[i] == num) {// 找到后继 temp = i + 1; break; } } if (temp == -2) {// 没有该元素 return -2; } return arrayList->element[temp]; }
（7）插入元素
插入元素之前要判断线性表是否初始化（主函数中实现），插入的位置是否合法，顺序表是否已满。
在顺序表的第i个位置插入元素e，与数组的插入操作基本相同，将顺序表第i个位置之后的元素从后向前依次向后移动一个位置，然后将元素e插入第i个位置，在插入元素之后要将顺序表的当前长度listSize++，但要注意是从后往前依次移动元素，即：先移动最后一个元素，在移动倒数第二个元素，依次类推
bool insertElement(SeqList*& arrayList, int index, int num) // 插入元素 { if (index < 1 || index > arrayList->listSize + 1) // 判断插入的位置是否合法 { return false; } if (arrayList->listSize >= arrayList->capacity) // 判断顺序表的空间是否已满 { try { int* newbase = new int[LIST_INIT_SIZE + LISTNCREMENT]; // 重新分配新的空间 copy(arrayList->element, arrayList->element + LIST_INIT_SIZE, newbase); // 将顺序表的元素赋值给新的顺序表 arrayList->element = newbase; arrayList->capacity += LISTNCREMENT; } catch (bad_alloc) { exit(OVERFLOW); } } for (int i = arrayList->listSize - 1; i >= index - 1; i--) // 插入操作，同数组的插入 { arrayList->element[i + 1] = arrayList->element[i]; } arrayList->element[index - 1] = num; arrayList->listSize++; return true; }
（8）删除元素
删除元素之前要判断线性表是否初始化（主函数实现），顺序表是否为空（主函数实现），删除的位置是否合法。
删除线性表中的第i个元素，与数组的删除操作基本相同，需要将表中第i个元素之后的元素依次向前移动一位，将前面的元素覆盖。移动元素时要将第i+1个元素移动到第i个位置，在将第i+2个元素移动i+1的位置，直到将最后一个元素移动到它的前一个位置，删除元素之后，将顺序表的当前长的listSize--;
bool deleteElement(SeqList*& arrayList, int index) // 删除下表对应的元素 { if (index < 1 || index > arrayList->listSize) // 判断用户输入的下标是否合法 { return false; } for (int i = index - 1; i < arrayList->listSize; i++) // 删除操作，同数组的删除 { arrayList->element[i] = arrayList->element[i + 1]; } arrayList->listSize--; return true; }
（9）遍历线性表
void showElement(SeqList*& arrayList) // 遍历线性表 { cout << "该线性表的元素为：" << endl; for (int i = 0; i < arrayList->listSize; i++) { cout << arrayList->element[i] << "t"; } cout << endl; }
（10）合并两个非降序线性表
ps：该方法也是我自己在力扣上做题的时候学的，下面附上该方法的链接
画解算法：88. 合并两个有序数组
void megerList(SeqList*& arrayList, SeqList *& myList) // 合并两个线性表 { // myList 线性表在调用该函数前需要初始化，具体实现在主函数 int size1 = arrayList->listSize; // 记录arrayList的空间大小 int size2 = myList->listSize; // 记录myArray的空间大小 int len1 = size1 - 1; int len2 = size2 - 1; int len = size1 + size2 - 1; // 以上声明均为了更方便的实现一下操作 // 合并两个非降序线性表前需要将两个线性表非降序排序 sort(arrayList->element, arrayList->element + size1); sort(myList->element, myList->element + size2); SeqList * newList = new SeqList (); // 新的线性表，用来存储两个线性表合并后的新表 newList->element = new int[size1 + size2]{ -1 }; newList->listSize = size1 + size2; while (len1 >= 0 && len2 >= 0) // 合并两个线性表的具体实现 { newList->element[len--] = arrayList->element[len1] > myList->element[len2] ? arrayList->element[len1--] : myList->element[len2--]; } if (len1 >= 0) { copy(arrayList->element, arrayList->element + (len1 + 1), newList->element); } if (len2 >= 0) { copy(myList->element, myList->element + (len2 + 1), newList->element); } cout << "合并后的顺序表为：" << endl; for (int i = 0; i < newList->listSize; i++) { cout << newList->element[i] << "t"; } cout << endl; }
主函数的实现
int main()
{
initMenu();
SeqList* arrayList = new SeqList();
int choice;
cout << "请输入操作代码：";
cin >> choice;
while (choice > 0)
{
switch (choice)
{
case 1://初始化线性表空间
{
arrayList = initList();
break;
}
case 2://销毁线性表
{
bool isTrue = distroyList(arrayList);
if (isTrue)
{
cout << "销毁成功！" << endl;
}
else
{
cout << "销毁失败！" << endl;
exit(1);
}
break;
}
case 3://清空线性表
{
bool isTrue = clearList(arrayList);
if (isTrue)
{
cout << "清空成功！" << endl;
}
else
{
cout << "清空失败！" << endl;
exit(1);
}
break;
}
case 4://判断线性表是否为空
{
bool isTrue = isEmpty(arrayList);
if (isTrue)
{
cout << "该表为空" << endl;
}
else
{
cout << "该表不为空" << endl;
}
break;
}
case 5://求线性表的长度
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
cout << "线性表的长度为：" << getLength(arrayList) << endl;
break;
}
case 6://获取线性表中指定位置的元素
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
int index;
cout << "请输入要查找元素的位置：";
cin >> index;
int temp = getElement(arrayList, index);
if (temp == -1)
{
cerr << "访问越界！" << endl;
}
else
{
cout << "该元素为：" << temp << endl;
}
break;
}
case 7://获取线性表元素的位置
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
int num;
cout << "请输入您要查找的元素：";
cin >> num;
int temp = getIndex(arrayList, num);
if (temp == -1)
{
cerr << "线性表中没有该元素！" << endl;
}
else
{
cout << "该元素的下标为：" << temp << endl;
}
break;
}
case 8://求前驱
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
int num;
cout << "请输入求前驱的元素：";
cin >> num;
int temp = getPreElement(arrayList, num);
if (temp == -1)
{
cout << "该元素没有前驱！" << endl;
}
else if (temp == -2)
{
cerr << "线性表中没有该元素!" << endl;
}
else
{
cout << "该元素的前驱为：" << temp << endl;
}
break;
}
case 9://求后继
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
int num;
cout << "请输入求后继的元素：";
cin >> num;
int temp = getSeqElement(arrayList, num);
if (temp == -1)
{
cout << "该元素没有后继！" << endl;
}
else if (temp == -2)
{
cerr << "线性表中没有该元素!" << endl;
}
else
{
cout << "该元素的后继为：" << temp << endl;
}
break;
}
case 10://在线性表指定位置插入元素
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
int index, num;
cout << "请输入要插入的位置下标与元素（end of -1）：";
cin >> index >> num;
while (index != -1)
{
bool isTrue = insertElement(arrayList, index, num);
if (!isTrue)
{
cerr << "错误插入！" << endl;
exit(1);
}
else
{
cout << "插入成功！" << endl;
cout << "请输入要插入的位置下标与元素（end of -1）：";
cin >> index >> num;
}
}
break;
}
case 11://删除线性表指定位置的元素
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "该顺序表已空！" << endl;
break;
}
int index;
cout << "请输入要删除的位置：";
cin >> index;
bool isTrue = deleteElement(arrayList, index);
if (!isTrue)
{
cerr << "删除失败！" << endl;
exit(1);
}
else
{
cout << "删除成功！" << endl;
}
{}
break;
}
case 12://显示线性表
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
showElement(arrayList);
break;
}
case 13://合并两个非递减有序的线性表
{
if (arrayList->element == nullptr)
{
cout << "请先初始化顺序表!" << endl;
break;
}
if (isEmpty(arrayList))
{
cout << "请先为顺序表添加元素！" << endl;
break;
}
cout << "自动创建一个新的线性表！" << endl;
SeqList* myList = initList();
int index, num;
cout << "请输入要插入的位置下标与元素（end of -1）：";
cin >> index >> num;
while (index != -1)
{
insertElement(myList, index, num);
cout << "请输入要插入的位置下标与元素（end of -1）：";
cin >> index >> num;
}
megerList(arrayList, myList);
break;
}
default:
break;
}
Sleep(1000);
system("cls");
initMenu();
cout << "请输入操作代码：";
cin >> choice;
}
cout << "程序退出!" << endl;
return 0;
}
注：本人已测试过该代码，如要亲自测试该代码，请添加头文件
#include
#include
#include
最后：
本人是第一次发表文章，以上代码仅为个人写法，不喜勿喷，如有不足或错误的地方欢迎指正。如果文章对你有所帮助，欢迎点赞支持。欢迎转载。
