nexo未来骑士团盾牌:关于数据结构！

/*以下代码测试通过*/
#include<stdio.h>
void Sift(int A[],int n,int i)
{
int x=A[i];
int j;
j=2*i+1;
while(j<=n-1)
{
if(j<n-1&&A[j]<A[j+1])
j++;
if(x<A[j]){
A[i]=A[j];
i=j;j=2*i+1;
}
else
break;
}
A[i]=x;
}

void HeapSort(int A[],int n)
{
int x;
int i;
for(i=n/2-1;i>=0;i--)
Sift(A,n,i);
for(i=1;i<=n-1;i++)
{
x=A[0];A[0]=A[n-i];A[n-i]=x;
Sift(A,n-i,0);
}
}

void main()
{
int a[]={99,12,32,14,25,98,24,44};
int i;

printf("Before sort : \n");
for(i=0;i<8;i++)
printf("%d ", a[i]);
printf("\n");

HeapSort(a,8);
printf("Sorted : \n");
for(i=0;i<8;i++)
printf("%d ", a[i]);
printf("\n");
}

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct PolyNode//结构体
{
int coef;
int expn;
struct PolyNode *next;
}PolyNode, *PolyType;

void FreePoly(PolyType *poly)
{
PolyNode *p = *poly, *q;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
*poly = NULL;
}

void DispPoly(PolyType poly)
{
PolyNode *p = poly->next;
printf("%d", poly->expn);
while (p != NULL)
{
printf(", %d, %d", p->coef, p->expn);
p = p->next;
}
printf("\n");
}

void AddPoly(PolyType *res, PolyType left, PolyType right)
{
PolyNode *t, *p = left->next, *q = right->next;
*res = (PolyNode *)malloc(sizeof(PolyNode));
(*res)->expn = (*res)->coef = 0;
(*res)->next = NULL;
t = *res;
while (p!=NULL || q!=NULL)
{
if (p!=NULL && q!=NULL && p->expn==q->expn)
{
if (p->coef+q->coef != 0)
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = p->expn;
t->coef = p->coef+q->coef;
t->next = NULL;
(*res)->expn++;
}
p = p->next;
q = q->next;
}
else if (q==NULL || (p!=NULL && q!=NULL && p->expn>q->expn))
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = p->expn;
t->coef = p->coef;
t->next = NULL;
(*res)->expn++;
p = p->next;
}
else
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = q->expn;
t->coef = q->coef;
t->next = NULL;
(*res)->expn++;
q = q->next;
}
}
}

void SubPoly(PolyType *res, PolyType left, PolyType right)
{
PolyNode *t, *p = left->next, *q = right->next;
*res = (PolyNode *)malloc(sizeof(PolyNode));
(*res)->expn = (*res)->coef = 0;
(*res)->next = NULL;
t = *res;
while (p!=NULL || q!=NULL)
{
if (p!=NULL && q!=NULL && p->expn==q->expn)
{
if (p->coef-q->coef != 0)
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = p->expn;
t->coef = p->coef-q->coef;
t->next = NULL;
(*res)->expn++;
}
p = p->next;
q = q->next;
}
else if (q==NULL || (p!=NULL && q!=NULL && p->expn>q->expn))
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = p->expn;
t->coef = p->coef;
t->next = NULL;
(*res)->expn++;
p = p->next;
}
else
{
t->next = (PolyNode *)malloc(sizeof(PolyNode));
t = t->next;
t->expn = q->expn;
t->coef = -q->coef;
t->next = NULL;
(*res)->expn++;
q = q->next;
}
}
}

void ReadPoly(PolyType *poly)
{
PolyNode *p, *q;
int coef, expn;
*poly = (PolyNode *)malloc(sizeof(PolyNode));
(*poly)->expn = (*poly)->coef = 0;
(*poly)->next = NULL;
scanf("%d%d", &coef, &expn);
while (expn >= 0)
{
p = *poly;
q = (*poly)->next;
while (q!=NULL && q->expn>expn)
{
p = p->next;
q = q->next;
}
if (q!=NULL && q->expn==expn)
{
if (q->coef+coef == 0)
{
p->next = q->next;
((*poly)->expn)--;
free(q);
}
else
q->coef += coef;
}
else
{
p->next = (PolyNode *)malloc(sizeof(PolyNode));
p = p->next;
p->expn = expn;
p->coef = coef;
p->next = q;
((*poly)->expn)++;
}
scanf("%d%d", &coef, &expn);
}
}

int main()
{
PolyType left, right, res;
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

ReadPoly(&left);
ReadPoly(&right);

printf("polynomial #1: ");
DispPoly(left);
printf("polynomial #2: ");
DispPoly(right);

AddPoly(&res, left, right);
printf("polynomial #1 + #2: ");
DispPoly(res);
FreePoly(&res);

SubPoly(&res, left, right);
printf("polynomial #1 - #2: ");
DispPoly(res);
FreePoly(&res);

FreePoly(&left);
FreePoly(&right);

getch();
return 0;
}