IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Динамические структуры данных. Язык Си., Списки.
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


Умножение многочленов. Проблема такая: не могу задать степень второго многочлена и вообщем то реализовать сам алгоритм перемножения. Может кто-нибудь кинет идею.

Код


#include "stdafx.h"
#include <stdio.h>
struct list
{
    int inf1,inf2; // коэфициенты
    int st1,st2; // степени
    struct list *ref1,*ref2;
};
main()
{
    FILE *fp,*fp2;
    struct list *p1,*p2,*beg1 = NULL,*beg2 = NULL,*end1 = NULL,*end2 = NULL;
    fp = fopen ("spisok.txt","r");
    fp2= fopen ("spisok2.txt","r");
    printf("MNOGOCHLENI\n");
    int i,k;
    i = -1; // степень первого многочлена
    k = -1; //степень второго многочлена
    while ( !feof(fp) && !feof(fp2) )
    {
        p1 = p2 = (struct list*)malloc(sizeof(struct list));
        fscanf (fp,"%d",&p1->inf1);
        fscanf (fp2,"%d",&p2->inf2);
        i++; //увеличиваем степень первого многочлена, степени идут с головы списка
        if (feof(fp) && feof(fp2))
        {
            free(p1);
            free(p2);
            break;
        }
        end1 = p1; end2 = p2;
        end1->ref1 = end2->ref2 = NULL;
        while (p1!=NULL) // вывод на экран первого списка
        {
            p1->st1 = i;
            printf("k = %d, st = %d\n",p1->inf1,p1->st1);
            p1=p1->ref1;

        }
        while (p2!=NULL) // вывод на экран второго списка
        {
            printf("k2 = %d\n",p2->inf2);
            p2=p2->ref2;

        }
    }
}


Вот набрасал алгоритм:
1) Начинаем обходить 1ый список
2) Считываем степень
3) Перемножаем элементы 1-го списка с элем. 2-го списка, если степени равны
4) Если степени не равны, то (?????????) - тута че-то не доходит
5) Результат записываем в третий список.

Сообщение отредактировано: Bo2nik -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






"Разделяй и властвуй"... Не надо в одной структуре хранить данные обоих многочленов, если ты разделишь это на 2 структуры, будет гораздо проще:

#include <stdio.h>
struct list
{
int inf; // коэфициенты
int st; // степени
struct list *ref;
};

/* Функция, возвращающая указатель на начало созданного списка */
struct list *get_list(FILE *fp)
{
struct list *last = NULL, *first = NULL, *p;
int value, i = -1;

while(!feof(fp)) {
p = (struct list*)malloc(sizeof(struct list));
fscanf(fp, "%d", &value);
if(!feof(fp)) {
p->inf = value;
p->st = ++i;
p->ref = NULL;

/*
если first == 0, то есть пока список пуст, то считаем
началом только что выделенный элемент, иначе то что раньше было
"хвостом" должно указывать на новый элемент
*/
if(!first) first = p;
else last->ref = p;

last = p; /* В любом случае новый элемент становится "хвостом" */
}
}
return first; /* Что ж здесь непонятного? Вернуть начало списка... */
}

void print_list(struct list *p)
{
/*
мне не надо инициализировать p в начале цикла, начинаем работать
непосредственно с тем, что передали в функцию как параметр, поэтому
оставляем первую часть пустой
*/
for(; p; p = p->ref) {
printf("k = %d, st = %d\n", p->inf, p->st);
}
}

int main()
{
FILE *fp,*fp2;
struct list *L1, *L2; // , *p;

fp = fopen ("spisok.txt","r");
fp2= fopen ("spisok2.txt","r");

printf("first poly:\n");
L1 = get_list(fp);
print_list(L1);

printf("second poly:\n");
L2 = get_list(fp2);
print_list(L2);

return 0;
}


А теперь - просто пройди по двум спискам, и перемножь их (причем, если один из списков кончился, то перемножение можно тоже завершить)...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


Объясните пожалуйста вот это:
Цитата(volvo @ 9.04.2008 20:10) *


#include <stdio.h>
// это процедура или как? чет не доходит
struct list *get_list(FILE *fp)
{

struct list *last = NULL, *first = NULL, *p;
int value, i = -1;
// ну тут понятно всё : )
while(!feof(fp)) {
p = (struct list*)malloc(sizeof(struct list));
fscanf(fp, "%d", &value);
if(!feof(fp)) {
p->inf = value;
p->st = ++i;
p->ref = NULL;
// вот тут можно поподробнее, хотя вроде тож понимаю, но плохо
if(!first) first = p;
else last->ref = p;

last = p;
}
}
// это тоже не понятно : (
return first;
}

void print_list(struct list *p)
{
for(/*почему тут ничего не пишется? */; p; p = p->ref) {
printf("k = %d, st = %d\n", p->inf, p->st);
}
}

