زیپ (ساختار داده) کیست؟ توضیح بده.
ساختار داده زیپ تکنیکی برای نمایش یک ساختار داده انبوه است به طوری که برای نوشتن برنامه‌هایی که خودسرانه ساختار را طی می‌کنند و محتویات آن را به روز می‌کنند، به خصوص در راحت باشد. زیپ توسط در سال ۱۹۹۷ توصیف شد. این شامل و تعمیم تکنیک است که گاهی با آرایه‌ها استفاده می‌شود.تکنیک زیپ از این نظر کلی است که می‌توان آن را با فهرست‌ها، درخت‌ها و دیگر ساختارهای داده‌ای که به تعریف می‌شوند، تطبیق داد. چنین ساختارهای داده‌ای اصلاح شده معمولاً به عنوان «یک درخت با زیپ» یا «یک لیست با زیپ» نامیده می‌شود تا تأکید شود که ساختار از نظر مفهومی یک درخت یا لیست است، در حالی که زیپ جزئیات پیاده‌سازی است.توضیح یک فرد عادی برای درختی با زیپ یک سیستم فایل کامپیوتری معمولی با عملیاتی برای رفتن به والد (اغلب codice_1) و امکان رفتن به سمت پایین (codice_2) است. زیپ نشانگر مسیر فعلی است. در پشت صحنه، زیپ‌ها هنگام ایجاد تغییرات (عملکردی) در یک ساختار داده کارآمد هستند، جایی که یک ساختار داده جدید، کمی تغییر یافته از یک عملیات ویرایش بازگردانده می‌شود (به جای ایجاد تغییر در ساختار داده فعلی).مثال: پیمایش لیست دوطرفه.بسیاری از ساختارهای داده رایج در علوم کامپیوتر را می‌توان به عنوان ساختاری که توسط چند عملیات سازنده اولیه یا عملیات مشاهده گر ایجاد می‌شود بیان کرد. اینها شامل ساختار لیست‌های محدود است که می‌تواند توسط دو عملیات ایجاد شود:بنابراین فهرستی مانند codice_7 عبارت codice_8 است. می‌توان مکان را در چنین لیستی به عنوان تعداد مراحل از جلوی لیست تا مکان مورد نظر توصیف کرد. به‌طور رسمی‌تر، یک مکان در لیست تعداد عملیات codice_9 مورد نیاز برای بازسازی کل لیست از آن مکان خاص است. برای مثال، در codice_10 یک عملیات codice_11 و یک codice_12 برای بازسازی لیست مورد نیاز است. موقعیت X با نام codice_13 شناخته می‌شود. این ضبط همراه با مکان، نمایش زیپ شده از لیست یا زیپ لیست نامیده می‌شود.برای روشن بودن، یک مکان در لیست فقط تعداد عملیات codice_9 نیست، بلکه تمام اطلاعات دیگر در مورد آن codice_9 است. در این حالت، مقادیری که باید دوباره وصل شوند. در اینجا، این مقادیر ممکن است به راحتی در یک لیست جداگانه به ترتیب کاربرد از محل مورد نظر نشان داده شوند. به‌طور خاص، از متن "۳" در لیست codice_16 ، یک ضبط (که معمولاً به عنوان "مسیر" نامیده می‌شود) می‌تواند به عنوان codice_17 نشان داده شود که در آن codice_11 به دنبال آن codice_19 برای بازسازی لیست اصلی با شروع از codice_20 اعمال می‌شود.یک لیست زیپ همیشه کل ساختار داده را نشان می‌دهد. با این حال، این اطلاعات از منظر یک مکان خاص در آن ساختار داده است. در نتیجه، یک لیست زیپ جفتی است که هم از مکان به عنوان زمینه یا نقطه شروع و هم از یک ضبط یا مسیری تشکیل شده است که امکان بازسازی از آن مکان شروع را فراهم می‌کند. به‌طور خاص، فهرست زیپ codice_16 در محل "۳" ممکن است به صورت codice_22 نمایش داده شود. حال، اگر "۳" به "۱۰" تغییر یابد، آنگاه زیپ لیست تبدیل به codice_23 می‌شود. سپس فهرست ممکن است به‌طور مؤثر بازسازی شود: codice_24 یا مکان‌های دیگری که به آن‌ها رفته‌اند.با فهرستی که به این شکل نمایش داده می‌شود، تعریف عملیات نسبتاً کارآمد بر روی ساختارهای داده تغییرناپذیر مانند فهرست‌ها و درختان در مکان‌های دلخواه آسان است. به‌طور خاص، اعمال تبدیل زیپ به یک درخت، درج یا حذف مقادیر در هر مکان خاص در درخت را آسان می‌کند.زمینه‌ها و تمایز.نوع زمینه‌های یک زیپ را می‌توان از طریق از نوع اصلی که از طریق با مشتق حساب دیفرانسیل و انتگرال مرتبط است، ساخت. انواع بازگشتی که زیپ‌ها از آنها تشکیل می‌شوند را می‌توان به عنوان یک سازنده نوع یکنواخت در نظر گرفت. formula_1 . به عنوان مثال، با یک سازنده نوع بالاتر formula_2 که حداقل نقطه ثابت آرگومان خود را می‌سازد، یک درخت باینری بدون برچسب را می‌توان به صورت نمایش داد formula_3 و یک لیست بدون برچسب ممکن است شکل بگیرد formula_4 . در اینجا، نماد توان، ضرب و جمع به ترتیب با ، و مطابقت دارد، در حالی که اعداد طبیعی را برچسب گذاری می‌کنند. به این ترتیب، سازنده‌های نوع شبیه توابع چند جمله‌ای هستند formula_5 .بنابراین مشتق سازنده نوع را می‌توان از طریق این قیاس نحوی تشکیل داد: برای مثال یک درخت سه تایی بدون برچسب، مشتق سازنده نوع آن formula_6 معادل خواهد بود formula_7 ، مشابه استفاده از قواعد دیفرانسیل‌گیری و در حساب دیفرانسیل. نوع زمینه‌های زیپ روی یک نوع اصلی formula_8 معادل مشتق سازنده نوع اعمال شده برای نوع اصلی است، formula_9 .برای مثال، ساختار داده بازگشتی یک درخت باینری با گره‌هایی را در نظر بگیرید که یا از نوع هستند یا حاوی مقداری از نوع هستند:formula_10مشتق جزئی سازنده نوع را می‌توان به صورت محاسبه کردformula_11بنابراین، نوع زمینه‌های زیپ استformula_12به این ترتیب، متوجه می‌شویم که زمینه هر گره فرزند غیر نگهبان در درخت باینری برچسب‌گذاری شده، سه‌گانه است که شاملبه‌طور کلی، یک زیپ برای یک درخت از نوع formula_8 از دو بخش تشکیل شده است: فهرستی از زمینه‌های نوع formula_9 از گره فعلی و هر یک از اجداد آن تا گره ریشه، و مقدار نوع formula_8 که گره فعلی شامل می‌شود.استفاده.زیپ اغلب در جایی استفاده می‌شود که مفهوم یا حرکت به اطراف در مجموعه‌ای از داده‌ها وجود داشته باشد، زیرا معنای آن منعکس‌کننده حرکت به اطراف است اما به شیوه‌ای کاربردی غیر مخرب.از زیپ استفاده شده است درجایگزین‌ها و الحاقات.اصلاح مستقیم.در یک زبان برنامه‌نویسی غیر کاربردی، ممکن است ساده‌تر از ساختار داده اصلی عبور کرد و مستقیماً آن را اصلاح کرد (شاید پس از ، برای جلوگیری از تأثیرگذاری روی کدهای دیگر که ممکن است به آن ارجاع دهند).زیپ عمومی.زیپ عمومی تکنیکی برای دستیابی به همان هدفی است که زیپ معمولی با ثبت وضعیت پیمایش در ادامه هنگام بازدید از هر گره انجام می‌شود. (کد Haskell داده شده در مرجع از برنامه‌نویسی عمومی برای تولید تابع پیمایش برای هر ساختار داده استفاده می‌کند، اما این اختیاری است. - می‌توان از هر تابع پیمایش مناسب استفاده کرد)با این حال، زیپ عمومی شامل وارونگی کنترل است، بنابراین برخی از کاربردهای آن نیاز به یک ماشین حالات متناهی (یا معادل) برای پیگیری کارهای بعدی دارند.