Помощь - Поиск - Пользователи - Календарь
Полная версия: Полиномы
Форум «Всё о Паскале» > Delphi, Assembler и другие языки. > Другие языки
blackhard
Помогите пожалуйста с написанием следующей программы: мне нужно написать программу выполняющую арефмитические операции над полиномами + - * например <2x^3+x^2-5x>*<23x+2> полином должен быть представлен ввиде упорядоченного списка мономов. Нам сказали использовать 2 структуры


typedef struct  //собственно так выглядит моном он состоит из коэфициента пред х и степени х.
{
	int index; 
	int step;
}TMonom;

typedef struct TNode1
{
	TMonom *monom; //это собственно сам элемент списка
	struct TNode1 *next;

}TNode;


Собственно вопрос у меня пока 1 как из этого сформировать список?Если я выделяю память под элемент
TNode *beg=(TNode*)malloc(sizeof(TNode));
выделится память и пою моном?
volvo
Цитата
выделится память и пою моном?
Нет... Нужно выделять самому, выделится только память под указатель на моном... Вот так:
TNode *beg=(TNode*)malloc(sizeof(TNode));
beg->monom = (TMonom*)malloc(sizeof(TMonom));
blackhard
Цитата(volvo @ 20.05.2008 18:59) *

Нет... Нужно выделять самому, выделится только память под указатель на моном... Вот так:
TNode *beg=(TNode*)malloc(sizeof(TNode));
beg->monom = (TMonom*)malloc(sizeof(TMonom));


Спасибо! А вот как потом эту память освобождать? Вначале проходимся по всему списку и делаем free(beg->monom), а потом просто free(beg)?
volvo
Зачем же... Если у тебя уже есть список, и адрес его начала - в переменной start, то:

TNode *ptr, *T;
for(ptr = start; ptr; ) { /* пока ptr != NULL */
  free(ptr->monom);
  ptr = (T = ptr) -> next; /* одновременно запоминаем T = ptr и передвигаем ptr дальше */
  free(T); /* удаляем узел, на который указывал T */
}
blackhard
Все написал спасибо за помощь!


#include"polimon.h"

int main()
{
	int tc=0;
	TNode *beg=NULL;
	TNode *beg2=NULL;
	TNode *end=NULL;
	TNode *rez=NULL;
	u=0;
fi=fopen("in.txt","r");
	while(c!=EOF)
	{
		c=getc(fi);
		while(isspace(c))c=getc(fi);
		if(c==EOF){fclose(fi);return 0;}
		if(c=='<'){	*b++=toupper(c);while(c!='>'){c=getc(fi);*b++=toupper(c);}*b=0;b=buf;;beg=getpolinom(buf);}
		while(isspace(c)||c=='>')c=getc(fi);
		while(!isspace(c)&&c!=';'&&!isalnum(c)&&c!='<'){*o++=c;c=fgetc(fi);}*o--=0;
		while(isspace(c))c=getc(fi);
     	while(c!=';'){*b2++=toupper(c);c=fgetc(fi);}*b2=0;b2=buf2; beg2=getpolinom(buf2);
		printf("%s",buf);
		printf("%s",op);
		printf("%s\n",buf2);
		for(k=0;k<KOL;k++)
			if(*op==*sim[k])break;
		switch(k)
		{
			case 0: 
					 
					 beg=sumpol(beg,beg2);
					 printf("\nUsed: %d bytes\n",u);
					 printf("RESULT: ");
					 printpol(beg);
					 tc+=destructpoli(beg);
					 tc+=destructpoli(beg2);
					 printf("\nReleased: %d bytes\n",tc);
					 u=0;
					 tc=0;
					break;
			case 1:  
					 beg=subpol(beg,beg2);
					 printf("\nUsed: %d bytes\n",u);
					 printf("RESULT: ");
					 printpol(beg);
					 tc+=destructpoli(beg);
					 tc+=destructpoli(beg2);
					 printf("\nReleased: %d bytes\n",tc);
					 u=0;
					 tc=0;
				    
					break;
			case 2:  
				    
					 rez=mulpol(beg,beg2,rez);
					  printf("\nUsed: %d bytes\n",u);
					 printf("RESULT: ");
					 printpol(rez);
					 tc+=destructpoli(beg);
					 tc+=destructpoli(rez);
					 tc+=destructpoli(beg2);
					 printf("\nReleased: %d bytes\n",tc);
					 tc=0;
					 u=0;
					break;
		}
			beg=NULL;
			beg2=NULL;
			end=NULL;
			rez=NULL;
			b=buf;
			b2=buf2;
			o=op;
	
	}
	fclose(fi);
return 0;
	
}



