2023年数据结构实验报告10

数据结构实验报告一一实验4学号：姓名：得分：一、实验目的I、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和(带头结点)单链表；3、了解有序表。二、实验内容1、(必做题)假设有序表中数据元素类型是整型，请采用顺序表或(带头结点)单链表实现：(1)OrderInsert(&L,e,int(*compare)(a,b))//根据有序鉴定函数compare,在有序表L的适当位置插入元素e；(2)0rdcrlnput(&L,int(*comparc)(a,b))〃根据有序鉴定函数compare,并运用有序插入函数0rderInserl,构造有序表L；0rdcrMerge(&La,&Lb,&Lc,int(*compare)())〃根据有序鉴定函数compare,将两个有序表La和Lb归并为一个有序表Lc。2、(必做题)请实现：(1)开事多项式的构造，升幕多项式是指多项式的各项按指数升序有序，约定系数不能等于0,指数不能小于0；(2)两个升基多项式的相加。三、算法描述(采用自然语言描述)创建带头节点的链表，输入两个有序表数据LaLb归并两个有序表得有序表Lcvoidvisit(LinkList*NewList,void(*Show)())printf("有序表如下：5")；printf("第一个有序表为:\n");(*Show)(NewList+0);printf("\n")；printf("第二个有序表为：'n")；(*Show)(NewList+1);printf(H\n");printf("归并后有序表为:\n");(*Show)(NewList+2);printf("'n")；)intmain(){LinkList*NewList=NULL;LinkList*L;inti,e；printf("请按规定输入数据\n")；NewList=Initialize(NewList);Insert(NewList);for(i=0;i<2；i++)OrderMerge(NewList+i,NewList+2,compare);visit(NewList,Show);L=NewList；printf("\n请输入将要插入的e:\n");seanf("%d",&e);Oiderinsert((NewList+i),e,compare);Printf("对归并后有序表插入e后得\n”)；Show(NewList+2);return0;)#include<stdio.h>#include<malloc.h>typedefstructnode(intxi；ntzi;structnode*next;}Node;Node*Crcat()〃用链表储存多项式的序数与指数{Node*head,*p,火q;inior,in;head=(Node*)mal1oc(sizeof(Node));head->next=NULL;q=head：printf(”请输入多项式的序数与指数\n(注意：按照指数升序输入,系数不能等于0且指数不能小于0,序数与指数用空格隔开，并以00结束输入)5”)；seanf("%d%d'\&or,&in);while(or){p=(Node*)ma1loc(sizeof(Node))；p->xi=or;p->zi=in:p->next=q—>next;q->ncxt=p;q=P;scanf("%d%d",&or,&in);)returnhead;}voidvisit(Node*head)//输出多项式(Node*p=head->next;while(p){printf("%dXA%d+",p->xi,p->zi);p=p->ncxt;printf("NULL\n\n");Node*Add(Node*head1.Node*head2)〃多项式相力口{Node*p,*head,*pl,*p2;intsum;head=(Node*)malloc(sizeof(Node));p=head;pl=head1->next;p2=head2->next;whilc(pl&&p2)〃当两多项式都存在时(if(p1->zi==p2->zi)〃假如指数相等{sum=pl->xi+p2->xi;if(sum){pl->xi=sum;p->next=pl;P=pl；)pl=p1->next;p2=p2->next;)else〃指数不相等分两种情况p->next=p1；P二Pl；pl=p1->next;}

else

(p->next=p2;P=P2；p2=p2->next：})}if(pl)p->next=p1；//将1中剩余结点接到和链表中由于最终只剩下一段链表多项式eIsep->next=p2;〃将2中剩余结点接到和链表中这段链的链头接到目的链表就可以了returnhead;)intmain()(prinlf("请输入第一个多项式\n");Nodc*head,*p1,*p2;p1=Creat();printf("多项式为：\n”)；Visit(p1);printf("请输入第二个多项式\n”);p2=Crcat();printf("多项式为:\n");visit(p2);head=Add(pl,p2);printf("\n多项式相加后得:\n");visit(head)；return0;六、测试和结果（给出测试用例，并给出测试结果）1.请按要求输入数据在第1个表中插入数据，输入“N”再对下个表插入数据8476N在第2个表中插入数据，输入“N”结束。17528N有序表如下：第一个有序表为：4678第二个有序表为：2578归并后有序表为：124567788请输入将要插入的e：3对归并后有序表插入e后得请输入第一个多项式请输入多项式的序数与指数（注意：按照指数升序输入，系数不能等于0且指数不能小于0,序数与指数用空格隔开，并以00结束输入）25500多项式为：2X"2+5X"5+NULL请输入第二个多项式请输入多项式的序数与指数（注意：按照指数升序输入，系数不能等于0且指数不能小于0,序数与指数用空格隔开，并以00结束输入）33447500多项式为:3X"3+4X"4+7X"5+NULL多项式相加后得：2X-2+3X-3+4X-4+12X"5+NULL七、用户手册（告诉用户如何使用程序，使用注意事项等）.按照规定输入输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式得和四、具体设计（画出程序流程图）32.五、程序代码(给出必要注释)#inc1ude<stdio.h>#inc1ude<mal1oc.h>typedefs(ructLNode(intdate;structLNode*nexl;}LNode,火Link；typedefstructLinkList(Linkhead;//头结点int1enth;〃链表中数据元素的个数}LinkList;intcompare(LinkList*L,inte)〃有序鉴定函数compare(ntLc=0;Linkp;p=L->head;p=p—>next；whiic(p!=NULL)if(e>p->date)p=p->next;Lc++;)elsereturnLc;}reiurnLc;IvoidOrderlnsert(LinkList*L,inte,int(*compare)())//根据有序鉴定函数compare,在有序表L的适当位置插入元素e;{Linktemp,p,q;intLc,i;temp=(Link)malloc(sizeof(LNode))；temp->date=e;p=q=L->head;P=p->next;Lc=(*compare)(L,e)；if(Lc==L->lenth)(whi1c(q->ncxt!=NULL)q=q->ncxt；q->next=temp;temp->next=NULL:}else(for(i=0;i<Lc;i++)(p=p->next；q=q->next;)q->next=temp;temp->next=p;)++L->lcnth；)voidOrderMerge(LinkList*La,LinkList*Lb,inl(*compare)())//根据有序鉴定函数ompare,将两个有序表La和Lb归并为一个有序表{inti,Lc=0;Linktemp,p,q;q=La->head—>next;whi1c(q!=NULL)(p=Lb—>hcad;temp=(Link)ma11oc(sizeof(LNode))；temp->date=q->date;Lc=(*compare)(Lb,q->date);if(Lc==Lb->lenth){while(p—>next!=NULL)(p=p->next;}p->next=temp；temp—>next=NULL；Ielse(for(i=0;i<Lc;i++)(p=p->next;)temp->next=p->next;p->next=temp;)q=q->next;++Lb->lenth；LinkList*Initialize(LinkList*NewList)inti；Linktemp;NewList=(LinkList*)malloc((2+l)*sizeof(LinkList));for(i=0；i<2+l;i++){temp=(Link)mal1oc(sizeof(LNode))；temp->date=O；temp->next=NULL;(NewList+i)->head=temp;(NewList+i)—>1enth=O;)retumNewList;IvoidInsert(LinkList*NewList){inta,i;charc；printf("在第1个表中插入数据，输入“N”再对下个表插入数据\n");for(i=0;i<2;i++)(whilc(1)(scanf("%d",&a);c=getchar();if(c=='N')if(i<2-2)prinlf("在第％d个表中插入数据，输入"N"再对下个表插入数据