Проблема с организацией списка FIFO, C++ Опции

[ninja]

Добрый вечер. Необходимо решить следующую задачу:

Разработать алгоритм и программу. Организовать и заполнить два линейных динамических списка L1 и L2 типа FIFO, элементами которых являются целые числа, принимающие значения в диапазоне типа Integer.
Выполнить следующие действия над списками:
- удалить из списка L1 все отрицательные числа и поместить их в список L2, взяв их по модулю;
- определить включает ли список L1 список L2, если включение имеет место, то объединить эти списки в один и упорядочить по возрастанию значений элементов.
Действия выполнятся в произвольном порядке по выбору пользователя с отображением результатов преобразований. При заполнении списка и добавлении элементов выполнить анализ объема доступной динамической памяти.


Начал писать программу столкнулся с такой проблемой необходимо в функцию передать 2 значения, из другой функции т.е. у меня функция spisok_L1 которая заполняет список, и функция prosmotr, но чтобы вывести значения из памяти мне необходимо знать адрес откуда начинать, и когда заканчивать вывод. Переменная schet4ik отвечает за количество элементов в списке, эта переменная передается, но как мне передать переменную которая указывает на начало списка.

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
int menu ()
	{
	 char menu[5][15]={{"Dobavlenie"},{"Prosmotr"},{"Sortirovka"},{"ochistka file"},{"exit"}};
	 int index=0;
	 char ch='\0';
	 int i,j=0;
	 while (ch!=13)
		{
		 clrscr();
		 for (i=0;i<=4;i++)
			{
			 if (i==index)
			 textattr(70);
			 j=0;
			 while (menu[i][j]!='\0')
			 cprintf("%c",menu[i][j++]);
			 printf("\n");
			 textattr(07);
			 }
	ch=getche();
	if (ch=='\0') ch=getch();
	if (ch==72) index--;
	if (ch==80) index++;
	if (index==-1)  index=4;
	if (index==5) index=0;
	}
return index;
	}

struct L1
  {
   int info;
   struct L1 *next;
  };


spisok_L1()
{
	L1 *head, *p;//*tail;
	int chislo=0;
	char ch='\0';
	int schet4ik=0;

	head=new(L1);
	p=head;

	while (ch!='n')
	    {
		clrscr();
		cout << "Vvedite element spiska " << endl;
		cin >>chislo;
		cout << endl;
		(*p).info=chislo;
		(*p).next=new(L1);
		p=(*p).next;
		//tail=p;
		schet4ik++;
		cout << "Prodoljitb vvod? [y/n]" << endl;
		ch = getche();
		cout << endl;
	   }
clrscr();
p=head;
//while (p!=tail)
	{
	 //printf("%d",p->info);
	 //p=p->next;
	}
return schet4ik;
}





int prosmotr (int schet4ik)
{
L1 *p, *head;
int k=0;

p=head;
while (k!=schet4ik)
{
 cout << (*p).info << endl;
 p=(*p).next;
 k++;
}

//for (p=head;p!=tail;p=(*p).next)
  //	cout << (*p).info << endl;

getche();
return 0;
}

void main ()
{
L1 *head, *p, *tail;
int index;
int m=0;
	do
	 {
	  index=menu();
	  switch (index)
	    {
	     case 0:{
		     m=spisok_L1();
		     break;
		    }
	     case 1:{
		     prosmotr(m);
		     break;
		    }
	     case 2:{

		     break;
		    }
	     case 3:{

		     break;
		    }
	     case 4:{

		     exit(1);
		    }

	    }
	 }
	while (index!=4);


getch();
}

[volvo]

но как мне передать переменную которая указывает на начало списка.

Через двойной указатель. Вот так, например:

int spisok_L1(struct L1 **first)
{
    /* тут все действия */

    *first = head;
    return schet4ik;
}

/* Вызывать так: */
m = spisok_L1(&head);

[ninja]

Спасибо огромное работает.

[ninja]

