[C/C++] Ép chữ thường thành chữ hoa trong C/C++

Chương trình sau dùng để chuyển đổi chữ thường thành  chữ hoa. Logic của chương trình như sau: Tất cả các chữ cái thường (a đến z) có giá trị trong bảng mã ASCII nằm trong khoảng 97 đến 122 và các chữ cái hoa tương ứng (A đến Z) có giá trị nhỏ hơn 32 trong bảng mã ASCII.
Ví dụ: chữ cái 'a' trong bảng mã ASCII có giá trị là 97 và chữ cái 'A' trong bảng mã ASCII có giá trị 65 (97-32). Các chữ cái khác cũng theo quy tắc tương tự.
Theo logic đó chương trình cài đặt thực hiện ép chữ cái thường thành chữ cái hoa.

#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;
int main(){
 char inputString[] = "simplecodecjava.blogspot.com";
 char outputString[256];
 for(int index = 0; index < sizeof(inputString); index++){
  if(inputString[index] >='a' && inputString[index] <='z'){
   //ký tự là chữ cái thường.
   outputString[index] = inputString[index] - 32;
  }else {
   //ký tự là ký tự hoa hoặc là ký tự đặc biệt.
   outputString[index] = inputString[index];
  }
 }
 cout<<"string chữ hoa: " << outputString;
 _getch();
 return 0;
}

JSON Tutorial - Kiến thức căn bản về JSON.

1. JSON
JSON là viết tắt của JavaScript Object Notation. JSON được sử dụng để truyền dữ liệu giữa Server và Client, XML cũng được sử dụng để truyền dữ liệu giữa Server và Client. Tuy nhiên việc truyền dữ liệu bằng JSON Objects có một vài lợi thế so với XML. Bài viết này sẽ đưa ra cái nhìn tổng quan về JSON và cách sử dụng JSON.
Dữ liệu kiểu JSON là một cặp key - value.

var student = {
   "firstName" : "Hạnh",
   "lastName" : "Nguyễn",
   "age" :  "23"
}; 

Với các chú ý sau:
- Chuỗi JSON được được bắt đầu và kết thúc bằng cặp dấu '{}'.
- Các key và value của JSON được đặt trong dấu nháy kép   " " . Nếu value có chứa dấu nháy kép ' " ' thì cần phải đặt ký tự ' \ ' trước dấu nháy kép. Ví dụ value = "simplecodecjava.blogspot.com" thì khi định nghĩa dữ liệu trong JSON phải viết là \"simplecodecjava.blogspot.com\".
- Nếu có nhiều dữ liệu ( nhiều cặp key-value) thì ta dùng dấu ' ,' để ngăn cách các cặp dữ liệu.
- Các key của JSON thường được đặt là các chữ cái không dấu, chữ số, dấu '_' và không có khoảng trắng.
2. Đặc trưng của JSON
- Là kiểu dữ liệu nhẹ.
- Không phụ thuộc vào ngôn ngữ.
- Dễ đọc và viết.
- Viết dựa trên text, nên có thể dễ dàng hiểu nội dung của JSON.
 3. Tại sao sử dụng JSON.
 - Cấu trúc chuẩn: JSON được định nghĩa theo một cấu trúc chuẩn nó giúp cho Developer dễ dàng đọc, viết và hiểu. Vì vậy mà các Developer thường chọn JSON.
- Là kiểu dữ liệu nhẹ: Khi làm việc với AJAX cần phải load dữ liệu nhanh và đồng bộ mà không cần phải gửi request lại. Vì JSON là kiểu dữ liệu nhẹ nên việc tải và request dữ liệu nhanh hơn.
- Khả năng linh hoạt: JSON không phụ thuộc vào ngôn ngữ, điều đó có nghĩa là nó hoạt động tốt với hầu hết tất cả các ngôn ngữ lập trình hiện đại. Giả xử khi cần thay đổi ngôn ngữ lập trình bên phía server, trong trường hợp này việc thay đổi kiến trúc của JSON trở nên dễ dàng cho mọi ngôn ngữ lập trình.
4. JSON vs. XML
Hãy xem cách mà JSON và XML lưu trữ 4 bản ghi học sinh .
Dữ liệu dưới dạng JSON.

{"students":[
   {"name":"Tuấn", "age":"23", "city":"Hà Nội"},
   {"name":"Đạt", "age":"28", "city":"Đà Nẵng"},
   {"name":"Lan", "age":"32", "city":"Thừa Thiên Huế"},
   {"name":"Yến", "age":"28", "city":"TP.Hồ Chí Minh"}
]}

