فصل ۱۰ − 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 به دست آید.