Giải Thuật Và Lập Trình - C: IV. Danh Sách Liên Kết Kép (DOUBLE

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Giải thuật và lập trình - C Chương I. Mở đầu I. Từ bài toán đến chương trình II. Kiểu dữ liệu trừu tượng (ABSTRACT DATA TYPE - ADT) III. Kiểu dữ liệu, Cấu trúc dữ liệu, Kiểu dữ liệu trừu tượng (DATA TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES) Chương II. Các kiểu dữ liệu trừu tượng cơ bản I. Kiểu dữ liệu danh sách (LIST) II. Ngăn xếp (Stack) III. Hàng đợi (QUEUE) IV. Danh sách liên kết kép (DOUBLE - LISTS) BÀI TẬP Chương III. Cấu trúc cây (TREES) I. Các thuật ngữ cơ bản trên cây II. Kiểu dữ liệu trừu tượng cây III. Cài đặt cây IV. Cây nhị phân (BINARY TREES) V. Cây tìm kiếm nhị phân (BINARY SEARCH TREES) BÀI TẬP Chương IV. Tập hợp I, II. Khái niệm, Kiểu dữ liệu trừu tượng tập hợp III. Cài đặt tập hợp IV. Từ điển (DICTIONARY) V. HÀNG ƯU TIÊN (PRIORITY QUEUE) BÀI TẬP Chương V. Đồ thị (Graph) I. Các định nghĩa II. Kiểu dữ liệu trừu tượng đồ thị III. Biều diễn đồ thị IV. Các phép duyệt đồ thị (Traversals of graph) V. Một số bài toán trên đồ thị BÀI TẬP Solutions Solution CÀI ĐẶT CÂY (TREE) bằng mảng Giải thuật và lập trình - C: IV. Danh sách liên kết kép (DOUBLE - LISTS) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

IV. DANH SÁCH LIÊN KẾT KÉP (DOUBLE - LISTS)

Một số ứng dụng đòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một cách hiệu quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trước X và sau X một cách mau chóng. Trong trường hợp này ta phải dùng hai con trỏ, một con trỏ chỉ đến phần tử đứng sau (next), một con trỏ chỉ đến phần tử đứng trước (previous). Với cách tổ chức này ta có một danh sách liên kết kép. Dạng của một danh sách liên kép như sau:

Hình II.15 Hình ảnh một danh sách liên kết kép

Các khai báo cần thiết

typedef ... ElementType;

//kiểu nội dung của các phần tử trong danh sách

typedef struct Node{

ElementType Element; //lưu trữ nội dung phần tử

//Hai con trỏ trỏ tới phần tử trước và sau

Node* Prev;

Node* Next;

};

typedef Node* Position;

typedef Position DoubleList;

Để quản lí một danh sách liên kết kép ta có thể dùng một con trỏ trỏ đến một ô bất kỳ trong cấu trúc. Hoàn toàn tương tự như trong danh sách liên kết đơn đã trình bày trong phần trước, con trỏ để quản lí danh sách liên kết kép có thể là một con trỏ có kiểu giống như kiểu phần tử trong danh sách và nó có thể được cấp phát ô nhớ (tương tự như Header trong danh sách liên kết đơn) hoặc không được cấp phát ô nhớ. Ta cũng có thể xem danh sách liên kết kép như là danh sách liên kết đơn, với một bổ sung duy nhất là có con trỏ previous để nối kết các ô theo chiều ngược lại. Theo quan điểm này thì chúng ta có thể cài đặt các phép toán thêm (insert), xoá (delete) một phần tử hoàn toàn tương tự như trong danh sách liên kết đơn và con trỏ Header cũng cần thiết như trong danh sách liên kết đơn, vì nó chính là vị trí của phần tử đầu tiên trong danh sách.

Tuy nhiên, nếu tận dụng khả năng duyệt theo cả hai chiều thì ta không cần phải cấp phát bộ nhớ cho Header và vị trí (position) của một phần tử trong danh sách có thể định nghĩa như sau: Vị trí của phần tử ai là con trỏ trỏ tới ô chứa ai, tức là địa chỉ ô nhớ chứa ai. Nói nôm na, vị trí của ai là ô chứa ai. Theo định nghĩa vị trí như vậy các phép toán trên danh sách liên kết kép sẽ được cài đặt hơi khác với danh sách liên đơn. Trong cách cài đặt này, chúng ta không sử dụng ô đầu mục như danh sách liên kết đơn mà sẽ quản lý danh sách một các trực tiếp (header chỉ ngay đến ô đầu tiên trong danh sách).

Tạo danh sách liên kết kép rỗng

Giả sử DL là con trỏ quản lí danh sách liên kết kép thì khi khởi tạo danh sách rỗng ta cho con trỏ này trỏ NULL (không cấp phát ô nhớ cho DL), tức là gán DL=NULL.

void MakeNull_List (DoubleList *DL){

(*DL)= NULL;

}

Kiểm tra danh sách liên kết kép rỗng

Rõ ràng, danh sách liên kết kép rỗng khi và chỉ khi chỉ điểm đầu danh sách không trỏ tới một ô xác định nào cả. Do đó ta sẽ kiểm tra DL = NULL.

int Empty (DoubleList DL){

return (DL==NULL);

}

Xóa một phần tử ra khỏi danh sách liên kết kép

Để xoá một phần tử tại vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta phải chú ý đến các trường hợp sau:

• Danh sách rỗng, tức là DL=NULL: chương trình con dừng.
• Trường hợp danh sách khác rỗng, tức là DL!=NULL, ta phải phân biệt hai trường hợp

Ô bị xoá không phải là ô được trỏ bởi DL, ta chỉ cần cập nhật lại các con trỏ để nối kết ô trước p với ô sau p, các thao tác cần thiết là (xem hình II.16):

Nếu (p->previous!=NULL) thì p->previous->next=p->next;

Nếu (p->next!=NULL) thì p->next->previous=p->previous;

Xoá ô đang được trỏ bởi DL, tức là p=DL: ngoài việc cập nhật lại các con trỏ để nối kết các ô trước và sau p ta còn phải cập nhật lại DL, ta có thể cho DL trỏ đến phần tử trước nó (DL = p->Previous) hoặc đến phần tử sau nó (DL = p->Next) tuỳ theo phần tử nào có mặt trong danh sách. Đặc biệt, nếu danh sách chỉ có một phần tử tức là p->Next=NULL và p->Previous=NULL thì DL=NULL.

p->Previous p p->Next

Hình II.16 Xóa phần tử tại vị trí p

void Delete_List (Position p, DoubleList *DL){

if (*DL == NULL) printf(”Danh sach rong”);

else{

if (p==*DL) (*DL)=(*DL)->Next;

//Xóa phần tử đầu tiên của danh sách nên phải thay đổi DL

else p->Previous->Next=p->Next;

if (p->Next!=NULL)

p->Next->Previous=p->Previous; free(p);

}

}

Thêm phần tử vào danh sách liên kết kép

Để thêm một phần tử x vào vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta cũng cần phân biệt mấy trường hợp sau:

Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm đến giá trị của p. Để thêm một phần tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá trị x vào trường Element của ô nhớ này và cho hai con trỏ previous, next trỏ tới NULL còn DL trỏ vào ô nhớ này, các thao tác trên có thể viết như sau:

DL=(Node*)malloc(sizeof(Node));

DL->Element = x;

DL->Previous=NULL;

DL->Next =NULL;

Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình II.18:

Hình II.17: Danh sách trước khi thêm phần tử x

Hình II.18: Danh sách sau khi thêm phần tử x vào tại vị trí p (phần tử tại vị trí p cũ trở thành phần tử "sau" của x).

Lưu ý: các kí hiệu p, p->Next, p->Previous trong hình II.18 để chỉ các ô trước khi thêm phần tử x, tức là nó chỉ các ô trong hình II.17.

Trong trường hợp p=DL, ta có thể cập nhật lại DL để DL trỏ tới ô mới thêm vào hoặc để nó trỏ đến ô tại vị trí p cũ như nó đang trỏ cũng chỉ là sự lựa chọn trong chi tiết cài đặt.

void Insert_List (ElementType X,Position p, DoubleList *DL){

if (*DL == NULL){

(*DL)=(Node*)malloc(sizeof(Node));

(*DL)->Element = X;

(*DL)->Previous =NULL;

(*DL)->Next =NULL;

}

else{

Position temp;

temp=(Node*)malloc(sizeof(Node));

temp->Element=X;

temp->Next=p;

temp->Previous=p->Previous;

if (p->Previous!=NULL)

p->Previous->Next=temp;

p->Previous=temp;

}

}

TỔNG KẾT CHƯƠNG

Chương mô tả các cấu trúc dữ liệu trừu tượng và các giải thuật cài đặt các phép toán này. Tuy nhiên, tùy theo bài toán cụ thể và mức độ thay đổi của dữ liệu cũng mà ta lựa chọn các cấu trúc dữ liệu cho phù hợp. Trong chương này, phần cơ bản nhất là danh sách đặc và liên kết, còn các cấu trúc khác chỉ là sự biến tấu của cấu trúc này. Trong chương này cũng đề cập đến các ứng dụng cụ thể của từng cấu trúc dữ liệu trừu tượng bên ngoài thực tế. Cách cài đặt các cấu trúc dữ liệu trừu tượng khác nhau và có vận dụng cấu trúc đã có để mô tả cho một cấu trúc dữ liệu trừu tượng mới.

» Tiếp: BÀI TẬP « Trước: III. Hàng đợi (QUEUE) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×