资源描述：
《数据结构实验报告4.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构实验报告——实验4学号：姓名：得分：______________一、实验目的1、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和（带头结点）单链表；3、了解有序表。二、实验内容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（1）OrderInsert(&L,e,int(*compare)(a,b))//根据有序判定函数compare，在有序表L的适当位置插入元素e；（2）OrderInput(&L,int(*compare)(a,b))//
2、根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；（3）OrderMerge(&La,&Lb,&Lc,int(*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。2、（必做题）请实现：（1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0；（2）两个升幂多项式的相加。三、算法描述（采用自然语言描述）1.创建带头节点的链表，输入两个有序表数据LaLb归并两个有序表
3、得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式得和四、详细设计（画出程序流程图）101.创建带头节点的链表输入两个有序表数据LaLb开始归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc结束2.创建链表按指数升序输入多项式得序数和指数开始输出多项式按指数升序输入第二个多项式得序数和指数两个多
4、项式相加输出第二个多项式和两个多项式的和结束10五、程序代码（给出必要注释）1.#include#includetypedefstructLNode{intdate;structLNode*next;}LNode,*Link;typedefstructLinkList{Linkhead;//头结点intlenth;//链表中数据元素的个数}LinkList;intcompare(LinkList*L,inte)//有序判定函数compare{intLc=0;
5、Linkp;p=L->head;p=p->next;while(p!=NULL){if(e>p->date){p=p->next;Lc++;}elsereturnLc;}returnLc;}voidOrderInsert(LinkList*L,inte,int(*compare)())//根据有序判定函数compare，在有序表L的适当位置插入元素e；{Linktemp,p,q;intLc,i;temp=(Link)malloc(sizeof(LNode));temp->date=e;p=q=L
6、->head;10p=p->next;Lc=(*compare)(L,e);if(Lc==L->lenth){while(q->next!=NULL){q=q->next;}q->next=temp;temp->next=NULL;}else{for(i=0;inext;q=q->next;}q->next=temp;temp->next=p;}++L->lenth;}voidOrderMerge(LinkList*La,LinkList*Lb,int(*compar
7、e)())//根据有序判定函数compare,将两个有序表La和Lb归并为一个有序表{inti,Lc=0;Linktemp,p,q;q=La->head->next;while(q!=NULL){p=Lb->head;temp=(Link)malloc(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;
8、temp->next=NULL;10}else{for(i=0;inext;}temp->next=p->next;p->next=temp;}q=q->next;++Lb->lenth;}}LinkList*Initialize(LinkList*NewList){inti;Linktemp;NewList=(LinkList*)malloc((2+1)*sizeof(LinkList));for(i=0;i<2+1;i++){temp=(Link)malloc(s
