数据结构实验报告(2)1

1、数据结构实验报告(2)数据结构实验报告实验4学号：姓名：得分：_一、实验目的1、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和（带头结点）单链表；3、了解有序表。二、实验内容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（1）orderinsert(&l, e, int (*compare)(a, b)/根据有序判定函数compare，在有序表l的适当位置插入元素e；（2）orderinput(&l, int (*compare)(a, b)/根据有序判定函数compare，并利用有序插入函数orderinsert，构造有序表l；（3）orde

2、rmerge(&la, &lb, &lc, int (*compare)()/根据有序判定函数compare，将两个有序表la和lb归并为一个有序表lc。2、（必做题）请实现：（1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0；（2）两个升幂多项式的相加。三、算法描述（采用自然语言描述）1.创建带头节点的链表，输入两个有序表数据la lb归并两个有序表得有序表lc输出三个有序表输入需插入数据e将e插入有序表lc输出插入e后的lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多

3、项式和两个多项式得和四、详细设计（画出程序流程图） 1. 2. 五、程序代码 （给出必要注释）1.#include#includetypedef struct lnodeint date;struct lnode *next; lnode,*link;typedef struct linklistlink head;/头结点int lenth;/链表中数据元素的个数 linklist;int compare (linklist *l,int e)/有序判定函数compareint lc=0;link p;p=l-head;p=p-next;while(p!=null)if(ep-date)p=

4、p-next;lc+;elsereturn lc;return lc;void orderinsert (linklist *l,int e,int (*compare)()/根据有序判定函数compare，在有序表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=(*compare)(l,e);if(lc=l-lenth)while(q-next!=null)q=q-next;q-next=temp;temp-next=null;els

5、efor(i=0; ip=p-next;q=q-next;q-next=temp;temp-next=p;+l-lenth;void ordermerge (linklist *la,linklist *lb,int (*compare)()/根据有序判定函数compare ,将两个有序表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=(*compare)(lb,q-date);if

6、(lc=lb-lenth)while(p-next!=null)p=p-next;p-next=temp;temp-next=null; elsefor(i=0; ip=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; itemp=(link)malloc(sizeof(lnode);temp-date=0;t

7、emp-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; iwhile(1)scanf(%d,&a);c=getchar();if(c=n) if(iprintf(在第%d个表中插入数据,输入“n ”再对下个表插入数据n,i+2); else if(i=2-2)printf(在第%d个表中插入数据,输入“n ”结束。n,i+2);b

8、reak;elseorderinsert(newlist+i),a,compare);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(归并后有序

9、表为: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; iordermerge (newlist+i,newlist+2,compare);visit(newlist,show);l=newlist;printf(n请输入将要插入的e:n);scanf(%d,&e);orderinsert(newlist+i),e,compare

10、);printf(对归并后有序表插入e后得n);show(newlist+2);return 0;2.#include#includetypedef struct nodeint 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结

11、束输入）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,*he

12、ad,*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-zizi) p-next=p1; p=p1;p1=p1-next;elsep-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(多项