合肥工业大学数据结构试验一实验报告

计算机与信息学院数据结构实验报告专业班级学生姓名及学号课程教学班号任课教师实验指导教师实验地点2015~2016学年第2学期说明实验报告是关于实验教学内容、过程及效果的记录和总结，因此，应注意以下事项和要求：1．每个实验单元在4页的篇幅内完成一份报告。“实验单元”指按照实验指导书规定的实验内容。若篇幅不够，可另附纸。2、各实验的预习部分的内容是进入实验室做实验的必要条件，请按要求做好预习。3．实验报告要求：书写工整规范，语言表达清楚，数据和程序真实。理论联系实际，认真分析实验中出现的问题与现象，总结经验。4．参加实验的每位同学应独立完成实验报告的撰写，其中程序或相关的设计图纸也可以采用打印等方式粘贴到报告中。严禁抄袭或拷贝，否则，一经查实，按作弊论取，并取消理论课考试资格。5．实验报告作为评定实验成绩的依据。实验序号及名称：实验一单链表实验实验时间∶2016年5月预习内容一、实验目的和要求∶（1）理解线性表的链式存储结构。（2）熟练掌握动态链表结构及有关算法的设计。（3）根据具体问题的需要，设计出合理的表示数据的链表结构，设计相关算法。二、实验任务∶说明1：本次实验中的链表结构均为带头结点的单链表。说明2：为使实验程序简洁直观，下面的部分实验程序中将所需要的函数以调用库函数的形式给出，并假设将库函数放在程序文件“linklist.h”中，同时假设该库函数文件中定义了链表结构中的指针类型为link，结点类型为node，并定义了部分常用运算。例如构建链表、以某种方式显示链表、从文件中读入一个链表、跟踪访问链表结点等。各运算的名称较为直观，并有相应的注释，因而易于理解和实现。三、实验准备方案，包括以下内容：（硬件类实验：实验原理、实验线路、设计方案等）（软件类实验：所采用的核心方法、框架或流程图及程序清单）实验准备方案：构建库函数：定义了链表结构中的指针类型为link，结点类型为node，并定义了部分常用运算，如构建链表，显示链表，读取链表，访问链表等；流程：略实验内容一、实验用仪器、设备：个人计算机C-free5.0二、实验内容与步骤（过程及数据记录）：1求链表中第i个结点的指针（函数），若不存在，则返回NULL。实验测试数据基本要求：第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2第二组数据：链表长度n=0，i分别为0，2node*list::address(inti){node*p=head-next;intn=1;while(n!=i&&p!=NULL){p=p-next;n++;}if(p!=NULL)returnp;elsereturnNULL;}第一组数据第二组数据2在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数据：链表长度n≥10，x=100,i分别为5,n,n+1,0,1,n+2第二组数据：链表长度n=0，x=100，i=5errorcodelist::insert(constinti,constintx){node*p;p=head;intn=1;while(n!=i&&p!=NULL){p=p-next;n++;}if(i1||ilength()+1)returnrangeerror;node*s=newnode;s-data=x;s-next=p-next;p-next=s;count++;returnsuccess;}3删除链表中第i个元素结点。实验测试数据基本要求：第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0第二组数据：链表长度n=0，i=5errorcodelist::delete_ele(constinti){node*p;p=head;intn=1;while(n!=i&&p!=NULL){p=p-next;n++;}if(i1||icount)returnrangeerror;node*u;u=p-next;p-next=u-next;count--;deleteu;returnsuccess;}4在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：链表元素为（10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8errorcodelist::orderinsert(intx){node*p=head;intn=1;while(p-next!=NULL){if(p-next-datax)p=p-next;elsebreak;}node*u=newnode;u-data=x;u-next=p-next;p-next=u;count++;returnsuccess;}5将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：第一组数据：链表元素为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：链表元素为（10,20,30,40,50,60,70,80,90,100）voidseparate(list&A,list&B,list&C){node*LA;node*LB;node*p;node*q;node*u;node*s;LA=A.get_head();LB=B.get_head();q=LA;p=LA-next;s=LB;if(p-data%2==0){u=p;p=p-next;q-next=p;s-next=u;s=s-next;}else{p=p-next;q=q-next;}}6求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据基本要求：第一组第一个链表元素为（1，3，6，10，15，16，17，18，19，20）第二个链表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）第二组第一个链表元素为（1，3，6，10，15，16，17，18，19，20）第二个链表元素为（2，4，5，7，8，9，12，22）第三组第一个链表元素为（）第二个链表元素为（1，2，3，4，5，6，7，8，9，10）bingji(listA,listB,list&C){node*LA;node*LB;node*LC;node*a;node*b;LC=C.get_head();LA=A.get_head();LB=B.get_head();a=LA-next;b=LB-next;while(a!=NULL&&b!=NULL){if(a-datab-data)a=a-next;elseif(a-datab-data)b=b-next;else{node*c=newnode;c-data=a-data;LC-next=c;LC=c;C.count++;a=a-next;b=b-next;}LC-next=NULL;}CPP文件附加：数据结构试验一.cpp#includeiostream.h#includemath.henumerror_code{success,arrange_error};typedefstructnode{intdata;node*next;}node;classlist{public:list();intlength()const;~list(){};node*get_element(intlocate)const;node*locate(constintx)const;error_codecharu(constinti);error_codeinsert(constintlocate,constinti);error_codedelete_element(constinti);node*get_head(){returnhead;}voidseparate(list&A,list&B);intbingji(listA,listB,list&C);voidcreate_R();voidlist::show();private:intcount;node*head;node*rear;};list::list(){head=newnode;head-next=NULL;count=0;}intlist::length()const{node*p=head-next;intcount=0;while(p!=NULL){count++;p=p-next;}returncount;}voidlist::create_R(){intx;cout请输入链表中的数值，按-1后结束创建endl;cinx;node*rear=head;while(x!=-1){count++;node*s=newnode;s-data=x;rear-next=s;rear=s;rear-next=NULL;cinx;}}node*list::get_element(intlocate)const{if(count==0)return0;else{if(locate=0||locate=count)return0;else{node*p=head;intk=0;while(p!=NULL&&klocate){p=p-next;k++;}returnp;}}}voidlist::show(){node*p=head;while(p!=NULL){coutp-data\t;p=p-next;}}error_codelist::insert(constintlocate,constinti){if(count==0){node*s=newnode;s-data=i;s-next=NULL;head-next=s;rear=s;count=1;returnsuccess;}else{if(locate1||locatecount+1)returnarrange_error;else{node*p=head;intj=0;while(j!=locate-1&&p!=NULL){p=p-next;j++;}node*s=newnode;s-data=i;s-next=p-next;p-next=s;count++;returnsuccess;}}}error_codelist::charu(constinti){node*p=head;while(p!=NULL&&p-next!=NULL){if(p-data=i&&i=p-next-data){node*s=newnode;s-data=i;s-next=p-next;p-next=s;count++;}elsep=p-next;}if(p-next==NULL){node*s=newnode;s-data=i;s-next=NULL;p-next=s;count++;}returnsuccess;}error_codelist::delete_element(constinti){node*p=head;intj=0;while(j!=i-1&&p!=NULL){p=p-next;j++;}if(i1||icount)returnarrange_error;node*u=newnode;u=p-next;p-next=u-next;deleteu;count--;returnsuccess;}voidseparate(list&A,list&B){node*LA;node*LB;node*p;node*q;node*u;node*s;LA=A.get_head();LB=B.get_head();q=LA;p=LA-next;s=LB;while(p!=NULL){if(p-data%2==0){u=p;p=p-nex