Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Вставить второй список в первый, Помогите пожалуйстаразобраться с задачей 
V
    Опции темы
Girumm
Дата 7.7.2010, 00:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 6.7.2010

Репутация: нет
Всего: нет



Здравствуйте.
Решаю задачу:
Даны упорядоченные списки L1 и L2.Вставить элементы списка L2 в список L1, не нарушая его упорядоченности.

Я сначала реализую сортировку списков(для общего случая) потом пробую вставить второй в первый. Но при вставке происходят проблемы.
1)Не знаю как описать два списка чтобы лучше с ними работать было
2)Какие именно проще использовать в данном случае(очередь стек и тд)
3)Как осуществлять вставку списка.
Я пишу без <list>  
Помогите плз разобраться с задачей.
Заранее спасибо
Код

#include "stdafx.h"
#include <iostream>
using namespace std;
#include <Windows.h>
struct Node
{
    int x,x1;
    Node *next,*next1;
};
struct Queue
{
    Node *Head,*Tail, *Head1,*Tail1;
};

int menu();
void add_el (Queue &Q,int x);
void add_el1 (Queue &Q1,int x);
void sort_list (Queue &Q);
void sort_list1 (Queue &Q1);
void insert_list (Queue &Q,Queue &Q1);
void out_lists(Queue Q,Queue Q1);
void out_list(Queue &Q,Queue &Q1);

int _tmain(int argc, _TCHAR* argv[])
{
    SetConsoleOutputCP(1251);
    int x,x1,pm;
    Node p;
    Nod1 p1;
    Queue Q;
    Queue Q1;
    Q.Tail=NULL;
    Q.Head=NULL;
    Q1.Head1=NULL;
    Q1.Tail1=NULL;
    p1=p;
    while(1)
    {
        pm=menu();
        if(pm==1)
        {
            cout<<"Введите элемент списка 1"<<endl;
            cin>>x;
            add_el(Q,x);
        }
         else if(pm==2)
         {
             cout<<"Введите элемент списка 2"<<endl;
            cin>>x1;
            add_el1(Q1,x1);
        }
         else
             break;
    }
    sort_list(Q);
    sort_list1(Q1);
    insert_list (Q,Q1);
    out_list(Q,Q1);
    
    return 0;
}

int menu()
{
    char p;
    do
    {
        cout<<"1.Добавить элемент в список 1\n2.Добавить элемент в список 2\n3.Необходимое количество елементов добавлено.\nВаш выбор: ";
        cin>>p;
    }
    while(strchr("123",p)==NULL);
    return p-48;
}

void add_el(Queue &Q,int x)
{
    Node *NewEl=new Node;
    NewEl->x=x;
    NewEl->next=NULL;
    if(Q.Tail!=NULL)
        Q.Tail->next=NewEl;
    Q.Tail=NewEl;
    if(Q.Head==NULL)
        Q.Head=Q.Tail;
}

void add_el1(Queue &Q1,int x)
{
    Node *NewEl=new Node;
    NewEl->x1=x;
    NewEl->next1=NULL;
    if(Q1.Tail1!=NULL)
        Q1.Tail1->next1=NewEl;
    Q1.Tail1=NewEl;
    if(Q1.Head1==NULL)
        Q1.Head1=Q1.Tail1;
}
void sort_list (Queue &Q)
{
    Node *top=Q.Head,*end=Q.Tail->next,*p,*q=Q.Head,tmp;
    while(top!=end)
    {
        for(p=q;p->next!=end;p=p->next)
            if(p->x>p->next->x)
            {
                tmp.x=p->x;
                p->x=p->next->x;
                p->next->x=tmp.x;
            }
            end=p;
    }
}
void sort_list1 (Queue &Q1)
{
    Node *top1=Q1.Head1,*end1=Q1.Tail1->next1,*p1,*q1=Q1.Head1,tmp;
    while(top1!=end1)
    {
        for(p1=q1;p1->next1!=end1;p1=p1->next1)
            if(p1->x1>p1->next1->x1)
            {
                tmp.x1=p1->x1;
                p1->x1=p1->next1->x1;
                p1->next1->x1=tmp.x1;
            }
            end1=p1;
    }
}
void out_list(Queue &Q,Queue &Q1)
{
    Node *p,*q,*p1;
    p=Q.Head;
    while(p!=NULL )
    {
        cout<<p->x<<" ";
        p=p->next;
    }
    /*cout<<endl;
    p1=Q1.Head1;
    while(p1!=NULL )
    {
        cout<<p1->x1<<" ";
        p1=p1->next1;
    }
    cout<<endl;
    */
}
void insert_list (Queue &Q,Queue &Q1)
{
    Node *p;
    Node *top1=Q1.Head1,*p1=Q1.Head1;
    while(p1!=NULL)
    {
        Q1.Head1=Q1.Head1->next1;
        for(p=Q.Head;p->next!=0;p=p->next)
        {
            if(p1->x1>p->x && p1->x1<p->next->x)
            {
                
                p1->next1=p->next;
                p->next=p1;
                

            }
            else if(p1->x1<Q.Head->x)
            {
                
                p1->next1=Q.Head;
                Q.Head=p1;
            }
            else if(p1->x1>Q.Tail->x)
            {
                
                p1->next1=NULL;
                Q.Tail->next=p1;
                Q.Tail=p1;
            }
            
            
        }
        p1=Q1.Head1;
    }
}