Dữ liệu dưới dạng XML.

<students>
  <student>
    <name>Tuấn</name> <age>23</age> <city>Hà Nội</city>
  </student>
  <student>
    <name>Đạt</name> <age>28</age> <city>Đà Nẵng</city>
  </student>
  <student>
    <name>Lan</name> <age>32</age> <city>Thừa Thiên Huế</city>
  </student>
  <student>
    <name>Yến</name> <age>28</age> <city>TP.Hồ Chí Minh</city>
  </student>
</students>

Có thể dễ dàng thấy rằng dữ liệu dưới dạng JSON thì  nhẹ hơn so với dữ liệu dưới dạng XML.
5. Kiến trúc dữ liệu kiểu và cách đọc JSON.
a. Đối tượng JSON.

var person= {
  "name" : "ZappyMans",
  "age" = "24",
  "website" = "simplecodecjava.blogspot.com"
};

Để truy cập đữ liệu cho đối tượng JSON ở trên chúng ta viết key theo sau tên đối tượng theo mẫu sau:

<đối_tượng>.<key>
ví dụ:
Tên của đối tượng person: person.name
Tuổi của đối tượng person: person.age
Website của đối tượng person: person.website

b. Mảng đối tượng JSON.
Phần trên trình bày cách lưu trữ thông tin của một đối tượng person. Giả sử muốn lưu thông tin của nhiều hơn một đối tượng, trong trường hợp này chúng ta dùng mảng.

var students = [{
   "name" : "Lan",
   "age" :  "23",
   "gender" : "Nữ"
},
{
   "name" : "Tuấn",
   "age" : "24",
   "gender" : "Nam"
},
{
   "name" : "Yến",
   "age" : "21",
   "gender" : "Nữ"
}];

Để truy cập và lấy ra dữ liệu của một phần tử trong mảng, ta chèn thêm chỉ số và phần tử của mảng.

Tên của học sinh thứ 1: students[0].name // Lan
Tuổi của học sinh thứ 2: students[1].age //24
Giới tính của học sinh thứ 3: students[2].gender //Nữ 

c. Khai báo JSON theo cấu trúc lồng nhau.
Cách khác để truy cập và lấy ra dữ liệu của một phần tử của trong một mảng JSON được khai báo lồng nhau.

var students = {
  "Lan" : {
  "name" : "Lan",
  "age" :  "23",
  "gender" : "Nữ" 
},

"Tuấn" : {
  "name" : "Tuấn",
  "age" : "24",
  "gender" : "Nam"
},

"Yến" : {
  "name" : "Yến",
  "age" : "21",
  "gender" : "Nữ"
}
}

Tuổi của Lan : student.Lan.age // 23
Giới tính của Tuấn: student.Tuấn.gender // Nam

6. JSON và JavaScript.
JSON được xem là 'tập con' của JavaScript nhưng không có nghĩa là nó không thể dùng được với các ngôn ngữ khác. Trên thực tế JSON được sử dụng rất hiệu quả với PHP, Perl, Python, Ruby, Java, Ajax và nhiều ngôn ngữ nữa.
Để chứng minh JSON có thể sử dụng với JavaScript, hãy xem ví dụ sau.
a. Đọc dữ liệu từ file JSON và chuyển đổi thành JavaScript Object.

var student = {
   "firstName" : "Hạnh",
   "lastName" : "Nguyễn",
   "age" :  "23"
}; 

Để chuyển đối tượng JSON Object phía trên thành JavaScript Object sử dụng phương thức parse của JSON.

var javaScriptObject = JSON.parse(student); 

b. Chuyển đối tượng JavaScript Object thành JSON text 
Sử dụng phương thức stringify.

 var jsonObject = JSON.stringify(myObject);

[Java] Sắp xếp ArrayList trong Java

1. Sắp xếp mảng String ArrayList
Để sắp  xếp ArrayList có kiểu dữ liệu là String, ta dùng method Collections.sort(arraylist), dữ liệu được chứa trong ArrayList sẽ được sắp xếp theo thứ tự alphabetic.
Ví dụ.

package simplecodecjava.blogspot.com;

import java.util.ArrayList;
import java.util.Collections;

