實驗一：線性表應(yīng)用

1、實驗報告學(xué)院（系）名稱：計算機與通信工程學(xué)院姓名* *學(xué)號* *專業(yè)計算機科學(xué)與技術(shù)班級2015級*班實驗項目實驗一：線性表應(yīng)用 課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實驗時間2017年 3 月 9 日第一節(jié)實驗地點7-219考核標(biāo)準(zhǔn)實驗過程25分程序運行20分回答問題15分實驗報告30分特色功能5分考勤違紀(jì)情況5分成績成績欄其它批改意見: 教師簽字：考核內(nèi)容評價在實驗課堂中的表現(xiàn)，包括實驗態(tài)度、編寫程序過程等內(nèi)容等。功能完善, 功能不全有小錯無法運行正確基本正確有提示無法回答完整較完整一般內(nèi)容極少無報告有無有無 一、實驗?zāi)康膶嶒災(zāi)康模?理解線性表的邏輯特點；掌握順序表、鏈表存儲結(jié)構(gòu)，以

2、及線性表的基本操作，如插入、刪除、查找，以及線性表合并等操作在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)算法，并能夠在實際問題背景下的靈活運用線性表來解決問題，實現(xiàn)相應(yīng)算法。二、實驗題目與要求1一元稀疏多項式簡單的計算器 1）問題描述：用線性表表示一元稀疏多項式，設(shè)計一個一元多項式運算器 2）要求: （1）采用單鏈表存儲結(jié)構(gòu)一元稀疏多項式 （2）輸入并建立多項式 （3）輸出多項式 （4）實現(xiàn)多項式加、減運算 3）分析算法時間復(fù)雜度 2. 約瑟夫環(huán)問題 1）問題描述：有編號為 1, 2n 的 n 個人按順時針方向圍坐一圈，每人持有一個正整數(shù) 密碼。開始給定一個正整數(shù) m，從第一個人按順時針方向自 1 開

3、始報數(shù)，報到 m 者出列，不再參加 報數(shù)，這時將出列者的密碼作為 m，從出列者順時針方向的下一人開始重新自 1 開始報數(shù)。如此下 去，直到所有人都出列。試設(shè)計算法，輸出出列者的序列。 2）要求: 采用順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)實現(xiàn) 3）分析算法時間復(fù)雜度 3單鏈表基本操作練習(xí) 1）問題描述：在主程序中提供下列菜單： 1建立鏈表 2連接鏈表 3輸出鏈表 0結(jié)束 2）實驗要求：算法中包含下列過程，分別完成相應(yīng)的功能： CreateLinklist(): 從鍵盤輸入數(shù)據(jù)，創(chuàng)建單鏈表 ContLinklist()：將前面建立的兩個單鏈表首尾相連 OutputLinklist()：輸出顯示單鏈表 3）分析算

4、法時間復(fù)雜度 4單鏈表基本操作練習(xí) 1）問題描述：已知單鏈表 L（帶頭節(jié)點）是一個遞增有序表，試編寫算法，刪除表中值大 于 min 且小于 max 的節(jié)點（若表中有這樣的節(jié)點），同時釋放被刪節(jié)點的空間。 2）實驗要求：min 和 max 是兩個給定參數(shù)。 3）分析算法時間復(fù)雜三、 實驗過程與實驗結(jié)果 應(yīng)包括如下主要內(nèi)容：Ø 數(shù)據(jù)結(jié)構(gòu)定義Ø 鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存

5、儲下一個結(jié)點地址的指針域。 Ø 算法設(shè)計思路簡介Ø 通過建立包含數(shù)據(jù)和指針的節(jié)點來保存數(shù)據(jù)，然后將一系列節(jié)點通過指針插入到鏈表中去，實現(xiàn)建立鏈表，插入、刪除節(jié)點，進而組合各種基本功能，編寫符合題目要求的算法。Ø 算法描述：可以用自然語言、偽代碼或流程圖等方式Ø 1、ØØ （1）將多項式各項的系數(shù)和指數(shù)分別存在A、B兩個鏈表的中。Ø （2）用指針Pa、Pb分別指向連個鏈表的首元素。Ø （3）遍歷兩個鏈表，比較各元素的指數(shù)，若相同則相加減，將結(jié)果插入新表中，若不相等則將指數(shù)較小的插入新表中，繼續(xù)向后遍歷，直到

