编写程序Node.h 实现例9-5的结点类,并编写测试程序lab91.cpp实现链表的基本操作。
时间: 2024-03-05 13:51:17 浏览: 29
以下是Node.h的代码实现:
```c++
#ifndef NODE_H
#define NODE_H
template<typename T>
class Node {
public:
Node() : data(0), next(nullptr) {}
Node(T d, Node<T>* n = nullptr) : data(d), next(n) {}
T data;
Node<T>* next;
};
#endif // NODE_H
```
以下是lab91.cpp的代码实现:
```c++
#include <iostream>
#include "Node.h"
using namespace std;
template<typename T>
class LinkedList {
public:
LinkedList() : head(nullptr), size(0) {}
~LinkedList() {
Node<T>* current = head;
while (current != nullptr) {
Node<T>* temp = current;
current = current->next;
delete temp;
}
}
void insert_front(T data);
void insert_end(T data);
void insert_at(T data, int position);
void remove_front();
void remove_end();
void remove_at(int position);
void print();
private:
Node<T>* head;
int size;
};
template<typename T>
void LinkedList<T>::insert_front(T data) {
head = new Node<T>(data, head);
size++;
}
template<typename T>
void LinkedList<T>::insert_end(T data) {
if (head == nullptr) {
head = new Node<T>(data);
} else {
Node<T>* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node<T>(data);
}
size++;
}
template<typename T>
void LinkedList<T>::insert_at(T data, int position) {
if (position < 0 || position > size) {
cout << "Invalid position" << endl;
return;
}
if (position == 0) {
insert_front(data);
} else if (position == size) {
insert_end(data);
} else {
Node<T>* current = head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
current->next = new Node<T>(data, current->next);
size++;
}
}
template<typename T>
void LinkedList<T>::remove_front() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
Node<T>* temp = head;
head = head->next;
delete temp;
size--;
}
template<typename T>
void LinkedList<T>::remove_end() {
if (head == nullptr) {
cout << "List is empty" << endl;
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
} else {
Node<T>* current = head;
while (current->next->next != nullptr) {
current = current->next;
}
delete current->next;
current->next = nullptr;
}
size--;
}
template<typename T>
void LinkedList<T>::remove_at(int position) {
if (position < 0 || position >= size) {
cout << "Invalid position" << endl;
return;
}
if (position == 0) {
remove_front();
} else if (position == size - 1) {
remove_end();
} else {
Node<T>* current = head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
Node<T>* temp = current->next;
current->next = temp->next;
delete temp;
size--;
}
}
template<typename T>
void LinkedList<T>::print() {
Node<T>* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
int main() {
LinkedList<int> list;
list.insert_front(1);
list.insert_front(2);
list.insert_end(3);
list.insert_at(4, 2);
list.print();
list.remove_front();
list.remove_end();
list.remove_at(1);
list.print();
LinkedList<string> list2;
list2.insert_front("hello");
list2.insert_front("world");
list2.insert_end("!");
list2.insert_at("beautiful", 2);
list2.print();
list2.remove_front();
list2.remove_end();
list2.remove_at(1);
list2.print();
return 0;
}
```
该程序包括链表的基本操作,如插入、删除和打印链表。在主函数中,创建了两个不同类型的链表,并对它们进行了测试。