《数据结构》实验三报告13网二吴睿

江西师范大学计算机信息工程学院学生实验报告专业_网络工程2班姓名_吴睿_学号1308093095日期__2014.10.30课程名称数据结构实验室名称X4313c实验名称带头结点的单链表指导教师左正康成绩实验目的理解带头结点的单链表的特点，掌握采用这种数据结构的算法设计熟练掌握运用带头结点链表表示特定形式的数据的方法，并设计出有关算法实验原理和内容基于slnklist.h文件中定义的单链表表，完成实验1~9。实验：编写函数voiddelx(linklisthead,datatypex)，删除带头结点单链表head中第一个值为x的结点。假设线性表（a1,a2,a3,…an）采用带头结点的单链表存储，请设计算法函数linklistreverse(linklisthead)，将带头结点的单链表head就地倒置，使表变成（an,an-1,…a3.a2,a1）。假设带头结点的单链表head是升序排列的，设计算法函数linklistinsert(linklisthead,datatypex)，将值为x的结点插入到链表head中，并保持链表有序性。编写算法函数linklistdelallx(linklisthead,intx)，删除带头结点单链表head中所有值为x的结点。已知线性表存储在带头结点的单链表head中，请设计算法函数voidsort(linklisthead)，将已知两个带头结点的单链表L1和L2中的结点值均已按升序排序，设计算法函数linklistmergeAscend(linklistL1,linklistL2)将L1和L2合并成一个升序的带头结单链表作为函数的返回结果；设计算法函数linklistmergeDescend(linklistL1,linklistL2)将L1和L2合并成一个降序的带头结单链表作为函数的返回结果head中的结点按结点值升序排列。设计一个算法linklistinterSection(linklistL1,linklistL2)，求两个单链表表示的集合L1和L2的交集，并将结果用一个新的带头结点的单链表保存并返回表头地址。请编写一个算法函数voidpartion(linklisthead)，将带头结点的单链表head中的所有值为奇数的结点调整到链表的前面，所有值为偶数的结点调整到链表的后面。编写一个程序，用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址，如果不存在，则返回NULL。实验步骤在visualC++6.0中进行编程，调试，完成实验。程序及运行结果（或实验数据记录及分析）实验1：linklistdelx(linklisthead,datatypex){ linklistp=head->next,pre=head,q; inti=0; while(p!=NULL&&i==0){ if(p->info==x){ q=p; p=p->next; pre->next=p; free(q); i=1; }else{ pre=p; p=p->next; i=0; } }returnhead;}实验2linklistreverse(linklisthead){ linklistp,q; p=head->next; head->next=NULL; while(p!=NULL){ q=p->next; p->next=head->next; head->next=p; p=q; } returnhead;}实验3linklistinsert(linklisthead,datatypex){ linklistp,q; q=head; p=(linklist)malloc(sizeof(node)); p->info=x; while(q->next->info<x&&q->next!=NULL){ q=q->next; } p->next=q->next; q->next=p; returnhead;}：实验4linklistdelallx(linklisthead,intx){linklistp=head->next,pre=head,q; while(p!=NULL){ if(p->info==x){ q=p; p=p->next; pre->next=p; free(q); }else{ pre=p; p=p->next; } }returnhead;}实验5voidsort(linklisthead)//插入法排序{ linklistp,q,qpre,pnext; p=head->next; head->next=NULL; while(p!=NULL){ qpre=head; q=head->next; while(q!=NULL&&q->info<=p->info){ qpre=q; q=q->next; } pnext=p->next; p->next=qpre->next; qpre->next=p; p=pnext; }}实验6linklistmergeAscend(linklistL1,linklistL2){linklisthead,tmp=NULL;linklisthead1=L1,head2=L2;head=(linklist)malloc(sizeof(node)); head->next=NULL;if(L1->next->info>L2->next->info)//哪个链表第一个节点值小，则把它的头指针作为合并后的头指针{head1=L2;head2=L1;}head->next=head1->next;while(head2!=NULL){while((head1->next->info<head2->info)&&head1->next!=NULL){head1=head1->next;}tmp=head2;head2=head2->next;tmp->next=head1->next;head1->next=tmp;}returnhead;}实验7linklistinterSection(linklistL1,linklistL2){linklistp1,p2,p3,L3,r;L3=r=(linklist)malloc(sizeof(node));L3->next=NULL;p1=L1->next;while(p1!=NULL){p2=L2->next;while((p2!=NULL)&&(p2->info!=p1->info))p2=p2->next;if((p2!=NULL)&&(p2->info==p1->info)){p3=(linklist)malloc(sizeof(node)); //L3=L3->next;p3->info=p1->info;r->next=p3;r=p3; }p1=p1->next;}//print(L3); r->next=NULL; returnL3;}实验8voidpartion(linklisthead){ linklistp,s,pre; pre=head; p=head->next; while(p) { if(p->info%2==0) { pre=p; p=p->next; } else { s=p; pre->next=p->next; p=pre->next; s->next=NULL; s->next=head->next; head->next=s; } }}实验9linklistsearch(linklisthead,intk