main.cpp

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

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

  43. 对于次数很高，但项目很少的多项式，可用链表来表示。
  例如：X^1000－76*X^76＋3*X^3－7可表示为

  ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐
  │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│
  └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘

 在此方式下，编程完成两个多项式的加法与乘法。

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

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

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

FILE *fp;

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

	fscanf(fp,"%d",&c);
	while(c != 0)
	{
		fscanf(fp,"%d",&p);
		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;
		}
		fscanf(fp,"%d",&c);
	}

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

Node* MulLink(Node *la, Node *lb)
{
	Node *rs=NULL;
	Node *s,*t,*pr,*qr;
	int c,p;

	for(s=la; s; s=s->next)
	{
		for(t= lb; t; t=t->next)
		{
			c = s->c * t->c;
			p = s->p + t->p;
			for(qr=rs,pr=NULL; qr; pr=qr,qr=qr->next)
			{
				if(p >= qr->p)
					break;
			}
			if(qr && p == qr->p)
				qr->c += c;
			else
			{
				Node *temp;
				temp = (Node*)malloc(sizeof(Node));
				temp->c = c;
				temp->p = p;
				temp->next = NULL;
				if(!qr)
				{
					if(!pr)
						rs = temp;
					else pr->next = temp;
				}
				else
				{
					temp->next = pr->next;
					pr->next = temp;
				}
			}
		}
	}
	
	return rs;
}

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)
	{
		printf("Cannot open data file!\n");
		return;
	}
	la = CreateLink();
	PrintLink(la);
	lb = CreateLink();
	PrintLink(lb);
	lc = AddLink(la,lb);
	PrintLink(lc);
	lc = MulLink(la,lb);
	PrintLink(lc);
	fclose(fp);
}