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

        大一的时候我们专业开了一门C语言限选课，老师觉得指针太难，所以不讲指针。大三的时候学数据结构，考虑到数据结构比较难，老师不要求代码实现。就这样，两门比较重要的课就这样浑浑噩噩的过去了。后来学Java，算是学的还行，也独立的做过一些导师的项目。只是在找工作的时候，才发现笔试题、面试题到处都是C、C++和数据结构的题。多多少少也因此碰了不少壁。不管怎么样，自己还年轻，以前没学好，现在学也不晚。

        这一系列博客，我会分别用Java和C实现一些数据结构基本操作以及书中提到的问题。一方面算是巩固Java，另一方面算是重新学习数据结构和C语言吧。

        教材：《数据结构与算法分析——C语言描述》（第二版）（Mark Allen Weiss著，冯舜玺译）（机械工业出版社）。

1.链表的基本操作

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

 

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;
struct Node 
{
	ElementType Element;
	Position Next;
};

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

 

//创建链表
List CreateList();
//遍历链表
void TraverseList(List L);
//清空链表
List MakeEmpty(List L);
//判断给定列表是否为空
int IsEmpty(List L);
//判断节点在给定链表中是否为空
int IsLast(Position P, List L);
//在指定的链表中查找给定元素。
//存在则返回其第一次出现的位置，不存在则返回NULL
Position Find(ElementType X, List L);
//删除链表中的某个元素
void Delete(ElementType X, List L);
//在指定链表中查找给定元素的前驱节点
Position FindPrevious(ElementType X, List L);
//在链表给定位置的后面插入元素
void Insert(ElementType X, List L, Position P);
//删除链表
void DeleteList(List L);
//返回链表的头结点
Position Header(List L);
//返回链表第一个数据元素节点
Position First(List L);
//返回当前位置的下一个位置
Position Advance(Position P);
//获取当前位置元素的值
ElementType Retrive(Position P);

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

 

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

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;
struct Node 
{
	ElementType Element;
	Position Next;
};

//创建链表
List CreateList();
//遍历链表
void TraverseList(List L);
//清空链表
List MakeEmpty(List L);
//判断给定列表是否为空
int IsEmpty(List L);
//判断节点在给定链表中是否为空
int IsLast(Position P, List L);
//在指定的链表中查找给定元素。
//存在则返回其第一次出现的位置，不存在则返回NULL
Position Find(ElementType X, List L);
//删除链表中的某个元素
void Delete(ElementType X, List L);
//在指定链表中查找给定元素的前驱节点
Position FindPrevious(ElementType X, List L);
//在链表给定位置的后面插入元素
void Insert(ElementType X, List L, Position P);
//删除链表
void DeleteList(List L);
//返回链表的头结点
Position Header(List L);
//返回链表第一个数据元素节点
Position First(List L);
//返回当前位置的下一个位置
Position Advance(Position P);
//获取当前位置元素的值
ElementType Retrive(Position P);

int IsEmpty(List L)
{
	
	return L->Next == NULL;
}

int IsLast(Position P, List L)
{
	return P->Next == NULL;
}

Position Find(ElementType X, List L)
{
	Position P = L->Next;
	while(P != NULL && P->Element != X)
	{
		P = P->Next;
	}
	return P;
}

void Delete(ElementType X, List L)
{
	Position P,TmpCell;
	P = FindPrevious(X,L);	
	if(!IsLast(P,L))
	{
		TmpCell = P->Next;
		P->Next = TmpCell->Next;
		free(TmpCell);
	}
}

Position FindPrevious(ElementType X, List L)
{
	Position P = L;
	while(P->Next != NULL && P->Next->Element != X)
	{
		P = P->Next;
	}
	return P;
}

void Insert(ElementType X, List L, Position P)
{
	Position TmpCell;
	TmpCell = malloc(sizeof(struct Node));
	if(TmpCell == NULL)
	{
		printf("Out of space!\n");
		return;
	}
	TmpCell->Element = X;
	TmpCell->Next = P->Next;
	P->Next = TmpCell;
}

void DeleteList(List L)
{
	Position P,Tmp;
	P = L->Next;
	L->Next = NULL;
	while(P != NULL)
	{
		Tmp = P->Next;
		free(P);
		P = Tmp;
	}
}

