linked list deletion algorithm 9721bbbce61d13dd25e138d628d66ac6 Linked list deletion algorithm

Mục lục

  • Duyệt qua một danh sách được liên kết
  • Chèn các phần tử vào một danh sách được liên kết
    • Chèn một nút vào đầu danh sách được liên kết
      • Thuật toán: InsertAtBeginning
    • Chèn một nút vào cuối danh sách được liên kết
    • Chèn một nút sau một nút nhất định trong danh sách được liên kết
      • Thuật toán: InsertAfterAnElement
  • Xóa các phần tử khỏi danh sách được liên kết
    • Xóa một nút khỏi đầu danh sách được liên kết
      • Thuật toán: DeleteFromBeginning
    • Xóa nút cuối cùng khỏi danh sách được liên kết
    • Xóa Node sau một Node nhất định trong danh sách được Liên kết
      • Thuật toán: DeleteAfterANode
  • Tìm kiếm

Một danh sách liên kết đơn là loại danh sách liên kết đơn giản nhất, với mỗi nút chứa một số dữ liệu cũng như một con trỏ đến nút tiếp theo. Đó là một danh sách được liên kết đơn lẻ chỉ cho phép truyền dữ liệu theo một cách. Có một số hoạt động danh sách liên kết cho phép chúng tôi thực hiện các tác vụ khác nhau.

Các hoạt động cơ bản của danh sách liên kết là:

  • Truyền tải Truy cập các nút của danh sách.
  • Chèn Thêm một nút mới vào danh sách liên kết hiện có.
  • Xóa Xóa một nút khỏi danh sách liên kết hiện có.
  • Tìm kiếm Tìm một phần tử cụ thể trong danh sách được liên kết.

Duyệt qua một danh sách được liên kết

Việc truy cập các nút của danh sách được liên kết để xử lý nó được gọi là đi ngang qua một danh sách được liên kết. Thông thường, chúng tôi sử dụng thao tác duyệt để hiển thị nội dung hoặc tìm kiếm một phần tử trong danh sách được liên kết. Thuật toán để duyệt qua danh sách được liên kết được đưa ra bên dưới.

Thuật toán: Traverse

Bước 1: [INITIALIZE] SET PTR = HEAD Bước 2: Lặp lại Bước 3 và 4 trong khi PTR! = NULL Bước 3: Áp dụng quy trình cho PTR -> DATA Bước 4: ĐẶT PTR = PTR-> NEXT
[END OF LOOP]
Bước 5: THOÁT

  • Đầu tiên chúng ta khởi tạo PTR với địa chỉ của HEAD. Bây giờ PTR trỏ đến nút đầu tiên của danh sách được liên kết.
  • Một vòng lặp while được thực hiện và hoạt động được tiếp tục cho đến khi PTR đến nút cuối cùng (PTR = NULL).
  • Áp dụng quy trình (hiển thị) cho nút hiện tại.
  • Di chuyển đến nút tiếp theo bằng cách chuyển giá trị của PTR đến địa chỉ của nút tiếp theo.

Khối mã sau in tất cả các phần tử trong danh sách liên kết trong C.

nút struct * ptr = head; printf (“Các phần tử trong danh sách liên kết là:”); while (ptr! = NULL) {printf (“% d”, ptr-> data); ptr = ptr-> tiếp theo; }

Chèn các phần tử vào một danh sách được liên kết

Chúng ta sẽ xem cách một nút mới có thể được thêm vào danh sách liên kết hiện có trong các trường hợp sau.

  1. Nút mới được chèn vào lúc đầu.
  2. Nút mới được chèn vào cuối.
  3. Nút mới được chèn sau một nút nhất định.

Chèn một nút vào đầu danh sách được liên kết

Hãy xem xét danh sách liên kết được hiển thị trong hình. Giả sử chúng ta muốn tạo một nút mới với dữ liệu 24 và thêm nó làm nút đầu tiên của danh sách. Danh sách liên kết sẽ được sửa đổi như sau.

linked list deletion algorithm 9721bbbce61d13dd25e138d628d66ac6 Linked list deletion algorithm
inserting an element in the beginning of a linked list 1 Linked list deletion algorithm
  • Phân bổ bộ nhớ cho nút mới và khởi tạo phần DATA của nó thành 24.
  • Thêm nút mới làm nút đầu tiên của danh sách bằng cách trỏ phần TIẾP THEO của nút mới đến HEAD.
  • Làm cho HEAD trỏ đến nút đầu tiên của danh sách.

Thuật toán: InsertAtBeginning

Bước 1: IF AVAIL = NULL Ghi OVERFLOW Đi đến Bước 7
[END OF IF]
Bước 2: SET NEW_NODE = AVAIL Bước 3: SET AVAIL = AVAIL -> NEXT Bước 4: SET NEW_NODE -> DATA = VAL Bước 5: SET NEW_NODE -> NEXT = HEAD Bước 6: SET HEAD = NEW_NODE Bước 7: THOÁT

