大数据结构实验报告材料4.doc

word数据结构实验报告实验4学号： ： 得分：_一、实验目的1、复习线性表的逻辑结构、存储结构与根本操作；2、掌握顺序表和带头结点单链表；3、了解有序表。二、实验容1、必做题假设有序表中数据元素类型是整型，请采用顺序表或带头结点单链表实现：1OrderInsert(&L, e, int (*pare)(a, b)/根据有序判定函数pare，在有序表L的适当位置插入元素e；2OrderInput(&L, int (*pare)(a, b)/根据有序判定函数pare，并利用有序插入函数OrderInsert，构造有序表L；3 OrderMerge(&La, &Lb, &Lc, int (*pare)()/根据有序判定函数pare，将两个有序表La和Lb归并为一个有序表Lc。2、必做题请实现：1升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0；2两个升幂多项式的相加。三、算法描述采用自然语言描述1.创建带头节点的链表，输入两个有序表数据La Lb归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式得和四、详细设计画出程序流程图1.创建带头节点的链表输入两个有序表数据La Lb开始归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc完毕2.创建链表按指数升序输入多项式得序数和指数开始输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式的和完毕五、程序代码给出必要注释1.#include<stdio.h>#include<malloc.h>typedef struct LNode int date; struct LNode *next; LNode,*Link;typedef struct LinkList Link head;/头结点 int lenth;/链表中数据元素的个数 LinkList;int pare (LinkList *L,int e)/有序判定函数 pare int Lc=0; Link p; p=L->head; p=p->next; while(p!=NULL) if(e>p->date) p=p->next; Lc+; else return Lc; return Lc;void OrderInsert (LinkList *L,int e,int (*pare)()/根据有序判定函数pare，在有序表L的适当位置插入元素e； Link temp,p,q; int Lc,i; temp=(Link)malloc(sizeof(LNode); temp->date=e; p=q=L->head; p=p->next; Lc=(*pare)(L,e); if(Lc=L->lenth) while(q->next!=NULL) q=q->next; 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->lenth;void OrderMerge (LinkList *La,LinkList *Lb,int (*pare)()/根据有序判定函数 pare ,将两个有序表 La 和 Lb 归并为一个有序表 int i,Lc=0; Link temp,p,q; q=La->head->next; while(q!=NULL) p=Lb->head; temp=(Link)malloc(sizeof(LNode); temp->date=q->date; Lc=(*pare)(Lb,q->date); if(Lc=Lb->lenth) while(p->next!=NULL) p=p->next; p->next=temp; temp->next=NULL; else 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) int i; Link temp; NewList=(LinkList *)malloc(2+1)*sizeof(LinkList); for(i=0; i<2+1; i+) temp=(Link)malloc(sizeof(LNode); temp->date=0; temp->next=NULL; (NewList+i)->head=temp; (NewList+i)->lenth=0; return NewList;void Insert (LinkList *NewList) int a,i; char c; printf("在第1个表中插入数据,输入“ N 再对下个表插入数据 n"); for(i=0; i<2; i+) while(1) scanf("%d",&a); c=getchar(); if(c='N') if(i<2-2) printf("在第 %d个表中插入数据,输入 “ N 再对下个表插入数据 n",i+2); else if(i=2-2) printf("在第 %d个表中插入数据,输入“ N 完毕。 n",i+2); break; else OrderInsert(NewList+i),a,pare); void Show (LinkList *L)/输出有序表 Link p; p=L->head->next; while(p!=NULL) printf("%d ",p->date); p=p->next; void visit(LinkList *NewList,void (*Show)() printf("有序表如下:n"); printf("第一个有序表为:n"); (*Show)(NewList+0); printf("n"); printf("第二个有序表为:n"); (*Show)(NewList+1); printf("n"); printf("归并后有序表为:n"); (*Show)(NewList+2); printf("n");int main() LinkList *NewList=NULL; LinkList *L; int i, e; printf("请按要求输入数据n"); NewList=Initialize(NewList); Insert(NewList); for(i=0; i<2; i+) OrderMerge (NewList+i,NewList+2,pare); visit(NewList,Show); L=NewList; printf("n请输入将要插入的e:n"); scanf("%d",&e); OrderInsert(NewList+i),e,pare); printf("对归并后有序表插入e后得n"); Show(NewList+2); return 0;2.#include<stdio.h>#include<malloc.h>typedef struct node int xi; int zi; struct node *next; Node;Node *Creat()/用链表储存多项式的序数与指数 Node *head,*p,*q; int or,in; head=(Node *)malloc(sizeof(Node); head->next=NULL; q=head; printf("请输入多项式的序数与指数n注意：按照指数升序输入，系数不能等于0且指数不能小于0，序数与指数用空格隔开,并以0 0完毕输入n"); scanf("%d %d",&or,&in); while(or) p=(Node *)malloc(sizeof(Node); p->xi=or; p->zi=in; p->next=q->next; q->next=p; q=p; scanf("%d %d",&or,&in); return head;void visit(Node *head) /输出多项式 Node *p=head->next; while(p) printf("%dX%d+",p->xi,p->zi); p=p->next; printf("NULLnn");Node *Add(Node *head1,Node *head2)/多项式相加 Node *p,*head,*p1,*p2; int sum; head=(Node *)malloc(sizeof(Node); p=head; p1=head1->next; p2=head2->next; while(p1&&p2) /当两多项式都存在时 if(p1->zi=p2->zi) /如果指数相等 sum=p1->xi+p2->xi; if(sum) p1->xi=sum; p->next=p1; p=p1; p1=p1->next; p2=p2->next; else /指数不相等分两种情况 if(p1->zi<p2->zi) p->next=p1; p=p1; p1=p1->next; else p->next=p2; p=p2; p2=p2->next; if(p1) p->next=p1; /将1中剩余结点接到和链表中 因为最终只剩下一段链表多项式 else p->next=p2; /将2中剩余结点接到和链表中 这段链的链头接到目标链表就可以了 return head;int main() printf("请输入第一个多项式n"); Node *head,*p1,*p2; p1=Creat(); printf("多项式为:n"); visit(p1); printf("请输入第二个多项式n"); p2=Creat(); printf("多项式为:n"); visit(p2); head=Add(p1,p2); printf("n多项式相加后得：n"); visit(head); return 0;六、测试和结果给出测试用例，并给出测试结果1.2.七、用户手册告诉用户如何使用程序，使用须知事项等10 / 10