Khái niệm danh sách liên kết

Khái niệm danh sách liên kết

Danh sách liên kết đơn, mỗi cấu trúc chứa một con trỏ trỏ đến cấu trúc tiếp theo hoặc trước đó. Đối với danh sách con trỏ trỏ về trước, cấu trúc đầu tiên của danh sách sẽ trỏ về hằng con trỏ NULL, cấu trúc cuối cùng được đánh dấu bởi con trỏ last là con trỏ trỏ vào cấu trúc này. Đối với danh sách con trỏ trỏ về cấu trúc tiếp theo, cấu trúc đầu sẽ được đánh dấu bằng con trỏ head và cấu trúc cuối cùng chưa con trỏ NULL.

Danh sách liên kết kép gồm 2 con trỏ, một trỏ đến cấu trúc trước và một trỏ đến cấu trúc sau, 2 đầu của danh sách được đánh dấu bởi các con trỏ head, last.

Danh sách liên kết vòng gồm 1 con trỏ trỏ về sau (hoặc trước), hai đầu của danh sách được nối với nhau tạo thành vòng tròn. Chỉ cần một con trỏ head để đánh dấu đầu danh sách.

Do trong cấu trúc có chứa các con trỏ trỏ đến cấu trúc tiếp theo và/hoặc cấu trúc đứng trước nên từ một cấu trúc này chúng ta có thể truy cập đến một cấu trúc khác (trước và/hoặc sau nó). Kết hợp với các con trỏ đánh dấu 2 đầu danh sách (head, last) chúng ta sẽ dễ dàng làm việc với bất kỳ phần tử nào của danh sách. Có thể kể một số công việc thường thực hiện trên một danh sách như: bổ sung phần tử vào cuối danh sách, chèn thêm một phần tử mới, xoá một phần tử của danh sách, tìm kiếm, sắp xếp danh sách, in danh sách …

Hình vẽ bên dưới minh hoạ một danh sách liên kết đơn quản lý sinh viên, thông tin chứa trong mỗi phần tử của danh sách gồm có họ tên sinh viên, điểm. Ngoài ra mỗi phần tử còn chứa con trỏ tiep để nối với phần tử tiếp theo của nó. Phần tử cuối cùng nối với cấu trúc rỗng (NULL).

NVA 9.0

TTB 7.5

PHT 4.0

NULL

Các phép toán trên danh sách liên kết

Dưới đây chúng ta mô tả tóm tắt cách thức thực hiện một số thao tác trên danh sách liên kết đơn.

Tạo phần tử mới

Để tạo phần tử mới thông thường chúng ta thực hiện theo các bước sau đây:

dùng toán tử new xin cấp phát một vùng nhớ đủ chứa một phần tử của danh sách.

nhập thông tin cần lưu trữ vào phần tử mới. Con trỏ tiep được đặt bằng NULL.

gắn phần tử vừa tạo được vào danh sách. Có hai cách:

hoặc gắn vào đầu danh sách, khi đó vị trí của con trỏ head (chỉ vào đầu danh sách) được điều chỉnh lại để chỉ vào phần tử mới.

hoặc gắn vào cuối danh sách bằng cách cho con trỏ tiep của phần tử cuối danh sách (đang trỏ vào NULL) trỏ vào phần tử mới. Nếu danh sách có con trỏ last để chỉ vào cuối danh sách thì last được điều chỉnh để trỏ vào phần tử mới. Nếu danh sách không có con trỏ last thì để tìm được phần tử cuối chương trình phải duyệt từ đầu, bắt đầu từ con trỏ head cho đến khi gặp phần tử trỏ vào NULL, đó là phần tử cuối của danh sách.

head

MOI 0.0			NVA 9.0			TTB 7.5			PHT 4.0	NULL
Gắn phần tử mới vào đầu danh sách

Chèn phần tử mới vào giữa

Giả sử phần tử mới được chèn vào giữa phần tử thứ i và i+1. Để chèn ta nối phần tử thứ i vào phần tử mới và phần tử mới nối vào phần tử thứ i+1. Thuật toán sẽ như sau:

Cho con trỏ p chạy đến phần tử thứ i.

