Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Динамические структуры данных. Язык Си.

Автор: Bo2nik 9.04.2008 22:22

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

Код

#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) Результат записываем в третий список.

Автор: volvo 9.04.2008 23:10

"Разделяй и властвуй"... Не надо в одной структуре хранить данные обоих многочленов, если ты разделишь это на 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;
}

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

Автор: Bo2nik 9.04.2008 23:42

Объясните пожалуйста вот это:

Цитата(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;
        }
    }
}

Автор: volvo 10.04.2008 0:10

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

Цитата

Вот так что-ли

Все проще гораздо, у тебя списки упорядочены по полю 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;
    }
}

Автор: Bo2nik 10.04.2008 0:35

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

Цитата

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

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

Автор: volvo 10.04.2008 0:37

Цитата

прога не будет работать

Опять не разобрался... Будет она работать, просто перемножать будет столько элементов, сколько есть в более коротком многочлене. Для этого и условие:

while(p && p2) ...

Автор: Bo2nik 10.04.2008 0:41

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

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

походу у меня проблемы с алгеброй...

Автор: volvo 10.04.2008 0:54

Погоди...

Нет, при умножении надо делать по другому... Там надо вложенный цикл... Сейчас покажу.

Автор: volvo 10.04.2008 1:14

Вот, посмотри:

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