数据结构报告

Status Append(LinkList *L,Link s) //将指针s所指(彼此以指针相连)的一串结点链接在线形链表L的最后 一个结点之后，并改变链表L的尾指针指向新的尾结点 { int i=1; L->tail->next=s; while(s->next) { s=s->next; i++; } L->tail=s; L->length+=i; return OK; }
开始 菜单
多项式A 是 A.e>B.e 是 将B的项 插入和多 项式 否 判定A,B 的系数 A.c+B.c =0 将和多项式的系数 以A.c+B.c输入
多项式B 否 将A的项插入 和多项式
判定A,B项的指数 A.e>=B.e
删除A，B 的项
输出 和多 项式
本段主讲：易洛安 #include"iostream.h" #include"stdio.h" #include"stdlib.h" #define OK 1 #define ERROR 0 #define TURE 1 #define FALSE 0 #define OVERFLOW 0 #define INFEASIBLE 0 typedef int Status; typedef struct{//项的表示,多项式的项作为LinkList的数据元素 float coef;//系数 int expn;//指数 }term,ElemType;//两个类型名: term用于为LinkList的数据对象名 typedef struct LNode{//结点类型 ElemType data; struct LNode * next; }*Link,*Position;
Status Append(LinkList *L,Link s);//将指针s所指(彼此以指针相连)的一 串结点链接在线形链表L的最后一个结点之后，并改变链表L的尾指 针指向新的尾结点 void FreeNode(Link p);//释放p所指向结点 Status InsFirst(LinkList *L,Link h,Link s);//已知h指向线形链表的头结点， 将s所指结点插入在第一个结点之前 Link InsBefore(LinkList *L,Link p,Link s);//已知p指向线形链表L中的一 个结点，将s所指结点插入在所指结点之前，并修改指针p指向新插 入的结点 Status SetCurElem(Link p,ElemType e);//已知p指向线形链表L中的一个 结点，用e更新所指向结点中数据元素的值 Status ListEmpty(LinkList *L);//若线形链表L为空表，则返回TRUE，否 则返回FALSE Position LocateElem(LinkList *L,ElemType e,int (*cmp)(term a,term b));//返回线形链表L中第1个与e满足函数cmp()判定关系的元素的位 置，若不存在这样的元素，则返回NULL Status Link_Increase(LinkList *L);//给链表按递增排序
本段主讲：杨淳 Status ListEmpty(LinkList *L)//若线形链表L为空表，则返回TRUE，否则返回FALSE { if(L->length) { return FALSE; } else { return TURE; } } Status InitList(LinkList *L)//构造一个空的线形链表L //注意:不能通过指向L的指针给L开辟空间(即不能通过函数给L开辟空间) { Link p; p=(Link)malloc(sizeof(struct LNode)); if(p==NULL)return ERROR; p->next=NULL; L->head=p; L->tail=p; L->length=0; return OK; }
本段主讲人：陈鹤 void CreatPolyn(polynomial *P,int m)//输入m型的系数和指数,建立 表示一元多项式的有序链表P { int i; ElemType e; Link h,s=NULL,q; InitList(P); h=GetHead(P); e.coef=0.0;//设置头结点的数据元素 e.expn=-1; SetCurElem(h,e);//设置头结点的数据元素 for(i=1;i<=m;++i)
Link MakeNode(Link p,ElemType e) //分配由p指向的值为e的结点，并返回OK；若分配失败，返回 ERROR { p=(Link)malloc(sizeof(struct LNode)); if(p==NULL) return ERROR; p->data=e; p->next=NULL; return p; }
Link_Increase(P); }//CreatPolyn void PrintPolyn(polynomial *P)//打印输出一元多项式P { Link q; q=P->head->next; while(q) { if(q==P->head->next) { if(q->data.coef!=1)cout<<q->data.coef; if(q->data.expn==1)cout<<"X"; else cout<<"X^"<<q->data.expn; } else { if(q->data.coef>0) { cout<<"+"; if(q->data.coef!=1)cout<<q->data.coef; if(q->data.expn==1)cout<<"X"; else cout<<"X^"<<q->data.expn; }
{//依次输入m个非零项 cout<<"输入第"<<i<<"项的系数:"; cin>>e.coef; cout<<"输入第"<<i<<"项的指数:"; cin>>e.expn; q=LocateElem(P,e,cmp); if(!q) {//当前链表中不存在该指数项 s=MakeNode(s,e); if(s) { InsFirst(P,h,s);//生成结点并插入链表 } } else { q->data.coef+=e.coef; } }
case 1: //多项式PB中当前结点的指数值小 qb=DelFirst(Pb,hb); InsFirst(Pa,ha,qb); qb=NextPos(hb); ha=NextPos(ha); break; default: cout<<"出错了!"<<endl; }//switch }//while if(!ListEmpty(Pb)) Append(Pa,qb);//链接Pb中剩余结点 FreeNode(hb);//释放Pb的头结点 }//AddPolyn int cmp(term a,term b)//依a的指数值<(或=)(或>)b的指数值,分别返回-1,0和+1 { if(a.expn==b.expn) return ERROR; else return (a.expn-b.expn)/abs(a.expn-b.expn); }
typedef struct{//链表类型 Link head,tail;//分别指向线形链表中的头结点和最后一个结点 int length;//指示线形链表中数据元素的个数 }LinkList; typedef LinkList polynomial;//用带表头结点的有序链表表示多项式 void CreatPolyn(polynomial *p,int m);//输入m型的系数和指数,建立表示一元多项式的有序链 表P void PrintPolyn(polynomial *p);//打印输出一元多项式P void AddPolyn(polynomial *pa,polynomial *pb);//完成多项式相加运算,即:Pa=Pa+Pb,并销毁 一元多项式Pb int cmp(term a,term b);//依a的指数值<(或=)(或>)b的指数值,分别返回-1,0和+1 Status InitList(LinkList *L);//构造一个空的线形链表L Link MakeNode(Link p,ElemType e);//分配由p指向的值为e的结点，并返回OK；若分配失败 ，返回ERROR Position GetHead(LinkList *L);//返回线形链表L中头结点的位置 Position GetLast(LinkList *L);//返回线形链表L中最后一个结点的位置 Position PriorPos(LinkList *L,Link p);//已知p指向线形链表L中的一个结点，返回p所指向结 点的直接前驱的位置，若无前驱，则返回NULL Position NextPos(Link p);//已知p指向线形链表L中的一个结点，返回p所指向结点的直接后 驱的位置，若无后继，则返回NULL ElemType GetCurElem(Link p);//已知p指向线形链表L中的一个结点，返回p所指结点中所指 元素的值 Link DelFirst(LinkList *L,Link h);//已知h指向线形链表的头结点，删除链表中的第一个结点 并返回q
{
case -1://多项式PA中当前结点的指数值小 ha=qa; qa=NextPos(qa); break; case 0: //两者的指数值相等 a.coef=a.coef+b.coef; if(a.coef!=0.0) {//修改多项式PA中当前结点的系数值 SetCurElem(qa,a); ha=qa; } else {//删除多项式PA中当前结点 qa=DelFirst(Pa,ha); FreeNode(qa); } qb=DelFirst(Pb,hb); FreeNode(qb); qb=NextPos(hb); qa=NextPos(ha); break;
else { if(q->data.coef!=1)cout<<q->data.coef; if(q->data.expn==1)cout<<"X"; else cout<<"X^"<<q->data.expn; } } q=q->next;
} cout<<endl;
}
本段主讲：刘敏
void AddPolyn(polynomial *Pa,polynomial *Pb)//完成多项式相加运算 ,即:Pa=Pa+Pb,并销毁一元多项式Pb { Link ha,hb,qa,qb; ElemType a,b; ha=GetHead(Pa);//ha和hb分别指向Pa和Pb的头结点 hb=GetHead(Pb); qa=NextPos(ha);//qa和qb分别指向Pa和Pb中当前结点 qb=NextPos(hb); while(qa&&qb) {//qa和qb均非空 a=GetCurElem(qa);//a和b为两表中当前比较元素 b=GetCurElem(qb); switch(cmp(a,b))
本来本来我们不知道什么是数 据结构
但是，雷老师给了我们光，让我们 知道了什么是——数据结构
老师给我们的目标程序是关于 多项式的运算。 但是我们不才，做的不是很好。 但是我们还是做了，真正的做了！
首先来介绍一下我们的小组成员
• 组长：张林宇 • 组员Fra Baidu bibliotek刘 敏 陈平红 易洛安 陈 鹤 谢 友 杨 淳 韵小琴 司金丽 曹丽婷
本段主讲：司金丽 void FreeNode(Link p) //释放p所指向结点 { free(p); p=NULL; } Link DelFirst(LinkList *L,Link h) //已知h指向线形链表的头结点，删除链表中的第一个结点并以q返回 { Link q=h->next; if(q)//链表非空 { h->next=q->next; if(!h->next) L->tail=h;//h->next=NULL,修改尾结点 L->length--; q->next=NULL; return q; } else return q;//链表空 }