数据结构课程设计报告-双链表创建与演示设计.doc

课 程 设 计 报 告 课程名称课程名称 数据结构数据结构 课题名称课题名称 双链表创建演示双链表创建演示 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 计算机计算机 0703 学学 号号 姓姓 名名 指导教师指导教师 2009 年年 11 月月 7 日日 1 课 程 设 计 任 务 书 课程名称 数据结构 课 题 双链表创建演示 专业班级 学生姓名 张 理 学 号 指导老师 审 批 2 1 1 设设计计内内容容与与设设计计要要求求 1.11.1 设计内容设计内容 1.1.11.1.1 算术算术 2424 游戏演示游戏演示 由系统随机生成 4 张扑克牌，用户利用扑克牌的数字及运算符号“+” 、 “” 、 “*” 、 “/”及括号“（”和“） ”从键盘上输入一个计算表达式，系统 运行后得出计算结果，如果结果等于 24，则显示“congratulation!” ，否则 显示“incorrect!” 设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达 式，利用后缀表达式求值。 1.1.21.1.2 迷宫探索迷宫探索 随机生成一个迷宫图，迷宫大小为 n*n，n 预定义为常数，修改 n 的值可 以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统 设计两种运行方式：一种是系统自动探索（用递归方法实现） ；另一种是由人 工操作探索通路。 设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可 选择二维数组来存储。数组元素只有两种值 0 和 1，分别代表通路和墙壁。图 形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确 定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递 归算法实现。 1.1.31.1.3 二叉树遍历演示二叉树遍历演示 演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形 状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一 种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二 叉树不超过 5 层，最多 26 个字符，输入字符小数点“.”代表 null。初始树 为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示 当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历 图形的下方显示出遍历序列。 1.1.41.1.4 数组应用数组应用 按照行优先顺序将用户随机输入的数据建成 2 维数组并以图形方式逐步 3 显示出来，然后再按照列优先顺序以图形方式逐步输出相应数组。 1.1.51.1.5 拓扑排序演示拓扑排序演示 演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一 个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意 的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它 为尾的弧。 1.1.61.1.6 图的遍历图的遍历 演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。 要求图的结点数不能少于 6 个。可以由系统随机生成图，也可以由用户手动 输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一 步改进图的效果。 1.1.71.1.7 八皇后问题演示八皇后问题演示 在 8*8 的棋盘上摆放 8 个皇后，使他们不在同一条对角线上和不在一行 和列上。 解决 8 皇后时，在安放第 i 行皇后时，需要在列的方向从 1 到 n 试探(j =1, n)：首先在第 j 列安放一个皇后，如果在列、主对角线、次 对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有 出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1 行皇后。 该课题要求 求解可能的方案及方案数并逐步演示摆放皇后的过程。 1.1.81.1.8 双链表创建演示双链表创建演示 建立一个递增有序递增有序的双链表。功能是随机生成 8 个结点数据，每生成一 个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后 将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入 位置，第二不演示插入过程中指针的变化，第三步显示插入后的链表结果。 1.1.91.1.9 公园导游图公园导游图 给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一 景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重 复地游览各景点，最后回到出口（出口就在入口旁边） 。要求用图示展示最佳 路径。 4 1.21.2 选题方案：选题方案： 所选题目根据学号确定，学号模 9 加 1，即（学号%9+1） 。如你的学号为 12，则所选题目号为：12%9+1（题目 4） 。注意，所有的课题都要求用图形 方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法 来设计一个演示过程的算法，但要预先告知老师，经过审批，方可确定课题。 1.31.3 设计要求：设计要求： 1.3.11.3.1 课程设计报告规范课程设计报告规范 （1）需求分析 a. 程序的功能。 b. 输入输出的要求。 （2）概要设计 a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每 个模块的功能。 b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什 么样的结构，它们之间有什么关系等。 （3）详细设计 a. 采用 c 语言定义相关的数据类型。 b. 写出各模块的类 c 码算法。 c. 画出各函数的调用关系图、主要函数的流程图。 （4）调试分析以及设计体会 a. 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结 果和含有错误的输入及输出结果。 b. 程序调试中遇到的问题以及解决问题的方法。 c. 课程设计过程经验教训、心得体会。 （5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。 （6）书写格式 a. 设计报告要求用 a4 纸打印成册： b. 一级标题用 3 号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距 5 为 22。 （7）附录 a.源程序清单（带注释） 1.3.21.3.2 考核方式考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创 新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级 给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： （1）平时出勤 （占 10%） （2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占 10%） （3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%） （4）设计报告（占 30%） 注意：不得抄袭他人的报告（或给他人抄袭） ，一旦发现，成绩为零分。 （5）独立完成情况（占 10%） 。 1.3.31.3.3 课程验收要求课程验收要求 （1）运行所设计的系统。 （2）回答有关问题。 （3）提交课程设计报告。 （4）提交软盘（源程序、设计报告文档） 。 （5）依内容的创新程度，完善程序情况及对程序讲解情况打分。 2 2 进度安排进度安排 2.12.1 计算机计算机 0701/07020701/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：0018：00 上机 2.22.2 计算机计算机 07030703 班：班： 第 7 周：星期一 8：0012：00 上课 星期一 14：0016：00 上课 6 星期六 8：0012：00 上机 星期日 14：0018：00 上机 第 8 周：星期六 8：0012：00 上机 星期日 14：0018：00 上机 第 9 周：星期六 14：0018：00 上机 星期日 18：0022：00 上机 目目 录录 一、一、需求分析需求分析 - 1 - 1.1.程序功能说明程序功能说明 .- 1 - 2.2.输入输出输入输出 - 1 - 二、二、概要设计概要设计 - 2 - 1.1.程序模块程序模块 本程序由于仅需实现双链表的创建演示，所以程序结构比较简单，主本程序由于仅需实现双链表的创建演示，所以程序结构比较简单，主 要由三部分模块函数组成，即构建生成双链表，演示指针变化，结果输出。要由三部分模块函数组成，即构建生成双链表，演示指针变化，结果输出。- 2 - 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 - 2课程设计过程经验教训、心得体会。课程设计过程经验教训、心得体会。- 7 - 五、五、使用说明使用说明 - 7 - 六、六、附录附录- 10 - 源程序清单源程序清单.- 10 - 参考文献参考文献 - 15 - - 0 - 一、一、 需求分析需求分析 1.1. 程序功能说明 链表是线性表的链式表示，由于它不要求逻辑上相邻的元素在物理位置上链表是线性表的链式表示，由于它不要求逻辑上相邻的元素在物理位置上 也相邻，所以它没有顺序存储结构在做插入删除操作时需要移动大量元素也相邻，所以它没有顺序存储结构在做插入删除操作时需要移动大量元素 的弱点。双链表的结点中有两个指针域，一个指向直接后继，一个指向直的弱点。双链表的结点中有两个指针域，一个指向直接后继，一个指向直 接前驱。所以双链表创建演示就是建立一个递增有序的双链表。程序功能接前驱。所以双链表创建演示就是建立一个递增有序的双链表。程序功能 是首先由程序随机生成是首先由程序随机生成 8 8 个结点数据，生成一个结点后则申请空间得到一个结点数据，生成一个结点后则申请空间得到一 个指针，将数据存放到指针所指的数据域中，再生成一个结点后先判断此个指针，将数据存放到指针所指的数据域中，再生成一个结点后先判断此 结点的数值和已生成结点的大小，由于要求建立递增有序的双链表，所以结点的数值和已生成结点的大小，由于要求建立递增有序的双链表，所以 把结点插入到比其大的所有结点中的最小结点之前和比其小的所有结点中把结点插入到比其大的所有结点中的最小结点之前和比其小的所有结点中 最大结点的之后，并在插入过程中显示指针变化，最后输出排好序的双链最大结点的之后，并在插入过程中显示指针变化，最后输出排好序的双链 表。表。 2.2. 输入输出 由于本程序为演示程序，结点也由程序随机生成，所以在输入方面不需实由于本程序为演示程序，结点也由程序随机生成，所以在输入方面不需实 现功能，只需用户控制程序操作。输出方面主要是在屏幕显示插入结点的现功能，只需用户控制程序操作。输出方面主要是在屏幕显示插入结点的 结果和显示指针变化的功能，具体输出过程为输出首先生成的结点，然后结果和显示指针变化的功能，具体输出过程为输出首先生成的结点，然后 显示对已生成结点的排序，再演示出指针变化，指针以弯折的箭头表示，显示对已生成结点的排序，再演示出指针变化，指针以弯折的箭头表示， 最后输出排序后的链表，直箭头表示双链表的前驱后驱。最后输出排序后的链表，直箭头表示双链表的前驱后驱。 - 1 - 二、 概要设计计 1.1. 程序模块 本程序由于仅需实现双链表的创建演示，所以程序结构比较简单，主要由本程序由于仅需实现双链表的创建演示，所以程序结构比较简单，主要由 三部分模块函数组成，即构建生成双链表，演示指针变化，结果输出。三部分模块函数组成，即构建生成双链表，演示指针变化，结果输出。 程序结构图： 2.2. 课题涉及的数据结构和数据库结构 本课题所用到的数据结构主要是双向链表，所用到的数据结构如下本课题所用到的数据结构主要是双向链表，所用到的数据结构如下 2.12.1 双链表存储结构双链表存储结构 typedef struct dulnode elemtype data; struct dulnode *prior; struct dulnode *next; dulnode, *dulinklist; 2.22.2 双链表结点的插入双链表结点的插入 status listinsert_dul(dulinklist if(!(s=(dulinklist)malloc(sizeof(dulnode) return error; 双链表创建演示主程 序 双链表创建指针变化演示结果输出 - 2 - s-data=e; s-prior=p-prior; p-piror-next=s; s-next=p; p-prior=s; return ok; 2.32.3 双链表结点的删除双链表结点的删除 status listdelete_dul(dulinklist e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return ok; - 3 - 三、三、 详细设计详细设计 1. 采用 c 语言定义相关的数据类型 1.11.1 双链表结点定义双链表结点定义 typedef struct link int data; struct link *right; struct link *left; int num; linkx,*linky; 2. 写出各模块的类 c 码算法 2.12.1 建立并插入双链表建立并插入双链表的类的类 c c 算法算法 void initlist(void) randomize(); 将产生的随机数字转换成字符串并输出； sleep(1); prlink(head,n); /*显示只有头节点的链表*/ n+; while(n!=8) s-data=random(100); if(s-datadata) /*小于头结点，插在头*/ q=head-right; q-num+; /*节点数加 1；*/ 显示具体插入过程； else /其他情况/ if(p=null) /*这个数是当前最大的数，插在尾部*/ 显示插入的具体过程； else /*随即产生的数排在表中*/ while(s!=null) s-num+;s=s-right; - 4 - 显示插入的具体过程； 2.22.2指针变化演示类指针变化演示类 c c 算法算法 void drawchange(int data,int i,int n) 判断插入结点的位置： if(i!=-1) 当前指针是头指针，画前驱、后继指针； if(i!=n-1) 当前指针是尾指针，画前驱、后驱指针； if(i!=n-1 - 5 - 3.画出各函数的调用关系图、主要函数的流程图。 y y y n 进入 调用 prlink(head,n) closr(void) 调用 drawchange(s-data,q-num,n) 调用 drawchange(s-data,n-1,n) 调用 drawchange(s-data,t,n) 调用 prink(p ,n) 调用 inintlist(void) s- datadata p=null - 6 - 具体 inintlist(void)函数的流程图： - 7 - 四、四、 调试分析以及设计体会调试分析以及设计体会 1程序调试中遇到的问题以及解决问题的方法。 主要是在结点插入判断方面有难度，一开始不能准确的进行结点的判断和插 入，然后就是插入结点的过程中位置不对，不是递增有序的，后面在网上找 到了一段演示代码，通过研究这段代码解决了这个问题。还有就是在显示指 针变化方面有问题，经过查询资料，解决结点插入方面的问题，用画箭头的 方式来表现指针的变化。 2课程设计过程经验教训、心得体会。 在进行本次课程设计的实验操作中，由于自己的基础知识不是很好，出现了一 些问题：在编程方面不熟，所以写出的代码总是出错；数据结构课程以前也没 有好好学过，造成在构建程序数据结构时出现由于概念模糊而写错功能的问题。 但是在老师和同学们的帮助下，再通过查阅资料，最后终于写出了可以正确运 行结果的代码，所以要感谢给我帮助的老师和同学。以前用 c 编程，只是注重 如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意 识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能 完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够 综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？ 然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编 写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样， 即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样 无形中就提高了自己编写的程序的质量。 通过这次课程设计，使我意识到作为一个计算机系的学生，正确掌握一门程序 语言和数据结构的重要性，想要在程序设计上面作出成绩，必须要有扎实的编 程语言基础和良好的数据结构算法知识，我决定在余下的在校时间里，认认真 真学一门语言，并去详细了解程序的算法设计。 - 8 - 五、五、 使用说明使用说明 本程序是演示程序，在运行后按任意键即执行演示过程，可直观的看到程序运 行时双链表指针的变化情况，为方便观察结果，在程序运行的时候，按一下执 行一步，也可以通过按 q 键来退出程序，也可以在等待所有过程结束后再退出。 1进入程序后界面： 2随机产生结点，图中已产生 2 个结点，由于 57 大于 1，所以没有右指 针 3指针变化情况 - 9 - 4完成一个链表创建，下一结点插入中 5所有步骤完成后程序显示界面，可清晰看到排序后的双链表结果 - 10 - 六、六、 附录附录 源程序清单 #include “stdlib.h“ #include “graphics.h“ typedef struct link/*双链表结点定义*/ int data; struct link *right; struct link *left; int num;/*给链表加序号,为了演示时计算正确位置*/ linkx,*linky; void init(void);/*图形驱动*/ void close(void);/*图形关闭*/ void initlist(void);/*建立双链表,边建立边插入*/ void prlink(linky p,int n);/*每次插入后输出链表*/ void drawchange(int data,int i,int n);/*画链表插入的指针变化*/ void main(void) init();/*图形关闭*/ initlist();/*建立链表*/ close();/*图形关闭*/ exit(0); void initlist(void) /*建立双向链表,边建立边插入*/ linky head,p,q,s; int n=0; char str5; randomize();/*随机数发生机*/ - 11 - setcolor(blue); outtextxy(200,20,“perss any key to start“); setcolor(red); outtextxy(400,30,“press q to quit“); getch(); head=s=(linky)malloc(sizeof(linkx); s-data=random(100);/*随机生成 100 以内的数字*/ s-num=n; sprintf(str,“%d“,s-data);/*将数字转换成字符串并输出*/ settextstyle(4,0,1); setcolor(white); outtextxy(50,50,“nodedata:“); outtextxy(50,70,“doublelinks:“); setcolor(10); outtextxy(155+n*35,50,str);/*显示数据*/ getch(); s-right=null; s-left=null; prlink(head,n);/*每次插入新数字后都显示当前链表*/ n+; while(n!=8) s=(linky)malloc(sizeof(linkx); s-data=random(100); s-num=n; sprintf(str,“%d“,s-data);/*将数字转换成字符串并输出*/ setcolor(10); outtextxy(155+n*35,50,str); getch(); p=head;/*每生成一个结点，将该结点插入到有序双链表中*/ if(s-datadata)/*小于头结点，插在头*/ drawchange(s-data,-1,n);/*显示插入的具体过程*/ s-right=head; s-left=null; s-num=0; head-left=s; head=s; q=head-right;/*后面所有数的序号都加 1，相当于数据后移*/ while(q!=null) q-num+; q=q-right; - 12 - else/*其他情况*/ while(s-datap-data p=p-right; if(p=null)/*这个数是当前最大的数，插在尾部*/ drawchange(s-data,n-1,n);/*显示插入的具体过程*/ q-right=s; s-right=null; s-left=q; s-num=n; else /*结点插入位置位于两数之间*/ q-right-left=s; s-right=q-right; s-left=q; q-right=s; s-num=q-num+1; drawchange(s-data,q-num,n);/*显示插入的具体过程*/ /*后面所有数的序号都加 1*/ s=s-right; while(s!=null) s-num+; s=s-right; prlink(head,n);/*每次插入新数据后都显示新链表*/ n+; /*画链表插入的具体过程，data 是要插入的数据，i 为插入结点前驱结点序号，n 为当前结点个数， 先将前驱结点和后继之间的指针线擦除，显示新结点插入过程，插入后擦除插入过程，恢复删除的 前驱结点的指针线*/ void drawchange(int data,int i,int n) char str5; setfillstyle(solid_fill,black); setcolor(red);/*插入链表的新数据用红色显示*/ sprintf(str,“%d“,data); - 13 - outtextxy(55+70*i+35,100+n*50,str);/*输出插入的位置*/ bar(50+70*i+35,100+(n-1)*50-20,50+70*i+65,100+(n-1)*50+20); /*去除插入结点位置原结点间的指针线*/ setcolor(yellow); if(i!=-1) /*不是插在头，新结点的前驱指针线*/ line(50+70*i+34,100+n*50,50+70*i+30,100+n*50); line(50+70*i+30,100+n*50,50+70*i+30,100+n*50-25); line(50+70*i+30,100+n*50-25,50+70*i+27,100+n*50-22); line(50+70*i+30,100+n*50-25,50+70*i+33,100+n*50-22); getch(); if(i!=n-1)/*不是插在尾，新结点的后继指针线*/ line(50+70*i+61,100+n*50,50+70*i+65,100+n*50); line(50+70*i+65,100+n*50,50+70*i+65,100+n*50-25); line(50+70*i+65,100+n*50-25,50+70*i+62,100+n*50-22); line(50+70*i+65,100+n*50-25,50+70*i+68,100+n*50-22); getch(); setcolor(6); if(i!=-1)/*不是插在头，新结点前驱结点的后继指针线*/ line(50+70*i+20,100+n*50-25,50+70*i+20,110+n*50); line(50+70*i+20,110+n*50,50+70*i+34,110+n*50); line(50+70*i+34,110+n*50,50+70*i+31,110+n*50-3); line(50+70*i+34,110+n*50,50+70*i+31,110+n*50+3); getch(); if(i!=n-1) /*不是插在尾，新结点后继结点的前驱指针线*/ line(50+70*i+75,100+n*50-25,50+70*i+75,110+n*50); line(50+70*i+75,110+n*50,50+70*i+61,110+n*50); line(50+70*i+61,110+n*50,50+70*i+64,110+n*50-3); line(50+70*i+61,110+n*50,