数据结构课程设计指导书简.docxVIP

数据结构及算法分析课程设计指导书制订教师：张娟、丛松城市学院2015年09月一、实训目的数据结构旨在使读者学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算，把现实世界中的问题转化为计算机内部的表示和处理。进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；掌握软件设计的基本内容和设计方法，并培养规范化软件设计的能力；将理论知识和实际结合起来，锻炼分析解决实际问题的能力。二、课程设计题目题目1:通讯录管理通讯录管理系统一般包括通讯录结点信息的插入、查询、删除、更新以及通信录信息的输出等功能。而通讯录的信息一般包括编号、姓名、性别、电话以及地址等项。本题主要考查用链式结构来实现通讯录管理系统（链表的操作）。1、设计步骤、（1）定义通讯者的结点类型typedef structchar num5;/编号char name9;/姓名char sex3;/性别char phone13;/电话char addr31;/地址DataType;因此，线性表的链式存储结构定义如下：typedef struct nodeDataType data;struct node* next;ListNode;Typedef ListNode* LinkList;ListNode *p;/定义一个指向结点的指针变量LinkList head;/定义指向单链表的头指针（2）通讯录管理：包括单通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询及通讯录表的输出等2、设计要点实现通讯录的建立和输出、通讯者的插入、删除和查询等几种操作功能。用单链表作存储结构；用菜单作为应用程序的主要界面，主界面的主控菜单如下： 通讯录链表*1. 通讯录链表的建立2. 通讯录结点的插入3. 通讯录结点的查询4. 通讯录结点的删除5. 通讯录链表的输出0. 退出通讯录管理系统 * 请选择菜单号：*：使用数字05来选择菜单项，其他输入无效，并给出错误提示。设计功能程序运行后的功能有：（1）菜单选择界面（2）建立通讯录记录（3）插入联系人记录（4）查找联系人记录（名称和编号查询）（6）删除联系人记录（7）输出所有联系人记录（8）退出程序3、设计进度安排D1D3：完成个人任务D4D5：开题，设计。从问题需求,数据结构,数据组织,算法难点等关键方面进行分析,形成的总体设计方案D6D7：编码调试。小组成员根据初步的综合性设计方案,团结协作完成编码调试（每人独立完成系统的一个专题）D8D9:测试扩展。在各程序模块编码完成并集成后,就可以开始对整个系统进行测试，在最小系统基础上扩展、完善功能和界面。D10:答辩与验收。通过演示、答辩等的形式对程序的功能进行评价验收，根据个人的设计调试过程，独立撰写设计报告。4、主要技术关键的分析、解决思路和方案比较等内容。建立通讯录链表的设计是本设计的关键，这里实际上是要求建立一个带头结点的单链表。头插法是每次将新插入的结点插入在链表的表头，而尾插法是将新插入的结点插入在链表的表尾。要建立链表，首先要生成结点，因此尾插法建立链表的算法描述如下：（1） 使链表的头尾指针head,rear指向新生成的头结点（也是尾结点）（2） 置结束标志为0（假）（3） While(结束标志不为真)P指向新生成的结点；读入一个通讯者的数据至新结点的数据域；将新结点链到尾结点之后；使尾指针指向新结点;提示：是否结束建表，读入一个结束标志；（4） 尾结点指针域置空值NULL算法设计系统流程图如图所示：主函数设计由于主函数设计的是菜单选择项，所以在程序未退出的的情况下要实现循环运行，并且要考虑到未建立通讯录链表的情况下其他功能无法实现的情况。故在实现循环运行的功能时定义一个变量j=1，在选择退出后再将j赋值为0，要考虑判定是否建表的情况定义了一个全局变量flag1=0，建链表后flag1赋值为1。为了达到选择各功能,采用switch判定选择项并跳转入相应功能函数。判定是否建表语句:if(flag1!=1) printf(请先建立表!); getchar();system(cls);616 功能程序设计为了达到程序各项功能的实现，以及满足菜单选择项的功能，对每个功能的实现分别用了不同函数，并且有用到函数的嵌套以减少代码的重复。6题目2：约瑟夫环【问题描述】编 号是1，2，?,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向 自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出 列为止。设计一个程序来求出出列顺序。【要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。【测试数据】m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=7,（正确的出列顺序应为6,7,4,1,5,3,2）。【实现提示】程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。基本要求：建立模型，确定存储结构； 对任意 n个人，密码为 m，实现约瑟夫环问题；出圈的顺序可以依次输出，也可以用一个数组存储。设计指导思想：首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图2-1所示。二方案论证：本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表，过程如下：约瑟夫问题中的人数个数即为链表的长度，链表中node-num 编号n，node-data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node-num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。三过程论述：typedef struct node int data; int num; struct node *next; listnode; 定义一个结构体用来储存学生的编号和所携带的密码for(i=1;inext=(listnode*)malloc(sizeof(listnode);/建立一个新的空间，并将它的地址赋给p1-next p1=p1-next; p1-data=j; p1-num=i;/对结点的num和data成员赋值p1-next=head-next;/构成单循环链表 定义指针p1，然后建立一个新结点并将p1-next指向它的地址，然后将这个地址赋给p1，最后将head-next赋给p1-next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值do k=1; while(k!=m)/当k=m时一轮报数结束 p1=p1-next; k+; /报数过程中将指针p1指向下一位p2=p1-next; p1-next=p2-next;/将报m的人的结点从链表中删去printf(编号为%d的人出列，他的密码%d作为新的m值n,p2-num,p2-data);/报数为m的人出列 m=p2-data;/报数为m的人的密码作为新的m值 free(p2);/释放报m的人的结点while(p1-next!=p1);/当p1-next指向的地址是它自己的地址，所有报数结束定义指针p1用以循环链表，定义变量k计数，指针p1每移动一次，k加1，直到k=m时，输出指针p1所指向的节点序号，也就是令这个“人”出列，p2指向该节点上一节点，令上一节点next域指向该节点下一节点，然后删除该节点，令头节点p1指向该节点下一节点作为再次报数初始“人”，再令k归1，继续循环。 直到p1-next= =p1时，表示所有“人”出列完毕，删除最后的节点后跳出循环.题目3:学生搭配问题【问题描述】一班有m个女生，有n个男生(m不等于n)，现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上，每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程。【基本要求】（1）输出每曲配对情况（2）计算出任何一个男生(编号为X)和任意女生(编号为Y)，在第K曲配对跳舞的情况。至少求出K的两个值。【提示】用队列来解决比较方便.基本思路及关键问题的解决方法基本思路：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。循环队列是在队列的顺序存储结构中，除了用乙组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。循环队列的入队，出队，判队满，判队空。（1）要模拟动态地显示出现题目中所要求的循环，我们要先建立两个循环队列SqQueue和SqQueue2。（2）将男生、女生两组人分别存入这两个队列。以实现他们的循环配对输出，这是循环队列固有的特性。（3）利用循环队列的特性，将男女生分别进行入队列和出队列操作，且实现搭配输出。（4）循环队列的长度分别设为男女生的个数即可。 （5）在计算机终端输出的结果是：根据要求输出男生女生搭配情况关键问题:循环队列的应用解决方法：数据模型（逻辑结构）: 循环队列（两个），将男生、女生两组人分别存放，以实现循环配对输出。存储结构: 循环链表核心算法: 循环队列的入队，出队，判队满，判队空。输入数据: 男生人数、女生人数，歌曲数量输出数据: 每一首歌曲播放时，男生和女生搭配情况（只输出编号即可）当要查找的男女搭配时输出歌曲编号，和他们搭配的总次数。通过以上分析，该程序具有可行性。八、算法与流程图题目4:建立二叉树，层序、先序遍历【设计目标】二叉树是一个重要的数据类型，通过建立一个链式存储结构，能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。【二叉树遍历实现流程图】3设计实现题目5： 校园最短路径问题本题主要考图中最短路径的操作。在交通网络非常发达的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也兴趣。用图结构来表示交通网络系统，图中的顶点表示城市，边表示城市之间的交通关系。假设图中的每一站都需要换车，那么这个问题就反映到图上找一条从顶点A到B所含边的数目最少的路径。1、设计步骤、（1）建立图的存储结构如果G是带权有向图,则： Aij= wij :若vivj且E(G) :其他邻接矩阵的数据类型定义如下：#define MAXV typedef struct int no;/*顶点编号*/ InfoType info; /*顶点其他信息*/ VertexType;/*顶点类型*/typedef struct /*图的定义*/ int edgesMAXVMAXV; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数,弧数*/ VertexType vexsMAXV;/*存放顶点信息*/ MGraph;2、设计要点一个图的邻接矩阵表示是唯一的，图的邻接矩阵表示除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点Vi的信息。单源点最短路径Dijksstra提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法，迪克斯特拉算法的具体步骤如下： (1) 初始时,S只包含源点,即S=v,v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边)或(若u不是v的出边邻接点)。 (2) 从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v到k的最短路径长度)。 (3) 以k为新考虑的中间点,修改U中各顶点的距离：若从源点v到顶点u(uU)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。 (4) 重复步骤(2)和(3)直到所有顶点都包含在S中。V到j的最小距离MIN(cvk+wkj,cvj)3、需求分析 ：（1）、问题描述图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：a) 顶点数b) 边数c) 边的长度（2）、功能需求 要求完成以下功能：a) 输出顶点信息：将校园内各位置输出。b) 输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。c) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离。d) 求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出任意一点与其它各点的最短路径。e) 删除：删除任意一条边。f) 插入：插入任意一条边。（3）、实现要点 a) 对图的创建采用邻接矩阵的存储结构，为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。4、概要设计:1. 抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性数据元素的集合，称为顶点集。数据关系R：R=VRVR=（v，w）| v , wV, (v , w)表示v和w之间存在路径基本操作P：CreatGraph(&G, V, VR)初始条件： V是图的顶点集，VR是图中边的集合。操作结果： 按定义(V, VR) 构造图G。DestroyGraph(&G)初始条件： 图G已存在。操作结果： 销毁图。LocateVex(G, u) 初始条件： 图G存在，u和G中顶点具有相同特征。操作结果： 若G中存在顶点u，则返回该顶点在图中“位置” ；否则返回其它信息。GetVex(G, v) 初始条件： 图G存在，v是G中某个顶点。操作结果： 返回v的信息。InsertVex(&G, v) 初始条件： 图G存在，v和G中顶点具有相同特征。操作结果： 在图G中增添新顶点v。DeleteVex(&G, v)初始条件： 图G存在，v和G中顶点具有相同特征。操作结果： 删除G中顶点v及其相关的边。InsertArc(&G, v, w) 初始条件： 图G存在，v和w是G中两个顶点。操作结果： 在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G, v, w)初始条件： 图G存在，v和w是G中两个顶点。操作结果： 在G中删除弧，若G是无向的，则还删除对称弧。 ADT Graph2. 主程序void main() 初始化； while(“命令”!=“退出”) Switch语句 接受命令（输入选择项序号）； 处理命令； 3. 本程序运用函数的调用，只有两个模块，它们的调用关系为：主程序模块带权无向图模块题目6：内部排序算法比较【问题描述】在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 【基本要求】（1）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。（2）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 【测试数据】由随机数产生器生产。 【实现提示】主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和异动次数的计数操作。程序还可以考虑几组数据的典型性，如正序、逆序和不同程度的乱序。一、任务描述（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）显示随机数：调用Dip()函数输出数组a。数组a中保存有随机产生的随机数。（2）直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。（3）冒泡排序：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较（4）希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（5）直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。（6）显示各排序算法排序后的的数据和时间效率，并比较找出其中2种较快的方法2、数据对象分析排序方式：直接选择排序、冒泡排序、希尔排序、直接插入排序.显示排序后的的数据和时间效率。三、数据结构设计1.主要全程变量及数据结构数据结构：typedef struct KeyType key; InfoType otherinfo; RedType; typedef struct RedType rMAXSIZE+1; int length; SqList;