Danh sách liên kết tròn: Ưu điểm với Ví dụ về chương trình C

Mục lục:

Anonim

Danh sách liên kết theo vòng tròn là gì?

Danh sách liên kết vòng tròn là một chuỗi các nút được sắp xếp theo cách mà mỗi nút có thể được truy xuất lại về chính nó. Ở đây "nút" là một phần tử tự tham chiếu với các con trỏ đến một hoặc hai nút trong vùng lân cận của iI.

Dưới đây là mô tả của một danh sách liên kết hình tròn với 3 nút.

Tại đây, bạn có thể thấy rằng mỗi nút có thể truy xuất lại cho chính nó. Ví dụ được hiển thị ở trên là một danh sách được liên kết đơn lẻ.

Lưu ý: Danh sách liên kết hình tròn đơn giản nhất, là một nút chỉ theo dõi chính nó như được hiển thị

Trong hướng dẫn danh sách liên kết vòng tròn này, bạn sẽ học:

  • Danh sách liên kết theo vòng tròn là gì?
  • Hoạt động cơ bản
  • Thao tác chèn
  • Thao tác xóa
  • Duyệt qua một danh sách được liên kết theo vòng tròn
  • Ưu điểm của danh sách liên kết theo vòng tròn
  • Danh sách được liên kết đơn lẻ dưới dạng Danh sách được liên kết theo vòng tròn
  • Các ứng dụng của Danh sách Liên kết Thông tư

Hoạt động cơ bản

Các thao tác cơ bản trên danh sách liên kết vòng là:

  1. Chèn
  2. Xóa và
  3. Traversal
  • Chèn là quá trình đặt một nút tại một vị trí xác định trong danh sách liên kết vòng.
  • Xóa là quá trình xóa một nút hiện có khỏi danh sách được liên kết. Nút có thể được xác định bằng sự xuất hiện của giá trị hoặc vị trí của nó.
  • Duyệt qua danh sách được liên kết vòng tròn là quá trình hiển thị toàn bộ nội dung của danh sách được liên kết và quay trở lại nút nguồn.

Trong phần tiếp theo, bạn sẽ hiểu việc chèn một nút và các kiểu chèn có thể có trong Danh sách liên kết đơn lẻ.

Thao tác chèn

Ban đầu, bạn cần tạo một nút trỏ đến chính nó như thể hiện trong hình ảnh này. Nếu không có nút này, việc chèn sẽ tạo ra nút đầu tiên.

Tiếp theo, có hai khả năng:

  • Chèn ở vị trí hiện tại của danh sách liên kết vòng tròn. Điều này tương ứng với việc chèn vào đầu cuối của danh sách liên kết số ít thông thường. Trong danh sách liên kết vòng tròn, phần đầu và phần cuối giống nhau.
  • Chèn sau một nút được lập chỉ mục. Nút phải được xác định bằng một số chỉ mục tương ứng với giá trị phần tử của nó.

Để chèn vào đầu / cuối danh sách liên kết vòng tròn, tức là ở vị trí mà nút đầu tiên được thêm vào,

  • Bạn sẽ phải phá vỡ liên kết tự hiện có với nút hiện có
  • Con trỏ tiếp theo của nút mới sẽ liên kết với nút hiện có.
  • Con trỏ tiếp theo của nút cuối cùng sẽ trỏ đến nút được chèn.

LƯU Ý: Con trỏ là mã thông báo chính hoặc đầu / cuối của vòng tròn có thể được thay đổi. Nó sẽ vẫn quay trở lại cùng một nút trên một đường truyền, đã được thảo luận ở phần trước.

Các bước trong (a) i-iii được trình bày dưới đây:

(Nút hiện có)

BƯỚC 1) Phá vỡ liên kết hiện có

BƯỚC 2) Tạo liên kết chuyển tiếp (từ nút mới đến nút hiện có)

BƯỚC 3) Tạo liên kết vòng lặp đến nút đầu tiên

Tiếp theo, bạn sẽ thử chèn sau một nút.

Ví dụ: chúng ta hãy chèn "VALUE2" sau nút có "VALUE0". Giả sử rằng điểm bắt đầu là nút có "VALUE0".

  • Bạn sẽ phải ngắt dòng giữa nút đầu tiên và nút thứ hai và đặt nút có "VALUE2" ở giữa.
  • Con trỏ tiếp theo của nút đầu tiên phải liên kết với nút này và con trỏ tiếp theo của nút này phải liên kết với nút thứ hai trước đó.
  • Phần còn lại của sự sắp xếp vẫn không thay đổi. Tất cả các nút đều có thể truy xuất lại chính nó.

LƯU Ý: Vì có một sự sắp xếp theo chu kỳ, việc chèn một nút bao gồm cùng một quy trình cho bất kỳ nút nào. Con trỏ hoàn thành một chu trình sẽ hoàn thành chu trình giống như bất kỳ nút nào khác.

Điều này được hiển thị bên dưới:

(Hãy để chúng tôi nói rằng chỉ có hai nút. Đây là một trường hợp nhỏ)

