C++ 线性表操作实现及代码示例
C++ 线性表操作实现及代码示例
本文提供 C++ 代码实现线性表的各种操作，包括初始化、销毁、清空、判断是否为空、求长度、获取指定位置的元素、获取元素的位置、求前驱、求后继、插入元素、删除元素、显示线性表、合并两个线性表等。并附带菜单界面供用户选择操作。
#include <iostream>
using namespace std;
// 数据元素的类型定义
typedef int ElementType;
// 线性表结构体定义
const int MaxSize = 100; // 最大容量
struct SeqList {
ElementType data[MaxSize]; // 数据元素数组
int length; // 当前长度
};
// 初始化线性表
void init(SeqList& list) {
list.length = 0;
}
// 销毁线性表
void destroy(SeqList& list) {
list.length = 0;
}
// 清空线性表
void clear(SeqList& list) {
list.length = 0;
}
// 判断线性表是否为空
bool isEmpty(SeqList list) {
return list.length == 0;
}
// 求线性表长度
int length(SeqList list) {
return list.length;
}
// 获取线性表中指定位置的元素
bool getElement(SeqList list, int pos, ElementType& elem) {
if (pos < 1 || pos > list.length) {
return false; // 位置不合法，获取失败
}
elem = list.data[pos - 1];
return true; // 获取成功
}
// 获取线性表元素的位置
bool getPosition(SeqList list, ElementType elem, int& pos) {
for (int i = 0; i < list.length; i++) {
if (list.data[i] == elem) {
pos = i + 1; // 找到元素位置
return true;
}
}
return false; // 未找到元素
}
// 求前驱元素
bool getPredecessor(SeqList list, ElementType elem, ElementType& predecessor) {
int pos;
if (getPosition(list, elem, pos) && pos > 1) {
predecessor = list.data[pos - 2]; // 找到前驱元素
return true;
}
return false; // 未找到元素或元素为第一个，无前驱
}
// 求后继元素
bool getSuccessor(SeqList list, ElementType elem, ElementType& successor) {
int pos;
if (getPosition(list, elem, pos) && pos < list.length) {
successor = list.data[pos]; // 找到后继元素
return true;
}
return false; // 未找到元素或元素为最后一个，无后继
}
// 在线性表指定位置插入元素
bool insert(SeqList& list, int pos, ElementType elem) {
if (pos < 1 || pos > list.length + 1 || list.length == MaxSize) {
return false; // 插入位置不合法或线性表已满，插入失败
}
// 将插入位置后的元素后移
for (int i = list.length; i >= pos; i--) {
list.data[i] = list.data[i - 1];
}
list.data[pos - 1] = elem; // 插入新元素
list.length++; // 长度加1
return true; // 插入成功
}
// 删除线性表指定位置的元素
bool remove(SeqList& list, int pos) {
if (pos < 1 || pos > list.length) {
return false; // 删除位置不合法，删除失败
}
// 将删除位置后的元素前移
for (int i = pos - 1; i < list.length - 1; i++) {
list.data[i] = list.data[i + 1];
}
list.length--; // 长度减1
return true; // 删除成功
}
// 显示线性表元素
void display(SeqList list) {
for (int i = 0; i < list.length; i++) {
cout << list.data[i] << ' ';
}
cout << endl;
}
// 合并两个非递减有序的线性表
SeqList merge(SeqList listA, SeqList listB) {
SeqList result;
init(result);
int i = 0, j = 0;
while (i < listA.length && j < listB.length) {
if (listA.data[i] <= listB.data[j]) {
insert(result, result.length + 1, listA.data[i]);
i++;
} else {
insert(result, result.length + 1, listB.data[j]);
j++;
}
}
while (i < listA.length) {
insert(result, result.length + 1, listA.data[i]);
i++;
}
while (j < listB.length) {
insert(result, result.length + 1, listB.data[j]);
j++;
}
return result;
}
// 显示菜单
void displayMenu() {
cout << '1----初始化一个线性表' << endl;
cout << '2----销毁线性表' << endl;
cout << '3----清空线性表' << endl;
cout << '4----判断线性表是否为空' << endl;
cout << '5----求线性表长度' << endl;
cout << '6----获取线性表中指定位置的元素' << endl;
cout << '?----获取线性表元素的位置' << endl;
cout << '8----求前驱' << endl;
cout << '9----求后继' << endl;
cout << '10----在线性表指定位置插入元素' << endl;
cout << '11---删除线性表指定位置的元素' << endl;
cout << '12---显示线性表' << endl;
cout << '13---合并两个非递减有序的线性表' << endl;
cout << '0----退出' << endl;
}
int main() {
SeqList list;
init(list);
int choice;
while (true) {
displayMenu();
cout << '请输入操作代码：';
cin >> choice;
if (choice == 1) {
init(list);
cout << '线性表初始化成功！' << endl;
} else if (choice == 2) {
destroy(list);
cout << '线性表销毁成功！' << endl;
} else if (choice == 3) {
clear(list);
cout << '线性表清空成功！' << endl;
} else if (choice == 4) {
if (isEmpty(list)) {
cout << '线性表为空！' << endl;
} else {
cout << '线性表不为空！' << endl;
}
} else if (choice == 5) {
cout << '线性表长度为：' << length(list) << endl;
} else if (choice == 6) {
int pos;
ElementType elem;
cout << '请输入要获取元素的位置：';
cin >> pos;
if (getElement(list, pos, elem)) {
cout << '位置 ' << pos << ' 的元素为：' << elem << endl;
} else {
cout << '位置不合法！' << endl;
}
} else if (choice == '?') {
ElementType elem;
int pos;
cout << '请输入要查找的元素值：';
cin >> elem;
if (getPosition(list, elem, pos)) {
cout << '元素 ' << elem << ' 在线性表中的位置为：' << pos << endl;
} else {
cout << '元素不在线性表中！' << endl;
}
} else if (choice == 8) {
ElementType elem, predecessor;
cout << '请输入要求前驱的元素值：';
cin >> elem;
if (getPredecessor(list, elem, predecessor)) {
cout << '元素 ' << elem << ' 的前驱元素为：' << predecessor << endl;
} else {
cout << '未找到前驱元素或该元素为第一个元素！' << endl;
}
} else if (choice == 9) {
ElementType elem, successor;
cout << '请输入要求后继的元素值：';
cin >> elem;
if (getSuccessor(list, elem, successor)) {
cout << '元素 ' << elem << ' 的后继元素为：' << successor << endl;
} else {
cout << '未找到后继元素或该元素为最后一个元素！' << endl;
}
} else if (choice == 10) {
int pos;
ElementType elem;
cout << '请输入要插入的位置和元素值：';
cin >> pos >> elem;
if (insert(list, pos, elem)) {
cout << '插入成功！' << endl;
} else {
cout << '插入失败！' << endl;
}
} else if (choice == 11) {
int pos;
cout << '请输入要删除的位置：';
cin >> pos;
if (remove(list, pos)) {
cout << '删除成功！' << endl;
} else {
cout << '删除失败！' << endl;
}
} else if (choice == 12) {
cout << '线性表元素为：';
display(list);
} else if (choice == 13) {
SeqList listA, listB, mergedList;
init(listA);
init(listB);
int lengthA, lengthB;
cout << '请输入第一个线性表的长度：';
cin >> lengthA;
cout << '请输入第一个线性表的元素值（按顺序输入）：';
for (int i = 0; i < lengthA; i++) {
cin >> listA.data[i];
}
listA.length = lengthA;
cout << '请输入第二个线性表的长度：';
cin >> lengthB;
cout << '请输入第二个线性表的元素值（按顺序输入）：';
for (int i = 0; i < lengthB; i++) {
cin >> listB.data[i];
}
listB.length = lengthB;
mergedList = merge(listA, listB);
cout << '合并后的线性表为：';
display(mergedList);
} else {
break;
}
}
return 0;
}
以上代码实现了根据菜单选择进行线性表的各种操作，并根据需要提供了相应的功能。请根据实际需求使用该代码，并按照菜单提示进行操作和测试。测试时，注意处理不合法情况，例如插入和删除时的位置不合法等。
如果还有其他疑问，请随时提问。
原文地址: https://www.cveoy.top/t/topic/bqb4 著作权归作者所有。请勿转载和采集!