لغة قائمة مرتبطة C مثيرة للاهتمام

Question

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

لنفترض أن لدينا سجل قائمة مرتبط محددًا على النحو التالي:

typedef struct _record
{
    char* value;
    struct _record* next;
} record;

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

void insert_sorted(record** r, const char* value)
{
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0)
        r = &((*r)->next); /* move r to point to the next field of the record */
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
}

عند استدعاء الدالة، يشير r إلى المؤشر الرئيسي للقائمة.أثناء حلقة while، يتم تحديث r للإشارة إلى next حقل السجل الذي يأتي مباشرة قبل النقطة التي نريد وضع السجل الجديد فيها.يقوم السطر الأخير من الوظيفة إما بتحديث مؤشر رأس القائمة (إذا حدث الإدراج في البداية) أو next مجال السجل السابق، وهو أمر رائع جدا.

بضعة أسئلة:

• هل لهذا المثل اسم أم أنه مذكور في أي كتاب؟

• هل يوجد مثلها في لغة C؟

اعتقدت أنني أعرف لغة C جيدًا وأنني اكتشفت المؤشرات والمراوغات بشكل جيد، لكن هذا الأمر استغرق مني بعض الوقت لأفهمه تمامًا.

Answer 1

لقد استخدمت شيئًا مشابهًا لهذا لإدراجه في شجرة ثنائية.لأنه عند تكرار الشجرة، عادة ما تتوقف عندما يصبح المؤشر NULL (لقد هربت من الشجرة).

إذن للإدراج، لديك 3 خيارات،

1:استخدم متغيرًا يتتبع القيمة السابقة للمؤشر التكراري.

2:توقف عندما يكون المؤشر الذي ستتبعه NULL قبل أن تتبعه، وهو يعمل ولكنه أقل أناقة قليلاً في رأيي.

3:أو الحل الأكثر أناقة هو ببساطة استخدام مؤشر إلى مؤشر، بحيث يمكنك فقط القيام بما يلي: *it = new_node(); وسوف إضافته حيث NULL اعتاد أن يكون في شجرتك.

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

Answer 2

أود أن أقول أن المصطلح هو "نوع الكود الذي أعطى "c" اسمًا سيئًا"

• ذكي بلا مبرر
• المدمجة بشكل غير مبرر
• آثار جانبية مفاجئة على المتصل
• لا يوجد خطأ في التعامل مع malloc
• يعمل فقط مع السلاسل الإنجليزية الأمريكية

Answer 3

لا أرى أي شيء يمكن أن أسميه مصطلحًا في حد ذاته.يبدو وكأنه ترميز قياسي عند التعامل مع هياكل البيانات في لغة C.

شكواي الوحيدة هي تعديل مؤشر المتصلين (*r).اعتمادًا على استخدام الوظيفة، أتوقع أن يكون هناك تأثير جانبي غير متوقع.إلى جانب إزالة التأثير الجانبي غير المتوقع، فإن استخدام متغير محلي للعب دور *r من شأنه أن يجعل التعليمات البرمجية أكثر قابلية للقراءة.

Answer 4

ماذا سيكون المصطلح هنا؟بالتأكيد ليس تنفيذ قائمة مرتبطة.استخدام المؤشر لبناء المؤشر؟الحلقة المدمجة؟

أنا شخصياً سأستخدم قيمة إرجاع المؤشر بدلاً من العمل على قيمة الإدخال.لأن رؤية نوع بيانات الإدخال هذا من شأنه أن يدق الجرس، مما يجعلني أنسخ القيمة الخاصة بي قبل تسليمها إلى وظيفتك.

Answer 5

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

الكود بالطريقة التي أكتبها عادة هو شيء على غرار

void insertIntoSorted(Element *&head, Element *newOne)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && less(curr, newOne)) {
    pp = &(pp->next);
  }
  newOne->next = *pp;
  *pp = newOne;
}

تحديث:

لقد نسيت الغرض الآخر من هذه الخدعة - وهو أكثر أهمية.يتم استخدامه لحذف العناصر من القوائم المرتبطة الفردية:

// returns deleted element or NULL when key not found
Element *deleteFromList(Element *&head, const ElementKey &key)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && !keyMatches(curr, key)) {
    pp = &(pp->next);
  }
  if (curr == NULL) return NULL;
  *pp = (*pp)->next; // here is the actual delete
  return curr;
}

Answer 6

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

في البداية، تكون دائمًا مرتبطة بشكل مزدوج لأن هذا يجعل الاجتياز في كلا الاتجاهين أسهل، لكل من عمليات المعالجة والإدراج/الحذف.

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

يصبح إدراج عقدة جديدة y قبل العقدة x أمرًا بسيطًا:

x -> prev -> next = y
y -> next = x
y -> prev = x -> prev
x -> prev = y

يعد حذف العقدة x أمرًا بسيطًا:

x -> prev -> next = x -> next
x -> next -> prev = x -> prev
free x

يتم ضبط الاجتياز لتجاهل الرأس والذيل الدخيلين:

n = head -> next
while n != tail
    process n
    n = n -> next

كل هذا يعمل على تسهيل فهم التعليمات البرمجية دون كل المعالجة الخاصة لحالات الحافة، على حساب بضع عقد من الذاكرة.

Answer 7

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

record* insert_sorted(const record* head, const char* value)

أنت تفتقد معالجة الأخطاء لحالة فشل malloc/strdup راجع للشغل.

Answer 8

تم تقديم هذا المصطلح في الفصل 12 من "مؤشرات على لغة C". ويستخدم هذا لإدراج عقدة في قائمة مرتبطة بدون رأس القائمة.

Answer 9

للإجابة على السؤال الأصلي، يُعرف هذا بالنهج الذي يركز على المؤشر بدلاً من النهج الذي يركز على العقدة الساذجة.الفصل 3 من "تقنيات البرمجة المتقدمة" بقلم ريكس بارزي متاح في amazon.com يتضمن مثالًا أفضل بكثير لتنفيذ النهج الذي يركز على المؤشر.

Answer 10

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

Element** previous = &firstElement, *current;
while((current = *previous)) {
    if(shouldRemove(current)) {
        *previous = current->next;  //delete
    } else {
        previous = &current->next;  //point to next
    }
}

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

Answer 11

على الرغم من الحيل، ألم يتغير دور المتغير "r"؟كيف يخبر المتصل ما هو "*r" بعد الاتصال؟أو بعد التنفيذ ما هو رأس القائمة؟

لم أستطع أن أصدق أنه يمكن تمثيل ذلك (حتى في بعض الكتب؟!).هل فوت اي شيء؟

إذا لم تقم بإرجاع أي مؤشر (كما اقترح الآخرون)، فأنا أقترح إجراء التغييرات التالية للحفاظ على دور الإدخال.

void insert_sorted(record** head, const char* value)
{
    record** r = head;
    bool isSameHead = false;
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0) {
        r = &((*r)->next); isSameHead = true; }
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
    if (!isSameHead) *head = newrec;
}

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

    void insert_sorted(record** head, const char* value)
    {
        record dummyHead;
        dummyHead.next = *head;
        record* r = &dummyHead;
        while(r->next) {
           if(strcmp(value, r->next->value) < 0) 
              break;
           r = r->next;}
        newrec = malloc(sizeof(record));
        newrec->value = strdup(value);
        newrec->next = r->next;
        r->next = newrec;
        *head = dummyHead.next;
    }