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

實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告實(shí)驗(yàn)名稱：實(shí)驗(yàn)一——鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表學(xué)生姓名：班級：班內(nèi)序號：學(xué)號：日期：實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模和ㄟ^選擇下面四個題目之一進(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)線性表，并完成線性表的基本功能。線性表存儲結(jié)構(gòu)（五選一）：帶頭結(jié)點(diǎn)的單鏈表不帶頭結(jié)點(diǎn)的單鏈表循環(huán)鏈表雙鏈表靜態(tài)鏈表線性表的基本功能：構(gòu)造：使用頭插法、尾插法兩種方法插入：要求建立的鏈表按照關(guān)鍵字從小到大有序刪除查找獲取鏈表長度銷毀其他：可自行定義編寫測試main()函數(shù)測試線性表的正確性。2.程序分析存儲結(jié)構(gòu)存儲結(jié)構(gòu)：順序表關(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;時間復(fù)雜度：O(n)尾插法算法步驟：堆中建立新結(jié)點(diǎn)Node<T>*s=newNode<T>;將新結(jié)點(diǎn)加入到鏈表中r->next=front->next修改尾指針r=s按值查找結(jié)點(diǎn)示意圖：eq\o\ac(○,1)定位計數(shù)和定位指針inti=1; Node<T>*p; p=front->next;eq\o\ac(○,2)比較P指向的元素是否與檢索值相同 if(p) while(p) { if(p->data==n) cout<<"元素序號："<<i<<endl; p=p->next; i++; } else throw"空鏈表！";時間復(fù)雜度：O(n)插入操作：算法步驟：堆中建立新結(jié)點(diǎn)Node<T>*s=newNode<T>;將新結(jié)點(diǎn)插入到要插入位置后一節(jié)點(diǎn)p的后面，將后一結(jié)點(diǎn)數(shù)據(jù)寫入sP指向s，在p中寫入新的值s->data=p->data; s->next=p->next;p->next=s; p->data=x;時間復(fù)雜度：O（1）刪除結(jié)點(diǎn)示意圖：刪除結(jié)點(diǎn)示意圖算法步驟：①從第一個結(jié)點(diǎn)開始，查找第i-1個元素，設(shè)為p指向該結(jié)點(diǎn)；②設(shè)q指向第i個元素：q=p->next;③摘鏈，即將q元素從鏈表中摘除：p->next=q->next;④保存q元素的數(shù)據(jù)：x=q->data;⑤釋放q元素：deleteq;說明：如果算法比較復(fù)雜，可以將多句代碼合成一個步驟進(jìn)行說明。比如也可以這樣寫：①從第一個結(jié)點(diǎn)開始，查找第i-1個元素，設(shè)為p指向該結(jié)點(diǎn)；②設(shè)q指向第i個元素：q=p->next;③摘鏈，即將q元素從鏈表中摘除：p->next=q->next;x=q->datadeleteq;時間復(fù)雜度：O(n)其他程序代碼：#include<iostream>usingnamespacestd;template<classT>structNode{ Tdata; structNode<T>*next;};template<classT>classLinkList{public: LinkList(){front=newNode<T>;front->next=NULL;} LinkList(Ta[],intn); ~LinkList(); Node<T>*Get(inti); Node<T>*Locate(intn,Node<T>*s); voidInsert(inti,Tx); TDelete(inti); intGetLength(); voidPrint();private: Node<T>*front;};template<classT>LinkList<T>::LinkList(Ta[],intn)程序運(yùn)行結(jié)果測試主函數(shù)流程：流程圖如圖所示開始打印序列開始打印序列是否退出結(jié)束是輸入插入的位置和數(shù)值輸入插入的位置和數(shù)值打印修改后序列打印修改后序列輸入刪除的位置輸入刪除的位置打印修改后序列打印修改后序列輸入查找的關(guān)鍵值輸入查找的關(guān)鍵值打印查找關(guān)鍵值打印查找關(guān)鍵值的位置測試條件：初始序列為123456插入位置1數(shù)值6是刪除元素序號3查找元素序號2查找元素6測試結(jié)論初始序列為123456插入位置1數(shù)值6后序列：6123456是刪除元素序號3后序列：613456查找元素序號2后查找到序號2所對應(yīng)元素為：1查找元素6查找到所對應(yīng)元素序號為1和64.總結(jié)本次實(shí)驗(yàn)我掌握了線性表的操作的實(shí)現(xiàn)方法，實(shí)現(xiàn)了線