Двусвязный в односвязный список

Тема в разделе "Общие вопросы по С и С++", создана пользователем Demonhunterus1, 17 окт 2010.

  1. Demonhunterus1

    Demonhunterus1 Гость

    Добрый день.Столкнулся с такого вот рода проблемой: необходимо переделать код программы,обрабатывающей двусвязный список,для работы с односвязными списками.Как ни пытался - ничего толком не получилось.Сам листинг программы:
    Код (C++):
    #include <iostream>
    #include <conio.h>
    #include <stdlib.h>
    #include <cstring>

    using namespace std;

    struct base {
    char fio [30]; // ФИО сотрудника
    char bolezn [50]; // Название болезни
    int dlit;        // Длительность болезни
    base *prev;   // Указатель на предыдущую запись
    base *next;   // Указатель на следующую запись
    };

    base *first = NULL; // Указатель на начало списка
    base *last = NULL; // Указатель на конец списка


    int List (void);  

    void AddItem (void)
    {
    base *db;

    // создаем новую структуру
    db = new base;
    // заполняем её
    cout << "Введите фамилию сотрудника: ";
    cin >> db->fio;
    cout << "Введите название болезни: ";
    cin >> db->bolezn;
    cout << "Введите длительность болезни: ";
    cin >> db->dlit;
    // добавляем в список
    if (last != NULL) // если список уже существует
    {
    db->prev = last;
    db->next = NULL;
    last->next = db;
    last = db;
    }
    else             // если список ещё не создан
    {
    db->prev = NULL;
    db->next = NULL;
    first = db;
    last = db;
    };
    }


    void DeleteItem (void)
    {
    // выводим список всех структур
    int i = List ();
    int num;

    cout << "Введите номер удаляемой записи ";
    cin >> num;
    if (num < 1 || num > i) return;

    base *db = first;
    // находим указатель на удаляемую структуру
    for (i = 1; i < num; i++)
    {
    db = db->next;
    }
    // удаляем её
    if (db)
    {
    if (db->prev) db->prev->next = db->next;
    if (db->next) db->next->prev = db->prev;
    if (db == first) first = first->next;
    if (db == last) last = last->prev;
    delete db;
    };
    }


    void Input (void)
    {
    bool enough = false;

    do
    {
    AddItem (); // заполняем очередную структуру
    cout << "Продолжить ввод информации? (y/n)" << endl;
    if (getch () == 'n') enough = true;
    }
    while (!enough);
    }


    void Find (void)
    {
    base *db = first;
    char name[20]=" ";
    int i=0;
    cout<<"Введите название болезни :";
    cin>>name;
    cout << "Результаты поиска:" << endl;
    while (db)
    {
    if (!strcmp(db->bolezn,name)) // проверяем запись
    {
    cout << db->fio << " "
    << db->bolezn << " "
    << db->dlit << endl;
    i++;
    }
    db = db->next; // переходим к следующей записи
    }
    if (i==0)cout<<"Поиск не дал результата";
    }


    int List (void)
    {
    base *db = first;
    int i = 0;

    cout << endl << "В списке содержатся:" << endl;
    while (db)
    {
    i++;
    cout << i << ". " << db->fio << " " << db->bolezn << " " << db->dlit << endl;
    db = db->next;
    }
    return i;
    }


    int Menu (void)
    {
    char ch = 0;

    // Выводим список возможных вариантов выбора
    cout << "Ваш выбор:" << endl;
    cout << "1. Сформировать список" << endl;
    cout << "2. Печать списка" << endl;
    cout << "3. Добавить в список" << endl;
    cout << "4. Удалить из списка" << endl;
    cout << "5. Поиск в списке" << endl;
    cout << "6. Выход" << endl;

    // ожидаем нажатия правильной клавиши
    while (ch < '1' || ch > '6')
    {
    ch = getch ();
    }

    // осуществляем выбор согласно набраной клавише
    switch (ch)
    {
    case '1': Input (); break;
    case '2': List (); break;
    case '3': AddItem (); break;
    case '4': DeleteItem (); break;
    case '5': Find (); break;
    case '6': return 0;
    };
    return 1;
    }

    int main (void)
    {
    while (Menu ()); // цикл,пока пользователь не выбрал Выход
    return 0;
    }
    Нашел ещё примеры нескольких соглашений,на основе которых можно описывать односвязный список,но как применить к этой программе - не знаю...
    1)Список циклический,никогда не бывает пустым:
    Код (C++):
    первая вставка: head->next = head;
    вставка t после x: t->next=x->next; x->next=t;
    удаление после x: x->next=x->next->next
    цикл обхода: t=head;
    do {... t=t>next;}
    while (t!=head);
    проверка на наличие лишь одного элемента: if (head->next==head)
    2)Ведущий указатель,null-указатель завершающего узла
    Код (C++):
    инициализация: head=0;
    вставка t после x: if (x==0) {head=t; head->next=0;}
    else {t->next=x->next;x->next=t;}
    Удаление после x: t=x->next; x->next=t->next;
    цикл обхода: for (t=head;t!=0;t=t->next)
    Проверка на пустоту: if (head=0)
    3)Фиктивный ведущий узел,null-указатель завершающего узла
    Код (C++):
    инициализация: head=new node;
    head->next=0;
    вставка t после x: t->next=x->next;x->next=t;
    удаление после x: t=x->next;x->next=t->next
    цикл обхода: for(t=head->next;t!=0;t=t->next)
    проверка на пустоту: if(head->next=0)
    Буду благодарен за любую помощь.
     
  2. Demonhunterus1

    Demonhunterus1 Гость

    Попытался что-то типа такого сделать,по второму соглашению для ввода,но после ввода 2х элементов - вылет програмы.
    Код (C++):
     if (first == NULL)
    { first=db;
    first->next=NULL;

    }
    else             
    {
    db->next=last->next;
    last->next=db;
    };
    }
     
  3. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Код твой почти не правил, просто немного адаптировал
    Код (C++):
    #include <iostream>
    #include <conio.h>
    #include <stdlib.h>
    #include <cstring>

    using namespace std;

    struct base {
    char fio [30]; // ФИО сотрудника
    char bolezn [50]; // Название болезни
    int dlit;        // Длительность болезни
    // base *prev;    // Указатель на предыдущую запись
    base *next;   // Указатель на следующую запись
    };

    base *first = NULL; // Указатель на начало списка
    base *last = NULL; // Указатель на конец списка


    int List (void);  

    void AddItem (void)
    {
    base *db;

    // создаем новую структуру
    db = new base;
    // заполняем её
    cout << "Введите фамилию сотрудника: ";
    cin >> db->fio;
    cout << "Введите название болезни: ";
    cin >> db->bolezn;
    cout << "Введите длительность болезни: ";
    cin >> db->dlit;
    // добавляем в список
    if (last != NULL) // если список уже существует
    {
    //db->prev = last;
    db->next = NULL;
    last->next = db;
    last = db;
    }
    else             // если список ещё не создан
    {
    //db->prev = NULL;
    db->next = NULL;
    first = db;
    last = db;
    };
    }


    void DeleteItem (void)
    {
    // выводим список всех структур
    int i = List ();
    int num;

    cout << "Введите номер удаляемой записи ";
    cin >> num;
    if (num < 1 || num > i) return;

    base *db = first;
    base *lastdel = NULL;
    // находим указатель на удаляемую структуру
    for (i = 1; i < num; i++)
    {  
    lastdel = db;
    db = db->next;
    }

    // удаляем её
    if (db)
    {
    if (db->next) //Удаление внутри списка
    {
    if (db == first) //Удаление первого элемента
    {
    first = db->next;
    }
    else //Если элемент не первый
    {
    lastdel->next = db->next;
    }
    }
    else //Удаление в конце списка либо единственного элемента
    {
    if (db == first) //Удаление первого элемента
    {
    first = NULL;
    last = NULL;
    }      
    else
    {
    lastdel->next = NULL;
    last = lastdel;
    }
    }

    delete db;
    };
    }


    void Input (void)
    {
    bool enough = false;

    do
    {
    AddItem (); // заполняем очередную структуру
    cout << "Продолжить ввод информации? (y/n)" << endl;
    if (getch () == 'n') enough = true;
    }
    while (!enough);
    }


    void Find (void)
    {
    base *db = first;
    char name[20]=" ";
    int i=0;
    cout<<"Введите название болезни :";
    cin>>name;
    cout << "Результаты поиска:" << endl;
    while (db)
    {
    if (!strcmp(db->bolezn,name)) // проверяем запись
    {
    cout << db->fio << " "
    << db->bolezn << " "
    << db->dlit << endl;
    i++;
    }
    db = db->next; // переходим к следующей записи
    }
    if (i==0)cout<<"Поиск не дал результата";
    }


    int List (void)
    {
    base *db = first;
    int i = 0;

    cout << endl << "В списке содержатся:" << endl;
    while (db)
    {
    i++;
    cout << i << ". " << db->fio << " " << db->bolezn << " " << db->dlit << endl;
    db = db->next;
    }
    return i;
    }


    int Menu (void)
    {
    char ch = 0;

    // Выводим список возможных вариантов выбора
    cout << "Ваш выбор:" << endl;
    cout << "1. Сформировать список" << endl;
    cout << "2. Печать списка" << endl;
    cout << "3. Добавить в список" << endl;
    cout << "4. Удалить из списка" << endl;
    cout << "5. Поиск в списке" << endl;
    cout << "6. Выход" << endl;

    // ожидаем нажатия правильной клавиши
    while (ch < '1' || ch > '6')
    {
    ch = getch ();
    }

    // осуществляем выбор согласно набраной клавише
    switch (ch)
    {
    case '1': Input (); break;
    case '2': List (); break;
    case '3': AddItem (); break;
    case '4': DeleteItem (); break;
    case '5': Find (); break;
    case '6': return 0;
    };
    return 1;
    }

    int main (void)
    {
    setlocale(LC_ALL,"Russian");   

    while (Menu ()); // цикл,пока пользователь не выбрал Выход
    return 0;
    }
     
Загрузка...
Похожие Темы - Двусвязный односвязный список
  1. b0006
    Ответов:
    0
    Просмотров:
    1.038
  2. koly
    Ответов:
    1
    Просмотров:
    1.292
  3. ЮрийПрп
    Ответов:
    1
    Просмотров:
    3.148

Поделиться этой страницей