Lưu ý rằng bước đầu tiên của thuật toán kiểm tra xem có đủ bộ nhớ để tạo một nút mới hay không. Bước thứ hai và thứ ba cấp phát bộ nhớ cho nút mới.

Thuật toán này có thể được thực hiện trong C như sau:

nút cấu trúc * new_node; new_node = (struct node *) malloc (sizeof (struct node)); new_node-> data = 24; new_node-> next = head; head = new_node;

Chèn một nút vào cuối danh sách được liên kết

Hãy xem danh sách liên kết trong hình. Giả sử chúng ta muốn thêm một nút mới với dữ liệu 24 là nút cuối cùng của danh sách. Sau đó, danh sách liên kết sẽ được sửa đổi như sau.

inserting an element in the end of a linked list Linked list deletion algorithm
inserting an element in the end of a linked list Linked list deletion algorithm
  • Phân bổ bộ nhớ cho nút mới và khởi tạo phần DATA của nó thành 24.
  • Đi ngang đến nút cuối cùng.
  • Trỏ phần TIẾP THEO của nút cuối cùng đến nút mới được tạo.
  • Đặt giá trị của phần tiếp theo của nút cuối cùng thành NULL.

Thuật toán: InsertAtEnd

Bước 1: IF AVAIL = NULL Ghi OVERFLOW Chuyển đến Bước 10
[END OF IF]
Bước 2: SET NEW_NODE = AVAIL Bước 3: SET AVAIL = AVAIL -> NEXT Bước 4: SET NEW_NODE -> DATA = VAL Bước 5: SET NEW_NODE -> NEXT = NULL Bước 6: SET PTR = HEAD Bước 7: Lặp lại Bước 8 while PTR -> NEXT! = NULL Bước 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Bước 9: THIẾT LẬP PTR -> NEXT = NEW_NODE Bước 10: THOÁT

Điều này có thể được thực hiện trong C như sau,

nút cấu trúc * new_node; new_node = (struct node *) malloc (sizeof (struct node)); new_node-> data = 24; new_node-> next = NULL; nút struct * ptr = head; while (ptr-> next! = NULL) {ptr = ptr-> next; } ptr-> next = new_node;

Chèn một nút sau một nút nhất định trong danh sách được liên kết

Trường hợp cuối cùng là khi chúng ta muốn thêm một nút mới sau một nút nhất định. Giả sử chúng ta muốn thêm một nút mới với giá trị 24 sau khi nút có dữ liệu 9. Những thay đổi này sẽ được thực hiện trong danh sách liên kết.

inserting an element after an element in a linked list 1 Linked list deletion algorithm
inserting an element after an element in a linked list 1 Linked list deletion algorithm
  • Phân bổ bộ nhớ cho nút mới và khởi tạo phần DATA của nó thành 24.
  • Duyệt qua danh sách cho đến khi đạt đến nút được chỉ định.
  • Thay đổi con trỏ NEXT cho phù hợp.

Thuật toán: InsertAfterAnElement

Bước 1: IF AVAIL = NULL Ghi OVERFLOW Đi đến Bước 12
[END OF IF]
Bước 2: SET NEW_NODE = AVAIL Bước 3: SET AVAIL = AVAIL -> NEXT Bước 4: SET NEW_NODE -> DATA = VAL Bước 5: SET PTR = HEAD Bước 6: SET PREPTR = PTR Bước 7: Lặp lại các bước 8 và 9 trong khi PREPTR -> DATA! = NUM ​​Bước 8: ĐẶT PREPTR = PTR Bước 9: ĐẶT PTR = PTR -> NEXT
[END OF LOOP]
Bước 1: PREPTR -> NEXT = NEW_NODE Bước 11: SET NEW_NODE -> NEXT = PTR Bước 12: EXIT

Xóa các phần tử khỏi danh sách được liên kết

Hãy thảo luận về cách một nút có thể bị xóa khỏi một liên kết được liệt kê trong các trường hợp sau.

  1. Nút đầu tiên bị xóa.
  2. Nút cuối cùng bị xóa.
  3. Nút sau khi một nút nhất định bị xóa.

Xóa một nút khỏi đầu danh sách được liên kết

Giả sử chúng ta muốn xóa một nút khỏi đầu danh sách liên kết. Danh sách phải được sửa đổi như sau:

deleting first node of a linked list 1 Linked list deletion algorithm
deleting first node of a linked list 1 Linked list deletion algorithm
  • Kiểm tra xem danh sách liên kết có trống hay không. Thoát nếu danh sách trống.
  • Làm cho HEAD trỏ đến nút thứ hai.
  • Giải phóng nút đầu tiên khỏi bộ nhớ.

Thuật toán: DeleteFromBeginning

Bước 1: NẾU HEAD = NULL Viết UNDERFLOW Đi đến Bước 5
[END OF IF]
Bước 2: ĐẶT PTR = HEAD Bước 3: ĐẶT ĐẦU = ĐẦU -> TIẾP THEO Bước 4: MIỄN PHÍ PTR Bước 5: THOÁT

Điều này có thể được thực hiện trong C như sau,

