實(shí)驗(yàn)一-鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表

北京郵電大學(xué)信息與通信工程學(xué)院第5頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表學(xué)生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模和ㄟ^選擇下面四個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法學(xué)習(xí)指針、模板類、異常處理的使用掌握線性表的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用線性表解決實(shí)際問題的能力實(shí)驗(yàn)內(nèi)容：根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表，并完成線性表的基本功能。線性表存儲(chǔ)結(jié)構(gòu)（五選一）：帶頭結(jié)點(diǎn)的單鏈表不帶頭結(jié)點(diǎn)的單鏈表循環(huán)鏈表雙鏈表靜態(tài)鏈表線性表的基本功能：構(gòu)造：使用頭插法、尾插法兩種方法插入：要求建立的鏈表按照關(guān)鍵字從小到大有序刪除查找獲取鏈表長(zhǎng)度銷毀其他：可自行定義編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：順序表2.2關(guān)鍵算法分析頭插法示意圖：算法步驟：堆中建立新結(jié)點(diǎn)S->next指向front->nextfront->next指向sNode<T>*s=newNode<T>; s->data=a[i]; s->next=front->next; front->next=s;時(shí)間復(fù)雜度：O(n)尾插法算法步驟：堆中建立新結(jié)點(diǎn)Node<T>*s=newNode<T>;將新結(jié)點(diǎn)加入到鏈表中r->next=front->next修改尾指針r=s按值查找結(jié)點(diǎn)示意圖：template<classT>LinkList<T>::~LinkList()//析構(gòu)函數(shù){ Node<T>*p=front; while(p) { front=p; p=p->next; deletefront; }}template<classT>Node<T>*LinkList<T>::Get(inti){ Node<T>*p=front->next; intj=1; while(p&&j!=i) { p=p->next; j++; } returnp; }template<classT>Node<T>*LinkList<T>::Locate(intn,Node<T>*s){ inti=1; Node<T>*p; p=front->next; if(p) while(p) { if(p->data==n) cout<<"元素序號(hào)："<<i<<endl; p=p->next; i++; } else throw"空鏈表！"; /*while(p&&p->data!=n) { p=p->next; } returnp; t=0; if(p->next)// Locate(n,p->next) ; else returnNULL;*/}template<classT>voidLinkList<T>::Insert(inti,Tx){ Node<T>*p=Get(i); if(p) {Node<T>*s=newNode<T>; s->data=p->data;// s->next=p->next; p->next=s; p->data=x; } else throw"輸入有誤";}template<classT>TLinkList<T>::Delete(inti){ Node<T>*p=front; if(i!=1) p=Get(i-1); Node<T>*q=p->next; p->next=q->next; Tx=q->data; deleteq; returnx;}template<classT>intLinkList<T>::GetLength(){ inti=0; Node<T>*p=front->next; if(p){ i++; p=p->next;} returni;}template<classT>voidLinkList<T>::Print(){ Node<T>*p=front->next; if(front->next) { while(p) { cout<<p->data<<""; p=p->next; } cout<<endl; } else throw"該表沒有元素";}voidmain(){ intx,y; inta[6]={1,2,3,4,5,6}; LinkList<int>L(a,6); L.Print(); cout<<"請(qǐng)輸入要插入的位置和數(shù)值："; cin>>x>>y; L.Insert(x,y); L.Print(); cout<<"請(qǐng)輸入要?jiǎng)h除的元素序號(hào)："; cin>>x; L.Delete(x); L.Print(); cout<<"請(qǐng)輸入需要查找的元素序號(hào)："; cin>>x; cout<<L.Get(x)->data<<endl; cout<<"請(qǐng)輸入需要查找的元素："; cin>>x; L.Locate(x,NULL); cout<<L.GetLength();3.程序運(yùn)行結(jié)果測(cè)試主函數(shù)流程：流程圖如圖所示開始打印序列開始打印序列是否退出？結(jié)束是輸入插入的位置和數(shù)值輸入插入的位置和數(shù)值打印修改后序列打印修改后序列輸入刪除的位置輸入刪除的位置打印修改后序列打印修改后序列輸入查找的關(guān)鍵值輸入查找的關(guān)鍵值打印查找關(guān)鍵值打印查找關(guān)鍵值的位置測(cè)試條件：初始序列為123456插入位置1數(shù)值6是刪除元素序號(hào)3查找元素序號(hào)2查找元素6測(cè)試結(jié)論初始序列為123456插入位置1數(shù)值6后序列：6123456是刪除元素序號(hào)3后序列：613456查找元素序號(hào)2后查找到序號(hào)2所對(duì)應(yīng)元素為：1查找元素6查找到所對(duì)應(yīng)元素序號(hào)為1和64.總結(jié)本次實(shí)驗(yàn)我掌握了線性表的