public class SortingInArrayList {
 public static void main(String[] args){
  ArrayList<String> arrayList = new ArrayList<>();
  arrayList.add("Hà Nội");
  arrayList.add("Đà Nẵng");
  arrayList.add("Nha Trang");
  arrayList.add("TP.Hồ Chí Minh");
  System.out.println("Trước khi sắp xếp");
  for(String item: arrayList){
   System.out.println(item);
  }
  Collections.sort(arrayList);
  System.out.println("Sau khi sắp xếp");
  for(String item: arrayList){
   System.out.println(item);
  }
 }
}

Kết quả output:

Trước khi sắp xếp
Hà Nội
Đà Nẵng
Nha Trang
TP.Hồ Chí Minh
Sau khi sắp xếp
Hà Nội
Nha Trang
TP.Hồ Chí Minh
Đà Nẵng

*note: Trong bảng mã Unicode ký tự Đ đứng sau ký tự T 

2. Sắp xếp mảng Interger ArrayList.
Tương tự như với mảng String, phương thức Collections.sort(arraylist) cũng được dùng để sắp xếp mảng Interger.
Ví dụ

package simplecodecjava.blogspot.com;

import java.util.ArrayList;
import java.util.Collections;

public class SortingInArrayList {
 public static void main(String[] args){
  ArrayList<Integer> arrayList = new ArrayList<>();
  arrayList.add(10);
  arrayList.add(2);
  arrayList.add(221);
  arrayList.add(991);
  System.out.println("Trước khi sắp xếp");
  for(Integer item: arrayList){
   System.out.println(item);
  }
  Collections.sort(arrayList);
  System.out.println("Sau khi sắp xếp");
  for(Integer item: arrayList){
   System.out.println(item);
  }
 }
}

Output:

Trước khi sắp xếp
10
2
221
991
Sau khi sắp xếp
2
10
221
991

3. Sắp xếp mảng Object ArrayList
Phương thức Collections.sort(arraylist) cũng được dùng để sắp xếp mảng đối tượng, tuy nhiên đối tượng cần phải là lớp thực thi của Comparable interaface hoặc viết lại phương thức compare của Comparator interface.
Trước tiên hãy xem ví dụ sau khi dùng Collections.sort(arraylist) mà chưa cài đặt bằng một trong hai cách trên.

package simplecodecjava.blogspot.com;

public class Student {
 private int MSV;
 private String ten;
 private int namsinh;
 private String khoa;
 public Student(int MSV, String ten, int namsinh, String khoa){
  this.MSV = MSV;
  this.ten = ten;
  this.namsinh = namsinh;
  this.khoa = khoa;
 }
 @Override
 public String toString() {
  return MSV + " - " + ten + " - " + namsinh + " - " + khoa;
 }
}

Main chương trình:

package simplecodecjava.blogspot.com;

import java.util.ArrayList;
import java.util.Collections;

public class SortingInArrayList {
 public static void main(String[] args){
  ArrayList<Student> arrayList = new ArrayList<Student>();
  arrayList.add(new Student(1, "Cảnh", 1991, "Công nghệ thông tin"));
  arrayList.add(new Student(5, "Tuấn", 1992, "Công nghệ thông tin"));
  arrayList.add(new Student(9, "Việt", 1994, "Điện tử viễn thông"));
  arrayList.add(new Student(1, "Tú Anh", 1993, "Công nghệ thông tin"));
  arrayList.add(new Student(1, "Liên", 1991, "Điện tử viễn thông"));
  arrayList.add(new Student(1, "Hiệp", 1990, "Điện tử viễn thông"));
  arrayList.add(new Student(1, "Quỳnh", 1992, "Công nghệ thông tin"));
  System.out.println("Trước khi sắp xếp");
  for(Student item: arrayList){
   System.out.println(item);
  }
  Collections.sort(arrayList);
  System.out.println("Sau khi sắp xếp");
  for(Student item: arrayList){
   System.out.println(item);
  }
 }
}

Với chương trình main trên, sẽ có thông báo lỗi ở dòng

Collections.sort(arrayList);

Với lỗi thông báo như sau:

Bound mismatch: The generic method sort(List) of type Collections is not applicable for the arguments 
 (ArrayList). The inferred type Student is not a valid substitute for the bounded parameter >

Lỗi trên có thể được fix bằng một trong hai cách sau:
3.1 Cài đặt Class Student là lớp thực thi của Comparable interaface.

package simplecodecjava.blogspot.com;

