1.Khái niệm danh sách kề
Danh sách là một tập hợp có sự sắp xếp các phần tử có cùng kiểu với nhau. Các phần tử trong danh sách luôn có thứ tự đứng trước – sau.
Danh sách kề sử dụng mảng là khái niệm căn bản trong cấu trúc danh sách. Hiểu được danh sách kề sử dụng mảng sẽ dễ dàng tiếp cận hơn với danh sách liên kết đơn, danh sách liên kết đôi….
2.Cài đặt danh sách kề bằng mảng
Khi cài đặt một cấu trúc danh sách kề sử dụng mảng ta cần có:
- N: Quản lý số phần tử mảng.
- A: là mảng lưu chữ các phần tử của danh sách.
- MAX: là số lượng phần tử có thể lưu trữ của mảng
Chú ý: Các phần tử có trong danh sách được lưu trữ ở các vị trí kế tiếp nhau trong bộ nhớ!
Ví dụ một danh sách lưu trữ 11 số nguyên: 1,2,3,4,5,6,7,8,9,10,11 (ta ngầm hiểu rằng mảng A gồm 11 phần tử ở hình minh họa bên dưới!)
Cài đặt danh sách kề với mảng A gồm 11 phần tử với ngôn ngữ C/C++ với kiểu struct DSKe như sau:
#include <stdio.h> #define MAX 100 //dinh nghia so luong phan tu cua mang co the luu tru typdef struct DSKe{ //mang int a voi kich thuoc MAX = 100 int A[MAX]; //quan ly so luong N phan tu int n; }DSKe;
Chú ý:
- MAX ở trên ta có thể thay thế là một số lớn hơn 11 (ở trên tôi để MAX = 100). Tuy nhiên với yêu cầu lưu trữ 11 phân tử ta không được phép khai báo MAX nhỏ hơn 11.
- Vì ta cần danh sách lưu trữ cho giá trị số nguyên nên mảng A sẽ mang kiểu int A[MAX], nếu ta cần lưu trữ cho giá trị là các ký tự thì ta có thể sử dụng kiểu char A[MAX], hay lưu trữ giá trị trong danh sách có kiểu Sinh viên mà ta tự định nghĩa thì ta có thể sử dụng kiểu SinhVien A[MAX]
- Từ khóa typedef struct DSKe được sử dụng để viết ngắn ngọn struct trên thành DSKe
3.Các thao tác trên danh sách kề
3.1 Khởi tạo danh sách kề
Danh sách ban đầu khi được khởi tạo sẽ mặc định có N bằng 0, nghĩa là việc khởi tạo danh sách chính là việc đưa danh sách này về rỗng (NULL).
Hình minh họa dưới đây cho thấy hàm khởi tạo mặc định danh sách kề ban đầu bằng rỗng (đặt số phần tử mảng bằng 0)
Hàm void KhoiTao(DSKe &ds) duới đây nhận tham chiếu đầu vào là DSKe &ds và gán giá trị ds.n = 0;
#include <stdio.h> #define MAX 100 //dinh nghia so luong phan tu cua mang co the luu tru //cai dat cau truc DSK typedef struct DSKe{ //mang int a voi kich thuoc MAX = 100 int A[MAX]; //quan ly so luong N phan tu int n; }DSKe; //khai bao ham khoi tao void KhoiTao(DSKe &ds){ //ban dau danh sach la rong (n = 0) ds.n = 0; } int main(){ //khai bien ds co kieu DSKe DSKe ds; //dua ds o tren vao ham khoitao KhoiTao(ds); }
3.2 Kiểm tra danh sách rỗng
Một việc hết sức quan trọng khi thao tác lấy phần tử trong danh sách đó là kiểm tra xem danh sách đó còn rỗng không (nếu không rỗng thì mới có thể lấy ra phần tử trong danh sách người lại nếu rỗng thì không có phần tử để lấy ra)
Hàm int KiemTraRong(DSKe ds) duới đây nhận đầu vào là DSKe ds và dùng câu lệnh điều kiện để kiểm tra danh sách có rỗng hay không:
Nếu điều kiện ds.n == 0 (nghĩa là danh sách là rỗng) thì return 1; ngược lại return 0;
int KiemTraRong(DSKe ds){ //neu ds.n == 0 thi rong if (ds.n==0){ return 1; } return 0; }
3.2 Kiểm tra danh sách đầy
Ngược lại với kiểm tra rỗng, ta sẽ cần kiểm tra xem danh sách đã đầy hay chưa (nếu đầy rồi thì không thể thêm phần tử vào danh sách)
Hàm int KiemTraDay(DSKe ds) duới đây nhận đầu vào là DSKe ds và dùng câu lệnh điều kiện để kiểm tra danh sách đã đầy hay chưa:
Nếu điều kiện ds.n == MAX (nghĩa là danh sách đã có đủ số lượng phần tử bên trong bằng MAX) thì return 1; ngược lại return 0;
int KiemTraDay(DSKe ds){ //neu ds.n == MAX thi da day if (ds.n == MAX){ return 1; } return 0; }
4.Cài đặt hoàn chỉnh danh sách kề sử dụng mảng
Chương trình dưới đây là một chương trình đầy đủ các hàm (hay đầy đủ nội dung) cần thiết mà tôi đã đề cập ở trên.
#include <stdio.h> #define MAX 100 //dinh nghia so luong phan tu cua mang co the luu tru typedef struct DSKe{ //mang int a voi kich thuoc MAX = 100 int A[MAX]; //quan ly so luong N phan tu int n; }DSKe; //khai bao ham khoi tao void KhoiTao(DSKe &ds){ //ban dau danh sach la rong (n = 0) ds.n = 0; } //khai bao ham kiem tra rong int KiemTraRong(DSKe ds){ //neu ds.n == 0 thi rong if (ds.n==0){ return 1; } return 0; } //khai bao ham kiem tra day int KiemTraDay(DSKe ds){ //neu ds.n == MAX thi da day if (ds.n == MAX){ return 1; } return 0; } int main(){ //khai bien ds co kieu DSKe DSKe ds; //dua ds vao ham khoitao KhoiTao(ds); }
Chú ý: Các hàm cài đặt danh sách kề, khởi tạo danh sách, kiểm tra rỗng, kiểm tra đầy là bắt buộc phải có trong chương trình trên để thuận tiện cho công việc thao tác và sử dụng danh sách kề trong những bài tiếp theo!