Bài giảng Cấu trúc dữ liệu - Nguyễn Thị Thúy Loan

BÀI GIẢNG CẤU TRÚC DỮ LIỆU ThS. Nguyễn Thị Thúy Loan 6/8/2010 Nguyễn Thị Thúy Loan 2 Cách đánh giá  Thực hành: 30%  Bài tập: 20%  Lý thuyết: 50% 6/8/2010 Nguyễn Thị Thúy Loan 3 Tài liệu tham khảo 1. Bài giảng: ThS. Nguyễn Hà Giang 2. Cấu trúc dữ liệu & giải thuật, Dương Anh Đức, Trần Hạnh Nhi, NXB ĐHQG Tp.HCM, 2008. 3. Cấu trúc dữ liệu, Nguyễn Trung Trực, ĐHBK, 1992. 4. Giải thuật & lập trình, Lê Minh Hoàng, ĐHSPHN, 1999-2002. 5. Cấu trúc dữ liệu + giải thuật = chương trình, Nguyễn Quốc Cường – Hoàng Đức Hải, NXB Giáo dục. 6. Fundamentals of Data Structures, Ellis Horowitz, Sartaj Sahni. 6/8/2010 Nguyễn Thị Thúy Loan 4 NỘI DUNG CHƯƠNG TRÌNH  Độ phức tạp thuật toán.  Tìm kiếm và sắp xếp.  Danh sách liên kết.  Stack & Queue.  Cây. ĐỘ PHỨC TẠP THUẬT TOÁN ThS. Nguyễn Thị Thúy Loan Chương I 6/8/2010 Nguyễn Thị Thúy Loan 6 NỘI DUNG I. ĐO THỜI GIAN II. DỰA VÀO ĐỘ LỚN CỦA DỮ LIỆU III. MỘT SỐ CÔNG THỨC THƯỜNG DÙNG IV. CÁCH TÍNH ĐỘ PHỨC TẠP 6/8/2010 Nguyễn Thị Thúy Loan 7 Đo thời gian 6/8/2010 Nguyễn Thị Thúy Loan 8 Dựa vào độ lớn của dữ liệu Gọi t(n) là thời gian thực hiện của thuật toán A (thông thường là chu kỳ của CPU), t(n) sẽ là một trong các loại: a. O(1): độ phức tạp là một hằng số. VD: for (int i=1; i<= 10 ; i++) printf (“%d”, i ); Phép so sánh: i = 1..10 và i =11 (để dừng) = 11. Phép gán: i = 1 + (i = 1..10) = 11. 6/8/2010 Nguyễn Thị Thúy Loan 9 Dựa vào độ lớn của dữ liệu b. O(log2n): Tìm nhị phân. c. O(√n): Kiểm tra một số có phải là số nguyên tố? VD: Kiểm tra số nguyên tố, xét i=2 → (n/2), nếu i là ước số của n  n không phải là số nguyên tố, ngược lại n là nguyên tố. 6/8/2010 Nguyễn Thị Thúy Loan 10 Dựa vào độ lớn của dữ liệu Nhận xét  Trừ số 2, tất cả các số chẵn không phải là số nguyên tố.  Các số lẻ không có ước số chẵn.  i là ước số của n → (n/i) là ước số của n. 6/8/2010 Nguyễn Thị Thúy Loan 11 d. O(n): Độ phức tạp tuyến tính (áp dụng duyệt mảng, dãy). e. O(nlog2n): “thuật toán Logarit” (áp dụng sắp xếp mảng). f. O(nα) (α>1): đa thức. g. O(2n), O(n!): mũ (áp dụng liệt kê tất cả các tập con của tập gồm n phần tử). Dựa vào độ lớn của dữ liệu 6/8/2010 Nguyễn Thị Thúy Loan 12 Một số công thức thường dùng    n i nnib 1 2 )1(.    n i na 1 1.         b ai b i a i Nbaab 1 1 1 )(1111    n ai aanni 2 )11)(1()1(    2 1 22 2 )1(n i nni 6/8/2010 Nguyễn Thị Thúy Loan 13    n i nnnic 1 2 6 )12)(1(.    n ai aaannni 6 )12)(1()12)(1(2        n i n i nniid 1 222 1 3 4 )1(. Một số công thức thường dùng 6/8/2010 Nguyễn Thị Thúy Loan 14 Cách tính độ phức tạp Ví dụ 1: Cho thuật toán tính tổng như sau: long Tong (int n) { long s = 0; for (int i = 1 ; i <= n ; i ++) s += i; return s; } a. Tính độ phức tạp của thuật toán. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. 6/8/2010 Nguyễn Thị Thúy Loan 15 Cách tính độ phức tạp GIẢI a) Số phép so sánh: Số phép gán:  Độ phức tạp là O(n).    n i n 1 111    n i n 1 22)11(11 6/8/2010 Nguyễn Thị Thúy Loan 16 Cách tính độ phức tạp b) Thực chất là tính:  Cải tiến: long Tong (int n) { return (n * (n + 1))/2; }  Không phép so sánh, không phép gán  O(1).    n i nnis 1 2 )1( 6/8/2010 Nguyễn Thị Thúy Loan 17 Cách tính độ phức tạp Vd2: Cho thuật toán sau: long Tong (int n) { long s = 0; for (int i = 1 ; i <= n ; i ++) for (int j = i ; j<= n ; j ++) s += j; return s; } a. Tính độ phức tạp của thuật toán. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. 6/8/2010 Nguyễn Thị Thúy Loan 18 Cách tính độ phức tạp Vd3: Cho thuật toán sau: long Tong (int n) { long s = 0; for (int i = 1 ; i <= n ; i ++) for (int j = 1 ; j<= i*i ; j ++) s += j; return s; } a. Tính độ phức tạp của thuật toán. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. TÌM KIẾM VÀ SẮP XẾP ThS. Nguyễn Thị Thúy Loan Chương II Tham khảo bài giảng ThS. Nguyễn Hà Giang 6/8/2010 Nguyễn Thị Thúy Loan 20 Nội dung trình bày  TÌM KIẾM  SẮP XẾP 6/8/2010 Nguyễn Thị Thúy Loan 21  Tìm kiếm là thao tác quan trọng & thường được sử dụng trong tin học. o Tìm kiếm một nhân viên trong danh sách nhân viên. o Tìm một sinh viên trong danh sách sinh viên của một lớp… o Tìm kiếm một tên sách trong thư viện. Tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 22  Tìm kiếm là quá trình xác định một đối tượng nào đó trong một tập các đối tượng. Kết quả trả về là đối tượng tìm được (nếu có) hoặc một chỉ số (nếu có) xác định vị trí của đối tượng trong tập đó.  Việc tìm kiếm dựa theo một trường nào đó của đối tượng, trường này là khóa (key) của việc tìm kiếm. Tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 23  VD: Muốn tìm sinh viên tên Nguyễn Văn A có trong lớp hay không?  Ta có hai cách tìm kiếm như sau: Tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 24 Tìm kiếm Tìm kiếm tuyến tính Tìm kiếm nhị phân Tập dữ liệu đã được sắp xếp Tập dữ liệu bất kỳ Tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 25 Bài toán được mô tả như sau:  Tập dữ liệu được lưu trữ là dãy a0, a2,.., an-1. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính, có khai báo: int a[MAX];  Khóa cần tìm là x, có kiểu nguyên: int x; Tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 26  Ý tưởng chính: duyệt tuần tự từ phần tử đầu tiên, lần lượt so sánh khóa tìm kiếm với khoá tương ứng của các phần tử trong danh sách. Cho đến khi gặp phần tử cần tìm hoặc đến khi duyệt hết danh sách. Tìm kiếm tuyến tính 6/8/2010 Nguyễn Thị Thúy Loan 27  Bước 1: i = 0;  Bước 2: So sánh a[i] với x, có hai t.hợp: o a[i] = x: Tìm thấy  Trả về vị trí i o a[i]  x: Sang bước 3  Bước 3: i = i + 1// xét phần tử kế tiếp o Nếu i≥N:Hết mảng không thấyTrả về -1 o Nếu i  N: Quay lại bước 2 Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 28 12 2 5 8 1 6 4 x = 8 Tìm được Ví dụ: Cho dãy số a, giá trị tìm x = 8: 12 2 5 8 1 6 4 Tìm kiếm tuyến tính 6/8/2010 Nguyễn Thị Thúy Loan 29 1. Cài đặt bình thường. 2. Cải tiến lại bằng cách sử dụng phần tử cầm canh. Tìm kiếm tuyến tính 6/8/2010 Nguyễn Thị Thúy Loan 30 Nhận xét:  Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ. Tìm kiếm tuyến tính 6/8/2010 Nguyễn Thị Thúy Loan 31  Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng nhiều đến tốc độ thực hiện. Ví dụ như thuật toán cải tiến sẽ chạy nhanh hơn thuật toán trước do vòng lặp while chỉ so sánh một điều kiện... Tìm kiếm tuyến tính 6/8/2010 Nguyễn Thị Thúy Loan 32 Khái niệm:  Phép tìm kiếm nhị phân được áp dụng trên dãy khóa đã có thứ tự: k[0]  k[0]... k[n-1].  Phương pháp này dựa trên ý tưởng sau: Giả sử ta cần tìm trong đoạn a[left..right] với khoá tìm kiếm là x, trước hết ta xét phần tử giữa a[mid], với mid = (left + right)/2. Tìm kiếm nhị phân 6/8/2010 Nguyễn Thị Thúy Loan 33  Nếu a[mid] < x thì có nghĩa là đoạn a[left] đến a[mid] chỉ chứa khóa < x, ta tiến hành tìm kiếm từ a[mid+1] đến a[right].  Nếu a[mid] > x thì có nghĩa là đoạn a[mid] đến a[right] chỉ chứa khoá > x, ta tiến hành tìm kiếm từ a[left] đến a[mid-1].  Nếu a[mid]=x thì việc tìm kiếm thành công.  Quá trình tìm kiếm thất bại nếu left > right. Tìm kiếm nhị phân 6/8/2010 Nguyễn Thị Thúy Loan 34  B1: left =0, right = n-1  B2: mid = (left + right)/2// lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng o a[mid] = x: Tìm thấy  Trả về vị trí mid o a[mid] >x: right = mid -1; o a[mid] < x: left = mid +1  B3: o Nếu left  right // còn phần tử Lặp B2 o Ngược lại: Trả về -1// đã xét hết các phần tử Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 35 Ví dụ: cho dãy số gồm 8 phần tử bên dưới và x = 8: 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 Left = 0 X = 8 Right = 7Mid = 3 1 2 4 5 6 8 12 15 Left = 4 X = 8 Right = 7Mid = 5 Đoạn tìm kiếm Đoạn tìm kiếm = Tìm kiếm nhị phân 6/8/2010 Nguyễn Thị Thúy Loan 36 Nhận xét:  Thuật giải nhị phân dựa vào quan hệ giá trị của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được với dãy đã có thứ tự.  Thuật giải nhị phân tìm kiếm nhanh hơn tìm kiếm tuyến tính. Tìm kiếm nhị phân 6/8/2010 Nguyễn Thị Thúy Loan 37  Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi mảng được sắp thứ tự rồi thì mới tìm kiếm nhị phân. Tìm kiếm nhị phân 6/8/2010 Nguyễn Thị Thúy Loan 38 Sắp xếp  Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng theo một thứ tự nhất định.  Ví dụ: {1, 2, 5, 7, 9, 12}, {14, 12, 7, 5, 2, 1} {“An” “Binh” “Dương” “Hương”} 6/8/2010 Nguyễn Thị Thúy Loan 39  Việc sắp xếp là một bài toán phổ biến trong tin học. Do các yêu cầu tìm kiếm thuận lợi, sắp xếp kết xuất cho các bảng biểu... Sắp xếp 6/8/2010 Nguyễn Thị Thúy Loan 40  Dữ liệu thường được tổ chức thành mảng các mẫu tin.  Mỗi mẫu tin thường có một số các trường dữ liệu khác nhau.  Trường tham gia quá trình tìm kiếm gọi là khóa (key).  Việc sắp xếp sẽ được tiến hành dựa vào giá trị khoá này. Sắp xếp 6/8/2010 Nguyễn Thị Thúy Loan 41 1. Đổi chỗ trực tiếp (interchange Sort) 2. Chèn trực tiếp (insertion Sort) 3. Chọn trực tiếp (Selection Sort) 4. Nổi bọt (Bubble Sort ) 5. Shell sort 6. Quick sort Các phương pháp sắp xếp 6/8/2010 Nguyễn Thị Thúy Loan 42  Để tiện cho việc minh họa các thuật toán sắp xếp ta mô tả bài toán như sau: Cho một mảng a gồm các phần tử, mỗi phần tử trong mảng có một thuộc tính khóa. Hãy sắp xếp tăng hoặc giảm các phần tử trong mảng theo giá trị khóa này. Mô tả bài toán 6/8/2010 Nguyễn Thị Thúy Loan 43  Do mỗi phần tử có giá trị khóa nên ta gọi k[0..n-1] là mảng các khóa của các phần tử trong e.  Yêu cầu: sắp xếp các giá trị này sao cho mảng k có thứ tự tăng hoặc giảm. Mô tả bài toán 6/8/2010 Nguyễn Thị Thúy Loan 44 Ý tưởng:  Xuất phát từ đầu dãy, lần lượt tìm những phần tử còn lại không thỏa thứ tự với phần tử đang xét. Với mỗi phần tử tìm được mà không thoả thứ tự • Thực hiện hoán vị để thỏa thứ tự  Lặp lại tương tự với các phần tử tiếp theo Interchange Sort 6/8/2010 Nguyễn Thị Thúy Loan 45 B1: i = 0; // đầu dãy B2: j = i +1; // duyệt qua các phần tử sau i B3: while j < n do o if a[j] < a[i] then Swap(a[i], a[j]); o j = j +1; B4: i = i +1; o if i < n then B2; o else  Kết thúc! Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 46 10 3 7 6 2 5 4 16 i j Ví dụ minh họa 6/8/2010 Nguyễn Thị Thúy Loan 47 Cài đặt 6/8/2010 Nguyễn Thị Thúy Loan 48 Ý tưởng:  Cho dãy ban đầu a[0], a[2],.., a[n-1], ta có thể xem dãy con gồm một phần tử a[0] đã được sắp.  Sau đó thêm a[1] vào đoạn a[0] sao cho a[0] a[1] được sắp. Insertion Sort 6/8/2010 Nguyễn Thị Thúy Loan 49  Tiếp tục thêm a[2] vào để có a[0] a[1] a[2] được sắp....  Cho đến khi thêm xong a[n-1] vào đoạn a[0] a[1]...a[n-2]  đoạn a[0] a[1]...a[n-2] a[n-1] được sắp. Insertion Sort 6/8/2010 Nguyễn Thị Thúy Loan 50 B1: i = 1;//giả sử có đoạn a[0] đã được sắp B2: x= a[i]; o Tìm được vị trí cần chèn x vào là pos B3: Dời chỗ các phần tử từ a[pos]  a[i-1] sang phải một vị trí để dành chỗ cho a[i]. B4: a[pos] = x;// có a[0]...a[i] được sắp. B5: i = i +1; o Nếu i < n: Lặp lại B2 o Ngược lại: Dừng  Dãy đã được sắp Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 51 Ý tưởng:  Lượt thứ nhất, chọn trong dãy khoá k[0..n-1] ra khóa nhỏ nhất và đổi giá trị với k[0], khi đó k[0] sẽ trở thành khoá nhỏ nhất.  Lượt thứ hai, chọn trong dãy khoá k[1..n-1] ra khóa nhỏ nhất và đổi giá trị với k[1]….  Lượt n-2, chọn giá trị nhỏ nhất trong k[n-2] và k[n-1] ra khoá nhỏ nhất và đổi giá trị với k[n-2]. Selection Sort 6/8/2010 Nguyễn Thị Thúy Loan 52 B1: i = 0 B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1] B3: Hoán vị a[i] và a[min] B4: Nếu i < n -1 thì i= i+1  Lặp B2 Ngược lại  Dừng Ví dụ: Cho dãy số như sau: 12 2 8 5 1 6 4 1 Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 53 Ý tưởng:  Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn về đầu.  Sau đó ở bước tiếp theo không xét phần tử đó nữa. Do vậy lần xử lý thứ i sẽ có vị trí đầu dãy là i.  Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào được xét. Bubble Sort 6/8/2010 Nguyễn Thị Thúy Loan 54 B1: i=0; // lần xử lý đầu tiên B2: j=n-1; // duyệt từ cuối ngược về i Trong khi (j>i) thực hiện: o Nếu a[j] < a[j-1]: Hoán đổi a[j] và a[j-1] o j = j -1; B3: i = i+1; // lần xử lý kế tiếp oNếu i > n-1: Hết dãy  Dừng o Ngược lại: quay lại B2 Các bước thực hiện 6/8/2010 Nguyễn Thị Thúy Loan 55 ShellSort Ý tưởng:  Cải tiến insertion sort o Hạn chế phương pháp chèn: khi luôn chèn 1 phần tử vào đầu dãy!  ShellSort cải tiến bằng cách chia làm nhiều dãy con và thực hiện phương pháp chèn trên từng dãy con. 6/8/2010 Nguyễn Thị Thúy Loan 56  Xét một dãy a[0]...a[n-1], cho một số nguyên h (1  h  n), chia dãy thành h dãy con như sau: o Dãy con 1: a[1], a[1+h], a[1+2h]... o Dãy con 2: a[2], a[2+h], a[2+2h]... o Dãy con 3: a[3], a[3+h], a[3+2h]... o Dãy con h: a[h], a[2h], a[3h]... ShellSort 6/8/2010 Nguyễn Thị Thúy Loan 57  VD: cho dãy n = 8, h = 3 10 3 7 6 2 5 4 16 Dãy chính 10 3 7 6 2 5 4 16 Dãy con 1 10 6 4 Dãy con 2 3 2 16 Dãy con 3 7 5 Ví dụ minh họa 6/8/2010 Nguyễn Thị Thúy Loan 58  Với mỗi bước h, áp dụng Insertion Sort trên từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính.  Tiếp tục làm tương tự đối với bước h div 2... cho đến h = 1.  Khi h =1 thực hiện Insertion Sort trên 1 dãy duy nhất là dãy chính  Kết quả được dãy phần tử được sắp. Ý tưởng 6/8/2010 Nguyễn Thị Thúy Loan 59 Các bước thực hiện B1: chọn k khoảng cách h[0], h[1],..,h[k-1], và i = 0; B2: Chia dãy ban đầu thành các dãy con có bước nhảy là h[i]. o Thực hiện sắp xếp từng dãy con bằng insertion sort. B3: i = i+1 o Nếu i ≥ k:  Dừng o Ngược lại:  Bước 2. 6/8/2010 Nguyễn Thị Thúy Loan 60 QuickSort  Thuật toán do Hoare đề xuất o Tốc độ trung bình nhanh hơn thuật toán khác. o Do đó Hoare dùng “quick” để đặt tên  Ý tưởng chính: QS phân hoạch dãy ban đầu thành hai phần dựa vào một giá trị x. o Dãy 1: gồm các phần tử a[i] nhỏ hơn x o Dãy 2: gồm các phần tử a[i] lớn hơn x 6/8/2010 Nguyễn Thị Thúy Loan 61  Phân hoạch dãy cần sắp a[l] .. a[r] thành ba phần: o a[k] < x, với k = 0...i o a[k] = x, với k = i..j o a[k] > x, với k = j..n-1 Trong đó x là một giá trị nào đó trong dãy a[k] x QuickSort 6/8/2010 Nguyễn Thị Thúy Loan 62  B1: Phân hoạch dãy a[l]...a[r] thành các dãy con: o Dãy con 1: a[l]...a[j] < x o Dãy con 2: a[j+1]...a[i-1] = x o Dãy con 3: a[i]...a[r] > x  B2: o Nếu (l < j): Phân hoạch dãy a[l]..a[j] o Nếu (i<r): Phân hoạch dãy a[i]...a[r] Các bước thực hiện B1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, l  k  r, o Cho x = a[k], i = l, j = r; B2: Tìm và hoán vị cặp phần tử a[i] và a[j] không đúng thứ tự đang sắp: o Trong khi a[i] < x  i++; o Trong khi a[j] > x  j--; o Nếu i <= j  Swap(a[i], a[j]) B3: Nếu i <= j  Bước 2; o Ngược lại  Dừng. Ý tưởng DANH SÁCH LIÊN KẾT ThS. Nguyễn Thị Thúy Loan Chương III Tham khảo bài giảng ThS. Nguyễn Hà Giang 6/8/2010 Nguyễn Thị Thúy Loan 65 Nội dung  Danh sách liên kết đơn o Giới thiệu o Cài đặt o Thao tác o Ứng dụng  Danh sách vòng  Danh sách liên kết kép 6/8/2010 Nguyễn Thị Thúy Loan 66 DSLK đơn - Giới thiệu  Mảng 1 chiều o Kích thước cố định o Chèn 1 phần tử vào mảng rất khó o Các phần tử tuần tự theo chỉ số 0  n-1 o Truy cập ngẫu nhiên 0 1 2 3 4 n-2 n-1 chèn 6/8/2010 Nguyễn Thị Thúy Loan 67 Giới thiệu Danh sách liên kết  Cấp phát động lúc chạy chương trình  Các phần tử nằm rải rác ở nhiều nơi trong bộ nhớ  Kích thước danh sách chỉ bị giới hạn do RAM  Thao tác thêm Xóa đơn giản 6/8/2010 Nguyễn Thị Thúy Loan 68 Giới thiệu Insert, Delete 6/8/2010 Nguyễn Thị Thúy Loan 69 Định nghĩa  Danh sách liên kết đơn là chuỗi các Node, được tổ chức theo thứ tự tuyến tính  Mỗi Node gồm 2 phần: o Phần Data, information o Phần link hay con trỏ trỏ đến Node kế tiếp 6/8/2010 Nguyễn Thị Thúy Loan 70 Ôn pointer  Nhắc lại pointer int i, *pi; i pi 1FF0 1FF4 ? ? pi = &i; i pi 1FF0 1FF4 ? 1FF0*pi i = 10 or *pi = 10 i pi 1FF0 1FF4 10 1FF0*pi 6/8/2010 Nguyễn Thị Thúy Loan 71 Minh họa  Mô tả danh sách A1 A2 A3 An Head Node Node Tail Node null Data Link 6/8/2010 Nguyễn Thị Thúy Loan 72 Minh họa  Ví dụ: ‘D’ 500 ‘S’ 600 ‘L’ 300 ‘D’ null 700 500 600 300 Địa chỉ pHead 6/8/2010 Nguyễn Thị Thúy Loan 73 Khai báo phần data  Khai báo danh sáchLK  Data o Kiểu dữ liệu định nghĩa trước o Chứa dữ liệu, thông tin của từng Node Typedef struct Node { DATA info ; Node * next ; }; Data: int, long, float, SV, NV,…. 6/8/2010 Nguyễn Thị Thúy Loan 74 typedef struct Node { Data info; Node * next; }; typedef struct Node { int info; Node * next; }; typedef struct Node { SinhVien info; Node * next; }; Cấu trúc Node Khai báo phần data 6/8/2010 Nguyễn Thị Thúy Loan 75 Khai báo và khởi tạo typedef struct Node { Data info; Node * next; }; Node* h; Node* h = NULL; h quản lý danh sách Khởi tạo danh sách 6/8/2010 Nguyễn Thị Thúy Loan 76 Thao tác cơ bản  Tạo một nút mới  Thêm phần tử vào đầu danh sách  Thêm phần tử vào cuối danh sách  Thêm phần tử vào sau q  Xóa phần tử đầu.  Xóa phần tử sau q  Tìm kiếm.  Sắp xếp. Phần minh họa sẽ dùng Data là int 6/8/2010 Nguyễn Thị Thúy Loan 77 Tạo nút mới Node * Getnode (Data x) { Node * p = new Node; if ( p == NULL ) return NULL; p  info = x; p  next = NULL; return p ; } 6/8/2010 Nguyễn Thị Thúy Loan 78  Thêm vào đầu danh sách h h p new h p h p Thêm phần tử vào đầu DS 6/8/2010 Nguyễn Thị Thúy Loan 79 Thêm phần tử vào đầu DS 6/8/2010 Nguyễn Thị Thúy Loan 80 Thêm phần tử vào cuối DS 6/8/2010 Nguyễn Thị Thúy Loan 81 Thêm vào sau phần tử q  Thêm vào sau Node q trong danh sách q q p new q p q p 6/8/2010 Nguyễn Thị Thúy Loan 82 Xóa phần tử đầu  Xóa phần tử đầu danh sách h h h h p p 6/8/2010 Nguyễn Thị Thúy Loan 83 Xóa phần tử sau q  Xóa phần tử sau Node q trong danh sách q p pq q 6/8/2010 Nguyễn Thị Thúy Loan 84 Xóa toàn bộ danh sách h p h p 6/8/2010 Nguyễn Thị Thúy Loan 85 Xóa toàn bộ danh sách 6/8/2010 Nguyễn Thị Thúy Loan 86 Tìm kiếm  Tìm phần tử lớn nhất.  Tìm vị trí phần tử lớn nhất.  Tìm phần tử có giá trị bằng x. 6/8/2010 Nguyễn Thị Thúy Loan 87 Sắp xếp void Interchange_sort (Node * h) { } 6/8/2010 Nguyễn Thị Thúy Loan 88 void Selection_sort (Node* h) { } Sắp xếp 6/8/2010 Nguyễn Thị Thúy Loan 89 Duyệt danh sách void Duyet (Node* h [, Node * t] ) { for (Node* p = h; p ; p = p  next) ; } 6/8/2010 Nguyễn Thị Thúy Loan 90 Minh họa in danh sách p = h; while (p!=NULL) { printf(“ %5d”, p info); p = p  next; } 3000 4 5000 10 4000 5 NULL 3000 5000 4000h p 6/8/2010 Nguyễn Thị Thúy Loan 91 p = h; while (p!=NULL) { printf(“ %5d”, p info); p = p  next; } 3000 4 5000 10 4000 5 NULL 3000 5000 4000 3000 h p Minh họa in danh sách 6/8/2010 Nguyễn Thị Thúy Loan 92 p = h; while (p!=NULL) { printf(“ %5d”, p info); p = p  next; } 3000 4 5000 10 4000 5 NULL 3000 5000 4000 3000 h p Minh họa in danh sách 6/8/2010 Nguyễn Thị Thúy Loan 93 p = h; while (p!=NULL) { printf(“ %5d”, p info); p = p  next; } 3000 4 5000 10 4000 5 NULL 3000 5000 4000 3000 h p Minh họa in danh sách 6/8/2010 Nguyễn Thị Thúy Loan 94 In danh sách void Indanhsach(Node *h) { for (Node *p = h; p; p = p  next) printf(“%5d”, p info); } void Indanhsach (