Появилась еще одна проблема: когда запускаю программу выбираю пункт меню добавить, добавляю 3 элемента т.е. ввожу 1,2,3 затем нажимаю просмотр, все выводится нормально, если хочу добавить еще элементы он добавляет только 1 остальные почему-то не выводятся, отслеживал по адресам вроде все нормально.

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
int menu ()
	{
	 char menu[5][15]={{"Dobavlenie"},{"Prosmotr"},{"Sortirovka"},{"ochistka"},{"exit"}};
	 int index=0;
	 char ch='\0';
	 int i,j=0;
	 while (ch!=13)
		{
		 clrscr();
		 for (i=0;i<=4;i++)
			{
			 if (i==index)
			 textattr(70);
			 j=0;
			 while (menu[i][j]!='\0')
			 cprintf("%c",menu[i][j++]);
			 printf("\n");
			 textattr(07);
			 }
	ch=getche();
	if (ch=='\0') ch=getch();
	if (ch==72) index--;
	if (ch==80) index++;
	if (index==-1)  index=4;
	if (index==5) index=0;
	}
return index;
	}

struct L1
  {
   int info;
   struct L1 *next;
  };


spisok_L1(struct L1 **phead, struct L1 **ptail)
{
	L1 *head, *p, *tail;
	int tt=0;
	int chislo=0;
	char ch='\0';
	int schet4ik=0;

	if (*phead==NULL)
		{
		head=*phead;
		tt=1;
		}
	else
		{
		 /*p=*phead;
		 while (p!=NULL)
		    {

		     p=(*p).next;
		     if (p!=NULL)
			tail=p;
		    }        */
		p=*ptail;
		}

	if (head==NULL)
		{
		 head=new(L1);
		 p=head;
		}
	else
		{
		 p=new(L1);
		}

	while (ch!='n')
	    {
		clrscr();
		cout << "Vvedite element spiska " << endl;
		cin >>chislo;
		cout << endl;
		(*p).info=chislo;
		(*p).next=new(L1);
		p=(*p).next;
		tail=p;
		schet4ik++;
		cout << "Prodoljitb vvod? [y/n]" << endl;
		ch = getche();
		cout << endl;
	   }
*ptail=tail;
(*p).next=NULL;
clrscr();
if (tt==1)
*phead=head;
//p=head;
//while (p!=tail)
	{
	 //printf("%d",p->info);
	 //p=p->next;
	}
return schet4ik;
}





int prosmotr (int schet4ik,struct L1 **phead,struct L1 **ptail)
{
L1 *p, *head,*tail;
int k=0;
head=*phead;
p=head;
clrscr();
tail=*ptail;
while (p!=NULL)//(k!=schet4ik)
{
 if (p!=tail)
 cout << (*p).info << endl;
 p=(*p).next;
 k++;
}

//for (p=head;p!=tail;p=(*p).next)
  //	cout << (*p).info << endl;
getche();
clrscr();
return 0;
}

void main ()
{
L1 *phead=NULL, *p, *tail;
int index;
int m=0;
	do
	 {
	  index=menu();
	  switch (index)
	    {
	     case 0:{
		     m=spisok_L1(&phead,&tail);
		     break;
		    }
	     case 1:{
		     prosmotr(m,&phead,&tail);
		     break;
		    }
	     case 2:{

		     break;
		    }
	     case 3:{

		     break;
		    }
	     case 4:{

		     exit(1);
		    }

	    }
	 }
	while (index!=4);


getch();
}

[volvo]

Я устал уже догадываться, тебе нужен С или С++, ты в заголовке пишешь одно, а в самом посте - другое. Вот как производится добавление в список и его распечатка на чистом С:

typedef
struct L1
{
    int info;
    struct L1 *next;
} Lst;
typedef Lst *PLst;

