VPF::[C++] Вставить второй список в первый

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

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);

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

альтернативный вариант - вставлять элементы второго в первый поштучно, сразу в требуемую позицию, тогда сортировка не потребуется

graffi

Дата 8.7.2010, 12:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

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

Цитата(vnf @ 7.7.2010, 22:15)

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

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;
}

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