實驗一-鏈式結(jié)構(gòu)實現(xiàn)線性表

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