"تنفيذ قائمة متعددة الأغراض" المرتبطة في ج

Question

هذا ليس بالضبط سؤال تقني، لأنني أعرف نوع C بما يكفي للقيام بالأشياء التي أحتاج إليها (أعني، من حيث عدم السماح باللغة في طريقك ")، لذلك هذا السؤال هو أساسا" ما الاتجاه لاتخاذ السؤال.

الوضع هو: أنا حاليا أخذ دورة خوارزميات متقدمة، ومن أجل "يكبر كبرامج المبرمجين"، من المطلوب استخدام C النقي C لتنفيذ المهام العملية (يعمل بشكل جيد: إلى حد كبير أي خطأ صغير تقوم به عليك أن تفهم تماما ما تفعله من أجل إصلاحه). في سياق التنفيذ، من الواضح أنني نفاد مشكلة الاضطرار إلى تنفيذ هياكل البيانات الأساسية "الأساسية" من الألف إلى الياء: في الواقع ليس فقط القوائم المرتبطة فقط، ولكن أيضا مداخن وأشجار وأشجار وآخرون.

أنا أركز على القوائم في هذا الموضوع لأنه عادة ما يكون بنية في نهاية المطاف استخدام الكثير في البرنامج، إما كهيكل "رئيسي" أو كهيكل "مساعد" لأكبر أخرى (على سبيل المثال، شجرة التجزئة التي تقرر النزاعات باستخدام قائمة مرتبطة).

يتطلب ذلك أن تخزن القائمة عناصر الكثير من أنواع مختلفة. أفترض هنا كأرضية لا أريد إعادة كود القائمة لكل نوع. لذلك، يمكنني التوصل إلى هذه البدائل:

• إجراء قائمة من مؤشرات الفراغ (Kinda inlegant؛ أصعب تصحيح)
• صنع قائمة واحدة فقط، ولكن وجود اتحاد ك "نوع عنصر"، يحتوي على جميع أنواع العناصر، وسأستعبه في البرنامج (أسهل في التصحيح؛ الفراغ المساحة إذا كانت العناصر ليست كلها بنفس الحجم)
• باستخدام ماكرو Preprocessor لتجديد التعليمات البرمجية لكل نوع، بأسلوب SGLIB., ، "تقليد" STL C ++ STL (إبداعي؛ لا تضيع المساحة؛ العناصر لديها نوع صريح فهي في الواقع عندما يتم إرجاعها؛ يمكن أن يكون أي تغيير في رمز القائمة دراماتيكي حقا)
• فكرتك / الحل

لجعل السؤال واضح: أي واحد من أعلاه هو الأفضل؟

ملاحظة: نظرا لأنني أساسيا في سياق أكاديمي، فأنا مهتم أيضا بإطلالة على الأشخاص الذين يعملون مع خالص ج هناك في هذه الصناعة. أفهم أن معظم مبرملي C النقي في منطقة الأجهزة المضمنة، حيث لا أعتقد أن هذا النوع من المشاكل التي أواجهها شائعة. ومع ذلك، إذا كان أي شخص يعرف كيف يتم ذلك "في العالم الحقيقي"، سأكون مهتما جدا برأيك.

Answer 1

أ void * هو القليل من الألم في قائمة مرتبطة منذ أن تضطر إلى إدارة تخصيصها بشكل منفصل إلى القائمة نفسها. نهج واحد استخدمته في الماضي هو الحصول على هيكل "متغير الحجم" مثل:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

الآن أدرك أن هذا لا نظرة حجم متغير ولكن دعونا تخصيص هيكل وهكذا:

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

الآن لديك عقدة أنه، لجميع النوايا والأغراض، يبدو أن هذا:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

أو في شكل رسومي (حيث [n] يعني n بايت):

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

وهذا هو، على افتراض أنك تعرف كيفية معالجة الحمولة بشكل صحيح. ويمكن القيام بذلك على النحو التالي:

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

هذا الخط المصبوب ببساطة يلقي عنوان payload شخصية (في tNode النوع) ليكون عنوانا tPerson نوع الحمولة.

باستخدام هذه الطريقة، يمكنك حمل أي نوع الحمولة التي تريدها في العقدة، حتى أنواع حمولة مختلفة في كل عقدة, ، دون المساحة الضائعة للاتحاد. يمكن رؤية هذه الهدر مع ما يلي:

union {
    int x;
    char y[100];
} u;

حيث يتم إهدار 96 بايت في كل مرة تقوم فيها بتخزين نوع عدد صحيح في القائمة (لعدد صحيح 4 بايت).

نوع الحمولة في tNode يتيح لك الكشف بسهولة عن نوع الحمولة التي تقوم بها هذه العقدة، لذلك يمكن أن يقرر رمزك كيفية معالجة ذلك. يمكنك استخدام شيء على غرار:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

أو (ربما أفضل):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Answer 2

بلدي $ 0.002:

• إجراء قائمة من مؤشرات الفراغ (DiseLegant كيندا؛ أصعب تصحيح)

هذا ليس هذا الاختيار السيئ، IMHO، إذا كان يجب عليك الكتابة في C. قد تضيف أساليب API للسماح للتطبيق بتوفير طريقة طباعة () لسهولة تصحيح الأخطاء. يمكن استدعاء طرق مماثلة عند إضافة العناصر (على سبيل المثال) عناصر أو إزالتها من القائمة. (بالنسبة للقوائم المرتبطة، هذا عادة غير ضروري، ولكن لمزيد من الهياكل المعقدة للبيانات - جداول التجزئة، على سبيل المثال) - يمكن أن يكون في بعض الأحيان حيوية.)

