مرتب سازی و ادغام فهرست پیوندی واحد

معرفی

تا اینجا، در این مجموعه 3 قسمتی در مورد لیست های پیوندی در پایتون، بحث خود را در مورد لیست پیوندی شروع کردیم. ما دیدیم که لیست پیوندی به همراه مزایا و معایب آن چیست. ما همچنین برخی از متداول‌ترین روش‌های لیست پیوندی مانند پیمایش، درج، حذف، جستجو و شمارش یک عنصر را مطالعه کردیم. در نهایت، دیدیم که چگونه یک لیست پیوندی را معکوس کنیم.

در این مقاله از همان جایی که در مقاله گذشته گذاشتیم ادامه خواهیم داد و خواهیم دید که چگونه یک لیست پیوندی را با استفاده از مرتب سازی حباب و ادغام مرتب کنیم و چگونه دو لیست پیوندی مرتب شده را ادغام کنیم.

قبل از ادامه، ذکر این نکته ضروری است که باید آن را ایجاد کنید Node و LinkedList کلاس هایی که در مقاله قبلی ایجاد کردیم.

مرتب سازی لیست های پیوندی با استفاده از مرتب سازی حباب

دو راه برای مرتب‌سازی فهرست پیوندی با استفاده از مرتب‌سازی حبابی وجود دارد:

1. تبادل داده بین گره ها
2. اصلاح پیوندهای بین گره ها

در این بخش، روش عملکرد هر دو این رویکردها را خواهیم دید. از الگوریتم مرتب سازی حبابی استفاده می کنیم تا ابتدا لیست پیوندی را با تغییر داده ها مرتب کنیم و سپس خواهیم دید که چگونه می توانیم از مرتب سازی حبابی برای تغییر پیوندها برای مرتب سازی لیست پیوند شده استفاده کنیم.

مرتب سازی لیست پیوندی با تبادل داده

برای مرتب کردن یک لیست پیوندی با تبادل داده، باید سه متغیر را تعریف کنیم p، q، و end. متغیر p با شروع مقداردهی اولیه خواهد شد node، در حالی که end تنظیم خواهد شد None.

برای پیاده سازی مرتب سازی حبابی، به دو مورد نیاز داریم while حلقه ها بیرونی while حلقه تا مقدار متغیر اجرا می شود end برابر است با self.start_node.

درونی while حلقه اجرا می شود تا زمانی که p برابر می شود end متغیر. داخل بیرونی while حلقه، ارزش p تنظیم خواهد شد self.start_node که اولین است node. داخل باطن while حلقه، ارزش q تنظیم خواهد شد p.link که در واقع همان است node جنب q. سپس مقادیر p و q مقایسه خواهد شد اگر p بزرگتر است از q مقادیر هر دو متغیر مبادله می شود و سپس p اشاره خواهد کرد p.ref، که بعدی است node. در نهایت، end مقدار تخصیص داده خواهد شد p. این process تا زمانی که لیست پیوندی مرتب شود ادامه می یابد.

این را بفهمیم process با کمک یک مثال فرض کنید لیست زیر را داریم:

8,7,1,6,9

بیایید الگوریتم خود را برای مرتب سازی لیست پیاده سازی کنیم. خواهیم دید که در طول هر تکرار چه اتفاقی خواهد افتاد.

هدف از مرتب‌سازی حبابی این است که در طول هر تکرار، بزرگترین مقدار باید به انتها فشار داده شود، بنابراین در پایان تمام تکرارها، لیست به طور خودکار مرتب می‌شود.

قبل از اجرای حلقه، مقدار end تنظیم شده است None.

در اولین تکرار، p تنظیم خواهد شد 8، و q تنظیم خواهد شد 7. از آنجا که p بزرگتر است از q، مقادیر مبادله می شوند و p خواهد شد p.ref. در این مرحله از زمان، لیست پیوند شده به شکل زیر خواهد بود:

7,8,1,6,9

از حالا روی، p برابر نیست end، حلقه ادامه خواهد داشت و اکنون p خواهد شد 8 و q خواهد شد 1. از آنجا که p دوباره بزرگتر از q، مقادیر مجدداً مبادله می شوند و p دوباره تبدیل خواهد شد p.ref:

7,1,8,6,9

اینجا دوباره، p برابر نیست end، حلقه ادامه خواهد داشت و اکنون p خواهد شد 8 و q خواهد شد 6. از آنجایی که دوباره p بزرگتر است از q، مقادیر مجدداً مبادله می شوند و p دوباره تبدیل خواهد شد p.ref. لیست به شکل زیر خواهد بود:

