实验报告-线性表基本操作

PAGEPAGE1计算机学院实验报告专用纸实验室：网络实验室机号：网20实验日期：2008年3月21日姓名XXX班级课程名称数据结构任课教师实验项目名称线性表基本操作指导教师实验组别X同组者无教师评语及成绩：实验成绩：教师签字：（请按照实验报告的有关要求书写。一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题与解决方法；6、实验结果、结果分析与体会等内容）1、实验目的（1）掌握使用C或C++上机调试程序的基本方法；（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。2、实验内容建立一个数据域定义为整型的单链表，根据输入的整数，进行插入、删除、取数据元素等操作。3、实验步骤和方法（1）认真阅读和掌握和本实验相关的教材内容；（2）认真阅读和掌握本章相关内容的程序，分析、理解给出的示例程序；（3）上机调试程序，并设计输入数据运行程序；（4）保存和打印出程序的运行结果，并结合程序进行分析；（5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。4、实验数据与程序清单计算机学院实验报告附页姓名XXX班级实验名称线性表基本操作和简单程序1）头文件模块#includeiostream.h>//头文件#include<malloc.h>//库头文件动态分配内存空间typedefintelemtype;//定义数据域的类型typedefstructlinknode//定义结点类型{elemtypedata;//定义数据域structlinknode*next;//定义结点指针}nodetype;2）创建单链表nodetype*create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束{elemtyped;//定义数据元素dnodetype*h=NULL,*s,*t;//定义结点指针inti=1;cout<<"建立一个单链表"<<endl;while(1){cout<<"输入第"<<i<<"结点data域值：";cin>>d;if(d==0)break;//以0表示输入结束if(i==1)//建立第一个结点{h=(nodetype*)malloc(sizeof(nodetype));//表示指针hh->data=d;h->next=NULL;t=h;//h是头指针}else//建立其余结点{s=(nodetype*)malloc(sizeof(nodetype));s->data=d;s->next=NULL;t->next=s;t=s;//t始终指向生成的单链表的最后一个节点}i++;}returnh;}3）输出单链表中的元素voiddisp(nodetype*h)//输出由h指向的单链表的所有data域之值{nodetype*p=h;计算机学院实验报告附页姓名XXX班级实验名称线性表基本操作和简单程序cout<<"输出一个单链表:"<<endl<<"";if(p==NULL)cout<<"空表";while(p!=NULL){cout<<p->data<<"";p=p->next;}cout<<endl;}4）计算单链表的长度intlen(nodetype*h)//返回单链表的长度{inti=0;nodetype*p=h;while(p!=NULL){p=p->next;i++;}returni;}5）寻找第i个节点nodetype*find(nodetype*h,inti)//返回第i个节点的指针{nodetype*p=h;intj=1;if(i>len(h)||i<=0)returnNULL;//i上溢或下溢celse{while(p!=NULL&&j<1)//查找第i个节点，并由p指向该节点{j++;p=p->next;}returnp;}}6）单链表的插入操作nodetype*ins(nodetype*h,inti,elemtypex)//在单链表head中第i个节点//（i>=0）之后插入一个data域为x的节点{nodetype*p,*s;s=(nodetype*)malloc(sizeof(nodetype));//创建节点s计算机学院实验报告附页姓名XXX班级实验名称线性表基本操作和简单程序s->data=x;s->next=NULL;if(i==0)//i=0:s作为该单链表的第一个节点{s->next=h;h=s;}else{p=find(h,i);//查找第i个节点，并由p指向该节点if(p!=NULL){s->next=p->next;p->next=s;}returnh;}}7）单链表的删除操作nodetype*del(nodetype*h,inti)//删除第i个节点{nodetype*p=h,*s;intj=1;if(i==1)//删除第1个节点{h=h->next;free(p);}else{p=find(h,i-1);//查找第i-1个节点，并由p指向该节点if(p!=NULL&&p->next!=NULL){s=p->next;//s指向要删除的节点p->next=s->next;free(s);}elsecout<<"输入i的值不正确"<<endl;}returnh;}8）释放节点空间voiddispose(nodetype*h)//释放单链表的所有节点占用的空间{nodetype*pa=h,*pb;计算机学院实验报告附页姓名XXX班级实验名称线性表基本操作和简单程序if(pa!=NULL){pb=pa->next;if(pb==NULL)//只有一个节点的情况free(pa);else{while(pb!=NULL)//有两个及以上节点的情况{free(pa);pa=pb;pb=pb->next;}free(pa);}}}9)主程序模块:#include"slink.h"//包含头文件slinkvoidmain(){nodetype*head;//定义节点指针变量head=create();//创建一个单链表disp(head);//输出单链表cout<<"单链表长度:"<<len(head)<<endl;ins(head,2,0);//在第二个节点之后插入以0为元素的节点disp(head);//输出新链表del(head,2);//删除第二个节点disp(head);//输出新链表}5、实验结果建立一个单链表：输入第1结点data域值：1输入第2结点data域值：2输入第3结点data域值：3输入第4结点data域值：4输入第5结点data域值：5输入第6结点data域值：6输入第7结点data域值：7输入第8结点data域值：8输入第9结点data域值：9输入第10结点data域值0：输出一个单链表：计算机学院