实验一：设线性表L1和L2分别代表集合A和B，试设计算法求A 和B的并集C，并用线性表L3代表集合C。
实验二：设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减。
1.实验目的：掌握线性表的链式存储结构设计与基本操作的实现。
2.实验内容与要求：⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；3.数据结构设计实验一：逻辑结构：线性结构存储结构：链式存储结构实验二：逻辑结构：线性结构存储结构：链式存储结构4.算法设计实验一#include<stdio.h>#include<stdlib.h>typedef int datatype;typedef struct node{datatype data; //结点值struct node *next; //存储下一个结点的地址}LinkList;LinkList *CREATLISTF(LinkList *L,int n) {int num,i;LinkList *head,*s,*r;head=L;r=head;head->next=NULL;printf("请输入集合中的元素(由小到大)：\n");for(i=0;i<n;i++){scanf("%d",&num);s=(LinkList*)malloc(sizeof(LinkList));s->data=num;r->next=s; //链接到表中r=s; //r指向新的尾结点}r->next=NULL;return head;}LinkList *merge(LinkList *L1,LinkList *L2){LinkList *L3,*pa,*pb1,*pb2,*pc;L3=(LinkList*)malloc(sizeof(LinkL ist));//申请结点L3->next=NULL; //初始化链表L3pa=L1->next; //pa是链表L1的工作指针,指向第一个结点pb1=pb2=L2->next; //pb1是链表L2的工作指针,指向第一个结点pc=L3; //pc是链表L3的工作指针,指向头结点while(pa && pb1) //L1和L2均非空if(pa->data<pb1->data){//L1中元素插入L3pc->next=pa; pc=pa; pa=pa->next;}else if(pa->data>pb1->data){//L2中元素插入L3pc->next=pb1; pc=pb1; pb1=pb1->next;}else{pc->next=pa;pc=pa;pa=pa->next; pb1=pb2=pb1->next;}if(pa) pc->next=pa; //若pa未到尾，将pc指向paelse pc->next=pb1; //若pb1未到尾，将pc指向pb1return(L3);}void display(LinkList *L){LinkList *head;head=L->next;do{printf("%d\t",head->data);head=head->next;}while(head!=NULL);}void main(){int an,bn;LinkList *L1,*L2,*L3;L1=(LinkList*)malloc(sizeof(LinkL ist));L2=(LinkList*)malloc(sizeof(LinkL ist));printf("\n请输入集合A中元素的个数：\n");scanf("%d",&an);*L1=*CREATLISTF(L1,an);printf("集合A的元素为：\n");display(L1);printf("\n请输入集合B中元素的个数：\n");scanf("%d",&bn);*L2=*CREATLISTF(L2,bn);printf("集合B的元素为：\n");display(L2);L3=merge(L1,L2);printf("交集为：\n");display(L3);}实验二typedef struct node{ int coef;int exp;struct node *next;}polynode;polynode *Creat1polynode();polynode *Creat2polynode();polynode *subpolynode(polynode *ha,polynode *hb);polynode *addpolynode(polynode *ha,polynode *hb);#include<stdlib.h>#include<stdio.h>int main(){ polynode *ha,*hb,*hc,*hd,*p;ha=Creat1polynode();p=ha->next;printf("输出多项式A:");if(p->exp==0)printf("%d",p->coef);elseprintf("%dx^%d",p->coef,p->exp); p=p->next;while(p!=NULL){ if(p->coef>0){ printf("+");printf("%dx^%d",p->coef,p->exp);}elseprintf("%dx^%d",p->coef,p->exp);p=p->next;}printf("\n");hb=Creat2polynode();p=hb->next;printf("输出多项式B:");if(p->exp==0)printf("%d",p->coef);else printf("%dx^%d",p->coef,p->exp); p=p->next;while(p!=NULL){ if(p->coef>0){ printf("+");printf("%dx^%d",p->coef,p->exp);}elseprintf("%dx^%d",p->coef,p->exp);p=p->next;}printf("\n");hc=subpolynode(ha,hb);p=hc->next;printf("输出差多项式:");if(p->exp==0)printf("%d",p->coef);elseprintf("%dx^%d",p->coef,p->exp); p=p->next;while(p!=NULL){ if(p->coef>0){ printf("+");printf("%dx^%d",p->coef,p->exp);}elseprintf("%dx^%d",p->coef,p->exp);p=p->next;}printf("\n");hd=addpolynode(ha,hb);p=hd->next;printf("输出和多项式:");if(p->exp==0)printf("%d",p->coef);elseprintf("%dx^%d",p->coef,p->exp);p=p->next;while(p!=NULL){ if(p->coef>0){ printf("+");printf("%dx^%d",p->coef,p->exp);}elseprintf("%dx^%d",p->coef,p->exp);p=p->next;}printf("\n");}polynode *Creat1polynode(){ polynode *s,*r,*ha;int m,n;ha=(polynode*)malloc(sizeof(polynode));r=ha;printf("请输入系数m和指数n: ");scanf("%d,%d",&m,&n);while(m!=0){ s=(polynode *)malloc(sizeof(polynode));s->coef=m;s->exp=n;r->next=s;r=s;printf("请输入系数m和指数n: ");scanf("%d,%d",&m,&n);}r->next=NULL;return(ha);}polynode *Creat2polynode(){ polynode *s,*r,*hb;int m,n;hb=(polynode*)malloc(sizeof(polynode));r=hb;printf("请输入系数m和指数n: "); scanf("%d,%d",&m,&n);while(m!=0) { s=(polynode *)malloc(sizeof(polynode));s->coef=m;s->exp=n;r->next=s;r=s;printf("请输入系数m和指数n: ");scanf("%d,%d",&m,&n);}r->next=NULL;return(hb);}polynode *subpolynode(polynode *ha,polynode *hb){ polynode *hc,*p,*q,*s,*r;int sum;p=ha->next;q=hb->next;hc=(polynode*)malloc(sizeof(polynode));r=hc;while(p!=NULL&&q!=NULL){ if(p->exp==q->exp){ sum=p->coef-q->coef;if(sum!=0){ s=(polynode *)malloc(sizeof(polynode));s->coef=sum;s->exp=p->exp;r->next=s;r=s;}p=p->next;q=q->next;}else{ if(p->exp<q->exp){ s=(polynode *)malloc(sizeof(polynode));s->coef=p->coef;s->exp=p->exp;r->next=s;r=s;p=p->next;}else{ s=(polynode *)malloc(sizeof(polynode));s->coef=0-q->coef;s->exp=q->exp;r->next=s;r=s;q=q->next;}}}while(p!=NULL){ s=(polynode *)malloc(sizeof(polynode));s->coef=p->coef;s->exp=p->exp;r->next=s;r=s;p=p->next;}while(q!=NULL){ s=(polynode *)malloc(sizeof(polynode));s->coef=0-q->coef;s->exp=q->exp;r->next=s;r=s;q=q->next;}r->next=NULL;return(hc);}polynode *addpolynode(polynode *ha,polynode *hb){ polynode *p,*q,*pre,*r;int sum;p=ha->next;q=hb->next;pre=ha;while(p!=NULL&&q!=NULL){ if(p->exp<q->exp){ pre->next=p;pre=pre->next;p=p->next;}else if(p->exp==q->exp) { sum=p->coef+q->coef;if(sum!=0){ p->coef=sum;pre->next=p;pre=pre->next;p=p->next;r=q;q=q->next;free(r);}else{ r=p->next;free(p);p=r;r=q->next;free(q);q=r;}}else{ pre->next=q;pre=pre->next;q=q->next;}}while(p!=NULL){ pre->next=p;pre=pre->next;p=p->next;}while(q!=NULL){ pre->next=q;pre=pre->next;q=q->next;}pre->next=NULL;return(ha);}5.测试结果实验一实验二。