7,1,6,8,9

از نو p برابر نیست end، حلقه ادامه خواهد داشت و اکنون p خواهد شد 8 و q خواهد شد 9. اینجا از آن زمان p بزرگتر از q، ارزش ها تعویض نخواهد شد و p خواهد شد p.ref. در این نقطه از زمان، مرجع از p اشاره خواهد کرد None، و end همچنین اشاره می کند None. از این رو درونی while حلقه خواهد شکست و end تنظیم خواهد شد p.

در مجموعه بعدی از تکرارها، حلقه تا زمانی که اجرا می شود 8، از آنجا که 9 در حال حاضر در پایان است را process تا مرتب شدن کامل لیست ادامه می یابد.

کد پایتون برای مرتب‌سازی لیست پیوندی با استفاده از مرتب‌سازی حبابی با تبادل داده‌ها به شرح زیر است:

    def bub_sort_datachange(self):
        end = None
        while end != self.start_node:
            p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.item, q.item = q.item, p.item
                p = p.ref
            end = p

هنگامی که روش را به لیست پیوندی اضافه کردید، هر مجموعه ای از گره ها را با استفاده از آن ایجاد کنید make_new_list() روش و سپس استفاده کنید bub_sort_dataexchange() برای مرتب کردن لیست هنگام اجرا باید لیست مرتب شده را ببینید traverse_list() روش.

مرتب سازی لیست های پیوندی با تغییر پیوندها

مرتب‌سازی حبابی می‌تواند برای مرتب‌سازی فهرست پیوندی با اصلاح پیوندها به جای تغییر داده‌ها استفاده شود. را process کاملاً شبیه مرتب سازی لیست با تبادل داده است، با این حال، در این مورد، ما یک متغیر اضافی داریم r که همیشه با آن مطابقت دارد node قبلی از p node.

بیایید یک مثال ساده از روش انجام آن بیاوریم swap دو گره با تغییر پیوندها. فرض کنید ما یک لیست پیوندی با موارد زیر داریم:

10,45,65,35,1

و ما می خواهیم swap 65 و 35. در این لحظه از زمان p مطابقت دارد node 65، و q مطابقت دارد node 35. متغیر r مطابقت خواهد داشت node 45 (قبلی به node p). حال اگر node p بزرگتر است از node q، که در اینجا وجود دارد p.ref تنظیم خواهد شد q.ref و q.ref تنظیم خواهد شد p. به همین ترتیب، r.ref تنظیم خواهد شد q. این اراده swap گره ها 65 و 35.

روش زیر مرتب‌سازی حبابی را برای لیست پیوندی با تغییر پیوندها پیاده‌سازی می‌کند:

    def bub_sort_linkchange(self):
        end = None
        while end != self.start_node:
            r = p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.ref = q.ref
                    q.ref = p
                    if p != self.start_node:
                        r.ref = q
                    else:
                        self.start_node = q
                    p,q = q,p
                r = p
                p = p.ref
            end = p

هنگامی که روش را به لیست پیوندی اضافه کردید، هر مجموعه ای از گره ها را با استفاده از آن ایجاد کنید make_new_list() روش و سپس استفاده کنید bub_sort_linkchange() برای مرتب کردن لیست هنگام اجرا باید لیست مرتب شده را ببینید traverse_list() روش.

ادغام فهرست پیوندی مرتب شده

در این بخش، خواهیم دید که چگونه می‌توانیم دو لیست پیوندی مرتب‌سازی شده را به گونه‌ای ادغام کنیم که لیست پیوندی حاصل نیز مرتب شود. برای رسیدن به این هدف دو رویکرد وجود دارد. ما می توانیم یک لیست پیوندی جدید ایجاد کنیم که حاوی لیست های مرتب شده به صورت جداگانه باشد یا می توانیم به سادگی پیوندهای دو لیست پیوند خورده را برای پیوستن به این دو تغییر دهیم. در مورد دوم، ما مجبور نیستیم یک لیست پیوندی جدید ایجاد کنیم.

بیایید ابتدا ببینیم چگونه می توانیم با ایجاد یک لیست جدید، دو لیست مرتبط را با هم ادغام کنیم.

ادغام لیست های پیوندی مرتب شده با ایجاد یک لیست جدید

اجازه دهید ابتدا الگوریتم را به صورت خشک اجرا کنیم تا ببینیم چگونه می‌توانیم دو لیست پیوندی مرتب شده را با کمک یک لیست جدید ادغام کنیم.

فرض کنید ما دو لیست پیوندی مرتب شده زیر را داریم:

