Danh sách liên kết là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử được liên kết thông qua con trỏ. Mỗi phần tử hoặc nút của danh sách liên kết có một phần dữ liệu và liên kết, hoặc chúng ta có thể nói con trỏ đến phần tử tiếp theo theo trình tự. Các phần tử có thể chiếm các vị trí không liền nhau trong bộ nhớ.
Chúng tôi được cung cấp một danh sách liên kết duy nhất trong đó có một phần dữ liệu và liên kết đến phần tử tiếp theo. Đầu vào khác là một số K. Nhiệm vụ là tìm phần tử Tối đa và Nhỏ nhất của danh sách liên kết chia hết cho số K. Chỉ có thể duyệt danh sách liên kết tuyến tính theo một hướng. Tại mỗi nút, chúng tôi sẽ kiểm tra tính chia hết của phần dữ liệu của nó với K. Nếu số đó là tối đa hoặc tối thiểu được tìm thấy cho đến nay thì chúng tôi sẽ cập nhật các giá trị của MaxD và MinD.
Đầu vào
SList : 5-->2-->10-->12-->3-->20-->7, K=5
Đầu ra
Maximum element which is divisible by K : 20 Maximum element which is divisible by K : 5
Giải thích - Đi ngang từ nút Head, tiếp tục chia phần dữ liệu với K và kiểm tra xem nó có chia hết hoàn toàn hay không, phần còn lại là 0.
Chỉ 5, 10 và 20 chia hết cho 5, trong đó 5 là nhỏ nhất và 20 là tối đa.
Đầu vào
SList : 12-->2-->5-->18-->3-->144-->7, K=4
Đầu ra
Maximum element which is divisible by K : 144 Maximum element which is divisible by K : 12
Giải thích - Đi ngang từ nút Head, tiếp tục chia phần dữ liệu với K và kiểm tra xem nó có chia hết hoàn toàn hay không, phần còn lại là 0.
Chỉ 12 và 144 chia hết cho 4, trong đó 12 là tối thiểu và 144 là tối đa.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tạo một nút danh sách liên kết. Ở đây chúng tôi đã tạo một SLLnode lớp, có phần thông tin và con trỏ tiếp theo.
-
Tạo một danh sách liên kết. Ở đây chúng tôi đã tạo một SLList lớp với đối tượng SLLnode là thành viên của nó. Vì vậy, SLList bao gồm SLLnodes.
-
Hàm addtohead (int) đang thêm các nút vào danh sách này.
-
Để thêm các phần tử vào SLList, chúng tôi đang gọi addtohead (int) bằng cách sử dụng đối tượng SLList có tên LIST.
-
Sau khi SLList được tạo, chúng ta gọi hàm Divisible (SLLnode, int) lấy hai tham số đầu vào là đầu danh sách và số nguyên K.
-
Bây giờ bên trong Divisible, chúng ta lấy hai biến maxD và minD để lưu trữ phần tử Tối đa và Tối thiểu của một danh sách được liên kết chia hết cho một số K cho trước.
-
maxD được khởi tạo bằng -1 và minD được khởi tạo bằng 9999. Đây được coi là phạm vi mà đầu vào nằm trong đó.
-
Trong vòng lặp for, chúng tôi duyệt qua danh sách được liên kết bắt đầu từ đầu. Đối với biến này, start là trỏ tới head.
-
So sánh phần thông tin của mỗi nút với maxD và minD và khả năng chia của nó với K. Nếu thông tin của nút hiện tại có thể chia được và nhỏ hơn minD, hãy cập nhật minD với phần thông tin hiện tại.
-
Nếu thông tin của nút hiện tại chia hết cho K và lớn hơn maxD, hãy cập nhật maxD với phần thông tin hiện tại.
-
In kết quả thu được theo minD và maxD.
Ví dụ
#include<iostream.h>
#include<process.h>
#include<conio.h>
class SLLnode{
public:
int info;
SLLnode *next;
SLLnode(int e1,SLLnode *ptr=0){
info=e1;
next=ptr;
}
};
class SLList{
public:
SLLnode *head;
SLList()
{ head=0; }
void addtohead(int); };
void SLList::addtohead(int el)
{ head=new SLLnode(el,head); }
void Divisible(SLLnode* head, int K){
int minD=9999;
int maxD=-1;
SLLnode* start=head;
for(start;start->next!=NULL;start=start->next){
if ((start->info < minD) && (start->info % K == 0))
minD = start->info;
if ((start->info > maxD) && (start->info % K == 0))
maxD = start->info;
}
cout << "Max Element divisible by K: " << maxD << endl;
cout << "Min Element divisible by K: " << minD;
}
// Driver Code
int main(){
clrscr();
// Start with empty list
SLList LIST;
LIST.addtohead(50);
LIST.addtohead(21);
LIST.addtohead(32);
LIST.addtohead(45);
LIST.addtohead(11);
LIST.addtohead(23);
LIST.addtohead(90);
LIST.addtohead(56);
int K = 5;
Divisible(LIST.head, K);
getch();
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Max Element divisible by K: 90 Min Element divisible by K: 45