public class Student implements Comparable<Student>{
 private int MSV;
 private String ten;
 private int namsinh;
 private String khoa;
 public Student(int MSV, String ten, int namsinh, String khoa){
  this.MSV = MSV;
  this.ten = ten;
  this.namsinh = namsinh;
  this.khoa = khoa;
 }
 @Override
 public String toString() {
  return MSV + " - " + ten + " - " + namsinh + " - " + khoa;
 }
 // sắp xếp sinh viên theo tên và theo khoa.
 @Override
 public int compareTo(Student o) {
  if(this.khoa.compareTo(o.khoa)== 0){
   return this.ten.compareTo(o.ten);
  }else{
   return this.khoa.compareTo(o.khoa);
  }
 }
}

Output: Sắp  xếp sinh viên theo khoa và theo tên theo thứ tự tăng dần.

Trước khi sắp xếp
1 - Cảnh - 1991 - Công nghệ thông tin
5 - Tuấn - 1992 - Công nghệ thông tin
9 - Việt - 1994 - Điện tử viễn thông
10 - Tú Anh - 1993 - Công nghệ thông tin
22 - Liên - 1991 - Điện tử viễn thông
17 - Hiệp - 1990 - Điện tử viễn thông
23 - Quỳnh - 1992 - Công nghệ thông tin
Sau khi sắp xếp
1 - Cảnh - 1991 - Công nghệ thông tin
23 - Quỳnh - 1992 - Công nghệ thông tin
5 - Tuấn - 1992 - Công nghệ thông tin
10 - Tú Anh - 1993 - Công nghệ thông tin
17 - Hiệp - 1990 - Điện tử viễn thông
22 - Liên - 1991 - Điện tử viễn thông
9 - Việt - 1994 - Điện tử viễn thông

3.2 Viết lại phương thức compare của Comparator interface.
Với cách này chúng ta không cần cài đặt Student là lớp thực thi từ Comparator interface như ở 3.1, thay vào đó phương thức compare của Comparator interace được viết lại như sau:

package simplecodecjava.blogspot.com;
import java.util.Comparator;
public class Student{
 private int MSV;
 private String ten;
 private int namsinh;
 private String khoa;
 public Student(int MSV, String ten, int namsinh, String khoa){
  this.MSV = MSV;
  this.ten = ten;
  this.namsinh = namsinh;
  this.khoa = khoa;
 }
 @Override
 public String toString() {
  return MSV + " - " + ten + " - " + namsinh + " - " + khoa;
 }
 public static Comparator<Student> compare = new Comparator<Student>() {

  @Override
  public int compare(Student o1, Student o2) {
   if(o1.khoa.compareTo(o2.khoa)== 0){
    return o1.ten.compareTo(o2.ten);
   }else{
    return o1.khoa.compareTo(o2.khoa);
   }
  }
 };
 }

Main chương trình:

package simplecodecjava.blogspot.com;

import java.util.ArrayList;
import java.util.Collections;

public class SortingInArrayList {
 public static void main(String[] args){
  ArrayList<Student> arrayList = new ArrayList<Student>();
  arrayList.add(new Student(1, "Cảnh", 1991, "Công nghệ thông tin"));
  arrayList.add(new Student(5, "Tuấn", 1992, "Công nghệ thông tin"));
  arrayList.add(new Student(9, "Việt", 1994, "Điện tử viễn thông"));
  arrayList.add(new Student(10, "Tú Anh", 1993, "Công nghệ thông tin"));
  arrayList.add(new Student(22, "Liên", 1991, "Điện tử viễn thông"));
  arrayList.add(new Student(17, "Hiệp", 1990, "Điện tử viễn thông"));
  arrayList.add(new Student(23, "Quỳnh", 1992, "Công nghệ thông tin"));
  System.out.println("Trước khi sắp xếp");
  for(Student item: arrayList){
   System.out.println(item);
  }
  Collections.sort(arrayList, Student.compare);
  System.out.println("Sau khi sắp xếp");
  for(Student item: arrayList){
   System.out.println(item);
  }
 }
}

Output:

