2023年數(shù)據(jù)結構實驗報告單鏈表

2023級數(shù)據(jù)結構實驗報告實驗名稱：實驗一線性表一一題目1學生姓名：李文超班級：班內(nèi)序號：15號:期：2023年11月13日自然語言描述:a:在堆中建立新結點b:將要插入的結點的數(shù)據(jù)寫入到新結點的數(shù)據(jù)域c:修改新結點的指針域d:修改前一個指針的指針域，使其指向新插入的結點的位置偽代碼描述a:Node<T>*s=newNode<T>;b：s-data=p->datac：s->next=p->nextd:p->next=se：p->data=x(9)刪除函數(shù)自然語言描述：a:從第一個結點開始,查找要刪除的位數(shù)i前一個位置i-1的結點b:設q指向第i個元素c:將q元素從鏈表中刪除d:保存q元素的數(shù)據(jù)e：釋放q元素偽代碼描述a：q=p->nextb：p->next=q—>nextc：x=q->datad:deleteq2、代碼具體分析(插入)：(1)從第一個結點開始，查找節(jié)點，使它的數(shù)據(jù)比x大，設P指向該結點:while(x>p->data){p=p—>next；}(2)新建一個節(jié)點s,把p的數(shù)據(jù)賦給s：s->data=p->data：(3)把s力口至Up后面:s—>nexl=p—>next;p->next=s;(4)p節(jié)點的數(shù)據(jù)用x替換:p->data=x;p->data3、關鍵算法的時間復雜度：0(1)3.程序運營結果1.流程圖：初始化一個整形數(shù)組，作為賦值準備分別運用頭插法和尾插法初始化，并且用遍歷打印函數(shù)來顯示數(shù)值執(zhí)行插入函數(shù)，之后遍歷打印函數(shù)來測試是否真的插入執(zhí)行刪除函數(shù)，之后遍歷打印函數(shù)來測試是否真的刪執(zhí)行花僑杳找和帶值杳杪函物2、結果截圖?d:\Cpp\vader\Debug\vader.exe線性表的長度為：8幄歷線性表結果為:123456國入一個值后的線性表為:0123456，d:\Cpp\vader\Debug\vader.exe刪除一個值后的線性表為：146I,第5個位置上的元素地址是:009E5440請按任意鍵繼續(xù)....測試結論:可以對的的對鏈表進行插入，刪除，取長度，輸出操作。且插入任意一個元素后,鏈表的順序仍然是由小到大。4、給出代碼（文末）.總結1問題①書中已經(jīng)給出析構、查找、插入、刪除過程代碼，遍歷以及獲取長度代碼需要自己寫出，剛開始寫時一直出現(xiàn)各種基本錯誤,后來通過不斷調(diào)試解決了問題。②編寫main函數(shù)時，調(diào)用插入刪除等操作的代碼一直編寫失敗,后自行查找資料后解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];//給新結點數(shù)據(jù)域賦值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++：.實驗規(guī)定實驗目的：根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈式結構實現(xiàn)線性表，并完畢線性表的基本功能。線性表存儲結構（五選一）：1、帶頭結點的單鏈表2、不帶頭結點的單鏈表3、循環(huán)鏈表4、雙鏈表5、靜態(tài)鏈表線性表的基本功能：1、構造：使用頭插法、尾插法兩種方法2、插入：規(guī)定建立的鏈表按照關鍵字從小到大有序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()函數(shù)測試線性表的對的性。.程序分析2.1存儲結構單鏈表的存儲：(1)鏈表用一組任意的存儲單元來存放線性表的結點。這組存儲單元既可以是連續(xù)的,也可以是不連續(xù)的，甚至零散地分布在內(nèi)存的某些位置。(2)鏈表中結點的邏輯順序和物理順序不一定相同。為了能對的表達結點間的邏輯關系,在存儲每個元素值的同時,還要存儲該元素的直接后繼元素的位置信息，這個信息稱為指針或鏈。結點結構a?11data域---存放結點值的數(shù)據(jù)域a|data|next|next域存放結點的直接后繼的地址的指針域a?114單鏈表在內(nèi)存中的存儲示意內(nèi)存單元地址內(nèi)存單元頭指針一?frcn"…42關鍵算法分析1、關鍵算法:?（1）頭插法自然語言描述:a:在堆中建立新結點b：將a[i]寫入到新結點的數(shù)據(jù)域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]寫入到新結點的數(shù)據(jù)域：c:將新結點加入到鏈表中d：修改修改尾指針偽代碼描述a:Node<T>*s=newNode<T>b:s->data=a[i]c:r->next=s;d:r=s(3)遍歷打印函數(shù)自然語言描述：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)獲取鏈表長度函數(shù)自然語言描述:a:判斷該鏈表是否為空鏈表，假如是，輸出長度0b:假如不是空鏈表，新建立一個temp指針，初始化整形數(shù)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)析構/刪除函數(shù)自然語言描述：a:新建立一個指針,指向頭結點b：判斷要釋放的結點是否存在，c:暫時保存要釋放的結點d:移動a中建立的指針e:釋放要釋放的指針