BƯỚC 1) Loại bỏ liên kết bên trong giữa các nút được kết nối

BƯỚC 2) Kết nối nút bên trái với nút mới

BƯỚC 3) Kết nối nút mới với nút bên tay phải.

Thao tác xóa

Hãy giả sử một danh sách liên kết vòng tròn 3 nút. Các trường hợp xóa được đưa ra dưới đây:

  • Xóa phần tử hiện tại
  • Xóa sau một phần tử.

Xóa ở đầu / cuối:

  1. Đi qua nút đầu tiên từ nút cuối cùng.
  2. Để xóa từ cuối, chỉ nên có một bước duyệt, từ nút cuối cùng đến nút đầu tiên.
  3. Xóa liên kết giữa nút cuối cùng và nút tiếp theo.
  4. Liên kết nút cuối cùng với phần tử tiếp theo của nút đầu tiên.
  5. Giải phóng nút đầu tiên.

(Thiết lập hiện tại)

BƯỚC 1 ) Xóa liên kết vòng tròn

CÁC BƯỚC 2) Xóa liên kết giữa nút đầu tiên và nút tiếp theo, liên kết nút cuối cùng, với nút sau nút đầu tiên

BƯỚC 3) Giải phóng / phân bổ nút đầu tiên

Xóa sau một nút:

  1. Đi ngang cho đến khi nút tiếp theo là nút bị xóa.
  2. Di chuyển đến nút tiếp theo, đặt một con trỏ trên nút trước đó.
  3. Kết nối nút trước với nút sau nút hiện tại, sử dụng con trỏ tiếp theo của nó.
  4. Giải phóng nút hiện tại (đã xóa liên kết).

BƯỚC 1) Giả sử rằng chúng ta cần xóa một nút có "VALUE1".

BƯỚC 2) Xóa liên kết giữa nút trước và nút hiện tại. Liên kết nút trước của nó với nút tiếp theo được trỏ bởi nút hiện tại (với VALUE1).

BƯỚC 3) Giải phóng hoặc phân bổ nút hiện tại.

Duyệt qua một danh sách được liên kết theo vòng tròn

Để duyệt qua danh sách liên kết vòng tròn, bắt đầu từ con trỏ cuối cùng, hãy kiểm tra xem bản thân con trỏ cuối cùng có phải là NULL hay không. Nếu điều kiện này sai, hãy kiểm tra xem chỉ có một phần tử. Nếu không, hãy di chuyển bằng con trỏ tạm thời cho đến khi con trỏ cuối cùng được tiếp cận hoặc nhiều lần nếu cần, như được hiển thị trong GIF bên dưới.

Ưu điểm của danh sách liên kết theo vòng tròn

Một số ưu điểm của danh sách liên kết vòng là:

  1. Không yêu cầu chỉ định NULL trong mã. Danh sách vòng tròn không bao giờ trỏ đến một con trỏ NULL trừ khi được phân bổ hoàn toàn.
  2. Danh sách liên kết tròn có lợi cho các hoạt động cuối cùng vì đầu và cuối trùng nhau. Các thuật toán như lập lịch Round Robin có thể loại bỏ gọn gàng các quy trình được xếp hàng đợi theo kiểu vòng tròn mà không gặp phải các con trỏ treo lơ lửng hoặc con trỏ tham chiếu NULL.
  3. Danh sách liên kết tròn cũng thực hiện tất cả các chức năng thông thường của danh sách liên kết đơn lẻ. Trên thực tế, các danh sách được liên kết kép theo vòng tròn được thảo luận dưới đây thậm chí có thể loại bỏ nhu cầu truyền tải có độ dài đầy đủ để xác định vị trí một phần tử. Phần tử đó sẽ chỉ hoàn toàn ngược lại với phần đầu, chỉ hoàn thành một nửa danh sách được liên kết.

Danh sách được liên kết đơn lẻ dưới dạng danh sách được liên kết theo vòng tròn

