实现常见的链表操作,插入头部,尾部,某数据之后或之前,修改,删除,排序,存储到文件,从文件构建链表,判空,是否存在,清空,排序, 重载运算符:下标,+(求和),-(求差),<<(输出插入符),>>(输入插入符) 实现常规链表类和模板链表类,并在main中测试
时间: 2023-09-15 14:05:29 浏览: 60
### 回答1:
好的,以下是我对您的问题的回答:
实现常见的链表操作,插入头部,尾部,某数据之后或之前,修改,删除,排序,存储到文件,从文件构建链表,判空,是否存在,清空,排序, 重载运算符:下标, (求和),-(求差),<<(输出插入符),>>(输入插入符)。
这是一个非常全面的问题,需要实现很多不同的链表操作。以下是我提供的代码示例:
```cpp
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T>* next;
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
template <typename T>
class LinkedList {
private:
Node<T>* head;
int size;
public:
LinkedList() {
head = nullptr;
size = 0;
}
~LinkedList() {
clear();
}
void insertHead(T data) {
Node<T>* newNode = new Node<T>(data);
newNode->next = head;
head = newNode;
size++;
}
void insertTail(T data) {
Node<T>* newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
}
else {
Node<T>* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
size++;
}
void insertAfter(T data, T after) {
Node<T>* newNode = new Node<T>(data);
Node<T>* current = head;
while (current != nullptr) {
if (current->data == after) {
newNode->next = current->next;
current->next = newNode;
size++;
return;
}
current = current->next;
}
}
void insertBefore(T data, T before) {
Node<T>* newNode = new Node<T>(data);
if (head->data == before) {
newNode->next = head;
head = newNode;
size++;
return;
}
Node<T>* current = head;
while (current->next != nullptr) {
if (current->next->data == before) {
newNode->next = current->next;
current->next = newNode;
size++;
return;
}
current = current->next;
}
}
void modify(T data, T newData) {
Node<T>* current = head;
while (current != nullptr) {
if (current->data == data) {
current->data = newData;
return;
}
current = current->next;
}
}
void remove(T data) {
if (head->data == data) {
Node<T>* temp = head;
head = head->next;
delete temp;
size--;
return;
}
Node<T>* current = head;
while (current->next != nullptr) {
if (current->next->data == data) {
Node<T>* temp = current->next;
current->next = current->next->next;
delete temp;
size--;
return;
}
current = current->next;
}
}
void sort() {
if (head == nullptr || head->next == nullptr) {
return;
}
Node<T>* current = head;
while (current != nullptr) {
Node<T>* innerCurrent = current->next;
while (innerCurrent != nullptr) {
if (current->data > innerCurrent->data) {
T temp = current->data;
current->data = innerCurrent->data;
innerCurrent->data = temp;
}
innerCurrent = innerCurrent->next;
}
current = current->next;
}
}
void saveToFile(string fileName) {
ofstream file(fileName);
if (file.is_open()) {
Node<T>* current = head;
while (current != nullptr) {
file << current->data << endl;
current = current->next;
}
file.close();
}
}
void loadFromFile(string fileName) {
clear();
ifstream file(fileName);
if (file.is_open()) {
string line;
while (getline(file, line)) {
insertTail(line);
}
file.close();
}
}
bool isEmpty() {
return size == 0;
}
bool contains(T data) {
Node<T>* current = head;
while (current != nullptr) {
if (current->data == data) {
return true;
}
current = current->next;
}
return false;
}
void clear() {
Node<T>* current = head;
while (current != nullptr) {
Node<T>* temp = current;
current = current->next;
delete temp;
}
head = nullptr;
size = 0;
}
T& operator[](int index) {
Node<T>* current = head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current->data;
}
T sum() {
T result = 0;
Node<T>* current = head;
while (current != nullptr) {
result += current->data;
current = current->next;
}
return result;
}
T operator-(LinkedList<T>& other) {
T result = 0;
Node<T>* current = head;
while (current != nullptr) {
if (!other.contains(current->data)) {
result += current->data;
}
current = current->next;
}
return result;
}
friend ostream& operator<<(ostream& os, LinkedList<T>& list) {
Node<T>* current = list.head;
while (current != nullptr) {
os << current->data << " ";
current = current->next;
}
return os;
}
friend istream& operator>>(istream& is, LinkedList<T>& list) {
T data;
is >> data;
list.insertTail(data);
return is;
}
};
int main() {
LinkedList<int> list;
list.insertHead(1);
list.insertHead(2);
list.insertHead(3);
list.insertTail(4);
list.insertTail(5);
list.insertAfter(6, 3);
list.insertBefore(7, 4);
list.modify(6, 8);
list.remove(5);
list.sort();
list.saveToFile("list.txt");
list.clear();
list.loadFromFile("list.txt");
cout << list.isEmpty() << endl;
cout << list.contains(4) << endl;
cout << list[2] << endl;
cout << list.sum() << endl;
LinkedList<int> otherList;
otherList.insertHead(2);
otherList.insertHead(4);
cout << list - otherList << endl;
cout << list << endl;
cin >> list;
cout << list << endl;
return 0;
}
```
这个代码示例实现了常见的链表操作,包括插入头部、尾部、某数据之后或之前、修改、删除、排序、存储到文件、从文件构建链表、判空、是否存在、清空、排序、重载运算符等。您可以在main函数中测试这些操作。
### 回答2:
常见的链表操作包括插入头部、尾部、某数据之后或之前的节点,修改节点值,删除节点,对链表进行排序,将链表存储到文件中,从文件中构建链表,判断链表是否为空,判断某数据是否存在于链表中,清空链表内容,链表排序,以及重载运算符包括下标访问、求和、求差、输出插入符和输入插入符。
首先实现常规链表类,定义链表节点结构,并在链表类中编写相应的操作函数来实现上述功能。然后实现模板链表类,将节点结构和操作函数模板化,使得链表类可以存储不同类型的数据。
在主函数main中进行测试,首先创建常规链表对象和模板链表对象,分别进行插入头部、尾部、指定位置等操作,并进行修改、删除、排序等操作,在操作过程中通过重载的运算符进行求和、求差、输出和输入操作,最后将链表内容存储到文件中,并从文件中构建链表对象进行遍历和判空操作。
通过测试,可以验证链表类和模板链表类的功能是否正常,并确认各个操作的实现是否正确。
### 回答3:
常规链表类:
```c++
#include<iostream>
#include<fstream>
using namespace std;
// 链表节点
template<class T>
class Node {
public:
T data; // 节点数据
Node *next; // 下一个节点指针
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
// 常规链表类
template<class T>
class LinkedList {
private:
Node<T> *head; // 头节点
int size; // 链表大小
public:
LinkedList() {
head = nullptr;
size = 0;
}
// 在头部插入节点
void insertHead(T data) {
Node<T> *newNode = new Node<T>(data);
newNode->next = head;
head = newNode;
size++;
}
// 在尾部插入节点
void insertTail(T data) {
Node<T> *newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
} else {
Node<T> *current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
size++;
}
...
// 存储到文件
void saveToFile(string filename) {
ofstream file(filename);
if (file.is_open()) {
Node<T> *current = head;
while (current != nullptr) {
file << current->data << " ";
current = current->next;
}
file.close();
}
}
// 从文件构建链表
void buildFromFile(string filename) {
ifstream file(filename);
if (file.is_open()) {
T data;
while (file >> data) {
insertTail(data);
}
file.close();
}
}
...
};
```
模板链表类:
```c++
#include<iostream>
#include<fstream>
using namespace std;
// 链表节点
template<class T>
class Node {
public:
T data; // 节点数据
Node *next; // 下一个节点指针
Node(T data) {
this->data = data;
this->next = nullptr;
}
};
// 模板链表类
template<class T>
class LinkedList {
private:
Node<T> *head; // 头节点
int size; // 链表大小
public:
LinkedList() {
head = nullptr;
size = 0;
}
// 在头部插入节点
void insertHead(T data) {
Node<T> *newNode = new Node<T>(data);
newNode->next = head;
head = newNode;
size++;
}
// 在尾部插入节点
void insertTail(T data) {
Node<T> *newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
} else {
Node<T> *current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
size++;
}
...
// 存储到文件
void saveToFile(string filename) {
ofstream file(filename);
if (file.is_open()) {
Node<T> *current = head;
while (current != nullptr) {
file << current->data << " ";
current = current->next;
}
file.close();
}
}
// 从文件构建链表
void buildFromFile(string filename) {
ifstream file(filename);
if (file.is_open()) {
T data;
while (file >> data) {
insertTail(data);
}
file.close();
}
}
...
};
```
在main函数中测试:
```c++
int main() {
LinkedList<int> list1;
list1.insertHead(3);
list1.insertHead(2);
list1.insertHead(1);
list1.insertTail(4);
list1.insertTail(5);
list1.insertAfter(3, 6);
list1.insertBefore(4, 7);
list1.modify(2, 8);
list1.remove(1);
list1.sort();
list1.saveToFile("data.txt");
LinkedList<int> list2;
list2.buildFromFile("data.txt");
// 进行其他操作
return 0;
}
```