Cho con trỏ tiep của phần tử mới trỏ vào phần tử thứ i+1 (tuc p->tiep).

Cho con trỏ tiep của phần tử thứ i (hiện được trỏ bởi p) thay vì trỏ vào phần tử thứ i+1 bây giờ sẽ trỏ vào phần tử mới.

MOI

đầu 0.0

i 9.0

i+1 7.5

cuối 4.0

NULL

Chèn phần tử mới vào giữa phần tử i và i+1

1. 
   Xoá phần tử thứ i khỏi danh sách
   

Việc xoá một phần tử ra khỏi danh sách rất đơn giản bởi chỉ việc thay đổi các con trỏ. Cụ thể giả sử cần xoá phần tử thứ i ta chỉ cần cho con trỏ tiep của phần tử thứ i-1 trỏ ("vòng qua" phần tử thứ i) vào phần tử thứ i+1. Như vậy bây giờ khi chạy trên danh sách đến phần tử thứ i-1, phần tử tiếp theo là phần tử thứ i+1 chứ không còn là phần tử thư i. Nói cách khác phần tử thứ i không được nối bởi bất kỳ phần tử nào nên nó sẽ không thuộc danh sách. Có thể thực hiện các bước như sau:

Cho con trỏ p chạy đến phần tử thứ i-1.

Đặt phần tử thứ i vào biến x.

Cho con trỏ tiep của phần tử thứ i-1 trỏ vào phần tử thứ i+1 bằng cách đặt tiep = x.tiep.

Giải phóng bộ nhớ được trỏ bởi x bằng câu lệnh delete x.

i-1 0.0			i 9.0			i+1 7.5			cuối 4.0	NULL
Xóa phần tử thứ i

Duyệt danh sách

Duyệt là thao tác đi qua từng phần tử của danh sách, tại mỗi phần tử chương trình thực hiện một công việc gì đó trên phần tử mà ta gọi là thăm phần tử đó. Một phép thăm có thể đơn giản là hiện nội dung thông tin của phần tử đó ra màn hình chẳng hạn. Để duyệt danh sách ta chỉ cần cho một con trỏ p chạy từ đầu đến cuối danh sách đến khi phần tử cuối có con trỏ tiep = NULL thì dừng. Câu lệnh cho con trỏ p chuyển đến phần tử tiếp theo của nó là:

p = p ® tiep ;

Tìm kiếm

Cho một danh sách trong đó mỗi phần tử của danh sách đều chứa một trường gọi là trường khoá, thường là các trường có kiểu cơ sở hoặc kết hợp của một số trường như vậy. Bài toán đặt ra là tìm trên danh sách phần tử có giá trị của trường khoá bằng với một giá trị cho trước. Tiến trình thực hiện nhiệm vụ thựcchất cũng là bài toán duyệt, trong đó thao tác "thăm" chính là so sánh trường khoá của phần tử với giá trị cho trước, nếu trùng nhau ta in kết quả và dừng, Nếu đã duyệt hết mà không có phần tử nào có trường khoá trùng với giá trị cho trước thì xem danh sách không chứa giá trị này.

Ngoài các thao tác trên, nói chung còn nhiều các thao tác quen thuộc khác tuy nhiên chúng ta không trình bày ở đây vì nó không thuộc phạm vi của giáo trình này.

Dưới đây là một ví dụ minh hoạ cho cấc cấu trúc tự trỏ, danh sách liên kết và một vài thao tác trên danh sách liên kết thông qua bài toán quản lý sinh viên.

Khai báo

struct DATE

{

int day, month, year; // ngày, tháng, năm

};

struct Sinhvien { // cấu trúc tự trỏ

char hoten[31];

DATE ns;

float diem;

Sinhvien *tiep ;

};

Sinhvien *dau = NULL, *cuoi = NULL; // Các con trỏ tới đầu và cuối ds

Sinhvien *cur = NULL; // Con trỏ tới sv hiện tại

int sosv = 0; // Số sv của danh sách

Tạo sinh viên mới và nhập thông tin, trả lại con trỏ trỏ đến sinh viên mới.

Sinhvien* Nhap1sv() // Tạo 1 khối dữ liệu cho sv mới