Trước khi sắp xếp
1 - Cảnh - 1991 - Công nghệ thông tin
5 - Tuấn - 1992 - Công nghệ thông tin
9 - Việt - 1994 - Điện tử viễn thông
10 - Tú Anh - 1993 - Công nghệ thông tin
22 - Liên - 1991 - Điện tử viễn thông
17 - Hiệp - 1990 - Điện tử viễn thông
23 - Quỳnh - 1992 - Công nghệ thông tin
Sau khi sắp xếp
1 - Cảnh - 1991 - Công nghệ thông tin
23 - Quỳnh - 1992 - Công nghệ thông tin
5 - Tuấn - 1992 - Công nghệ thông tin
10 - Tú Anh - 1993 - Công nghệ thông tin
17 - Hiệp - 1990 - Điện tử viễn thông
22 - Liên - 1991 - Điện tử viễn thông
9 - Việt - 1994 - Điện tử viễn thông

[Java] ArrayList trong Java

ArrayList là một Class implement (thực thi) của List Interface, được sử dụng phổ biến bởi khả năng linh động của nó. Hầu hết tất cả các developer chọn ArrayList thay vì Array truyền thống như trong C/C++.
Vấn đề với Array đó là kích thước cố định của nó, nếu Array được khai báo có kích thước n phần tử thì khi Array đã chứa đầy n phần tử thì ta không thể chèn thêm bất kỳ phần tử nào nữa. Còn ArrayList thì khác ta có thể chèm thêm tùy ý mà không cần lo lắng là ArrayList sẽ bị đầy, chính vì đặc tính này mà giúp cho ArrayList phổ biến hơn Array.
Ví dụ về ArrayList.

import java.util.ArrayList;
public class ArrayListExample {
 public static void main(String args[]) {
       /*
        *Tạo ArrayList: Thêm String
        *Dữ liệu được thêm vào có kiểu dữ liệu là String
        **/
    ArrayList<String> obj = new ArrayList<String>();
    /*This is how elements should be added to the array list*/
    obj.add("Hà Nội");
    obj.add("Đà Nẵng");
    obj.add("TP Hồ Chí Minh");
    obj.add("Hoàng Sa");
    obj.add("Trường Sa");
    System.out.println("ArrayList chứa những String sau.:"+obj);
    /*Thêm String mới vào các vị trí*/
    obj.add(0, "Nha Trang");
    obj.add(1, "Đà Lạt");
    /*Loại bỏ String khỏi ArrayList*/
    obj.remove("Đà Nẵng");
    obj.remove("TP Hồ Chí Minh");
    System.out.println("ArrayList mới nhận được:"+obj);
    /*Loại bỏ String ở vị trí 1*/
    obj.remove(1);
    System.out.println("ArrayList mới nhận được:"+obj);
    }
}

Kết quả chương trình:

ArrayList chứa những String sau.:[Hà Nội, Đà Nẵng, TP Hồ Chí Minh, Hoàng Sa, Trường Sa]
ArrayList mới nhận được:[Nha Trang, Đà Lạt, Hà Nội, Hoàng Sa, Trường Sa]
ArrayList mới nhận được:[Nha Trang, Hà Nội, Hoàng Sa, Trường Sa]

Các Method của ArrayList class.

1. add(Object o): Thêm một đối tượng vào trong ArrayList.

obj.add("Hello");

Thêm String "Hello" vào cuối ArrayList
2. add(int index, Object o): Thêm một đối tượng vào trong ArrayList ở vị trí index.

obj.add(2,"Hello");

Thêm String "Hello" vào vị trí thứ 2 của ArrayList.
3. boolean remove(Object o): Loại bỏ đối tượng o ra khỏi ArrayList.

obj.remove("Hello");

Loại bỏ String "Hello" trong ArrayList. Nếu  có String "Hello" phương thức sẽ trả về TRUE, nếu không có phương thức sẽ trả về FALSE.
4. E remove(int index): Loại bỏ đối tượng ở vị trí index.

obj.remove(1);

Loại bỏ đối  tượng ở vị trí index = 1 trong ArrayList. Kết quả trả về đối tượng ở vị trí số 1.
5. E set(int index, Object o): Được dùng để update một đối tượng, sẽ thay thế đối tượng ở vị trí index bằng đối tượng o. Phương thức trả về đối tượng ở vị trí index trước khi bị thay thế bởi đối tượng o.

obj.set(1,"Hello");

Thay thế String ở vị trí 1 bằng String "Hello", phương thức trả về String ở vị trí 1 trước khi bị thay thế bởi String "Hello".
6. int indexOf(Object o): Đưa ra vị trí của đối tượng o trong ArrayList. Nếu đối tượng không tìm thấy trong ArrayList method sẽ trả về -1.

obj.indexOf("Hello");

