Hỏi đáp

Danh sách liên kết đơn trong C | TopDev

Bạn đang quan tâm đến Danh sách liên kết đơn trong C | TopDev phải không? Nào hãy cùng VCCIDATA đón xem bài viết này ngay sau đây nhé, vì nó vô cùng thú vị và hay đấy!

XEM VIDEO Danh sách liên kết đơn trong C | TopDev tại đây.

danh sách liên kết đơn giản là gì?

danh sách liên kết đơn là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử được liên kết với phần tử chính xác sau nó trong danh sách. mỗi phần tử (được gọi là nút hoặc nút) trong danh sách được liên kết đơn lẻ là một cấu trúc có hai thành phần:

Phần tử dữ liệu

  • : lưu trữ thông tin về chính phần tử đó.
  • phần tử liên kết: lưu địa chỉ của phần tử tiếp theo trong danh sách, nếu phần tử là một phần thì phần tử cuối cùng là null.

tham khảo thêm: việc làm lập trình c ++ lương cao tại topdev

Bạn đang xem: Node trong c++ là gì

Danh sách liên kết đơn trong C++ Minh họa danh sách liên kết đơn

đặc điểm của một danh sách được liên kết đơn lẻ

Vì danh sách được liên kết đơn lẻ là một cấu trúc dữ liệu động được tạo bằng cách gán động, nên nó có các đặc điểm sau:

  • bộ nhớ được cấp phát trong thời gian chạy
  • có thể thay đổi kích thước bằng cách thêm và bớt các phần tử
  • kích thước tối đa phụ thuộc vào tính khả dụng của bộ nhớ ram
  • các phần tử được được lưu trữ ngẫu nhiên (không liên tiếp) trong ram

và do sự liên kết của phần tử đầu tiên và phần tử theo sau nó trong một danh sách được liên kết đơn lẻ, nó có các đặc điểm sau:

  • bạn chỉ cần biết phần tử đầu tiên và cuối cùng để có thể quản lý danh sách
  • quyền truy cập vào phần tử ngẫu nhiên phải đi ngang từ đầu đến vị trí đó
  • chỉ có thể tìm kiếm tuyến tính một phần tử

cấu hình danh sách liên kết đơn

Trước khi chuyển sang triển khai danh sách liên kết đơn, hãy đảm bảo bạn hiểu rõ về con trỏ và phép gán động trong C ++. Vì danh sách liên kết đơn giản là một cấu trúc dữ liệu động, nếu bạn không thành thạo với con trỏ và phép gán động, bạn sẽ khó hiểu được bài viết này. Nếu bạn chưa rõ, hãy dành một chút thời gian để đọc bài viết này của tôi. Và bây giờ hãy bắt đầu!

tạo nút

danh sách liên kết đơn được tạo thành từ nhiều nút, vì vậy trước tiên chúng ta sẽ đi từ nút cùng nhau. Một nút bao gồm hai thành phần, một thành phần dữ liệu và một thành phần liên kết. phần tử dữ liệu có thể là một kiểu dữ liệu dựng sẵn hoặc bạn tự định nghĩa nó (cấu trúc hoặc lớp …), trong bài viết này, để đơn giản, tôi sẽ sử dụng kiểu int cho dữ liệu. phần tử liên kết là một địa chỉ sẽ tự nhiên là một con trỏ, con trỏ này trỏ đến nút tiếp theo, vì vậy con trỏ này là một con trỏ tới một nút.

Để tạo một nút mới, chúng tôi sẽ tự động cấp phát nút mới, khởi tạo nó với giá trị ban đầu và trả về địa chỉ của nút mới được cấp phát.

XEM THÊM:  Tại sao tải zing speed không chơi được

tạo một danh sách được liên kết riêng

Chúng tôi có nút tạo nên danh sách các liên kết riêng lẻ, sau đó chúng tôi cần quản lý chúng bằng cách biết các phần tử đầu tiên và cuối cùng. bởi vì mỗi mục được liên kết với các mục tiếp theo, mô tả chỉ cần biết các mục đầu tiên và cuối cùng để quản lý danh sách này. vì vậy chúng ta chỉ cần tạo một cấu trúc để lưu trữ địa chỉ của phần tử đầu tiên (phần đầu) và phần tử cuối cùng (hoặc phần tử đuôi).

khi chúng tôi tạo danh sách lần đầu tiên, danh sách sẽ không có phần tử nào, vì vậy phần đầu và phần đuôi không trỏ đến bất kỳ đâu, chúng tôi sẽ đặt chúng thành null. chúng tôi xây dựng hàm tạo danh sách như sau:

