Tác giả phạm hồng thái bài giảng ngôn ngữ LẬp trình c/C++



tải về 1.98 Mb.
trang35/55
Chuyển đổi dữ liệu07.07.2016
Kích1.98 Mb.
1   ...   31   32   33   34   35   36   37   38   ...   55

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


Danh sách liên kết là một cấu trúc dữ liệu cho phép thể hiện và quản lý danh sách bằng các cấu trúc liên kết với nhau thông qua các con trỏ trong cấu trúc. Có nhiều dạng danh sách liên kết phụ thuộc vào các kết nối, ví dụ:

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).




head






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();

}

1   ...   31   32   33   34   35   36   37   38   ...   55


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương