جستجوی زیر لیست (Sublist Search) – راهنمای کاربردی

در این مطلب، جستجوی زیر لیست (Sublist Search | جستجوی ساب لیست) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و #C انجام شده است. دو لیست لینک شده به یکدیگر، ارائه شده است. هدف، بررسی این است که آیا لیست اول در لیست دوم وجود دارد یا خیر. برای درک بهتر این مطلب، مثال زیر قابل توجه است.

Input  : list1 =  10->20
         list2  = 5->10->20
Output : LIST FOUND

Input  : list1 =  1->2->3->4
         list2  = 1->2->1->2->3->4
Output : LIST FOUND

Input  : list1 =  1->2->3->4
         list2  = 1->2->2->1->2->3
Output : LIST NOT FOUND

جستجوی زیر لیست (Sublist Search)

الگوریتم جستجوی زیر لیست (Sublist Search | جستجوی ساب لیست) در ادامه ارائه شده است.

1. اولین گره از دومین لیست را دریافت کن.
2. تطبیق دادن اولین لیست را از این گره ابتدایی آغاز کن.
3. اگر کل لیست مطابقت دارد، مقدار True را بازگردان.
4. در غیر این صورت، break کن و اولین لیست را به اولین گره ببر.
5. و دومین لیست را به دومین گره ببر.
6. این مراحل را تا هنگامی که هر یک از لیست‌های پیوندی خالی باشد، تکرار کن.
7. اگر لیست اول خالی شد، بنابراین لیست پیدا شده است، در غیر این صورت، لیست پیدا نشده است.

در ادامه، پیاده‌سازی الگوریتم بالا ارائه شده است.

جستجوی زیر لیست در ++C

جستجوی زیر لیست در جاوا

جستجوی زیر لیست در #C

خروجی قطعه کدهای بالا، به صورت زیر است.

LIST FOUND

پیچیدگی زمانی از درجه O(m*n)‎ است که در آن، m تعداد گره‌ها در دومین لیست و n در اولین لیست است.

بهینه‌سازی روش ارائه شده در بالا

کد بالا را می‌توان با استفاده از فضای اضافی که لیست را در دو رشته ذخیره و الگوریتم KMP را اعمال می‌کند، بهینه‌سازی کرد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
• الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده

^^