링크 를 사용 하여 다항식 덧셈 을 하 다.

링크 만 들 기
데이터 구 조 는 단일 체인 표 로 선택 되 고 여러 가지 식 에 매개 변수 와 지 수 를 포함 하기 때문에 링크 에 포 함 된 요 소 는 매개 변수, 지수, 링크 지침 이 어야 한다. 다음 과 같다.

typedef int Elemtype;
struct LkList
{
	int para;
	int index;
	LkList* next;
};
typedef LkList* LIST;
typedef LkList* Position;

링크 데이터 가 져 오기
우 리 는 먼저 데 이 터 를 링크 에 가 져 옵 니 다. 이것 은 링크 의 생 성과 함께 놓 습 니 다.주의해 야 할 것 은 모든 지수 항목 을 가 져 와 야 한 다 는 것 이다. 즉, 하나의 지수 항목 의 매개 변수 가 0 이면 가 져 와 야 한 다 는 것 이다.

void ini_LkList(LIST L, int para, int index)
{
	Position p, add;
	p = new LkList;
	add = new LkList;
	p->next = L;
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = add;
	add->next = NULL;
	add->para = para;
	add->index = index;
}

링크 정렬
링크 를 만 든 후에 덧셈 을 하려 면 지수 항목 과 더 해 야 하기 때문에 우 리 는 링크 를 정렬 해 야 합 니 다.우 리 는 거품 정렬 디자인 알고리즘 을 참고 하여 다음 과 같다.

for (int j = 0; j < maxList - 1 - i; j++)
{
	if (three != NULL)
	{
		if (two->index < three->index)
		{
			change(one, two, three);
			display(L);
			one = one->next;
			two = three->next;
			three = two->next;
		}
	}
}

여기 서 원 은 두 요 소 를 비교 하기 전의 그 요 소 를 대표 한다.two 와 three 는 비교 요 소 를 대표 한다.주의해 야 할 것 은 마지막 두 줄 의 코드 입 니 다. 순서 가 바 뀌 었 기 때문에 전달 하 는 상황 도 순서대로 교환 해 야 합 니 다.
덧셈
정렬 한 후에 두 개의 링크 의 대응 부분 을 더 하면 우 리 는 마지막 에 추 가 된 링크 를 얻 을 수 있다.
전체 코드

/*      
**HIT Visual Lab
**2019.02.22  */

#include "stdafx.h"
#include 
#include "stdlib.h"

#define maxList 10

using namespace std;

typedef int Elemtype;
struct LkList
{
	int para;
	int index;
	LkList* next;
};
typedef LkList* LIST;
typedef LkList* Position;

void ini_LkList(LIST L, int para, int index);
void display(LIST L);
void change(Position first, Position second, Position third);
void ListSort(LIST L);
LIST adding(LIST L1, LIST L2);

int main()
{
	LIST L1, L2, L;
	L1 = new LkList;
	L2 = new LkList;
	L = new LkList;
	L1->para = 0;
	L1->index = 0;
	L1->next = NULL;
	L2->para = 0;
	L2->index = 0;
	L2->next = NULL;
	//   
	for (int i = 0; i < maxList; i++)
	{
		ini_LkList(L1, i - 1, i + 1);
	}
	//  
	for (int i = 0; i < maxList; i++)
	{
		ini_LkList(L2, -i + 1, i - 1);
	}
	display(L1);
	display(L2);
	ListSort(L1);
	display(L1);
	ListSort(L2);
	display(L2);
	L = adding(L1, L2);
	display(L);
	return 0;
}

//    
void ini_LkList(LIST L, int para, int index)
{
	Position p, add;
	p = new LkList;
	add = new LkList;
	p->next = L;
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = add;
	add->next = NULL;
	add->para = para;
	add->index = index;
}

//    
void display(LIST L)
{
	Position p;
	p = L;
	while (p != NULL)
	{
		cout << p->index << " ";
		p = p->next;
	}
	cout << endl;
}

//      
void change(Position first, Position second, Position third)
{
	Position p, r;
	p = new LkList;
	r = new LkList;
	first->next = third;
	second->next = third->next;
	third->next = second;
}

//    
void ListSort(LIST L)
{
	Position one, two, three;
	one = new LkList;
	two = new LkList;
	three = new LkList;
	for (int i = 0; i < maxList - 1; i++)
	{
		one = L;
		one->index = L->index;
		one->para = L->para;

		two = L->next;
		two->index = L->next->index;
		two->para = L->next->para;

		three = L->next->next;
		three->index = L->next->next->index;
		three->para = L->next->next->para;

		for (int j = 0; j < maxList - 1 - i; j++)
		{
			if (three != NULL)
			{
				if (two->index < three->index)
				{
					change(one, two, three);
					//display(L);
					one = one->next;
					two = three->next;
					three = two->next;
				}
			}
		}
	}
}

LIST adding(LIST L1, LIST L2)
{
	LIST res;
	res = new LkList;
	res->index = -1;
	res->para = -1;
	res->next = NULL;
	Position p_high, p_low, p;
	if (L1->next->index >= L2->next->index)
	{
		p_high = L1->next;
		p_low = L2->next;
	}
	else
	{
		p_high = L2->next;
		p_low = L1->next;
	}
	while (p_high != NULL)
	{
		if (p_high->index != p_low->index)
		{
			ini_LkList(res, p_high->para, p_high->index);
			p_high = p_high->next;
		}
		else
		{
			ini_LkList(res, p_high->para + p_low->para, p_high->index + p_low->index);
			p_high = p_high->next;
			p_low = p_low->next;
		}
	}
	return res;
}