int spisok_L1(PLst *phead, PLst *ptail)
{
    PLst p;
    int chislo, schet4ik = 0;
    char ch = '\0';

    while(ch != 'n')
    {
        printf("Vvedite element spiska\n");
        scanf("%d", &chislo);

        p = (PLst)malloc(sizeof(Lst));
        p->info = chislo;
        p->next = NULL;

        if((*phead) == NULL) *phead = p;
        else (*ptail)->next = p;

        *ptail = p;

        schet4ik += 1;
		printf("Prodoljitb vvod? [y/n]\n");
		ch = getche();
    }
    return schet4ik;
}

int prosmotr (int schet4ik, PLst phead, PLst ptail)
{
    PLst p;
    int k;

    for(k = 0, p = phead; p; p = p->next)
    {
        printf("%d\n", p->info);
        k += 1;
    }
    return 0;
}

Естественно, что брать адрес при вызове функции prosmotr не нужно, потому что ничего не должно изменяться, указатели на начало и на конец списка после печати должны быть такими же, как и до нее.

Все прекрасно работает - добавляются значения в конец списка и после распечатки тоже.

Да и функцию menu я бы переписал, зачем выводить по одному символу, если можно сразу вывести строку?

[ninja]

Спасибо огромное Владимир, вообще нужно на С++, я извиняюсь, за такой "кривой код" просто я не знаю в чем отличия С и С++, преподаватель задачу поставил, я кусками в интернете ищу, причем когда вставляю в компилятор С++ все работает.

[volvo]

просто я не знаю в чем отличия С и С++

Вот это - больше похоже на С++, чем то, что было написано раньше. Насколько я понимаю (по использованию функций clrscr() и cprintf()), у тебя обычный dos-овский Turbo C++? Тогда мой код будет работать.

#include <iostream.h>
#include <stdio.h>
#include <conio.h>

int menu()
{
    const int nItems = 5;
    const char *menu[nItems] = {
        "Dobavlenie", "Prosmotr", "Sortirovka", "ochistka", "exit"
    };

    int index = 0;
    char ch = '\0';

    while(ch != 13)
    {
        clrscr();
        for(int i = 0; i < nItems; i++)
        {
            if(i == index) textattr(70);
            cprintf("%s\r\n", menu[i]);
            textattr(7);
        }

        int delta = 0;
        if((ch = getch()) == 0)
        {
            ch = getch();
            switch(ch)
            {
                case 72:
                    delta = -1; break;
                case 80:
                    delta = +1; break;
            }
            index = (nItems + index + delta) % nItems;
        }
    }
    return index;
}


class List
{
public:
    List()
    {
        head = tail = 0;
    }
    void Append(int);
    void Print();

private:
    class ListItem
    {
    public:
        int val;
        ListItem *next;

        ListItem(int value, ListItem *item = 0)
        {
            val = value; next = item;
        }
    };

    ListItem *head, *tail;
};

void List::Append(int val)
{
    ListItem *p = new ListItem(val);
    if(!head) head = p;
    else tail->next = p;

    tail = p;
}
void List::Print()
{
    for(ListItem *p = head; p; p = p->next)
    {
        cout << p->val << endl;
    }
}


int main ()
{
    List myList;
    int index;

    do
    {
        switch(index = menu())
        {
            case 0:
            {
                char ch = '\0';
                int n;

                while(ch != 'n')
                {
                    cout << "Vvedite element spiska" << endl;
                    cin >> n;

                    myList.Append(n);
                    cout << "Prodoljitb vvod? [y/n]" << endl;
                    ch = getch();
                }
            }
            break;

            case 1:
                myList.Print();
                getch();
                break;

            case 2:
            case 3:
                break;
        }

    }
    while(index < 4);

    return 0;
}

[ninja]

ага, у меня обычный dos-овский Turbo C++, Владимир спасибо Вам огромное все отлично работает, сейчас буду разбираться.

[ninja]

Добавил еще 1 функцию Sort () которая должна сортировать значения в 1м списке, т.е если значения в 1м списке отрицательные их нужно из первого списка удалить и поместить в другой (по модулю), все вроде нормально работает, из 1го все нормально удаляется, только когда помещаю во второй, данные вроде заносятся, а когда считываю 2й список пуст. Объявил еще 1 класс для 2го списка.

