我正在做一个需要这样做的项目：
在C++中，创建一个类，它是一个双链接的整数列表。
此类应具有以下内容：-正常插入功能（push_back、push_front）-正常删除功能（pop_back、pop_front）-3排序功能-插入排序-合并排序-气泡排序
排序方法应打印出处理时间（最短为微米或毫秒）和使用的排序（例如，在气泡排序完成后，气泡排序-100ms）。
创建一个程序，从文件中读取一堆数字，并创建您的链表（每次运行创建三个列表）。然后，程序应该按照每个方法进行排序。显示三次跑步的结果，一次包含100000个数字，一次显示10000个数字，另一次显示1000个数字。
我一直在尝试导入我的第一个文件（file1.txt），它有100000个整数，并将它们保存到我的双链接列表中。任何关于如何做到这一点的建议都将是非常棒的。接下来，我将尝试研究插入排序算法，到目前为止，我所拥有的是数组的插入排序，而不是双链表。如果你能扫描我的代码，给我任何建议，那就太好了。我从来没有用C++编写过代码，只用java编写过，这项任务对我来说很有挑战性！
#include<iostream>
//for time elapsed
#include <chrono>
using namespace std;
template <class T>
class doublylinkedlist
{
private :
struct node
{
T data;
node *prev;
node *next;
};
node *head;
node *tail;
public :
doublylinkedlist()
{
head=tail=NULL;
}
void createlist(T[] , int);
void pushfirst(T);
void pushlast(T);
void pushafter(T,T);
void pop(T);
void displayforward();
void displaybackward();
};
//creating doubly linked list
template<class T>
void doublylinkedlist<T>::createlist(T x[], int n) //n = size
{
node *q;
node *p=new node; //create first node
p->data=x[0];
p->next=NULL;
p->prev=NULL;
for(int i=1;i<n;i++)
{
q=p;
p=p->next=new node;
p->data=x[i];
p->next=NULL;
p->prev=q;
}
tail=p;
}
// Inserting new node at start of doubly linked list
template<class T>
void doublylinkedlist<T>::pushfirst(T item)
{
node *p=new node;
p->data=item;
p->prev=NULL;
head->prev=p;
}
//Inserting new node at last of Double Linkedlist
template<class T>
void doublylinkedlist<T>::pushlast(T item)
{
node *p=new node;
p->data=item;
p->prev=tail;
p->next=NULL;
tail=p;
}
//deleting item from double linked list
template<class T>
void doublylinkedlist<T>::pop(T item)
{
if(head==NULL)
{
cout<<"This list is empty!"<<endl;
return;
}
if(head->data==item)
{
head=head->next;
head->prev=NULL;
return;
}
if(tail->data==item)
{
tail=tail->prev;
tail->next=NULL;
return;
}
node *p=head->next;
while(p!=NULL)
{
if(p->data==item)
break;
p=p->next;
}
if(p==NULL)
{
cout<<item<<"not found "<<endl;
return;
}
(p->prev)->next=p->next;
(p->next)->prev=p->prev;
return;
}
//displaying list elements in forward direction
template<class T>
void doublylinkedlist<T>::displayforward()
{
node *p=head;
cout<<"n Doubly linked list (Forward)";
while(p!=NULL)
{
cout<<p->data<<"";
p=p->next;
}
}
//displaying list elements in reverse direction
template<class T>
void doublylinkedlist<T>::displaybackward()
{
node *p=tail;
cout<<"n Doubly linked list (Backward)";
while(p!=NULL)
{
cout<<p->data<<"";
p=p->prev;
}
}
//insertion sort function
void doublylinkedlist<T>::insertionSort(T x[], int n)
{
auto beg = std::chrono::high_resolution_clock::now();
int i, j ,tmp;
for (i = 1; i < n; i++)
{
j = i;
while (j > 0 && x[j - 1] > x[j])
{
tmp = x[j];
x[j] = x[j - 1];
x[j - 1] = tmp;
j--;
}
printArray(x,5);
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - beg).count() << std::endl;
std::cin.get();
return 0;
}
int main()
{
ifstream myfile ("file1.txt");
if (myfile.is_open())
{
//i need to insert the file into the doubly linked list here.
//file.txt is has 100000 integers
doublylinkedlist<int> firstList;
myfile.close();
}
else cout << "Unable to open file";
return 0;
//replace this with input from file
//10000 numbers
doublylinkedlist<int> secondList;
//1000 numbers
doublylinkedlist<int> thirdList;
//example of what to run
firstList.createlist(x,2);
firstList.pushfirst(22);
firstList.pushlast(55);
firstList.pushafter(66,33);
firstList.pop(22);
firstList.pop(55);
firstList.pop(66);
return 0;
}
成功打开文件后，您需要添加一个循环执行：
read a number from the file into temp variable
firstList.pushlast(temp)
关于排序，我相信您应该移动列表中的节点（而不是像在数组中那样在节点之间复制值）以使列表排序。