Bài giảng Kỹ thuật lập trình - Chương 2: Kỹ thuật xử lý dữ liệu có cấu trúc - Trần Minh Thái

KỸ THUẬT LẬP TRÌNHChương 2Kỹ thuật xử lý dữ liệu có cấu trúc(12 tiết)TRẦN MINH THÁI – minhthai@huflit.edu.vn, www.minhthai.edu.vn PHẠM ĐỨC THÀNH – phamducthanh@huflit.edu.vn, www.phamthao.com 12/3/20201Trần Minh Thái - Phạm Đức Thành2.1. Giới thiệu2.2. Kỹ thuật xử lý và tổ chức dữ liệu biểu diễn danh sách2.3. Kỹ thuật xử lý mảng2.4. Thuật toán xử lý chuỗi2.5. Phương pháp biểu diễn đồ thị và thuật toán cơ bản2.6. Tổ chức dữ liệu biểu diễn cấu trúc cây2.7. Tóm tắt chương12/3/20202Trần Minh Thái - Phạm Đức ThànhNội dungTì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)..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. 12/3/20203Trần Minh Thái - Phạm Đức Thành[2.1] Giới thiệuKhái niệm.Tổ chức dữ liệu bằng danh sách (list).Kỹ thuật xử lý danh sách. 12/3/20204Trầ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áchMột tập sắp theo thứ tự các phần tử có cùng kiểu.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.12/3/20205Trần Minh Thái - Phạm Đức ThànhKhái niệm danh sáchMộ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 đó...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.12/3/20206Trần Minh Thái - Phạm Đức ThànhKhái niệm danh sáchVí 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).12/3/20207Trần Minh Thái - Phạm Đức ThànhKhái niệm danh sáchCú pháp: Danh sáchList list = new List();Ví dụ, khai báo danh sách số nguyên List list = new List();12/3/20208Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu bằng danh sáchVí 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();12/3/20209Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu bằng danh sáchDanh sách liên kết:class Node{ int key; Node next;}LinkedList linkList = new LinkedList();12/3/202010Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu bằng danh sáchKiể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");12/3/202011Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchThêm một phần tử vào danh sách:list.Add(100);Thêm nhiều phần tử vào danh sách:list.AddRange(new int[] { 33, 44, 55 });12/3/202012Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchChèn phần tử vào cuối danh sách: list.Insert(list.Count, 9999);Truy xuất đến các phần tử trong danh sách:foreach (int x in list)Console.WriteLine(x);12/3/202013Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchĐế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);12/3/202014Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchTì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");12/3/202015Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchChèn một phần tử vào danh sách: list.Insert(3, 5);Xóa một phần tử khỏi danh sách tại vị trí xác định:list.RemoveAt(4);Sắp xếp danh sách:list.Sort();12/3/202016Trần Minh Thái - Phạm Đức ThànhKỹ thuật xử lý danh sáchBà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: Nhập danh sách các mặt hàngIn danh sách các mặt hàng được nhập vào cách đây ít nhất 10 ngàySắp xếp danh sách các mặt hàng theo thứ tự tăng dần của tên hàng12/3/2020Trần Minh Thái - Phạm Đức Thành17Bài tập ví dụstruct MatHang{ public string maHang; public string tenHang; public DateTime ngayNhap; public int soLuong; public int donGia;}12/3/2020Trần Minh Thái - Phạm Đức Thành18Khai báo cấu trúc mặt hàngBài tập ví dụ12/3/2020Trần Minh Thái - Phạm Đức Thành19 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);}Nhập thông tin của một mặt hàngBài tập ví dụ12/3/2020Trần Minh Thái - Phạm Đức Thành20Nhập danh sách mặt hàngstatic 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');}Bài tập ví dụ12/3/2020Trần Minh Thái - Phạm Đức Thành21Xuất thông tin mặt hàngstatic 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(); } }Bài tập ví dụ12/3/2020Trần Minh Thái - Phạm Đức Thành22Xuất mặt hàng được nhập ít nhất 10 ngày & sắp xếp theo tên hàngstatic 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);}Bài tập ví dụ12/3/2020Trần Minh Thái - Phạm Đức Thành23static 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);}12/3/2020Trần Minh Thái - Phạm Đức Thành24Giả sử ngày chạy chương trình là 23/02/2016Bài tập về nhàBổ sung vào chương trình của bài tập ví dụ một số chức năng sau:Nhập vào mã số mặt hàng x, tìm và in ra thông tin mặt hàng và tổng tiền có mã số x (nếu có)Chèn thêm thông tin một mặt hàng p sao cho danh sách mặt hàng vẫn có thứ tự tăng dần theo tên hàngCập nhật giá mới cho mặt hàng có mã số x sao cho tăng thêm 15% so với giá cũXóa mặt hàng có ngày nhập vào là d (nếu có) Sắp xếp danh sách mặt hàng giảm dần theo số lượng12/3/2020Trần Minh Thái - Phạm Đức Thành25Mảng một chiều.Array và ArrayList.Mảng hai chiều (ma trận – matrix).Mảng hai chiều vuông.Jagged Array.12/3/202026Trần Minh Thái - Phạm Đức Thành[2.3] Kỹ thuật xử lý mảngChứa các biến có cùng kiểu dữ liệu.Truy xuất phần tử thông qua chỉ số (index).Chỉ số bắt đầu bằng 0.12/3/202027Chỉ số01234Phần tửA[0]A[1]A[2]A[3]A[4]Trần Minh Thái - Phạm Đức ThànhMảng một chiềuKhai báo:12/3/202028Datatype[ ] array-name;Ví dụ 1:int [ ] myArr = new int [5]; string [ ] myStr = new string[5]; string [] myStr2 = {“abc”, “def”}; Trần Minh Thái - Phạm Đức ThànhMảng một chiềustatic void Main(string[] args){ int[] Arr = new int[] { 2, 3, 4, 1, 6, 5 }; for (int i = 0; i X) Console.Write("{0,4}", ai);}12/3/202033Trần Minh Thái - Phạm Đức ThànhMảng một chiềuTính tổng/tích:int TongXXX(int []A){ int s = 0; for (int i = 0; iA[i+1]) //vi phạm điều kiện tăng dần { flag = false; break; } return flag;}12/3/202037Trần Minh Thái - Phạm Đức ThànhMảng một chiềuĐếm:int DemXXX(int []A){ int d = 0; for (int i = 0; i a[vtmax]) vtmax = i; return vtmax;}12/3/202042Trần Minh Thái - Phạm Đức ThànhMảng một chiềuKĩ thuật đặt lính canh:Ví dụ: Viết hàm tìm phần tử x có xuất hiện trong mảng một chiều các số nguyên hay không? Nếu có trả về vị trí đầu tiên của x trong mảng, ngược lại trả về -1.12/3/202043Trần Minh Thái - Phạm Đức ThànhMảng một chiềustatic int Tim_x(int []a, int x){ int i = 0; while (i = 0) return false; return true;}12/3/202051Trần Minh Thái - Phạm Đức ThànhMảng một chiềuTính giá trị trung bình có điều kiệnfloat TrungBinhXXX(int []a){ float s = 0; int d = 0; for (int i = 0; i a[j]) Hoanvi(ref a[i],ref a[j]);}12/3/202055Trần Minh Thái - Phạm Đức ThànhMảng một chiềuXóa: phần tử đầu tiên của mảngstatic void xoaDau(ref int []a){ int[] tam = new int[a.Length - 1]; for (int i = 0; i 0) Console.Write("{0,4}", A[i, j]);}12/3/202074Trần Minh Thái - Phạm Đức ThànhMảng hai chiềuTính tổng các phần tử có giá trị lẻ trong mảng :static int tongLe(int[,] A){ int S = 0; for (int i = 0; i 10)//Gặp ptử thỏa đk { flag = true; break; } return flag;}12/3/202077Trần Minh Thái - Phạm Đức ThànhMảng hai chiềuĐếm: các phần tử có giá trị là số âm.static int demAm(int[,] A){ int dem = 0; for (int i = 0; i a[vtd,vtc]) { vtd = i; vtc = j; } return a[vtd,vtc];}12/3/202079Trần Minh Thái - Phạm Đức ThànhMảng hai chiềuKiểm tra xem mảng có tồn tại số lẻ không.static bool kiemTraTonTaiLe(int [,]A){ for (int i = 0; i a[j]) Hoanvi(ref a[i],ref a[j]);}12/3/202083Trần Minh Thái - Phạm Đức ThànhMảng hai chiềustatic void Copy(int [,]a,out int []b){ b = new int[a.GetLength(0) * a.GetLength(1)]; int i = 0; foreach (int ai in a) b.SetValue(ai,i++);}12/3/202084Trần Minh Thái - Phạm Đức ThànhMảng hai chiềustatic void Copy(int[] a,ref int[,] b){ int k = 0; for (int i = 0; i list = new List();Trần Minh Thái - Phạm Đức ThànhBiểu diễn đồ thị trên máy tính12/3/2020123Tìm kiếm theo chiều rộng: Thuật toán [BFS]:Cho G=(V, E) và 1 đỉnh xuất phát s. Bước 1: Viếng thăm đỉnh s.Bước 2: Tìm các đỉnh (gọi là S1) chưa được viếng thăm và kề với s, rồi viếng thăm các đỉnh trong S1.Bước 3: Tìm các đỉnh (gọi là S2) chưa được viếng thăm và kề với S1, rồi viếng thăm các đỉnh trong S2.Bước 4: Quá trình này thực hiện cho đến khi không thể tìm được các đỉnh kế tiếp.Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020124Tìm kiếm theo chiều rộng: Thuật toán [BFS]:3041256Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020125Tìm kiếm theo chiều rộng: Thuật toán [BFS]:3041256Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020126Tìm kiếm theo chiều rộng: Thuật toán [BFS]:3041256Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020127Tìm kiếm theo chiều rộng: Thuật toán [BFS]:3041256Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020128Tìm kiếm theo chiều rộng: Thuật toán [BFS]:3041256Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020129Tìm kiếm theo chiều rộng: Thuật toán [BFS]:Nhận xét: Những đỉnh gần với s nhất sẽ được viếng thăm trước Các đỉnh chỉ được viếng thăm duy nhất 1 lần Cài đặt thuật toán: Ta dùng hàng đợi:Queue q = new Queue();Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020130Thuật toán cài đặt bằng hàng đợi như sau:Bước 1: Khởi tạo Đánh dấu mọi đỉnh chưa được viếng thăm Thăm đỉnh s (Đánh dấu đỉnh s đã viếng thăm)Khởi tạo hàng đợi q chỉ chứa sBước 2: Lặp cho đến khi hàng đợi q rỗng Lấy đỉnh u ra khỏi hàng đợi qTìm tất cả đỉnh v chưa viếng thăm và kề với đỉnh uTham đỉnh v (Đánh dấu đỉnh v đã viếng thăm)Đẩy đỉnh v vào hàng đợiTrần Minh Thái - Phạm Đức ThànhTìm kiếm theo chiều rộng12/3/2020131Tìm kiếm theo chiều sâu: Thuật toán DFS:Cho G=(V, E) và 1 đỉnh xuất phát s. Bước 1: Viếng thăm đỉnh s Bước 2: Tìm đỉnh u chưa được viếng thăm và kề với s Nếu có đỉnh u thì đặt s=u và quay về Bước 1Nếu không có đỉnh u thì quay về đỉnh k là đỉnh trước của đỉnh s, đặt s=k và quay về bước 2Quá trình này được thực hiện cho đến khi không thể quay về đỉnh trước đóTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020132Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020133Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020134Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020135Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020136Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020137Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020138Tìm kiếm theo chiều sâu: Thuật toán DFS:BADECFTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020139Cài đặt thuật toán: Stack s = new Stack();Thuật toán cài đặt bằng stack như sau:Bước 1. Đánh dấu s đã viếng thăm.Bước 2. Đưa s vào stack.Bước 3. Trong khi stack chưa rỗng.B3.1 Lấy 1 đỉnh u từ stack.B3.2 Tìm 1 đỉnh v chưa được viếng thăm và kề u.B3.2.1 Đánh dấu v đã viếng thăm.B3.2.2 Đẩy u vào lại stack.B3.2.3 Đẩy v vào stack.B3.2.4 Quay lại bước 3Trần Minh Thái - Phạm Đức ThànhTìm kiếm theo chiều sâu12/3/2020140Thuật toán Dijkstra: Tìm đường đi từ s đến t.Ý tưởng: xây dựng dần các đỉnh đi từ s và gần s nhất.Thuật toán Dijkstra không thể thực hiện khi đồ thị có cạnh âm (đồ thị vô hướng) hay đồ thị có chu trình âm (đồ thị có hướng)Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020141Thuật toán Dijkstra:Bước 1 [Khởi tạo]: d(v) = +∞,  vV. d(s)=0 và tập S=V.Bước 2: [Lặp][Chọn Min] Chọn đỉnh u  S sao cho d(u) có giá trị min.[Cập Nhật] Với mọi đỉnh v kề u. d(v) = min{d(v), d(u) + w(u,v)}S = S - {u} Lặp cho đến khi t  STrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020142Thuật toán Ford – Bellman: chu trình âm hay trả về cây đường đi.Bước 1 [Khởi tạo]: d0(v) = +∞,  vV. d0(s)=0, k=0Bước 2: [Lặp]k = k+1[Cập Nhật] Với mọi đỉnh u kề v dk(s) = 0. dk(v) = min{dk-1(u) + w(u,v)}[Kiểm tra] Nếu dk(v) = dk-1(v), v, thì dừng.Lặp cho đến khi k=nBước 3: Nếu k=n thì đồ thị có chu trình âm Trần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020143Tìm đường đi ngắn nhất: Thuật toán Floyd.Hoặc chỉ ra đồ thị có chu trình âm.Input: G=(V, E)Output: Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i, j]: độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh jMa trận ghi nhận đường đi p[i, j]: ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất từ đỉnh i đến đỉnh jTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020144Tìm đường đi ngắn nhất: Thuật toán Floyd.Bước 1: [Khởi tạo]d[i, j]=a[i, j]p[i, j] = j;Bước 2: [Lặp]Cho k, i, j chạy từ 0 đến n-1 Nếu (d[i, j] > d[i, k] + d[k, j]) thì d[i, j] = d[i, k] + d[k, j] p[i, j] = kTrần Minh Thái - Phạm Đức ThànhCác thuật toán cơ bản12/3/2020145Khái niệm cơ bản.Cây là một cấu trúc dữ liệu gồm tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp “cha - con”. Có một nút đặc biệt gọi là gốc (root).Cây rỗng (null tree) là cây không có nút nào cả.Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu biểu diễn cấu trúc cây12/3/2020146ABCDKJIHGFEMức 0Mức 1Mức 2Mức 3Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu biểu diễn cấu trúc cây12/3/2020147Nút A là gốc, là cha của B, C, D.Nút G, H, I là con của nút D.Số các nút con là bậc của nút đó. Ví dụ: nút D bậc 3, H bậc 2.Nút có bậc bằng 0 là nút là (leaf). Ví dụ: nút C, E, F.Nút không phải là gốc hoặc lá gọi là nhánh.Bậc cao nhất của tất cả các nút gọi là bậc của cây. Cây ở hình trên là cây bậc 3.Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu biểu diễn cấu trúc cây12/3/2020148Ví dụ ứng dụng thực tế:Mục lục của một cuốn sách.Cấu trúc thư mục trên đĩa trong cửa sồ File Explorer/Windows Explorer.Gia phả của một họ tộc.Một biểu thức toán học.Trần Minh Thái - Phạm Đức ThànhTổ chức dữ liệu biểu diễn cấu trúc cây12/3/2020149Biểu diễn bằng danh sách kề:3019468752ĐỉnhĐỉnh kề0194136234752567898Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020150Biểu diễn bằng danh sách kề: Cài đặt trên máy: int sodinh = 10; int[][] Vertices = new int[sodinh][]; Vertices[0] = new int[] { 1,9, 4 }; Vertices[1] = new int[] { 3,6 }; Vertices[2] = null; Vertices[3] = null; Vertices[4] = new int[] { 7,5,2 }; Vertices[5] = null; Vertices[6] = null; Vertices[7] = null; Vertices[8] = null; Vertices[9] = new int[] { 8 };Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020151Biểu diễn bằng danh sách liên kết:19adj[0]36adj[1]nulladj[2]nulladj[3]null725adj[4]null4nullTrần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020152Biểu diễn bằng danh sách liên kết: Cài đặt trên máy: int[] dinhS0 = { 1, 9, 4 }; LinkedList listAdj0 = new LinkedList(dinhS0); int[] dinhS1 = { 3,6 }; LinkedList listAdj1 = new LinkedList(dinhS1); int[] dinhS2 = null; LinkedList listAdj2 = new LinkedList(dinhS2); int[] dinhS3 = null; LinkedList listAdj3 = new LinkedList(dinhS3);Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020153 int[] dinhS4 = { 7,5,2 }; LinkedList listAdj4 = new LinkedList(dinhS4); int[] dinhS5 = { 1, 9, 4 }; LinkedList listAdj5 = new LinkedList(dinhS5); int[] dinhS6 = null; LinkedList listAdj6 = new LinkedList(dinhS6); int[] dinhS7 = null; LinkedList listAdj7 = new LinkedList(dinhS7); int[] dinhS8 = null; LinkedList listAdj8 = new LinkedList(dinhS8); int[] dinhS9 = { 8 };Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020154LinkedList listAdj9 = new LinkedList(dinhS9);List> Graphs = new List>(); Graphs.Add(listAdj0); Graphs.Add(listAdj1); Graphs.Add(listAdj2); Graphs.Add(listAdj3); Graphs.Add(listAdj4); Graphs.Add(listAdj5); Graphs.Add(listAdj6); Graphs.Add(listAdj7); Graphs.Add(listAdj8); Graphs.Add(listAdj9);Trần Minh Thái - Phạm Đức Thành12/3/2020155Biểu diễn bằng mảng các đỉnh kề:0123456789a194367528previous0149index0355588888Trong đó:Đỉnh kề với 0: 0-2 Đỉnh kề với 1: 3-4 Đỉnh kề với 4: 5-7 Đỉnh kề với 9: 8-8 Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020156Mảng các đỉnh kề: công thức tính đỉnh kề với i:Cài đặt trên máy: int n = 10; int[] a = new int[n]; int[] index = new int[n];Đỉnh kề với i: a[index[i]]  a[index[i+1]-1]Trần Minh Thái - Phạm Đức ThànhBiểu diễn cây trên máy tính12/3/2020157Kiểu dữ liệu + các thao tác xử lý được định nghĩa trên nó.Danh sách là một tập thứ tự các phần tử có cùng kiểu. Danh sách là cấu trúc dữ liệu tuyến tính, các phần tử dữ liệu được sắp thứ tự xác định.Dữ liệu kiểu mảng dùng cho việc biểu diễn những thông tin có cùng kiểu dữ liệu liên tiếp nhau.Khi cài đặt bài tập mảng một chiều nên xây dựng thành những hàm chuẩn để dùng lại cho các bài tập khác.Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020158Các thao tác mảng theo quy tắc nhất định, ứng dụng mảng trong việc biểu diễn số lớn, dùng bảng tra, khử đệ qui, Giống mảng một chiều, thao tác truy xuất trên mảng hai chiều, trên chuỗi hoàn toàn tương tự. Bên cạnh đó, kiểu chuỗi còn được cài đặt sẵn một số hàm thư viện rất hữu ích, khi cài đặt, cố gắng tận dụng tối đa hàm thư viện này. C# hỗ trợ cho người lập trình rất nhiều trong namespace System.Collections và System.Collections.Generic.Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020159Biểu diễn đồ thị: dùng ma trận kề, ma trận trọng số và danh sách mà giáo trình trình bày ở chương này. Với các thuật toán tìm đường đi...Biểu diễn cây: dùng mảng, danh sách kề và danh sách liên kết.Đồ thị và cây trong tài liệu chỉ giới thiệu tổ chức dữ liệu là chính. Tìm hiểu sâu hơn, các bạn tìm hiểu ở 2 giáo trình khác là: Lý thuyết đồ thị, Cấu trúc Dữ liệu và Thuật toán.Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020160Viết hàm tìm vị trí phần tử có giá trị x xuất hiện cuối cùng trong mảng.Viết hàm tìm vị trí của phần tử lớn nhất trong mảng các số thực.Viết hàm in vị trí các phần tử nguyên tố trong mảng các số nguyên.Viết hàm tìm vị trí phần tử âm đầu tiên trong m