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

《885191317数据结构课程设计报告双链表创建与演示设计.doc》由会员分享，可在线阅读，更多相关《885191317数据结构课程设计报告双链表创建与演示设计.doc（24页珍藏版）》请在三一办公上搜索。

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 -一、 需求分析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 ERROR;

15、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 OK;三、

16、详细设计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&i!=-

18、1)不是头指针也不是尾指针时： 画前驱指针； 画后继指针； 擦掉所画的指针线；3.3输出已排序双链表类C代码 void PrLink(linky p,int n) while(p!=NULL) 输出随机产生的数据；if(p-left!=NULL) /*第一个节点不显示前驱指针*/ 画前驱指针； if(p-right!=NULL) 画后继指针； p=p-right;进入3.画出各函数的调用关系图、主要函数的流程图。调用Inintlist(void)调用prink(p ,n) p=NULLs-datadata Y Y Y调用Drawchange(s-data,n-1,n)调用Drawchange(

19、s-data,t,n) N调用Drawchange(s-data,q-num,n)调用Prlink(head,n)Closr(void)具体Inintlist(void)函数的流程图：四、 调试分析以及设计体会1 程序调试中遇到的问题以及解决问题的方法。主要是在结点插入判断方面有难度，一开始不能准确的进行结点的判断和插入，然后就是插入结点的过程中位置不对，不是递增有序的，后面在网上找到了一段演示代码，通过研究这段代码解决了这个问题。还有就是在显示指针变化方面有问题，经过查询资料，解决结点插入方面的问题，用画箭头的方式来表现指针的变化。2课程设计过程经验教训、心得体会。在进行本次课程设计的实验操

20、作中，由于自己的基础知识不是很好，出现了一些问题：在编程方面不熟，所以写出的代码总是出错；数据结构课程以前也没有好好学过，造成在构建程序数据结构时出现由于概念模糊而写错功能的问题。但是在老师和同学们的帮助下，再通过查阅资料，最后终于写出了可以正确运行结果的代码，所以要感谢给我帮助的老师和同学。以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一

21、种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。通过这次课程设计，使我意识到作为一个计算机系的学生，正确掌握一门程序语言和数据结构的重要性，想要在程序设计上面作出成绩，必须要有扎实的编程语言基础和良好的数据结构算法知识，我决定在余下的在校时间里，认认真真学一门语言，并去详细了解程序的算法设计。五、 使用说明本程序是演示程序，在运行后按任意键即执行演示过程，可直观的看到程序运行时双链表指针的变化情况，为方便观察结果

22、，在程序运行的时候，按一下执行一步，也可以通过按Q键来退出程序，也可以在等待所有过程结束后再退出。1进入程序后界面：2随机产生结点，图中已产生2个结点，由于57大于1，所以没有右指针3指针变化情况4完成一个链表创建，下一结点插入中5所有步骤完成后程序显示界面，可清晰看到排序后的双链表结果六、 附录源程序清单#include stdlib.h#include graphics.htypedef struct Link/*双链表结点定义*/ int data; struct Link *right; struct Link *left; int num;/*给链表加序号,为了演示时计算正确位置*/

23、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) /*建立双向链表,边建立边

24、插入*/ linky head,p,q,s; int n=0; char str5; randomize();/*随机数发生机*/ 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);/*将数字转换成字符串并输

25、出*/ 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; sp

26、rintf(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-n

27、um+; q=q-right; else/*其他情况*/ while(s-datap-data&p!=NULL) q=p; 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

28、,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); se

29、tcolor(RED);/*插入链表的新数据用红色显示*/ sprintf(str,%d,data); 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,

30、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

31、*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,5

32、0+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,50+70*i+64,110+n*50+3); getch(); setcolor(WHITE); if(i!=n-1&i!

33、=-1)/*第一个节点和最后一个结点不恢复指针*/ line(50+70*i+35,100+(n-1)*50,50+70*i+65,100+(n-1)*50);/*画前驱指针*/ line(50+70*i+35,100+(n-1)*50,50+70*i+40,95+(n-1)*50); line(50+70*i+35,110+(n-1)*50,50+70*i+65,110+(n-1)*50);/*画右指针*/ line(50+70*i+65,110+(n-1)*50,50+70*i+60,115+(n-1)*50); bar(0,100+(n-1)*50+21,640,120+n*50);/*

34、擦掉插入过程的指针线*/void PrLink(linky p,int n)/*每次插入后输出链表*/ char str5; while(p!=NULL)/*不为空就输出*/ sprintf(str,%d,p-data); setcolor(GREEN); outtextxy(55+70*p-num,100+n*50,str); /*输出数据*/ setcolor(WHITE); if(p-left!=NULL)/*第一个节点不显示左指针*/ line(50+70*(p-num-1)+35,100+n*50,50+70*(p-num-1)+65, 100+n*50);/*画左指针*/ line

35、(50+70*(p-num-1)+35,100+n*50,50+70*(p-num-1)+ 40,95+n*50); if(p-right!=NULL) line(50+70*p-num+35,110+n*50,50+70*p-num+65,110+n*50);/*画右指针*/ line(50+70*p-num+65,110+n*50,50+70*p-num+60,115+n*50); p=p-right; void Init(void)/*图形驱动*/ int gd=DETECT,gm; initgraph(&gd,&gm,c:tc); cleardevice();void Close(void)/*图形关闭*/ getch(); closegraph();参考文献a) 严蔚敏，吴伟民， 数据结构（C语言版），北京：清华大学出版社，2005b) 严蔚敏，吴伟民， 数据结构题集（C语言版），北京：清华大学出版社，2003c) 郭翠英 等 C语言课程设计案例精编，北京：水利水电出版社，2004计算机与通信学院课程设计评分表课程名称： 双链表创建演示 项 目评 价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩 教师签名： 日 期： （注：1此页附在课程设计报告之后；2综合成绩按优、良、中、及格和不及格五级评定。）