Position Header(List L)
{
	return L;
}

Position First(List L)
{
	return L->Next;
}

Position Advance(Position P)
{
	return P->Next;
}

ElementType Retrive(Position P)
{
	return P->Element;
}

List CreateList()
{
	int i;
	Position P,Tmp;
	List L = malloc(sizeof(struct Node));
	P = L;
	for(i = 0; i < 5; i++)
	{
		Tmp = malloc(sizeof(struct Node));
		Tmp->Element = i;
		P->Next = Tmp;
		P = Tmp;		
	}
	P->Next = NULL;
	return L;
}

void TraverseList(List L)
{
	Position P;
	P = L->Next;
	while(P != NULL)
	{
		printf("%d\n",P->Element);	
		P = P->Next;
	}
}

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

 

 

2.一元N次多项式相加

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

思路一：

数据结构定义：

 

typedef struct Poly
{
	int CoeffArray[11];
	int HighPower;
} *Polynomial;

 实现代码：

 

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

typedef struct Poly
{
	int CoeffArray[11];
	int HighPower;
} *Polynomial;

void ZeroPolynomial(Polynomial Poly)
{
	int i;
	for(i = 0; i < 11; i++)
	{
		Poly->CoeffArray[i] = 0;
	}
	Poly->HighPower = 0;
}

void AddPolynomial(Polynomial Poly1,Polynomial Poly2, Polynomial PolySum)
{
	int i;
	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];
	}
}

int main(void)
{
	int i,j,k;
	Polynomial P1,P2,Sum;
	P1 = malloc(sizeof(struct Poly));
	P2 = malloc(sizeof(struct Poly));
	Sum = malloc(sizeof(struct Poly));
	//初始化
	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("The high power of the Polynomial is %d\n",Sum->HighPower);
	for(k = 0; k <= 10; k++)
	{
		printf("The Coeff of power %d is %d\n",k,Sum->CoeffArray[k]);
	}

	return 0;
}

思路二：

数据结构：

 

typedef struct PolyNode *PtrToNode;

//定义链表节点，也就是多项式中的某一项；
typedef struct PolyNode
{
	int Coeff;
	int Exponent;
	PtrToNode Next;
} PolyNode;

 实现代码：

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

typedef struct PolyNode *PtrToNode;

//定义链表节点，也就是多项式中的某一项；
typedef struct PolyNode
{
	int Coeff;
	int Exponent;
	PtrToNode Next;
} PolyNode;


typedef PtrToNode Polynomial;

/************************************************************
*多项式相加的函数:
*P、Q为存储两个多项式各项的单链表(含头结点)
*Sum为多项式相加结果存放的单链表
*
************************************************************/
void AddPolynomial(Polynomial P,Polynomial Q,Polynomial Sum)
{
	Polynomial PIndex,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;
		}
		else if(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)
			{
				Polynomial PP = malloc(sizeof(struct PolyNode));
				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：待遍历的链表
*************************************************************/
void TraversePolynomial(Polynomial P)
{
	Polynomial Tmp = P->Next;
	while(Tmp != NULL)
	{
		printf("Coeff is %d and Exponent is %d\n",Tmp->Coeff,Tmp->Exponent);
		Tmp = Tmp->Next;
	}
}



int main(void)
{
	Polynomial Poly1,Poly2,Poly3,Poly11,Poly22;
	int i,j;
	Poly1 = malloc(sizeof(struct PolyNode));
	Poly2 = malloc(sizeof(struct PolyNode));
	Poly3 = malloc(sizeof(struct PolyNode));
	Poly11 = Poly1;
	Poly22 = Poly2;

	//创建两个链表时，需要保证是按照指数递减的方式构造的
	for(i = 5;i >= 1;i--)
	{
		Polynomial Tmp  = malloc(sizeof(struct PolyNode));
		Tmp->Coeff = i;
		Tmp->Exponent = i;
		Poly11->Next = Tmp;
		Poly11 = Poly11->Next;
	}
	Poly11->Next = NULL;
	for(j = 11;j >= 3;j--)
	{
		Polynomial Tmp  = malloc(sizeof(struct PolyNode));
		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);
	return 0;
}