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

2 0 23级数据结构实验报告实验名称：实验一线性表一一题目1学生姓名：李文超班 级：班内序号：15 号:期：202 3年11月13日自然语言描述:a:在堆中建立新结点b :将要插入的结点的数据写入到新结点的数据域c :修改新结点的指针域d :修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a : No de < T > * s=new No d e <T >b： s-d ata =p-> d atac： s->nex t =p->nextd : p->next=se： p->d a ta= 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:dele t e q2、代码具体分析(插入)：(1)从第一个结点开始，查找节点，使它的数据比x大，设P指向该结点:while (x>p->data) p=p>n ext； (2)新建一个节点s,把p的数据赋给s： s ->dat a =p->data：(3)把 s 力口至 Up后面:s> nexl=p>n ext; p-> n ex t =s;(4) p节点的数据用x替换:p-> d at a = x ;p->d a ta3、关键算法的时间复杂度：0(1)3.程序运营结果1.流程图：初始化一个整形数组，作为赋值准备分别运用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行插入函数，之后遍历打印函数来测试是否真的插入执行删除函数，之后遍历打印函数来测试是否真的删执行花侨杳找和带值杳杪函物2、结果截图 d:CppvaderDebugvader.exe线性表的长度为：8 幄历线性表结果为:123456国入一个值后的线性表为: 0123456，d:CppvaderDebugvader.exe删除一个值后的线性表为：146I,第5个位置上的元素地址是: 009E5440请按任意键继续.3 .测试结论:可以对的的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后, 链表的顺序仍然是由小到大。4、给出代码（文末）.总结1 问题书中已经给出析构、查找、插入、删除过程代码，遍历以及获取长度代码需要自己写 出，刚开始写时一直出现各种基本错误,后来通过不断调试解决了问题。编写ma in函数时，调用插入删除等操作的代码一直编写失败,后自行查找资料后解2、收获这次编程任务完毕地较为艰辛，但做完之后大大加深了自己对书中各个知识点的印象 和理解。也学会了一些编写算法的小技巧，要有耐心，多看书复习知识。总之，这次实验使我 印象深刻。# include <i o s t r e a m>using n am e s p a c e std：t e mp 1 a t e <class T>struct Node(0T data;struct No d e * next;)：t em p 1 ate <cla s s T>c I ass Link Li s t(P ub 1 i c:0LinkList() / /无参构造0(PEfront = new No d e<T>：f r o n t->next = NULL；)0Lin k Li s t( T a, i nt n )；/ / 头插法0/Link L ist(T a, i n t n);尾插法void PrintList <)； 按顺序遍历0 i n t Ge t Length();获取线性表的长度N o de <T>* G c t(int i)： 获取笫i个位置上的元素结点的地址i nt L o c at e (T x ) ; / / 查找0void I nsert(in t i, T x);插入0T Del e t e (int i );删除ETUnkListO ；销毁p r i v a te：ENode <T> * fro n t;)；tempi a t e <class T>Li n kL i st<T>:L i n kList(T a, i nt n) / /头插法fro n t = new Nod e<T>fron t ->next = NU LL：f o r (i n t i = n - 1； i >= 0; i-)0(Node<T> * s = n ew Node<T>建立新结点s->da t a = a i ;/ /给新结点数据域赋值0 s ->nex t =front>next;修改新结点的指针域闭front >next = s; 修改头指针的指针域0)/*t e mp 1 at e <cl ass T>Lin kList<T>： ： L i nkL i s t (T a(, i nt n ) 尾插法(fro nt=new Nod e<T>Nod e <T> * r = f ro n t;f o r(int i = 0 ； i< n ； i +)N o de< T > * s = new Node<T>；s->data= a i ：r -> n e xt=s;r=s;r->ne x t=NULL；*/tern p I a te < c I a ss T>voi d LinkL i s t <T>: Pri n tList ()N ode< T > * p = fr o nt;0whi 1 e(p-> n e x t != NU L L) Ep = p>next;cout << p-> d ata << e nd 1 ；0) temp 1 ate <class T> in t LinkList<T>： ： G e tL e ng t h()Nod e <T> * p = f r o n t；in t n = 0;while( p >n e xt != NULL) p = p>next： n+; r e tu r n n;)tem p late <cl ass T>No d e<T> * Li n kL i s t <T>:Get ( i nt i ) (Nod e<T> * p = fr o n t ->next;intj= 1;whil e ( p &&j != i)(p = P ->next：00j+：1 .实验规定实验目的：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完毕线性 表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：规定建立的链表按照关键字从小到大有序3、删除 4、查找0 r eturn p;tem p I a te <cl a ss T>v o id LinkL i st<T>:： Insert (i n t i, T x )N o de<T> * p = f r o nt;if(i != 1 )03p = G et( i -1)；0i f (P)0(0Node< T > * s = new Node< T >；0s-> d ata = x;s>n e x t = p ->next;p->n e xt = s;即Elelse throw"位置错误"templa t e <cla s s T>T LinkL i st<T>:： D e 1 ete (int i)(0N o de< T > * p = f r o nt;0if (i != 1 ) p = Get (i- 1)；if(!p && !p->next) throw"位置错误”；Node <T> * q = p-> n e xt;P -> n ext = q ->next；Tx = q ->data：delete q;0 r e t u r n x;)t em p I a te < c I a ss T>LinkList<T>:"wLinkLi s t()(HN o de< T> * p = fro n t ：w hile (p)0(p = p->n e xt；H del e t e fr o nt;00front = p;0)i n t mai n ()(const int n = 8;int an = 1,2,3,4, 5,6,7, 8)；Link List<int> list(a, n )；0co u t<< ”线性表的长度为:"<< list.GetLe n g t h ) << end 1 ;c o u t « e n d I;c o u t« "遍历线性表结果为："<Ve n d I;0 1 i st.PrintLis t ();0 c ou t « endl;0 c o ut<< ”插入一个值后的线性表为:" V< e ndl;list. Inser t (1, 0 );0 1 ist. Pr i ntLi s t()；cout<<endl;0cou t <<"删除一个值后的线性表为:"«endl：list.Dele t e(l);Olis t .PrintL i s t ();0 c out«e n d I；c out« "第个位置上的元素地址是："«en d I;0 c o ut« list.Get(2) << end I ;0cout«endl；Pllist. LinkU s t ()；syst e m ("pau s e")：r eturn 0;5、获取链表长度 6、销毁7、其他:可自行定义编写测试ma i n()函数测试线性表的对的性。2 .程序分析2. 1存储结构单链表的存储：(1)链表用一组任意的存储单元来存放线性表的结点。这组存储单元既可以是连续的, 也可以是不连续的，甚至零散地分布在内存的某些位置。(2)链表中结点的逻辑顺序和物理顺序不一定相同。为了能对的表达结点间的逻辑关系, 在存储每个元素值的同时,还要存储该元素的直接后继元素的位置信息，这个信息称为指针 或链。结点结构a 11da ta域-存放结点值的数据域a | da t a | ne x t |next域 存放结点的直接后继的地址的指针域a 114单链表在内存中的存储示意内存单元地址头指针一f rcn"42关键算法分析 1、关键算法:（1）头插法自然语言描述:a :在堆中建立新结点b：将ai写入到新结点的数据域c：修改新结点的指针域d：修改头结点的指针域。将新结点加入链表中伪代码描述a： Node <T> * s=new Node <T>b :s->data=aic: s->ne x t = front >n e xt;d : f r o n t ->n e xt=s(2)尾插法自然语言描述：a :在堆中建立新结点：b :将a i 写入到新结点的数据域：c :将新结点加入到链表中d：修改修改尾指针伪代码描述a: No de <T> * s=new Node <T>b:s->data= a ic:r->ne x t =s;d:r= s(3)遍历打印函数自然语言描述：a ：判断该链表是否为空链表,假如是,报错b:假如不是空链表,新建立一个temp指针c:将lemp指针指向头结点d ：打印t cmp指针的d a ta域e:逐个往后移动tem p指针,直到t emp指针的指向的指针的next域为空伪代码描述a : I f f r ont-> n e x t = =NU1. LThrow " a n emp t y 1 ist ”NodeT* t e mp= f r o n t ->ne x t；b:while (temp-> n ext)c :cout<< t e mp-> data <<”"d:temp=temp->next;(4 )获取链表长度函数自然语言描述:a :判断该链表是否为空链表，假如是，输出长度0b:假如不是空链表，新建立一个temp指针，初始化整形数n为。c：将temp指针指向头结点d :判断temp指针指向的结点的ne x t域是否为空，假如不是,n加一，否则re t urn ne ： 使temp指针逐个后移,反复d操作，直到temp指针指向的结点的ne x t 域为0,返回n伪代码描述a: if ront-> n ex t =NULLb： No d e<T>* tem p = f r ont->next;w h ile (tem p > n ext)c: tem p =temp->n ext;(5)析构/删除函数自然语言描述：a :新建立一个指针,指向头结点b：判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e :释放要释放的指针伪代码描述a： Node <T> * p=frontw h ile (p)c： f r on t =pd:p=p->nexte： del e t e f r ont(6)按位查找函数自然语言描述：a:初始化工作指针p和计数器j, p指向第一个结点,j = lb:循环以下操作，直到p为空或者j等于1:P指向下一个结点:j加1c:若p为空,说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素,返回元素地址 伪代码描述a:Node <T> * p=fron t ->nex t ； j=l;b :wh i 1 e(p&&j!=l)：P =p->ne x t：j +b: i f (! p) throw ”er rorwd:re t u rn p(7)按位查找函数自然语言描述：a：初始化工作指针p和计数器j, P指向第一个结点，j=lb：循环以下操作，找到这个元素或者p指向最后一个结点:判断P指向的结点是不是要查找的值，假如是，返回j，否则P指向下一个 结点，并且j的值加一c:假如找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a: Node <T> * p=fr o nt-> n e x t; j= 1 ;b: while(p)： if(p->ne x t=x) re t urn jp= p ->nextj+c: r e tur n “error”(8)插入函数