Chapter 6. Linked List

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 6: Linked Lists
// Chapter 12: Simple search algorithms

// Linked List

#include "linked_list.h"

int main() {
  LinkedList list;
  char ch;
  for(ch = 65; ch < 75; ch++) {
    list.setLast();
    list.insert(ch);
  }

  list.print();
  cout << "\n--\n";
  list.print(list.getHead());
  cout << "\nInput data: "; cin >> ch;
  if(list.search(list.getHead(),ch)) cout << "found." << endl;
  // non-recursive call:  list.search(ch);
  else cout << "not found!" << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 6: Linked Lists
// Chapter 12: Simple search algorithms

// List
// File name: linked_list.h

#include <iostream>
using namespace std;

typedef char Data;
class Node {
  Data element;
  Node *next;
  Node(const Data evalue, Node* nvalue = NULL) {
    element = evalue; next = nvalue; }
  friend class LinkedList;
};

class LinkedList {
  Node* head;
  Node* tail;
  Node* curr;
public:
  LinkedList() { head = tail = curr = NULL; }
  ~LinkedList(){};
  Node *getHead();
  void insert(const Data);
  Data remove();
  void reset() { curr = NULL; }
  void next() { curr = curr->next; }
  void setFirst() { curr = head; }
  void setLast() { curr = tail; }
  void print();
  void print(Node *);
  Node *search(Data);
  Node *search(Node *, Data);
};

void LinkedList::insert(const Data item){
  if(!curr) {
    head = curr = new Node(item, head);
    if(!tail) tail = head;
  }
  else {
    curr->next = new Node(item, curr->next);
    if(tail == curr) tail = curr->next;
  }
}

void LinkedList::print() {
  setFirst();
  while(curr) {
    cout << curr->element << " ";
    next();
  }
}

inline Node* LinkedList::getHead() { return head;}

void LinkedList::print(Node *p) {
  if(!p) return;
  else {
    print(p->next);
    cout << p->element << " ";
  }
}

// Search function using loop
Node *LinkedList::search(Data d) {
  setFirst();
  while(curr && (curr->element != d)) next();
  return curr;
}

// Search function using recursion
Node *LinkedList::search(Node *p, Data d) {
  if(p) {
    if(p->element == d) return p;
    else return search(p->next, d);
  }
  else return p;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 6: Linked Lists

// The cat eats Mth mouse from N mice that numbered from 1 to N. Find a number of the last mouse
// Using array, but list

#include <iostream>
#include <algorithm>

using namespace std;

int main() 
{
  int i,M,N, eta, step, *mouse;
  cout << "How many mouse: "; cin >> N;
  cout << "Step: "; cin >> M;

  mouse = new int [N] (); 
  fill_n(mouse, N, 1);
  eta = step = 0; i = N-1;
  
  while(eta < N-1) {
    i = (++i)%N;
    if(mouse[i])
      if(!(step =(step+1)% M)) {
  mouse[i] = 0;
  eta++;
      }
  }

  i=0;
  while(!mouse[i++]);
  cout << "Number of the last mouse: " << i << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 6: Linked Lists

// The cat eats M-th mouse from N mice that numbered from 1 to N. Find a number of the last mouse
// Using single linked list

#include <iostream>
using namespace std;
typedef int Type;
class Mouse {
  Type number;
  Mouse *next;
  Mouse(const Type mnum, Mouse* nm) {
    number = mnum; next = nm; }
  friend class MouseList;
};

class MouseList {
  Mouse *head, *curr;
public:
  MouseList() { head =  curr = NULL; }
  ~MouseList(){};
  void insert(const Type);
  Type eat();
  void next() { curr = curr->next; }
  int isLast() { return curr == curr->next; }
  void lastMouse() { 
    cout << "Number of the last mouse: " << curr->number << endl; }
};

void MouseList::insert(const Type num){
  if(!head) {
    head = curr = new Mouse(num, head);
    curr->next = head;
  }
  else {
    curr->next = new Mouse(num, head);
    next();
  }
}
 
Type MouseList::eat() {
  Mouse *temp;
  int mnum;
  temp = curr->next;
  curr->next = temp->next;
  mnum = temp->number;
  delete temp;
  return mnum;
}

int main() {
  MouseList mlist;
  int N, M, step=0;

  cout << "How many mouse: "; cin >> N;
  cout << "Step: "; cin >> M;

  for(int i=1; i<=N; i++) mlist.insert(i);
  
  while(!mlist.isLast()) {
    if(!(step = ++step%M)) mlist.eat();
    else mlist.next();
  }
  mlist.lastMouse();
}