main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/*****************************************************************************************

  44. (一元多项式加法) 实现两个整系数一元多项式的加法。例如, 对于多项式
 5*X^6＋4*X^3－7*X^4＋1 与多项式 50*X^2＋4*X, 运算结果为：
 5*X^6－7*X^4＋4*X^3＋50*X^2＋4*X＋1。

   程序要求：键盘输入多项式的各项系数及指数，每项系数及指数为一组数据（系
 数及指数之一可为零），以'0,0'结束一个多项式的输入，结果按降幂排列，同类
 项要合并（指数最大不超过３０）。

   上例第一式的输入为：    5,6
                           4,3
                          -7,4
                           1,0
                           0,0
  输出结果应为：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.

  *****************************************************************************************/

#include <stdio.h>
#include <malloc.h>

typedef struct tagNode
{
	int c;
	int p;
	tagNode *next;
} Node;

FILE *fp;

void sort(Node *l)
{
	Node *cur,*max,*pos;
	for(pos=l; pos; pos=pos->next)
	{
		max = pos;
		for(cur=pos->next; cur; cur=cur->next)
		{
			if(cur->p > max->p)
				max = cur;
		}
		if(max != pos)
		{
			int c,p;
			c = max->c;
			p = max->p;
			max->c = pos->c;
			max->p = pos->p;
			pos->c = c;
			pos->p = p;
		}
	}
}

Node* CreateLink()
{
	int c,p;
	Node *head = NULL;
	Node *tail = NULL;
	Node *temp = NULL;

	
	while(1)
	{
		fscanf(fp,"%d",&c);
		fscanf(fp,"%c",&p);
		fscanf(fp,"%d",&p);

		if(c==0 && p==0)
			break;

		temp = (Node*)malloc(sizeof(Node));
		temp->c = c;
		temp->p = p;
		temp->next = NULL;
		if(!head)
		{
			tail = head = temp;
		}
		else 
		{
			tail->next = temp;
			tail = tail->next;
		}
	}

	return head;
}

Node* AddLink(Node *la, Node *lb)
{
	Node *head=NULL,*tail=NULL,*temp;
	Node *s,*t;
	s = la;
	t = lb;

	while(s && t)
	{
		temp = (Node*)malloc(sizeof(Node));
		temp->next = NULL;
		if(s->p == t->p)
		{
			temp->c = s->c + t->c;
			temp->p = s->p;
			s = s->next;
			t = t->next;
		}
		else if(s->p > t->p)
		{
			temp->c = s->c;
			temp->p = s->p;
			s = s->next;
		}
		else 
		{
			temp->c = t->c;
			temp->p = t->p;
			t = t->next;
		}
		if(!head)
		{
			head = tail = temp;
		}
		else 
		{
			tail->next = temp;
			tail = tail->next;
		}
	}
	if(!t)
		s = t;
	while(s)
	{
		temp = (Node*)malloc(sizeof(Node));
		temp->c = s->c;
		temp->p = s->p;
		s = s->next;
		if(!head)
		{
			head = tail = temp;
		}
		else 
		{
			tail->next = temp;
			tail = tail->next;
		}
	}

	return head;
}

void PrintLink(Node* l)
{
	Node* cur = l;
	while(cur)
	{
		if(cur->c > 0 && cur != l)
			printf("+"); 
		if(cur->p != 0)
		{
			if(cur->p != 1)
			{
				if(cur->c != 1)
				{
					if(cur->c != -1)
						printf("%dX^%d",cur->c,cur->p);
					else printf("-X^%d",cur->p);
				}
				else
					printf("X^%d",cur->p);
			}
			else
			{
				if(cur->c != 1)
				{
					if(cur->c != -1)
						printf("%dX",cur->c);
					else printf("-X");
				}
				else
					printf("X");
			}
		}
		else printf("%d",cur->c);
		cur = cur->next;
	}
	printf("\n");
}

void main()
{
	Node *la,*lb,*lc;

	fp = fopen("data.txt","r");
	if(!fp) return; 

	la = CreateLink();
	sort(la);
	PrintLink(la);
	lb = CreateLink();
	sort(lb);
	PrintLink(lb);
	lc = AddLink(la,lb);
	sort(lc);
	PrintLink(lc);

	fclose(fp);
}