nat-code

Untitled

From Bistre Hummingbird, 3 Years ago, written in Plain Text, viewed 268 times.
URL https://code.nat.moe/view/194b724d Embed
Download Paste or View Raw
  1. //CIS554 HW1
  2. //Due: 11:59PM, Friday (Feb. 1st)
  3. //Do not modify main funaiton.
  4. //Do not introduce new functions
  5.  
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. class node {
  10. public:
  11.         int value;
  12.         node * next;
  13.         node * previous;
  14.         node(int i) { value = i; next = previous = nullptr; }
  15.         node() { next = previous = nullptr; }
  16. };
  17.  
  18. class doubly_linked_list {
  19. public:
  20.         node * head;
  21.         node * tail;
  22.         doubly_linked_list() { head = tail = nullptr; }
  23.         void make_random_list(int m, int n);
  24.         void print_forward();
  25.         void print_backward();
  26.  
  27.         //inplement the following member functions:
  28.  
  29.         void sort();//sort all values based on frequency.
  30.                                                   //In case of ties, the values occur earlier will appear earlier
  31.                                                   //Example:  for list with values  7 6 12 4 33 12 6 6 7
  32.                                                   //sorted results: 6 6 6 7 7 12 12 4 33
  33.  
  34.         doubly_linked_list operator+(const doubly_linked_list &L);//L is read-only
  35.                                                                                                                           //return a frequency_sorted list by combining the current frequency_sorted list with another
  36.                                                                                                                           //frequency_sorted list L
  37.                                                                                                                           //If your algorithm is inefficient, you might lose points.
  38.                                                                                                                           //The values in the current list occur before that of L.
  39.                                                                                                                           //You will not modify L.
  40.  
  41.         void insert(int k);
  42.         //after insert(12) to the above,
  43.         //we have 6 6 6 12 12 12 7 7 4 33
  44.         //Insert value k to a frequency_sorted list
  45.         //After insert, the list remains frequency_sorted
  46.  
  47.  
  48.  
  49.  
  50.  
  51.         void remove(int k, int n); //remove value k n times from a frequency_sorted list.
  52.                                                            //if there are fewer than n occurances of k, then remove all occurnces of k
  53.                                                            //The final result will remain a frequency_sorted list.
  54.                                                            //For example, if the list is 7 7 7 2 2 4 4 5 5 44 3
  55.                                                            //After remove(2,5), the list will become 7 7 7 4 4 5 5 44 3
  56. };
  57.  
  58. void doubly_linked_list::sort() {
  59.         node * p1, *p2;
  60.         p1 = head -> next;
  61.         while (p1 != nullptr) {
  62.                 p2 = p1->next;
  63.                 while (p2 != nullptr) {
  64.                         if (p1->value == p2->value) {
  65.                                 if (p2->next == nullptr) p2->previous->next = nullptr;
  66.                                 else {
  67.                                         p2->previous->next = p2->next;
  68.                                         p2->next->previous = p2->previous;
  69.                                 }
  70.                                 p2->next = p1->next;
  71.                                 p2->previous = p1;
  72.                         }
  73.                         p2 = p2->next;
  74.                 }
  75.                 p1 = p1->next;
  76.  
  77.         }
  78.  
  79. }
  80.  
  81. void doubly_linked_list::make_random_list(int m, int n) {
  82.  
  83.         for (int i = 0; i < m; i++) {
  84.                 node * p1 = new node(rand() % n);
  85.                 p1->previous = tail;
  86.                 if (tail != nullptr) tail->next = p1;
  87.                 tail = p1;
  88.                 if (head == nullptr) head = p1;
  89.         }
  90. }
  91.  
  92. void doubly_linked_list::print_forward() {
  93.         cout << endl;
  94.         node * p1 = head;
  95.         while (p1 != nullptr) {
  96.                 cout << p1->value << " ";
  97.                 p1 = p1->next;
  98.         }
  99. }
  100.  
  101. void doubly_linked_list::print_backward() {
  102.         cout << endl;
  103.         node * p1 = tail;
  104.         while (p1 != nullptr) {
  105.                 cout << p1->value << " ";
  106.                 p1 = p1->previous;
  107.         }
  108. }
  109.  
  110. int main() {
  111.         doubly_linked_list d1;
  112.         d1.make_random_list(50, 20);
  113.         d1.print_forward();
  114.         d1.print_backward();
  115.  
  116.         d1.sort();
  117.         d1.print_forward();
  118.         d1.print_backward();
  119.  
  120.         d1.insert(16);
  121.         d1.print_forward();
  122.         d1.print_backward();
  123.  
  124.         d1.insert(16);
  125.         d1.print_forward();
  126.         d1.print_backward();
  127.  
  128.         d1.insert(16);
  129.         d1.print_forward();
  130.         d1.print_backward();
  131.  
  132.         d1.insert(16);
  133.         d1.print_forward();
  134.         d1.print_backward();
  135.  
  136.         d1.remove(4, 3);
  137.         d1.print_forward();
  138.         d1.print_backward();
  139.  
  140.         getchar();
  141.         getchar();
  142.         return 0;
  143. }

Reply to "Untitled"

Here you can reply to the paste above

captcha
Powered by Stikked