int main()
{
FILE *fp,*fp2;
struct list *L1, *L2; // , *p;

fp = fopen ("spisok.txt","r");
fp2= fopen ("spisok2.txt","r");

printf("first poly:\n");
L1 = get_list(fp);
print_list(L1);

printf("second poly:\n");
L2 = get_list(fp2);
print_list(L2);

return 0;
}




Цитата(volvo @ 9.04.2008 20:10) *

А теперь - просто пройди по двум спискам, и перемножь их (причем, если один из списков кончился, то перемножение можно тоже завершить)...


Вот так что-ли(сильно не ругайте, я знаю что этот код никогда не заработает):
Код

void pr_list(struct list *p, *p2) // это указатель на второй полином)
{
    for(; p; p = p->ref)
    {
        p2 = (struct list*)malloc(sizeof(struct list));
        p->st = k;
        p2->st = k2;
        if k == k2
        {
            p3 = (struct list*)malloc(sizeof(struct list)); // какой-то третий список???
            x = p->inf;
            y = p2->inf;
            pr = x*y;
            p3->inf = pr;
        }
    }
}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Комментарии добавлены выше...

Цитата
Вот так что-ли
Все проще гораздо, у тебя списки упорядочены по полю st, так что достаточно:
void pr_list(struct list *p, struct list *p2)
{
while(p && p2) {
printf("(%d): %d\n", p->st, p->inf * p2->inf); /* в скобках - степень */
/* Ну, можешь добавить результат умножения в третий список */
p = p->ref; p2 = p2 -> ref;
}
}

 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


Всё заработало. Спасибо. Только там еще надо дописать, если в одном многочлене больше коэфициентов чем в другом, прога не будет работать.

Цитата
причем, если один из списков кончился, то перемножение можно тоже завершить


Вот это как раз мне не надо делать, т.е. завершать умножение(если я правильно понял алгоритм умножения многочленов в линейной алгебре).


Сообщение отредактировано: Bo2nik -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Цитата
прога не будет работать
Опять не разобрался... Будет она работать, просто перемножать будет столько элементов, сколько есть в более коротком многочлене. Для этого и условие:
while(p && p2) ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 30
Пол: Мужской
Реальное имя: Никита

Репутация: -  0  +


Цитата(volvo @ 9.04.2008 21:37) *

просто перемножать будет столько элементов, сколько есть в более коротком многочлене

походу у меня проблемы с алгеброй...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Погоди...

Нет, при умножении надо делать по другому... Там надо вложенный цикл... Сейчас покажу.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Вот, посмотри:
#include <stdio.h>
struct list
{
int inf; // коэфициенты
int st; // степени
struct list *ref;
};

/*
процедура добавляет элемент, если этой степени еще не было,
и суммирует коэффициенты, если степень уже есть в списке
*/
void append(struct list **first, struct list **last, int st, int inf)
{
struct list *pt, *p;
int found = 0;

for(pt = *first; (!found) && pt; pt = pt->ref) {
if(pt->st == st) {
pt->inf += inf;
found = 1;
}
}
if(!found) {
p = (struct list*)malloc(sizeof(struct list));
p->st = st; p->inf = inf; p->ref = NULL;

if(!(*first)) *first = p;
else (*last)->ref = p;

*last = p;
}
}

struct list *get_list(FILE *fp)
{
struct list *last = NULL, *first = NULL, *p;
int value, i = -1;

while(!feof(fp)) {
p = (struct list*)malloc(sizeof(struct list));
fscanf(fp, "%d", &value);
if(!feof(fp)) {
p->inf = value;
p->st = ++i;
p->ref = NULL;

if(!first) first = p;
else last->ref = p;

last = p;
}
}
return first;
}

void print_list(struct list *p)
{
for(; p; p = p->ref) {
printf("k = %d, st = %d\n", p->inf, p->st);
}
}

struct list *pr_list(struct list *p, struct list *p2)
{
struct list *first, *second;
struct list *begin = NULL, *end = NULL;

for(first = p; first; first = first->ref) { /* Теперь делаем умножение как положено */
for(second = p2; second; second = second->ref) {
printf("(%d): %d\n", (first->st + second->st), (first->inf * second->inf)); /* для контроля */
append(&begin, &end, (first->st + second->st), (first->inf * second->inf));
}
}

return begin;
}

int main()
{
FILE *fp,*fp2;
struct list *L1, *L2, *L3;

fp = fopen ("spisok.txt","r");
fp2= fopen ("spisok2.txt","r");

printf("first poly:\n");
L1 = get_list(fp);
print_list(L1);

printf("second poly:\n");
L2 = get_list(fp2);
print_list(L2);

L3 = pr_list(L1, L2);
print_list(L3);


return 0;
}

 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 2.12.2020 8:30
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name