Trả về vị trí của String "Hello" có trong ArrayList. Nếu không có String "Hello" trong ArrayList, phương thức sẽ trả về -1.
7. Object get(int index): Trả về đối tượng của ArrayList ở vị trí index.

obj.get(1);

Trả về đối tượng ở vị trí 1.
8. int size(): Trả về số đối tượng có trong ArrayList.

obj.size();

9. boolean contains(Object o): Thực hiện kiểm tra đối tượng o có trong ArrayList hay không. Nếu có phương thức sẽ trả về TRUE, nếu không có phương thức sẽ trả về FALSE.

obj.contains("Hello");

Nếu ArayList có chứa String "Hello" phương thức sẽ trả về TRUE, nếu không chứa sẽ trả về FALSE.
10. clear(): Loại bỏ tất cả các đối tượng có trong ArrayList.

obj.clear();

Nếu bạn có câu hỏi hay góp ý xin hãy để lại ý kiến trong phần comment của bài viết.

[Java] HashMap trong Java và ví dụ

HashMap còn được gọi là mảng băm chứa cặp khóa - giá trị và được ký hiệu  HashMap <Key, Value> hoặc HashMap <K, V> . HashMap là implements(thực thi) của Map Interface. HaskMap tương tự như Hashtable, các phương thức của HashMap không đồng bộ (unsynchornized) và cho phép khóa và giá trị có thể nhận giá trị null. HashMap được sử dụng để lưu trữ ánh xạ giá trị vào khóa tương ứng.
HashMap không phải là một Collection có thứ tự điều đó có nghĩa là các giá trị được lấy từ HashMap ra không theo thứ tự mà chúng đã được chèn vào trong HashMap.
Ví dụ về HashMap:
Chương trình sau cài đặt hầu hết các method quan trọng của HashMap. Để biết thêm chi tiết về các phương thức bạn có thể xem thêm tại đây

package simplecodecjava;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class SimpleCodeCJava {
    public static void main(String[] args) {
     HashMap<Integer, String> hmap = new HashMap<Integer, String>();
      /*Thêm giá trị tương ứng vào các key.*/
      hmap.put(12, "Hà Nội");
      hmap.put(2, "Đà Nẵng");
      hmap.put(7, "Nha Trang");
      hmap.put(49, "Thành Phố Hồ Chí Minh");
      hmap.put(3, "Cà Mau");
      /* Hiện thị giá trị bên trong HashMap sử dụng Iterator*/
      Set set = hmap.entrySet();
      Iterator iterator = set.iterator();
      while(iterator.hasNext()) {
         Map.Entry mentry = (Map.Entry)iterator.next();
         System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
         System.out.println(mentry.getValue());
      }

      /* Lấy ra giá trị dựa vào key*/
      String var= hmap.get(2);
      System.out.println("Value at index 2 is: "+var);

      /* Xóa dữ liệu dựa vào key*/
      hmap.remove(3);
      System.out.println("Map key and values after removal:");
      Set set2 = hmap.entrySet();
      Iterator iterator2 = set2.iterator();
      while(iterator2.hasNext()) {
          Map.Entry mentry2 = (Map.Entry)iterator2.next();
          System.out.print("Key is: "+mentry2.getKey() + " & Value is: ");
          System.out.println(mentry2.getValue());
       }
   }
}

Kết quả chạy chương trình:

key is: 49 & Value is: Thành Phố Hồ Chí Minh
key is: 2 & Value is: Đà Nẵng
key is: 3 & Value is: Cà Mau
key is: 7 & Value is: Nha Trang
key is: 12 & Value is: Hà Nội
Value at index 2 is: Đà Nẵng
Map key and values after removal:
Key is: 49 & Value is: Thành Phố Hồ Chí Minh
Key is: 2 & Value is: Đà Nẵng
Key is: 7 & Value is: Nha Trang
Key is: 12 & Value is: Hà Nội

Danh sách phương thức của HashMap.

