一、实验目的1、深入了解线性表的逻辑结构特性及其基本操作。
2、实现熟悉线性表链式存储结构定义及其基本操作的C语言。
3 .掌握单向链表、单向循环链表的应用，逐步培养解决实际问题的能力。
4、可以从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用情况。
二、实验内容1、一元稀疏多项式计算机
(1)将pn ) x )和QM ) x )分别作为2个一元稀疏多项式，利用单链表存储pn ) x )和QM ) x )。
)通过键盘输入一元多项式的信息，制成一元稀疏多项式pn(x )和QM (x )并输出。
)3)实现pn(x )和QM ) x )的加法运算，输出两者之和pn ) x ) QM ) x )。
)4)实现pn(x )和QM ) x )的减法运算，输出两者之和pn ) x ) QM ) x )。
)5)将两者之差pn(x )-QM (x )当场相反。
2、设计并验证了以下算法，如果起始节点的单向链表l的数据元素是非增加有序、非增加有序，则判断为是相同的册数删除值的多余元素，如果将删除的链表L:就地反向放置，不是非增加有序，则对应的提示
)1)根据键盘输入数据用尾塞法建立首节点单向链表l。
)2)输出起始节点的单向链表l、删除了相同多余要素的单向链表l、当场反向的单向链表l。
三.代码实现和结果第一题
代码：
# include stdio.h # include malloc.h # include stdlib.htypedefstructpolynomial { float coef； int expn； struct Polynomial *next； }*Polyn，Polynomial； //定义项表达式项voidinsert(polynp，Polyn h ) if ) p-coef==0) free(p ) p )； //系数0释放节点else { Polyn q1，q2； q1=h； q2=h-next； while(Q2P-ExpnQ2-Expn ) /查找插入位置) { q1=q2； q2=q2-next； (if ) Q2P-Expn==Q2-Expn ) /指数相同且相辅相成) { q2-coef=p-coef； free(p； if (！ Q2-Coef(Q1-next=Q2-next； free(Q2 )； } } else { p-next=q2； q1-next=p； }}polyncreatepolyn(polynhead，int m ) /创建指针head，项数m元项表达式(int m； Polyn p； p=head=(Polyn ) malloc ) sizeof ) structpolynomial )； 头- next=null； for(I=0； im； I () p=(Polyn ) malloc ) sizeof ) structpolynomial )； //请输入接收数据printf ('第%d项的系数和指数： '，i 1 )； scanf('%f%d )、p-coef和p-expn )； 插入(p，head )； //插入节点}返回头； }voiddestroyPolyn(Polynp ) /放弃项表达式p ) p{ Polyn q1，q2； q1=p-next； q2=q1-next； while(Q1-next ) ) free ) Q1； q1=q2； q2=q2-next； }voidprintpolyn(polynp ) { Polyn q=P-next； int flag=1； if (！ q//若项式空输0{putchar('0)； 打印((n )； 返回； (while ) q ) if ) q-coef 0标志！=1) putchar (' )； 国际机场！=1q-coef！=-1 ) printf('%g '，q-gt
;coef); if(q->expn==1) putchar('X'); else if(q->expn) printf("X^%d",q->expn); } else { if(q->coef==1) { if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf("X^%d",q->expn); } if(q->coef==-1) { if(!q->expn) printf("-1"); else if(q->expn==1) printf("-X"); else printf("-X^%d",q->expn); } } q=q->next; flag++; } printf("n");}int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn) return 1; else if(!a||a->expn<b->expn) return -1; else return 0; } else if(!a&&b) return -1; else return 1;}Polyn AddPolyn(Polyn pa,Polyn pb) //求解并建立项式a+b返其指针{ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial)); hc->next=NULL; headc=hc; while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc); //相加系数0释放该结点 } return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb) //求解并建立项式a-b返其指针{ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) { p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next; p; p=p->next) p->coef*=-1; return pd;}main(){ int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; printf("请输入a项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m); //建立项式a printf("请输入b项数:"); scanf("%d",&n); pb=CreatePolyn(pb,n); //建立项式b printf("n"); //输菜单 printf("1:输出项式a n"); printf("2:输出项式b n"); printf("3:输出a+b n"); printf("4:输出a-b n"); printf("5:退出程序 n"); while(1) { printf("n请选择操作："); scanf(" %c",&flag); switch(flag) { case'1': { printf("n 项式a="); PrintPolyn(pa); break; } case'2': { printf("n 项式b="); PrintPolyn(pb); break; } case'3': { pc=AddPolyn(pa,pb); printf("n a+b="); PrintPolyn(pc); break; } case'4': { pc=SubtractPolyn(pa,pb); printf("n a-b="); PrintPolyn(pc); break; } case'5': { printf("n感谢谢使用程序!n");exit(0); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; } default: printf("n您选择错误请重新选择!n"); } }}结果：
第二题
代码（思路）：