Блог

Я работаю над проектом, который похож на адресную книгу. Во-первых, у нас есть несколько студентов в текстовом файле. Я собираюсь реализовать многосвязный список, у которого в этом списке есть 2 указателя head tail (указатель head tail для имени, фамилии). Эти указатели показывают один и тот же список, но в разных местах, потому что я добавляю узлы в порядке возрастания и использую двойные указатели для печати списка в обратном порядке. Проблема в том, что я реализовал список, добавив узлы по имени и фамилии, и операция проходит успешно, когда я вставляю еще один. Но я понял, что когда я удаляю узел по ее / его «имени» и снова печатаю список, ученик не существует, но когда я печатаю список по «фамилии», ученик существует. Затем я узнаю, что я реализовал два отдельных связанных списка. Мне сказали реализовать только ОДНУ функцию добавления и удаления. Но как я могу добавить узел по указателям на его имя и фамилии вместе? Я надеюсь, что я объяснил свою проблему понятно. Вот мои блоки кода.

Мои структуры:

 typedef struct node {
    int birth_date;
    int zipcode;
    int phone_num;
    char first_name[50];
    char last_name[50];
    char city[50];
    char address[50];
    char email_addr[50];

    struct node* fn_next;
    struct node* fn_pre;
    struct node* ln_next;
    struct node* ln_pre;
    struct node* birdat_next;
    struct node* birdat_pre;
} NODE;

typedef struct {
    int fn_count;
    int ln_count;

    NODE* fn_head;
    NODE* ln_head;

    NODE* fn_tail;
    NODE* ln_tail;
}LIST;
  

Блок кода, в котором я читаю файл построчно и вызываю функции добавления:

 while ( !feof(myfile) ) {
    NODE* pnew_stu;

    if( !(pnew_stu = (NODE*) malloc(sizeof(NODE))) ) {
        printf("ERROR NOT ENOUGH MEMORY!!!n");
        exit(100);
    }

    fscanf(myfile,"%s", amp;(pnew_stu->first_name) );
    fscanf(myfile,"%s", amp;(pnew_stu->last_name) );
    fscanf(myfile,"%s", amp;(pnew_stu->email_addr) );
    fscanf(myfile,"%d", amp;(pnew_stu->phone_num) );
    fscanf(myfile,"%s", amp;(pnew_stu->address) );
    fscanf(myfile,"%s", amp;(pnew_stu->city) );
    fscanf(myfile,"%d", amp;(pnew_stu->zipcode) );

    add_Node(list,pnew_stu);
}
  

И, наконец, мои функции добавления:

 void add_fn_Node(LIST* list, NODE* pnew_stu) {
    NODE* temp = list->fn_head;

    if( list->fn_head == NULL ) {
        pnew_stu->fn_next = list->fn_head;
        pnew_stu->fn_pre = list->fn_head;

        list->fn_head = pnew_stu;
        list->fn_count = 1;
        return;
    }
    else {
        if ( (strcmp( pnew_stu->first_name, temp->first_name )) <= 0 ) { // Basa Ekleme Kosulu
            pnew_stu->fn_next = temp;
            pnew_stu->fn_pre = temp->fn_pre;
            temp->fn_pre = pnew_stu;

            list->fn_head = pnew_stu;
            list->fn_count  ;   
            return;
        }
        else {
            while ( temp->fn_next != NULL ) { // Ortaya Ekleme Kosulu
                if ( (strcmp( pnew_stu->first_name, temp->first_name ) >= 0 ) amp;amp; (strcmp( pnew_stu->first_name, temp->fn_next->first_name) < 0)) {
                    pnew_stu->fn_next = temp->fn_next;
                    pnew_stu->fn_pre = temp;
                    temp->fn_next->fn_pre = pnew_stu;
                    temp->fn_next = pnew_stu;

                    list->fn_count  ;
                    return;
                }

                temp = temp->fn_next;
            }
            if ( temp->fn_next == NULL ) { // Sona Ekleme Kosulu
                temp->fn_next = pnew_stu;
                pnew_stu->fn_pre = temp;
                pnew_stu->fn_next = NULL;

                list->fn_tail = pnew_stu;
                list->fn_count  ;
                return;
            }
        }
    }
}

