Ứng Dụng Danh Sách Liên Kết Kép Quản Lý Sinh Viên Sử Dụng Danh Sách Liên Kết Đơn

Giới thiệu Mở đầu Mảng và nhỏ trỏ Mảng tĩnh Mảng động bé trỏ Sơ đồ bộ nhớ lưu trữ trong các chương trình C Danh sách liên kết cấp phát động Danh sách links đơn Danh sách link kép Cây nhị phân Khái niệm cấu trúc dữ liệu dạng cây Cây nhị phân để mắt tới cây theo chiều rộng Duyệt cây theo chiều sâu Cây tìm kiếm nhị phân Cây tìm kiếm nhị phân Cây cân nặng bằng - AVL Tree Cây cân nặng bằng phòng xếp ngăn xếp Hàng đợi Hàng đợi

Trongbài trước về danh sách liên kết đơn đã đề cập, nó có điểm yếu là chỉ có liên kết tới node kế tiếp mà ko có liên kết tới node đứng trước. Bởi vậy ta luôn phải duyệt toàn bộ danh sách từ node gốc để tìm kiếm dữ liệu tai một vị trí bất kì.

Bạn đang xem: Danh sách liên kết kép quản lý sinh viên

Một node vào danh sách liên kết kép được cấu thành từ cha thành phần là dữ liệu và phần kết nối tới node kế tiếp và node trước nó.

Prev: Là bé trỏ tới node trước.

Next: Là con trỏ tới node kế tiếp.

Xây dựng danh sách liên kết kép bởi liên kết các node với nhau.

Việc chèn dữ liệu trong danh sách liên kết kép

Giả sử trước khi chèn dữ liệu ta có một node riêng rẽ biệt và một danh sách liên kết kép.

Trường hợp ta muốn chèn vào vị trí giữa danh sách liên kết ở trên sẽ được mô tả như sau:

So sánh với danh sách liên kết đơn

Ưu điểm:

Ta có thể duyệt danh sách theo cả nhì chiều bởi vì danh sách liên kết kép có bé trỏ prev để truy nã cập node trước và con trỏ next để truy hỏi cập node sau. Nên những khi muốn tìm kiếm dữ liệu trong danh sách ta không nhất thiết phải duyệt từ đầu danh sách như với danh sách liên kết đơn.

Nhược điểm:

Vì bé trỏ prev được thêm vào mỗi node, như vậy sẽ tốn thêm không khí bộ nhớ. Cách thức hoạt động của danh sách liên kết kép cũng vì vậy mà phức tạp hơn.Xây dựng danh sách liên kết kép với C/C++

Các thành phần của danh sách liên kết kép bao gồm:

Các node: Mỗi node bao gồm phần dữ liệu, một bé trỏ prev để trỏ đến node ngay lập tức trước nó và một nhỏ trỏ next để trỏ tới node ngay tiếp sau nó.

struct node int data; /* Phần dữ liệu của một node */ struct node* next; /* con trỏ tới node kế tiếp */ struct node* prev; /* nhỏ trỏ tới node trước nó */;Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết.struct node * head; /* bé trỏ tới head node */Các thao tác chính với danh sách liên kết kép:

Tạo một node mới và trả về nhỏ trỏ tới node đó

/* Tạo một node mới và trả về bé trỏ tới node đó. */struct node* NewNode(int x) struct node* new_node = (struct node*)malloc(sizeof(struct node)); /* Cấp phát bộ nhớ cho node */ new_node->data = x; new_node->next = NULL; new_node->prev = NULL; return new_node;

Chèn một node vào cuối danh sách

/* Chèn node vào vị trí cuối của danh sách liên kết */void InsertAtEnd(int x) struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp làm cầm cố đổi vị trí trỏ của nhỏ trỏ head */struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần */ /* dữ liệu là tham số được truyền vào */ /* hàm NewNode đã được viết ở trên */if(head == NULL) /* Nếu danh sách rỗng, nhỏ trỏ head sẽ trỏ tới node được chèn vào danh sách */head = new_node;return;while(temp->next != NULL) temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */temp->next = new_node; /* Chèn node mới vào cuối danh sách */ new_node->prev = temp; /* Ghi lại địa chỉ node trước của node vừa chèn vào */

Chèn một node vào đầu danh sách

