2023年數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告單鏈表

2023級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)一線性表一一題目1學(xué)生姓名：李文超班級(jí)：班內(nèi)序號(hào)：15號(hào):期：2023年11月13日自然語(yǔ)言描述:a:在堆中建立新結(jié)點(diǎn)b:將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn)的數(shù)據(jù)域c:修改新結(jié)點(diǎn)的指針域d:修改前一個(gè)指針的指針域，使其指向新插入的結(jié)點(diǎn)的位置偽代碼描述a:Node<T>*s=newNode<T>;b：s-data=p->datac：s->next=p->nextd:p->next=se：p->data=x(9)刪除函數(shù)自然語(yǔ)言描述：a:從第一個(gè)結(jié)點(diǎn)開始,查找要?jiǎng)h除的位數(shù)i前一個(gè)位置i-1的結(jié)點(diǎn)b:設(shè)q指向第i個(gè)元素c:將q元素從鏈表中刪除d:保存q元素的數(shù)據(jù)e：釋放q元素偽代碼描述a：q=p->nextb：p->next=q—>nextc：x=q->datad:deleteq2、代碼具體分析(插入)：(1)從第一個(gè)結(jié)點(diǎn)開始，查找節(jié)點(diǎn)，使它的數(shù)據(jù)比x大，設(shè)P指向該結(jié)點(diǎn):while(x>p->data){p=p—>next；}(2)新建一個(gè)節(jié)點(diǎn)s,把p的數(shù)據(jù)賦給s：s->data=p->data：(3)把s力口至Up后面:s—>nexl=p—>next;p->next=s;(4)p節(jié)點(diǎn)的數(shù)據(jù)用x替換:p->data=x;p->data3、關(guān)鍵算法的時(shí)間復(fù)雜度：0(1)3.程序運(yùn)營(yíng)結(jié)果1.流程圖：初始化一個(gè)整形數(shù)組，作為賦值準(zhǔn)備分別運(yùn)用頭插法和尾插法初始化，并且用遍歷打印函數(shù)來(lái)顯示數(shù)值執(zhí)行插入函數(shù)，之后遍歷打印函數(shù)來(lái)測(cè)試是否真的插入執(zhí)行刪除函數(shù)，之后遍歷打印函數(shù)來(lái)測(cè)試是否真的刪執(zhí)行花僑杳找和帶值杳杪函物2、結(jié)果截圖?d:\Cpp\vader\Debug\vader.exe線性表的長(zhǎng)度為：8幄歷線性表結(jié)果為:123456國(guó)入一個(gè)值后的線性表為:0123456，d:\Cpp\vader\Debug\vader.exe刪除一個(gè)值后的線性表為：146I,第5個(gè)位置上的元素地址是:009E5440請(qǐng)按任意鍵繼續(xù)....測(cè)試結(jié)論:可以對(duì)的的對(duì)鏈表進(jìn)行插入，刪除，取長(zhǎng)度，輸出操作。且插入任意一個(gè)元素后,鏈表的順序仍然是由小到大。4、給出代碼（文末）.總結(jié)1問(wèn)題①書中已經(jīng)給出析構(gòu)、查找、插入、刪除過(guò)程代碼，遍歷以及獲取長(zhǎng)度代碼需要自己寫出，剛開始寫時(shí)一直出現(xiàn)各種基本錯(cuò)誤,后來(lái)通過(guò)不斷調(diào)試解決了問(wèn)題。②編寫main函數(shù)時(shí)，調(diào)用插入刪除等操作的代碼一直編寫失敗,后自行查找資料后解2、收獲這次編程任務(wù)完畢地較為艱辛，但做完之后大大加深了自己對(duì)書中各個(gè)知識(shí)點(diǎn)的印象和理解。也學(xué)會(huì)了一些編寫算法的小技巧，要有耐心，多看書復(fù)習(xí)知識(shí)?？傊@次實(shí)驗(yàn)使我印象深刻。#include<iostream>usingnamespacestd：temp1ate<classT>structNode(0Tdata;structNode*next;)：temp1ate<classT>cIassLinkList(Pub1ic:0LinkList()//無(wú)參構(gòu)造0(PEfront=newNode<T>：front->next=NULL；)0LinkList(Ta[],intn)；//頭插法0//LinkList(Ta[],intn);〃尾插法voidPrintList<)；〃按順序遍歷0intGetLength();〃獲取線性表的長(zhǎng)度Node<T>*Gct(inti)：〃獲取笫i個(gè)位置上的元素結(jié)點(diǎn)的地址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>;〃建立新結(jié)點(diǎn)s->data=a[i];//給新結(jié)點(diǎn)數(shù)據(jù)域賦值0s->next=front—>next;〃修改新結(jié)點(diǎn)的指針域閉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++：.實(shí)驗(yàn)規(guī)定實(shí)驗(yàn)?zāi)康模焊鶕?jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表，并完畢線性表的基本功能。線性表存儲(chǔ)結(jié)構(gòu)（五選一）：1、帶頭結(jié)點(diǎn)的單鏈表2、不帶頭結(jié)點(diǎn)的單鏈表3、循環(huán)鏈表4、雙鏈表5、靜態(tài)鏈表線性表的基本功能：1、構(gòu)造：使用頭插法、尾插法兩種方法2、插入：規(guī)定建立的鏈表按照關(guān)鍵字從小到大有序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"位置錯(cuò)誤";template<classT>TLinkList<T>:：De1ete(inti)(0Node<T>*p=front;0if(i!=1)p=Get(i-1)；if(!p&&!p->next)throw"位置錯(cuò)誤”；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<<”線性表的長(zhǎng)度為:"<<list.GetLength{)<<end1;cout?endI;cout?"遍歷線性表結(jié)果為："<VendI;01ist.PrintList();0cout?endl;0cout<<”插入一個(gè)值后的線性表為:"V<endl;list.Insert(1,0);01ist.PrintList()；cout<<endl;0cout<<"刪除一個(gè)值后的線性表為:"?endl：list.Delete(l);Olist.PrintList();0cout?endI；cout?"第個(gè)位置上的元素地址是："?endI;0cout?list.Get(2)<<endI;0cout?endl；Pllist.~LinkUst()；system("pause")：return0;5、獲取鏈表長(zhǎng)度6、銷毀7、其他:可自行定義編寫測(cè)試main()函數(shù)測(cè)試線性表的對(duì)的性。.程序分析2.1存儲(chǔ)結(jié)構(gòu)單鏈表的存儲(chǔ)：(1)鏈表用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)。這組存儲(chǔ)單元既可以是連續(xù)的,也可以是不連續(xù)的，甚至零散地分布在內(nèi)存的某些位置。(2)鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。為了能對(duì)的表達(dá)結(jié)點(diǎn)間的邏輯關(guān)系,在存儲(chǔ)每個(gè)元素值的同時(shí),還要存儲(chǔ)該元素的直接后繼元素的位置信息，這個(gè)信息稱為指針或鏈。結(jié)點(diǎn)結(jié)構(gòu)a?11data域---存放結(jié)點(diǎn)值的數(shù)據(jù)域a|data|next|next域存放結(jié)點(diǎn)的直接后繼的地址的指針域a?114單鏈表在內(nèi)存中的存儲(chǔ)示意內(nèi)存單元地址內(nèi)存單元頭指針一?frcn"…42關(guān)鍵算法分析1、關(guān)鍵算法:?（1）頭插法自然語(yǔ)言描述:a:在堆中建立新結(jié)點(diǎn)b：將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域c：修改新結(jié)點(diǎn)的指針域d：修改頭結(jié)點(diǎn)的指針域。將新結(jié)點(diǎn)加入鏈表中偽代碼描述a：Node<T>*s=newNode<T>b:s->data=a[i]c:s->next=front—>next;d:front->next=s(2)尾插法自然語(yǔ)言描述：a:在堆中建立新結(jié)點(diǎn)：b:將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域：c:將新結(jié)點(diǎn)加入到鏈表中d：修改修改尾指針偽代碼描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:r->next=s;d:r=s(3)遍歷打印函數(shù)自然語(yǔ)言描述：a：判斷該鏈表是否為空鏈表,假如是,報(bào)錯(cuò)b:假如不是空鏈表,新建立一個(gè)temp指針c:將lemp指針指向頭結(jié)點(diǎn)d：打印tcmp指針的data域e:逐個(gè)往后移動(dòng)temp指針,直到temp指針的指向的指針的next域?yàn)榭諅未a描述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)獲取鏈表長(zhǎng)度函數(shù)自然語(yǔ)言描述:a:判斷該鏈表是否為空鏈表，假如是，輸出長(zhǎng)度0b:假如不是空鏈表，新建立一個(gè)temp指針，初始化整形數(shù)n為。c：將temp指針指向頭結(jié)點(diǎn)d:判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，假如不是,n加一，否則returnne：使temp指針逐個(gè)后移,反復(fù)d操作，直到temp指針指向的結(jié)點(diǎn)的next域?yàn)?,返回n偽代碼描述ifront->next==NULLb：Node<T>*temp=front->next;while(temp—>next)temp=temp->next;(5)析構(gòu)/刪除函數(shù)自然語(yǔ)言描述：a:新建立一個(gè)指針,指向頭結(jié)點(diǎn)b：判斷要釋放的結(jié)點(diǎn)是否存在，c:暫時(shí)保存要釋放的結(jié)點(diǎn)d:移動(dòng)a中建立的指針e:釋放要釋放的指針