void add_ln_Node(LIST* list, NODE* pnew_stu) {
    NODE* temp = list->ln_head;

    if( list->ln_head == NULL ) {
        pnew_stu->ln_next = list->ln_head;
        pnew_stu->ln_pre = list->ln_head;

        list->ln_head = pnew_stu;
        list->ln_count = 1;
        return;
    }
    else {
        if ( (strcmp( pnew_stu->last_name, temp->last_name )) <= 0 ) { // Basa Ekleme Kosulu
            pnew_stu->ln_next = temp;
            pnew_stu->ln_pre = temp->ln_pre;
            temp->ln_pre = pnew_stu;

            list->ln_head = pnew_stu;
            list->ln_count  ;
            return;
        }
        else {
            while ( temp->ln_next != NULL ) { // Ortaya Ekleme Kosulu
                if ( (strcmp( pnew_stu->last_name, temp->last_name ) >= 0 ) amp;amp; (strcmp( pnew_stu->last_name, temp->ln_next->last_name) < 0)) {
                    pnew_stu->ln_next = temp->ln_next;
                    pnew_stu->ln_pre = temp;
                    temp->ln_next->ln_pre = pnew_stu;
                    temp->ln_next = pnew_stu;

                    list->ln_count  ;

                    return;
                }
                temp = temp->ln_next;
            }
            if ( temp->ln_next == NULL ) { // Sona Ekleme Kosulu
                temp->ln_next = pnew_stu;
                pnew_stu->ln_pre = temp;
                pnew_stu->ln_next = NULL;

                list->ln_tail = pnew_stu;

                list->ln_count  ;

                return;
            }
        }
    }
}
  

