Помощь - Поиск - Пользователи - Календарь
Полная версия: Проблема с организацией списка FIFO
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
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;
}
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).
volvo
Значит, смотри что у меня получилось:

Нажмите для просмотра прикрепленного файла

Рассказываю: эта программа компилируется (с 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 (и на любом другом современном компиляторе) задача решается гораздо короче.

Вот так: (Показать/Скрыть)
ninja
скачал GCC, попробовал запустить вроде работает нормально, только менюшка глючит, и почему то функция clrscr() не работает, а на С++ Builder'e вроде нормально работает, добавил очистку экрана после нажатия клавиши.
Спасибо огромное, код правда на половину мне не понятен, пока, буду разбираться....
volvo
Цитата
почему то функция clrscr() не работает
Потому что функция clrscr - это "примочка" Борланда. В компиляторах этой фирмы она есть. В других - нету. В Стандарте С++ про такую функцию тоже ни слова нет, кстати. Так что лучше ее вообще не использовать, чтоб не завязываться под определенный компилятор.

Цитата
код правда на половину мне не понятен
Welcome to C++ ... Что именно не понятно, можно уточнить? Вроде, ничего особенно сложного не используется.
ninja
я имел ввиду синтаксис вот например

private:
list<int>& items;

просто впервые вижу такое....

for(list<int>::iterator it = the_list.begin(); it != the_list.end(); it++)

сложновато пока, но буду разбираться, Спасибо

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.