/ 猿问

# 求问使用智能指针双链表的插入排序问题

2018-11-06 12:57:08

//Implment insertion sort using smart pointers.

//You are not allowed to swap node values; instead, you are only

#include <iostream>

#include <memory>

using namespace std;

class node {

public:

int value;

//node * next;

//node * previous;

shared_ptr<node> next;

weak_ptr<node> previous;

//node(int i) { value = i; next = previous = nullptr; }

node(int i) { value = i; }

//node() { next = previous = nullptr; }

node() {}

};

public:

//node * tail;

void make_random_list(int m, int n);

void print_forward();

void print_backward();

//***************************

//You need to implement insertion_sort following the

//special requirements.

void insertion_sort();

};

void doubly_linked_list::make_random_list(int m, int n) {

for (int i = 0; i < m; i++) {

//node * p1 = new node(rand() % n);

shared_ptr<node> p1 = make_shared<node>(rand() % n);

p1->previous = tail;

//if (tail != nullptr ) tail->next = p1;

if (tail) tail->next = p1;

tail = p1;

}

}

cout << endl;

//while (p1 != nullptr) {

while (p1) {

cout << p1->value << " ";

p1 = p1->next;

}

}

cout << endl;

//node * p1 = tail;

shared_ptr<node> p1 = tail;

//while (p1 != nullptr) {

while (p1) {

cout << p1->value << " ";

p1 = p1->previous.lock();

}

}

int main() {

d1.make_random_list(30, 10);

d1.print_forward();

d1.print_backward();

d1.insertion_sort();

d1.print_forward();

d1.print_backward();

getchar();

getchar();

return 0;

}

• 0 回答
• 0 关注
• 754 浏览

0/150