Bài giảng Kỹ thuật lập trình Chương 2: Trần Minh Thái, Phạm Đức Thành

Ỹ

Ậ

K THU T L P TRÌNH Chương 2 Kỹ thuật xử lý dữ liệu có cấu trúc (12 tiết)

minhthai@huflit.edu.vn, www.minhthai.edu.vn

Ầ Ạ

phamducthanh@huflit.edu.vn,

TR N MINH THÁI – Ứ PH M Đ C THÀNH – www.phamthao.com

1 9/17/16 Trần Minh Thái - Phạm Đức Thành

Nội dung

v 2.1. Giới thiệu v 2.2. Kỹ thuật xử lý và tổ chức dữ liệu biểu

diễn danh sách

v 2.3. Kỹ thuật xử lý mảng v 2.4. Thuật toán xử lý chuỗi v 2.5. Phương pháp biểu diễn đồ thị và

thuật toán cơ bản

v 2.6. Tổ chức dữ liệu biểu diễn cấu trúc

cây

v 2.7. Tóm tắt chương

2 9/17/16 Trần Minh Thái - Phạm Đức Thành

[2.1] Giới thiệu

v Tìm hiểu về các kỹ thuật xử lý trên kiểu dữ diệu người dùng tự định nghĩa như: danh sách (list), mảng (array), chuỗi (string), cây (tree)..

v C# hỗ trợ rất tốt về dữ liệu có cấu trúc và các

thao tác trên đó thông qua: Ø Namespace System.Collections. Ø Namespace System.Collections.Generic.

3 9/17/16 Trần Minh Thái - Phạm Đức Thành

[2.2] Kỹ thuật xử lý và tổ chức dữ liệu biểu diễn danh sách

v Khái niệm. v Tổ chức dữ liệu bằng danh sách (list). v Kỹ thuật xử lý danh sách.

4 9/17/16 Trần Minh Thái - Phạm Đức Thành

Khái niệm danh sách

v Một tập sắp theo thứ tự các phần tử có cùng

kiểu.

v Cấu trúc dữ liệu tuyến tính, trong đó các phần tử dữ liệu được sắp theo một thứ tự xác định.

5 9/17/16 Trần Minh Thái - Phạm Đức Thành

Khái niệm danh sách

v Một số thao tác:

Ø Kiểm tra danh sách có rỗng không. Ø Đếm số phần tử theo tiêu chí xác định

trước.

Ø Tìm một phần tử trong danh sách. Ø Chèn một phần tử vào danh sách. Ø Xóa một phần tử khỏi danh sách. Ø Sắp xếp theo tiêu chí nào đó...

v Các phép toán trên danh sách không phụ thuộc vào kiểu dữ liệu của phần tử trong danh sách.

6 9/17/16 Trần Minh Thái - Phạm Đức Thành

Khái niệm danh sách

v Ví dụ:

Ø Danh sách sinh viên. Ø Danh sách diện thoại (danh bạ điện thoại). Ø Danh sách môn học. Ø Danh sách nhân viên. Ø Danh sách hàng hóa (danh mục hàng hóa).

7 9/17/16 Trần Minh Thái - Phạm Đức Thành

Tổ chức dữ liệu bằng danh sách

v Cú pháp: Danh sách

List list = new List();

v Ví dụ, khai báo danh sách số nguyên

List list = new List();

8 9/17/16 Trần Minh Thái - Phạm Đức Thành

Tổ chức dữ liệu bằng danh sách

v Ví dụ, khai báo danh sách có tên list là danh

sách chứa các sinh viên.

struct sinhVien

{

public string maSV, hoTen;

public DateTime ngaySinh;

public string diaChi, maLop;

}

List list = new List();

9 9/17/16 Trần Minh Thái - Phạm Đức Thành

Tổ chức dữ liệu bằng danh sách

linkList

=

new

v Danh sách liên kết: class Node { int key; Node next; } LinkedList LinkedList();

10 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Kiểm tra danh sách rỗng: if (list.Count == 0)

Console.WriteLine("Danh sách rỗng");

else

Console.WriteLine("Danh sách không rỗng");

11 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Thêm một phần tử vào danh sách:

list.Add(100);

v Thêm nhiều phần tử vào danh sách:

list.AddRange(new int[] { 33, 44, 55 });

12 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Chèn phần tử vào cuối danh sách: list.Insert(list.Count, 9999); v Truy xuất đến các phần tử trong danh sách: foreach (int x in list)

Console.WriteLine(x);

13 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Đếm số phần tử bằng giá trị X cho trước: int X = 5, dem = 0; foreach (int ai in list) if (ai == X) dem++; Console.WriteLine("Co {0} phan tu bang {1}", dem, X);

