Lập trình Java cơ bản

Chia sẻ: thaiduongae

Linked List là cấu trúc gồm các node liên kết với nhau thông qua các mối liên kết. Node cuối linked list được dặt là null để đánh dấu kết thúc danh sách. Liked list giúp tiết kiệm bộ nhớ so với mảng trong các bài toán xử lý danh sách. Khi chèn/ xóa một node trên linked list, không phải dãn/ dồn các phần tử như trên mảng. Việc truy nhập trên linked list luôn phải tuần tự

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Lập trình Java cơ bản

 

  1. Lập trình Java cơ bản Cao Đức Thông ­ Trần Minh Tuấn cdthong@ifi.edu.vn, tmtuan@ifi.edu.vn  1
  2. Bài 8. Collections • Cấu trúc dữ liệu trong Java • Linked List • Stack và Queue • Tree • Collections Framework • Danh sách (List) • Tập hợp (Set) • Bảng ánh xạ (Map) • Bài tập 2
  3. Cấu trúc dữ liệu • Cấu trúc dữ liệu là cách tổ chức dữ liệu để giải  quyết vấn đề. • Một số cấu trúc dữ liệu phổ biến: • Mảng (Array) • Danh sách liên kết (Linked List) • Ngăn xếp (Stack) • Hàng đợi (Queue) • Cây (Tree) 3
  4. Linked List • Linked list là cấu trúc gồm các node liên kết với nhau  thông qua các mối liên kết. Node cuối linked list  được đặt là null để đánh dấu kết thúc danh sách. • Linked list giúp tiết kiệm bộ nhớ so với mảng trong  các bài toán xử lý danh sách. • Khi chèn/xoá một node trên linked list, không phải  dãn/dồn các phần tử như trên mảng. • Việc truy nhập trên linked list luôn phải tuần tự. 4
  5. Linked List • Thể hiện Node thông qua lớp tự tham chiếu (self­ referential class) class Node { private int data; private Node nextNode; // constructors and methods ... } 15 10 5
  6. Linked List • Một linked list được quản lý bởi tham chiếu tới  node đầu và node cuối. firstNode lastNode H D ... Q 6
  7. Cài đặt Linked List // Dinh nghia mot node trong linked list          class ListNode  {      int data;      ListNode nextNode;      ListNode(int value)       { this(value, null);       }      ListNode(int value, ListNode node)      { data = value;     nextNode = node;       }      int getData()       {  return data;  }      ListNode getNext()  {  return nextNode;  } }     7
  8. Cài đặt Linked List // Dinh nghia lop LinkedList public class LinkedList  {       private ListNode firstNode;       private ListNode lastNode;          public LinkedList()        {  firstNode = lastNode = null;       }         public void insertAtFront(int insertItem)       { if ( isEmpty() )           firstNode = lastNode = new ListNode( insertItem ); else                  firstNode = new ListNode( insertItem, firstNode );       }      8
  9. Cài đặt Linked List     public void insertAtBack( int insertItem )     {         if ( isEmpty() )            firstNode = lastNode = new ListNode( insertItem );         else             lastNode = lastNode.nextNode = new ListNode( insertItem );     }     public int removeFromFront()     {         int removeItem = ­1;         if ( ! isEmpty() ) {  removeItem = firstNode.data;    if ( firstNode == lastNode )      firstNode = lastNode = null;             else      firstNode = firstNode.nextNode;         }         return removeItem;       } 9
  10. Cài đặt Linked List      public int removeFromBack()      { int removeItem = ­1; if ( ! isEmpty() ) {            removeItem = lastNode.data;         if ( firstNode == lastNode ) firstNode = lastNode = null;       else       { ListNode current = firstNode; while ( current.nextNode != lastNode )        current = current.nextNode; lastNode = current; current.nextNode = null;       } } return removeItem;      } 10
  11. Cài đặt Linked List      public boolean isEmpty()      {   return (firstNode == null);      }      public void print()      { ListNode node = firstNode; while (node != null) {                  System.out.print(node.data + " ");        node = node.nextNode; } System.out.println("\n");      } } 11
  12. Mô tả insertAtFront (a) firstNode 7 11 new ListNode 12 (b) firstNode 7 11 new ListNode 12 12
  13. Mô tả insertAtBack (a) firstNode lastNode new ListNode 12 7 11 5 (b) firstNode lastNode new ListNode 12 7 11 5 13
  14. Mô tả removeFromFront firstNode lastNode (a) 12 7 11 5 firstNode lastNode (b) 12 7 11 5 removeItem 14
  15. Mô tả removeFromBack firstNode lastNode (a) 12 7 11 5 firstNode current lastNode (b) 12 7 11 5 removeItem 15
  16. Sử dụng Linked List public class ListTest {       public static void main( String args[] )       { LinkedList list = new LinkedList();   list.insertAtFront( 5 ); list.insertAtFront( 7 ); list.insertAtBack( 9 ); list.insertAtBack( 8 ); list.insertAtBack( 4 ); list.print(); list.removeFromFront(); list.removeFromBack();           list.print();       } }   16
  17. Stack • Stack là một cấu trúc theo kiểu LIFO (Last In  First Out), phần tử vào sau cùng sẽ được lấy ra  trước. • Hai thao tác cơ bản trên Stack • Chèn phần tử: Luôn chèn vào đỉnh Stack (push) • Lấy ra phần tử: Luôn lấy ra từ đỉnh Stack (pop) 17
  18. Cài đặt Stack public class Stack {       private LinkedList stackList;       public Stack()          {             stackList = new LinkedList();        }       public void push( int value )       {            stackList.insertAtFront( value );        }       public int pop()  { return stackList.removeFromFront(); }       public boolean isEmpty()   { return stackList.isEmpty(); }       public void print() { stackList.print(); } } 18
  19. Sử dụng Stack public class StackTest {       public static void main(String[] args)        { Stack stack = new Stack(); stack.push(5); stack.push(7); stack.push(4); stack.push(8); stack.print(); stack.pop(); stack.pop(); stack.print();       } } 19
  20. Queue • Queue (Hàng đợi) là cấu trúc theo kiểu FIFO  (First In First Out), phần tử vào trước sẽ được lấy  ra trước. • Hai thao tác cơ bản trên hàng đợi • Chèn phần tử: Luôn chèn vào cuối hàng đợi  (enqueue) • Lấy ra phần tử: Lấy ra từ đầu hàng đợi (dequeue) 20
Theo dõi chúng tôi
Đồng bộ tài khoản