polimon.h


//////////////////////////////////////INCLUDE////////////////////////////////////////
#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
#include<string.h>
//////////////////////////////////////DEFINE////////////////////////////////////////
#define Len 200
#define KOL 3 
#define MALLMOC(ptr,index,step) ptr=(TNode*)malloc(sizeof(TNode));ptr->monom=(TMonom*)malloc(sizeof(TMonom));ptr->monom->index=index;ptr->monom->step=step
//////////////////////////////////////STRUCT///////////////////////////////////////
typedef struct
{
	int index;
	int step;
}TMonom;


typedef struct TNode1
{
	TMonom *monom;
	struct TNode1 *next;

}TNode;
/////////////////////////////////////////////////////////////////////////////////////
char *sim[KOL]={"+","-","*"};

int k,u;

FILE *fi,*fo;

char c,buf[Len],*b=buf,buf2[Len],*b2=buf2,op[Len],*o=op;

/////////////////////////////////////////ADDMONOM////////////////////////////////////
TNode* addmonom(int index,int step,TNode *begin)
{
	TNode *ptr=NULL,*go=NULL;

		if(begin==NULL)
		{
			u+=sizeof(TMonom)+sizeof(TNode);
			MALLMOC(ptr,index,step);
			ptr->next=NULL;
			begin=ptr;
			return begin;
		}
		for(go=begin;go; )
		{
		
			if(go->monom->step==step)
			{
				go->monom->index+=index;
				return begin;
			}
			if(begin->monom->step<step)
			{	
				u+=sizeof(TMonom)+sizeof(TNode);
				MALLMOC(ptr,index,step);
				ptr->next=begin;
				begin=ptr;
				return begin;
			}
			if(go->next==NULL)
			{
				u+=sizeof(TMonom)+sizeof(TNode);
				MALLMOC(ptr,index,step);
				go->next=ptr;
				ptr->next=NULL;
				return begin;
			}
			if(go->next->monom->step<step)
			{
				u+=sizeof(TMonom)+sizeof(TNode);	
				MALLMOC(ptr,index,step);
				ptr->next=go->next;
				go->next=ptr;
				return begin;
			}
			go=go->next;
		}
	
	return begin;
}