14 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Tìm một phần tử có giá trị X cho trước: int index=list.IndexOf(X); if (index == -1) Console.WriteLine("Tim khong thay"); else Console.WriteLine("Tim thay");

15 9/17/16 Trần Minh Thái - Phạm Đức Thành

Kỹ thuật xử lý danh sách

v Chèn một phần tử vào danh sách:

list.Insert(3, 5); v Xóa một phần tử khỏi danh sách tại vị trí xác

định:

list.RemoveAt(4);

v Sắp xếp danh sách:

list.Sort();

16 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Cho danh sách các mặt hàng, mỗi mặt hàng gồm các thông tin: mã hàng, tên hàng, số lượng, đơn giá, ngày nhập hàng. Hãy viết các hàm: v Nhập danh sách các mặt hàng v In danh sách các mặt hàng được nhập vào

cách đây ít nhất 10 ngày

v Sắp xếp danh sách các mặt hàng theo thứ tự

tăng dần của tên hàng

17 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Khai báo cấu trúc mặt hàng

struct MatHang {

public string maHang; public string tenHang; public DateTime ngayNhap;

public int soLuong;

public int donGia; }

18 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Nhập thông tin của một mặt hàng

static void NhapMatHang(out MatHang x) {

Console.Write("- Nhap ma hang: "); x.maHang = Console.ReadLine(); Console.Write("- Nhap ten hang: "); x.tenHang = Console.ReadLine(); Console.Write("- Nhap so luong: "); x.soLuong = int.Parse(Console.ReadLine()); Console.Write("- Nhap don gia: "); x.donGia = int.Parse(Console.ReadLine()); Console.Write("- Nhap vao ngay nhap hang (dd/mm/yyyy):

");

string ngay = Console.ReadLine(); x.ngayNhap = DateTime.Parse(ngay);

19 } 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Nhập danh sách mặt hàng

static void NhapDanhSach(List dshang) {

MatHang x; char nhap; do {

NhapMatHang(out x); dshang.Add(x); Console.Write("Nhap tiep mat hang (Y/N)?: "); nhap = char.Parse(Console.ReadLine());

} while (nhap == 'Y' || nhap == 'y');

}

20 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Xuất thông tin mặt hàng

static void XuatMatHang(MatHang mh) {

Console.Write("{0, 8}|{1, 15}|{2, 8}|{3, 8}|{4, 8}", mh.maHang, mh.tenHang, mh.soLuong, mh.donGia,

mh.ngayNhap.ToShortDateString()); } static void XuatDanhSach(List dsmh) {

Console.WriteLine("{0, 8}|{1, 15}|{2, 8}|{3, 8}|{4, 8}",

"Ma hang", "Ten hang", "So luong", "Don gia", "Ngay nhap");

foreach (MatHang x in dsmh)

{

XuatMatHang(x); Console.WriteLine();

}

21 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

Xuất mặt hàng được nhập ít nhất 10 ngày & sắp xếp theo tên hàng

static void XuatMHNhapTu10Ngay(List dsmh) {

Console.WriteLine("{0, 8}|{1, 15}|{2, 8}|{3, 8}|{4, 8}",

"Ma hang", "Ten hang", "So luong", "Don gia", "Ngay nhap"); foreach (MatHang mh in dsmh)

{

if ((DateTime.Now - mh.ngayNhap).Days >= 10)

{

XuatMatHang(mh);

Console.WriteLine();

}

} static int SoSanhMhTheoTen(MatHang x, MatHang y) {

return x.tenHang.CompareTo(y.tenHang);

22 } 9/17/16 Trần Minh Thái - Phạm Đức Thành

Bài tập ví dụ

static void Main(string[] args) {

List dsmh = new List(); NhapDanhSach(dsmh); Console.WriteLine("Danh sach mat hang:"); XuatDanhSach(dsmh); Console.WriteLine("\nDanh sach mat hang duoc nhap vao

it nhat 10 ngay:");

ắ ế ầ

XuatMHNhapTu10Ngay(dsmh); //S p x p danh sách mặt hàng tăng d n theo tên hàng dsmh.Sort(SoSanhMhTheoTen); Console.WriteLine("\nDanh sach mat hang duoc sap tang

theo ten hang:");

XuatDanhSach(dsmh);

}

23 9/17/16 Trần Minh Thái - Phạm Đức Thành

ả ử Gi s ngày ươ ạ ch y ch ng trình là 23/02/2016

24 9/17/16 Trần Minh Thái - Phạm Đức Thành