实现串的应用每一行是顺序结构,每一页包括若干行,每一行是一个节点,节点之间采用链式结构,页与页之间采用链式结构。可以实现字符串的插入,删除,查询等操作的代码
时间: 2024-02-24 12:57:13 浏览: 14
下面是一个基于链表实现的串的代码示例,其中每一个节点代表一个字符,每一页代表一个链表:
```c++
#include <iostream>
#include <string>
using namespace std;
const int PAGE_SIZE = 10; // 每一页的大小
// 链表节点
struct Node {
char data;
Node* next;
Node(char c) : data(c), next(nullptr) {}
};
// 串
class String {
private:
Node* head; // 头节点
int len; // 串的长度
public:
String() : head(nullptr), len(0) {}
// 插入字符
void insert(int pos, char c) {
if (pos < 0 || pos > len) return; // 位置不合法
int page = pos / PAGE_SIZE; // 计算所在页
int offset = pos % PAGE_SIZE; // 计算在页内的偏移量
Node* cur = getPage(page); // 获取所在页的头节点
Node* prev = nullptr;
while (cur && offset > 0) { // 找到所在节点的前驱节点
prev = cur;
cur = cur->next;
offset--;
}
Node* newNode = new Node(c); // 创建新节点
newNode->next = cur;
if (prev == nullptr) { // 头节点为nullptr,说明是第一页
head = newNode;
} else {
prev->next = newNode;
}
len++; // 串的长度加1
}
// 删除字符
void remove(int pos) {
if (pos < 0 || pos >= len) return; // 位置不合法
int page = pos / PAGE_SIZE; // 计算所在页
int offset = pos % PAGE_SIZE; // 计算在页内的偏移量
Node* cur = getPage(page); // 获取所在页的头节点
Node* prev = nullptr;
while (cur && offset > 0) { // 找到所在节点的前驱节点
prev = cur;
cur = cur->next;
offset--;
}
if (prev == nullptr) { // 头节点为nullptr,说明是第一页
head = cur->next;
} else {
prev->next = cur->next;
}
delete cur; // 释放内存
len--; // 串的长度减1
}
// 查询字符
char get(int pos) {
if (pos < 0 || pos >= len) return '\0'; // 位置不合法
int page = pos / PAGE_SIZE; // 计算所在页
int offset = pos % PAGE_SIZE; // 计算在页内的偏移量
Node* cur = getPage(page); // 获取所在页的头节点
while (cur && offset > 0) { // 找到所在节点
cur = cur->next;
offset--;
}
return cur->data;
}
private:
// 获取指定页的头节点
Node* getPage(int page) {
Node* cur = head;
while (cur && page > 0) { // 找到指定页
cur = cur->next;
page--;
}
if (cur == nullptr && page > 0) { // 没有找到指定页
throw out_of_range("page out of range");
}
return cur;
}
};
int main() {
String s;
s.insert(0, 'a');
s.insert(1, 'b');
s.insert(2, 'c');
s.remove(1);
cout << s.get(0) << s.get(1) << endl; // 输出 "ac"
return 0;
}
```
该代码将串分为若干页,每一页包含若干个节点。通过 getPage 函数可以获取指定页的头节点,然后找到该页内的指定节点进行操作。在插入和删除时,需要先找到指定位置所在的节点的前驱节点,然后插入或删除节点。在查询时,直接找到指定节点即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)