线性表的链式存储结构实验报告.docx

线性表的链式存储结构实验报告

第一篇：线性表的链式存储结构实验报告实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：2015.01.30班级：数媒1401姓名：范业嘉学号1030514108一、实验目的掌握线性表的链式存储结构设计与基本操作的实现。二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。三、数据结构设计1.按所用指针的类型、个数、方法等的不同，又可分为：线性链表（单链表）静态链表循环链表双向链表双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。四、算法设计1.定义一个链表voidcreatlist(Linklist&L,intn){inti;Linklistp,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;is=(Linklist)malloc(sizeof(Lnode));scanf(“%d”,&s->data);s->next=NULL;p->next=s;p=s;/8}}2.（1）两个链表的合并voidMergelist(Linklist&La,Linklist&Lb,Linklist&Lc){Linklistpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}（2）两个链表的并集Linklistunionlist(Linklist&La,Linklist&Lb){Linklistp1,p2,head,q,s;intflag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;/8}q->next=Lb->next;returnhead;}3.（1）一元多项式的加法Listaddpoly(Listpa,Listpb)//一元多项式的加法{intn;Listpc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(structLinklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(structLinklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}elseif(pa->expnexpn){s=(List)malloc(sizeof(structLinklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}else{n=pa->coef+pb->coef;if(n!=0){s=(List)malloc(sizeof(structLinklist));s->expn=pa->expn;/8s->coef=n;s->next=NULL;p->next=s;p=s;}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(sizeof(structLinklist));s->expn=pa->expn;s->coef=pa->coef