实验课程设计指导书

1、数据结构与测绘开发实验指导书矿业大学测绘与国土2014-05-20中心实验一 线性表类的设计与实现一、实验要求利用 C+语言编程分别实现线性表的顺序与链式。二、实验基本操作1、新建工程1）执行菜单：文件新建项目，选择“Win32台应用程序”；2）更改工程路径；3） 更改工程名称；4） 点击“确定”。2、添加头文件与类的1）头文件在#include “stdafx.h”之后加入如下语句： #include <iostream>using namespace std;2）顺序表在 main 函数前加入如下类的class SeqList：public:/ 构造、析构函数SeqList()

2、;explicit SeqList(int maxSize); / 仅包含一个参数的构造函数SeqList( );public:/构造函数、赋值运算SeqList(const SeqList& sl);SeqList& operator=(const SeqList& sl);public:/ 成员函数int Length( ) const;int Find(int& x) const; int Locate(int i) const; int Insert(int& x, int i ); int Remove(int& x ); int Ne

3、xt(int& x ) ;int Prior(int& x ) ;int IsEmpty( );/查找定位删除后继/ 前驱int IsFull ( ); int Get (int i);public:/ 提取friend ostream& operator<<(ostream& os, SeqList& sl)for (int i = 0; i < sl.Length(); i+) os << sl.Get(i) << " "return os;private: / 成员变量int * _da

4、ta; int _curSize; int _maxSize;3）链表在 main 函数前加入如下类的typedef int Type;：typedef struct ListNode intdata;/ 数据域struct ListNode struct ListNode LNode;class LinkedList*prior;*next;/ 指针域/ 指针域public: / 构造、析构函数LinkedList();explicit LinkedList(int MaxSize);LinkedList() public:/构造函数、赋值运算LinkedList(const LinkedL

5、ist& sl); LinkedList& operator=(const LinkedList& sl);public:/ 成员函数int Length() const;int Search(Type& x) const; int Insert(Type& x, int i); int Remove(Type& x);void Sort();/查找删除排序int IsEmpty(); void SetNull(); Type Get(int i); void Output();private: / 成员变量ListNode *head; int

6、 _size;/链表是否为空置空提取输出3、添加类的实现代码（顺序表）在各自类的之后，添加如下代码：1）顺序表的函数/ 构造函数SeqList:SeqList(): _data(NULL), _maxSize(0), _curSize(0)SeqList:SeqList(int maxSize): _maxSize(maxSize), _curSize(0)_data = new int_maxSize;/ 开辟用于线性表的空间（连续空间）/ 析构函数SeqList:SeqList()if (NULL != _data) delete _data;/ 取得线性表的长度int SeqList:L

7、ength() constreturn _curSize;/ 在线性表中定位 x 所在位置int SeqList:Find(int& x) constfor (int i = 0; i < _curSize; +i) if (x = _datai)return i;return -1;/元素 xint SeqList:Insert(int& x, int i)/下标是否越界if (i < 0 | i >= _maxSize)return -1;/线性表是否已满if (_curSize = _maxSize)return -1;/的位置是否位于_curSize

8、之后if (i < _maxSize - 1) && i >= _curSize)_data_curSize = x;_curSize+; / 线性表的长度加 1return 1;/ 首先将位于位置 i 之后的所有元素后移一个位置for (int j = _curSize; j > i; j-)_dataj = _dataj - 1;_datai = x;_curSize+;/ 将待元素i 位置/ 线性表的长度加 1return 1;/ 删除元素 xint SeqList:Remove(int & x)for (int i = 0; i < _c

9、urSize; 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(int & x)for (int i = 0; i < _curSize; i+)if (_datai = x)return i + 1; / 调用此函数的过程需要检查返回的值是否越界/ 取得 x 所在位置的前一个位置int SeqList:Prior(in

10、t & x)for (int i = 0; i < _curSize; i+)if (_datai = x)return i - 1;/调用此函数的过程需要检查返回的值是否越界/线性表是否为空int SeqList:IsEmpty()if (_curSize <= 0) return 1;elsereturn 0;/线性表是否已经满int SeqList:IsFull()if (_curSize = _maxSize) return 1;elsereturn 0;/ 取得 i 位置的元素Type SeqList:Get(int i)return _datai;2）顺序表的两

11、个重要应用/ 集合的交与并/void Join(SeqList& A, SeqList& B, SeqList& R)/ 首先遍历 Afor (int i = 0; i < A.Length(); +i)int x = A.Get(i);/ 取得 i 位置的元素if (B.Find(x) != -1) / 在 B 中寻找同样的元素，若不，则返回-1R.Insert(x, R.Length();void Merge(SeqList<int>& A, SeqList<int>& B)for (int i = 0; i <

12、B.Length(); +i)int x = B.Get(i);if (A.Find(x) = -1)A.Insert(x, A.Length();3）main 函数的实现int main(int argc, char* argv)/ 实例化两个线性表SeqList A(20); SeqList B(20);/ 线性表 A 的数据初始化for (int i = 0; i < 10; i+) A.Insert(i, i);/ 线性表 B 的数据初始化for (int i = 5; i < 15; i+) B.Insert(i, i - 5);/ 输出 Acout << &

13、quot;A:" << endl;for (int i = 0; i < A.getCurSize(); i+) cout << A.Get(i) << " "cout << endl;/ 输出 Bcout << "B:" << endl;for (int i = 0; i < B.getCurSize(); i+) cout << B.Get(i) << " "cout << endl;/ 交运算SeqL

14、ist<int> R(20); Join(A, B, R);/ 交运算结果输出cout << "线性表 A 与 B 取交的结果：" << endl; for (int i = 0; i < R.getCurSize(); i+)cout << R.Get(i) << " "cout << endl;/ 并运算cout << "线性表 A 与 B 取并的结果：" << endl; Merge(A, B);/ 并运算结果输出for (in

15、t i = 0; i < A.getCurSize(); i+) cout << A.Get(i) << " "cout << endl;/函数调用cout << "模板输出结果：n" cout << A << endl;cout << B << endl;cout << R << endl;return 0;4、添加类的实现代码（链表）1）链表的实现函数/ 构造函数LinkedList:LinkedList(): _size(0

16、), head(NULL)LinkedList:LinkedList(int MaxSize): _size(MaxSize), head(NULL)int LinkedList:Length() constreturn _size;/ 返回元素 x 所在的位置，第一个节点序号为 1 int LinkedList:Search(Type& x) constif (NULL = head) return -1;int result = 1; ListNode *cur;cur = head;while (cur != NULL)if (cur->data = x) return r

17、esult;elsecur = cur->next; result+;return -1;int LinkedList:Insert(Type& x, int i)if (i <= 0) / 越界return -1;if (_size = 0)/结点操作ListNode *temLN = new ListNode(); temLN->data = x;temLN->next = NULL;head = temLN;_size+;return 1;else if (i > _size)/ 在链表尾部ListNode*cur = head; while (cu

18、r->next != NULL)cur = cur->next;/结点操作ListNode*temLN = new ListNode(); temLN->data = x;temLN->next = NULL;cur->next = temLN;_size+;return 1;ListNode*cur = head;for (int k = 1; k < i - 1; k+)cur = cur->next;/结点操作ListNode*temLN = new ListNode(); temLN->data = x;temLN->next =

19、cur->next;cur->next = temLN;_size+;return 1;int LinkedList:Remove(Type& x)ListNode * cur = head;if (cur->data = x) / 删除表头第一个元素head = cur->next; return 1;/ 删除除表头之外的其他位置元素while (cur->next != NULL)if (cur->next->data = x)/ 执行删除操作cur->next = cur->next->next;return 1;cur

20、 = cur->next;return 1;int LinkedList:IsEmpty()if (_size = 0 | head = NULL)return 1;return 0;void LinkedList:SetNull()_size = 0; head = NULL;Type LinkedList:Get(int i)if (i <= 0 | i > _size)cout << "下表越界！" << endl; return -1;ListNode* cur = head; for (int k = 1; k <i

21、; k+)cur = cur->next;return cur->data;void LinkedList:Output()ListNode * cur; cur = head;while (cur != NULL)cout << cur->data << " " cur = cur->next;cout << endl;2）main 函数的实现int main(int argc, char* argv)/ 建立一个包含 10 个结点的链表LinkedList myList;for (int i = 1; i &l

22、t;= 10; +i)myList.Insert(i, i);/ 遍历myList.Output();/ 删除第 5 个元素int x = 5; myList.Remove(x);/ 遍历myList.Output();/ 在第 5 个元素位置处x = 50;myList.Insert(x, 5);一个 50/ 遍历myList.Output();return 0;实验二 二叉树的构建与遍历一、实验要求利用 C+语言编程实现二叉树的构建及其先序、中序、后序遍历算法.二、实验基本操作1、新建工程1）执行菜单：文件新建项目，选择“Win32台应用程序”；2）更改工程路径；3） 更改工程名称；4）

23、点击“确定”。2、添加头文件与类的1）头文件在#include “stdafx.h”之后加入如下语句： #include <iostream>#include <vector>using namespace std;2）类的在 main 函数前加入如下类的typedef struct BTNodeint data;BTNode *lChild; BTNode *rChild; SBTNode;：class CBinTreepublic:/ 构造、析构函数CBinTree();CBinTree();/ 构造二叉排序树void createBSTree(vector<

24、int>& xArray);void insertNode(SBTNode*& temNode, BTNode*& root);/ 树的遍历void InOrder(BTNode*& root);void PreOrder(BTNode*& root); void PostOrder(BTNode*& root);/中序遍历先序遍历后序遍历public:BTNode* root; vector<int> xArray;3、添加类的实现代码1）二叉树的实现函数/ 构造函数CBinTree:CBinTree(): root(NULL

25、)/ 析构函数CBinTree:CBinTree()xArray.clear();/ 构造一颗二叉排序树void CBinTree:createBSTree(vector<int>& xArray)for (vector<int>:iterator iter = xArray.begin(); iter != xArray.end(); +iter)BTNode *temNode = new BTNode; temNode->data = *iter;temNode->lChild = NULL;temNode->rChild = NULL;i

26、nsertNode(temNode, root);/ 构造二叉排序树的节点子过程void CBinTree:insertNode(SBTNode*& temNode, BTNode*& root)if (root = NULL) root = temNode; elseif (temNode->data > root->data) insertNode(temNode, root->rChild);elseinsertNode(temNode, root->lChild);/ 二叉树的中序遍历void CBinTree:InOrder(BTNode

27、*& root)if (root = NULL) return;InOrder(root->lChild); cout << root->data << " "InOrder(root->rChild);/ 二叉树的先序遍历void CBinTree:PreOrder(BTNode*& root)if (root = NULL) return;cout << root->data << " "PreOrder(root->lChild); PreOrder(ro

28、ot->rChild);/ 二叉树的后续遍历void CBinTree:PostOrder(BTNode*& root)if (root = NULL) return;PostOrder(root->lChild); PostOrder(root->rChild);cout << root->data << " "2）main 函数的实现int main(int argc, char* argv)/ 构造一棵二叉排序树vector<int> xArray; xArray.push_back(10); xAr

29、ray.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.InOrder(BT.root); cout << endl;/ 先序遍历BT.PreOrder(BT.root); cout << endl;/ 后序遍历BT.PostOrder(BT

30、.root);cout << endl;return 0;实验三 图的创建、遍历及其 MST 的构建一、实验要求利用 C+语言编程实现二叉树的构建及其先序、中序、后序遍历算法.二、实验内容1） 图的创建2） 基于深度优先的图的遍历算法的设计与实现3） 基于广度优先的图的遍历算法的设计与实现4） 基于 Prim 算法的最小生成树的构建5） 基于 Kruskal 算法的最小生成树的构建三、实验基本操作1、新建工程1）执行菜单：文件新建项目，选择“Win32台应用程序”；2）更改工程路径；3） 更改工程名称；4） 点击“确定”。2、添加头文件与类的1）头文件在#include “stda

31、fx.h”之后加入如下语句： #include <vector>#include <map> #include <deque> #include <iostream>using namespace std;2）类的在 main 函数前加入如下类的：/ 用于图的节点及其相邻节点的结构体变量类型struct SGNode int key; / 结点自身标识map<int, float> neighNodes;/ 与当前结点相邻的结点集合，及其与相邻结点之间路径的;/ 用于边的结构体变量类型struct SGEdge int start;i

32、nt end;/ 用于边及其权重的 map 容器（注意：会按照权重自小而大自动排序）typedef map<float, SGEdge> EdgeSet;class CMyGraphpublic:CMyGraph(void);CMyGraph(void);public: / 其他函数，供实例调用void DFS();void DFS(int i, vector<int>& mystack, bool* visited); void BFS();void BFS(int i, deque<int>& mydeque, bool* visited

33、); void Prim();void Kruskal(); protected: / 属性变量/* 自行设计完成 */private: / 成员变量vector<SGNode> NodeSet;3、添加类的实现代码CMyGraph:CMyGraph(void)float g88 =0, 12,12, 0,1,0,0,9,2,0,0,0,11,9,0,0,0,8,0,0,2,0,0,0,5,0,10,0,0,0,0,7,0,0,0,8,5,7,0,4,0,0,0,3,6,0,1,0,0,0,0,0,11,0,10,0,4, 0,;0,0,3,6,0,0for (int i = 0;

34、 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<int, float>:value_type(j, gij);vector<SGNode>:iterator iter;for (iter = NodeSet.begin(); iter != NodeSet.end(); iter+)cout <&

35、lt; (*iter).key;map<int, float>:iterator iter2;for (iter2 = (*iter).neighNodes.begin(); iter2 != (*iter).neighNodes.end(); iter2+)cout << ", (" << (*iter2).first << ", " << (*iter2).second << ")"cout << endl;CMyGraph:CMyGraph(vo

36、id)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 CMyGraph:DFS(int i, vector<int>& mystack, bool * visited)if (i >= 0 && i < NodeSet.size()if (!visitedi)cout <&l

37、t; i << "n" mystack.push_back(i); visitedi = true;map<int, float>:iterator iter;for (iter = NodeSeti.neighNodes.begin(); iter != NodeSeti.neighNodes.end(); iter+)if (!visited(*iter).first) DFS(*iter).first, mystack, visited);if (iter = NodeSeti.neighNodes.end()if (mystack.size(

38、) > 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 (int i = 0; i < 8; i+) visitedi = false; deque<int> mydeque;BFS(0, mydeque, visited);void CMyGraph:BFS(int i, deque<int&g

39、t;& mydeque, bool* visited)if (!visitedi)cout << i << "n"for (map<int, float>:iterator iter = NodeSeti.neighNodes.begin(); iter != NodeSeti.neighNodes.end(); iter+)if (!visited(*iter).first) mydeque.push_back(*iter).first);visitedi = true;while (mydeque.size() > 0)

40、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);/ 选择初始节点float weight; while (1)weight = 100000.0f; start = -1;s1 = -1;/ 人为设定较大值for (set<int>:iterator iter = mtSet.begin(); ite

41、r != mtSet.end(); iter+)map<int, float>:iterator curIter = NodeSet(*iter).neighNodes.begin(); while (curIter != NodeSet(*iter).neighNodes.end()/ 当前节点已经在集合中if ( mtSet.end() != ( mtSet.find( (*curIter).first ) ) )curIter+; continue;/ 当前节点不在集合中，该节点并作为备选节点if (*curIter).second < weight) / 选择权重最小

42、的s1 = (*iter);start = (*curIter).first; weight = (*curIter).second;边接的节点curIter+;if (-1 != start)/ 从备选边与节点加入到最小生成mtSet.insert(start);cout << "(" << s1 << ", " << start << ") " << endl;if (mtSet.size() = NodeSet.size()break;void CMyGra

43、ph:Kruskal()/ 对所有EdgeSet es;排序for (int i = 0; i < NodeSet.size(); i+)for (map<int, float>:iterator iter = NodeSeti.neighNodes.begin(); iter != NodeSeti.neighNodes.end(); iter+)if (*iter).second != 0.0f)SGEdge sg; sg.start = i;sg.end = (*iter).first; es.insert(EdgeSet:value_type( (*iter).sec

44、ond, sg);set<int> mtSet;/ 依次加入权重最小的边（数目：顶点数1）EdgeSet:iterator iter = es.begin(); for (int i = 0; i < NodeSet.size() - 1;)/ 初始最小生成空的情况if (mtSet.size() = 0)cout << "(" << (*iter).second.start; cout << ", "cout << (*iter).second.end << ")&

45、quot; << endl;mtSet.insert(*iter).second.start); mtSet.insert(*iter).second.end); iter+;i+;continue;/ 待加入边的两个端点位于两个不同的子图中if (mtSet.find(*iter).second.start) = mtSet.end() && mtSet.find(*iter).second.end) != mtSet.end() |(mtSet.find(*iter).second.start) != mtSet.end() && mtSet.f

46、ind(*iter).second.end)= mtSet.end()cout << "(" << (*iter).second.start; cout << ", "cout << (*iter).second.end << ")" << endl;mtSet.insert(*iter).second.start); mtSet.insert(*iter).second.end); iter+;i+;elseiter+;4、添加 main 函数的实现代码在 ma

47、in 函数中加入如下实现代码：int _tmain(int argc, _TCHAR* argv)CMyGraph mg;cout << "Depth first scanning:" << endl;mg.DFS();cout << "Bmg.BFS();th first scanning:" << endl;cout << "Prim:n"mg.Prim();cout << "Kruskal:n"mg.Kruskal();return 0;

48、实验四 矩阵类的设计与实现一、实验要求利用 C+语言编程实现矩阵相关操作的实现代码。二、实验基本操作1、新建工程1）执行菜单：文件新建项目，选择“Win32台应用程序”；2）更改工程路径；3） 更改工程名称；4） 点击“确定”。2、添加头文件与类的1）添加类执行：项目添加类，在弹出的框中，输入类的名称：CMatrix;2）添加头文件从属性页 File View 中找到 matrix.h 文件，双击打开，并添加如下#include <iostream> #include <string> #include <cassert> using namespace s

49、td;头文件：3）添加如下矩阵类的class CMatrixpublic:/ 默认构造函数CMatrix(void);/ 构造函数一CMatrix(int row, int column);/构造函数CMatrix(const CMatrix& m);public:/ 默认析构函数CMatrix(void);public:/ 运算符/ 赋值运算符CMatrix& operator=(const CMatrix& m);/ 比较运算符bool operator=(const CMatrix& m); bool operator!=(const CMatrix&am

50、p; m);/ 加/减运算符CMatrix operator+(const CMatrix& m); CMatrix operator-(const CMatrix& m);/ 自加/减运算符CMatrix& operator+=(const CMatrix& m); CMatrix& operator-=(const CMatrix& m);/ 下标运算符重载double*& operator(int row)assert(row < _row);return _Arow;/ 单目运算符CMatrix operator-(); /

51、 取负数/ 乘法运算符CMatrix operator*(const CMatrix& m); CMatrix operator*(const double& s);friend std:ostream& operator<<(std:ostream& os, CMatrix& m)for (int i = 0; i < m.getRow(); +i)for (int j = 0; j < m.getColumn(); +j)if (j = 0)os << m.getValue(i, j);elseos <<

52、; "" << m.getValue(i, j);os << endl;return os;public:/ 属性变量/ 设置(i,j)的值void setValue(int row, int column, double value) _Arowcolumn = value; double getValue(int row, int column) const return _Arowcolumn; / 设置行、列的值void setRow(const int row) _row = row; int getRow() const return _

53、row; void setColunm(const int column) _column = column; int getColumn() const return _column; / 设置阵bool setUnitMatrix();public:/ 矩阵转置CMatrix transpose();/ 矩阵求逆CMatrix inverse();/列主元素法private: / 成员变量double* _A;int _row;int _column;/ 行/ 列;3、添加类的实现代码从属性页 File View 中找到 matrix.cpp 文件，双击打开，并添加如下实现代码：/ 默认构

54、造函数CMatrix:CMatrix(void): _A(NULL), _row(-1), _column(-1)/ 构造函数一CMatrix:CMatrix(int row, int column)_row = row;_column = column;_A = new double *row; for (int i = 0; i < row; i+)_Ai = new doublecolumn;/ Initializefor (int i = 0; i < row; i+)for (int j = 0; j < column; j+)_Aij = 0.0f;/构造函数CM

55、atrix:CMatrix(const CMatrix& m)_row = m._row;_column = m._column;_A = new double *_row; for (int i = 0; i < _row; i+)_Ai = new double_column;for (int i = 0; i < _row; i+)for (int j = 0; j < _column; j+)_Aij = m._Aij;/ 默认析构函数CMatrix:CMatrix(void)if (NULL != _A)for (int i = 0; i < _row; i+) delete _Ai;/if (NULL != _A)delete _A;/ 赋值运算符CMatrix& CMatrix:operator=(const CMatrix&am