fork download
copy 
  1. // Example program
  2. #include <iostream>
  3. #include <string>
  4. using namespace std ;
  5.  
  6. template <class E> 
  7. struct Node
  8. {
  9.     E element ; // lưu giá trị
  10.     Node<E> *next; // con trỏ để lưu địa chỉ node sau/kế
  11.  
  12.     Node( E v = E() , Node<E>* n = 0):element(v),next(n){}
  13. };
  14.  
  15.  
  16. template <class E> 
  17. class SList{
  18.     protected:
  19.         int size ; // số lg phần tử hiện tại 
  20.         Node<E> * head; // Con trỏ để lưu địa chỉ Node đầu tiên
  21.  
  22.     public:
  23.         SList(){
  24.             this -> size = 0 ;
  25.             this -> head = nullptr ;
  26.         }
  27.  
  28.         void print() const{
  29.             Node<E> * tmp = head ; // Biến tạm đi qua tất cả các node 
  30.             while( tmp != nullptr ) {
  31.                 cout << tmp -> element <<" ";
  32.                 tmp = tmp->next;
  33.             }
  34.             cout <<endl;
  35.         }
  36.  
  37.         void addFirst(E value) {
  38.             // B0: Khởi tạo Node với giá trị value
  39.             Node<E> * u = new Node<E> (value) ;
  40.             // B1: nối newNode -> node đầu hiện tại
  41.             u -> next = head ; // Do địa chỉ node đầu tiên dang 
  42.             // ở head
  43.             // B2: Nối head đến newNode 
  44.             head = u ;
  45.             size++;
  46.         }
  47.  
  48.         void removeFirst() {
  49.             Node<E>* tmp = head ; // Chứa node đầu cần giải phóng
  50.             head = head -> next  ; // Nối head đến node thứ 2
  51.             delete tmp ; // Giải phóng node đầu cũ
  52.             size--;
  53.         }
  54.  
  55.  
  56.        // O(size)
  57.         // Lay ra gia tri tai vi tri thu index
  58.         E getElement(int index) {
  59.             if ( index < 0 or index > size )
  60.                 return E() ;
  61.         //   head[5]
  62.             Node<E> *tmp = head ; // Mang nhiem vu duyet qua lan luot cac node o trong ds
  63.  
  64.             int cnt = 0 ; // dem la da duyet duoc bao nhieu Node
  65.             while( tmp != nullptr) {
  66.                 if ( cnt == index)  // Neu da duyet den vi tri thu index => dung lai
  67.                     return tmp -> element ;
  68.                 cnt++;
  69.                 tmp = tmp -> next ;
  70.             }
  71.         }
  72.  
  73.         // O(size)
  74.         // Lieu ap dung tim kiem nhi phan vao SList co duoc khong ?
  75.         bool find(E value) const{
  76.             Node<E> *tmp = head ; // Mang nhiem vu duyet qua lan luot cac node o trong ds
  77.  
  78.             while( tmp != nullptr) {
  79.                 if ( tmp -> element == value)
  80.                     return true;
  81.                 tmp = tmp -> next ;
  82.             }
  83.  
  84.             return false;
  85.         }
  86.  
  87.         // chen vao vi tri thu index
  88.  
  89.         void add (int index, E value) {
  90.             if ( index == 0 ) {
  91.                 addFirst(value);
  92.                 return ;    
  93.             }
  94.  
  95.         // Buoc 1: Tao Node u voi value
  96.             Node <E> * u = new Node<E> (value);
  97.             Node<E> * tmp = head ;
  98.  
  99.         // Buoc 2: Duyet den vi tri thu index  - 1
  100.             for ( int i = 0; i < index - 1 ; i++)
  101.                 tmp= tmp-> next ;
  102.  
  103.         // Buoc 3: Noi u voi index
  104.             u -> next = tmp -> next;
  105.         // Buoc 4: Noi index - 1 voi u 
  106.             tmp-> next = u ;
  107.  
  108.         // Buoc 5: size++;
  109.             size++;
  110.         }
  111.  
  112.         void remove( int index) {
  113.             Node<E> * tmp = head ;
  114.         // Buoc 2: Duyet den vi tri thu index  - 1
  115.             for ( int i = 0; i < index - 1 ; i++)
  116.                 tmp= tmp-> next ;
  117.             // Buoc 3: Tao Node de luu node hien tai
  118.             Node<E> * old = tmp -> next;
  119.             // Buoc 4: Noi Node i - 1 den Node i + 1
  120.             tmp -> next = old -> next ;
  121.             delete old;
  122.             size--;
  123.         }
  124. };
  125.  
  126. int main()
  127. {
  128.     SList<int> s1; 
  129.     s1.addFirst(10) ; // 10
  130.     s1.addFirst(9) ; // 9 10
  131.     s1.addFirst(11) ; // 11 9 10
  132.     s1.addFirst(7) ; //7 11 9 10
  133.     s1.print();
  134.     cout << s1.getElement(-1) <<endl;
  135.     cout << s1.find(8) <<endl;   
  136.     s1.add(1, 20) ; // 7 20 11 9 10
  137.     s1.print();
  138.     s1.add(5, 100) ; // 7 20 11 9 10 100
  139.     s1.print();
  140.     s1.remove(1); // 7 11 9 10 100
  141.     s1.print();
  142.     s1.remove(3); // 7 11 9 100
  143.     s1.print();
  144. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 11 9 10 
0
0
7 20 11 9 10 
7 20 11 9 10 100 
7 11 9 10 100 
7 11 9 100
https://ideone.com/4yebHc
language:
C++ (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!