list1:
10,45,65

list2:
5,15,35,68

این دو لیستی است که می خواهیم با هم ادغام کنیم. الگوریتم ساده است. تنها چیزی که نیاز داریم سه متغیر است، p، q، و emو یک لیست خالی newlist.

در ابتدای الگوریتم، p به اولین عنصر اشاره خواهد کرد list1 در حالیکه q به اولین عنصر اشاره خواهد کرد list2. متغیر em خالی خواهد بود در شروع الگوریتم، مقادیر زیر را خواهیم داشت:

p = 10
q = 5
em = None
newlist = None

بعد، ما اولین عنصر را با هم مقایسه می کنیم list1 با اولین عنصر از list2به عبارت دیگر، مقادیر را با هم مقایسه می کنیم p و q و مقدار کوچکتر در متغیر ذخیره می شود em که اولین خواهد شد node از لیست جدید ارزش em به پایان اضافه خواهد شد newlist.

پس از اولین مقایسه، مقادیر زیر را خواهیم داشت:

p = 10
q = 15
em = 5
newlist = 5

از آنجا که q کمتر از p، مقدار را ذخیره کردیم q که در em و حرکت کرد q یک شاخص به سمت راست در پاس دوم مقادیر زیر را خواهیم داشت:

p = 45
q = 15
em = 10
newlist = 5, 10

اینجا از آن زمان p کوچکتر بود، ارزش آن را اضافه کردیم p به newlist، تنظیم em به p، و سپس نقل مکان کرد p یک شاخص در سمت راست:

p = 45
q = 35
em = 15
newlist = 5, 10, 15

به همین ترتیب، در تکرار بعدی:

p = 45
q = 68
em = 35
newlist = 5, 10, 15, 35

در تکرار بعدی، p دوباره کوچکتر از q، از این رو:

p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

و در نهایت:

p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

وقتی یکی از لیست ها می شود None، تمام عناصر لیست دوم در انتهای لیست جدید اضافه می شوند. بنابراین، لیست نهایی به شرح زیر خواهد بود:

p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