#include <iostream.h>
#include <stdio.h>
#include <conio.h>

int menu()
{
    const int nItems = 5;
    const char *menu[nItems] = {
        "Dobavlenie", "Prosmotr", "Sortirovka", "ochistka", "exit"
    };

    int index = 0;
    char ch = '\0';

    while(ch != 13)
    {
	clrscr();
	for(int i = 0; i < nItems; i++)
        {
	    if(i == index) textattr(70);
	    cprintf("%s\r\n", menu[i]);
	    textattr(7);
	}

	int delta = 0;
	if((ch = getch()) == 0)
	{
	    ch = getch();
	    switch(ch)
	    {
		case 72:
		    delta = -1; break;
		case 80:
		    delta = +1; break;
	    }
	    index = (nItems + index + delta) % nItems;
	}
    }
    return index;
}


class List
{
public:
    List()
    {
	head = tail = 0;
    }
    void Append(int);
    void Print();
    void Sort();
private:
    class ListItem
    {
    public:
	int val;
	ListItem *next;

	ListItem(int value, ListItem *item = 0)
	{
	    val = value; next = item;
	}
    };

    ListItem *head, *tail;
};


class List2
{
public:
    List2()
    {
	head2 = tail2 = 0;
    }
    void Append2(int);
    void Print2();
    void Sort2();
private:
    class ListItem2
    {
    public:
	int val2;
	ListItem2 *next2;

	ListItem2(int value2, ListItem2 *item2 = 0)
	{
	    val2 = value2; next2 = item2;
	}
    };

    ListItem2 *head2, *tail2;
};



void List2::Append2(int val2)
{
    ListItem2 *p2 = new ListItem2(val2);
    if(!head2) head2 = p2;
    else tail2->next2 = p2;

    tail2 = p2;
}


void List2::Print2()
{

    int x=1,y=1;

    for(ListItem2 *p2 = head2; p2; p2 = p2->next2)
    {
	gotoxy(x+15,y);
	cout << p2->val2 << endl;
	y++;
    }

}


void List::Append(int val)
{
    ListItem *p = new ListItem(val);
    if(!head) head = p;
    else tail->next = p;

    tail = p;
}
void List::Print()
{
    for(ListItem *p = head; p; p = p->next)
    {
	cout << p->val << endl;
    }
}

void List::Sort()
{
    ListItem *p = head;
    p=head;
    int zna4=0;
    List2 L2;
    ListItem *tek;
    int perest=0;
    while (p!=NULL)
	{
	 if ((p->val < 0)&&(p==head)&&(perest==0))
		{
		 zna4=p->val * (-1);
		 L2.Append2(zna4);
		 tek=p;
		 head=head->next;
		 delete(tek);
		 perest=1;
		}
	 if ((p->next->val < 0)&&(p->next!=tail)&&(perest==0))

		{
		 zna4=p->next->val * (-1);
		 L2.Append2(zna4);
		 tek=p->next;
		 p->next=tek->next;
		 delete(tek);
		 perest=1;
		}
	 if ((p->next->val < 0)&&(p->next==tail)&&(perest==0))
		{
		 zna4=p->next->val * (-1);
		 L2.Append2(zna4);
		 tek=p->next;

		 p->next=tail->next;
		 delete(tek);
		 tail=p;
		 perest=1;

		}


	  if (perest==1)
	  p=head;
	  else
	  p=p->next;
	  perest=0;
	}
}

int main ()
{
    List myList;
    List2 myList2;
    int index;

    do
    {
	switch(index = menu())
	{
	    case 0:
	    {
		char ch = '\0';
		int n;

		while(ch != 'n')
		{
		    clrscr();
		    cout << "Vvedite element spiska" << endl;
		    cin >> n;

		    myList.Append(n);
		    cout << "Prodoljitb vvod? [y/n]" << endl;
		    ch = getch();
		}
	    }
	    break;

	    case 1:
		clrscr();
		myList.Print();
		myList2.Print2();
		getch();
		break;

	    case 2:
		 {
		  myList.Sort();
		 }
	    case 3:
		break;
	}

    }
    while(index < 4);

    return 0;
}

