数据结构实验报告1链表及其反转

任课教师：孙树森《数据结构与算法》（2012-2013学年第2学期）实验报告学号：姓名：班级：

实验1：链表的建立与操作实验目的：掌握链表数据结构的建立及操作；实验重点：利用链表的原空间进行链表的反转；实验内容：设计一个将输入数据建立成链表、并依次输出链表数据、利用原空间把链表反转的程序。实验步骤：掌握链表的数据结构；建立空链表；用头插法向链表插入数据，实验数据:验证数据：20，20，17，16，15，15，11，10，8，7，7，5，4；依次输出链表中的数据；利用链表原空间进行对链表进行反转；依次输出反转后的链表数据，以判断反转操作的正确性，注意反转后，链表的第一个和最后一个元素是否正确；实验提示:实验1链表。PPT；7，进阶要求：完成P403.6.1的功能；程序源码：方法1：#include<iostream>#include<stdlib.h>usingnamespacestd;structLinkedList{ intdata; structLinkedList*next;};voidexam(LinkedList*la,intx){ LinkedList*l,*r,*q;r=la->next;l=la->next; q=r->next; while(!l->next==NULL){ l->next=q->next; la->next=q; q->next=r; r=q; q=l->next; } cout<<"反转后是："<<endl; for(intk=0;k<x;k++) { la=la->next; cout<<la->data<<""; }}intmain(){ LinkedList*p,*l; l=newLinkedList();intn; cout<<"输入长度:"; cin>>n; for(inti=0;i<n;i++) { p=newLinkedList(); p->data=rand()%100+1; p->next=l->next; l->next=p; } cout<<"列表为："<<endl; for(intj=0;j<n;j++){ cout<<p->data<<""; p=p->next; } cout<<endl; exam(l,n); cin>>n; return0; }方法2：#include<iostream>#include<stdlib.h>usingnamespacestd;structLinkedList{ intdata; structLinkedList*next;};voidexam(LinkedList*la,intx){ LinkedList*l,*p,*q,*pre; pre=la->next; p=pre; for(inti=1;i<x;i++){ p=p->next; } l=newLinkedList(); l=p; la->next=l; for(intn=x-1;n>0;n--){ p=pre; for(intm=1;m<n;m++){ p=p->next; } q=newLinkedList(); q=p; l=q->next; l->next=q; } cout<<"反转后是："<<endl; for(inti=0;i<x;i++) { la=la->next; cout<<la->data<<""; }}intmain(){ LinkedList*p,*l; l=newLinkedList();intn; cout<<"输入长度:"; cin>>n; for(inti=0;i<n;i++) { p=newLinkedList(); p->data=rand()%100+1; p->next=l->next; l->next=p; } cout<<"列表为："<<endl; for(intj=0;j<n;j++){ cout<<p->dat