重学数据结构001——链表基本操作与一元多项式相加

1.链表的基本操作

链表数据结构的定义：由于链表一方面需要在节点中存储数据，另一方面还需要存储"线索"，因此，通常采用结构体定义链表节点数据类型。

structNode;
typedefstructNode*PtrToNode;
typedefPtrToNodeList;
typedefPtrToNodePosition;
typedefintElementType;
structNode
{
ElementTypeElement;
PositionNext;
};

链表的操作不算太多，下面是一些常用的操作：

//创建链表
ListCreateList();
//遍历链表
voidTraverseList(ListL);
//清空链表
ListMakeEmpty(ListL);
//判断给定列表是否为空
intIsEmpty(ListL);
//判断节点在给定链表中是否为空
intIsLast(PositionP,ListL);
//在指定的链表中查找给定元素。
//存在则返回其第一次出现的位置，不存在则返回NULL
PositionFind(ElementTypeX,ListL);
//删除链表中的某个元素
voidDelete(ElementTypeX,ListL);
//在指定链表中查找给定元素的前驱节点
PositionFindPrevious(ElementTypeX,ListL);
//在链表给定位置的后面插入元素
voidInsert(ElementTypeX,ListL,PositionP);
//删除链表
voidDeleteList(ListL);
//返回链表的头结点
PositionHeader(ListL);
//返回链表第一个数据元素节点
PositionFirst(ListL);
//返回当前位置的下一个位置
PositionAdvance(PositionP);
//获取当前位置元素的值
ElementTypeRetrive(PositionP);

下面是实现基本操作以及简单使用的一个完整的例子：

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

structNode;
typedefstructNode*PtrToNode;
typedefPtrToNodeList;
typedefPtrToNodePosition;
typedefintElementType;
structNode
{
ElementTypeElement;
PositionNext;
};

//创建链表
ListCreateList();
//遍历链表
voidTraverseList(ListL);
//清空链表
ListMakeEmpty(ListL);
//判断给定列表是否为空
intIsEmpty(ListL);
//判断节点在给定链表中是否为空
intIsLast(PositionP,ListL);
//在指定的链表中查找给定元素。
//存在则返回其第一次出现的位置，不存在则返回NULL
PositionFind(ElementTypeX,ListL);
//删除链表中的某个元素
voidDelete(ElementTypeX,ListL);
//在指定链表中查找给定元素的前驱节点
PositionFindPrevious(ElementTypeX,ListL);
//在链表给定位置的后面插入元素
voidInsert(ElementTypeX,ListL,PositionP);
//删除链表
voidDeleteList(ListL);
//返回链表的头结点
PositionHeader(ListL);
//返回链表第一个数据元素节点
PositionFirst(ListL);
//返回当前位置的下一个位置
PositionAdvance(PositionP);
//获取当前位置元素的值
ElementTypeRetrive(PositionP);

intIsEmpty(ListL)
{

returnL->Next==NULL;
}

intIsLast(PositionP,ListL)
{
returnP->Next==NULL;
}

PositionFind(ElementTypeX,ListL)
{
PositionP=L->Next;
while(P!=NULL&&P->Element!=X)
{
P=P->Next;
}
returnP;
}

voidDelete(ElementTypeX,ListL)
{
PositionP,TmpCell;
P=FindPrevious(X,L);
if(!IsLast(P,L))
{
TmpCell=P->Next;
P->Next=TmpCell->Next;
free(TmpCell);
}
}

PositionFindPrevious(ElementTypeX,ListL)
{
PositionP=L;
while(P->Next!=NULL&&P->Next->Element!=X)
{
P=P->Next;
}
returnP;
}

voidInsert(ElementTypeX,ListL,PositionP)
{
PositionTmpCell;
TmpCell=malloc(sizeof(structNode));
if(TmpCell==NULL)
{
printf("Outofspace!\n");
return;
}
TmpCell->Element=X;
TmpCell->Next=P->Next;
P->Next=TmpCell;
}

voidDeleteList(ListL)
{
PositionP,Tmp;
P=L->Next;
L->Next=NULL;
while(P!=NULL)
{
Tmp=P->Next;
free(P);
P=Tmp;
}
}

PositionHeader(ListL)
{
returnL;
}

PositionFirst(ListL)
{
returnL->Next;
}

PositionAdvance(PositionP)
{
returnP->Next;
}

ElementTypeRetrive(PositionP)
{
returnP->Element;
}

ListCreateList()
{
inti;
PositionP,Tmp;
ListL=malloc(sizeof(structNode));
P=L;
for(i=0;i<5;i++)
{
Tmp=malloc(sizeof(structNode));
Tmp->Element=i;
P->Next=Tmp;
P=Tmp;
}
P->Next=NULL;
returnL;
}

voidTraverseList(ListL)
{
PositionP;
P=L->Next;
while(P!=NULL)
{
printf("%d\n",P->Element);
P=P->Next;
}
}

intmain(void)
{
//创建链表
ListL=CreateList();
//查找元素1在链表中的位置
PositionP=Find(1,L);
//在元素1后面插入元素8
Insert(8,L,P);
//查找元素8前驱结点
P=FindPrevious(8,L);
//遍历链表
TraverseList(L);
return0;
}

2.一元N次多项式相加

对于两个一元多项式，如果需要对他们进行多项式相加操作，常见的两种思路如下：(1)对于一个多项式，保存其最高项次数HighPowder，以及一个该多项式对应次数分别为0-HighPowder的各项的系数的数组()。(2)多项式中系数不为零的每一项，保存其系数与该项的次数。下面分别用这两种思路实现一元多项式加法操作。