• إجراء قائمة واحدة فقط، ولكن وجود نقابة ك "نوع العنصر"، تحتوي على جميع أنواع العناصر التي سأستخدمها في البرنامج (أسهل في التصحيح؛ مساحة النفايات إذا كانت العناصر ليست كل نفس الحجم)

أود تجنب هذا مثل الطاعون. (حسنا، أنت تسأل.) وجود تبعية تجميعها يدويا، وتجميع الوقت من بنية البيانات لأنواعها الواردة هي أسوأ من جميع أنحاء العالم. مرة أخرى، IMHO.

• باستخدام ماكرو Preprocessor لتجديد التعليمات البرمز لكل نوع، في نمط SGLIB (SGLIB.SourceForge.net)، "تقليد" STL C ++ STL (إبداعي؛ لا تضيع المساحة؛ العناصر لديها نوع صريح فهي في الواقع عندما تكون يتم إرجاعها؛ أي تغيير في رمز القائمة يمكن أن يكون دراماتيكي حقا)

فكرة مثيرة للاهتمام، ولكن بما أنني لا أعرف SGLIB، لا أستطيع أن أقول أكثر بكثير من ذلك.

• فكرتك / الحل

سأذهب مع الخيار الأول.

Answer 3

لقد قمت بذلك في الماضي، في الكود الخاص بنا (تم تحويلها منذ ذلك الحين إلى C ++)، وفي ذلك الوقت، قررت في نهج الفراغ *. لقد فعلت ذلك للتو من أجل المرونة - كنا نوفر دائما مؤشرا دائما في القائمة على أي حال، وبساطة من الحل وسهولة الاستخدام تفوقها (بالنسبة لي) السلبي إلى النهج الأخرى.

ومع ذلك، كان هناك مرة واحدة حيث تسبب في بعض الأخطاء السيئة التي كان من الصعب تصحيح الأخطاء، لذلك ليس بالتأكيد حل مثالي. أعتقد أنه لا يزال الشخص الذي كنت أتناوله، رغم ذلك، إذا كنت أفعل ذلك مرة أخرى الآن.

Answer 4

باستخدام ماكرو Preprocessor هو الخيار الأفضل. ال قائمة Linux Kernel مرتبطة هو تطبيق ممتاز لقائمة مرتبطة دائرية في C. المحمولة للغاية وسهلة الاستخدام. هنا نسخة مستقل من Linux Kernel 2.6.29 List.h.

FreeBSD / OPENBSD SYS / قائمة الانتظار هو خيار جيد آخر لقائمة مرتبطة كورو عام

Answer 5

أنا لم أرمز ج منذ سنوات ولكن غليظ يدعي توفير "مجموعة كبيرة من مهام المرافق للأسلوت وهياكل البيانات الشائعة"، من بينها قوائم مرتبطة.

