(1) 编程模板中给出了不带头结点的单链表类模板SimpleLinkListWithoutHeadNode,请补全所缺少的插入和删除函数。
时间: 2023-09-26 18:06:27 浏览: 93
### 回答1:
以下是SimpleLinkListWithoutHeadNode的完整代码,包括插入和删除函数:
```c++
template <typename T>
class SimpleLinkListWithoutHeadNode {
private:
struct Node {
T data;
Node* next;
Node(const T& d, Node* n = nullptr) : data(d), next(n) {}
};
Node* head;
public:
SimpleLinkListWithoutHeadNode() : head(nullptr) {}
~SimpleLinkListWithoutHeadNode() {
while (head) {
Node* p = head;
head = head->next;
delete p;
}
}
bool isEmpty() const { return head == nullptr; }
void insert(const T& x) {
Node* p = new Node(x);
p->next = head;
head = p;
}
void remove(const T& x) {
Node* p = head, *prev = nullptr;
while (p) {
if (p->data == x) {
if (prev) prev->next = p->next;
else head = p->next;
delete p;
return;
}
prev = p;
p = p->next;
}
}
};
```
希望能对您有所帮助!
### 回答2:
插入函数的实现如下:
```
void insert(int index, T data) {
if (index < 0 || index > size) {
throw "索引越界";
}
// 创建新的节点
Node<T> *newNode = new Node<T>(data);
if (index == 0) {
// 插入到链表头部
newNode->next = head;
head = newNode;
} else {
Node<T> *prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
newNode->next = prev->next;
prev->next = newNode;
}
size++;
}
```
删除函数的实现如下:
```
void remove(int index) {
if (index < 0 || index >= size) {
throw "索引越界";
}
Node<T> *removedNode;
if (index == 0) {
// 删除链表头部节点
removedNode = head;
head = head->next;
} else {
Node<T> *prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
removedNode = prev->next;
prev->next = removedNode->next;
}
delete removedNode;
size--;
}
```
以上是在不带头结点的单链表类模板SimpleLinkListWithoutHeadNode中补全插入和删除函数的实现。插入函数用于在指定的索引位置插入一个新的节点,而删除函数用于删除指定索引位置的节点。在实现过程中需要注意边界条件的判断,以及指针的连接和内存管理。
### 回答3:
单链表类模板SimpleLinkListWithoutHeadNode是不带头结点的,所以头指针直接指向第一个节点。
插入函数的实现如下:
1. 在头部插入一个新节点。首先创建一个新节点,然后将新节点的next指针指向原来的头节点,最后将头指针指向新节点即可。
```cpp
void insertAtHead(T value) {
Node<T>* newNode = new Node<T>(value);
newNode->next = head;
head = newNode;
}
```
2. 在尾部插入一个新节点。首先创建一个新节点,然后遍历链表找到最后一个节点,将最后一个节点的next指针指向新节点即可。
```cpp
void insertAtTail(T value) {
Node<T>* newNode = new Node<T>(value);
if (head == nullptr) {
head = newNode;
} else {
Node<T>* curr = head;
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = newNode;
}
}
```
删除函数的实现如下:
1. 删除头节点。首先判断链表是否为空,如果为空则直接返回;否则将头指针指向下一个节点,然后删除原来的头节点。
```cpp
void deleteAtHead() {
if (head == nullptr) {
return;
}
Node<T>* temp = head;
head = head->next;
delete temp;
}
```
2. 删除指定值的节点。首先判断链表是否为空,如果为空则直接返回;否则遍历链表找到要删除的节点的前一个节点,将其next指针指向要删除节点的下一个节点,然后删除要删除的节点。
```cpp
void deleteByValue(T value) {
if (head == nullptr) {
return;
}
if (head->data == value) {
deleteAtHead();
} else {
Node<T>* curr = head;
while (curr->next != nullptr && curr->next->data != value) {
curr = curr->next;
}
if (curr->next != nullptr) {
Node<T>* temp = curr->next;
curr->next = temp->next;
delete temp;
}
}
}
```
阅读全文