/* Chèn node vào vị trí cuối của danh sách liên kết */void InsertHead(int x) struct node* new_node = NewNode(x); /* Tạo ra một node mới với phần */ /* dữ liệu là tham số được truyền vào */ /* hàm NewNode đã được viết ở bên trên */if(head == NULL) /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */head = new_node;return;head->prev = new_node ;new_node >next = head; head = new_node ; /* Head lúc này là new_node vì new_node được chèn vào đầu danh sách */

Xóa một phần tử khỏi danh sách liên kết kép

Trong phần này ta có thể tách ra làm nhì hàm riêng rẽ biệt.

Xem thêm: Thanh Lý Cân Trẻ Sơ Sinh Nhơn Hòa Cũ & Mới Cao Cấp Giá Rẻ, Thanh Lý Cân Trẻ Sơ Sinh Nhơn Hòa 20Kg Tại Tphcm

Hàm deleteNode :

Dùng để xóa một node ra khỏi danh sách với điều kiện là ta đã biết địa chỉ của node cần xóa.

Có ba trường hợp mang lại việc xóa node là: xóa node ở vị trí đầu của danh sách, xóa node ở vị trí cuối của danh sách và xóa node ở vị trí giữa của dah sách.

Với việc xóa node ở vị trí đầu, ta chỉ việc chuyển bé trỏ head để trỏ vào vị trí kế tiếp của node đầu tiên và giải phóng bộ nhớ đã cấp mang lại node đầu tiên đó.

Để xóa node ở vị trí cuối cùng của danh sách ta duyệt đến vị trí của node đứng ngay trước node cuối cùng, sau đó gán cho nhỏ trỏ next của node đó trỏ tới NULL và giải phóng bộ nhớ đã cấp mang lại node cuối cùng.

Việc xóa node ở giữa danh sách phức tạp rộng một chút bao gồm các bước:

Chuyển nhỏ trỏ next của node đứng ngay lập tức trước node cần xóa tới vị trí của node ngay lập tức sau node cần xóa đó. Chuyển nhỏ trỏ prev của node đứng tức thì sau node cần xóa về vị trí của node ngay trước node cần xóa đó.Giải phóng bộ nhớ đã cấp đến node vừa xóa.

Hàm delNodeAtPos:

Hàm này được dùng để xóa một node ở một vị trí đã đến trong danh sách.

nhiệm vụ của hàm này là tìm ra địa chỉ của node tại vị trí đã cho, sau đó truyền địa chỉ đó vào hàm deleteNode ở trên.

Các công việc còn lại sẽ do hàm deleteNode đảm nhiệm.

/* Hàm dùng để xóa một node khỏi Doubly Linked List. Head_ref : nhỏ trỏ tới head node. Del : con trỏ tới node cần xóa */void deleteNode(struct node** head_ref, struct node* del) del == NULL) return; /* Nếu node cần xóa là head node */ if (*head_ref == del) *head_ref = del->next; /* nắm đổi node kế tiếp chỉ khi node cần xóa ko phải node cuối cùng vào danh sách */ if (del->next != NULL) del->next->prev = del->prev; /* chũm đổi node trước chỉ lúc node cần xóa ko phải node đầu tiên vào danh sách */ if (del->prev != NULL) del->prev->next = del->next; /* Cuối cùng, giải phóng bộ nhớ đã được chiếm giữ bởi del*/ free(del); /* Hàm để xóa một node ở một vị trí đã cho (int n) trong doubly linked danh sách */void delNodeAtPos(struct node** head_ref, int n) n next; /* Nếu vị trí đã mang đến lớn hớn số node tối nhiều của danh sách, ta thoát khỏi hàm */ if (current == NULL) return; /* Thực hiện việc xóa node mà ta đã tìm thấy tại vị trí đã đến */ deleteNode(head_ref, current);

Hiển thị tất cả các node vào danh sách.

void Display() /* Ta sẽ duyệt từ đầu danh sách, và qua mỗi node ta sẽ in giá trị của node đó ra */struct node* temp = head;while(temp != NULL) printf("%d ",temp->data);temp = temp->next;printf(" ");

Ứng dụng của danh sách liên kết kép trong thực tế

Ta có thể ứng dụng danh sách liên kết kép trong khá nhiều trường hợp, ví dụ:

Trong một phần mềm chơi nhạc có nút next và prev.Trong bộ đệm của trình duyệt web mang lại bạn tảo trở lại trang trước hoặc tới trang kế tiếp.Các phần mềm sử dụng tính năng undo và redo ( MS word, các IDE).