实现SinglyList<T>单链表类增加的以下成员方法,public权限
时间: 2023-05-23 17:01:04 浏览: 130
好的,我了解了!以下是您的答案:
首先,我们需要先定义一个SinglyList<T>单链表类,以下是其基本实现:
```
template <typename T>
class SinglyList {
public:
struct Node {
T value;
Node* next;
Node(T v): value(v), next(nullptr) {}
};
SinglyList(): head_(nullptr), size_(0) {}
~SinglyList() { clear(); }
void clear() {
Node* p = head_;
while (p) {
Node* q = p;
p = p->next;
delete q;
}
head_ = nullptr;
size_ = 0;
}
void push_front(T v) {
Node* p = new Node(v);
p->next = head_;
head_ = p;
size_++;
}
void push_back(T v) {
Node* p = new Node(v);
if (!head_) {
head_ = p;
} else {
Node* q = head_;
while (q->next) {
q = q->next;
}
q->next = p;
}
size_++;
}
T pop_front() {
if (!head_) {
throw std::out_of_range("pop_front() on empty list");
}
Node* p = head_;
T v = p->value;
head_ = head_->next;
delete p;
size_--;
return v;
}
T pop_back() {
if (!head_) {
throw std::out_of_range("pop_back() on empty list");
}
if (!head_->next) {
T v = head_->value;
delete head_;
head_ = nullptr;
size_--;
return v;
}
Node* p = head_;
while (p->next->next) {
p = p->next;
}
T v = p->next->value;
delete p->next;
p->next = nullptr;
size_--;
return v;
}
size_t size() const { return size_; }
private:
Node* head_;
size_t size_;
};
```
现在,我们可以增加以下public权限的成员方法:
1. `void insert(int pos, T v)`: 在链表的 pos 位置上插入指定元素 v。
```
void insert(int pos, T v) {
if (pos < 0 || pos > size()) {
throw std::out_of_range("insert() out of range");
}
if (pos == 0) {
push_front(v);
} else if (pos == size()) {
push_back(v);
} else {
Node* p = head_;
for (int i = 0; i < pos - 1; i++) {
p = p->next;
}
Node* q = new Node(v);
q->next = p->next;
p->next = q;
size_++;
}
}
```
2. `void remove(int pos)`: 删除链表上指定位置的元素。
```
void remove(int pos) {
if (pos < 0 || pos >= size()) {
throw std::out_of_range("remove() out of range");
}
if (pos == 0) {
pop_front();
} else if (pos == size() - 1) {
pop_back();
} else {
Node* p = head_;
for (int i = 0; i < pos - 1; i++) {
p = p->next;
}
Node* q = p->next;
p->next = q->next;
delete q;
size_--;
}
}
```
3. `bool empty() const`: 判断链表是否为空。
```
bool empty() const {
return size() == 0;
}
```
这样,我们就通过增加这三个成员方法,使得SinglyList<T>单链表类更加完善和实用了。