הגדרת טיפוס ב typedef ב C

[שניצל]

תאר לך שהייתה לך דרך להדליק, לכבות ולבדוק כל סיבית במספר באופן עצמאי, בלי קשר לסיביות האחרות. איך היית פותר את הבעיה?

[robicon]

טוב,הלכתי לאיבוד....

יש לך אתר עם הסבר טוב על הנושא?

[robicon]

אוקיי הבנתי מה אני אמור לעשות אבל לא איך...

התא הראשון במערך שווה 8 בייטים.

אני צריך לחלק אותו כך שכל בייט ייצג לי מספר שאני יכול לכבות ולהדליק אותו.

ואז תא 0 ייצג 0-7 תא 1 ייצג 8-15 וכו...

בשביל למצוא את מספר התא אני פשוט מחלק את המספר שקבלתי ב8 ובשביל למצוא את המקום שהוא נמצא ב8 בייטים אני עושה מודולו 8 על המספר.

מפה אני לא יודע איך להמשיך.

[שניצל]

מעולה. אז קודם כל תקרא את המדריך הבא על עבודה עם סיביות:

http://www.underwar.co.il/1-Programming/d195

אם זה נותן לך רעיון איך לפתור את הבעיה - אחלה. אם לא, תחזור אלינו וננסה לעזור.

[Maor_Splinter]

ה-ADT שכנראה מבקשים ממך לממש הוא Disjoint Sets (קבוצות זרות).

הפעולות הבסיסיות עליו הן:

MakeSet(x) - בנה קבוצה חדשה שנציגה הוא x וכוללת רק את x.

Find(x) - מיהו הנציג בקבוצה שאליה משתייך x.

Union(x, y)- איחוד הקבוצות שנציגהן x,y.

שני מבני נתונים למימוש הם:

1. יער של עצים. (המימוש בפועל מאוד יעיל, אם תרצה דוגמא למימוש תבקש)

2. רשימות משורשרות.

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

[שניצל]

לא, זה לא ה-ADT שמבקשים ממנו. הכוונה פה היא לייצוג של קבוצה ע"י מערך קומפקטי של ביטים (הרבה יותר יעיל מעץ).

שים לב שבשום מקום לא נדרש שהקבוצות יהיו זרות, וחוץ מזה הוא צריך לתמוך בפעולות על קבוצות כמו איחוד וחיתוך.

[robicon]

הבנתי מה אני אמור לעשות אבל לא הבנתי איך.

למשל אני מקבל את המספר 5. אני מחלק אותו ב8 ויודע שהוא אמור להיות בתא 0

עכשיו אני יודע שאני בתא 0 לעשות לו מודולו 8 ולדעת איזה ביט להדליק בכדי לסמן אותו. (6)

מה שאני לא יודע איך בעצם המצב ההתחלתי של התא?

ואיך אני ניגש לביט שאני רוצה להדליק?

[שניצל]

קראת את הלינק שנתתי לך לעבודה עם סיביות?

[robicon]

כן.

ואני מבין בערך את האופורטורים אבל אני לא יודע איך ליישם.

זאת אומרת שאני ניגש לתא שאני רוצה למשל לסמן בו 5 זה אמור להראות 00000100

בהתחלה התא הריק נראה כך 00000000?

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

[שניצל]

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

1. להדליק ביט (כלומר להפוך אותו ל-1).

2. לכבות ביט (כלומר להפוך אותו ל-0).

3. לבדוק האם ביט כבוי או דלוק (כלומר האם הוא 0 או 1).

אגב, כשסופרים את הביטים אז סופרים מימין לשמאל (דהיינו המקום ה-0 הוא הימני ביותר, וה-7 הוא השמאלי ביותר, במקרה של char).