Сообщение отредактировано: ninja - 20.05.2010 16:54

[volvo]

Объявил еще 1 класс для 2го списка.

Зачем? Достаточно было сделать:

    List myList;
    List myList2;

...

А теперь поподробнее о сортировке. Как именно тебе надо отсортировать список, можно уточнить?

[ninja]

Отсортировать нужно следующим образом, в 1м списке например содержаться следующие элементы:
1
-2
-3
-4
5
6
-7
8

после сортировки должно получится следующее:
в 1м списке должны остаться:
1
5
6
8
т.е все положительные, а второй список должен содержать отрицательные элементы, только взятые по модулю, т.е
2
3
4
7
Затем определить включает ли 1й список, 2й список, если включение имеет место, то объединить эти списки в один и упорядочить по возрастанию значений элементов.

[volvo]

Ты постоянно что-то недоговариваешь... Ну, допустим, со списком <1, -2, -3, -4, 5, 6, -7, 8> все понятно. Он изначально упорядочен по модулю. А если так: <10, -2, -23, -4, 15, 6, -7, 8> , тогда как быть? Если просто "раскидать" список на 2 в зависимости от знака - то это никакая не сортировка, это просто разделение. Если сортировка - то говори, каков критерий. (Для информации: после сортировки списка в нем должно остаться ровно столько же элементов, сколько было до нее. У тебя это не выполняется.)

[ninja]

Извиняюсь.... Необходимо сначала разделить 1й список на два , затем проверить включает ли 1й список, второй список, если включает, то объединить 1й и 2й список, и упорядочить элементы по возрастанию.

Например
1й список содержит элементы (1,-2,-5,-7,3)
сначала мне нужно во 2й записать отрицательный элементы и взять их по модулю т.е получится (2,5,7)
затем нужно удалить из 1го списка отрицательные т.е получится (1,3)
и проверить вхождения 2го списка в первый в данном случае вхождения нет.
А вот если например

1й список содержит, элементы (1,3,8) а второй содержит элементы (3,8), эти списки нужно объединить и упорядочить по возрастанию т.е получится (1,3,3,8,8).

Сообщение отредактировано: ninja - 20.05.2010 18:35

[volvo]

Значит, смотри что у меня получилось:

 LST01.CPP ( 4.34 килобайт ) Кол-во скачиваний: 396


Рассказываю: эта программа компилируется (с Warning-ами, но они не особо страшные, к тому же, если вынести реализацию методов с циклами for из определения класса, наружу, эти Warning-и пропадут) и работает. Вроде бы я ничего не упустил, тестируй программу на как можно большем числе тестов, если где-то работает не так, как должно - говори, на каких данных это происходит...

Теперь о том, как именно оно работает. Я все повесил на пункт меню "Добавление". То есть, сразу вводится первый список, тут же он разделяется на 2 (по тому признаку, который ты указал), проверяется вхождение одного в другой, и если надо - то слияние и сортировка.

Тестировал на списке <1, -3, 3, 8, -8, 11> - получается как и положено <1, 3, 3, 8, 8, 11>.

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

[ninja]

Владимир, тестировал сегодня программу, получились следующие результаты: если ввести список (1, 2, 3, 4, 5, -2, -4, -3)
должно получится 1й список (1, 2, 2, 3, 3, 4, 4, 5) а во 2м (2, 4, 3), а программа выводит:

2 added ...
1, 2, 3, 4, 5, -4, -3, 2
first list = -4, -3, 1, 2, 2, 3, 4, 5
second list = 2

Пробовал ввести, то что Вы вводили т.е.

вводил
1, -3, 3, 8, -8, 11

получилось