Это сообщение отредактировал(а) Girumm - 7.7.2010, 00:20
PM MAIL   Вверх
vnf
Дата 7.7.2010, 22:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



слишком сложно
для работы со списком лучше использовать список smile

Код

struct Node
{
    int x;
    Node *next;
};

Node * add_el (Node *head, int x)// добавляет новый элемент в голову
{
   Node *tmp = new Node;
   tmp -> x = x;
   tmp -> next = head;
   return tmp;
};

Node * merge(Node *head1, Node *head2)// добавляет второй в конец первого
{
   Node *tmp = head1;
   while(tmp->next)  tmp = tmp->next;
   tmp->next = head2;
   return head1;
};


это в main
// создаем первый список
Node * head1 = NULL;
head1 = add_el (head1, 1);
head1 = add_el (head1, 2);
head1 = add_el (head1, 7);
head1 = add_el (head1, 9);

// создаем второй список
Node * head2= NULL;
head2 = add_el (head2, 3);
head2 = add_el (head2, 6);
head2 = add_el (head2, 8);
head2 = add_el (head2, 13);
head2 = add_el (head2, 23);

// объединяем
Node * head = merge(head1,head2);

// осталось отсортировать новый список и всё



альтернативный вариант - вставлять элементы второго в первый поштучно, сразу в требуемую позицию, тогда сортировка не потребуется
PM MAIL   Вверх
graffi
Дата 8.7.2010, 12:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 6.4.2007

Репутация: нет
Всего: нет



Цитата(vnf @ 7.7.2010,  22:15)
альтернативный вариант - вставлять элементы второго в первый поштучно, сразу в требуемую позицию, тогда сортировка не потребуется

Вообще по заданию именно это требовалось.
Так что придется слегка модифицировать метод add_el (чтобы элемент можно было вставить в любую позицию) и добавить поиск нужного места (видимо, придется последовательно проходить все элементы, пока не будет обнаружено нужное место. Можно заморочиться с методом деления пополам, это уменьшит количество сравнений, но доступ-то все равно последовательный... так что смысла нет).

PM MAIL   Вверх
vnf
Дата 8.7.2010, 21:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



Код

Node * insert(Node *head, Node *newnode) //вставить элемент в список
{
   Node *prev = NULL;
   Node *tmp = head;
   while(tmp) // бежим по списку, пока не найдем элемент который меньше (списки в убывающем поряде, если в возрастающем поменять знак)
   {
       if(tmp->x < newnode->x)
       {
           node->next = tmp;
           if(prev)// вставляем в середину
           {
                newnode->next = tmp;
                prev->next = newnode;
                return head;
           }
           else// вставляем в голову списка
           {
               newnode->next = tmp;
               return newnode;
            }
       }
       prev = tmp;
       tmp = tmp->next;
   }
   // вставляем в хвост
   newnode->next = NULL;
   prev->next = newnode;
   return head;
}

Node * merge2(Node *head1, Node *head2)
{
   while(head2)// по одному снимаем элементы из головы списка
   {
      Node *tmp = head2;
      head2 = head2->next;
      head1 = insert(head1, tmp);// и вставляем
   }
   return head1;
}

PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.0706 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.