Xem thêm: Tại sao không có giải nobel toán học

bây giờ để tạo danh sách chúng ta làm như sau:

thêm mục vào danh sách

thêm vào đầu

Để thêm một nút vào đầu danh sách, trước tiên ta cần kiểm tra xem danh sách có trống hay không, nếu danh sách trống thì ta chỉ cần gán phần đầu và phần cuối danh sách cho nút đó. ngược lại, nếu danh sách không trống, chúng tôi trỏ đến phần tử được liên kết với tiêu đề và sau đó gán lại tiêu đề với nút mới.

Danh sách liên kết đơn trong C++ Thêm phần tử vào đầu danh sách liên kết đơn

Như trong hình trên, chúng tôi thêm nút không có dữ liệu vào danh sách. chúng ta trỏ các nút bên cạnh đầu danh sách (là nút đầu tiên trong danh sách có dữ liệu bằng 1), sau đó chúng ta trỏ đầu đến nút có dữ liệu 0 vừa được thêm vào. vì vậy phần tử đó đã ở đầu danh sách.

thêm vào cuối

Tương tự, để thêm một nút vào cuối danh sách, trước tiên ta kiểm tra xem danh sách có trống hay không, nếu trống ta gán head và tail cho nút mới. nếu không trống, chúng tôi trỏ đuôi- & gt; bên cạnh nút mới, sau đó gán lại đuôi với nút mới (vì bây giờ nút mới được thêm vào là đuôi).

Danh sách liên kết đơn trong C++ Thêm phần tử vào cuối danh sách liên kết đơn

Trong hình trên, chúng tôi đã thêm một nút có dữ liệu bằng 6 vào danh sách. tail hiện là nút có dữ liệu 5, gán tail-> next bằng nút mới để thêm vào cuối danh sách, lúc này nút mới trở thành mục cuối cùng trong danh sách nên ta gán lại tail bằng nút mới.

thêm vào sau bất kỳ nút nào

Để thêm một nút p sau bất kỳ nút q nào, trước tiên chúng ta cần kiểm tra xem nút q có rỗng hay không, nếu nút q là null tức là danh sách trống, thì chúng ta sẽ thêm nó vào đầu danh sách. . nếu nút q không rỗng, tức là nó tồn tại trong danh sách, chúng tôi đặt con trỏ p- & gt; next = q- & gt; next, sau đó q- & gt; next = p. sau đó ta kiểm tra xem nút q trước đó có phải là nút cuối cùng hay không, nếu nút q là nút cuối cùng thì thêm p, p sẽ trở thành nút cuối cùng nên ta gán lại tail = p.

XEM THÊM:  Khái niệm khó khăn thử thách là gì

Danh sách liên kết đơn trong C++ Thêm phần tử vào sau nút Q trong danh sách liên kết đơn

Trong hình trên, chúng ta thêm một nút có dữ liệu bằng 4 (nút p) sau nút có dữ liệu bằng 3 (nút q). chúng ta trỏ nút p bên cạnh nút q tiếp theo, tức là nút có dữ liệu bằng 5, sau đó chúng ta trỏ nút q cạnh nút p để nút p được thêm vào danh sách.

xóa mục khỏi danh sách

xóa ở đầu

để loại bỏ phần tử ở đầu danh sách, chúng ta kiểm tra xem danh sách có trống hay không, nếu rỗng thì không cần loại bỏ, nó trả về kết quả 0. nếu danh sách không rỗng thì chúng ta lưu phần đầu một lần nữa, sau đó thiết lập phần đầu với phần đầu của nút cha tiếp theo, sau đó xóa nút cha. tiếp theo chúng ta cần kiểm tra xem danh sách vừa xóa tiêu đề nút có trống hay không, nếu trống chúng ta gán lại hàng đợi với null rồi trả về kết quả 1.

Xem ngay: Nguồn gốc nảy sinh chiến tranh là gì

Lưu ý rằng trước khi xóa nút cha, chúng tôi sử dụng biến tham chiếu x để lưu trữ giá trị của nút đang bị hủy để sử dụng.

Danh sách liên kết đơn trong C++ Xóa phần tử đầu danh sách liên kết đơn

trong hình trên, tôi xóa nút đầu tiên với dữ liệu bằng 0. Tôi trỏ đầu đến nút tiếp theo từ nút 0 (hiện tại là đầu), khi đó đầu bây giờ sẽ là nút 1, sau đó tôi xóa nút 0, nó tốt.