6、其中一個鏈表到達表尾。Ø （4）將另一表中的剩余元素按指數(shù)大小順序全部插入到新表中。Ø （5）新表中的元素按規(guī)定格式輸出既為相加或相減后的多項式。Ø 3、ØØ （1）通過構(gòu)造函數(shù)創(chuàng)建單鏈表Ø （2）通過循環(huán)變量temp找到第一個鏈表的尾部設(shè)為p。Ø （3）使p的next指向第二個鏈表的第一個元素Ø （4）將連接后的兩鏈表輸出Ø 4、Ø （1）用兩個變量minZ,maxZ分別存儲輸入的最小值和最大值Ø （2）遍歷整個單鏈表，將小于minZ和大于maxZ的節(jié)點刪除Ø （3）輸出操

7、作后的單鏈表Ø 算法的實現(xiàn)和測試結(jié)果：包括算法運行時的輸入、輸出，實驗中出現(xiàn)的問題及解決辦法等Ø 出現(xiàn)問題Ø 無法返回操作后的單鏈表Ø 解決辦法Ø 經(jīng)老師直到后，在相關(guān)函數(shù)前面加*成功返回操作后的單鏈表Ø 1、 3、 4、 Ø 算法時間復(fù)雜度分析Ø 1、O(1表長度+2表長度)-可視為O(n)Ø 3、O(1表長度+2表長度)- 可視為O(n)Ø 4、O(n)¨四、收獲與體會線性表分為順序表和鏈表，其中順序表已相當(dāng)熟悉，主要練了新接觸的鏈表，感覺現(xiàn)在才真正體會到指針的魅力之處。同時也明白

8、了順序表和鏈表的優(yōu)缺點，在老師的知道下，更增進了對C+的理解。算法相對來說還是比較簡單的，很容易理解，關(guān)鍵在如何把算法變成你想要的計算機程序，在實驗課以及平時的訓(xùn)練中，自己對代碼的理解、控制能力都有所提高。五、源代碼清單采取分文件方式編寫源代碼1、節(jié)點文件Node.hclass Node /元素節(jié)點public:Node(int iCoef = 0,int iExp = 0);void printNode();/打印函數(shù)int coef;/系數(shù)int exp;/指數(shù)Node *next;Node.cpp#include"Node.h"#include<iostream

9、>using namespace std;Node:Node(int iCoef,int iExp) coef = iCoef;exp = iExp;void Node:printNode() if(exp = 0) cout << coef << "x"else cout << coef << "x" << exp;鏈表文件List1.h#include"Node.h"class List public:List();/建立鏈表List();/銷毀鏈表void Cle

10、arList();/清空鏈表bool ListInsert(int i,Node *pNode);/從指定位置將元素插入鏈表bool ListInsertTail(Node *pNode);/從尾部將元素插入鏈表List *ListAdd(List *pList1,List *pList2);/多項式相加函數(shù)List *ListMinus(List *pList1,List *pList2);/多項式相減函數(shù)void ListTraverse();/遍歷輸出函數(shù)private:int m_iLength;/鏈表長度Node *m_pList;/頭指針;List1.cpp#include<

11、iostream>#include"List1.h"using namespace std;List:List() m_pList = new Node;m_pList->coef = 0;m_pList->exp = 0;m_pList->next = NULL;m_iLength = 0;void List:ClearList() Node *CurrentNode = m_pList->next;while(CurrentNode != NULL) Node *temp = CurrentNode->next;delete Curr

12、entNode;CurrentNode = temp;m_pList->next = NULL;List:List() ClearList();delete m_pList;m_pList = NULL;bool List:ListInsert(int i,Node *pNode) Node *NewNode = new Node();if(i < 1 | i> m_iLength + 1) cout << "插入位置不合法." << endl;return false; else if(NewNode = NULL) cout &

