في مقابلة في TED 2016 (2:10 مساءً) ، تحدث Linus Torvalds عن أسلوب الترميز الجيد . كمثال ، يقدم خيارين لإزالة العناصر من القوائم المرتبطة بشكل فردي (انظر أدناه). الخيار الأول له حالة خاصة ، بينما الخيار الآخر ليس كذلك. يفضل لينوس هذا الأخير.



تعليقه:

[...] لا داعي للتفكير في سبب عدم وجود بيان إذا هنا. من المهم النظر إلى المشكلة من منظور مختلف وإعادة كتابتها بحيث تختفي الحالة الخاصة وتصبح حالة عادية ، وهذا رمز جيد . - ل. تورفالدس

يُظهر Linus رمزًا زائفًا بسيطًا إلى حد ما على غرار C كمثال. لكنها لا تقدم تفسيرًا مفاهيميًا. لذلك ، ليس من الواضح على الفور كيف يعمل المؤشر غير المباشر.



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

الرمز

يظهر الشكل الأساسي بنية البيانات لقائمة الأعداد الصحيحة المرتبطة بشكل فردي. 1.





التين. 1. قائمة من الأعداد الصحيحة مرتبطة بشكل منفرد.



الأرقام هي قيم صحيحة يتم اختيارها عشوائيًا ، وتتوافق الأسهم مع المؤشرات: head



 - هذا مؤشر نوع IntListItem*



، جميع الكتل هي أمثلة على بنية IntListItem



، لكل منها متغيرها الخاص ( next



في الكود) من النوع IntListItem*



، والذي يشير إلى العنصر التالي.



تنفيذ بنية البيانات في C:

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

أيضا (الحد الأدنى) API:

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

الآن دعونا نلقي نظرة على تطبيقات remove_cs101()



و remove_elegant()



. رمز الأمثلة لا يتعارض مع الرمز الزائف من مثال لينوس ، لكنه يجمع ويعمل.

النسخة الأساسية

الشكل: 2. نموذج مفاهيمي لهيكل بيانات القائمة في الخوارزمية الأساسية

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

في نهج موحد، واثنين من المؤشرات اجتياز cur



و prev



التي احتفال موقف اجتياز الحالي والسابق في القائمة، على التوالي. cur



يبدأ من رأس القائمة head



ويتقدم للأمام حتى يتم العثور على الهدف. في المقابل ، prev



يبدأ NULL



بالقيمة السابقة ويتم تحديثها لاحقًا إلى القيمة السابقة في cur



كل مرة تتحرك فيها للأمام. عندما يتم العثور على الهدف ، تتحقق الخوارزمية مما إذا لم يكن prev



صفراً. إذا كان الأمر كذلك ، فإنه cur



يشير إلى العنصر الأول في القائمة ، وفي هذه الحالة يعني الحذف تحريك رأس القائمة إلى الأمام.

حل أكثر أناقة

يحتوي الإصدار الأكثر أناقة على رمز أقل ولا يتطلب فرعًا منفصلاً لإزالة العنصر الأول في القائمة.

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

يستخدم الرمز مؤشرًا غير مباشر p



يحتوي على عنوان المؤشر لعنصر القائمة ، بدءًا من العنوان head



. في كل تكرار ، يتم توسيع هذا المؤشر ليشمل عنوان المؤشر إلى العنصر التالي في القائمة ، أي عنوان العنصر next



في العنصر الحالي IntListItem



. عندما يكون المؤشر إلى عنصر القائمة (*p)



متساويًا target



، فإننا نغادر حلقة البحث ونزيل العنصر من القائمة.

كيف تعمل؟

المؤشر غير المباشر له p



ميزتان مفاهيميتان:

1. يسمح لك بتفسير قائمة مرتبطة بطريقة head
   
   
   
   يصبح فيها المؤشر جزءًا لا يتجزأ من بنية البيانات. هذا يلغي الحاجة إلى حالة خاصة لإزالة العنصر الأول.
   
   
2. يسمح لك أيضًا بتقييم حالة الحلقة while
   
   
   
   دون الحاجة إلى تحرير المؤشر الذي يشير إليه target
   
   
   
   . يتيح لك ذلك تغيير المؤشر إلى target
   
   
   
   مكرر واحد والالتفاف حوله ، على عكس prev
   
   
   
   و cur
   
   
   
   .

دعونا نلقي نظرة على كل عنصر على حدة.

تكامل مؤشر الرأس

يفسر النموذج القياسي القائمة المرتبطة على أنها سلسلة من الأمثلة IntListItem



. يمكن الحصول على بداية التسلسل باستخدام مؤشر head



. هذا يؤدي إلى النموذج المفاهيمي الموضح في الشكل. 2. يتم head



التعامل مع المؤشر ببساطة على أنه مؤشر للوصول إلى بداية القائمة. prev



و cur



هي نوع مؤشرات IntListItem*



وتشير دائما إلى أو NULL



.



يستخدم التنفيذ الأنيق مخطط العنونة غير المباشر ، والذي يعطي رؤية مختلفة لهيكل البيانات:





الشكل. 3. نموذج مفاهيمي لهيكل بيانات القائمة في حل أكثر أناقة



هنا p



يمثل النوعIntListItem**



ويحتوي على عنوان المؤشر لعنصر القائمة الحالية. عندما يتحرك المؤشر إلى الأمام ، يتغير عنوانه إلى العنصر التالي.



في الكود ، يبدو مثل p = &(*p)->next



:

1. (*p)
   
   
   
   : dereference عنوان المؤشر لعنصر القائمة الحالية.
   
   
2. ->next
   
   
   
   : قم بإلغاء إشارة هذا المؤشر مرة أخرى وحدد الحقل بعنوان العنصر التالي.
   
   
3. &
   
   
   
   : خذ عنوان هذا الحقل (أي الحصول على مؤشر له).

يتبع هذا تفسير بنية البيانات ، حيث تكون القائمة عبارة عن سلسلة من المؤشرات إلى العناصر IntListItem



(الشكل 3).

اللمسة الأخيرة

من المزايا الإضافية لهذا التفسير المعين أنه يسمح بتحرير المؤشر next



لسلف العنصر الحالي طوال عملية الاجتياز .



إذا كان p



يحتوي على عنوان مؤشر لعنصر من عناصر القائمة ، فإن المقارنة في حلقة البحث تصبح:

while ((*p) != target) {
    ...
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

ستنتهي دورة البحث إذا كانت (*p)



متساوية target



، وبمجرد حدوث ذلك ، لا يزال بإمكاننا التغيير (*p)



، نظرًا لأننا نحتفظ بعنوانها p



. وبالتالي ، على الرغم من تكرار الحلقة حتى النهاية ، يتم تخزين واصف (عنوان الحقل next



أو المؤشر head



) يمكن استخدامه لتغيير المؤشر مباشرة إلى عنصر.



هذا هو السبب في أننا يمكن تغيير المدخلات إلى مؤشر عنصر للإشارة إلى موقع مختلف، وذلك باستخدام *p = target->next



، وبالتالي فإننا لا تحتاج مؤشرات الالتفافية prev



و cur



لإزالة العنصر.

تطبيق جديد

اتضح أنه يمكن تطبيق نفس الفكرة على تنفيذ مقتضب للغاية لوظيفة أخرى في القوائم المرتبطة: insert_before()



أي إدراج هذا العنصر قبل عنصر آخر.

الإدراج قبل العنصر الموجود

أولاً ، دعنا نضيف الإعلان التالي إلى list.h



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

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

إعادة هيكلة سريعة

قبل الانتقال ، دعنا نجعل حلقة البحث وظيفة منفصلة:

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

واستخدمه في remove_elegant()



:

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

إدراج () قبل التنفيذ

استخدامه find_indirect()



سهل التنفيذ insert_before()



:

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

ترضي الدلالات الصلبة لحالات الحافة بشكل خاص: إذا كانت before



تشير إلى رأس القائمة ، فسيتم إدراج عنصر جديد في البداية ، وإذا كان before



لاغياً أو غير صالح (أي غير موجود في l



) ، فسيتم إضافة عنصر جديد في النهاية.

خاتمة

الشرط الأساسي لحل أكثر أناقة لحذف العناصر هو تغيير بسيط واحد: مؤشر غير مباشر IntListItem**



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



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