编写一个程序,实现顺序表的各种基本运算和整体建表算法,假设顺序表的元素类型ElemType为char。
时间: 2024-10-12 20:12:08 浏览: 1
编写一个顺序表程序,用于处理字符类型的元素(ElemType为char),通常需要包含以下几个部分:
1. **定义顺序表结构**:
```c++
#include <iostream>
using namespace std;
// 定义顺序表的节点结构体
struct ListNode {
char data; // 存储字符数据
ListNode* next; // 指向下一个节点的指针
};
// 顺序表的全局变量
class SequentialList {
private:
ListNode* head; // 链表头指针
int size; // 列表长度
public:
// 构造函数,初始化空列表
SequentialList() : head(nullptr), size(0) {}
};
```
2. **基础操作**:
- **插入元素**: 在链表尾部添加元素
```cpp
void insertAtEnd(char value) {
if (head == nullptr) {
head = new ListNode{value, nullptr};
} else {
ListNode* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new ListNode{value, nullptr};
}
size++;
}
// 删除元素: 删除指定位置的元素
void deleteElement(int index) {
if (index < 0 || index >= size) {
return;
}
if (index == 0) {
head = head->next;
} else {
ListNode* prev = head;
for (int i = 0; i < index - 1 && prev != nullptr; ++i) {
prev = prev->next;
}
if (prev != nullptr) {
prev->next = prev->next->next;
}
}
size--;
}
// 查找元素: 返回给定索引处的元素
char findElement(int index) const {
if (index < 0 || index >= size) {
throw out_of_range("Index out of range");
}
ListNode* current = head;
for (int i = 0; i < index; ++i) {
current = current->next;
}
return current->data;
}
```
3. **整体建表算法**:
- **创建空列表**
```cpp
void createEmptyList() {
head = nullptr;
size = 0;
}
// 打印整个列表
void printList() const {
ListNode* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
```
4. **析构函数**:
```cpp
~SequentialList() {
clear(); // 清理内存
}
// 清除列表并释放所有节点
void clear() {
ListNode* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
size = 0;
}
};
```