1. כשעושים OR בינארי (לדוגמה ע"י z = x | y) אז התוצאה היא שהביטים הדולקים ב-z הם במקומות בהם היה ביט דולק ב-x או ב-y. אם ב-y יש רק ביט אחד דולק (לדוגמה כאשר y=1) אז כשנעשה x | y נקבל מספר שבו הביט הזה דולק, וכל שאר הביטים זהים למה שיש ב-x. לכן, הפעולה x |= y בעצם "מדליקה" את הביט הזה ב-x (במקרה של y=1 זה הביט הימני ביותר).

אז בשביל להדליק את הביט במקום ה-i, משתמשים ב-left shift (האופרטור >>). האופרטור "מזיז" את הביטים במספר שמאלה, ולכן אם ב-y=1 הביט הימני ביותר דולק (מה שקראנו לו מקום 0) אז ב-y<<i הביט במקום ה-i יהיה דולק (וכל השאר כבויים).

2. פה העקרון דומה, אבל עם AND בינארי. כשעושים z = x & y אז הביטים הדולקים ב-z הם במקומות שבהם היה ביט דולק ב-x וגם ב-y. אם באחד מהם הביט הוא 0, אז הביט במקום הזה ב-z הוא גם 0.

אם ניקח y שבו כל הביטים דלוקים פרט לאחד, אז x &= y בעצם "מכבה" את הביט הזה ב-x. איך מקבלים y כזה? כבר ראינו איך מקבלים y שבו ביט אחד בלבד דולק - אז אם נפעיל עליו not (האופרטור ~) נקבל מספר שבו כל הביטים דלוקים פרט לביט הזה.

3. כאן שוב נשתמש ב-AND. אם z=x&1 אז כל הביטים ב-z יהיו 0, פרט לימני ביותר שיהיה שווה לערכו של הביט הימני ב-x. ככה בעצם אפשר לבדוק אם הביט הזה שווה 0 או לא (אם x&1==0 או x&1==1). איך בודקים את המקומות האחרים? שוב באמצעות הזזה - הפעם right shift (האופרטור <<). הזזה ב-i מקומות ימינה תדאג לכך שהביט שהיה במקום ה-i נמצא עכשיו במקום ה-0.

[robicon]

קודם כל המון תודה על ההסברים.

אם הבנתי נכון... אני יכול ליצור משתנה מסוג char ולעשות or עם 1 ואז הוא יהיה שווה ל 00000001.

ולהזיז שמאלה ב i (שזה המודולו של המספר שקבלתי מהמשתמש)

ואז לשלוח את זה לפונקציה ולעשות or עם התא שבו אני רוצה להדליק אותו.

זה יעבוד?

[שניצל]

yup.

תשחק עם זה קצת, אפילו סתם עם דף ועט.

[robicon]

דבר ראשון תודה. הסתדרתי והבנתי איך לעבוד עם הביטים

עכשיו יש לי עוד בעיה קטנה.

יש לי פונקציה בשם read_set שהמטרה שלה זה לקרוא את הקלט מהמשתמש ולהכניס את המספרים לקבוצה מסוג set

הבעיה שלי זה שהקלט נראה למשל כך: read_set A,2,4,12,54,-1

read_set אמורה לקרוא לפונקציה....

A זה שם של קבוצה מסוג set (מוגדרת כבר) שאליה נכנסים המספרים עד 1-

אני יודע שאני צריך להשתמש ב fgets וב strtok

ושאלתי היא איך אני מבודד את ה A ? אני רוצה לקרוא עד ה A ואז לעשות בדיקה אם הוא מסוג set ואם כן להתחיל לסדר את המספרים בתוכו.

[שניצל]

לא הבנתי מה הכוונה בדיוק.

בעיקרון ברגע שקראת את כל השורה לתוך מחרוזת אמצעות fgets אתה יכול לעשות איתה מה שאתה רוצה - לפרק אותה לחלקים באמצעות strtok, לקחת תת מחרוזת באמצעות strncpy, להשוות למחרוזות אחרות באמצעות strcmp/strncmp וכן הלאה.

ולא הבנתי מה הכוונה בדיוק בלבדוק אם הוא מסוג set.

[robicon]

בניתי בעזרת typedef מערך של char בגודל 16

ובשביל לייצג קבוצות בניתי 6 קבוצות מהסוג הזה A,B,C,D,E,F

המשתמש מכניס בטרמינל פקודה כזאת: read_set A,2,4,12,54,-1

זאת אומרת שב קבוצה A אני אמור להכניס את המשתנים 2,4,12,54

הבעיה שלי זה שאני צריך ''לבודד'' את A בשביל לבדוק אם זה באמת סוג של קבוצה(אם המשתמש הכניס למשל W אז אני צריך לכתוב שזאת טעות)

ואז להמשיך לקרוא את הקלט ולהכניס אותו לתוך A.