xóa sau bất kỳ nút nào

để loại bỏ một nút p sau một nút q bất kỳ, chúng ta kiểm tra xem nút q có rỗng hay không, nếu nút q là null thì nó không tồn tại trong danh sách, vì vậy nó trả về 0, không loại bỏ nó. nếu nút q không rỗng nhưng nút sau q là null, tức là p là null, đừng loại bỏ nó, trả về 0 (vì sau q không có nút, q là đuôi). nếu nút p tồn tại, chúng tôi kiểm tra xem nút p có phải là hàng đợi hay không, nếu nút p là hàng đợi, sau đó gán lại hàng đợi là q, tức là nút trước đó để loại bỏ nút p.

Trong hình trên, chúng ta xóa nút dữ liệu 3 (nút p) sau nút dữ liệu 2 (nút q). ta trỏ nút q bên cạnh nút p tiếp theo, tức là nút có dữ liệu 4 thì nút p bị xóa.

quét danh sách và in

sau khi thêm và bớt các thao tác, chúng ta có thể in danh sách để kiểm tra xem thao tác đã đúng hay chưa. để in danh sách, chúng tôi lặp lại danh sách từ đầu đến cuối và in nó khi chúng tôi điều hướng. chúng ta phân bổ một nút có đầu, sau đó chúng ta kiểm tra xem nút đó có rỗng hay không, sau đó chúng ta in dữ liệu của nút đó, sau đó chúng ta phân bổ nút đó với nút tiếp theo của chính nó, tức là nút đó bây giờ là nút tiếp theo, cứ tiếp tục như vậy cho đến khi kết thúc.

XEM THÊM:  Tại sao không mở được file

lấy bất kỳ giá trị nút nào

Để nhận giá trị của phần tử trong danh sách, chúng tôi thực hiện thao tác duyệt giống như khi in phần tử. chúng ta sẽ tạo một biến đếm để biết vị trí hiện tại, lặp qua các nút cho đến khi nút rỗng hoặc bộ đếm bằng vị trí của nút cần lấy. kiểm tra xem nút nào không rỗng và bộ đếm bằng vị trí cần lấy thì ta sẽ trả về địa chỉ của nút đó, nếu không sẽ trả về null (hoặc danh sách trống hoặc vị trí cần lấy nằm ngoài phạm vi của danh sách ).

tìm một phần tử trong danh sách

Ý tưởng tìm kiếm một phần tử cũng là để duyệt qua danh sách, nếu bạn không tìm thấy nó, hãy tiếp tục duyệt. sau khi điều hướng xong, chúng ta chỉ cần kiểm tra xem nút điều hướng có rỗng hay không, nếu không có nghĩa là đã tìm thấy, chúng ta sẽ trả về địa chỉ của nút đó.

đếm số phần tử trong danh sách

việc đếm số phần tử cũng tương tự, chúng tôi áp dụng tính năng duyệt từ đầu đến cuối và đếm số lượng nút.

xóa danh sách

Để xóa danh sách, chúng ta cần hủy tất cả các nút, nghĩa là đi ngang và hủy từng nút. ở đây tôi sẽ sử dụng lại hàm removehead. đầu tiên, chúng tôi gán một nút đứng đầu, kiểm tra xem nút đó có phải là null không, sau đó gọi removehead và gán lại nút đứng đầu một lần nữa, và cứ tiếp tục như vậy cho đến khi nút đó là null. sau khi xóa tất cả các phần tử, hãy gán lại đuôi bằng null.

tóm tắt

Vì vậy, trong bài viết này, tôi đã giới thiệu cho bạn các danh sách được liên kết riêng lẻ và một số thao tác cơ bản trên danh sách. bạn không nhất thiết phải làm theo cách của mình, có nhiều cách khác nhau để thực hiện, miễn là bạn hiểu rõ về con trỏ và phép gán động trong c ++. Nếu thấy hay thì đừng quên chia sẻ cho bạn bè cùng biết nhé. cảm ơn vì đã tìm kiếm!

Xem thêm: Cách làm con lật đật hình chú ngựa siêu cute

mã nguồn

Vậy là đến đây bài viết về Danh sách liên kết đơn trong C | TopDev đã dừng lại rồi. Hy vọng bạn luôn theo dõi và đọc những bài viết hay của chúng tôi trên website VCCIDATA.COM.VN

Chúc các bạn luôn gặt hái nhiều thành công trong cuộc sống!

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button