/////////////////////////////////////////GETPOLINOM//////////////////////////////////
TNode* getpolinom(char * buf)
{
	char *e=buf,st[100],*s=st,in[100],*i=in,temp[100],*t=temp;
	int cof,step;
	TNode *beg=NULL;

	while(*e!='>'&&*e)
	{	
		 if(*e=='<')
		 {
			*t++=*++e;
			e++;
			if(*e=='X'||isdigit(*e))
			while(1){*t++=*e++;if(*e=='+'||*e=='-'||*e=='>')break;}
		    *t=0;
			t=temp;
		 }
		 else
			if(*e=='+'||*e=='-')
			{	
				*t=0;
				t=temp;
				*t++=*e++;
				while(1){*t++=*e++;if(*e=='+'||*e=='-'||*e=='>')break;}
				*t=0;
				t=temp;
			}
			else
			e++;
			if(strchr(temp,'X')&&strchr(temp,'^'))
			{
				if(strstr(temp,"-X")||strstr(temp,"+X")||*t=='X')
							if(*t=='-')cof=-1;
							else cof=1;
				else{ while(*t!='X')*i++=*t++;*i=0;i=in;cof=atoi(in);}
				while(*t!='^')t++;while(*t)*s++=*++t;*s=0;s=st;
							step=atoi(st);
							beg=addmonom(cof,step,beg);
			}
				else
					if(strchr(temp,'X'))
					{
						if(strstr(temp,"-X")||strstr(temp,"+X")||*t=='X')
							if(*t=='-')cof=-1;
							else cof=1;
							else{ while(*t!='X')*i++=*t++;*i=0;i=in;cof=atoi(in);}
						step=1;
						beg=addmonom(cof,step,beg);
					}
					else
					{
						cof=atoi(temp);
						step=0;
						beg=addmonom(cof,step,beg);
					}
	}
	return beg;
}
////////////////////////////////////////SUM/////////////////////////////////////////////
TNode* sumpol(TNode *x,TNode *y)
{
	TNode  *go=NULL;
	for(go=y;go;)
	{
		x=addmonom(go->monom->index,go->monom->step,x);
		go=go->next;
	}
	return x;	
}
////////////////////////////////////////SUB/////////////////////////////////////////////
TNode* subpol(TNode *x,TNode *y)
{
	TNode  *go=NULL;
	for(go=y;go;)
	{
		x=addmonom((-1*go->monom->index),go->monom->step,x);
		go=go->next;
	}
	return x;	
}
////////////////////////////////////////MUL/////////////////////////////////////////////
TNode* mulpol(TNode *x,TNode *y,TNode *r)
{
	TNode  *go=NULL,*pe=NULL,*re=r;
	for(go=x;go;)
	{	for(pe=y;pe;)
		{
			re=addmonom((go->monom->index*pe->monom->index),(go->monom->step+pe->monom->step),re);
			pe=pe->next;
		}
		go=go->next;
	}
	return re;	
}
/////////////////////////////////PRINTPOL///////////////////////////////////////////////
int printpol(TNode *start)
{
	TNode *rex=start;
	printf("\n");
	while(rex!=NULL)
	{ 
		if(rex->monom->index!=0)
		{
			if(rex!=start&&rex->monom->index>0)printf("+");
			if(rex->monom->index!=1)
			printf("%d",rex->monom->index);
			if(rex->monom->step!=0)
			{
				printf("X");
				if(rex->monom->step!=1)
				printf("^%d",rex->monom->step);
			}
		}
			rex=rex->next;
	}
	printf("\n");
	return 1;
}
/////////////////////////////////DESTRUCTOR/////////////////////////////////////////////
int destructpoli(TNode *start)
{
	unsigned i=0;
	TNode *ptr=NULL, *T=NULL;
	
	for(ptr = start; ptr; )
	{	
		free(ptr->monom);i+=sizeof(TMonom)+sizeof(TNode);
		ptr = (T = ptr) -> next; 
		free(T);
	}
	return i;
}

blackhard
Программа которую я написал может вычислять вот такие выражения<x^2-4x+12>*<23x+3>; , а как осуществить вычисления выражения вот такого рода (<12X^2+2x>+<12X^7+x+67>)*<x^2-x>.По сути это надо вычислять как выражение в инфиксной форме, но я же не могу засунуть в стек полином?Как можно реализовать подобное вычисление?
volvo
Цитата
Программа которую я написал может вычислять вот такие выражения<x^2-4x+12>*<23x+3>;
Если б она еще делала это правильно - цены б ей не было. А пока смотри, что получается:
<X^2-4X+12>*<23X+3>

Used: 112 bytes
RESULT:
-23X^2+273X+36

Released: 112 bytes

Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.

Хотя должно получиться 23X3-89X2+264X+36

Цитата
я же не могу засунуть в стек полином?
Что тебе мешает это сделать? Засунь указатель beg на полином (главное - чтобы поле данных стека позволяло, то есть, было того же типа, как и beg). Потом вытянешь его и сделаешь нужную операцию...

А насколько все было бы проще при использовании С++...
blackhard
Цитата(volvo @ 24.05.2008 3:09) *

Если б она еще делала это правильно - цены б ей не было. А пока смотри, что получается:
Хотя должно получиться 23X3-89X2+264X+36

Эх считает она правильно ,а вот полином собирает криво (например <2x^2-1>*<3x^4+12x+1>; считает абсолютно верно) буду искать ошибку.Вот у меня возник тут еще 1 вопрос,надо мне еще сделать проверку на переполнение типа в который мы помещаем коэфициент и степень при формировании полинома и при операциях над ними.С отслеживанием переполнения при операциях проблем не возникло, а вот как реализовать отслеживание переполнения при формировании полинома?Грубо говоря как отследить возникнет ли переполнение при переводе строки в число?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.