算法与数据结构课程设计报-告.docx

算法与数据结构课程设计报 告系 （院）： 计算机科学学院 专业班级： 姓 名： 学 号： 指导教师： 一设计方案 由课程设计任务书，按照要求，需要设计1.单链表的基本操作与应用。2.栈的基本操作及应用。3.数组的基本操作与应用。4.树的基本操作与应用。5.图的基本操作与应用。由于总的框架和单链表的实现已经给出，剩下的就是把后面4个基本操作及应用实现，将其功能函数添加进去，通过选择调用这些功能函数实现要求。1. 单链表已经给出，不需要设计写出功能函数，只需要将代码整理便可实现要求。例如创建单链表：void OnCreateList_L()int n;cout n;CreateList_L(L,n); /已给函数其他功能如插入，查找，删除均可按上面方法调用功能函数，2 栈的基本操作及应用。首先按照要求，创建栈结构体，包含数据域和指针域。将要实现的功能对应的功能函数写出。要实现的功能是进栈Push()，出栈Pop()，取栈顶元素OnGetTop()。在对应功能选择项下面来调用这些函数。3稀疏矩阵的压缩存储及应用。创建三元组Triple结构体，包含行列下标i,j，元素e。创建矩阵TSMatrix结构体，包含Triple类型dataMAXSIZE+1，矩阵矩阵的行数mu，列数nu和非零元个数tu。实现CreateSMatrix()函数创建矩阵，PrintSMatrix()函数显示已创建的矩阵。在对应功能选择项下面来调用这些函数。4. 树的基本操作与应用。创建BiTNode结构体，包含char类型data，结构体类型BiTNode指针*left，*right。实现InitBiTree()，CreateBiTree()，Visit()对元素操作的的应用函数，先序遍历PreOrderTraverse()对每个数据元素调用函数Visit。中序遍历InOrderTraverse ()，后序遍历PostOrderTraverse()，计算树的深度BiTreeDepth()，计算叶子节点个数Leave()返回左右子树为空的个数，查找双亲BiTNode* Parent()，查找兄弟OnBrother()调用Parent()找到双亲下面左右子树。实现这些函数便可完成基本操作。将三个遍历函数的调用放在OnTraverse()里，实现一次性调用遍历。同时，在对应功选择项下面来调用这些函数。5. 图的基本操作与应用。图的操作都是以两种存储结构为基础的，邻接矩阵存储结构和邻接表存储结构。如4种图（无向图，无向网，有向图，有向网）的创建，其他的操作都是在四种图创建后才开始进行的。所以，首先必须理解两种存储结构的定义。图的邻接矩阵存储结构即图的数组表示法。创建关于弧ArcNode结构体体，intadjvex;struct*nextarc;Infotype *info;ArcNode。创建结VNode typedef struct VNode VertexType data; ArcNode* firstarc; VNode,AdjListMAX_VERTEX_NUM; 创建ALGraph结构体typedef struct AdjList vertices; int vernum, arcnum; int kind; ALGraph所有结构体已经创建完成，接下来就是实现功能函数， CreatUDG_ALG(ALGraph & ALG)创建无向图的邻接表，CreatUDN_M(MGraph &MG)创建无向网，CreatDG_ALG(ALGraph & ALDG)创建有向图，CreatDN_ALG(ALGraph & ALDN)创建有向网。遍历OnTraverse(ALGraph & ALG)包含深度DFSTraverse(ALGraph ALG, Status(*Visit)(int v)，DFS(ALGraph ALG,int v)， 和广度BFSTraverse(ALGraph ALG, Status(*Visit)(int v)遍历。二实现过程1功能图开始3.矩阵1.创建2.显示3.矩阵乘法4.退出1.单链表1.创建2插入3.删除4.查找5.显示6.通讯录7.退出2.栈1.进栈2.出栈3.获取 栈顶 元素4.表达求解 5.退出6.退出4.二叉树1.创建2.遍历3.计算 深度4.叶子 结点个数5.查找双亲6.查找兄弟7.Huffuman编码8.退出5.图1.创建无向图2.创建无向网3.创建有向图4.创建有向网5.遍历6.拓扑排序7.最小生成树8.最短路径9.关键路径10.退出2创建无向图过程图开始输入顶点个数、弧的条数初始化邻接表构造邻接表输入两相邻节点结束OnLinkList()单链表InitList_L(LinkList&L)CreateList_L(LinkList&L, int n)ListInsert_L(LinkList &L, int i, ElemType e).ListDelete_L(LinkList&，L,int i，,ElemType&e)GetElem_L(LinkList L, int i, ElemType&e)Brower(LinkList L)三实现代码OnBiTree()二叉树InitBiTree(BiTree &T)CreatBiTree(BiTree &T)PreOrderTraverse(BiTree T, Status(*Visit)(char)InOrderTraverse(BiTree T, Status(*Visit)(char)PostOrderTraverse(BiTree T, Status(*Visit)(char)BiTreeDepth(BiTree T)Leave(BiTNode *T)BiTNode* Parent(BiTNode *T, char e)OnBrother()OnArray()稀疏矩阵CreateSMatrix(TSMatrix &M)PrintSMatrix(TSMatrix M)OnStack()栈InitStack(Stack &S)Push(Stack&S, int e)Pop(Stack&S, int&e)GetTop(Stack S, int&e)StackEmpty(Stack S)ShowMainMenu()主菜单OnGraph()图CreatUDG_ALG(ALGraph&ALG); CreatUDN_ ALG ALGraph&ALG) CreatDG_ALG(ALGraph&ALDG); CreatDN_ALG(ALGraph & ALDN);CreatDN_M(MGraph &MDN);DFSTraverse(ALGraph ALG, Status(*Visit)(int v)DFS(ALGraph ALG, int v)FistAdjVex(ALGraph ALG, int v)NextAdjVex(ALGraph ALG, int v, int w)BFSTraverse(ALGraph ALG, Status(*Visit)(int v)TopologicalSort(ALGraph & ALDG)CriticalPath(ALGraph & ALDN)MiniSpanTree(MGraph & MN)Status TopologicalSort(ALGraph G) / 算法7.12 / 有向图G采用邻接表存储结构。 / 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。 SqStack S; int count,k,i; ArcNode *p; char indegreeMAX_VERTEX_NUM; FindInDegree(G, indegree); / 对各顶点求入度indegree0.vernum-1 InitStack(S); for (i=0; inextarc) k = p-adjvex; / 对i号顶点的每个邻接点的入度减1 if (!(-indegreek) Push(S, k); / 若入度减为0，则入栈 if (countG.vexnum) return ERROR; / 该有向图有回路 else return OK; / TopologicalSortStatus TopologicalOrder(ALGraph G, Stack &T) / 算法7.13 / 有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。/ T为拓扑序列定点栈，S为零入度顶点栈。/ 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为 ERROR。 Stack S;int count=0,k; char indegree40; ArcNode *p; InitStack(S); FindInDegree(G, indegree); / 对各顶点求入度indegree0.vernum-1 for (int j=0; jG.vexnum; +j) / 建零入度顶点栈S if (indegreej=0) Push(S, j); / 入度为0者进栈 InitStack(T);/建拓扑序列顶点栈T count = 0; for(int i=0; inextarc) k = p-adjvex; / 对j号顶点的每个邻接点的入度减1 if (-indegreek = 0) Push(S, k); / 若入度减为0，则入栈 if (vej+p-info vek) vek = vej+p-info; /for *(p-info)=dut() /while if (countG.vexnum) return ERROR; / 该有向网有回路 else return OK; / TopologicalOrderStatus CriticalPath(ALGraph G) / 算法7.14 / G为有向网，输出G的各项关键活动。 Stack T; int a,j,k,el,ee,dut; char tag; ArcNode *p; if (!TopologicalOrder(G, T) return ERROR; for(a=0; anextarc) k=p-adjvex; dut=p-info; /dut if (vlk-dut vlj) vlj = vlk-dut; for (j=0; jnextarc) k=p-adjvex;dut=p-info; ee = vej; el = vlk-dut; tag = (ee=el) ? * : ; printf(j, k, dut, ee, el, tag); / 输出关键活动 return OK; / CriticalPathvoid DFSTraverse(Graph G, Status (*Visit)(int v) / 对图G作深度优先遍历。 int v; VisitFunc = Visit; / 使用全局变量VisitFunc，使DFS不必设函数指针参数 for (v=0; vG.vexnum; +v) visitedv = false; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFSbool visitedMAX_VERTEX_NUM; / 访问标志数组Status (* VisitFunc)(int v); / 函数变量void DFS(Graph G, int v) / 从第v个顶点出发递归地深度优先遍历图G。 int w; visitedv = true; VisitFunc(v); / 访问第v个顶点 for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) / 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w);四测试（运行结果图）1单链表（创建、插入、显示、删除）2栈（进栈、获取栈顶、出栈）3稀疏矩阵4二叉树（创建、遍历、查找双亲、查找兄弟）5图的基本操作与应用（遍历、拓扑排序、最小生成树、最短路径、关键路径）四 结论 一、有待完善在执行程序时，我做了判断机制，比如在选择单链表的操作时，没有先选择创建单链表选项时，先选择插入、删除和显示时，输出“请输入1创建单链表”，程序不会死掉。增加了程序的可靠性和便捷性。但是，在输入数据元素的，必须按照规定的方式输入，一旦未按规定方式输入，程序就会运行出错，且没有错误提示。可在此程序的基础之上设计错误处理机制，使程序更加完善，更加具有可用性。二、代码繁琐程序代码冗长：由于使用的是结构体设计，代码可重用率较低。如果使用面向对象的设计方法，可用到继承大方法，使程序更加简洁，增加了代码可复用性和可读性。五难点与收获 一、难点（1）课设的难点一在于自己知识的缺乏和对数据结构这门课的学习的不精。一看到课设的题目，立马就有一种书到用时方恨少的感觉，平常在学习数据结构时，没有将课本上的代码一一上机实践。导致在课设时写代码时只能对着书本上代码慢慢敲。我想，如果完全独立自主不借助书本，这次的课设是完成不了的。说到底，还是自己学艺不精，学习不刻苦。这是本次课设的主要难点。（2）课设的难点二在于编程、调试、解决问题能力不足，编程时出现的错误和问题，并不能完全的解决掉。即使解决了也需要花费相对较长的时间。这在有限的时间里显然是不合适的。所以通过本次课设还要提高自己的编程调试能力。二、收获通过本次课设，我有以下几点收获（1） 掌握并运用程序语言是编写程序的基础。我总结了这次课设，为什么有一些算法我知道实现原理，却写不出完整的