לא מבינה משהו

[lovelyAnonymus]

לא מבינה משהו

אולי מישהו יכול להסביר לי את העיקרון של מימוש תור מעגלי? אני לומדת קורס באסמבלי והגעתי לנושא של תור מקלדת בזכרון הראשי, ויש שם תור שממומש בצורה מעגלית. (אבל גם מי שלא לומד אסמבלי מוזמן לנסות לעזור לי). אז ככה,בתור לא מעגלי יש שני מצביעים- מצביע ראש ומצביע זנב. הזנב בעצם אומר מהו המקום הפנוי הבא שאליו מכניסים את האיבר החדש. והראש אומר מאיפה יתחיל התור. זאת אומרת כשמוסיפים איבר, מכניסים אותו למקום של הזנב ומקדמים את הזנב תא אחד קדימה, ואם רוצים להוציא איבר מהתור, אז כל מה שעושים זה לקדם את הראש תא אחד קדימה ובכך בעצם להוציא את האיבר הכי ראשון מהתחום של התור. התור הרגיל הזה לא יעיל, כי יוצא שהוא תופס מקום לא מוגבל (כי הרי הוא לא חוזר להתחלה, הוא כל הזמן הולך קדימה), וזה יוצר בעיה, כי הזכרון במחשב (במקרה שלי 8086) הוא די מוגבל. אז השאלה הכללית שלי היא כזאת- מה צריך לשנות במנגנון התור הרגיל כדי לקבל את העיקרון של התור המעגלי? ובנוסף, יש לי גבולות קבועים שבינהם חייב התור להימצא.

 

[emmi25]

תור מעגלי

אני לא כל כך זוכרת אסמבלי אבל: כל איבר בתור הוא struct שמכיל את ה data ומכיל מצביע לאיבר הבא. התור הוא בעצם רשימה מקושרת - כל איבר מצביע על האיבר הבא אחריו. בתור רגיל, נניח שהוא לא ממויין, כשאת מוסיפה איבר בהכרח האיבר האחרון הנוכחי יצביע עכשיו על האיבר החדש והאיבר החדש יצביע על NULL כי הוא האחרון "החדש". מכיוון שאת רוצה תור מעגלי ולא תור רגיל - אז פעולת ההכנסה תהיה: האיבר החדש יצביע על מה שהאיבר האחרון הצביע (והוא תמיד מצביע על האיבר הראשון) והאיבר האחרון יצביע על האיבר החדש. את קודם משנה את ההצבעה של האיבר החדש כדי לא לאבד את ההצבעה לראש התור, כמובן. בתור כלי עזר: - את יכולה להחזיק מצביע שיכיל את הכתובת של האיבר הראשון. - את יכולה להחזיק גם מצביע שיכיל את הכתובת של האיבר האחרון. - את יכולה לשנות את האיברים כך שיכילו גם מצביע לאיבר שאחריהם, גם את ה data וגם את האיבר שלפניהם, אבל אז את מאריכה את הפעולה של ההוספה וההורדה של איברים בכל מקרה - זה פחות או יותר הרעיון. מקווה שעזרתי

 

[emmi25]

כמה הערות נוספות

- גם בתור רגיל את לא חייבת להחזיק מצביע לזנב, אבל זה אומר שכדי להגיע אליו את צריכה לרוץ על כל התור - בתור רגיל הורדה של איבר לא נעשית בהכרח מתחילת התור. לפעמים צריך להוציא איבר מהאמצע - שימי לב לזה שאת לא בהכרח משנה את המצביע לראש. - כנ"ל לגבי הכנסה של איבר. לפעמים את מוסיפה איברים לאמצע - כדי שבאמת לא ייגמר לך הזכרון - את חייבת שהתור יהיה עם הקצאות דינמיות (שוב - אני לא זוכרת איך עושים את זה באסמבלר) - את מקצה זכרון לכל איבר חדש ומשחררת זכרון כשאת מוחקת איברים (למשל - new ו delete ב C++) לגבי הגבולות הקבועים - מה שהם בעצם אומרים לך זה שכמות האיברים בתור היא מוגבלת, בהתאם לגודל שתופס איבר בזכרון. ככה את יכולה להחזיק איזשהו משתנה ולהוסיף לו 1 או להוריד ממנו 1 כשאת מכניסה או מוציאה איבר מהתור בהתאמה.

 

[lovelyAnonymus]

תודה לך שכיוונת אותי לרעיון

אבל המנגנון עצמו שתיארת מתאים יותר לשפה עילית, בג'אווה לדוגמא זה היה המנגנון של רשימה מקושרת ותור גם יחד. באסמבלי זה שונה לגמרי, שכן אי אפשר להוציא איבר מהאמצע, כל העיניין הוא להוציא רק מהראש ולהכניס רק אל הסוף. (כי את עובדת עם תור מקלדת).. בכל מקרה, כיוונת אותי לרעיון אחר... תודה =)

 

[emmi25]

תמיד שמחה לעזור ../images/Emo9.gif

אני יודעת שמה שכתבתי לא מתאים לאסמבלי... אני עבדתי עם C++...

 

[עדין ר]

לא למדתי אסמבלי

אבל נראה לי שמה שקורה הוא כזה דבר: בהכנסת איבר לתור, מכניסים אותו למקום של הזנב, ואז מקדמים את הזנב תא אחד, אלא אם הזנב מצביע לגבול העליון שהוקצה לתור, ובמקרה זה הזנב יצביע לגבול התחתון שהוקצה לתור. אם פעולה זו גורמת לכך שהזנב והראש באותו מקום (כלומר התור התמלא), אז הראש מקודם תא אחד. ככה יוצא שהאיבר הראשון בתור "נדרס" ועכשיו האיבר השני בתור הוא הראשון. בהוצאת איבר מהתור, מקדמים את הראש תא אחד, אלא אם הראש מצביע לגבול העליון שהוקצה לתור, ובמקרה זה הראש יצביע לגבול התחתון שהוקצה לתור.