思路一：

数据结构定义：

typedefstructPoly
{
intCoeffArray[11];
intHighPower;
}*Polynomial;

实现代码：

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

typedefstructPoly
{
intCoeffArray[11];
intHighPower;
}*Polynomial;

voidZeroPolynomial(PolynomialPoly)
{
inti;
for(i=0;i<11;i++)
{
Poly->CoeffArray[i]=0;
}
Poly->HighPower=0;
}

voidAddPolynomial(PolynomialPoly1,PolynomialPoly2,PolynomialPolySum)
{
inti;
ZeroPolynomial(PolySum);
PolySum->HighPower=Poly1->HighPower>Poly2->HighPower?
Poly1->HighPower:Poly2->HighPower;
for(i=PolySum->HighPower;i>=0;i--)
{
PolySum->CoeffArray[i]=Poly1->CoeffArray[i]+Poly2->CoeffArray[i];
}
}

intmain(void)
{
inti,j,k;
PolynomialP1,P2,Sum;
P1=malloc(sizeof(structPoly));
P2=malloc(sizeof(structPoly));
Sum=malloc(sizeof(structPoly));
//初始化
ZeroPolynomial(P1);
ZeroPolynomial(P2);
P1->HighPower=10;
for(i=10;i>=0;i--)
{
P1->CoeffArray[i]=i;
}

P2->HighPower=8;
for(j=8;j>=0;j--)
{
P2->CoeffArray[j]=j;
}
P2->CoeffArray[8]=8;
AddPolynomial(P1,P2,Sum);

printf("ThehighpowerofthePolynomialis%d\n",Sum->HighPower);
for(k=0;k<=10;k++)
{
printf("TheCoeffofpower%dis%d\n",k,Sum->CoeffArray[k]);
}

return0;
}

思路二：

数据结构：

typedefstructPolyNode*PtrToNode;

//定义链表节点，也就是多项式中的某一项；
typedefstructPolyNode
{
intCoeff;
intExponent;
PtrToNodeNext;
}PolyNode;

实现代码：

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

typedefstructPolyNode*PtrToNode;

//定义链表节点，也就是多项式中的某一项；
typedefstructPolyNode
{
intCoeff;
intExponent;
PtrToNodeNext;
}PolyNode;


typedefPtrToNodePolynomial;

/************************************************************
*多项式相加的函数:
*P、Q为存储两个多项式各项的单链表(含头结点)
*Sum为多项式相加结果存放的单链表
*
************************************************************/
voidAddPolynomial(PolynomialP,PolynomialQ,PolynomialSum)
{
PolynomialPIndex,QIndex,SumIndex;
PIndex=P->Next;
QIndex=Q->Next;
SumIndex=Sum;
while(!(PIndex==NULL&&QIndex==NULL))
{
if(PIndex==NULL)
{
SumIndex->Next=QIndex;
QIndex=QIndex->Next;
SumIndex=SumIndex->Next;
}
elseif(QIndex==NULL)
{
SumIndex->Next=PIndex;
PIndex=PIndex->Next;
SumIndex=SumIndex->Next;
}
else
{
if(PIndex->Exponent>QIndex->Exponent)
{
SumIndex->Next=PIndex;
PIndex=PIndex->Next;
SumIndex=SumIndex->Next;
//continue在判断下面if条件时会有异常，类似Java
//的空引用异常
continue;
}
if(PIndex->Exponent==QIndex->Exponent)
{
PolynomialPP=malloc(sizeof(structPolyNode));
PP->Exponent=PIndex->Exponent;
PP->Coeff=PIndex->Coeff+QIndex->Coeff;
SumIndex->Next=PP;
PIndex=PIndex->Next;
QIndex=QIndex->Next;
SumIndex=SumIndex->Next;
continue;
}
if(PIndex->Exponent<QIndex->Exponent)
{
SumIndex->Next=QIndex;
QIndex=QIndex->Next;
SumIndex=SumIndex->Next;
continue;
}
}
}
SumIndex->Next=NULL;
}

/************************************************************
*遍历单链表(含头结点)函数:
*P：待遍历的链表
*************************************************************/
voidTraversePolynomial(PolynomialP)
{
PolynomialTmp=P->Next;
while(Tmp!=NULL)
{
printf("Coeffis%dandExponentis%d\n",Tmp->Coeff,Tmp->Exponent);
Tmp=Tmp->Next;
}
}



intmain(void)
{
PolynomialPoly1,Poly2,Poly3,Poly11,Poly22;
inti,j;
Poly1=malloc(sizeof(structPolyNode));
Poly2=malloc(sizeof(structPolyNode));
Poly3=malloc(sizeof(structPolyNode));
Poly11=Poly1;
Poly22=Poly2;

//创建两个链表时，需要保证是按照指数递减的方式构造的
for(i=5;i>=1;i--)
{
PolynomialTmp=malloc(sizeof(structPolyNode));
Tmp->Coeff=i;
Tmp->Exponent=i;
Poly11->Next=Tmp;
Poly11=Poly11->Next;
}
Poly11->Next=NULL;
for(j=11;j>=3;j--)
{
PolynomialTmp=malloc(sizeof(structPolyNode));
Tmp->Coeff=j;
Tmp->Exponent=j;
Poly22->Next=Tmp;
Poly22=Poly22->Next;
}
Poly22->Next=NULL;
TraversePolynomial(Poly1);
printf("*****************************************\n");
TraversePolynomial(Poly2);
AddPolynomial(Poly1,Poly2,Poly3);
printf("*****************************************\n");
TraversePolynomial(Poly3);
return0;
}