BÀI 5: DANH SÁCH NỐI ĐƠN
[Singlely Linked List]
Bộ môn CNPM- Khoa CNTT
Trường Đại học SPKT Hưng Yên
Mục tiêu
Sau khi học xong bài học người học có khả năng:
- Trình bày được khái niệm về danh sách nối đơn
- Trình bày được cấu trúc dữ liệu của 1 node trong danh
sách nối đơn
- Giải thích được nguyên tắc lưu trữ của danh sách nối
đơn
- Viết được các giải thuật thêm, xóa, tìm kiếm, duyệt
sanh sách nối đơn
- Hình thành kỹ năng lập trình
Nội dung
Danh sách liên kết
Danh sách liên kết đơn
Khái niệm
Khai báo
Truy xuất
Một số thao tác trên danh sách liên kết
Danh sách liên kết
Danh sách liên kết là tập hợp các phần tử được liên kết nhau bởi
các mối liên kết;
Mỗi phần tử của danh sách được gọi là 1 node;
Mỗi node gồm có thành phần dữ liệu để chứa thông tin của phần
tử, và một hoặc nhiều mối liên kết để liên kết với node trước [và
node sau nó]
Danh sách & danh sách liên kết
Danh sách Danh sách liên kết
Danh sách là một mô hình dữ
liệu, nó có thể được cài đặt bởi
các cấu trúc dữ liệu khác nhau.
DSLK là một cấu trúc dữ liệu,
nó được sử dụng để biểu diễn
danh sách.
Phân loại danh sách liên kết
Tùy thuộc vào số liên kết trên mỗi phần tử và cách thức kết nối
giữa các nút trong DSLK mà có thể chia DSLK thành nhiều
loại:
Danh sách liên kết đơn
Danh sách liên kết đôi/ kép
Danh sách liên kết vòng đơn
Danh sách liên kết vòng kép
Phân loại danh sách liên kết
Danh sách liên kết vòng: phần tử cuối danh sách
liên kết với phần tử đầu danh sách:
A B X Z Y
A B C D
Nội dung
Danh sách liên kết
Danh sách liên kết đơn
Khái niệm
Khai báo
Truy xuất
Một số thao tác trên danh sách liên kết
Khái niệm danh sách nối đơn
Mỗi phần tử [nút] gồm 2 thành phần:
Thành phần dữ liệu: chứa giá trị lưu trong nút đó.
Thành phần mối liên kết: chứa con trỏ [địa chỉ] tới nút kế tiếp
trong danh sách, hoặc lưu trữ một giá trị đặc biệt [gọi là con
trỏ rỗng null] nếu là nút cuối cùng của danh sách.
Nội dung
Danh sách liên kết
Danh sách liên kết đơn
Khái niệm
Định nghĩa cấu trúc của một phần tử trong danh sách
Truy xuất
Một số thao tác trên danh sách liên kết
Định nghĩa cấu trúc của một phần tử
trong danh sách
class Node
{
public DataType info; //Data là kiểu dữ liệu định nghĩa trước
public Node link; // con trỏ chỉ đến cấu trúc Node
}
Trong đó:
Node: là tên CTDL của 1 phần tử trong danh sách
DataType: là cấu trúc dữ liệu để biểu diễn cho 1 phần tử của
danh sách
link: Tên của mối liên kết [do người dùng đặt]
Ví dụ
Khai báo 1 node dữ liệu
lưu số nguyên:
class Node
{
public int info;
public Node link;
}
Khai báo 1 node dữ liệu lưu đối
tượng sinh viên:
class[struct] SinhVien
{
public string Ten;
public int MaSV;
}
class SVNode
{
public SinhVien info;
public SVNode link;
} 18
Ví dụ 2:
Định nghĩa CTDL của 1 node của DSLK đơn chứa 1 danh
sách tên của các đường phố
class Node{
public string info;
public Node link;
}
Ví dụ 3:
Định nghĩa CTDL của 1 node của DSLK đơn chứa 1 danh
sách sinh viên, biết rằng mỗi sinh viên gồm có các thông
tin: Mã sinh viên, Họ tên, Lớp, Năm sinh
Cấu trúc dữ liệu của 1 phần tử của danh sách có dạng:
class Node
{
public DataType info;
public Node link;
}
Vậy cấu trúc dữ liệu nào có thể biểu diễn được đầy đủ
của 1 sinh viên?
Đề bài: Xây dựng chương trình quản lý sinh viên bằng danh sách liên kết đơn, bao gồm các thông tin: Mã số sinh viên [MSSV], Họ và tên [HoTen], Điểm trung bình [DTB].
Yêu cầu:
- Nhập, xuất danh sách sinh viên.
- Tìm kiếm sinh viên theo MSSV.
- Thêm sinh viên vào danh sách đã sắp xếp.
- Xóa sinh viên khỏi danh sách theo MSSV.
- Sắp xếp danh sách sinh viên [Solection Sort, Interchange Sort, Bubble]
Khai báo kiểu cấu trúc SinhVien
typedef struct SinhVien
{
int MSSV;
char HoTen[30];
float DTB;
} SV;
Tạo cấu trúc danh sách liên kết đơn
struct node
{
SV info;
node* next;
};
typedef struct node NODE;
struct list
{
node* pHead;
node* pTail;
};
typedef struct list LIST;
1. Các thao tác cơ bản trên danh sách liên kết đơn
Khởi tạo danh sách liên kết đơn
void init[list& l]
{
l.pHead = NULL;
l.pTail = NULL;
}
Tạo node mới
node* makenode[SV s]
{
node* p = new node;
if [p == NULL]
{
cout info.MSSV = s.MSSV;
strcpy_s[p->info.HoTen, s.HoTen];
p->info.DTB = s.DTB;
p->next = NULL;
return p;
}
Thêm node vào đầu danh sách
void AddFirst[list& l, node* p]
{
if [l.pHead == NULL]
l.pHead = l.pTail = p;
else
{
p->next = l.pHead;
l.pHead = p;
}
}
Thêm node vào cuối danh sách
void AddLast[list& l, node* p]
{
if [l.pHead == NULL]
l.pHead = l.pTail = p;
else
{
l.pTail->next = p;
l.pTail = p;
}
}
Xóa node đầu danh sách
void RemoveFirst[list& l]
{
node* p = l.pHead;
if [l.pHead == NULL]
cout next;
delete p;
}
}
Xóa node cuối danh sách
void RemoveLast[list& l]
{
node* p = l.pHead;
node* r = new node;
if [l.pHead == NULL]
cout next;
}
l.pTail = r;
r->next = NULL;
delete p;
}
}
2. Nhập, xuất danh sách sinh viên
Hàm nhập thông tin của một sinh viên
void Nhap[SV& s]
{
cout > s.MSSV;
while [getchar[] != ‘\n’];
cout s.DTB;
}
Hàm nhập danh sách sinh viên
void InputList[list& l]
{
int n;
SV s;
do
{
cout > n;
if [n info];
}
}
- Sắp xếp Interchange Sort
void InterchangeSort[list l]
{
for [node* i = l.pHead; i != l.pTail; i = i->next]
for [node* j = i->next; j != NULL; j = j->next]
if [i->info.MSSV > j->info.MSSV]
swap[i->info, j->info];
}
- Sắp xếp Bubble
void Bubble[list l]
{
node* pTail2 = l.pTail, * r = l.pHead;
for [node* i = l.pHead; i != pTail2; pTail2 = r]
for [node* j = l.pHead; j != pTail2; j = j->next]
{
if [j->info.MSSV > j->next->info.MSSV]
swap[j->info, j->next->info];
r = j;
}
}
Tác giả: Lê Thị Mỹ Hậu [sinh viên lớp 21DHT02, khoa Công Nghệ Thông Tin]