Answer 6

على الرغم من أنه من المغري التفكير في حل هذا النوع من المشكلات باستخدام تقنيات لغة أخرى، إلا أن الأجنبي، في الممارسة العملية نادرا ما يفوز. من المحتمل أن تكون هناك بعض الحلول المعلبة التي تحصل عليها بشكل صحيح في معظم الأوقات (وأخبرك في وثائقها عندما يحصلون على خطأ)، باستخدام ذلك قد يفتقد نقطة التنازل، لذلك أعتقد مرتين حول هذا الموضوع. بالنسبة لعدد قليل جدا من الحالات، قد يكون من القدر من الكريمة لفة خاصة بك، ولكن لمشروع أي حجم معقول، من غير المرجح أن يكون يستحق جهد التصحيح.

بدلا من ذلك، عند البرمجة في اللغة X، يجب عليك استخدام التعريفات باللغة x. لا تكتب Java عند استخدام Python. لا تكتب ج عند استخدام نظامه. لا تكتب C ++ عند استخدام C99.

نفسي، ربما انتهى بك الأمر باستخدام شيء مثل اقتراح Pax، ولكن في الواقع استخدام نقابة من Char [1] و Void * و Int، لجعل الحالات الشائعة مريحة (وعلم نوع غير متانع)

(ربما انتهى الأمر أيضا في تنفيذ شجرة فيبوناتشي، فقط السبب الذي يبدو أن أنيقا، ولا يمكنك فقط تطبيق أشجار RB عدة مرات قبل أن تخسر نكهةها، حتى لو كان ذلك أفضل للحالات الشائعة التي يمكن استخدامها ل .)

تعديل: بناء على تعليقك، يبدو أنك قد حصلت على حالة جيدة لاستخدام حل معلن. إذا سمح مدرسك بذلك، ويوفر بناء الجملة أنه يشعر بالراحة، فحطيه دوامة.

Answer 7

هذه مشكلة جيدة. هناك حلولان أحب:

• ديف هانسون واجهات C والتنفيذ يستخدم قائمة void * المؤشرات، وهو أمر جيد بما فيه الكفاية بالنسبة لي.

• لاجلي الطلاب, ، كتبت البرنامج النصي AWK لإنشاء وظائف قائمة خاصة بالنوع. وبعد بالمقارنة مع وحدات الماكرو قبل المعالج، فإنها تتطلب خطوة بناء إضافية، ولكن تشغيل النظام أكثر شفافية إلى المبرمجين دون الكثير من الخبرة. ويساعد حقا في اتخاذ القضية لعادة الأعمدة الحديثة، والتي يرونها لاحقا في مناهجها.

  إليك مجموعة واحدة من الوظائف تبدو:

  int      lengthEL (Explist *l);
  Exp*     nthEL    (Explist *l, unsigned n);
  Explist *mkEL     (Exp *hd, Explist *tl);
  

  البرنامج النصي AWK هو رعب 150 خط؛ يبحث رمز C ل typedefوتولد مجموعة من وظائف القائمة لكل واحد. أنها قديمة جدا؛ ربما يمكن أن أبقى أفضل الآن :-)

لن أعطي قائمة بالاتحابات وقت اليوم (أو الفضاء على القرص الصلب الخاص بي). انها ليست آمنة، وهي غير قابلة للتوسيع، لذلك قد تستخدم كذلك void * ويتم القيام به معها.

Answer 8

تحسن واحد على جعلها قائمة باطل * ستجعلها قائمة بالبيضات التي تحتوي على الفراغ * وبعض البيانات المتتتية حول ما يشير إليه الفراغ * بما في ذلك نوعه وحجمه، إلخ.

أفكار أخرى: تضمين مترجم بيرل أو LISP.

أو الذهاب في منتصف الطريق: رابط مع مكتبة بيرل وجعلها قائمة من perl svs أو شيء من هذا.

Answer 9

ربما أذهب مع الفراغ * نهج نفسي، لكنه حدث لي أنه يمكنك تخزين بياناتك ك XML. ثم يمكن للقائمة أن يكون لديك سحر * للبيانات (والتي ستتحليلها عند الطلب على أي عناصر فرعية تحتاجها) ....