Мои функции удаления:

 void del_fn_name(LIST* list, char* str_key) {
    NODE* temp;

    int num,counter=1,flag;

    temp = list->fn_head;

    if( list->fn_head == NULL ) {
        printf("The list is EMPTY!!!n");
        return;
    }

    flag = search_fn(list,str_key);

    if ( flag ) {
        printf("Enter the number of student you want to delete : ");
        scanf("%d", amp;num);

        if( strcmp( list->fn_head->first_name, str_key ) == 0 ) { // Bastan Silme Kosulu
            if( num == counter ) {
                list->fn_head->fn_next->fn_pre = list->fn_head;
                list->fn_head = list->fn_head->fn_next;
                free(list->fn_head);

                printf("%s is deleted and the new header is %sn", str_key, list->fn_head->first_name );
                return;
            }
            counter  ;
        }
        temp = temp->fn_next;

        while ( temp->fn_next != NULL ) {
            if( strcmp( temp->first_name, str_key ) == 0 ) {
                if( num == counter ) {
                    temp->fn_pre->fn_next = temp->fn_next;
                    temp->fn_next->fn_pre = temp->fn_pre;
                    free(temp);
                    printf("%s deleted at between %s  and  %sn", str_key, temp->fn_pre->first_name, temp->fn_next->first_name);
                    return;
                }
                counter  ;
            }
            temp = temp->fn_next;
        }

        if( temp->fn_next == NULL ) { // Sondan Silme Kosulu
            if( strcmp(temp->first_name, str_key) == 0 ) {
                if( num == counter ) {
                    list->fn_tail = temp->fn_pre;
                    temp->fn_pre->fn_next = NULL;
                    free(temp);
                    printf("%s deleted at the end and new tail is %s n", str_key, list->fn_tail->first_name );
                    return;
                }
            }
        }
    }

void del_ln_name(LIST* list, char* str_key) {
    NODE* temp;
    int num,counter=1,flag;
    temp = list->ln_head;

    if( list->ln_head == NULL ) {
        printf("The list is EMPTY!!!n");
        return;
    }

    flag = search_ln(list,str_key);

    if ( flag ) {
        printf("Enter the number of student you want to delete : ");
        scanf("%d", amp;num);

        if( strcmp( list->ln_head->last_name, str_key ) == 0 ) { // Bastan Silme Kosulu
            if( num == counter ) {
                temp->ln_next->ln_pre = list->ln_head;
                list->ln_head = temp->ln_next;
                free(temp);

                printf("%s is deleted and the new header is %sn", str_key, list->ln_head->last_name );
                return;
            }
            counter  ;
        }
        temp = temp->ln_next;
        while ( temp->ln_next != NULL ) {
            if( strcmp( temp->last_name, str_key ) == 0 ) {
                if( num == counter ) {
                    temp->ln_pre->ln_next = temp->ln_next;
                    temp->ln_next->ln_pre = temp->ln_pre;
                    free(temp);

                    printf("%s deleted at between %s  and  %sn", str_key, temp->ln_pre->last_name, temp->ln_next->last_name);
                    return;
                }
                counter  ;
            }
            temp = temp->ln_next;
        }

        if( temp->ln_next == NULL ) { // Sondan Silme Kosulu
            printf("The last item %s second last item %sn", temp->first_name, list->fn_tail->fn_pre->first_name);*/
            if( strcmp(temp->last_name, str_key) == 0 ) {
                if( num == counter ) {
                    list->ln_tail = temp->ln_pre;
                    temp->ln_pre->ln_next = NULL;
                    free(temp);

                    printf("%s deleted at the end and new tail is %s n", str_key, list->ln_tail->last_name );
                    return;
                }
            }
        }
    }
  

Целые числа flag и counter предназначены для удаления повторяющихся студентов. Например, если есть три дубликата, он спрашивает меня, с каким номером ученика я хочу удалить. Итак, если я ввожу номер 2, это удаляет второй дубликат.

печать (поиск (тип=»клиент», код=random.randrange(1000))) печать(поиск(тип=»клиент», код=random.randrange(1000))) импорт системы sys.exit(1)

Ваш код кажется немного сложным для того, что необходимо, но идея правильная. Я не вижу никакой ошибки в методе insert, но довольно сложно следовать всем этим программам копирования и вставки. У вас могут быть ученики в нескольких разных списках одновременно, но я бы предложил использовать другой подход, чтобы избежать всего этого дублирования, что очень упрощает внесение ошибок.

Структура данных

Вы могли бы абстрагироваться от идеи ссылки и списка:

 typedef struct TList
{
    struct TLink *first, *last;
} List;

typedef struct TLink
{
    struct TStudent *student;
    struct TLink *prev, *next;
} Link;
  

List Структура — это любой из трех списков, которые вам нужны (имя, фамилия, дата рождения), и Link это любая из ссылок. Смотрите следующую картинку…

При таком подходе код для вставки / удаления ссылки в списке является общим для всех типов ссылок ( first_name , last_name , age ). Цена, которую приходится платить, — это дополнительный указатель на каждую ссылку и необходимость писать link->student->first_name вместо link->first_name .

Вставка / удаление ссылки

Добавление ссылки в список — это что-то вроде

 // Adds a new link before the link `before` or as last link
// if `before` is NULL
void addLink(List *list, Link *newlink, Link *before)
{
    newlink->next = before;
    newlink->prev = before ? before->prev : list->last;
    if (newlink->next) newlink->next->prev = newlink;
                  else list->last = newlink;
    if (newlink->prev) newlink->prev->next = newlink;
                  else list->first = newlink;
}
  

и удаление ссылки из списка — это что-то вроде

 void removeLink(List *lists, Link *link)
{
    if (link->next) link->next->prev = link->prev;
               else list->last = link->prev;
    if (link->prev) link->prev->next = link->next;
               else list->first = link->next;
}
  

Эти две функции могут использоваться для управления списками / ссылками всех трех типов (first_name, last_name и age) без какого-либо дублирования кода.

Вставка объекта Student

При таком подходе объект student может содержать все данные и множество объектов links

 typedef struct TStudent
{
    char first_name[NAMESIZE];
    char last_name[NAMESIZE};
    int age;
    Link first_name_link, last_name_link, age_link;
} Student;
  

Например, чтобы вставить ученика по порядку в first_name список, код становится

 Student *newstudent = ...
...
Link *before = first_name_list.first;
while (before != NULL amp;amp;
       strcmp(newstudent->first_name,
              before->student->first_name) > 0)
{
    before = before->next;
}
addLink(amp;first_name_list,
        amp;newstudent->first_name_link,
        before);
  

Пожалуйста, обратите внимание, что этот простой цикл корректно обрабатывает все случаи, которые в вашем коде вместо этого обрабатываются отдельно с помощью copy’n paste похожих инструкций (это первый вставленный ученик, последний, посередине).

Идея здесь в том, чтобы просто установить before узел первым в списке и продолжать перемещать его к следующему ученику, если вместо него нужно вставить новый.

Конечно, такой же цикл необходим, чтобы найти правильную точку вставки в двух других списках ( last_name_list и age_list ). С помощью указателей на функции можно было бы также исключить поиск точки вставки.

Удаление объекта Student

Для удаления a Student конечно, данные учащегося должны быть удалены из всех списков, другими словами, все три ссылки должны быть удалены. Это, однако, просто означает трехкратный вызов removeLink функции:

  removeLink(amp;first_name_list, amp;student->first_name_link);
 removeLink(amp;last_name_list, amp;student->last_name_link);
 removeLink(amp;age_list, amp;student->age_link);
 free(student);
  

Идиоматический ответ в C — просто использовать Boost.Мультииндекс. Это предназначено именно для добавления элементов с различными путями доступа (индексами) и поддержания синхронизации всех индексов.

Однако, если вы хотите переопределить мир, и если вы ограничены C (поскольку весь код, который вы представили до сих пор, является C, несмотря на тег), то я не знаю ни одной библиотеки, которая может предоставить это.

Вообще говоря, идея достаточно проста, особенно если достаточно простого списка. Как вы отметили в своем узле, вам просто нужна пара prev / next по индексу, в котором вы хотите сохранить узел.

Теперь, при добавлении узла, вам сначала нужно выделить его, затем определить местоположение точки вставки в каждом из индексов. Если все расположены и ошибка не возникает, то вы вставляете его в расположенную точку в каждом индексе, и структура теперь отвечает за управление памятью.

Аналогично, при удалении узла сначала нужно найти сам узел, затем удалить его из каждого индекса. Затем вы либо возвращаете его вызывающему ( pop подобным образом), либо освобождаете его самостоятельно.

это должно сработать:

 void add_Node(LIST* list,NODE* pnew_stu){
    add_fn_Node(list,pnew_stu);
    add_ln_Node(list,pnew_stu);
}

void remove_Node(LIST* list, NODE* pdead_stu){
    if(pdead_stu->fn_next){
        pdead_stu->fn_next->fn_pre=pdead_stu->fn_pre;
    }
    if(pnew_stu->fn_pre){
        pdead_stu->fn_pre->fn_next=pdead_stu->fn_next;
    }
    if(pnew_stu->ln_next){
        pdead_stu->ln_next->ln_pre=pdead_stu->ln_pre;
    }
    if(pnew_stu->ln_pre){
        pdead_stu->ln_pre->fn_pre=pdead_stu->ln_next;
    }
    if(list->fn_head==pdead_stu){list->fn_head=pdead_stu->fn_next;}
    if(list->ln_head==pdead_stu){list->ln_head=pdead_stu->ln_next;}
    if(list->fn_tail==pdead_stu){list->fn_tail=pdead_stu->fn_pre;}
    if(list->ln_tail==pdead_stu){list->ln_tail=pdead_stu->ln_pre;}
    list->fn_count--;
    list->ln_count--;
}