{

Sinhvien *kq = new Sinhvien[1] ; // Cấp phát bộ nhớ cho kq

cout << "\nSinh vien thu ", sosv+1 ;

cout << "Ho ten = " ; cin.getline(kq->hoten);

cout << "Ns = " ; cin >> kq->ns.day >> kq->ns.month >> kq->ns.year;

cout << "Diem = " ; cin >> kq->diem ; cin.ignore() ;

kq->tiep = NULL;

return kq ;

}

Bổ sung sinh viên mới vào cuối danh sách.

void Bosung() // Bổ sung sv mới vào cuối ds

{

cur = Nhap1sv();

if (sosv == 0) {dau = cuoi = cur;}

else { cuoi->tiep = cur; cuoi = cur; }

sosv++;

}

Chèn sv mới vào trước sinh viên thứ n.

void Chentruoc(int n) // Chèn sv mới vào trước sv thứ n

{

cur = Nhap1sv();

if (sosv==0) { dau = cuoi = cur; sosv++; return; }

if (sosv==1 || n==1) {cur->tiep = dau; dau = cur; sosv++; return;}

Sinhvien *truoc, *sau;

truoc = dau;

sau = dau -> tiep;

for (int i=1; itiep;

sau = truoc->tiep;

truoc->tiep = cur;

cur -> tiep = sau;

sosv ++;

}

Chèn sv mới vào sau sinh viên thứ n.

void Chensau(int n) // Chèn sv mới vào sau sv thứ n

{

cur = Nhap1sv();

if (sosv==0 || sosv

Sinhvien *truoc, *sau;

truoc = dau; sau = dau -> tiep;

for (int i=1; itiep;

sau = truoc->tiep;

truoc->tiep = cur;

cur -> tiep = sau;

sosv ++;

}
Xoá sinh viên thứ n.

void Xoa(int n) // Xoá sinh viên thứ n

{

if (sosv==1&&n==1) { delete dau ; dau = cuoi = NULL; sosv--; return; }

if (n==1) { cur = dau; dau = cur->tiep; delete cur; sosv--; return; }

Sinhvien *truoc, *sau;

truoc = dau;

sau = dau -> tiep;

for (int i=1; itiep;

cur = truoc->tiep; sau = cur->tiep; truoc->tiep = sau;

delete cur ;

sosv --;

}

Tạo danh sách sinh viên.

void Taods() // Tạo danh sách

{

int tiep = 1;

while (tiep) {

Bosung();

cout << "Tiep (0/1) ? " ; cin >> tiep ;

}

}

In danh sách sinh viên.

void Inds() // In danh sách

{

cur = dau; int i=1;

while (cur != NULL) {

cout << "\nSinh vien thu " << i << " ----------------------------\n") ;

cout << "Hoten:" << cur->hoten ;

cout << "Ngay sinh: "

cout << cur -> ns.day << "/" ;

cout << cur -> ns.month << "/" ;

cout << cur -> ns.year ;

cout << "Diem: " << cur->diem ;

cur = cur->tiep; i++;

}

}

Hàm chính.

void main()

{

clrscr();

Taods();

Inds();

getch();

}

Каталог: wp-content -> uploads -> 2015
2015 -> TRƯỜng đẠi học ngân hàng tp. Hcm markerting cơ BẢn lớP: mk001-1-111-T01
2015 -> Hãy là người đầu tiên biết
2015 -> Có chiến lược toàn diện về việc truyền phát tin tức
2015 -> BỘ TÀi chính
2015 -> THỦ TƯỚng chính phủ
2015 -> SỞ lao đỘng thưƠng binh và XÃ HỘI
2015 -> CỘng hòa xã HỘi chủ nghĩa việt nam trưỜng đẠi học cần thơ Độc lập – Tự do – Hạnh phúc
2015 -> Dapandethi. Blogspot. Com lịch sử BÁo chí thế GiỚI
2015 -> Dapandethi. Blogspot. Com đẠi học quốc gia hà NỘi trưỜng đẠi học khoa học xã HỘi và nhân văn khoa báo chí
2015 -> Tài liệu đang trong quá trình chỉnh sửa, không phải là giá trình chính thức Dân số và sự gia tăng dân số

tải về 1.98 Mb.

Chia sẻ với bạn bè của bạn: