數(shù)據(jù)結(jié)構(gòu)與測繪軟件開發(fā)

1、?數(shù)據(jù)結(jié)構(gòu)與測繪軟件開發(fā)?實驗指導(dǎo)書中國礦業(yè)大學(xué)測繪與國土信息中心2021-05-20實驗一 線性表類的設(shè)計與實現(xiàn)4學(xué)時一、實驗要求利用C+語言編程分別實現(xiàn)線性表的順序存儲與鏈?zhǔn)酱鎯?。二、實驗根本操?、新建工程1執(zhí)行菜單：文件新建工程，選擇“Win32控制臺應(yīng)用程序；2更改工程存儲路徑；3更改工程名稱；4點擊“確定。2、添加頭文件與類的聲明1頭文件在#include “stdafx.h之后參加如下語句：#include <iostream>using namespace std;2順序表在main函數(shù)前參加如下類的聲明：class SeqListpublic:/ 構(gòu)造、析構(gòu)函數(shù)

2、SeqList(); explicit SeqList(int maxSize); / 僅包含一個參數(shù)的構(gòu)造函數(shù) SeqList( );public:/ 復(fù)制構(gòu)造函數(shù)、賦值運算SeqList(const SeqList& sl);SeqList& operator=(const SeqList& sl);public:/ 成員函數(shù) int Length( ) const; int Find(int& x) const; / 查找int Locate(int i) const; / 定位 int Insert(int& x, int i ); / 插入 i

3、nt Remove(int& x ); / 刪除 int Next(int& x ) ; / 后繼 int Prior(int& x ) ; / 前驅(qū) int IsEmpty( ); int IsFull ( ); int Get (int i) / 提取private:/ 成員變量 int * _data; int _curSize; int _maxSize;3鏈表Typedef struct LNode int data; / 數(shù)據(jù)域 struct Lnode *prior; / 指針域 struct Lnode *next; / 指針域 LNode; class

4、 LinkedListpublic:/ 構(gòu)造、析構(gòu)函數(shù) LinkedList(int MaxSize = 0); LinkedList( );public:/ 復(fù)制構(gòu)造函數(shù)、賦值運算 LinkedList (const LinkedList& sl); LinkedList& operator=(const LinkedList& sl)public:/ 成員函數(shù) int length( ) const; int search(int& x) const; / 查找 int insert(int& x, int i ); / 插入 int remove(

5、int& x ); / 刪除 void sort( );/ 排序 int isEmpty( ); void setNull( );/ 置空 int get (int i) / 提取private:/ 成員變量 LNode *head; int _size;3、添加類的實現(xiàn)代碼順序表在各自類的聲明之后，添加如下代碼：1順序表的函數(shù)/ 構(gòu)造函數(shù)SeqLis:SeqList(): _data(NULL), _maxSize(0), _curSize(0)SeqList:SeqList(int maxSize): _maxSize(maxSize), _curSize(0)_data = ne

6、w int_maxSize;/ 開辟用于存儲線性表的空間連續(xù)空間/ 析構(gòu)函數(shù)SeqList:SeqList()if (NULL != _data)delete _data;/ 取得線性表的長度int SeqList:Length() constreturn _curSize;/ 在線性表中定位x所在位置int SeqList:Find(Type& x) constfor (int i = 0; i < _curSize; +i)if (x = _datai)return i;return -1;/ 插入元素xint SeqList:Insert(Type& x, int

7、i)/ 判斷下標(biāo)是否越界if (i < 0 | i >= _maxSize)return -1;/ 判斷線性表是否已滿if (_curSize = _maxSize)return -1;/ 判斷插入的位置是否位于_curSize之后if (i < _maxSize - 1) && i >= _curSize)_data_curSize = x;_curSize+;/ 線性表的長度加1return 1;/ 首先將位于位置i之后的所有元素后移一個位置for (int j = _curSize; j > i; j-)_dataj = _dataj - 1

8、;_datai = x;/ 將待插入元素插入i位置_curSize+;/ 線性表的長度加1return 1;/ 刪除元素xint SeqList:Remove(Type& x)for (int i = 0; i < _curSize; i+)if (_datai = x)/ 將i位置之后的元素前移一個位置for (int j = i; j < _curSize - 1; j+)_dataj = _dataj+1;_curSize-;return 1;return 0;/ 取得x所在位置的下一個位置int SeqList:Next(Type& x)for (int i

9、 = 0; i < _curSize; i+)if (_datai = x)return i + 1;/ 調(diào)用此函數(shù)的過程需要檢查返回的值是否越界/ 取得x所在位置的前一個位置int SeqList:Prior(Type& x)for (int i = 0; i < _curSize; i+)if (_datai = x)return i - 1;/ 調(diào)用此函數(shù)的過程需要檢查返回的值是否越界/ 判斷線性表是否為空int SeqList:IsEmpty()if (_curSize <= 0)return 1;else return 0;/ 判斷線性表是否已經(jīng)存儲滿int

10、 SeqList:IsFull()if (_curSize = _maxSize)return 1;elsereturn 0;/ 取得i位置的元素Type SeqList:Get(int i)return _datai;2順序表的兩個重要應(yīng)用/-/ 集合的交與并/-void Join(SeqList<int>& A, SeqList<int>& B, SeqList<int>& R)/ 首先遍歷Afor (int i = 0; i < A.getCurSize(); +i)int x = A.Get(i);/ 取得i位置的元素i

11、f (B.Find(x) != -1)/ 在B中尋找同樣的元素，假設(shè)不成功，那么返回-1R.Insert(x, R.getCurSize();void Merge(SeqList<int>& A, SeqList<int>& B)for (int i = 0; i < B.getCurSize(); +i)int x = B.Get(i);if (A.Find(x) = -1)A.Insert(x, A.getCurSize();3main函數(shù)的實現(xiàn)int main(int argc, char* argv)/ 實例化兩個線性表SeqList A(

12、20);SeqList B(20);/ 線性表A的數(shù)據(jù)初始化for (int i = 0; i < 10; i+)A.Insert(i, i);/ 線性表B的數(shù)據(jù)初始化for (int i = 5; i < 15; i+)B.Insert(i, i - 5);/ 輸出Acout << "A:" << endl;for (int i = 0; i < A.getCurSize(); i+)cout << A.Get(i) << " "cout << endl;/ 輸出Bcout

13、<< "B:" << endl;for (int i = 0; i < B.getCurSize(); i+)cout << B.Get(i) << " "cout << endl;/ 交運算SeqList<int> R(20);Join(A, B, R);/ 交運算結(jié)果輸出cout << "線性表A與B取交的結(jié)果：" << endl;for (int i = 0; i < R.getCurSize(); i+)cout <

14、;< R.Get(i) << " "cout << endl;/ 并運算cout << "線性表A與B取并的結(jié)果：" << endl;Merge(A, B);/ 并運算結(jié)果輸出for (int i = 0; i < A.getCurSize(); i+)cout << A.Get(i) << " "cout << endl;/ 友元函數(shù)調(diào)用cout << "模板輸出結(jié)果：n"cout << A &

15、lt;< endl;cout << B << endl;cout << R << endl;return 0;4、添加類的實現(xiàn)代碼鏈表1鏈表的實現(xiàn)函數(shù)/ 構(gòu)造函數(shù)LinkedList:LinkedList(): size(0), head(NULL)LinkedList:LinkedList(int MaxSize): _size(MaxSize), _head(NULL)int LinkedList:Length() constreturn size;/ 返回元素x所在的位置，第一個節(jié)點序號為1int LinkedList:Search(

16、Type& x) constif (NULL = head)return -1;int result = 1;ListNode *cur;cur = head;while (cur != NULL)if (cur->data = x)return result;elsecur = cur->next;result+;return -1;int LinkedList:Insert(Type& x, int i)if (i <= 0)/ 越界return -1;if (size = 0)/ 插入結(jié)點操作ListNode *temLN = new ListNode(

17、);temLN->data = x;temLN->link = NULL;head = temLN;size+;return 1;else if (i > size)/ 在鏈表尾部插入ListNode *cur = head;while (cur->link != NULL)cur = cur->link;/ 插入結(jié)點操作ListNode *temLN = new ListNode ();temLN->data = x;temLN->link = NULL;cur->link = temLN;size+;return 1;ListNode *cu

18、r = head;for (int k = 1; k < i - 1; k+)cur = cur->link;/ 插入結(jié)點操作ListNode *temLN = new ListNode ();temLN->data = x;temLN->link = cur->link;cur->link = temLN;size+;return 1;int LinkedList :Remove(Type& x)ListNode * cur = head;if (cur->data = x)/ 刪除表頭第一個元素head = cur->link;ret

19、urn 1;/ 刪除除表頭之外的其他位置元素while (cur->link != NULL)if (cur->link->data = x)/ 執(zhí)行刪除操作cur->link = cur->link->link;return 1;cur = cur->link;return 1;int LinkedList :IsEmpty()if (size = 0 | head = NULL)return 1;return 0;void LinkedList :SetNull()size = 0;head = NULL;Type LinkedList :Get(

20、int i)if (i <= 0 | i > size)cout << "下表越界！" << endl;return;ListNode* cur = head;for (int k = 1; k <i; k+)cur = cur->link;return cur->data;void LinkedList :Output()ListNode * cur;cur = head;while (cur != NULL)cout << cur->data << " "cur =

21、cur->link;cout << endl;2main函數(shù)的實現(xiàn)int main(int argc, char* argv)/ 建立一個包含10個結(jié)點的鏈表LinkedList myList;for (int i = 1; i <= 10; +i)myList.Insert(i, i);/ 遍歷myList.Output();/ 刪除第5個元素int x = 5;myList.Remove(x);/ 遍歷myList.Output();/ 在第5個元素位置處插入一個50x = 50;myList.Insert(x, 5);/ 遍歷myList.Output();ret

22、urn 0;實驗二 二叉樹的構(gòu)建與遍歷一、實驗要求利用C+語言編程實現(xiàn)二叉樹的構(gòu)建及其先序、中序、后序遍歷算法.二、實驗根本操作1、新建工程1執(zhí)行菜單：文件新建工程，選擇“Win32控制臺應(yīng)用程序；2更改工程存儲路徑；3更改工程名稱；4點擊“確定。2、添加頭文件與類的聲明1頭文件在#include “stdafx.h之后參加如下語句：#include <iostream>#include <vector>using namespace std;2類的聲明在main函數(shù)前參加如下類的聲明：typedef struct BTNodeint data;BTNode *lChi

23、ld;BTNode *rChild; SBTNode;class CBinTreepublic:/ 構(gòu)造、析構(gòu)函數(shù)CBinTree();CBinTree();/ 構(gòu)造二叉排序樹void createBSTree(vector<int>& xArray);void insertNode(SBTNode*& temNode, BTNode*& root);/ 樹的遍歷void InOrder(BTNode*& root);/ 中序遍歷 void PreOrder(BTNode*& root);/ 先序遍歷 void PostOrder(BTNod

24、e*& root);/ 后序遍歷 public:BTNode* root;vector<int> xArray;3、添加類的實現(xiàn)代碼1二叉樹的實現(xiàn)函數(shù)/ 構(gòu)造函數(shù)CBinTree:CBinTree(): root(NULL)/ 析構(gòu)函數(shù)CBinTree:CBinTree()xArray.clear();/ 構(gòu)造一顆二叉排序樹void CBinTree:createBSTree(vector<int>& xArray)for (vector<int>:iterator iter = xArray.begin();iter != xArray.e

25、nd(); +iter)BTNode *temNode = new BTNode;temNode->data = *iter;temNode->lChild = NULL;temNode->rChild = NULL;insertNode(temNode, root);/ 構(gòu)造二叉排序樹的插入節(jié)點子過程void CBinTree:insertNode(SBTNode*& temNode, BTNode*& root)if (root = NULL)root = temNode;elseif (temNode->data > root->dat

26、a)insertNode(temNode, root->rChild);elseinsertNode(temNode, root->lChild);/ 二叉樹的中序遍歷void CBinTree:InOrder(BTNode*& root)if (root = NULL)return;InOrder(root->lChild);cout << root->data << " "InOrder(root->rChild);/ 二叉樹的先序遍歷void CBinTree:PreOrder(BTNode*& r

27、oot)if (root = NULL)return;cout << root->data << " "PreOrder(root->lChild);PreOrder(root->rChild);/ 二叉樹的后續(xù)遍歷void CBinTree:PostOrder(BTNode*& root)if (root = NULL)return;PostOrder(root->lChild);PostOrder(root->rChild);cout << root->data << "

28、; "2main函數(shù)的實現(xiàn)int main(int argc, char* argv)/ 構(gòu)造一棵二叉排序樹vector<int> xArray;xArray.push_back(10);xArray.push_back(18);xArray.push_back(3);xArray.push_back(8);xArray.push_back(12);xArray.push_back(2);xArray.push_back(7);xArray.push_back(4);CBinTree BT;BT.createBSTree(xArray);/ 樹的遍歷/ 中序遍歷BT.In

29、Order(BT.root);cout << endl;/ 先序遍歷BT.PreOrder(BT.root);cout << endl;/ 后序遍歷BT.PostOrder(BT.root);cout << endl;return 0;實驗三 圖的創(chuàng)立、遍歷及其MST的構(gòu)建一、實驗要求利用C+語言編程實現(xiàn)二叉樹的構(gòu)建及其先序、中序、后序遍歷算法.二、實驗內(nèi)容1圖的創(chuàng)立2基于深度優(yōu)先的圖的遍歷算法的設(shè)計與實現(xiàn)3基于廣度優(yōu)先的圖的遍歷算法的設(shè)計與實現(xiàn)4基于Prim算法的最小生成樹的構(gòu)建5基于Kruskal算法的最小生成樹的構(gòu)建三、實驗根本操作1、新建工程1執(zhí)行菜

30、單：文件新建工程，選擇“Win32控制臺應(yīng)用程序；2更改工程存儲路徑；3更改工程名稱；4點擊“確定。2、添加頭文件與類的聲明1頭文件在#include “stdafx.h之后參加如下語句：#include <vector>#include <map>#include <deque>#include <iostream>using namespace std;2類的聲明在main函數(shù)前參加如下類的聲明：/ 用于存儲圖的節(jié)點及其相鄰節(jié)點的結(jié)構(gòu)體變量類型struct SGNode int key; / 結(jié)點自身標(biāo)識 map<int, float&

31、gt; neighNodes; / 與當(dāng)前結(jié)點相鄰的結(jié)點集合，及其與相鄰結(jié)點之間路徑的權(quán)值 ;/ 用于存儲邊的結(jié)構(gòu)體變量類型struct SGEdge int start;int end;/ 用于存儲邊及其權(quán)重的map容器注意：會按照權(quán)重自小而大自動排序typedef map<float, SGEdge> EdgeSet;class CMyGraphpublic:CMyGraph(void);CMyGraph(void);public: / 其他函數(shù)，供實例調(diào)用 void DFS(); void DFS(int i, vector<int>& mystack,

32、bool* visited); void BFS(); void BFS(int i, deque<int>& mydeque, bool* visited); void Prim(); void Kruskal(); protected: / 屬性變量 /* 自行設(shè)計完成 */ private: / 成員變量 vector<SGNode> NodeSet;3、添加類的實現(xiàn)代碼CMyGraph:CMyGraph(void)float g88 = 0, 12,1,0,0,0,0, 4,12,0, 0, 11, 0, 10, 0, 0,1, 0, 0, 9, 2,

33、0, 0, 0,0, 11, 9, 0, 0, 0, 8, 0,0, 0, 2, 0, 0, 0, 5, 3,0, 10, 0, 0, 0, 0, 7, 6,0, 0, 0, 8, 5, 7, 0, 0,4, 0, 0, 0, 3, 6, 0, 0;for (int i = 0; i < 8; i+)SGNode sg;sg.key = i;NodeSet.push_back(sg);for (int i = 0; i < 8; i+)for (int j = 0; j < 8; j+)if (gij != 0)NodeSeti.neighNodes.insert(map&l

34、t;int, float>:value_type(j, gij);vector<SGNode>:iterator iter;for (iter = NodeSet.begin(); iter != NodeSet.end(); iter+)cout << (*iter).key;map<int, float>:iterator iter2;for (iter2 = (*iter).neighNodes.begin(); iter2 != (*iter).neighNodes.end(); iter2+)cout << ", (&q

35、uot; << (*iter2).first << ", " << (*iter2).second << ")"cout << endl;CMyGraph:CMyGraph(void)void CMyGraph:DFS()bool *visited;visited = new bool8;for (int i = 0; i < 8; i+)visitedi = false;vector<int> mystack;DFS(0, mystack, visited);void CMy

36、Graph:DFS(int i, vector<int>& mystack, bool * visited)if (i >= 0 && i < NodeSet.size()if (!visitedi)cout << i << "n"mystack.push_back(i);visitedi = true;map<int, float>:iterator iter;for (iter = NodeSeti.neighNodes.begin(); iter != NodeSeti.neighNo

37、des.end(); iter+)if (!visited(*iter).first)DFS(*iter).first, mystack, visited);if (iter = NodeSeti.neighNodes.end()if (mystack.size() > 0)mystack.pop_back();if (mystack.size() > 0)DFS(mystack.at(mystack.size() - 1), mystack, visited);void CMyGraph:BFS()bool *visited;visited = new bool8;for (in

38、t i = 0; i < 8; i+)visitedi = false;deque<int> mydeque;BFS(0, mydeque, visited);void CMyGraph:BFS(int i, deque<int>& mydeque, bool* visited)if (!visitedi)cout << i << "n"for (map<int, float>:iterator iter = NodeSeti.neighNodes.begin();iter != NodeSeti.n

39、eighNodes.end(); iter+)if (!visited(*iter).first)mydeque.push_back(*iter).first);visitedi = true;while (mydeque.size() > 0)int i = mydeque.at(0);mydeque.pop_front();BFS(i, mydeque, visited);void CMyGraph:Prim()/ 選擇圖中的任一頂點作為起點int start = 0;int s1;set<int> mtSet;mtSet.insert(start);/ 選擇初始節(jié)點fl

40、oat weight;while (1)weight = 100000.0f;/ 人為設(shè)定較大值start = -1;s1 = -1;for (set<int>:iterator iter = mtSet.begin(); iter != mtSet.end(); iter+)map<int, float>:iterator curIter = NodeSet(*iter).neighNodes.begin();while (curIter != NodeSet(*iter).neighNodes.end()/ 當(dāng)前節(jié)點已經(jīng)在集合中if ( mtSet.end() !=

41、 ( mtSet.find( (*curIter).first ) ) )curIter+;continue;/ 當(dāng)前節(jié)點不在集合中，記錄該節(jié)點并作為備選節(jié)點if (*curIter).second < weight) / 選擇權(quán)重最小的邊所邊接的節(jié)點s1 = (*iter);start = (*curIter).first;weight = (*curIter).second;curIter+;if (-1 != start)/ 從備選邊與節(jié)點參加到最小生成樹中mtSet.insert(start);cout << "(" << s1 << ", " << start << ") " << endl;if (mtSet.size() = NodeSet.size()break;void CMyGraph:Kruskal()/ 對所有邊進行排序EdgeSet es;for (int i = 0; i < NodeSet.size(); i+)for (map<int, float>:iterator it