从文件导入c++插入排序(&I)

Question

我正在做一个需要这样做的项目：

在C++中创建一个类，该类是一个双向链接的整数列表。

此类应具有以下功能：-Normal插入功能(push_back，push_front) -Normal删除功能(pop_back，pop_front)排序功能-3 \f25 -Insertion Sort -Merge -3\f25 Sort -Bubble -3\f6排序

排序方法应打印出处理时间(下至微秒或毫秒)和所使用的排序(例如，气泡排序完成后，气泡排序- 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;
}

Answer 1

成功打开文件后，您需要添加一个执行以下操作的循环：

read a number from the file into temp variable
firstList.pushlast(temp)

关于排序，我相信您应该移动列表中的节点(而不是在节点之间复制值-这是在数组中完成的方式)来对列表进行排序。