Bạn được khuyến khích cố gắng đọc và triển khai mã bên dưới. Nó trình bày số học con trỏ liên kết với danh sách liên kết vòng tròn.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Giải thích mã:

  1. Hai dòng mã đầu tiên là các tệp tiêu đề bao gồm cần thiết.
  2. Phần tiếp theo mô tả cấu trúc của mỗi nút tự tham chiếu. Nó chứa một giá trị và một con trỏ cùng kiểu với cấu trúc.
  3. Mỗi cấu trúc liên kết nhiều lần với các đối tượng cấu trúc cùng loại.
  4. Có các nguyên mẫu chức năng khác nhau cho:
    1. Thêm một phần tử vào danh sách liên kết trống
    2. Chèn vào vị trí hiện được trỏ của danh sách liên kết hình tròn.
    3. Chèn sau một giá trị được lập chỉ mục cụ thể trong danh sách được liên kết.
    4. Xóa / Xóa sau một giá trị được lập chỉ mục cụ thể trong danh sách được liên kết.
    5. Xóa ở vị trí hiện được trỏ của danh sách liên kết vòng tròn
  5. Hàm cuối cùng in từng phần tử thông qua một đường truyền tròn ở bất kỳ trạng thái nào của danh sách được liên kết.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Giải thích mã:

  1. Đối với mã addEmpty, hãy phân bổ một nút trống bằng cách sử dụng hàm malloc.
  2. Đối với nút này, hãy đặt dữ liệu vào biến tạm thời.
  3. Gán và liên kết biến duy nhất với biến tạm thời
  4. Trả lại phần tử cuối cùng về ngữ cảnh chính () / ứng dụng.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Giải thích mã

  1. Nếu không có phần tử nào để chèn, thì bạn nên đảm bảo thêm vào danh sách trống và trả lại quyền điều khiển.
  2. Tạo một phần tử tạm thời để đặt sau phần tử hiện tại.
  3. Liên kết các con trỏ như được hiển thị.
  4. Trả lại con trỏ cuối cùng như trong hàm trước đó.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Giải thích mã:

  1. Nếu không có phần tử nào trong danh sách, hãy bỏ qua dữ liệu, thêm mục hiện tại làm mục cuối cùng trong danh sách và trả lại quyền điều khiển
  2. Đối với mỗi lần lặp trong vòng lặp do-while, hãy đảm bảo rằng có một con trỏ trước đó giữ kết quả được duyệt qua cuối cùng.
  3. Chỉ sau đó mới có thể xảy ra chuyển tiếp tiếp theo.
  4. Nếu dữ liệu được tìm thấy hoặc tạm thời quay trở lại con trỏ cuối cùng, do-while kết thúc. Phần tiếp theo của mã quyết định những gì phải được thực hiện với mục.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Giải thích mã:

  1. Nếu toàn bộ danh sách đã được duyệt qua, nhưng mục không được tìm thấy, hãy hiển thị thông báo "không tìm thấy mục" và sau đó trả lại quyền kiểm soát cho người gọi.
  2. Nếu có một nút được tìm thấy và / hoặc nút chưa phải là nút cuối cùng, thì hãy tạo một nút mới.
  3. Liên kết nút trước với nút mới. Liên kết nút hiện tại với tạm thời (biến truyền tải).
  4. Điều này đảm bảo rằng phần tử được đặt sau một nút cụ thể trong danh sách liên kết vòng tròn. Quay lại người gọi.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Giải thích mã

  1. Để chỉ xóa nút cuối cùng (hiện tại), hãy kiểm tra xem danh sách này có trống không. Nếu đúng như vậy, thì không có phần tử nào có thể bị xóa.
  2. Biến tạm thời chỉ chuyển tiếp một liên kết.
  3. Liên kết con trỏ cuối cùng với con trỏ sau con trỏ đầu tiên.
  4. Giải phóng con trỏ tạm thời. Nó phân bổ con trỏ cuối cùng chưa được liên kết.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Giải thích mã

  1. Như với chức năng loại bỏ trước đó, hãy kiểm tra xem không có phần tử nào. Nếu điều này là đúng, thì không có phần tử nào có thể bị loại bỏ.
  2. Các con trỏ được chỉ định các vị trí cụ thể để xác định vị trí của phần tử sẽ bị xóa.
  3. Các con trỏ được nâng cao, cái này đi sau cái kia. (thắng sau tạm thời)
  4. Quá trình tiếp tục cho đến khi một phần tử được tìm thấy hoặc phần tử tiếp theo quay trở lại con trỏ cuối cùng.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Giải thích chương trình

  1. Nếu phần tử được tìm thấy sau khi duyệt qua toàn bộ danh sách được liên kết, một thông báo lỗi sẽ hiển thị cho biết không tìm thấy mục.
  2. Nếu không, phần tử sẽ được xóa và giải phóng ở bước 3 và 4.
  3. Con trỏ trước đó được liên kết với địa chỉ được chỉ ra là "tiếp theo" bởi phần tử cần xóa (tạm thời).
  4. Con trỏ tạm thời do đó được phân bổ và giải phóng.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Giải thích mã

  1. Không thể nhìn trộm hoặc duyệt qua nếu không có số 0 cần thiết. Người dùng cần phân bổ hoặc chèn một nút.
  2. Nếu chỉ có một nút thì không cần duyệt, nội dung của nút có thể được in ra, và vòng lặp while không thực thi.
  3. Nếu có nhiều hơn một nút, thì tạm thời sẽ in tất cả các mục cho đến phần tử cuối cùng.
  4. Thời điểm đạt đến phần tử cuối cùng, vòng lặp kết thúc và hàm trả về lời gọi hàm chính.

Các ứng dụng của Danh sách Liên kết Thông tư

  • Thực hiện lập lịch vòng tròn trong các quy trình hệ thống và lập lịch vòng tròn trong đồ họa tốc độ cao.
  • Mã thông báo đổ chuông lập lịch trong mạng máy tính.
  • Nó được sử dụng trong các đơn vị hiển thị như bảng cửa hàng yêu cầu truyền dữ liệu liên tục.