1. void clear(): Loại bỏ tất cả các cặp khóa và giá trị ra khỏi HashMap.
2. Object clone(): Trả về một bản copy tất cả các cặp khóa và giá trị, thường được sử dụng để sao chép sang một HashMap khác.
3. boolean containsKey(Object key): trả về TRUE nếu trong HashMap có chứa key, trả về FALSE nếu trong HashMap không chứa key.
4. boolean containsValue(Object value): trả về TRUE nếu trong HashMap có chứa value, trả về FALSE nếu trong HashMap không chứa value.
5. Value get(Object key): Trả về giá trị được ánh xạ bởi key tương ứng.
6. boolean isEmpty(): Thực hiện kiểm tra HashMap có rỗng hay không.
7. Set keySet(): Trả về Set - danh sách tất cả các key được lấy từ HashMap.
8. Value put(Key k, Value v): Chèn thêm value vào trong HashMap với key tương ứng.
9. int size(): Trả về số lượng phần tử có trong HashMap.
10. Collection values(): Trả về danh sách tất cả các giá trị có trong HashMap.
11. Value remove(Object key): Trả về cặp khóa giá trị tương ứng với key truyền vào.
12. void putAll(Map m): Copy tất cả các giá trị của HashMap vào Map truyền vào.

[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu được ma trận chi phí hai chiều.
Hãy giúp bộ xây dựng xây dựng xây dựng hệ thống đường sắt với yêu cầu trên với chi phí xây dựng nhỏ nhất.
[Input]
Dữ liệu đầu vào được chứa trong file WELLPROJECT.INP, dòng đầu chứa số lượng test case T ( T ≤ 10). Tiếp đó là N - Số thành phố. N dòng tiếp theo là ma trận chi phí xây dựng đường sắt nối liền 2 thành phố bất kỳ.
[Output]
In ra file WELLPROJECT.OUT chi phí nhỏ nhất xây dựng hệ thống đướng sắt trên. Kết quả của mỗi test case đươc in ra trên một dòng.
[Input example]
5
3
0 1 4
1 0 2
4 2 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
6
0 45 86 12 61 51
45 0 80 99 18 2
86 80 0 9 37 14
12 99 9 0 14 90
61 18 37 14 0 52
51 2 14 90 52 0
10
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0
10
0 40613 19297 99549 27948 50416 95139 82856 99082 79380
40613 0 96888 46784 65549 8396 18128 31348 94809 16773
19297 96888 0 83011 20456 42383 34635 86957 85569 95179
99549 46784 83011 0 24003 66861 44068 11524 97968 22654
27948 65549 20456 24003 0 16590 54758 37348 62125 17814
50416 8396 42383 66861 16590 0 67234 14142 90848 64960
95139 18128 34635 44068 54758 67234 0 81632 81223 19101
82856 31348 86957 11524 37348 14142 81632 0 38508 16462
99082 94809 85569 97968 62125 90848 81223 38508 0 37607
79380 16773 95179 22654 17814 64960 19101 16462 37607 0
[Output example]
3
28
51
9
162602
Chương trình giải bài toán trên được cài đặt theo thuật toán Prim như sau:

#include<iostream>
#include<conio.h>
using namespace std;
#define NMax 101
int map[NMax][NMax];
bool isVisited[NMax];
#define LENGTHMAX 1000000
int main(){
 freopen("WELLPROJECT.INP","r", stdin);
 freopen("WELLPROJECT.OUT","w", stdout);
 int T;
 cin>>T;
 for(int tc = 0; tc < T; tc++){
  int verticeCount;
  cin>>verticeCount;
  for(int i =1; i<= verticeCount; i++){
   // khởi tạo giá trị mảng visited.
   isVisited[i] = false;
   for(int j= 1;j <= verticeCount ; j++){
    cin>>map[i][j];
   }
  }
  // Prim algorithm.
  // bắt đầu từ đỉnh 1.
  isVisited[1] = true;
  int countEdge = 0;
  int sumOfEdge = 0;
  // Vòng lặp, thăm các đỉnh để tạo cây khung nhỏ nhất.
  while(countEdge < verticeCount - 1){
   int tempLength = LENGTHMAX;
   int tempVertice = 1;
   for(int i=1 ;i <= verticeCount; i++){
    if(isVisited[i]){
     for(int j=1; j <= verticeCount ; j++){
      if(j != i && !isVisited[j] && map[i][j] > 0 && map[i][j] < tempLength){
       tempLength = map[i][j];
       tempVertice = j;
      }
     }
    }
   }
   countEdge++;
   isVisited[tempVertice]= true;
   sumOfEdge += tempLength;
  }
  cout<<sumOfEdge<<endl;
 }

}

[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ ý s của đồ thị, nối s với đỉnh y sao cho trọng số cạnh c[s, y] là nhỏ nhất. Tiếp theo, từ đỉnh s hoặc y tìm cạnh có độ dài nhỏ nhất, điều này dẫn đến đỉnh thứ ba z và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình được tiếp tục cho tới khi ta nhận được cây gồm n-1 cạnh, đó chính là cây bao trùm nhỏ nhất cần tìm.
    Trong quá trình thực hiện thuật toán, ở mỗi bước, ta có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị được sẽ được gán các nhãn. Nhãn của một đỉnh v gồm hai phần, [d[v], near[v]]. Trong đó, phần thứ nhất d[v] dùng để ghi nhận độ dài cạnh nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng. Phần thứ hai, near[v] ghi nhận đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả thông qua thủ tục sau:

void Prim(void){
 /*bước khởi tạo*/
 Chọn s là một đỉnh nào đó của đồ thị;
 VH = { s }; T = φ; d[s] = 0; near[s] = s;
 For(v∈V\VH) {
  D[v] = C[s, v]; near[v] = s;
 }
 /* Bước lặp */
 Stop = False;
 While(not stop) {
  Tìm u∈V\VH thoả mãn: d[u] = min{ d[v] với u∈V\VH };
  VH = VH∪{ u }; T = T ∪(u, near[u]);
  If(| VH | ) == n ) {
  H = <VH, T> là cây khung nhỏ nhất của đồ thị;
  Stop = TRUE;
  }Else{
   For(v ∈V\VH) {
    If(d[v] > C[u, v]) {
     D[v] = C[u, v];
     Near[v] = u;
    }
   }
  }
 }
}

Chương trình cài đặt thuật toán Prim tìm cây bao trùm nhỏ nhất được thực hiện như sau:

Tìm cây khung nhỏ nhất với thuật toán Prim

#include<iostream>
#include<conio.h>
using namespace std;
#define TRUE 1 
#define FALSE  0 
#define MAX  10000 
int a[100][100];//ma trận trọng số của đồ thị.
int n;//số đỉnh của đồ thị
int m;//số cạnh của đồ thị.
int sc;//số cạnh của cây khung nhỏ nhất.
int w;//Độ dài của cây khung nhỏ nhất.
int chuaxet[100];//mảng đánh dấu danh sách đỉnh đã thêm vào cây khung nhỏ nhất.
int cck[100][3];//danh sách cạnh của cây khung nhỏ nhất.
void nhap(void){
 int i, j, k;
 freopen("baotrum.in", "r",stdin);
 cin>>n>>m;
 cout<<"So dinh: "<<n<<endl;
 cout<<"So canh: "<<m<<endl;
 //khỏi tạo ma trận trọng số của đồ thị a[i][j] = MAX.
 for (i = 1; i <= n; i++){
  chuaxet[i] = TRUE;//Gán nhãn cho các đỉnh.
  for (j = 1; j <= n; j++)
   a[i][j] = MAX;
 }

 //nhập danh sách cạnh.
 for (int p = 1; p <= m; p++){
  cin>>i>>j>>k;
  a[i][j] = k;
  a[j][i] = k;
 }
}
void PRIM(void){
 int k, top, min, l, t, u;
 int s[100];//mảng chứa các đỉnh của cây khung nhỏ nhất.
 sc = 0; w = 0; u = 1;
 top = 1;
 s[top] = u;// thêm đỉnh u bất kỳ vào mảng s[]
 chuaxet[u] = FALSE;
 while (sc<n - 1) {
  min = MAX;
  //tìm cạnh có độ dài nhỏ nhất với các đỉnh trong mảng s[].
  for (int i = 1; i <= top; i++){
   t = s[i];
   for (int j = 1; j <= n; j++){
    if (chuaxet[j] && min>a[t][j]){
     min = a[t][j];
     k = t;
     l = j;
    }
   }
  }
  sc++;
  w = w + min;
  //thêm vào danh sách cạnh của cây khung.
  cck[sc][1] = k;
  cck[sc][2] = l;
  chuaxet[l] = FALSE; 
  top++;
  s[top] = l;
 }
}
void Result(void){
 cout<<"Do dai ngan nhat:"<< w<<endl;
 cout<<"Cac canh cua cay khung nho nhat"<<endl;
 for (int i = 1; i <= sc; i++)
  cout<< cck[i][1]<<" "<< cck[i][2]<<endl;
}
void main(void){
 nhap(); 
 PRIM();
 Result();
 getch();
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh: 6
So canh: 9
Do dai ngan nhat: 56
Cac canh cua cay khung nho nhat
1 3
3 5
5 4
4 6
3 2

Bài tập ứng dùng bạn có thể xem thêm tại đây