Search on a bi-linked list



  • The file reads a body of copies of the contact structure. The two-track list is being developed. Function search() meets the entire list starting with the order number that the user enters. In order to save time on large lists, a search was made for the element from the two sides (depending on the location of the list element) at the entrance to the head list, but at the end of the list, a mistake was made, as the first element was on the list. How can you fix this mistake?

    #include "stdafx.h"
    #include<cstdlib>
    #include<string.h>
    #include<iostream>
    

    struct contact
    {
    char nomer[50];
    char adress[50];
    char sname[50];
    };

    struct Node
    {
    char nomer[50];
    char adress[50];
    char sname[50];
    Node *next, *prev;
    };typedef Node *PNode;

    PNode CreateNode(contact buf)
    {
    PNode NewNode = new Node;
    strcpy(NewNode->nomer, buf.nomer);
    strcpy(NewNode->adress, buf.adress);
    strcpy(NewNode->sname, buf.sname);
    NewNode->next = NULL;
    NewNode->prev = NULL;
    return NewNode;
    }

    void AddNode(PNode &Head, PNode &Tail, PNode NewNode)
    {
    NewNode->next = NULL;
    NewNode->prev = Tail;
    if (Tail) Tail->next = NewNode;
    Tail = NewNode;
    if (!Head) Head = Tail;
    }

    void AddAfter(PNode &Head, PNode &Tail, PNode p, PNode NewNode)
    {
    if (p==Tail)
    {
    NewNode->prev = Tail;
    Tail = NewNode;
    }
    NewNode->next = p->next;
    NewNode->prev = p;
    if (p->next)
    p->next->prev = NewNode;
    p->next = NewNode;
    Tail= NewNode;// add
    }
    void AddBefore(PNode &Head, PNode &Tail, PNode p, PNode NewNode)
    {
    if (Head == p)
    {
    NewNode->next = Head;
    Head = NewNode;
    }
    else
    {
    NewNode->prev = p->prev;
    NewNode->next = p;
    p->prev->next = NewNode;
    p->prev = NewNode;
    }
    }

    void ShowTwoLinkedList(PNode Head)
    {
    PNode p = Head;
    while (p != NULL)
    {
    printf("%s\n", p->sname);
    p = p->next;
    }
    fflush(stdin);
    getchar();
    }

    void AddAndSort(contact buf, PNode Head, PNode Tail)
    {
    PNode NewNode = CreateNode(buf);
    PNode p = Head;
    while (p->next && (strcmp(p->sname, NewNode->sname) < 0))
    p = p->next;
    if ((strcmp(p->sname, NewNode->sname) < 0))
    AddAfter(Head, Tail, p, NewNode);
    else
    AddBefore(Head, Tail, p, NewNode);
    }
    int Search(PNode Head,PNode Tail,int NumOfPosition, int kol_el)
    {
    if ((NumOfPosition < 1) || (NumOfPosition > (kol_el)))
    {
    printf("Ошибка:некорректный ввод позиции в списке.\n");
    return -1;
    }
    else if (kol_el / 2 >= NumOfPosition)
    {//cлева
    int count = 1;
    PNode p = Head;
    while (count != NumOfPosition)
    {
    p = p->next;
    count++;
    }
    system("cls");
    printf("Информация по запросу:\n");
    while (p->next)
    {
    printf("%s\n", p->sname);
    printf("%s\n", p->adress);
    printf("%s\n", p->nomer);
    printf("\n\n");
    p = p->next;
    }
    system("pause");
    }
    else
    {
    //справа
    int count = kol_el;
    PNode p = Tail;
    while (count != NumOfPosition)
    {
    p = p->prev;
    count--;
    }
    system("cls");
    printf("Информация по запросу:\n");
    while (p->next)
    {
    printf("Информация по запросу:\n");
    printf("%s\n", p->sname);
    printf("%s\n", p->adress);
    printf("%s\n", p->nomer);
    printf("\n\n");
    p = p->next;
    }
    system("pause");

        }
    

    }

    int main()
    {
    setlocale(LC_ALL, "RUS");
    int rezh;
    PNode Head = NULL;
    PNode Tail = NULL;
    FILE *f;
    f = fopen("telbook.dat", "r+b");
    fseek(f, 0, SEEK_END);
    int size = ftell(f);
    int kol_el = size / sizeof(contact);
    contact *buf = new contact[kol_el];
    fseek(f, 0, SEEK_SET);
    fread(buf, sizeof(contact), kol_el, f);
    fclose(f);
    do {
    system("cls");
    const int NotUsed = system("color 03");
    printf("Выберите действие:\n");
    printf("1.Показать список.\n");
    printf("2.Создание+сортировка.\n");
    printf("3.Поиск по списку.\n");
    printf("4.Выйти из программы.\n");
    scanf_s("%d", &rezh);
    switch (rezh)
    {
    case 1:
    {
    ShowTwoLinkedList(Head);
    break;
    }

        case 2:
        {
            PNode NewNode = CreateNode(buf[0]);
            AddNode(Head, Tail, NewNode);
            for (int i = 1; i &lt; kol_el; i++)
                AddAndSort(buf[i], Head, Tail);
            break;
        }
    
        case 3:
        {
            system("cls");
            printf("Введите номер:\n");
            int NumOfPosition;
            scanf("%d", &amp;NumOfPosition);
            Search(Head,Tail,NumOfPosition,kol_el);
        }
        }
    } while (rezh != 4);
    system("pause");
    return 0;    
    



  • Smoke with the signs. Each element of your list shall be marked on the following and the previous (except the head, which does not have the previous one, and the last one which does not have the following). Well, I figured it out.

    1. You've got a method. AddAfter There is a continuous census of the end of the list to a new element where errors with the indexes come from. In method AddBefore It's mutto, too.
    2. Search, method Search♪ Stroke while (p->next) As long as there's always a way to detect the last element, the search will be until the last element on the list.
    3. The main cycle with the menu is at the beginning. system("cls"); to clean the screen. When the contents of the list are placed on the screen, the contents shall be displayed and the screen shall be cleaned, the same delay may be added as the search.

    The code is:

    void AddAfter(PNode &Head, PNode &Tail, PNode& p, PNode NewNode)
    {
        // Для добавляемой ноды устанавливаем указатели на следующую и предыдущую ноды списка
        NewNode->next = p->next;
        NewNode->prev = p;
    
    // Для ноды, следующей ЗА замещаемой, изменяем указатель на предыдущую ноду
    if (p-&gt;next)
        p-&gt;next-&gt;prev = NewNode;
    
    // Для замещаемой ноды изменяем указатель на следующую ноду
    p-&gt;next = NewNode;
    
    // Если это конец списка, то перезаписываем указатель конца списка
    if (p == Tail)
        Tail = NewNode;
    

    }

    void AddBefore(PNode &Head, PNode &Tail, PNode& p, PNode NewNode)
    {
    // Для добавляемой ноды устанавливаем указатели на следующую и предыдущую ноды списка
    NewNode->next = p;
    NewNode->prev = p->prev;

    // Для ноды, следующей ПЕРЕД замещаемой, изменяем указатель на следующую ноду
    if (p-&gt;prev)
        p-&gt;prev-&gt;next = NewNode;
    
    // Для замещаемой ноды изменяем указатель на предыдущую ноду
    p-&gt;prev = NewNode;
    
    // Если это начало списка, то перезаписываем указатель начала списка
    if (p == Head)
        Head = NewNode;
    

    }

    In Search, replace while (p->next)while (p)




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2