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

[robicon]

אני צריך לייצר טיפוס בשם set שמסוגל להחזיק קבוצת שלמים בתחום [127....0] ,על המבנה להיות יעיל מבחינת כמות הזכרון הנדרשת לשמירתו (עבודה עם סביות).

איך אני עושה את זה הכי יעיל?

תודה.

[שניצל]

תחשוב איזה "מידע" המבנה הזה בעצם צריך לשמור. מה המידע שצריך להישמר לכל מספר בתחום בין 0 ל-127? תתחיל מפתרון יותר נאיבי ותחשוב איך בדיוק לשפר אותו.

[robicon]

אני אמור לקבל מהמשתמש רשימה של מספרים שהמספר הכי גבוהה יכול להיות 127 והכי נמוך 0

כל איבר בקבוצה מופיע רק פעם אחת.

אני אמור לייצר כמה טיפוסים מ set שיכילו מספרים ואז לעשות עליהם פעולות על קבוצות (חיתוך איחוד וכו..)

לכן חשבתי על מערך בגודל 127 ואז כל מספר שאני מקבל מהמשתמש אני מכניס למשל 1 בתא של אותו מספר

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

השאלה אם זה נכון ואם זה יעיל?

[שניצל]

בבסיס אתה צודק - מערך בגודל 128 שאתה שם בו 0 עבור כל מספר שלא נמצא בקבוצה, ו-1 עבור כל מספר שכן נמצא בקבוצה.

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

[robicon]

אפשר לייעל על ידי מערך של char

אבל באיזה גודל...

[שניצל]

על איזה אתה צריך לחשוב בעצמך.

כמה מידע צריך לשמור לכל מספר בין 0 ל-127? כמה מידע צריך סה"כ?

[robicon]

בסופו של דבר שורת פלט לקבוצה תיהיה לכל היותר עד 16 איברים.

אז ההגיון אומר לעשות מערך של 16

נראה לי שצריך בסופו של דבר לדחוס 128 בייטים ל 16 בייטים.

אבל אני לא יודע מה קורה עם המשתמש מכניס מעל ל16 מספרים שונים...

[שניצל]

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

איזה מידע צריך להחזיק עבור כל מספר בין 0 ל-127? כמה מידע זה? (ביט? בייט? int?)

[robicon]

הכי יעיל....

כנראה בייט

[robicon]

אוקיי אני יודע שזה אמור להיות:

#defin size 16
typedef unsigned char set [size];

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

[שניצל]

מה הגודל של char אחד? כמה מידע אפשר להחזיק בו?

[robicon]

8 ביטים לפחות

טווח ערכים מינימאלי 0~127

[שניצל]

לא לפחות - בדיוק.

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

[robicon]

אין לי מושג ....

הידע שלי בעבודה עם סיביות נמוך מאוד

[opbenesh]

יש בשפת C כמה אופרטורים שנקראים bitwise operations (למשל, | ו->>).

אני ממליץ לך לקרוא עליהם, ובעיקר - על מה אפשר לעשות איתם.