linklist.cpp

一个多重链表的演示

#include "LinkList.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void InitList( SLink &L )
{
  // 创建一个带头结点的空链表,L 为指向头结点的指针
  L = new LNode;
  if (!L) exit(1); 
  // 存储空间分配失败
  L->next = NULL;
} // nitList 

void DestroyList( SLink &L)
{
  // 销毁以L为头指针的单链表，释放链表中所有结点空间
  SLink p;
  while (L)
  {
    p = L;
    L = L->next;
    delete p;
  } // while
  L = NULL;
} // DestroyList

bool GetElem ( SLink L, int pos, ElemType &e )
{
  // 若1≤pos≤LengthList(L)，则用 e 带回指针L指向头结点的单链表
  // 中第 pos 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE

  SLink p = L->next; int j =1; // 变量初始化，p 指向第一个结点

  while ( p && j< pos )
  {
    // 顺结点的指针向后查找，直至 p 指到第pos个结点或 p 为空止
    p = p->next; 
    ++j;
  } // while

  if ( !p || j>pos ) return FALSE; // 链表中不存在第 pos 个结点
  e = p->data;  // 取到第 pos 个元素
  return TRUE;
} // GetElem

bool ListInsert ( SLink &L, int pos, ElemType e )
{
  // 若1≤pos≤LengthList(L)+1，则在指针L指向头结点的单链表
  // 的第 pos 个元素之前插入新的元素 e，且返回函数值为 TRUE,
  // 否则不进行插入且返回函数值为 FALSE
  SLink p=L; 
  int j=0;
  while(p && j<pos-1)
  {   // 查找第pos-1个结点，并令指针p指向该结点
    p=p->next; ++j; 
  } // while
  if(!p||j>pos-1)
    return FALSE;  // 参数不合法，pos 小于1或者大于表长+1
  LNode *s=new LNode;
  if (!s) exit(1);  // 存储空间分配失败
  s->data=e;  // 创建新元素的结点
  s->next=p-> next; 
  p->next=s; // 修改指针
  return TRUE;
}

bool ListDelete ( SLink &L, int pos, ElemType &e)
{
  // 若1≤pos≤LengthList(L)，则删除指针L指向头结点的单链表
  // 中第 pos 个元素并以 e 带回其值，返回函数值为 TRUE，
  // 否则不进行删除操作且返回函数值为 FALSE
  SLink p = L; 
  int j = 0;
  while (p->next && j < pos-1)
  {   // 寻找第pos个结点，并令p指向其前驱
    p = p->next; ++j;
  }
  if (!(p->next) || j > pos-1)
    return FALSE;   // 删除位置不合理
  SLink q = p->next; p->next = q->next; //修改指针
  e = q->data; delete(q);       // 释放结点空间 
  return TRUE;
} // ListDelete_L

bool ListTravel(SLink L)
{
  SLink p=L->next;
  printf("\n");
  while(p)
  {
    printf("%2fx^%d\t",p->data.ceof,p->data.exp);
    p=p->next;
  }
  return TRUE;
}

/***********************************************************
*函数名：void InitMultiPolyList(SLink &L)
*功能: 创建以L为头结点的多项式，从键盘输入多项式的系数和指数,
格式为"系数,指数",当输入的系数为接近于0.0的浮点数时，完成输入。
创建的多项式中结点的指数是无序的。
*输入：多项式链表头结点
*输出：无
*作者：ltyong
*时间：04/27/2005
***********************************************************/
void CreateMultiPolyList(SLink &L)
{
	float coef;
	int exp;
	ElemType e;
	InitList(L);
	printf("Input the node of the MultiPoly, the format is (ceof,exp), (0,n) to exit\n");
	scanf("%f,%d",&coef,&exp);
	e.ceof=coef;
	e.exp=exp;

	while(abs(coef-0.0)>0.0001)
	{
		ListInsert (L, 1, e );
		scanf("%f,%d",&coef,&exp);
		e.ceof=coef;
		e.exp=exp;
	}	
}
/***********************************************************
*函数名:void GetResult(SLink x,SLink y,SLink &z)
*功能：计算多项式x和多项式y的成绩，结果保存在z为头结点的链表中
，求得的结果中指数是无序的
*输入：参与乘法运算的两个多项式的头结点，和保存结果多项式的头结点
*输出：无
*作者：ltyong
*时间：04/27/2005
***********************************************************/
void GetResult(SLink x,SLink y,SLink &z)
{
	SLink px,py,pz;
	int isfound=0;
	ElemType e;
	CreateMultiPolyList(x);
	CreateMultiPolyList(y);
	InitList(z);
	px=x->next;	
	while(px)
	{
		py=y->next;
		while(py)
		{
			e.exp=px->data.exp+py->data.exp;
			e.ceof=px->data.ceof*py->data.ceof;
			pz=z->next;
			
			/*求得的乘积最好是按照指数递减的方式排列，本程序未考虑*/
			while(pz)
			{
				/*在Z中找到一个指数项与当前x,y中两项相等的项，则合并,合并后进行下一次处理*/
				if(pz->data.exp==e.exp)
				{
					isfound=1;
					pz->data.ceof+=e.ceof;/*对于e.ceof为0的情况，怎样处理？？？？？本程序未考虑*/
					break;
				}
				pz=pz->next;
			}
			/*在Z中未找到一个指数项与当前x,y中两项相等的项，则直接将该项插入到z中*/
			if((!pz)||(!isfound))
				ListInsert(z,1,e);	
			py=py->next;
		}
		px=px->next;
	}
}