数据结构课程设计报告双链表创建与演示设计.doc
《数据结构课程设计报告双链表创建与演示设计.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计报告双链表创建与演示设计.doc(25页珍藏版)》请在三一办公上搜索。
1、课 程 设 计 报 告课程名称 数据结构 课题名称 双链表创建演示 专 业 计算机科学与技术 班 级 计算机0703 学 号 姓 名 指导教师 2009 年 11 月 7 日课 程 设 计 任 务 书课程名称 数据结构 课 题 双链表创建演示专业班级 学生姓名 张 理 学 号 指导老师 审 批 1设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌,用户利用扑克牌的数字及运算符号“+”、“”、“*”、“/”及括号“(”和“)”从键盘上输入一个计算表达式,系统运行后得出计算结果,如果结果等于24,则显示“Congratulation!”,否则显示“Incorrec
2、t!”设计思路:从键盘输入中缀表达式,然后将中缀表达式转换为后缀表达式,利用后缀表达式求值。1.1.2 迷宫探索随机生成一个迷宫图,迷宫大小为N*N,N预定义为常数,修改N的值可以改变迷宫的大小。用白色表示可走的路,蓝色表示墙壁不可以通过。系统设计两种运行方式:一种是系统自动探索(用递归方法实现);另一种是由人工操作探索通路。设计思路:程序首先要考虑迷宫的表示,这是一个二维关系图,所以可选择二维数组来存储。数组元素只有两种值0和1,分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索,则依据按键来确定探索物的位置坐标,利用循环语句实现。如果是系统自动探索,可采用递归算法实现
3、。1.1.3 二叉树遍历演示演示遍历二叉树的过程,所以首先建立二叉树,并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建,设计两种生成树的方式:一种是系统随机生成,另一种是人工输入。考虑到屏幕界面的有限性,限定二叉树不超过5层,最多26个字符,输入字符小数点“.”代表NULL。初始树为某种颜色的结点,三种情况的遍历采用填充另外一种醒目的颜色,来表示当前遍历的结点,同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.1.4 数组应用按照行优先顺序将用户随机输入的数据建成2维数组并以图形方式逐步显示出来,然后再按照列优先顺序以图形方式逐步输出相应数组。1.1.
4、5 拓扑排序演示演示拓扑排序的过程。按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。1.1.6 图的遍历演示图的深度优先, 广度优先遍历过程,并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图,也可以由用户手动输入图。报告中要写出画图的思路;画出图的结构,有兴趣的同学可以进一步改进图的效果。1.1.7 八皇后问题演示在8*8的棋盘上摆放8个皇后,使他们不在同一条对角线上和不在一行和列上。 解决8皇后时,在安放第i行皇后时,需要在列的方向
5、从1到n试探(j =1, n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后不动,递归安放第i+1行皇后。 该课题要求求解可能的方案及方案数并逐步演示摆放皇后的过程。1.1.8 双链表创建演示建立一个递增有序的双链表。功能是随机生成8个结点数据,每生成一个结点则申请空间得到一个指针,将数据存放到指针所指的数据域中,然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置,第二不演示插入过程中指针的变化,第三步显示插入后的链表结果。1.1.9 公园导游图给出一张某公园的导游图,游客
6、通过终端询问可知:从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。要求用图示展示最佳路径。1.2 选题方案:所选题目根据学号确定,学号模9加1,即(学号%9+1)。如你的学号为12,则所选题目号为:12%9+1(题目4)。注意,所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法,但要预先告知老师,经过审批,方可确定课题。1.3设计要求:1.3.1 课程设计报告规范(1)需求分析a. 程序的功能。b. 输入输出的要求。(2)概要设计a. 程序由哪些模块
7、组成以及模块之间的层次结构、各模块的调用关系;每个模块的功能。b. 课题涉及的数据结构和数据库结构;即要存储什么数据,这些数据是什么样的结构,它们之间有什么关系等。(3)详细设计a. 采用C语言定义相关的数据类型。b. 写出各模块的类C码算法。c. 画出各函数的调用关系图、主要函数的流程图。(4)调试分析以及设计体会a. 测试数据:准备典型的测试数据和测试方案,包括正确的输入及输出结果和含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。(5)使用说明用户使用手册:说明如何使用你编写的程序,详细列出每一步的操作步骤。 (6)书写格式a.
8、 设计报告要求用A4纸打印成册:b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。(7)附录a. 源程序清单(带注释)1.3.2 考核方式指导老师负责验收程序的运行结果,并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评,并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分:(1)平时出勤 (占10%)(2)系统需求分析、功能设计、数据结构设计及程序总体结构合理与否(占10%)(3)程序能否完整、准确地运行,个人能否独立、熟练地调试程序(占40%)(4)设计报告(占30%)注意:不得抄袭他人的报告(或
9、给他人抄袭),一旦发现,成绩为零分。(5)独立完成情况(占10%)。1.3.3 课程验收要求(1)运行所设计的系统。(2)回答有关问题。(3)提交课程设计报告。(4)提交软盘(源程序、设计报告文档)。(5)依内容的创新程度,完善程序情况及对程序讲解情况打分。2 进度安排2.1 计算机0701/0702班:第 7 周:星期一 8:0012:00 上课 星期一 14:0016:00 上课 星期五 18:0022:00 上机第 8 周:星期六 14:0018:00 上机 星期日 8:0012:00 上机 星期日 18:0022:00 上课第 9 周:星期六 8:0012:00 上机 星期日 14:0
10、018:00 上机2.2 计算机0703班: 第 7 周:星期一 8:0012:00 上课 星期一 14:0016:00 上课 星期六 8:0012:00 上机 星期日 14:0018:00 上机第 8 周:星期六 8:0012:00 上机 星期日 14:0018:00 上机第 9 周:星期六 14:0018:00 上机 星期日 18:0022:00 上机目 录一、需求分析- 1 -1.程序功能说明 - 1 -2.输入输出- 1 -二、概要设计- 2 -1.程序模块 本程序由于仅需实现双链表的创建演示,所以程序结构比较简单,主要由三部分模块函数组成,即构建生成双链表,演示指针变化,结果输出。-
11、 2 -2.课题涉及的数据结构和数据库结构 本课题所用到的数据结构主要是双向链表,所用到的数据结构如下- 2 -2.1双链表存储结构- 2 -2.2双链表结点的插入- 2 -2.3双链表结点的删除- 3 -三、详细设计- 4 -1.采用C语言定义相关的数据类型- 4 -1.1双链表结点定义- 4 -2.写出各模块的类C码算法- 4 -2.1 建立并插入双链表的类C算法- 4 -2.2 指针变化演示类C算法- 5 -3.3 输出已排序双链表类C代码- 5 -3.画出各函数的调用关系图、主要函数的流程图。- 6 -四、调试分析以及设计体会- 6 -1程序调试中遇到的问题以及解决问题的方法。- 6
12、-2课程设计过程经验教训、心得体会。- 7 -五、使用说明- 7 -六、附录- 10 -源程序清单- 10 -参考文献- 15 - 17 -一、 需求分析1. 程序功能说明链表是线性表的链式表示,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构在做插入删除操作时需要移动大量元素的弱点。双链表的结点中有两个指针域,一个指向直接后继,一个指向直接前驱。所以双链表创建演示就是建立一个递增有序的双链表。程序功能是首先由程序随机生成8个结点数据,生成一个结点后则申请空间得到一个指针,将数据存放到指针所指的数据域中,再生成一个结点后先判断此结点的数值和已生成结点的大小,由于要求建立递
13、增有序的双链表,所以把结点插入到比其大的所有结点中的最小结点之前和比其小的所有结点中最大结点的之后,并在插入过程中显示指针变化,最后输出排好序的双链表。2. 输入输出由于本程序为演示程序,结点也由程序随机生成,所以在输入方面不需实现功能,只需用户控制程序操作。输出方面主要是在屏幕显示插入结点的结果和显示指针变化的功能,具体输出过程为输出首先生成的结点,然后显示对已生成结点的排序,再演示出指针变化,指针以弯折的箭头表示,最后输出排序后的链表,直箭头表示双链表的前驱后驱。二、 概要设计1. 程序模块本程序由于仅需实现双链表的创建演示,所以程序结构比较简单,主要由三部分模块函数组成,即构建生成双链表
14、,演示指针变化,结果输出。程序结构图:双链表创建演示主程序双链表创建指针变化演示结果输出2. 课题涉及的数据结构和数据库结构本课题所用到的数据结构主要是双向链表,所用到的数据结构如下2.1双链表存储结构typedef struct DuLNodeElemType data;struct DuLNode *prior; struct DuLNode *next;DuLNode, *DuLinkList;2.2双链表结点的插入Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)if(!(p=GetElemp_DuL(L,i)return E
15、RROR;if(!(s=(DuLinklist)malloc(sizeof(DuLNode)return ERROR;s-data=e;s-prior=p-prior; p-piror-next=s;s-next=p;p-prior=s;return OK;2.3双链表结点的删除Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e)if(!(p=GetElemP_DuL(L,i)return ERROR;e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p); return O
16、K;三、 详细设计1.采用C语言定义相关的数据类型1.1双链表结点定义 typedef struct Link int data; struct Link *right; struct Link *left; int num;linkx,*linky;2.写出各模块的类C码算法2.1 建立并插入双链表的类C算法 void InitList(void) randomize(); 将产生的随机数字转换成字符串并输出; sleep(1); PrLink(head,n); /*显示只有头节点的链表*/ n+; while(n!=8) s-data=random(100); if(s-datadata)
17、 /*小于头结点,插在头*/ q=head-right; q-num+; /*节点数加1;*/ 显示具体插入过程; else /其他情况/ if(p=NULL) /*这个数是当前最大的数,插在尾部*/显示插入的具体过程;else /*随即产生的数排在表中*/ while(s!=NULL) s-num+;s=s-right;显示插入的具体过程;2.2指针变化演示类C算法void DrawChange(int data,int i,int n) 判断插入结点的位置: if(i!=-1) 当前指针是头指针,画前驱、后继指针; if(i!=n-1)当前指针是尾指针,画前驱、后驱指针;if(i!=n-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 双链表 创建 演示 设计
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-4856607.html