《数据结构》实验报告（单链表实验、二叉树实验、排序实验）.docx

实验一单链表实验实验目的理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。根据具体问题的需要,设计出合理的表示数据的链表结构,并设计相关算法。实验任务编写算法实现下列问题的求解求链表中第i个结点的指针(函数),若不存在,则返回NULL。在第i个结点前插入值为x的结点。删除链表中第i个元素结点。在一个递增有序的链表L中插入一个值为x的元素,并保持其递增有序特性。将单链表L中的奇数项和偶数项结点分解开,并分别连成一个带头结点的单链表,然后再将这两个新链表同时输出在屏幕上,并保留原链表的显示结果,以便对照求解结果。求两个递增有序链表L1和L2中的公共元素,并以同样方式连接成链表L3。主要仪器设备PC机,Windows操作平台,VisualC++实验分析顺序表操作:定义一个顺序表类,该类包括顺序表的存储空间、存储容量和长度,以及构造、插入、删除、遍历等操作的方法源程序头文件文件名:#include<iostream>usingnamespacestd;structnode{intdata;node*next;};classlist{public:list();intlength()const{returncount;//求链表长度} ~list();voidcreate(); //链表构建,以0为结束标志voidoutput(); //链表输出intget_element(constinti)const; //按序号取元素node*locate(constintx)const; //搜索对应元素intinsert(constinti,constintx); //插入对应元素intdelete_element(constinti); //删除对应元素node*get_head(){returnhead;//读取头指针}voidinsert2(constintx);friendvoidSplitList(listL1,list&L2,list&L3);friendvoidget_public(listL1,listL2,list&L3);private:intcount;node*head;};list::list(){head=newnode;head->next=NULL;count=0;}voidlist::create()//链表构建,以0为结束标志{intx;cout<<"请输入当前链表,以0为结束符。\n";cin>>x;node*rear=head;while(x!=0){count++;node*s=newnode;s->data=x;rear->next=s;rear=s;rear->next=NULL;cin>>x;}}voidlist::output(){node*p=head->next;cout<<"******Topofthislist******"<<endl;while(p!=NULL){cout<<p->data<<"";p=p->next;}cout<<endl<<"******Endofthislist******"<<endl;}intlist::get_element(constinti)const//实验1{intx,j;node*p;p=head->next;j=1;while(p!=NULL&&j!=i){p=p->next;j++;}if(p==NULL)return0;else{returnx=p->data;return1;}}node*list::locate(constintx)const{node*p=head->next;while(p!=NULL)if(p->data==x)returnp;elsep=p->next;returnNULL;}intlist::insert(constinti,constintx)//实验2{node*p=head;intj=0;while(j!=i-1&&p!=NULL){p=p->next;j++;}if(i<1||i>count+1)return0;node*s=newnode;s->data=x;s->next=p->next;p->next=s;count++;return1;}intlist::delete_element(constinti)//实验3{node*p=head;intj=0;while(j!=i-1&&p!=NULL){p=p->next;j++;}if(i<1||i>count)return0;node*u=p->next;p->next=u->next;deleteu;count--;return1;}voidlist::insert2(constintx)//实验4{node