فصل ۱۰ − Pointer Types📎

➡ فهرست

1. فصل ۱۰ − Pointer Types
2. pointer variables and identified (dynamic) variables
3. New and Dispose

تاکنون درباره‌ی type هایی صحبت کرده‌ایم که برای اعلان متغیرهای statically allocated در نظر گرفته شده‌اند. یک متغیر static متغیری است که در برنامه اعلان می‌شود و متعاقبا به وسیله‌ی identifier اش به آن دلالت می‌شود. برای این به آن static می‌گوییم چون در طی تمام زمان اجرای بلاک (program، یا procedure، یا function) ای که این متغیر نسبت به آن local است وجود دارد (یعنی برای آن حافظه اختصاص داده شده است.) از طرف دیگر ممکن است در طی اجرای یک بلاک متغیرهایی را به صورت dynamic ایجاد کرد و یا از بین برد (بدون هیچ همبستگی با ساختار static برنامه). به چنین متغیرهایی dynamic variable یا identified variable می‌گوییم.

pointer variables and identified (dynamic) variables📎

identified (dynamic) variable ها در اعلان صریح متغیرها نمی‌آیند و به صورت مستقیم توسط identifier ها قابل دسترسی نیستند، در عوض آن‌ها به وسیله‌ی پروسیجرهای از پیش تعریف شده‌ی New و Dispose ایجاد و تخریب، و به وسیله‌ی pointer value ها شناسایی می‌شوند (که ممکن است فقط توسط آدرس‌های مکان ذخیره‌سازی متغیرهای تازه تخصیص داده شده پیاده‌سازی شوند). pointer value ها باید به pointer variable های از قبل موجود که pointer type مناسب دارند assign شوند.

سینتکس دیاگرام نوع pointer را در زیر ملاحظه می‌کنید:

توصیف یک نوع اشاره‌گر P یک domain type به نام T را مشخص می‌کند.

TYPE
    P = ↑T;     { P=Pointer type, T=Domain type }

مجموعه‌ی pointer value های از نوع P از تعداد نامحدودی از identifying values تشکیل شده است، که هر کدام از آن‌ها یک variable از نوع T را شناسایی می‌کند. در این مجموعه مقدار ویژه‌ی nil نیز قرار دارد که هیچ متغیری را مشخص نمی‌کند.

یک identified (dynamic) variable به وسیله‌ی یک pointer value که آن را شناسایی می‌کند مورد دسترسی قرار می‌گیرد؛ به طور مشخص، اگر Ptr به صورت زیر اعلان شده باشد:

VAR
    Ptr: P;

و یک identifying value در Ptr ریخته شده باشد، در این صورت ساختار Ptr↑ نشانگر identified variable است. سینتکس دیاگرام identified variable به صورت زیر است:

❗ در صورتی که Ptr تعریف نشده باشد یا NIL باشد Ptr↑ خطا است.

New(Ptr) یک identified variable از نوع T، ایجاد یا allocate می‌کند و identifying value آن را در Ptr می‌ریزد. Dispose(Ptr) عکس این کار را انجام می‌دهد یعنی variable ای که با مقدار Ptr شناسایی یا identify می‌شود را deallocate یا تخریب می‌کند؛ بعد از Dispose مقدار Ptr نامشخص یا undefined خواهد بود.

pointer ها ابزاری ساده برای ساختِ data structure های پیچیده و منعطف ( و حتی recursive) هستند.

اگر T ساختاری از نوع رکورد باشد و یک یا چند فیلد از نوع P داشته باشد، آنگاه می‌توان ساختارهایی معادل گراف‌های محدودِ دلخواه را ایجاد کرد؛ identified variable ها node ها را نمایندگی می‌کنند، و pointer ها یال‌ها هستند.

⬅ مثال 10.1 استفاده از pointer ها برای مدیریت یک لیست انتظار را نشان می‌دهد. (پروسیجرها در فصل بعد توضیح داده می‌شوند.)

به عنوان مثال دیگر، ساخت یک database برای یک گروه از آدم‌ها را در نظر بگیرید. فرض کنید آدم‌ها به وسیله‌ی نوع رکوردی که در فصل ۷ تعریف شده نشان داده می‌شوند ( اینجا ). آنگاه می‌توانیم با اضافه کردن یک فیلد از نوع pointer، یک زنجیر یا لیست پیوندی یا linked list از این چنین رکوردهایی ایجاد و برای عملیات جستجو و درج از آن استفاده کرد:

TYPE
    Link = ↑Person;
    ...
    Person = Record
        ...
        Next: Link;
    END;

یک linked list از n شخص را می‌توان به صورت زیر نشان داد. هر مربع یک نفر را نمایندگی می‌کند:

یک variable از نوع Link، که First نام دارد، به اولین نفر در لیست اشاره می‌کند. فیلد Next آخرین نفر در لیست NIL است. کد زیر:

First↑.Next↑.Next

به سومین عنصرِ لیست اشاره می‌کند. اگر فرض کنیم که، برای مثال، می‌توانیم برای بیان قامت افراد دیتای integer بخوانیم، در این صورت کد زیر می‌تواند برای ساخت زنجیره‌ی بالا استفاده شود:

VAR
    First, P: Link;
    H, I: Integer;
...
First := NIL;
FOR I := 1 TO N DO BEGIN
    Read(H);
    New(P);
    P↑.Next := First;
    P↑.Height := H;
    InitializeOtherFields(p↑);
    First := P;
END

توجه کنید که لیست بالا به سمت عقب رشد می‌کند. به منظور دسترسی، متغیر دیگری تعریف خواهیم کرد، Pt از نوع Link، و اجازه می‌دهیم که آزادانه در لیست حرکت کند. برای نشان دادن selection یا انتخاب فرض می‌کنیم که یک Person با Height برابر 175 وجود دارد و می‌خواهیم به این Person دسترسی بیابیم. راهبرد ما این است که Pt را از طریق Link تا جایی که شخص مورد نظر ما قرار گرفته است جلو ببریم:

Pt := First;
WHILE Pt↑.Height <> 175 DO
    Pt := Pt^.Next

توضیح گفتاری کد بالا به این صورت است: «اجازه بده که Pt به اولین شخص اشاره کند. مادامی که قامت شخصی که به وسیله‌ی Pt به آن اشاره می‌شود، یا به وسیله‌ی Pt شناسایی می‌شود، ۱۷۵ نیست، pointer value ذخیره شده در فیلد Next رکورد (که آن هم یک pointer variable است)، که Pt هم اکنون آن را شناسایی می‌کند را در Pt بریز.»

این search statement ساده فقط در صورتی کار می‌کند که مطمئن باشیم که حداقل یک فرد با Height برابر ۱۷۵ در لیست وجود دارد. اما آیا واقع‌بینانه است؟ بررسی شکست در یافتن ۱۷۵ قبل از رسیدن به پایان لیست ضروری است مگر اینکه بتوانیم این عدم شکست را تضمین کنیم. ممکن است برای گام نخست راه‌حل زیر را امتحان کنیم:

Pt := First;
WHILE (Pt <> NIL) AND (Pt↑.Height <> 175) DO
    Pt := Pt↑.Next

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

(1)
Pt := First;
B := True;

WHILE (Pt <> NIL) AND B DO
    IF Pt↑.Height = 175 THEN
        B := False
    ELSE
        Pt := Pt↑.Next

(2)
Pt := First;
WHILE Pt <> NIL DO BEGIN
    IF Pt↑.Height = 175 THEN
        GOTO 13;
    Pt := Pt↑.next
END;
13:

New and Dispose📎

برای نشان دادن یک مشکل دیگر، فرض کنید می‌خواهیم یک فرد نمونه را به database اضافه کنیم. ابتدا باید یک متغیر allocate شود و identifying value آن به وسیله‌ی پروسیجرِ از پیش تعریف شده‌ی New به دست آید.

1. New(P) : پروسیجری است که یک identified (dynamic) variable جدید P↑ را allocate می‌کند که از نوع domain type متغیر P است، یک identifying pointer value جدید از نوع P ایجاد می‌کند و آن را در P می‌ریزد. اگر P↑ یک variant record باشد، new(p) فضای کافی برای جا دادن تمام variant ها اختصاص می‌دهد.
2. New(P, C1, ..., Cn) : یک identified (dynamic) variable جدید P↑ allocate می‌کند که از نوع variant record type of P است با مقادیر C1,...,Cn برای مقدار tag filed تعداد n عدد variant part تو در تو. یک identifiying pointer value که از همان نوعی است که P از آن نوع است می‌سازد و آن را در P می‌ریزد. (صفحه‌ی ۹۹)

⛔ اگر با استفاده از شکل دومِ پروسیجر New یک record variable P↑ ایجاد کردیم آنگاه در طی اجرای برنامه این رکورد دیگر نباید variant اش را تغییر دهد. assignment به کل متغیر نادرست و خطاست؛ با این وجود assign کردن به مولفه‌های P↑ مشکلی ندارد.

اولین گام در برنامه‌نویسیِ یک راه حل برای مساله‌ی بالا تعریف یک pointer variable است. بگذارید اسمش را NewP بگذاریم. در این صورت statement:

New(NewP)

یک variable جدید از نوع Person را allocate می‌کند.

در مرحله‌ی بعد، متغیر جدید، که اشاره‌گر NewP به آن اشاره می‌کند، باید بعد از فردی که به وسیله‌ی Pt به آن ارجاع می‌شود قرار گیرد. تصویر زیر را ملاحظه کنید:

⚪ عمل درج بسیار ساده است و فقط با تغییر pointer ها صورت می‌گیرد:

NewP↑.Next := Pt↑.Next;
Pt↑.Next := NewP

نتیجه را در تصویر می‌بینید:

⚪ حذف یک person، که بعد از pointer معینِ Pt قرار گرفته است، در یک تک دستور انجام می‌شود:

Pt↑.Next := Pt↑.next↑.Next

⚪ معمولا یک لیست را با استفاده از دو pointer پردازش می‌کنند ــ یکی پیش‌رو یا lookahead و دیگری پس‌رو یا trailer، یکی به دنبال دیگری ــ در مورد حذف محتمل است که یک pointer، مثلا P1، مقدمِ بر عنصری باشد که می‌بایست حذف شود، و P2 به همان عنصرِ حذف شونده اشاره کند. پس به این ترتیب «حذف» می‌تواند در یک تک دستور بیان شود:

P1↑.Next := P2↑.Next

به هر صورت به شما هشدار داده می‌شود که deletion به این شیوه گاهی اوقات باعث از دست رفتن حافظه‌ی قابل استفاده خواهد شد. یک راه‌حل ممکن ایجاد یک لیستِ صریح از اعضای حذف شده است که متغیر Free به آن اشاره می‌کند. اگر این لیست خالی نباشد، متغیرهای جدید، به جای استفاده از پروسیجرِ New، از این لیست گرفته می‌شوند. حالا حذفِ یک عنصر از لیست به صورت انتقال آن عنصر از لیستِ عناصر به لیستِ عناصرِِ حذف شده در می‌آید:

P1↑.Next := P2↑.Next;
P2↑.Next := Free;
Free := P2

⚪ با استفاده از پروسیجرِ از پیش تعریف شده‌ی Dispose، می‌توان مدیریت اعضای حذف شده را به پیاده‌سازی پاسکال سپرد:

1. Dispose(Q) : identified variable Q↑ را deallocate و خود Q که identifying value است را نیز تخریب می‌کند. استفاده از این پروسیجر اگر Q برابر NIL و یا undefined باشد نادرست و خطا است. مقدار Q باید با اولین فرم پروسیجر New ایجاد شده باشد.
2. Dispose(Q, K1, ..., Kn) : identified variant record variable Q↑ با variant های فعال مشخص شده به وسیله‌ی K1, ..., Kn را dellocate و Q که identifying value آن است را نیز تخریب می‌کند. اگر Q NIL و یا undefined باشد استفاده از این پروسیجر نادرست است. مقدار Q باید با استفاده از دومین فرم New به دست آمده باشد و K1, ...,Kn نیز باید همان varinat هایی که Q با آن ساخته شده است را مشخص کند.

⚪ مثال‌های 11.6 و 11.7 در فصل یازده پیمایش ساختارهای درختی که با استفاده از pointer type ها ساخته شده‌اند را نشان می‌دهند.