В двусвязном списке продублировать те элементы, которые меньше следующ

Тема в разделе "C/C++/C#", создана пользователем gvenog, 13 дек 2010.

  1. gvenog

    gvenog New Member

    Регистрация:
    13 дек 2010
    Сообщения:
    3
    Симпатии:
    0
    В двусвязном списке продублировать те элементы, которые меньше следующего, но больше больше предыдущего.

    Код (C++):
    #include "stdafx.h"
    #include <iostream>
    #include <cstdlib>
    using namespace std;

    struct LIST {
    int info;
    LIST *next;
    LIST *prev;


    };

    LIST *head;
    int n1, n2;

    void Initial()
    {
    head = new LIST;
    head->next=head;
    head->prev=head;


    }

    int Empty()
    {
    if (head->next==head && head->prev==head)
    return 1;
    else
    return 0;


    }

    LIST *SearchOnward(int num)
    {
    LIST *tmp=head->next;
    while(tmp!=head && tmp->info!=num)
    {
    tmp=tmp->next;
    n1+=1;
    }
    if (tmp!=head)
    return tmp;
    else
    return NULL;


    }

    LIST *SearchBack(int num)
    {
    LIST *tmp=head->prev;
    while(tmp!=head && tmp->info!=num)
    {
    tmp=tmp->prev;
    n2+=1;
    }
    if (tmp!=head)
    return tmp;
    else
    return NULL;


    }

    int Del(int num)
    {
    LIST *current=SearchOnward(num);
    if (current!=NULL)
    {
    current->prev->next=current->next;
    current->next->prev=current->prev;
    delete current;
    return 1;
    }
    return 0;


    }

    int AddAfter(int num, int point)
    {
    if (Empty()==1)
    {
    LIST *tmp=new LIST;
    tmp->next=head;
    tmp->prev=head;
    tmp->info=num;
    head->next=tmp;
    head->prev=tmp;
    return 1;
    }
    LIST *current=SearchOnward(point);
    if (current!=NULL)
    {
    LIST *tmp=new LIST;
    tmp->next=current->next;
    tmp->prev=current;
    tmp->info=num;
    current->next->prev=tmp;
    current->next=tmp;
    return 1;
    }
    return 0;


    }

    int AddBefore(int num, int point)
    {
    LIST *current=SearchBack(point);
    if(current!=NULL)
    {
    LIST *tmp=new LIST;
    tmp->info=num;
    tmp->next=current;
    tmp->prev=current->prev;
    current->prev->next=tmp;
    current->prev=tmp;
    return 1;
    }
    return 0;


    }

    void ShowOnward()
    {
    LIST *tmp=head->next;
    cout << endl << "В прямом направлении:" << endl;
    while(tmp!=head)
    {
    cout << tmp->info << " ";
    tmp=tmp->next;
    }
    cout << endl;


    }

    void ShowBack()
    {
    LIST *tmp=head->prev;
    cout << endl << "В обратном направлении:" << endl;
    while(tmp!=head)
    {
    cout << tmp->info << " ";
    tmp=tmp->prev;
    }
    cout << endl;


    }

    int Double()
    {
    }

    int main()
    {
    setlocale(LC_ALL,"Russian");
    Initial();
    int num, tmp;
    char otv, otv2;
    do
    {
    cout << "1. Добавление" << endl
    << "2. Удаление" << endl
    << "3. Вывод"<< endl
    << "4. Поиск" << endl
    << "5. Дублирование" << endl
    << "0. Выход" << endl
    << " = ";
    cin >> otv;
    switch(otv)
    {
    case '1':
    cout << endl << "Введите элемент = ";
    cin >> num;
    if (Empty()==1)
    {
    AddAfter(num,0);
    cout << endl << "Элемент добавлен" << endl;
    }
    else
    {
    cout << endl << "1. Добавить перед"
    << endl << "2. Добавить после"
    << endl << " = ";
    cin >> otv2;
    switch(otv2)
    {
    case '1':
    cout << endl << "Перед каким элементом добавить = ";
    cin >> tmp;
    if (AddBefore(num,tmp)==1)
    cout << endl << "Элемент добавлен" << endl;
    else
    cout << endl << "Такого элемента не существует" << endl;
    break;


    case '2':
    cout << endl << "После какого элемента добавить = ";
    cin >> tmp;
    if (AddAfter(num,tmp)==1)
    cout << endl << "Элемент добавлен" << endl;
    else
    cout << endl << "Такого элемента не существует" << endl;
    break;


    default:
    cout << endl << "Ошибка" << endl;
    break;


    }

    }
    break;

    case '2':
    if(Empty()==1)
    cout << endl << "Список пуст" << endl;
    else
    {
    cout << endl << "Удаляемый элемент = ";
    cin >> num;
    if(Del(num)==1)
    cout << endl << "Элемент удален" << endl;
    else
    cout << endl << "Такого элемента не существует" << endl;
    }
    break;


    case '3':
    if(Empty()==1)
    cout << endl << "Список пуст" << endl;
    else
    {


    cout << endl << "1. Обход в прямом напрвлении" << endl
    << "2. Обход в обратном направлении" << endl
    << " = ";
    cin >> otv2;
    switch(otv2)
    {
    case '1':
    ShowOnward();
    break;


    case '2':
    ShowBack();
    break;


    default:
    cout << endl << "Ошибка" << endl;
    break;


    }

    }
    break;

    case '4':
    if(Empty()==1)
    cout << endl << "Список пуст" << endl;
    else
    {
    cout << endl << "Элемент для поиска = ";
    cin >> num;
    n1=0;
    n2=0;
    if(SearchOnward(num)!=NULL && SearchBack(num)!=NULL)
    {
    cout << endl << "Элемент найден" << endl;
    cout << endl << "В прямом направлении шаг = " << n1 << endl;
    cout << endl << "В обратном направлении шаг = " << n2 << endl;
    }
    else
    cout << endl << "Такого элемента не существует" << endl;


    }
    break;

    case '5':
    if(Empty()==1)
    cout << endl << "Список пуст" << endl;
    else
    {
    //Double();
    //ShowOnward();
    }
    break;

    case '0':
    break;


    default:
    cout << endl << "Ошибка" << endl;
    break;


    }

    }while(otv!='0');
    cin.get();

    }
    В функции Double() хотела сделать это самое дублирование, но столкнулась с проблемой сравнения элементов и копирования со сдвигом элементов в списке. Можете объяснить как это сделать?
     
  2. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Подожди, подожди.. Что означает слово "продублировать" ??
     
  3. gvenog

    gvenog New Member

    Регистрация:
    13 дек 2010
    Сообщения:
    3
    Симпатии:
    0
    Это значит что, если элемент больше предыдущего, но меньше следующего, то нужно его скопировать и вставить за ним, ну типа:

    был неупорядоченный список:
    1, 4, 2, 6, 8, 7, 10

    Элемент 6 больше 2 и меньше 8, значит нужно его скопировать:
    1, 4, 2, 6, 6, 8, 7, 10

    Вот так.
     
  4. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Не буду изучать твой длинный код.. Просто посмотри как я сделал. Сдвигать там ничего не надо.
    Код (C++):
    #include <iostream.h>
    #include <conio.h>

    typedef struct _list {
    int     v;
    _list * prev;
    _list * next;
    } list;

    list *  top = NULL;

    void list_add( int v )
    {
    if ( !top ) {
    top = new list;
    top->prev = NULL;
    top->next = NULL;
    top->v = v;
    } else {
    list *  last = top;
    while ( last->next ) last = last->next;
    last->next = new list;
    last->next->next = NULL;
    last->next->prev = last;
    last->next->v = v;
    }
    }

    void list_double( void )
    {
    list *  p = top;
    while ( p ) {
    if ( p->prev && p->next ) {
    if ( p->prev->v < p->v && p->v < p->next->v ) {
    //
    // insert between p->prev and p
    //
    list *d = new list;
    d->prev = p->prev;
    d->next = p;
    d->v = p->v;

    p->prev->next = d;
    p->prev = d;
    }
    }
    p = p->next;
    }
    }

    void list_print( void )
    {
    list *  p = top;
    while ( p ) {
    cout << p->v << endl;
    p = p->next;
    }
    }

    int main()
    {
    list_add( 1 );
    list_add( 4 );
    list_add( 2 );
    list_add( 6 );
    list_add( 8 );
    list_add( 7 );
    list_add( 10 );

    list_double();

    list_print();
    return 0;
    }
     
  5. gvenog

    gvenog New Member

    Регистрация:
    13 дек 2010
    Сообщения:
    3
    Симпатии:
    0

    Большое вам спасибо, теперь я поняла!
     
  6. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Спасибо не прокатит, а вот плюсик - вполне!
     
Загрузка...

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