線形表の練習問題二

1、firstをすでに知っているのはシングルチェーン表のヘッダーポインタで、チェーンテーブルに記憶されているのはすべて整数データで、下記の演算を実現する再帰アルゴリズムを書き出してみます.
(1)チェーンの中の最大整数を求める:
(2)チェーンの結点個数を求めます.
(3)チェーンのすべての要素の平均値を求めます.

#include 
using namespace std;
typedef int Elemtype; 
typedef struct node
{
	Elemtype data;
	struct node *link;
} Node,*LinkList;
//    ：        
int Max(LinkList first)
{
	if(first->link == NULL) return first->data;	//       ，     
	int temp = Max(first->link);
	if(first->data>temp) return first->data;
	else return temp;
}
//    ：        
int Num(LinkList first)
{
	if(first == NULL) return 0;	//        0
	return 1+Num(first->link);
}
//    ：           
float Avg(LinkList first,int &n)
{
	if(first->link == NULL)	//       
	{
		n = 1;
		return (float)(first->data);
	}
	else
	{
		float Sum = Avg(first->link,n)*n;	//            
		n++;
		return (first->data + Sum)/n;
	}
}

2、多項式をチェーンテーブルで記憶する構造の定義は以下の通りです.

typedef struct Term {	//     
	float coef;		//  
	int exp;		//  
	struct Term *link;	//   
} Term,*Polynomial;

は試しにアルゴリズムを作成し、多項式の係数と指数のセットを入力し、指数関数的にべき乗させる方式で多項式のチェーンテーブルを構築し、このチェーンテーブルには表頭の結節点があることを要求する.
入力された指数がチェーンテーブルのある項目の指数と等しい場合、新しい項目は追加されず、廃棄情報を報告します.入力シーケンス全体は、入力係数が0のフラグで終了します.
アルゴリズムの最初はPolynominal createPolyです.

Polynomial createPoly()
{
	Polynomial head,p,pre,s;
	float c;int i = 0,e;
	cout<exp = -1;head->link = NULL;//     exp   -1
	while(1)
	{
		cout<>c>>e;
		if(c==0) break;
		s = new Term;
		s->coef = c; s->exp = e;
		p = head; pre = NULL;
		while(p!=NULL&&p->exp>e)
		{
			pre = p;
			p = p->link;
		}
		if(p!=NULL&&p->exp==e) cout<link = p;
			pre->link = s;
		}
	}
	return head;
}

多項式に新しい項目を挿入するアルゴリズムInsertを与えます.各項目の指数eiは、逓減順に配列されています.em-1>em-2...>e 0>0 アルゴリズムの機能は、多項式の場合です.
新しい項目の指数に等しい項目がない場合、この新しい項目を多項式チェーンテーブルの適切な位置に挿入します.新しい指数に等しい項目が多項式にある場合、それらを結合します.

typedef struct Term
{
	float coef;
	int exp;
	struct Term *link;
} Term,*Polynominal;
void Insert(Polynominal poly,Term *t)
{
	Polynominal p = poly,pre = NULL;
	while(p!=NULL&&p->exp>t->exp)
	{
		pre = p;
		p = p->link;
	}
	if(p->exp==t->exp)
	{
		if(p->coef + t->coef!=0)
		{
			p->coef=p->coef+t->coef; //  
		}
		else
		{
			pre->link = p->link;	//  p  
			delete p;
		}
	}
	else if(pre==NULL)	//  ，     
	{
		t->link = poly;
		poly = t;
	}
	else	//p->expexp   p  （  p=NULL,  ）
	{
		pre->link = t;
		t->link = p;
	}
}