在有多个广义表需要存储的背景下,给出广义表的相关运 算和相应的描述,并设计存储结构及其运算实现。注意特 别要能对广义表标识符进行引用、指示等。
时间: 2024-06-06 13:08:01 浏览: 15
一、广义表的相关运算和描述
1. 创建空广义表:创建一个空的广义表,即没有任何元素。
2. 判断广义表是否为空:判断广义表是否为空,如果为空则返回 true,否则返回 false。
3. 添加元素:向广义表中添加元素,可以是一个原子或另一个广义表。
4. 删除元素:从广义表中删除一个元素。
5. 复制广义表:复制一个广义表,得到一个新的广义表。
6. 求广义表长度:求出广义表中元素的个数。
7. 获取广义表元素:获取一个广义表中指定位置的元素。
8. 修改广义表元素:修改一个广义表中指定位置的元素。
二、广义表的存储结构及其运算实现
广义表可以使用链表来存储,每个节点可以存储一个原子或一个子表。节点的结构如下:
struct GLNode {
bool isAtom; // 是否为原子
union {
AtomType atom; // 原子的类型
GLNode* subList; // 子表的头指针
} value;
GLNode* next; // 下一个节点的指针
};
其中 AtomType 为原子的类型,可以是整型、浮点型、字符型等。
广义表的操作可以定义为一个类,包含以下方法:
class GeneralizedList {
public:
GeneralizedList(); // 构造函数,创建一个空广义表
bool isEmpty(); // 判断广义表是否为空
void addAtom(AtomType atom); // 添加一个原子
void addSubList(GeneralizedList subList); // 添加一个子表
bool deleteElement(int index); // 删除指定位置的元素
GeneralizedList copy(); // 复制广义表
int length(); // 求广义表长度
GLNode* getElement(int index); // 获取指定位置的元素
bool setElement(int index, AtomType atom); // 修改指定位置的元素
private:
GLNode* head; // 头节点指针
};
具体实现可以参考下面的代码:
GeneralizedList::GeneralizedList() {
head = new GLNode;
head->isAtom = false;
head->next = nullptr;
}
bool GeneralizedList::isEmpty() {
return head->next == nullptr;
}
void GeneralizedList::addAtom(AtomType atom) {
GLNode* node = new GLNode;
node->isAtom = true;
node->value.atom = atom;
node->next = nullptr;
GLNode* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = node;
}
void GeneralizedList::addSubList(GeneralizedList subList) {
GLNode* node = new GLNode;
node->isAtom = false;
node->value.subList = subList.head->next;
node->next = nullptr;
GLNode* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = node;
}
bool GeneralizedList::deleteElement(int index) {
if (index < 1) {
return false;
}
GLNode* p = head;
int i = 0;
while (p->next != nullptr && i < index - 1) {
p = p->next;
i++;
}
if (p->next == nullptr) {
return false;
}
GLNode* q = p->next;
p->next = q->next;
delete q;
return true;
}
GeneralizedList GeneralizedList::copy() {
GeneralizedList newList;
GLNode* p = head->next;
while (p != nullptr) {
if (p->isAtom) {
newList.addAtom(p->value.atom);
} else {
newList.addSubList(p->value.subList->copy());
}
p = p->next;
}
return newList;
}
int GeneralizedList::length() {
int len = 0;
GLNode* p = head->next;
while (p != nullptr) {
len++;
p = p->next;
}
return len;
}
GLNode* GeneralizedList::getElement(int index) {
if (index < 1) {
return nullptr;
}
GLNode* p = head->next;
int i = 1;
while (p != nullptr && i < index) {
p = p->next;
i++;
}
return p;
}
bool GeneralizedList::setElement(int index, AtomType atom) {
GLNode* p = getElement(index);
if (p == nullptr || p->isAtom == false) {
return false;
}
p->value.atom = atom;
return true;
}
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)