بیایید همه اینها را با ایجاد دو روش در کد قرار دهیم – merge_helper() و merge_by_newlist():

    def merge_helper(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
        return merged_list

    def merge_by_newlist(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                p = p.ref
            else:
                em.ref = Node(q.item)
                q = q.ref
            em = em.ref

        while p is not None:
            em.ref = Node(p.item)
            p = p.ref
            em = em.ref

        while q is not None:
            em.ref = Node(q.item)
            q = q.ref
            em = em.ref

        return startNode

را merge_helper() متد یک لیست پیوندی را به عنوان پارامتر می گیرد و سپس آن را ارسال می کند self کلاس که خود یک لیست پیوندی است و لیست پیوندی به عنوان پارامتر به آن ارسال می شود merge_by_newlist() روش.

را merge_by_newlist() متد دو لیست مرتبط را با ایجاد یک لیست پیوندی جدید ادغام می کند و شروع آن را برمی گرداند node. این دو روش را به LinkedList کلاس دو لیست پیوندی جدید ایجاد کنید، آنها را با استفاده از فهرست مرتب کنید bub_sort_datachange() یا bub_sort_linkchange() روش هایی که در قسمت آخر ایجاد کردید و سپس از آن استفاده کنید merge_by_newlist() برای دیدن اینکه آیا می توانید دو لیست پیوندی مرتب شده را ادغام کنید یا خیر.

ادغام لیست های پیوندی مرتب شده با ترتیب مجدد پیوندها

در این رویکرد، یک لیست پیوندی جدید برای ذخیره ادغام دو لیست پیوندی مرتب شده استفاده نمی شود. بلکه پیوندهای دو لیست پیوندی به گونه ای اصلاح می شوند که دو لیست پیوندی به صورت مرتب شده ادغام می شوند.

بیایید یک مثال ساده از روش انجام این کار را ببینیم. فرض کنید ما همان دو لیست را داریم list1 و list2:

list1:
10,45,65

list2:
5,15,35,68

ما می خواهیم با مرتب کردن مجدد پیوندها آنها را به صورت مرتب شده ادغام کنیم. برای این کار به متغیرها نیاز داریم p، q، و em. در ابتدا، آنها مقادیر زیر را خواهند داشت:

p = 10
q = 5
em = none
newlist = none

در ادامه اولین عنصر را با هم مقایسه می کنیم list1 با اولین عنصر از list2به عبارت دیگر، مقادیر را با هم مقایسه می کنیم p و q و مقدار کوچکتر در متغیر ذخیره می شود em که اولین خواهد شد node از لیست جدید

پس از اولین مقایسه، مقادیر زیر را خواهیم داشت:

p = 10
q = 15
start = 5
em = start

پس از اولین تکرار، از آن زمان q کمتر است از p، آغاز node به سمت اشاره خواهد کرد q و q خواهد شد q.ref. را em برابر خواهد بود start. را em همیشه به موارد جدید درج شده اشاره خواهد کرد node در لیست ادغام شده:

p = 45
q = 15
em = 10

در اینجا، از آنجا که p کوچکتر از q، متغیر em اکنون به سمت ارزش اصلی اشاره می کند p و p تبدیل می شود p.ref:

p = 45
q = 35
em = 15

از آنجا که q کوچکتر از p، em به سمت اشاره می کند q و q تبدیل می شود q.ref:

p = 45
q = 68
em = 35

به همین ترتیب em در اینجا به سمت q:

p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

و اینجا em به سمت تبدیل می شود p:

p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

وقتی یکی از لیست ها می شود None، عناصر لیست دوم به سادگی در پایان اضافه می شوند:

p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

اسکریپتی که شامل متدهایی برای ادغام دو لیست بدون ایجاد لیست جدید است به شرح زیر است:

    def merge_helper2(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
        return merged_list

    def merge_by_linkChange(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                em = em.ref
                p = p.ref
            else:
                em.ref = Node(q.item)
                em = em.ref
                q = q.ref


        if p is None:
            em.ref = q
        else:
            em.ref = p

        return startNode

در اسکریپت بالا دو روش داریم: merge_helper2() و merge_by_linkChange(). روش اول merge_helper2() یک لیست پیوندی را به عنوان پارامتر می گیرد و سپس کلاس self را که خود یک لیست پیوندی است و لیست پیوندی را به عنوان پارامتر به آن ارسال می کند. merge_by_linkChange()، که با اصلاح پیوندها دو پیوند خورده را ادغام می کند و شروع را برمی گرداند node از لیست ادغام شده

این دو روش را به LinkedList کلاس دو لیست پیوندی جدید ایجاد کنید، آنها را با استفاده از فهرست مرتب کنید bub_sort_datachange() یا bub_sort_linkchange() روش هایی که در قسمت آخر ایجاد کردید و سپس از آن استفاده کنید merge_by_newlist() برای دیدن اینکه آیا می توانید دو لیست پیوندی مرتب شده را ادغام کنید یا خیر. اینو ببینیم process در عمل:

new_linked_list1 = LinkedList()
new_linked_list1.make_new_list()

اسکریپت از شما می خواهد تعداد گره هایی را که باید وارد کنید. هر تعداد گره را که دوست دارید وارد کنید و سپس برای هر کدام مقادیر اضافه کنید node همانطور که در زیر نشان داده شده است:

How many nodes do you want to create: 4
Enter the value for the node:12
Enter the value for the node:45
Enter the value for the node:32
Enter the value for the node:61

سپس، لیست پیوندی دیگری ایجاد کنید که موارد بالا را تکرار کند process:

new_linked_list2 = LinkedList()
new_linked_list2.make_new_list()

در مرحله بعد، چند گره ساختگی را با کمک اسکریپت زیر اضافه کنید:

How many nodes do you want to create: 4
Enter the value for the node:36
Enter the value for the node:41
Enter the value for the node:25
Enter the value for the node:9

مرحله بعدی مرتب کردن هر دو لیست است. اسکریپت زیر را اجرا کنید:

new_linked_list1. bub_sort_datachange()
new_linked_list2. bub_sort_datachange()

در نهایت، اسکریپت زیر دو لیست مرتبط را ادغام می کند:

list3 = new_linked_list1.merge_helper2(new_linked_list2)

برای اینکه ببینید آیا لیست ها واقعا ادغام شده اند یا خیر، اسکریپت زیر را اجرا کنید:

list3.traverse_list()

خروجی به شکل زیر است:

9
12
25
32
36
41
45
61

نتیجه

در این مقاله از همان جایی که در مقاله قبلی گذاشتیم ادامه دادیم. دیدیم که چگونه می‌توانیم فهرست‌های ادغام را با تغییر داده‌ها و سپس اصلاح پیوندها مرتب کنیم. در نهایت، روش‌های مختلف ادغام دو فهرست پیوندی مرتب‌شده را نیز مطالعه کردیم.

در مقاله بعدی، روش ساخت و اجرای عملیات را بررسی خواهیم کرد روی لیست های دارای پیوند دوگانه