2023年数据结构实验报告单链表

2023级数据结构实验报告实验名称：实验一线性表一一题目1学生姓名：李文超班级：班内序号：15号:期：2023年11月13日自然语言描述:a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node<T>*s=newNode<T>;b：s-data=p->datac：s->next=p->nextd:p->next=se：p->data=x(9)删除函数自然语言描述：a:从第一个结点开始,查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e：释放q元素伪代码描述a：q=p->nextb：p->next=q—>nextc：x=q->datad:deleteq2、代码具体分析(插入)：(1)从第一个结点开始，查找节点，使它的数据比x大，设P指向该结点:while(x>p->data){p=p—>next；}(2)新建一个节点s,把p的数据赋给s：s->data=p->data：(3)把s力口至Up后面:s—>nexl=p—>next;p->next=s;(4)p节点的数据用x替换:p->data=x;p->data3、关键算法的时间复杂度：0(1)3.程序运营结果1.流程图：初始化一个整形数组，作为赋值准备分别运用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行插入函数，之后遍历打印函数来测试是否真的插入执行删除函数，之后遍历打印函数来测试是否真的删执行花侨杳找和带值杳杪函物2、结果截图•d:\Cpp\vader\Debug\vader.exe线性表的长度为：8幄历线性表结果为:123456国入一个值后的线性表为:0123456，d:\Cpp\vader\Debug\vader.exe删除一个值后的线性表为：146I,第5个位置上的元素地址是:009E5440请按任意键继续....测试结论:可以对的的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后,链表的顺序仍然是由小到大。4、给出代码（文末）.总结1问题①书中已经给出析构、查找、插入、删除过程代码，遍历以及获取长度代码需要自己写出，刚开始写时一直出现各种基本错误,后来通过不断调试解决了问题。②编写main函数时，调用插入删除等操作的代码一直编写失败,后自行查找资料后解2、收获这次编程任务完毕地较为艰辛，但做完之后大大加深了自己对书中各个知识点的印象和理解。也学会了一些编写算法的小技巧，要有耐心，多看书复习知识。总之，这次实验使我印象深刻。#include<iostream>usingnamespacestd：temp1ate<classT>structNode(0Tdata;structNode*next;)：temp1ate<classT>cIassLinkList(Pub1ic:0LinkList()//无参构造0(PEfront=newNode<T>：front->next=NULL；)0LinkList(Ta[],intn)；//头插法0//LinkList(Ta[],intn);〃尾插法voidPrintList<)；〃按顺序遍历0intGetLength();〃获取线性表的长度Node<T>*Gct(inti)：〃获取笫i个位置上的元素结点的地址intLocate(Tx);//查找0voidInsert(inti,Tx);〃插入0TDelete(inti);〃删除ETUnkListO；〃销毁private：ENode<T>*front;)；tempiate<classT>LinkList<T>::LinkList(Ta[],intn)//头插法front=newNode<T>;front->next=NULL：for(inti=n-1；i>=0;i--)0(Node<T>*s=newNode<T>;〃建立新结点s->data=a[i];//给新结点数据域赋值0s->next=front—>next;〃修改新结点的指针域闭front—>next=s;〃修改头指针的指针域0)}/*temp1ate<classT>LinkList<T>：：LinkList(Ta(],intn)〃尾插法(front=newNode<T>;Node<T>*r=front;for(inti=0；i<n；i++)Node<T>*s=newNode<T>；s->data=a[i]：r->next=s;r=s;}r->next=NULL；}*/ternpIate<cIassT>voidLinkList<T>::PrintList(){Node<T>*p=front;0whi1e(p->next!=NULL){Ep=p—>next;cout<<p->data<<end1；0))temp1ate<classT>intLinkList<T>：：GetLength()Node<T>*p=front；intn=0;while(p—>next!=NULL){p=p—>next：n++;}@returnn;)template<classT>Node<T>*LinkList<T>::Get(inti)(Node<T>*p=front->next;intj=1;while(p&&j!=i)(p=P->next：00j++：.实验规定实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完毕线性表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：规定建立的链表按照关键字从小到大有序3、删除4、查找0returnp;tempIate<classT>voidLinkList<T>:：Insert(inti,Tx){@Node<T>*p=front;if(i!=1)03p=Get(i-1)；0if(P)0(0Node<T>*s=newNode<T>；0s->data=x;s—>next=p->next;@p->next=s;即Elelsethrow"位置错误";template<classT>TLinkList<T>:：De1ete(inti)(0Node<T>*p=front;0if(i!=1)p=Get(i-1)；if(!p&&!p->next)throw"位置错误”；Node<T>*q=p->next;P->next=q->next；Tx=q->data：deleteq;0returnx;)tempIate<cIassT>LinkList<T>::"wLinkList()(HNode<T>*p=front：while(p)0(p=p->next；Hdeletefront;00front=p;0))intmain()(constintn=8;inta[n]={1,2,3,4,5,6,7,8)；LinkList<int>list(a,n)；0cout<<”线性表的长度为:"<<list.GetLength{)<<end1;cout«endI;cout«"遍历线性表结果为："<VendI;01ist.PrintList();0cout«endl;0cout<<”插入一个值后的线性表为:"V<endl;list.Insert(1,0);01ist.PrintList()；cout<<endl;0cout<<"删除一个值后的线性表为:"«endl：list.Delete(l);Olist.PrintList();0cout«endI；cout«"第个位置上的元素地址是："«endI;0cout«list.Get(2)<<endI;0cout«endl；Pllist.~LinkUst()；system("pause")：return0;5、获取链表长度6、销毁7、其他:可自行定义编写测试main()函数测试线性表的对的性。.程序分析2.1存储结构单链表的存储：(1)链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的,也可以是不连续的，甚至零散地分布在内存的某些位置。(2)链表中结点的逻辑顺序和物理顺序不一定相同。为了能对的表达结点间的逻辑关系,在存储每个元素值的同时,还要存储该元素的直接后继元素的位置信息，这个信息称为指针或链。结点结构a।11data域---存放结点值的数据域a|data|next|next域存放结点的直接后继的地址的指针域a।114单链表在内存中的存储示意内存单元地址内存单元头指针一►frcn"…42关键算法分析1、关键算法:►（1）头插法自然语言描述:a:在堆中建立新结点b：将a[i]写入到新结点的数据域c：修改新结点的指针域d：修改头结点的指针域。将新结点加入链表中伪代码描述a：Node<T>*s=newNode<T>b:s->data=a[i]c:s->next=front—>next;d:front->next=s(2)尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d：修改修改尾指针伪代码描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:r->next=s;d:r=s(3)遍历打印函数自然语言描述：a：判断该链表是否为空链表,假如是,报错b:假如不是空链表,新建立一个temp指针c:将lemp指针指向头结点d：打印tcmp指针的data域e:逐个往后移动temp指针,直到temp指针的指向的指针的next域为空伪代码描述a:Iffront->next==NU1.L①Throw"anempty1ist”②Node〈T〉*temp=front->next；b:while(temp->next)c:cout<<temp->data<<”";d:temp=temp->next;(4)获取链表长度函数自然语言描述:a:判断该链表是否为空链表，假如是，输出长度0b:假如不是空链表，新建立一个temp指针，初始化整形数n为。c：将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，假如不是,n加一，否则returnne：使temp指针逐个后移,反复d操作，直到temp指针指向的结点的next域为0,返回n伪代码描述ifront->next==NULLb：Node<T>*temp=front->next;while(temp—>next)temp=temp->next;(5)析构/删除函数自然语言描述：a:新建立一个指针,指向头结点b：判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针