计算机科学与技术系实验报告专业名称计算机科学与技术课程名称数据结构与算法项目名称单链表的基本操作班级学号姓名实验日期格式要求实验报告注意格式规范，要求在word中编写，文中不要有空行，统一使用A4页面。

页边距：上2.5cm、下2cm、左2.5cm、右2cm。

标题：宋体、四号字、加粗、1.5倍行距。

正文：宋体、小四号字、1.2倍行距。

一、实验目的与要求：（一）实验目的1．理解排序算法基本思想。

2．掌握在顺序表上各种排序算法的实现。

3．对线性表排序算法的时间复杂度进行分析。

4．理解顺序表数据结构的特点（优缺点）和适用环境。

（二）实验要求1．定义一链表类型，并定义带有头结点的单链表。

2．将教材中链表的建立、初始化、插入、删除等函数实现。

3．由主函数按照用户要求对各个链表操作访问。

4．每次操作之前要有明确的说明，操作后要输出操作结果。

5．分析顺序表链表的插入、删除、查找的时间和空间复杂度。

二、实验方法：（代码）#include<stdio.h>#include<malloc.h>typedef struct Pnode{int coef;int exp;struct Pnode*next;}Polynode;typedef struct node{int data;struct node*next;}LinkList;//多项式链表的生成Polynode*PLcreate(Polynode*H){Polynode*R,*S;int c,e;H=(Polynode*)malloc(sizeof(Polynode));H->exp=-1;H->next=NULL;//建立空多项式单链表R=H;//R始终指向单链表的尾，便于尾插法建表printf("请输入多项式的系数和指数：");scanf("%d%d",&c,&e);//键入多项式的系数和指数项while(e!=-1)//若e=-1，则掉膘多项式的输入结束{S=(Polynode*)malloc(sizeof(Polynode));S->coef=c;S->exp=e;S->next=NULL;//生成新结点并赋值R->next=S;//在当前表尾做插入R=S;//printf("请继续输入多项式的系数和指数：");scanf("%d%d",&c,&e);}return H;}//两个一元多项式相加Polynode*polyadd(Polynode*A,Polynode*B){Polynode*p,*q,*temp,*pre;int sum;p=A->next;q=B->next;//p和q分别指向A和B多项式来拿表中的第一个结点pre=A;//pre指向*p的前驱结点free(B);//释放多项式B的头结点空间while(p!=NULL&&q!=NULL)//当两个多项式均未扫描结束时{if(p->exp<q->exp)//若果P指向的多子昂是的指数小于q的指数，指针p后移{pre=p;p=p->next;}else if(p->exp==q->exp)//若指数相等，则相应的系数相加{sum=p->coef+q->coef;if(sum!=0){p->coef=sum;B=q;pre=p;p=p->next;q=q->next;free(B);}else{temp=p;p=p->next;pre->next=p;free(temp);B=q;q=q->next;free(B);}}else{B=q;q=q->next;B->next=p;pre->next=B;pre=pre->next;}}if(q!=NULL)pre->next=q;//return(A);print_Pn(A);}int print_Pn(Polynode*A)//输出链表{printf("您的链表为:");printf("%d",A->exp);while(A->next!=NULL){printf("%d%d",A->next->coef,A->next->exp);A=A->next;}printf("\n");}//头插法建单链表LinkList*CreatlistH(LinkList*L){LinkList*head,*S;int n;L=(LinkList*)malloc(sizeof(LinkList));head=L;L->next=NULL;scanf("%d",&n);while(n!=-1){S=(LinkList*)malloc(sizeof(LinkList));S->data=n;S->next=L->next;L->next=S;//ch=getchar();scanf("%d",&n);}return head;}//两个有序链表的归并算法LinkList*Lmerge(LinkList*A,LinkList*B){LinkList*p,*q,*pre;p=A->next;q=B->next;//p和q分别指向A和B多项式来拿表中的第一个结点pre=A;//pre指向*p的前驱结点free(B);//释放多项式B的头结点空间while(p!=NULL&&q!=NULL)//当两个多项式均未扫描结束时{if(p->data<q->data)//如果*p结点的data值小于*q的data值，指针p后移{pre=p;p=p->next;}else//否则，将*q结点插入到链表A中*p结点前{B=q;q=q->next;B->next=p;pre->next=B;pre=pre->next;}/*if(q->data>=p->data)//如果*p结点的data值小于*q的data值，指针p后移{B=q;q=q->next;B->next=p;pre->next=B;pre=pre->next;}else//否则，将*q结点插入到链表A中*p结点前{pre=p;p=p->next;}*/}if(q!=NULL)//若链表B中还有剩余，则将剩余的结点插入到链表A的表尾pre->next=q;//return(p);print_LS(A);}int print_LS(LinkList*A)//输出链表{printf("您的链表为:");//printf("%d",A->data);while(A->next!=NULL){printf("%d",A->next->data);A=A->next;}printf("\n");}void main(){LinkList*x,*y;LinkList A,B;//Polynode*x,*y;//Polynode A,B;printf("多项式相加算法:\n");printf("*********请输入第一个一元多项式**********\n");x=PLcreate(&A);printf("*********请输入第二个一元多项式**********\n");y=PLcreate(&B);polyadd(x,y);printf("\n\n\n\n");printf("两个链表的归并算法：\n");printf("请输入第一个有序表：");x=CreatlistH(&A);printf("请输入第二个有序表：");y=CreatlistH(&B);Lmerge(x,y);}}三、实验分析与小结得分（百分制）。