计算机软件技术基础报告.doc

《计算机软件技术基础报告.doc》由会员分享，可在线阅读，更多相关《计算机软件技术基础报告.doc（17页珍藏版）》请在三一文库上搜索。

1、实验四_线性表_一、 实验目的：a) 掌握二叉树的逻辑结构；b) 掌握二叉树的二叉链表的存储结构；c) 掌握二叉树的二叉链表的存储的二叉树的遍历操作的实现二、 实验内容及测试结果：a) 建立一棵含有n个结点的二叉树，采用二叉链表存储；b) 前序（或中序、后序）遍历该二叉树。三、 算法或核心技术思考体会：前：根左右中：左根右后：左右根四、附件（源代码）（可选）/定义类中的成员函数，文件名为bitree.cpp#include#include#includebitree.husing namespace std;/* *前置条件：二叉树不存在 *输 入：无 *功 能：构造一棵二叉树 *输 出：无

2、*后置条件：产生一棵二叉树 */templateBiTree:BiTree( )this-root = Creat( );/* *前置条件：二叉树已存在 *输 入：无 *功 能：释放二叉链表中各结点的存储空间 *输 出：无 *后置条件：二叉树不存在 */templateBiTree:BiTree(void)Release(root);/* *前置条件：二叉树已存在 *输 入：无 *功 能：获取指向二叉树根结点的指针 *输 出：指向二叉树根结点的指针 *后置条件：二叉树不变 */templateBiNode* BiTree:Getroot( )return root;/* *前置条件：二叉树已存

3、在 *输 入：无 *功 能：前序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */templatevoid BiTree:PreOrder(BiNode *root)if(root=NULL) return;elsecoutdatalchild);PreOrder(root-rchild);/* *前置条件：二叉树已存在 *输 入：无 *功 能：中序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template void BiTree:InOrder (BiNode *root) if (root=NULL) return; /递归调

4、用的结束条件 else InOrder(root-lchild); /中序递归遍历root的左子树 coutdatarchild); /中序递归遍历root的右子树/* *前置条件：二叉树已存在 *输 入：无 *功 能：后序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template void BiTree:PostOrder(BiNode *root) if (root=NULL) return; /递归调用的结束条件 else PostOrder(root-lchild); /后序递归遍历root的左子树 PostOrder(root-rchild); /

5、后序递归遍历root的右子树 coutdata ; /访问根结点的数据域/* *前置条件：二叉树已存在 *输 入：无 *功 能：层序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template void BiTree:LeverOrder(BiNode *root)const int MaxSize = 100;int front = 0;int rear = 0; /采用顺序队列，并假定不会发生上溢BiNode* QMaxSize; BiNode* q;if (root=NULL) return;elseQrear+ = root;while (front

6、!= rear)q = Qfront+; coutdatalchild != NULL) Qrear+ = q-lchild;if (q-rchild != NULL) Qrear+ = q-rchild;/* *前置条件：空二叉树 *输 入：数据ch; *功 能：初始化一棵二叉树,构造函数调用 *输 出：无 *后置条件：产生一棵二叉树 */template BiNode* BiTree:Creat( )BiNode* root;T ch;cout请输入创建一棵二叉树的结点数据ch; if (ch=#) root = NULL; else root = new BiNode; /生成一个结点

7、root-data=ch; root-lchild = Creat( ); /递归建立左子树 root-rchild = Creat( ); /递归建立右子树 return root;/* *前置条件：二叉树已经存在 *输 入：无 *功 能：释放二叉树的存储空间，析构函数调用 *输 出：无 *后置条件：二叉树不存在 */templatevoid BiTree:Release(BiNode* root) if (root != NULL) Release(root-lchild); /释放左子树 Release(root-rchild); /释放右子树 delete root; 实验五 图的实验

8、一、 实验目的： 练习一 邻接表操作验证1 实验目的：a) 掌握图的逻辑结构；b) 掌握图的邻接表的存储结构；c) 掌握图的邻接表存储结构下的遍历算法的实现2 实验内容a) 建立一个有向图的邻接表存储结构；b) 对建立的有向图，进行深度优先遍历；c) 对建立的有向图，进行广度优先遍历。二、实验内容及测试结果：练习一template ALGraph:ALGraph(T a , int n, int e) arcNum = e; /边数vertexNum=n; /顶点数 int i,j;for (i=0; ivertexNum; i+) VertexNode tempvertex; tempver

9、tex.vertex = ai; tempvertex.firstedge = NULL; adjlisti = tempvertex;for (int k=0; karcNum; k+) /依次输入每一条边，并在相应边表中插入结点 coutij; /输入边所依附的两个顶点的序号 ArcNode *s=new ArcNode; s-adjvex=j; /生成一个边表结点s s-next=adjlisti.firstedge; /将结点s插入到结点i的边表的表头 adjlisti.firstedge=s;InsertArc(0,1); /插入边InsertArc(0,2);InsertArc(0

10、,3);InsertArc(1,3);InsertArc(1,4);InsertArc(2,0);InsertArc(2,4);InsertArc(3,1);InsertArc(3,4);InsertArc(4,2);InsertArc(4,3);/* 前置条件：图已存在 * 输 入：无 * 功 能：销毁图 * 输 出：无 * 后置条件：释放图所占用的存储空间 */template ALGraph:ALGraph( ) for (int i=0; inext; delete p; /释放结点空间 p=adjlisti.firstedge; /* *前置条件：图已存在 *输 入：顶点i *功 能

11、：输出图中顶点i的数据信息 *输 出：图中顶点i的数据信息 *后置条件：图保持不变 */template T ALGraph:GetVex(int i)if ( ivertexNum | i0 ) throw 输入顶点的位置不正确; /顶点i不存在则抛出异常return adjlisti.vertex; /返回第i个顶点的数据域 /* *前置条件：图已存在 *输 入：顶点i *功 能：将图中顶点i的数据域置为value *输 出：无 *后置条件：图保持不变 */运行结果如下：二、 算法或核心技术思考体会：基本掌握图的邻接表的存储结构和图的逻辑结构，图的邻接表存储结构下的遍历算法的实现四、附件（

12、源代码）（可选）实验六 _顺序查找 练习一顺序查找验证1 实验目的：a) 掌握顺序查找算法的基本思想；b) 掌握顺序查找算法的实现方法；c) 掌握顺序查找算法的时间性能。2 实验内容a) 对给定的数组（假设长度为n），查找数组中与定值k相等的元素。实验结果：设置哨兵的代码如下：int SeqSearch1(int r, int n, int k) r0=k ; /设置哨兵 int i=n,count=0;while (ri!=k) /若ri与k相等，则返回当前i的值;否则继续比较前一个记录;i-; count+; coutn比较的次数为countendl;return i;这里实现一种改进的顺

13、序查找算法，即将待查值放在查找方向的“尽头”处，起哨兵作用，这样，就免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。练习二、折半查找验证1实验目的：b) 掌握折半查找算法的基本思想；c) 掌握折半查找算法的实现方法；d) 掌握折半查找算法的时间性能。2实验内容对给定的有序数组（假设长度为n），查找数组中与定值k相等的元素。实验结果： 设置折半查找的源代码：int BinSearch1(int r , int n, int k)int low=0, high=n,count=0; /设置初始查找区间while (low=high) int mid=(low+high)/

14、2; /取中间点, 比较k与rmid， if (krmid)low=mid+1; if(k=rmid)count+;cout比较次数为:countendl; /查找成功 return mid;count+;cout比较次数为:countendl; return 0;/查找失败练习三、二叉排序树的建立1实验目的：a)掌握二叉排序树定义和特性；b)掌握二叉排序树的建立方法；c)实现基于二叉排序树的查找技术；d)掌握二叉排序树的查找性能。2实验内容a)对给定的一组无序序列，建立一棵二叉排序树；b)对建立的二叉排序树实现查找操作。三、算法或核心技术思考体会：基本掌握了二叉排序树的建立方法，实验中还是存

15、在一些问题，对顺序查找算法的基本思想； 算法的时间性能的了解还是比较少的。四、附件（源代码）（可选）实验七_排序_一、 实验目的：练习一 直接插入排序验证1 实验目的：a) 掌握直接插入排序的基本思想；b) 掌握直接插入排序的实现方法；c) 验证直接插入排序的时间性能。2 实验内容对一组数据进行直接插入排序（按升序排列）。练习二、起泡排序算法验证1 实验目的：a) 掌握起泡排序算法的基本思想；b) 掌握起泡排序算法的实现方法；c) 验证起泡排序算法的时间性能。2 实验内容对一组数据进行起泡排序算法（按升序排列）。练习三、简单选择排序算法验证1 实验目的：a) 掌握简单选择排序算法的基本思想；b

16、) 掌握简单选择排序算法的实现方法；c) 验证简单选择排序算法的时间性能。2 实验内容a) 对一组数据进行简单选择排序算法（按升序排列）。二、 实验内容及测试结果：三、 算法或核心技术思考体会：直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到一个已排序好的序列中，直到全部记录都排好序。简单选择排序算法的基本思想是：第i趟排序通过n-1次关键码的比较，在n-i+1(1=i=n-1)个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。四、附件（源代码）（可选）练习一算法如下：/直接顺序排序void InsertSort(int r, int n)count1 =

17、 0 ; count2 = 0 ; for (int i=2; in; i+) r0=ri; /设置哨兵 for (int j=i-1; +count1 & r0rj; j-) /寻找插入位置 rj+1=rj; /记录后移 rj+1=r0; count2+; rj+1 = r0; cout 比较次数为： count1 endl ; cout ”移动次数为：” count2 + 2 endl ;练习二算法如下；void BubbleSort(int r, int n)count1 = 0 ; count2 = 0 ;int temp;int exchange;int bound; exchang

18、e=n-1; /第一趟起泡排序的范围是r0到rn-1while (exchange) /仅当上一趟排序有记录交换才进行本趟排序bound=exchange; exchange=0; for (int j=0; jrj+1) temp=rj; rj=rj+1; rj+1=temp; count2 += 3 ; /一次交换需要三个赋值语句 exchange=j; /记录每一次发生记录交换的位置 cout 比较次数为： count1 endl ; cout ”移动次数为：” count2 + 2 endl ; 练习三的算法如下：void SelectSort(int r , int n) int i;int j;int index;int temp;count1 = 0 ; count2 = 0 ; for (i=0; in-1; i+) /对n个记录进行n-1趟简单选择排序 index=i; for (j=i+1; jn; j+) /在无序区中选取最小记录 if ( +count1 & rjrindex) index=j; if (index!=i) temp=ri; ri=rindex; rindex=temp; count2 += 3 ; /一次交换需要三个赋值语句 cout 比较次数为： count1 endl ; cout ”移动次数为：” count2 + 2 endl ;