[Powered by Google Translate] [תור] [כריס גרבר, אוניברסיטת הרווארד] זה CS50, CS50.TV] מבנה נתונים שימושי אחד לאחסון לאוסף מסודר של אלמנטים הוא תור. הוא משמש כאשר אלמנטי הצורך להסירו באותו הסדר שהם הוסיפו. מושג זה נקרא FIFO, שהוא ראשי התיבות הראשונות בראשון שיצא. כדי לעזור להמחיש זאת, זה עשוי להיות שימושי לתמונה בתור לקופה בחנות. כשאנשים יגיעו, הם מחכים בחלק האחורי של הקו. הקופאי לוקח תורות המשרתים את הלקוחות בחזית, שלאחר מכן צא מהשורה אחת בכל פעם. במדעי מחשב, אנו מתייחסים לראש התור כראש ועוד בזנב. דוגמה לעת אנו עשויים להשתמש ביישום היא רשימת המתנה להרשמות ייצוגיות. כמושבים הפכו זמינים בכיתה, האדם בראש רשימת ההמתנה ספק את ההזדמנות להירשם לכיתה. 

תור ניתן לבנות באמצעות כל אוסף מאחסן נתונים במטרה, כגון מערך או רשימה מקושרת. יחד עם האוסף כדי לאחסן את הפריטים בתור, אנו זקוקים גם לשיטה להוספת פריטים בסוף התור, אשר נקרא enqueuing, ואחר כדי להסיר פריט מראש התור, אשר נקרא dequeuing. זה בדרך כלל מועיל לכלול שיטה אחרת כדי להחזיר את האורך הנוכחי של התור כמו גם שיטה לבדוק אם התור ריק. בואו נסתכל כיצד תוכל ליישם את התור של מספרים שלמים בשפת C, באמצעות מערך לאוסף של אלמנטים. ראשית, אנו יוצרים מבנה המכונה תור להחזיק המשתנים שלנו. אנו נשתמש במערך מדד 0 קבוע בגודל של מספרים שלמים כדי לאחסן את האלמנטים. אנחנו נכלול גם ראש משתנה בשם שמאחסן את האינדקס של האלמנט שנמצא כעת בראש התור. משתנה שלישי, הנקרא אורך, ישמש כדי לעקוב אחר מספר האלמנטים במערך. כחלופה, אתה יכול לשקול שימוש בזנב, שנקרא משתנה כדי להצביע על מרכיב השדה האחרון במערך. לפני שנכתוב עוד קוד, בואו לנסות את העיצוב שלנו. בואו נתחיל עם מערך ריק של אורך 0, עם הראש מוגדר 0. עכשיו Enqueue 4 ערכים בואו - 6, 2, 3, ו 1. האורך עכשיו יהיה 4, והראש יישאר על 0. 

מה קורה אם אנחנו dequeue ערך? אנחנו נפחית את האורך עד 3, להגדיר עד ראש 1, ולהחזיר את הערך 6. קוד זה עשוי להיראות כך. כאן יש לנו את פונקצית dequeue, אשר לוקח את מצביע לתור - ש - ומצביע לאלמנט, שהוא הסוג int. ראשית עלינו לבדוק את אורך התור, כדי לוודא שזה יותר מ 0, על מנת להבטיח שיש אלמנט שdequeued. ואז אנחנו מסתכלים במערך האלמנטים, בראש העמדה, ולהגדיר את הערך של אלמנט להיות הערך במיקום זה. אז תחליף את הראש להיות המדד הבא % הקיבולת. אז אנו מפחיתים את אורך התור על ידי 1. לבסוף, אנו החזר אמיתיים כדי לציין שdequeue היה מוצלח. אם אנחנו dequeue שוב, האורך יהיה 2, הראש גם יהיה 2, ואת ערך ההחזרה יהיה 2. 

מה קורה אם אנחנו Enqueue ערך אחר כגון 7? כפי שהיינו בסוף התור, נצטרך לעטוף ולאחסן את הערך 0 באלמנט של המערך. מבחינה מתמטית, זה יכול להיות מיוצג על ידי הוספת האורך למדד של הראש וביצוע מודולוס באמצעות קיבולת התור. כאן שהם 2 +2, שהיא 4% 4, אשר הוא 0. מתרגם את הרעיון הזה לקוד שיש לנו בפונקציה זו. כאן אנו רואים את פונקצית Enqueue, אשר לוקח את מצביע לתור - ש - ולוקח את האלמנט שenqueued, שהיא מספר שלם. הפעם הבאה שנבדוק כדי לוודא שהקיבולת של התור עדיין גדול מהאורך הנוכחי של התור. בשלב בא, אנו מאחסנים את האלמנט במערך האלמנטים במדד אשר נקבע על ידי הראש +% אורך הקיבולת של התור. לאחר מכן, אנו מגדילים את אורך התור ב1, ולאחר מכן לחזור לנכון להצביע על כך שפונקצית Enqueue הייתה מוצלחת. 

בנוסף לשני התפקידים שהזכרנו, יש שתי פונקציות נוספות. הראשון הוא פונקצית isempty, אשר לוקח את מצביע לתור ומוודא שהאורך הוא 0. השני הוא פונקצית האורך, שגם לוקח מצביע לתור ומחזיר את האורך הנוכחי מstruct. סקירה קצרה זו הוכיחה מימוש אפשרי אחד של תור. אחת המגבלות ליישום זה הוא שהתור יש גודל מקסימאלי קבוע. אם ננסה להוסיף עוד אלמנטים מהתור יכול להכיל, ייתכן שנצטרך להתעלם מהבקשה ושחרר את האלמנט, או שאולי תעדיפו לחזור איזה סוג של שגיאה. שימוש ברשימה מקושרת ולא במערך יקל לגודל באופן דינמי את התור. עם זאת, מאחר שאין לנו גישה ישירה לאלמנטים של רשימה מקושרת, אם אנחנו לא לעקוב אחר הזנב, היינו צריכים לסרוק את כל הרשימה המקושרת כדי להגיע לסוף בכל פעם. גם אנחנו יכולים לשקול את שימוש מערך של נתונים מסוג אחר, כגון structs, ליצור תורים של אלמנטים יותר מורכבים. מחשבה לאחור לדוגמא לרשימת המתנה של מחלקה שלנו, מבנים אלה יכולים לייצג את התלמידים הבודדים. 

השם שלי הוא כריס גרבר, וזה CS50. [CS50.TV] וחוזר בזמן - עוד >> אחת. והחזר אמיתי כדי לציין ש-- התור היה מוצלח. -% הקיבולת של התור - זה הולך להיות כיף בעריכה. [שחוק]