利用單連結清單實作多項式的乘法與加法

題目：

利用單連結清單實作對多項式的加法與乘法。

輸入多項式A的項數及各項的系數和指數，多項式B的項數及各項的系數和指數。建立兩個多項式，按照指數降序輸出多項式。注意對系數為負數的情況進行處理。程式結構要清晰。資料結構的定義和函數的聲明寫在頭檔案(.h)中，函數的實作寫在源檔案(.c或.cpp)中。以菜單的形式展示各種運算的操作。

解題思路：

利用單連結清單的資料結構，在讀取資料時就按指數次方排序好，再加法的運算中可以直接按指數的大小進行運算，相比随機的讀入資料，這個方法優化了程式。乘法則是在加法的基礎上把每一項的系數進行相乘并最後求和。注意指數相乘時x指數是相加的。

實作代碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ElemType int 
#define MaxSize 100
typedef struct SSS {          //定義一個鍊式結構體
	ElemType data;            //存放對應指數的資料
	ElemType index;          //存放指數
	struct SSS* next;
}ListNode;

void InitList(ListNode*& L);

void CreatListTail(ListNode*& l, ElemType* a, int n);

bool ListEmpty(ListNode* L);

void DestoryList(ListNode*& l);

int Input(ListNode*& l, ListNode*& j);

ListNode* Plus(ListNode* l, ListNode* j);

ListNode* Seck(ListNode* l, ListNode* j);

bool InsertElem(ListNode* &L, int i, ElemType e);

void Put(ListNode* l)
{
	l = l->next;
	while (l != NULL) {
        if(l->next!=NULL)
		    printf("%dx^%d+", l->data, l->index);
        else 
            printf("%dx^%d",l->data, l->index);
		l = l->next;
	}
    printf("\n");
}


void InitList(ListNode*& L)
{
	L = (ListNode*)malloc(sizeof(ListNode));
	L->next = NULL;
}

void CreatListTail(ListNode*& l, ElemType* a, int n)//尾插法
{
	ListNode* s, * r; int i;
//	l = (ListNode*)malloc(sizeof(ListNode));
	r = l;

	for (i = 0; i < MaxSize; i++) {
		if (a[i] != 0&&a[i]!='\0') {
			s = (ListNode*)malloc(sizeof(ListNode));
			s->data = a[i];
			s->index = i;
			r->next = s;
			r = s;
		}
	}
	r->next = NULL;
	//連結清單的邏輯順序跟數組相同
}

bool ListEmpty(ListNode* L)  //判線性表是否為空表
{
	return(L->next == NULL);
}

void DestoryList(ListNode*& l)
{
	ListNode* pre = l, * p = l->next;

	while (p != NULL) {

		free(pre);
		pre = p;
		p = pre->next;

	}
	free(pre);
}


int Input(ListNode*& l, ListNode*& j)
{
	int flag = 0;
	InitList(l);
	InitList(j);
	int a[MaxSize] = { 0 }, b[MaxSize] = { 0 },in[MaxSize],in2[MaxSize], m = 0, n = 0;
	printf("請輸入第一個多項式：");
	scanf("%d\n", &n);
	m = n*2;
	
	for (int i = 0; i < m; i++) {
		if (i == m - 1) scanf("%d", &in[i]);
		else scanf("%d ", &in[i]);
	}
	//printf("yes");



	for (int i = 1; i <  m; i++) {
		
		a[in[i]] = in[i - 1];
	    i++;
	}	

    CreatListTail(l, a, n);

	printf("請輸入第二個多項式：");
	scanf("%d\n", &n);
	m = n * 2;

	for (int i = 0; i < m; i++) {
		if (i == m - 1) scanf("%d", &in2[i]);
		else scanf("%d ", &in2[i]);
	}
	//printf("yes");



	for (int i = 1; i < m; i++) {

		b[in2[i]] = in2[i - 1];
		i++;
	}


	CreatListTail(j, b, n);

	


	if (!ListEmpty(l) && !ListEmpty(j)) {
		printf("success\n");
	}
	else {
		printf("error\n");
	}
	Put(l);
//	printf("\n");
	Put(j);
	return flag;
}

bool InsertElem(ListNode* &L, int i, ElemType e)//插入元素
{
	int j = 0;
	ListNode* p = L, * s;

	if (j < 0) return false;

	while (j < i - 1 && p != NULL) {
		j++;
		p = p->next;
	}
	if (p == NULL) {
		return false;
	}
	else {
		s = (ListNode*)malloc(sizeof(ListNode));
		s->next = p->next;
		s->data = e;
		p->next = s;
	}

	return true;
}

ListNode* Plus(ListNode* l, ListNode* j)
{
	ListNode* h,*p=l->next,*q=j->next,*s,*r;
	InitList(h);
    s=h;


		while (p != NULL&&q != NULL) {
			if (p->index == q->index) {
				r = (ListNode*)malloc(sizeof(ListNode));
				r->data = p->data + q->data;
				r->index = p->index;
                s->next = r;
                s = r;
                p=p->next;
                q=q->next;
			}
			else if ( p->index < q->index ) {
				r = (ListNode*)malloc(sizeof(ListNode));
				r->data = p->data;
				r->index = p->index;
                s->next = r;
                s = r;
                p=p->next;
			}
			else if ( p->index > q->index ){
				r = (ListNode*)malloc(sizeof(ListNode));
				r->data = q->data;
				r->index = q->index;
                s->next = r;
                s = r;
                q=q->next;                
		    }
            
        }

		while(p!=NULL){
				r = (ListNode*)malloc(sizeof(ListNode));
				r->data = p->data;
				r->index = p->index;
                s->next = r;
                s = r;
                p=p->next;			
		}
		while(q!=NULL){
				r = (ListNode*)malloc(sizeof(ListNode));
				r->data = q->data;
				r->index = q->index;
                s->next = r;
                s = r;
                q=q->next;   			
		}

        s->next=NULL;
  //  Put(h);
	return h;
}

ListNode* Seck(ListNode* l, ListNode* j)
{
	ListNode*p=l->next,*q=j->next,*g,*h,*s,*r;
	int flag=0;

	InitList(h);   //初始化h，h作為每個元素每次乘的和連結清單

	while(p!=NULL){
		while(q!=NULL){
				InitList(g),    r=g;
			
			s=(ListNode*)malloc(sizeof(ListNode));
			s->data=p->data*q->data;
			s->index=p->index+q->index;
			r->next=s;
			r=s;
			r->next=NULL;

			h=Plus(g,h);
			DestoryList(g);

			q=q->next;
		}
		q=j->next;
		//printf("yes\n");
		p=p->next;
	}

    Put(h);
	return h;
}

int main()
{
	int i = 0,n=0,k=0,flag=0;
	ListNode* l,*j,*p,*s;
	InitList(l), InitList(j);

	/*printf("********************\n1.輸入兩個多項式\n2.加法\n3.乘法\n4.退出\n********************\n");
	scanf("%d", &k);
	while (1) {
		switch (k){
		    case 1: Input(l, j);    break;
			case 2: p=Plus(l, j, flag); break;
			case 3: s=Seck(l, j,flag); break;
			case 4: return 0;   break;
		}
		scanf("%d", &k);
	}

*/
	Input(l, j);
    p=Plus(l,j);
    Put(p);

	s=Seck(l,j);

    system("pause");
	return 0;
}
           

記得點贊哦^ - ^