数据结构单链表操作验证实验报告

班级：计算机11-2学号：40姓名：朱报龙成绩：_________实验三单链表操作验证一、实验目的⑴掌握线性表的链接存储结构；⑵验证单链表及其基本操作的实现；⑶进一步掌握数据结构及算法的程序实现的基本方法。二、实验内容⑴用头插法（或尾插法）建立带头结点的单链表；⑵对已建立的单链表实现插入、删除、查找等基本操作。三、设计与编码#includeiostreamusingnamespacestd;templateclassTstructNode{Tdata;NodeT*next;};templateclassTclassLinkList{public:LinkList(Ta[],intn);//建¡§立¢¡é有®Dn个?元a素?的Ì?单Ì£¤链¢¡ä表À¨ª~LinkList();//析?构1函¡¥数ºyvoidInsert(inti,Tx);//在¨²单Ì£¤链¢¡ä表À¨ª中D第̨²i个?位?置?插?入¨?元a素?值¦Ì为ax的Ì?结¨¢点Ì?TDelete(inti);//在¨²单Ì£¤链¢¡ä表À¨ª中D删¦?除y第̨²i个?结¨¢点Ì?intLocate(Tx);//求¨®单Ì£¤链¢¡ä表À¨ª中D值¦Ì为ax的Ì?元a素?序¨°号?voidPrintList();//遍À¨¦历¤¨²单Ì£¤链¢¡ä表À¨ª，ê?按ã¡ä序¨°号?依°¨¤次ä?输º?出?各¡Â元a素?private:NodeT*first;};templateclassTLinkListT::LinkList(Ta[],intn){NodeT*s;first=newNodeT;first-next=NULL;for(inti=0;in;i++){s=newNodeT;s-data=a[i];s-next=first-next;first-next=s;}};templateclassTLinkListT::~LinkList(){NodeT*q;NodeT*p=first;while(p){q=p;p=p-next;deleteq;}}templateclassTvoidLinkListT::Insert(inti,Tx){NodeT*p,*s;p=first;intj=0;//工¡è作Á¡Â指?针?p初?始º?化¡¥while(p&&ji-1){p=p-next;//工¡è作Á¡Â指?针?p后¨®移°?j++;}if(!p)throw位?置?;else{s=newNodeT();s-data=x;//向¨°内¨²存ä?申¦¨º请?一°?个?结¨¢点Ì?s，ê?其?数ºy据Y域®¨°为axs-next=p-next;//将?结¨¢点Ì?s插?入¨?到Ì?结¨¢点Ì?p之?后¨®p-next=s;}}templateclassTTLinkListT::Delete(inti){NodeT*p,*q;intx;p=first;intj=0;//工¡è作Á¡Â指?针?p初?始º?化¡¥while(p&&ji-1)//查¨¦找¨°第̨²i-1个?结¨¢点Ì?{p=p-next;j++;}if(!p||!p-next)throw位?置?;//结¨¢点Ì?p不?存ä?在¨²或¨°结¨¢点Ì?p的Ì?后¨®继¨¬结¨¢点Ì?不?存ä?在¨²else{q=p-next;x=q-data;//暂Y存ä?被À?删¦?结¨¢点Ì?p-next=q-next;//摘a链¢¡ädeleteq;returnx;}}templateclassTintLinkListT::Locate(Tx){NodeT*p;p=first-next;intj=1;while(p&&p-data!=x){p=p-next;//工¡è作Á¡Â指?针?p后¨®移°?j++;}if(p)returnj;elsereturn0;}templateclassTvoidLinkListT::PrintList(){NodeT*p;p=first-next;while(p!=NULL){coutp-data;p=p-next;}coutendl;}voidmeun(){//cout请?输º?入¨?几?个?数ºy字Á?endl;//inti;//cini;cout1、¡é插?入¨?endl;cout2、¡é删¦?除yendl;cout3、¡é查¨¦找¨°endl;cout4、¡é显?示º?endl;}intmain(){meun();inta[5]={23,14,56,78,90};//coutaendl;LinkListintb1(a,5);intfly=1;while(fly){cout请?你?输º?入¨?需¨¨要°a的Ì?选?项?：êo;intk,d,f,x,b,loc;cinb;switch(b){case1:{cout请?输º?入¨?要°a插?入¨?的Ì?数ºy字Á?endl;//intk;cink;cout请?选?择?要°a插?入¨?的Ì?位?置?endl;//intd;cind;//LinkListintc(intd,intk);b1.Insert(d,k);break;}case2:{cout请?输º?入¨?要°a删¦?除y的Ì?数ºy字Á?位?置?endl;//intf;cinf;//LinkListintl(intf);//LinkListintc(intf);b1.Delete(f);break;}case3:{cout请?输º?入¨?你?要°a查¨¦找¨°的Ì?数ºy字Á?endl;//intx;cinx;loc=b1.Locate(k);cout所¨´查¨¦数ºy据Y所¨´在¨²：êoloc位?endl;//LinkListintc(intx);b1.Locate(x);break;}case4:{b1.PrintList();break;}default:{cout你?输º?入¨?的Ì?数ºy字Á?有®D误¨®，ê?想?坑¨®爹̨´吗e？ê?endl;break;}}}return0;}四、运行与调试a)在调试程序的过程中遇到什么问题，是如何解决的？答：经常忘记对头结点的定义，以至于程序出错，经定义头结点，使程序正常运行b)设计了哪些设计数据？测试结果是什么？答：设计了插入、删除、显示、按值查找算法，实现插入、删除、显示、按值查找数据的功能。c)程序运行的结果如何？d)五、实验小结链表是通过指针来描述元素关系的一种数据结构，对于数组，可以动态的改变数据的长度，分配物理空间。因此单链表不用像顺序表那样指定长度，需要注意的是头插法和尾插法的不同，本程序用的是头插法因此最先输入的数据会排在链表的最后,输出时即变成了输入时的逆序输出。