13、lt;< "申請內(nèi)存失敗." << endl;return false; else Node *temp = m_pList;for(int k = 0;k < i - 1;k+) temp = temp->next;NewNode->coef = pNode->coef;NewNode->exp = pNode->exp;NewNode->next = temp->next;temp->next = NewNode;m_iLength+;return true;bool List:ListInsert

14、Tail(Node *pNode) Node *NewNode = new Node();if(NewNode = NULL) cout << "申請內(nèi)存失敗." << endl;return false; else Node *temp = m_pList;while(temp->next != NULL) temp = temp->next;NewNode->coef = pNode->coef;NewNode->exp = pNode->exp;temp->next = NewNode;NewNode-

15、>next = NULL;m_iLength+;return true;List *List:ListAdd(List *pList1,List *pList2) Node *Pa,*Pb;int x;List *pList3 = new List();Pa = pList1->m_pList->next;Pb = pList2->m_pList->next; while(Pa && Pb) if(Pa->exp = Pb->exp) x = Pa->coef + Pb->coef;if(x != 0) Node *n =

16、new Node();n->coef = x;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->next;Pb = Pb->next;else if(Pa->exp < Pb->exp) Node *n = new Node();n->coef = Pa->coef;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->next; else if(Pa->exp > Pb->exp)

17、Node *n = new Node();n->coef = Pb->coef;n->exp = Pb->exp;pList3->ListInsertTail(n);Pb = Pb->next;while(Pa) Node *n = new Node();n->coef = Pa->coef;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->next;while(Pb) Node *n = new Node();n->coef = Pb->coef;n-&g

18、t;exp = Pb->exp;pList3->ListInsertTail(n);Pb = Pb->next;return pList3;List *List:ListMinus(List *pList1,List *pList2) Node *Pa,*Pb;int x;List *pList3 = new List();Pa = pList1->m_pList->next;Pb = pList2->m_pList->next; while(Pa && Pb) if(Pa->exp = Pb->exp) x = Pa-&g

19、t;coef - Pb->coef;if(x != 0) Node *n = new Node();n->coef = x;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->next;Pb = Pb->next;else if(Pa->exp < Pb->exp) Node *n = new Node();n->coef = Pa->coef;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->

20、next; else if(Pa->exp > Pb->exp) Node *n = new Node();n->coef = Pb->coef;n->exp = Pb->exp;pList3->ListInsertTail(n);Pb = Pb->next;while(Pa) Node *n = new Node();n->coef = Pa->coef;n->exp = Pa->exp;pList3->ListInsertTail(n);Pa = Pa->next;while(Pb) Node *n

21、= new Node();n->coef = Pb->coef;n->exp = Pb->exp;pList3->ListInsertTail(n);Pb = Pb->next;return pList3;void List:ListTraverse() Node *temp = m_pList->next;cout << endl;while(temp != NULL) temp->printNode();if(temp->next != NULL) if(temp->next->coef > 0) cout

22、 << "+" else if(temp->next->coef = 0) continue; else cout << ""temp = temp->next;cout << endl; 主文件 Demo.cpp#include"List1.h"#include<iostream>using namespace std;int main()Node *n0 = new Node(20,0);Node *n1 = new Node(4,2);Node *n2 = new

23、 Node(2,5);Node *n3 = new Node(7,9);Node *n4 = new Node(5,12);Node *n5 = new Node(-11,18);List *pList1 = new List();pList1->ListInsert(1,n0);pList1->ListInsert(2,n1);pList1->ListInsert(3,n2);pList1->ListInsert(4,n3);pList1->ListInsert(5,n4);pList1->ListInsertTail(n5);pList1->Lis

24、tTraverse();Node *m1 = new Node(12,3);Node *m2 = new Node(2,5);Node *m3 = new Node(9,8);Node *m4 = new Node(20,9);Node *m5 = new Node(11,18);List *pList2 = new List();pList2->ListInsert(1,m1);pList2->ListInsert(2,m2);pList2->ListInsert(3,m3);pList2->ListInsert(4,m4);pList2->ListInsert

25、(5,m5);pList2->ListTraverse();List *pList4 = new List();pList4 = pList4->ListAdd(pList1,pList2);pList4->ListTraverse();pList4 = pList4->ListMinus(pList1,pList2);pList4->ListTraverse();return 0;3、節(jié)點文件Node.hclass Node public:int data;Node *next;Node(int iData = 0);void printNode();Node.

26、cpp#include"Node.h"#include<iostream>using namespace std;Node:Node(int iData) data = iData;void Node:printNode() cout << data << " "鏈表文件List.h#include"Node.h"class List public:List();/建立鏈表List();/銷毀鏈表void ClearList();/清空鏈表bool ListInsertTail(Node *pNod

27、e);/從尾部插入元素List *ContLinklist(List *pList1,List *pList2);/連接鏈表void OutputLinklist();/輸出鏈表private:Node *m_pList;int m_iLength;List.cpp#include"List.h"#include<iostream>using namespace std;List:List() m_pList = new Node();m_pList->data = 0;m_pList->next = NULL;m_iLength = 0;List

28、*List:ContLinklist(List *pList1,List *pList2) List *pList3 = pList1;Node *temp = pList3->m_pList;while(temp->next != NULL) temp = temp->next;temp->next = pList2->m_pList->next;return pList3;void List:OutputLinklist() Node *temp = m_pList;while(temp->next != NULL) temp = temp->

29、;next;temp->printNode();bool List:ListInsertTail(Node *pNode) Node *NewNode = new Node();if(NewNode = NULL) cout<<"申請內(nèi)存失敗."<<endl;return false; else Node *temp = m_pList;while(temp->next != NULL) temp = temp->next;NewNode->data = pNode->data;temp->next = NewNo

30、de;NewNode->next = NULL;m_iLength+;return true;void List:ClearList() Node *CurrentNode = m_pList->next;while(CurrentNode != NULL) Node *temp = CurrentNode->next;delete CurrentNode;CurrentNode = temp;m_pList->next = NULL;List:List() ClearList();delete m_pList;m_pList = NULL;主文件Demo.cpp#in

31、clude"List.h"#include<iostream>using namespace std;int main() Node *n1 = new Node(3);Node *n2 = new Node(7);Node *n3 = new Node(5);Node *n4 = new Node(6);Node *n5 = new Node(5);Node *n6 = new Node(1);List *pList1 = new List();List *pList2 = new List();List *pList3 = new List();cout &

32、lt;< "鏈表1 :" << endl;pList1->ListInsertTail(n1);pList1->ListInsertTail(n2);pList1->ListInsertTail(n3);pList1->OutputLinklist();pList2->ListInsertTail(n4);pList2->ListInsertTail(n5);pList2->ListInsertTail(n6);cout << endl << "鏈表2 :" <&l

33、t; endl;pList2->OutputLinklist();cout << endl << "連接之后為 :" << endl;pList3 = pList3->ContLinklist(pList1,pList2);pList3->OutputLinklist();return 0;4、#include<iostream>using namespace std;class Node public:int data;Node *next;Node(int iData = 0);void printNod

34、e();Node:Node(int iData) data = iData;void Node:printNode() cout << data << " "class List public:List();/建立鏈表List();/銷毀鏈表void ClearList();/清空鏈表bool ListInsertTail(Node *pNode);/從尾部將元素插入鏈表void OutputLinklist();/輸出鏈表void DeleteList(int min,int max);/刪除鏈表中的元素private:Node *m_pList;

35、/頭指針int m_iLength;/長度;List:List() m_pList = new Node();m_pList->data = 0;m_pList->next = NULL;m_iLength = 0;void List:OutputLinklist() Node *temp = m_pList;if(m_pList = NULL) cout << -1 << endl;while(temp->next != NULL) temp = temp->next;temp->printNode();bool List:ListInsertTail(Node *pNode) Node *NewNode = new Node();if(NewNode = NULL) cout<<"申請內(nèi)存失敗."<<endl;return false; else Node *temp = m_pList;while(temp->next != NULL) temp = temp->next;NewNode->data = pNode->data;temp->next = NewNode;NewNode->