if (head == NULL) {printf (“Dòng dưới”); } else {ptr = head; head = đầu -> tiếp theo; miễn phí (ptr); }

Xóa nút cuối cùng khỏi danh sách được liên kết

Giả sử chúng ta muốn xóa nút cuối cùng khỏi danh sách liên kết. Danh sách liên kết phải được sửa đổi như sau:

deleting last node from a linked list Linked list deletion algorithm
deleting last node from a linked list Linked list deletion algorithm
  • Di chuyển đến cuối danh sách.
  • Thay đổi giá trị của con trỏ tiếp theo của nút cuối cùng thứ hai thành NULL.
  • Giải phóng nút cuối cùng khỏi bộ nhớ.

Thuật toán: DeleteFromEnd

Bước 1: NẾU HEAD = NULL Viết UNDERFLOW Chuyển đến Bước 8
[END OF IF]
Bước 2: Đặt PTR = HEAD Bước 3: Lặp lại các bước 4 và 5 trong khi PTR -> NEXT! = NULL Bước 4: ĐẶT PREPTR = PTR Bước 5: ĐẶT PTR = PTR -> NEXT
[END OF LOOP]
Bước 6: ĐẶT PREPTR -> NEXT = NULL Bước 7: PTR MIỄN PHÍ Bước 8: THOÁT

Ở đây chúng ta sử dụng hai con trỏ PTR và PREPTR để truy cập vào nút cuối cùng và nút cuối cùng thứ hai. Điều này có thể được thực hiện trong C như sau,

if (head == NULL) {printf (“Dòng dưới”); } else {struct node * ptr = head; nút cấu trúc * preptr = NULL; while (ptr-> next! = NULL) {preptr = ptr; ptr = ptr-> tiếp theo; } preptr-> tiếp theo = NULL; miễn phí (ptr); }

Xóa Node sau một Node nhất định trong danh sách được Liên kết

Giả sử chúng ta muốn xóa đi sau nút chứa dữ liệu 9.

deleting the node after a given node in a linked list Linked list deletion algorithm
deleting the node after a given node in a linked list Linked list deletion algorithm
  • Đảo danh sách lên nút được chỉ định.
  • Thay đổi giá trị của con trỏ tiếp theo của nút trước (9) thành con trỏ tiếp theo của nút hiện tại (10).

Thuật toán: DeleteAfterANode

Bước 1: NẾU HEAD = NULL Viết UNDERFLOW Chuyển đến Bước 10
[END OF IF]
Bước 2: ĐẶT PTR = HEAD Bước 3: ĐẶT PREPTR = PTR Bước 4: Lặp lại các bước 5 và 6 trong khi PREPTR -> DATA! = NUM ​​Bước 5: ĐẶT PREPTR = PTR Bước 6: ĐẶT PTR = PTR -> TIẾP THEO
[END OF LOOP]
Bước 7: ĐẶT TEMP = PTR Bước 8: ĐẶT TRƯỚC -> TIẾP THEO = PTR -> TIẾP THEO Bước 9: TEMP MIỄN PHÍ Bước 10: Thoát

Việc triển khai trong C có dạng sau:

if (head == NULL) {printf (“Dòng dưới”); } else {struct node * ptr = head; nút struct * preptr = ptr; while (ptr-> data! = num) {preptr = ptr; ptr = ptr-> tiếp theo; } struct node * temp = ptr; preptr -> tiếp theo = ptr -> tiếp theo; miễn phí (tạm thời); }

Tìm kiếm

Tìm một phần tử tương tự như một phép toán duyệt. Thay vì hiển thị dữ liệu, chúng tôi phải kiểm tra xem dữ liệu có khớp với mục để tìm.

  • Khởi tạo PTR với địa chỉ của HEAD. Bây giờ PTR trỏ đến nút đầu tiên của danh sách được liên kết.
  • Một vòng lặp while được thực thi sẽ so sánh dữ liệu của mọi nút với mục.
  • Nếu mục đã được tìm thấy thì kiểm soát sẽ chuyển sang bước cuối cùng.

Thuật toán: Tìm kiếm

Bước 1: [INITIALIZE] SET PTR = HEAD Bước 2: Lặp lại Bước 3 và 4 trong khi PTR! = NULL Bước 3: Nếu ITEM = PTR -> DATA SET POS = PTR Chuyển đến Bước 5 ELSE SET PTR = PTR -> NEXT
[END OF IF]
[END OF LOOP]

Bước 4: ĐẶT POS = NULL Bước 5: THOÁT

Hoạt động tìm kiếm có thể được thực hiện trong C như sau:

nút struct * ptr = head; nút struct * pos = NULL; while (ptr! = NULL) {if (ptr-> data == item) pos = ptr printf (“Phần tử Tìm thấy”); phá vỡ; else ptr = ptr -> tiếp theo; }

Bạn đang xem chuyên mục Hỏi đáp
Thuộc website web giải đáp

Quảng cáo

Trả lời

Email của bạn sẽ không được hiển thị công khai.