Bạn biết bao nhiêu về danh sách được liên kết đơn lẻ (danh sách được liên kết) trong c ++? Đặc điểm là gì? Cách cài đặt danh sách liên kết c ++ và các bài tập liên quan. Hãy cùng techacademy tìm hiểu trong bài viết này nhé!
Tôi. Danh sách liên kết c ++ là gì
Danh sách được liên kết là một chuỗi các cấu trúc dữ liệu được liên kết với nhau bằng các liên kết. Nói một cách dễ hiểu, danh sách liên kết là một cấu trúc dữ liệu bao gồm một tập hợp các nút tạo thành một chuỗi. Mỗi nút chứa dữ liệu của nút đó và một tham chiếu đến nút tiếp theo trong chuỗi.
Danh sách được liên kết là cấu trúc dữ liệu được sử dụng rộng rãi thứ hai sau mảng. Dưới đây là các định nghĩa cơ bản liên quan đến danh sách được liên kết:
Liên kết: Mỗi liên kết của danh sách được liên kết có thể lưu trữ một phần dữ liệu được gọi là phần tử.
tiếp theo: Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết tiếp theo có tên là next.
đầu tiên: Danh sách các liên kết chứa các liên kết đến liên kết đầu tiên của liên kết đầu tiên.
Thứ hai. Các tính năng của danh sách liên kết đơn
Vì danh sách được liên kết đơn lẻ là cấu trúc dữ liệu động được tạo bằng cách phân bổ động, nên nó có các đặc điểm sau:
- Phân bổ bộ nhớ trong thời gian chạy
- 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 bộ nhớ khả dụng trong bộ nhớ
- Các phần tử được lưu trữ tự nhiên (không -liên tục) trong bộ nhớ
Và do sự liên kết giữa phần tử đầu tiên trong danh sách được liên kết đơn lẻ và các phần tử sau nó, nó có các đặc điểm sau:
- Chỉ cần biết phần tử đầu tiên và phần tử cuối cùng để quản lý danh sách
- Để truy cập một phần tử ngẫu nhiên, người ta phải truy cập vào vị trí đó ngay từ đầu
- Chỉ một phần tử có thể được tìm kiếm tuyến tính
III. Cài Đặt Linked List C++
+ Danh sách khai báo
Để đơn giản, dữ liệu của chúng tôi sẽ là số nguyên (int). Bạn cũng có thể sử dụng các kiểu nguyên thủy khác (float, char, …) hoặc kiểu dữ liệu struct (sinhvien, canbo, …) của riêng bạn.
Câu lệnh trên sẽ được sử dụng cho hầu hết các nút trong danh sách được liên kết. Trường dữ liệu sẽ lưu trữ giá trị và tiếp theo sẽ là một con trỏ đến giá trị tiếp theo.
Tại sao tiếp theo là loại danh sách liên kết của riêng nó? Vì nó là con trỏ của chính nó, nó trỏ đến nút tiếp theo cũng thuộc loại danh sách liên kết.
+ Tạo một nút mới
Hãy tạo loại dữ liệu danh sách liên kết để làm cho mã rõ ràng hơn:
Mỗi nút được khởi tạo, chúng ta cần cấp phát bộ nhớ cho nó, theo mặc định, con trỏ tiếp theo trỏ đến null. Giá trị nút được cung cấp khi các nút được thêm vào danh sách liên kết.
- typedef được sử dụng để định nghĩa các kiểu dữ liệu trong c. vd: typeder long long ll;
- malloc là hàm cấp phát bộ nhớ của c. Trong c ++, chúng tôi sử dụng new
- sizeof là một hàm trả về kích thước của một kiểu dữ liệu và được sử dụng làm đối số cho hàm malloc
Lưu ý: Không giống như mảng, arr [size] cần được khai báo. Trong một danh sách liên kết, vì mỗi nút sẽ có một con trỏ đến nút tiếp theo. Vì vậy, đối với một danh sách liên kết đơn, chỉ nút đầu tiên (đầu) cần được giữ lại. Nếu bạn có người đứng đầu, thì bạn có thể đi đến bất kỳ nút nào.
+ Thêm nút vào danh sách được liên kết
Thêm vào Bắt đầu
Thêm vào tiêu đề đang cập nhật tiêu đề. Chúng tôi gọi nút mới (tạm thời) và chúng tôi có:
-Nếu head trỏ đến null, điều đó có nghĩa là danh sách được liên kết trống và nút mới được thêm vào cũng ở đầu
– Nếu không, chúng tôi phải thay thế tiêu đề cũ bằng tiêu đề mới. Việc này phải được thực hiện theo trình tự sau:
- trỏ tới tiêu đề hiện tại để xem tạm thời tiếp theo
- đặt nhiệt độ cho tiêu đề mới
Thêm vào cuối
Chúng tôi cần nút đầu tiên và giá trị chúng tôi muốn thêm. Sau đó, chúng tôi sẽ:
- Tạo một nút mới với giá trị
- Nếu head = null, danh sách liên kết trống. Sau đó, nút mới (tạm thời) sẽ ở đầu.
- Nếu không, chúng tôi đi qua nút cuối cùng (có next = null) và trỏ người cuối cùng đến bên cạnh nút mới (tạm thời).
Tổng quát hơn, chúng tôi sẽ viết một hàm thêm một nút vào một vị trí tùy ý.
Thêm vào bất kỳ đâu
Để thực hiện việc này, chúng ta cần xem qua từ đầu để tìm vị trí của nút cần chèn, ví dụ như nút q, sau đó chúng ta cần thực hiện như sau:
- nút tiếp theo đối với nút mới trỏ đến nút được chỉ đến bởi nút q
- đối với nút q trỏ tới nút mới
Lưu ý: Chèn chỉ mục bắt đầu từ chỉ mục 0
Lưu ý: Nếu bạn cung cấp p-> next = temp trước, thứ tự trên phải được tuân theo. Khi đó bạn sẽ không thể lấy lại phần tiếp theo của danh sách liên kết (vì next chỉ được lưu trong p-> next, nếu bạn thay đổi p-> next thì nó sẽ không có giá trị cũ).
+ Xóa nút khỏi danh sách được liên kết
Xóa đầu
Loại bỏ cái đầu thật dễ dàng, bây giờ chỉ cần làm cho người bên cạnh cái đầu trở thành cái đầu. nơi đầu tiếp theo là đầu-> tiếp theo.
Xóa lần cuối
Xóa người cuối cùng là một công việc khó khăn, thật khó để duyệt đến người cuối cùng – 1 vì người cuối cùng – 1 trống.
Nút cuối cùng – 1 là nút trong đó p-> next-> next = null. Bạn đặt nó bên cạnh null và bạn đã hoàn tất.
Xóa mọi nơi
Xóa bất kỳ đâu gần giống như xóa đầu bên kia. Chúng tôi chỉ bỏ qua một phần tử, như được hiển thị bên dưới:
Lưu ý: Việc xóa chỉ mục bắt đầu với 0 người. Tìm nơi xóa chỉ duyệt đến nút gần cuối (end – 1). Đây là mã để xóa nút ở bất kỳ đâu
+ Nhận giá trị ở mọi nơi
Chúng tôi sẽ viết một hàm để lấy giá trị tại bất kỳ chỉ mục nào. Nếu chỉ mục vượt quá độ dài của danh sách liên kết – 1, hàm này trả về vị trí cuối cùng. Do các giới hạn, chúng tôi không thể đưa ra lỗi khi chỉ mục không hợp lệ. Theo mặc định, các chỉ số bạn nhập vào phải là số nguyên không âm. Nếu bạn muốn kiểm tra xem chỉ mục có hợp lệ hay không, bạn nên thực hiện trước khi gọi hàm này.
Lý do chúng tôi sử dụng p-> next! = null là vì chúng tôi chỉ muốn lặp lại các phần tử có giá trị.
+ Tìm kiếm trong danh sách liên kết
Hàm tìm kiếm này sẽ trả về chỉ mục của nút đầu tiên bằng giá trị tìm kiếm. Nếu không tìm thấy, chúng tôi trả về -1.
Chúng tôi có thể sử dụng chức năng này để xóa tất cả các nút có giá trị được chỉ định trong danh sách được liên kết, như sau:
+ Duyệt danh sách
Rất đơn giản để duyệt qua một danh sách được liên kết. Để khởi tạo từ nút đầu, bạn chỉ cần đi theo con trỏ tiếp theo cho đến khi nút trống.
+ Một số tính năng bổ sung khác
Hàm tạo nút đầu
Chỉ cần đặt con trỏ head = null. Nếu bạn để ý, chúng ta vẫn kiểm tra head = null để biết rằng danh sách không có phần tử nào trong hàm trên.
Hàm lấy số phần tử dslk
Miễn là nút không trống, hãy duyệt và đếm. Cuối cùng, trả về một giá trị.
Đầu vào danh sách được liên kết
IV. Thư Viện Linkedlist Trong C
Danh sách được liên kết là một chuỗi các cấu trúc dữ liệu được liên kết với nhau bằng các liên kết. Nói một cách dễ hiểu, danh sách liên kết là một cấu trúc dữ liệu bao gồm một tập hợp các nút tạo thành một chuỗi. Mỗi nút chứa dữ liệu cho nút đó và một tham chiếu đến nút tiếp theo trong chuỗi.
Các chương trình sử dụng c cho danh sách được liên kết
Kết quả
Biên dịch và chạy chương trình c trên để nhận được kết quả:
V. Bài Tập Linked List C++
Giúp ace cải thiện kỹ năng, kiến thức lập trình, ghi nhớ dễ dàng và hiểu sâu hơn trong khi học lý thuyết danh sách liên kết trong loạt bài tự học về cấu trúc dữ liệu và thuật toán của techacademy. Dưới đây là lời giải đầy đủ và chi tiết bài tập giải ace bằng một số ngôn ngữ lập trình khác nhau.
bài đăng 1: Xóa các phần tử trùng lặp trong danh sách đã sắp xếp
Cho một danh sách được liên kết được sắp xếp theo thứ tự tăng dần, hãy viết một hàm loại bỏ tất cả các nút trùng lặp trong danh sách được liên kết bằng cách duyệt qua danh sách được liên kết chỉ một lần
Ví dụ: {1, 2, 2, 2, 3, 4, 4, 5}
Sau khi thực hiện, kết quả là: {1, 2, 3, 4, 5}
Gợi ý: Vì danh sách được sắp xếp, chúng ta có thể tiếp tục giảm danh sách và so sánh các nút liền kề. Khi các nút liền kề giống nhau, hãy xóa nút thứ hai. Có một điều phức tạp là bạn cần chú ý đến nút này sau nút tiếp theo trước khi xóa.
bài đăng 2: Đảo ngược từng tập hợp k nút trong danh sách liên kết đã cho
Đối với danh sách được liên kết, hãy đảo ngược từng tập k nút liền kề, với k là số nguyên dương.
Ví dụ:
-> Đầu vào: 1 & gt; 2 & gt; 3 & gt; 4 & gt; 5 & gt; 6 & gt; 7 & gt; 8 & gt; null
k = 3
Đầu ra: 3 & gt; 2 & gt; 1 & gt; 6 & gt; 5 & gt; 4 & gt; 8 & gt; 7 & gt; null
k = 2
Đầu ra: 2 & gt; 1 & gt; 4 & gt; 3 & gt; 6 & gt; 5 & gt; 8 & gt; 7 & gt; null
k = 8
Đầu ra: 8 & gt; 7 & gt; 6 & gt; 5 & gt; 4 & gt; 3 & gt; 2 & gt; 1 & gt; null
Mẹo:
Ý tưởng là xem xét từng tập hợp k nút và đảo ngược đệ quy từng nút một. Cần có sự cẩn thận đặc biệt khi nối các nhóm nghịch đảo với nhau.
bài đăng 3: Di chuyển nút cuối cùng lên phía trước trong danh sách được liên kết
Đối với danh sách được liên kết, hãy di chuyển nút cuối cùng của nó lên phía trước.
Ví dụ: Đầu vào: 1,2,3,4
Đầu ra: 4,1,2,3
Gợi ý: Ý tưởng là lặp lại danh sách được liên kết, rồi ngắt chuỗi trước nút cuối cùng sau khi làm cho danh sách được liên kết trỏ đến nút cuối cùng.
bài đăng 4: Xóa tất cả n nút trong danh sách được liên kết sau khi bỏ qua m nút
Cho một danh sách được liên kết và hai số nguyên dương m và n, hãy xóa tất cả n nút trong đó sau khi bỏ qua m nút.
Ví dụ:
1 & gt; 2 & gt; 3 & gt; 4 & gt; 5 & gt; 6 & gt; 7 & gt; 8 & gt; 9 & gt; 10 & gt; trống
Nếu m = 1, n = 3
Đầu ra: 1> 5> 9> null
Nếu m = 2, n = 2
Đầu ra: 1 & gt; 2 & gt; 5 & gt; 6 & gt; 9 & gt; 10 & gt; null
Gợi ý: Ý tưởng rất đơn giản. Chúng tôi duyệt qua danh sách đã cho và bỏ qua m nút đầu tiên và xóa n nút tiếp theo trong đó và lặp lại cho phần còn lại. Giải pháp rất đơn giản, nhưng chúng ta cần đảm bảo rằng tất cả các điều kiện biên được xử lý chính xác trong mã.
bài đăng 5: Hợp nhất hai danh sách đã sắp xếp thành một
Viết một hàm nhận hai danh sách, mỗi danh sách được sắp xếp theo thứ tự tăng dần, sau đó hợp nhất hai danh sách thành một danh sách theo thứ tự tăng dần và trả về.
Ví dụ:
Đầu vào: 1 & gt; 7 & gt; 5 & gt; 4 và 2 & gt; 6 & gt; 3 & gt; 9
Đầu ra: 1 & gt; 2 & gt; 3 & gt; 4 & gt; 5 & gt; 6 & gt; 7 & gt; 9
Gợi ý: Các vấn đề có thể được giải quyết bằng cách lặp lại hoặc đệ quy. Có nhiều trường hợp cần xử lý: ‘a’ hoặc ‘b’ có thể được để trống, trong quá trình xử lý, ‘a’ hoặc ‘b’ có thể hết đầu tiên và cuối cùng là bắt đầu một quả trống từ danh sách cuối cùng và xây dựng nó trong khi chuyển ‘a’ “và” b “.
Có nhiều giải thưởng như sau:
- Sử dụng các nút giả
Chiến lược
ở đây sử dụng một nút giả tạm thời làm điểm bắt đầu cho danh sách kết quả. Đuôi của con trỏ luôn trỏ đến nút cuối cùng trong danh sách kết quả, vì vậy việc thêm các nút mới rất dễ dàng. Ban đầu, pseudonode cung cấp cho đuôi một cái gì đó để trỏ đến khi danh sách kết quả trống. Pseudonode này hiệu quả vì nó là tạm thời và được phân bổ trên ngăn xếp. Vòng lặp tiếp tục, loại bỏ một nút khỏi “a” hoặc “b” và thêm nó vào đuôi. Khi hoàn tất, kết quả là dummy.next.
- Sử dụng tài liệu tham khảo địa phương
Cấu trúc của giải pháp này rất giống với giải pháp trên, nhưng nó tránh được việc sử dụng các nút ảo. Thay vào đó, nó duy trì một con trỏ struct node ** lastptrref, con trỏ này luôn trỏ đến con trỏ cuối cùng của danh sách kết quả. Điều này giải quyết tình huống tương tự như pseudonodes – xử lý danh sách kết quả khi danh sách kết quả trống. Nếu bạn muốn tạo một danh sách ở cuối danh sách, bạn có thể sử dụng chiến lược nút giả hoặc nút cấu trúc ** “tham chiếu”.