3 added
1, 3, 8, -8, 11, 3
first list = -8, 1, 3, 3, 8, 11
second list = 3
если добавить еще 1 элемент (5)

выдает
3 added
1, 3, 3, 8, 11, 5, 3
8 added
first list 1, 3, 3, 3, 5, 8, 8, 11
second list 3, 8

[volvo]

если ввести список (1, 2, 3, 4, 5, -2, -4, -3)

Ну что ж, проверяем:

вводил
1, -3, 3, 8, -8, 11

И я вводил:


Что я делал неправильно?

[ninja]

Вводил тоже что и Вы у меня совсем другие результаты






Видать что-то с компилятором, Владимир не подскажете на каком Вы компилируете?

[volvo]

У меня GCC, там все нормально, вечером попробую проверить в Турбо С++, может действительно дело в компиляторе...

[ninja]

Спасибо, попробовал по-другому ввел сначала положительные числа т.е 1, 3, 8, 11, а затем отдельно сначала -3, потом еще отдельно -8, вроде получилось, только почему-то получилось 3 тройки т.е 1, 3, 3, 3, 8, 8, 11
сейчас попробую тоже скачать GCC

[volvo]

Ну, скачай. Как скачаешь - на GCC (и на любом другом современном компиляторе) задача решается гораздо короче.

Вот так: (Показать/Скрыть)

#include <iostream>
#include <iterator>
#include <list>
#include <algorithm>
#include <cmath>

#include <conio.h>

using namespace std;

// Эта функция может подглючивать. У меня на одной машине работает нормально,
// на другой - нет. Исправлю чуть позже...
int menu() 
{
    const int nItems = 5;
    const char *menu[nItems] = {
        "Dobavlenie", "Prosmotr", "Sortirovka", "ochistka", "exit"
    };

    int index = 0;
    char ch = '\0';

    while(ch != 13)
    {
        for(int i = 0; i < nItems; i++)
        {
            if(i == index) cout << "* ";
            cout << menu[i] << endl;
        }

        int delta = 0;
        if((ch = getch()) == 0)
        {
            ch = getch();
            switch(ch)
            {
                case 72:
                    delta = -1; break;
                case 80:
                    delta = +1; break;
            }
            index = (nItems + index + delta) % nItems;
        }
    }
    return index;
}


struct fNegative
{
    bool operator()(const int& rhs) {
        return (rhs < 0) ? (items.push_back(abs(rhs)), true) : false;
    }
    fNegative(list<int>& _items) : items(_items)
    {
    }
private:
    list<int>& items;
};

bool Contains(list<int>& the_list, list<int>& the_sublist)
{
    bool found = false;
    for(list<int>::iterator it = the_list.begin(); it != the_list.end(); it++)
    {
        pair<list<int>::iterator, list<int>::iterator> values;
        list<int>::iterator it_copy = it;
        values = mismatch(the_sublist.begin(), the_sublist.end(), it_copy);
        if(values.first == the_sublist.end())
        {
            found = true;
            break;
        }
    }
    return found;
}


int main ()
{
    list<int> myList;
    list<int> myList2;

    int index;

    do
    {
        switch(index = menu())
        {
            case 0:
            {
                char ch = '\0';
                int n;

                do
                {
                    cout << "Vvedite element spiska" << endl;
                    cin >> n;

                    myList.push_back(n);

                    cout << "Prodoljitb vvod? [y/n]" << endl;
                    ch = getch();
                }
                while(ch != 'n');

                myList.erase(
                    remove_if(myList.begin(), myList.end(), fNegative(myList2)),
                    myList.end()
                );
                if(Contains(myList, myList2))
                {
                    myList.sort(); myList2.sort();
                    myList.merge(myList2);
                }

                cout << "first list:" << endl;
                copy(myList.begin(), myList.end(), ostream_iterator<int>(cout," "));
                getch();
            }
            break;

            case 1: // Все повешено на первый пункт меню, но можно и раскидать по остальным
            case 2:
            case 3:
                break;
        }

    }
    while(index < 4);

    return 0;
}