c++代码实现以单链表为文件存储结构稳定的直接插入排序。
时间: 2023-06-25 22:06:53 浏览: 122
下面是以单链表为文件存储结构稳定的直接插入排序的C++代码实现:
```c++
#include <iostream>
#include <fstream>
using namespace std;
struct Node{
int data;
Node *next;
};
void insert(Node *&head, int x){
Node *p = new Node;
p->data = x;
p->next = head;
head = p;
}
void print(Node *head){
while(head){
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
void readFromFile(Node *&head){
ifstream inFile;
inFile.open("data.txt");
if (!inFile) {
cerr << "Unable to open file data.txt";
exit(1);
}
int x;
while (inFile >> x) {
insert(head, x);
}
inFile.close();
}
void writeToFile(Node *head){
ofstream outFile;
outFile.open("result.txt");
if (!outFile) {
cerr << "Unable to open file result.txt";
exit(1);
}
while (head) {
outFile << head->data << endl;
head = head->next;
}
outFile.close();
}
void insertionSort(Node *&head){
Node *sortedHead = nullptr; //已排序部分的头结点
Node *cur = head; //未排序部分的头结点
while(cur){
Node *tmp = cur;
cur = cur->next;
//将tmp节点插入到已排序部分中
if(sortedHead == nullptr || tmp->data < sortedHead->data){
tmp->next = sortedHead;
sortedHead = tmp;
}else{
Node *p = sortedHead;
while(p->next && tmp->data >= p->next->data){
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
}
head = sortedHead;
}
int main(){
Node *head = nullptr;
readFromFile(head);
print(head);
insertionSort(head);
print(head);
writeToFile(head);
return 0;
}
```
其中,`readFromFile`函数从文件中读取数据并创建链表,`writeToFile`函数将排序后的链表写入文件。`insertionSort`函数实现直接插入排序算法,注意要保证算法的稳定性。
完整代码已经实现了单链表的创建、打印、排序和文件读写等操作,你可以直接运行并测试。
阅读全文