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

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
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
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
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
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
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
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
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
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
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
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
Mô tả insertAtFront

(a) firstNode
7 11

new ListNode
12

(b) firstNode
7 11

new ListNode
12




12
Mô tả insertAtBack

(a) firstNode lastNode new ListNode




12 7 11 5



(b) firstNode lastNode new ListNode




12 7 11 5




13
Mô tả removeFromFront

firstNode lastNode
(a)




12 7 11 5

firstNode lastNode
(b)




12 7 11 5



removeItem




14
Mô tả removeFromBack
firstNode lastNode
(a)




12 7 11 5

firstNode current lastNode
(b)




12 7 11 5




removeItem



15
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
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
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
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
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
Cài đặt Queue
public class Queue
{
      private LinkedList queueList;
      public Queue() 
      { 
           queueList = new LinkedList(); 
      }
      public void enqueue( int value )
      { 
           queueList.insertAtBack( value ); 
      }
      public int dequeue()  { return queueList.removeFromFront();  }
      public boolean isEmpty() { return queueList.isEmpty(); }
      public void print() { queueList.print(); }
}

21
Sử dụng Queue
public class QueueTest
{
      public static void main(String[] args) 
      {
Queue queue = new Queue();
queue.enqueue(5);
queue.enqueue(7);
queue.enqueue(4);
queue.enqueue(8);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();
      }
}


22
Tree
• Tree là một cấu trúc phi tuyến (non­linear). 
• Mỗi node trên cây có thể có nhiều liên kết tới node 
khác.
Nút gốc


Nút trong




Nút lá

23
Binary Search Tree
• Cây nhị phân là cây mà mỗi node không có quá 2 
node con.
• Cây tìm kiếm nhị phân là cây nhị phân mà:
• Giá trị các nút thuộc cây con bên trái nhỏ hơn giá trị của 
nút cha.
• Giá trị các nút thuộc cây con bên phải lớn hơn giá trị của 
nút cha.
• Duyệt cây nhị phân
• Inorder traversal
• Preorder traversal
• Postorder traversal

24
Binary Search Tree

• Ví dụ về Binary Search Tree
47

Cây con trái Cây con phải
25 77

11 43 65 93

7 17 31 44 68



25
Cài đặt Binary Search Tree
public class TreeNode 
{
     int data;       
     TreeNode leftNode, rightNode;  
     public TreeNode( int nodeData )
     { 
          data = nodeData;              
          leftNode = rightNode = null;
     }
     public void insert( int value )
     {
         if ( value  data ) {
              if ( rightNode == null ) rightNode = new TreeNode(value);
              else rightNode.insert( value );
         }
     }  26
}
Cài đặt Binary Search Tree
public class Tree 
{
      private TreeNode root;
      public Tree() 
      { 
            root = null; 
      }
      public void insertNode( int insertValue )
      {
            if ( root == null )
                 root = new TreeNode( insertValue );
            else
                 root.insert( insertValue );
      }
      public void preorderTraversal()
      { 
            preorder( root ); 
      }         27
Cài đặt Binary Search Tree
     public void inorderTraversal()
     { 
           inorder( root ); 
     }
     public void postorderTraversal()
     { 
           postorder( root ); 
     }
     private void preorder( TreeNode node )
     {
           if ( node == null )        
                 return;
           System.out.print( node.data + " " );  
           preorder( node.leftNode );     
           preorder( node.rightNode );     
     }

28
Cài đặt Binary Search Tree
     private void inorder( TreeNode node )
     {
           if ( node == null )    
                 return;
           inorder( node.leftNode );
           System.out.print( node.data + " " );
           inorder( node.rightNode );
     }
     private void postorder( TreeNode node )
     {
           if ( node == null )      
                 return;
           postorder( node.leftNode );
           postorder( node.rightNode );
           System.out.print( node.data + " " );
     }
}

29
Sử dụng Binary Search Tree
public class TreeTest 
{
      public static void main( String[] args )
      {
           Tree tree = new Tree();
           int value;
           for ( int i = 1; i 
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản