软件技术基础实验教学大纲.docx

《软件技术基础实验教学大纲.docx》由会员分享，可在线阅读，更多相关《软件技术基础实验教学大纲.docx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件技术基础实验教学大纲目录一、课程简介2二、课程实验教学的目的、任务与要求2三、实验方式与基本要求2四、实验项目设置2五、教材（讲义、指导书）3六、实验报告要求3七、考试（考核）方式3八、使用说明3软件技术基础课程实验项目14软件技术基础课程实验项目28软件技术基础课程实验项目313软件技术基础课程实验项目421/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= int TrecDcpth(BinTree T)(int hl, hr, max;if(T)(hl=TreeDepth(T-lchi Id);求左深度hr=TreeDepth(T-rchild);求右深度max=hlhr?

2、hl :hr;取左右深度的最大值NodeNum=NodeNum+1;求结点数if(hl=O&hr=O) leaf=leaf+l; 若左右深度为 0,即为叶子。 return (max+1);)else return(0);)=利用先进先出(FIFO)队列，按层次遍历二叉树=void Leve1 order (Bi nTree T)(int front=0, rear=l;BinTNodc *cqMax, *p;定义结点的指针数组cqcq 1 =T;根入队while(front!=rear)(front=(front+l)%NodeNum;p=cqfront;出队printf (c, p-dat

3、a);出队，输出结点的值if(p-lchild!=NULL)rear二(rear+l)%NodeNum;cq rear=p-lchi Id;左子树入队)if(p-rchild!=NULL)rear=(rear+1)%NodeNum;cq rear =p-rch i 1 d;右子树入队)/=主 函 = void main()IBinTrce root;int i,depth;printf(n)；printf (z，Creat Bin_Tree； Input preorderO ; 输入完全二叉树的先序序列,/用#代表虚结点，如root=CreatBinTree();创建二叉树，返回根结点do 从

4、菜单中选择遍历方式，输入序号。printf (z,t* select *n);printf (Ati: Preorder Traversaln);printf (z/t2: lorder Traversaln，?);printf(t3: Postorder traversalXn);printf (l4: PostTreeDepth, Node number, Leaf numbern，z);printfCt5: Level Depthn)； 按层次遍历之前，先选择4,求出该树的结点数。 printf (，?t0: Exitn);printf(t*n);scant&i）; 输入菜单序号（0-5

5、）switch (i)printf (Print Bin tree Preorder:);Preorder (root);先序遍历break;case 1: printf (Print Bin Tree Inorder:);Inorder (root);/中序遍历break;printf (Print Bin_Tree Postorder:);Postordcr (root);后序遍历break;case 2: depth=TreeDepth(root);求树的深度及叶子数printf CBinTrce Dcpth=%d BinTree Node number=%d，, depth, Node

6、Num);printf (，z BinTree Leaf number=%dw, leaf); break;printf(TevePrint Bin_Tree:);Levelorder (root);按层次遍历break;default: exit(1);)printf(n);)while(i!=0);)七、实验要求1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如 ABD#CE#F#,建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子 及结点总数。八、场地、设备与器材计算机实验室，VC+6. 0软件技术基础课程实验项目3一、实

7、验项目名称及实验项目编号图的遍历操作，05612503二、课程名称及课程编号软件技术基础，056125三、实验目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构：掌握DFS及BFS对 图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用四、实验原理DFS和BFS的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo,然后选择一个 与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj 访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问 的顶点序列中最后个拥有未被访问的相邻顶点的顶点

8、W,从W出发按同样方法向前遍历。直到 图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点V。出发，首先访问V。，然后访问与Vo 相邻的所有未被访问过的顶点VI, V2,，Vt；再依次访问与VI, V2,，Vt相邻的起且 未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。五、实验内容1、分析、理解程序。2、调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS （深度优先遍历）和BFS （广度优先遍历）的操作。六、实验方法与步骤1 .邻接矩阵作为存储结构的程序示例#includestdio. httincludestdlib. hSdof

9、inc MaxVertcxNum 100定义最大顶点数typedef structchar vexsMaxVertexNum;顶点表int edgesMaxVertexNum MaxVertexNum; 邻接矩阵，可看作边表int n,e;图中的顶点数n和边数e MGraph;用邻接矩阵表示的图的类型=建立邻接矩阵=void GreatMGreiph (MGraph *G)int i, j, k; char a; printf(Input VertexNum(n) and EdgesNum(e):); scanf (飞d,%d”,&G-n,&G-e);输入顶点数和边数scanf&a); pri

10、ntf (Input Vertex string/); for(i=0;in;i+) ( scanf (?，%c，z, &a); G-vexsi=a;读入顶点信息，建立顶点表 for (i=0;in;i+) for(j=0;jn;j+) G-cdgcsi j=0;初始化邻接矩阵printf(，/1 nput edges, Creat Adjacency Matrix%); for(k=0;ke;k+) /读入e条边，建立邻接矩阵scanf(d%d,&i,&j);/输入边(Vi, Vj)的顶点序号G-edgesij=l;G-edgesji=l; 若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条

11、语句 ) =定义标志向量，为全局变量=二= typedef enumFALSE, TRUE Boolean; Boolean visi tedMaxVertexNuml;=DFS ：深度优先遍历的递归算法= void DFSM(MGraph *G, int i) 以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0, 1矩阵 int j; printf (c, G-vexsi);访问顶点 Vivisited i=TRUE;置己访问标志for(j=0;jn;j+)依次搜索Vi的邻接点if(G-edgesij=l & ! visitedj)DFSM(G, j):void DFS(MGra

12、ph *G)(int i;for(i=0;in;i+) visitedi=FAl.SE;for(i=0;in;i+) if(!visitedi)DFSM(G, i);/ (Vi, Vj) GE,且Vj未访问过，故Vj为新出发点/标志向量初始化/Vi未访问过以Vi为源点开始DFS搜索/=BFS：广度优先遍历= void BFS(MGraph *G,int k)/以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索定义队列标志向量初始化/队列初始化访问源点Vkint i,j, f=0, r=0;int cqMaxVertcxNum;for(i=0;in:i+)visitedi=FALSE;for(i

13、=0;in;i+)cqi=l；printf(%c, G-vexsk); visitedk=TRUE;cqr=k;/Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf !=-1) 队非空则执行i=cqf; f=f+l;Vf 出队for(j=0;jn;j+)依次 Vi 的邻接点 Vjif (G-edgesi j=l & !visitedj) Vj 未访问printf G-vexsj);访问 Vjvisitedj=TRUE;r=r+l; cqr=j;访问过 Vj 入队)/=ma i n=:void main()int i;MGraph *G;G= (MGraph *)malloc(s

14、izeof (MGraph); 为图 G 申请内存空间CrcatMGraph(G);CrcatMGraph(G);建立邻接矩阵prinlf(Print Graphprinlf(Print GraphDFS: )；DFS(G);深度优先遍历printf(*Print GraphBFS(G,3);BFS(G,3);以序号为3的顶点开始广度优先遍历printf(，znw);执行顺序:InputVertexNum(n) and EdgesNum(e): 8, 9InputVertex string: 01234567Inputedges, Great Adjacency MatrixvoPrintGr

15、aph DFS: 01374256PrintGraph BFS: 317042562 .邻接链表作为存储结构程序示例Sincludcstdio. h #includesldlib. h#define MaxVertexNum 50定义最大顶点数typedef stiuct node 边表结点int adjvex;邻接点域struct node *next;链域(EdgeNode;typcdef struct vnode 顶点表结点char vertex;顶点域EdgeNode *firstedge;边表头指针VcrtcxNode;typedef VertexNode Adjl.islMaxVe

16、rtexNum;AdjLisl 是邻接表类型typedef struct (AdjList adj list;邻接表int n, e;图中当前顶点数和边数ALGraph;图类型=建立图的邻接表=void CreatALGraph(ALGraph *G) (int i, j, k;char a;EdgeNode *s;定义边表结点printf(Input VertexNum(n) and EdgesNum(e):);scanf (%d,&G-e);读入顶点数和边数scanf&a);printf(Input Vertex string:);for (i=0; in; i+)建立边表(scanf(“

17、/c, &a);G-adjlist i. ver tex =a;读入顶点信息G-adjlisti, firstedge=NULL; 边表置为空表 ) printf (Input edges, Creat Adjacency Listn);for (k=0; ke; k+) 建立边表scanf(线读入边(Vi, Vj)的顶点对序号s= (EdgeNode *)malloc(sizeof (EdgeNode);生成边表结点s-adjvex=j;邻接点序号为js-next=G-adjlisti. firstedgc;G-adj 1 ist i . f i rstedge=s;将新结点*S插入顶点Vi

18、的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode);s-adjvex=i;邻接点序号为is-next=G-adjlistjL firstedgo;G-adjlist j. firstedge=s;将新结点*S插入顶点Vj的边表头部)=定义标志向量，为全局变量=:typedef enumFALSE, TRUE Boolean;Boolean visi tedMaxVertexNum;/=DFS：深度优先遍历的递归算法= void DFSM(ALGraph *G, int i)以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode *p;prinlf (

19、为G-adjlisti. vertex);访问顶点 Vivisitedi=TRUE;标记 Vi 已访问p=G-adjlist i. first edge;取 Vi 边表的头指针whi le(p) 依次搜索Vi的邻接点Vj,这里j=p-adjvexif(! visitedp-adjvex)DFSM(G, p-adjvex);p=p-next;)void DFS(ALGraph *G) int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+) if(!visitedti)DFSM(G, i);若Vj尚未被访问/则以Vj为出发点向纵深搜索找Vi的下一个邻接点

20、标志向量初始化/Vi未访问过以Vi为源点开始DFS搜索/=BFS：广度优先遍历= void BFS(ALGraph *G, int k)以Vk为源点对用邻接链表表示的图G进行广度优先搜索int i, f=0, r=0;EdgeNode *p;int cqMaxVertcxNum;int cqMaxVertcxNum;定义FIFO队列for(i=0;in;i+)visitedi=FALSE;标志向量初始化for(i=0;in;i+)初始化标志向量printf G-adjlistk. vertex); 访问源点 Vkvisitedk=TRUE;cqr=k;Vk已访问，将其入队。注意，实际上是将其序

21、号入队while(cqf !=-1) 队列非空则执行 i=cqf; f=f+l;Vi 出队p=G-adj 1 ist i. f irstedge;取 Vi 的边表头指针while(p) 依次搜索Vi的邻接点Vj (令p-adjvex二j)if (! visitedp-adjvex) 若 Vj 未访问过printfG-adj 1 ist p-adjvex. vertex); 访问 Vjvisi tedp-adjvex=TRUE; r=r+l; cqr=p-adjvex;访问过的 Vj 入队 p=p-next;找Vi的下一个邻接点) )/enclwhile /= 函数=void main()ALG

22、raph *G;G= (ALGraph *)malloc(sizeof(ALGraph);CroatALGraph(G);printf(Print Graph DFS:);DFS(G);printf(n);printf(Print Graph BFS:);课程名称：软件技术基础课程编号：056125英文名称：Base of Softwarc Engineering课程性质：非独立设课课程属性：考查课应开实验学期：第3学期学时学分：课程总学时-64,其中实验学时-16；课程总学分-一4,其中实验学分一1。实验者类别：本科生适用专业：自动化、电气工程及其自动化、电子信息工程、电子信息科学与技术、电

23、子科学与技术、 通信工程、计算机等专业的学生。先修课程：C语言、C+、数据结构、微机原理等课程。一、课程简介软件技术基础实验课是一门非独立的实验课，是同学对软件技术基础理论内容进行充分的 理解的基础上，根据相应的原理，设计实验内容，完成实验任务，是理论知识实践化的方式，利于 学生更好的吸收，领悟软件技术基础的原理与应用，培养学生的动手实践的能力。二、课程实验教学的目的、任务与要求1、理解软件技术基础的基本概念2、掌握各种算法的流程，以及相应的优缺点。3、会使用相应的软件技术基础分类器等算法处理实验问题。三、实验方式与基本要求实验方式：学生12人一机，独立实验，配合课程，采用边学，注意记录实验数

24、据与结果分析。基本要求：每次实验课前，学生应预习实验讲义，明确实验目的和任务，拟定实验步骤，并认 真复习与实验内容相关的理论。实验过程中严格按实验规程操作。爱护实验仪器设备。实验完成后 要写出实验报告，其内容包括实验数据的整理和计算，对实验结果及实验中出现的问题的分析讨论， 对实验方法的建议等。实验后，按要求编写实验报告。四、实验项目设置序号实验编号实验项目名称实验内容提要实验时数实验类型实验 类别实验要求每组人数101单链表的插入和删除链表操作4验证必开2202二叉树操作二叉树操作4综合必开2308图的遍历操作掌握图的概念和应用4综合专业必开2BFS(G, 3);printf(*n*);执行

25、顺序:InputVertexNum(n) and EdgesNum(e): 8, 9InputInputVortex string: 01234567InputInputedges,Great Adjacency ListPrintPrintGraph DFS: 02651473PrintGraph BFS: 37140265七、实验要求1、画出DFS方法和BFS方法遍历图G的示意图。2、画出你所设计的图，写出两种方法的遍历序列。八、场地、设备与器材计算机实验室，VC+6.0软件技术基础课程实验项目4一、实验项目名称及实验项目编号排序，05612504二、课程名称及课程编号软件技术基础，056

26、125三、实验目的掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实 际问题的特点和要求选择合适的排序方法。四、实验原理实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。五、实验内容1、分析、理解程序。2、调试程序，以关键字序列(265, 301, 751, 129, 937, 863, 742, 694, 76, 438)作为输 入数据，采用上述方法进行排序。3、修改程序，使之能输出以上各种排序算法的各趟排序结束时，关键字序列的状态。六、实验方法与步骤#includestdio. h假设文件长度 定义记录类型 关键字项#includ

27、esldlib. h#define Max 100 typedcf stjuct (int key;RecType;typedcf RccTypc SeqList Max+1; SeqList为顺序表,表中第0个元素作为哨兵顺序表实际的长度1、直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的 子文件中的适当位置，直到全部记录插入完成为止。=直接插入排序法=:void InsertSort(SeqList R)对顺序表R中的记录R1 -n按递增序进行插入排序int i, j;for(i=2;i=n;i+) 依次插入 R，Rnif(Ri. keyRi-l. key

28、) 若Ri. key大于等于有序区中所有的keys,则留在原位R0是Ri的副本R0是Ri的副本的位置RO=Ri;j=i-l;do /从右向左在有序区RliT中查找RiRj+l=Rj； 将关键字大于Ri.koy的记录后移 J；while（R0. keyRj. key）; 当 Ri. key2Rj. key 是终止Rj+1=RO;Ri插入到正确的位置上/endif ）2、冒泡排序的基本思想：设想被排序的记录数组Rl-n垂直排序。根据轻气泡不能在重气泡之 下的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换）， 如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为

29、止。=冒 泡排序=typedef enum（FALSE, TRUE Boolean; /FALSE 为 0, TRUE 为 1void Bubb1 eSort（SeqList R）（自下向上扫描对R做冒泡排序int i, j;Boolean exchange;Boolean exchange;交换标志for(i=l;in;i+) for(i=l;i=i; j)对当前无序区Rirn自下向上扫描if(Rj+1. keyRj. key)两两比较，满足条件交换记录RO=Rj+l;R0不是哨兵，仅做暂存单元Rj+l=Rj;Rj=RO;exchange=TRUE;发生了交换，故将交换标志置为真if(! e

30、xchange)本趟排序未发生交换，提前终止算法return;/ endfor (为循环)）3、快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作 为支点（又称基准记录）（pivot）,将所有关键字比它小的记录放置在它的位置之前，将所有关 键字比它大的记录放置在它的位置之后（称之为一次划分过程）。之后对所分的两部分分别重复上 述过程，直到每部分只有一个记录为止。/I. =一次划分函数=:= int Partition(SeqList R, int i, int j) (/ 对做一次划分，并返回基准记录的位置RecType pivot=Ri;用第一个记录作为基准

31、while(ij) 从区间两端交替向中间扫描，直到i二jwhile(i=pivot. key)基准记录 pivot 相当与在位置 i 上j-；从右向左扫描，查找第一个关键字小于pivot, key的记录Rjif (ij) 若找到的 Rj. key pivot, key,则Ri+=Rj; /交换Ri和Rj,交换后i指针加1 while(ijkey=pivot. key) 基准记录 pivot 相当与在位置 j 上i+;从左向右扫描，查找第一个关键字小于pivot. key的记录Riif(i pivot, key,则 Rj-=Ri；交换R和Rj，交换后j指针减1 ) Ri=pivot;此时，i二j

32、,基准记录已被最后定位return i;返回基准记录的位置) /2.=二快速排序:= void Quicksort(SeqList R, int low, int high) Rlow. high快速排序int pivotpos;划分后基准记录的位置if(lowhigh) 仅当区间长度大于1时才排序pivotpos=Partition(R, low, high) ; /对 Rlow. high做一次划分，得到基准记录的位置 QuickSort(R, low, pivotpos-1); 对左区间递归排序 Quicksort (R, pivotpos+1, high);对右区间递归排序) 4、直接

33、选择排序的基本思想：第i趟排序开始时，当前有序区和无序区分别为和Ri n (IWiWnT),该趟排序则是从当前无序区中选择出关键字最小的记录Rk,将它与无序区 的的第一个记录Ri交换，有序区增加一个记录，使和Ri +，n分别为新的有序区 和新的无序区。如此反复进行，直到排序完毕。 =直接选择排序= void SclectSort(SeqList R)int i, j, k;for (i=l; in; i+) 做第 i 趟排序(lWiWnT)k=i;for(j=i+l; j=n; j+) /在当前无序区Rin中选key最小的记录Rkif(Rj. keyRk. key)k=j;/k记下目前找到的最

34、小关键字所在的位置if(k!=i) / 交换 Ri和 RkR0=Ri ;Ri=Rk;Rk=R0;)/endif /endfor)5、堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将Rl-n看成是一个 完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前 无序区中选择关键字最大(或最小)的记录。BP：把待排序文件的关键字存放在数组子 中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录Rl作为二叉树的 根，以下各记录R2-n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子 是R2i,右孩子是R2i+1,双亲是Ri/20对

35、这棵完全二叉树的结点进行调整，使各结点的关 键字满足下列条件：Ri.keyR2i. key 并且 Ri.keyR2i+l. key 称小堆根或 Ri.keyR2i.key 并且 Ri.keyR2i+l. key 称大堆根=大根堆调整函数=void Heapify(SeqList R, int low, int high) 将Rlow.high调整为大根堆，除Rlow外，其余结点均满足堆性质int large; large指向调整结点的左、右孩子结点中关键字较大者RecType temp=Rlow; 暂存调整结点for(large=2*low; largehigh,则表示Rlow是叶子,调整结束

36、:否则先令large指向Rlow的左孩子if(largehigh & Rlarge. key=R large. key) /temp 始终对应 Rlowbreak; 当前调整结点不小于其孩子结点的关键字，结束调整Rlow =Rlarge； 相当于交换了 Rlow和 Rlargelow二large； 令low指向新的调整结点，相当于temp已筛下到large的位置) Rlow=temp;/将被调整结点放入最终位置I：)=构造大根堆= void BuiIdHeap(SeqList R) 将初始文件RL.n构造为堆int i;for(i=n/2;i0;i一) Heapify (R, i, n); 将

37、 Ri. n调整为大根堆 =堆排序= void HeapSort(SeqList R) 对RL.n进行堆排序，不妨用R0做暂存单元int i; BuildHeap(R); 将Rl. n构造为初始大根堆 for(i=n; il; i-) 对当前无序区Rl. i进行堆排序，共做nT趟。RO=R1; Rl=Ri;Ri=RO;将堆顶和堆中最后一个记录交换Heapify (R, 1, i-l); 将Rl. iT重新调整为堆，仅有Rl可能违反堆性质。 )I6、二路归并排序的基本思想：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序 列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列

38、；再两两归并， 如此重复，直到一个长度为n的有序序列为止。=二=将两个有序的子序列RElow. m和Rm+L . high归并成有序的序列Rlow. high= void Merge(SeqList R, int low, int m, int high) (int i=low, j=m+l,p=0; 置初始值 RecType *R1; /RI 为局部量 Rl=(RecType *)ma 11 oc (high-1 ow+1)*sizeof (RecType); /申请空间 while(i=m & j;high)两个子序列非空时取其小者输出到RlpRI p+ = (Ri.key=Rj. key

39、)? Ri+ :Rj+; while(i=m)若第一个子序列非空，则复制剩余记录到R1Rlp+=Ri+;while(j=high)若第二个子序列非空，则复制剩余记录到R1中Rlp+=Rj+;for(p=0, i=low;i=high;p+, i+)Ri=Rl p；归并完成后将结果复制回Rlow.high)=对Rl. n做一趟归并排序= void MergcPass(SoqList R, int length) (int i;for(i=l; i+2*length-K=n;i=i+2*length)Merge(R, i, i + length-1, i+2*length-l); 归并长度为len

40、gth的两个相邻的子序列 if(i + length-ln)尚有一个子序列，其中后一个长度小于lengthMerge(R, i, i+length-1, n); 归并最后两个子序列注意：若iWn且i+lengthT 2n时，则剩余一个子序列轮空，无须归并 )/=自底向上对RL . n做二路归并排序:=二=void MergeSort(SeqList R) (int length;for (length=l; lengthn; length*=2) 做Ign趟排序 McrgePass (R, length);有序长度2n 时终止)=输入顺序表= void inputint(SeqList R)

41、(int i;printf (Please input num(int): scanf (，%d，, &n);printf (?，Plase input %d integern); for(i=l;i=n;i+)scanfkey);)=输出顺序表=void output_int(SeqList R)int i;for(i=l;i=n;i+)printf (飞4d”, Ri. key); )=主函数= void main()SeqList R;input_int(R);prinlf (l* Select *n);printf (z，tl: Insert Sortn);printf (，zt2: Bubble Sortn);printf(,zt3: Quick Sortn);printf(z，t4: Straight Selection Sortn);printf (，zt5: Heap Sortn);printfCt6: Merge Sort