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
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
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)
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ự.
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
6
Linked List

Một linked list được quản lý bởi tham
chiếu tới node đầu và node cuối.
H D Q
firstNode lastNode
...
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; }
}
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 );
}
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;
}
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;
}
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");
}
}
12
Mô tả insertAtFront
7 11
firstNode
12
new ListNode
(a)
7 11
firstNode
12
new ListNode
(b)
13
Mô tả insertAtBack
12 7 11
firstNode lastNode
(a)
5
new ListNode
12 11
firstNode lastNode
(b)
5
new ListNode
7
14
Mô tả removeFromFront
firstNode lastNode
(a)
11
firstNode lastNode
(b)
removeItem
12
12
7
7
5
5
11
12
15
Mô tả removeFromBack
5
5
11
7
7
12
12
firstNode lastNode
(a)
firstNode lastNode
(b)
removeItem
current
11
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();
}
}
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)
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(); }
}
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();
}
}
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)
21
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(); }
}
22
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();
}
}
23
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 lá
Nút trong
24
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
25
Binary Search Tree

Ví dụ về Binary Search Tree
47
25 77
11 43 65 93
687 17 31 44
Cây con trái Cây con phải