ترتيب الهيكل على الأسماء (قائمة مرتبطة بشكل مضاعف)

Question

أحاول فرز بنيتي بناء على الأسماء (أبجديا).على سبيل المثال لدي هذا الهيكل:

struct person{
    char name[MAX];
    char num[MAX];
    char email[MAX];
    struct person *next;   
    struct person *previous;  
};

struct person *next, *first, *end;

وفي وظيفتي الرئيسية :

int main()
{
 struct person p = {{0}}
 .
 .
 .
 switch(choice)
    {
    case 1 : 
        printf("Name   : "); scanf("%s", &p.name);
        printf("Num : "); scanf("%s", &p.num);
        printf("E-Mail   : "); scanf("%s", &p.email);
        input(p); //function to input data    
        break;
    case 2 : 
        sort(p); //function to sort the data
        break;
               }
}

وفي وظيفة النموذج الأولي الخاص بي:

void sort(struct person p)
{
    struct person *ptr, *ptr2, *temp;

    ptr=first;
    ptr2=first;

    for (ptr= first; ptr!= NULL; ptr= ptr->next)
    {
        for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)
        {
            if (strcmp(ptr->name, ptr2->name) > 0)
            {
                temp = ptr;
                ptr= ptr2;
                ptr2= temp;
            }
        }
    }

}

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

Answer 1

الحلقة الداخلية

    for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)

يجب أن يكون

    for (ptr2= ptr->next; ptr2!= NULL; ptr2= ptr2->next)

(لاحظ ptr2 مقابل. ptr).

تحرير:

لن تعمل مؤشرات التبديل أيضا.يجب عليك إعادة الارتباط بالعناصر التي تتطلب متغيرات مساعدة في الحلقات.يمكن جعل الأشياء أكثر أناقة (- >التعامل مع رئيس القائمة) عند العمل مع المراجع:

static void swap(struct person **a, struct person **b)
{
    struct person       *tmp;

    if ((*a)->next)
        (*a)->next->prev = *b;

    if ((*b)->next)
        (*b)->next->prev = *a;

    tmp        = (*a)->prev;
    (*a)->prev = (*b)->prev;
    (*b)->prev = tmp;

    tmp        = (*a)->next;
    (*a)->next = (*b)->next;
    (*b)->next = tmp;

    tmp = *b;
    *b  = *a;
    *a  = tmp;
}

void foo()
{
    struct person **a;
    struct person *prev_a;

    for (a = &first; *a != NULL; a = &(prev_a->next)) {
        struct person **b;
        struct person *prev_b;

        prev_a = (*a)->prev;

        for (b = &(*a)->next; *b != NULL; b = &(prev_b->next)) {
            prev_b = (*b)->prev;

            if (strcmp((*a)->name, (*b)->name) > 0)
                swap(a, b);

            /* prev_b == NULL can not happen because inner loop is started
               in the middle of the list */
            prev_b = prev_b->next;
        }

        if (prev_a)
            prev_a = prev_a->next;
        else
            prev_a = first;
    }
}

تحرير:

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

     ,------------> HEAD ------------\
    | +------------     <-----------\  \ 
    | |                              |  |
    | `-> elem_n --> ... --> elem_0 -`  |
     `---        <-- ... <--        <---'

Answer 2

لا مبادلة المؤشرات والقيم المبادلة.أيضا ، تحتاج إلى تهيئة مؤشرات فارغة إلى NULL, ، فهي ليست افتراضيا.