《数据结构 课程设计》指导书 2014版 外专业.doc

数据结构 课程设计指导书一、课程名称及编号数据结构课程设计 028060二、学时与学分 学时：1周 学分：1.0三、教学对象 层次：本科 专业：计算机科学与技术、软件工程专业四、先修课程 C语言、C+语言、数据结构五、教学目的与任务数据结构课程设计是理解和掌握数据结构的重要环节，主要任务是实现各种数据组织中的数据逻辑结构，存储结构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养学生的数据抽象能力和软件设计的能力。通过全部过程培养和锻炼学生的钻研能力、动手能力、分析问题和解决问题的实际能力。六、主要内容数据结构课程设计的内容可根据专业要求和具体情况有授课老师进行选择和推荐。为了鼓励学生的创造精神和开放性设计，应容许学生进行自拟选题，但应按照先申报再实现的流程。部分选题如下，任课老师还应本着创新、提高、结合实际和科研等因素不断推出新的选题。开发平台推荐如下：BORLAND C、C+、C+ BUILDER。题目推荐：1. 带头结点的双向链表的常见操作。要求从文件读入数据，结果显示的同时也要放入文件。2. 利用栈计算表达式。3. 利用队列进行任务排队的效果演示软件。4. 文本文件统计软件。5. 三元组代表的稀疏矩阵进行运算。6. 某种数据结构常用功能图形演示软件7. 中国三十个大城市之间的最短路径求解。8. 中国三十个大城市之间的通信网最小生成树求解。9. 索引结构的软件实现。10. 平衡二叉树的常见操作。11. 哈弗曼二叉树的实际应用。12. 通过使用字符串的KMP算法编写出一个英语单词联想输入系统。单词量要求为初三前要求的近三千个词汇。13. 各种数据结构在windows下编程实现图形界面的设计。14. 多项式求导15. 马踏棋盘16. 停车场模拟软件17. 稀疏矩阵的加法18. 家族关系查询系统19. 各种利用数据结构实现的游戏软件七、基本要求由于数据结构属于基础类核心课程，故每个题目要求单人独立完成。最终的系统要求可以正常运行，要求制作的各类文档齐全，能回答系统开发中的关键问题。系统界面简洁，使用方便，功能齐全，数据结构的设计合理规范，存储结构的设计高效正确。在完成课题验收后，每位学生应在规定的时间内上交数据结构课程设计说明书一份、源代码和相关数据文件。设计说明书要求图文并茂，结构合理，对系统的数据结构设计和功能设计进行全面地描述，有收获和经验教训等。（约3000字）设计报告格式一、 设计题目二、 设计目的三、 总体设计四、 详细设计五、 设计结果与分析六、 总结（收获和不足）八、考核方式按平时开发过程监控、现场问答、源码阅读、报告评审等环节进行验收，根据验收情况和课程设计说明书的质量综合给出成绩。成绩分为优、良、中、及格、不及格五级评分制，基本评分标准涉及的方面如下：1. 课程设计任务完成情况、工作量大小、系统的难度和原创性。2. 系统的整体设计、数据结构和存储结构设计是否合理高效。是否有多种方案比较，容错机制。3. 系统界面是否简洁大方，方便用户使用。4. 资料制作是否完整系统美观。5. 进度控制是否符合要求。九、时间安排本课程设计安排为一周时间进行，可以在期末，也可以在期初。十、部分参考源码/功能：多链表基本功能操作演示#include /c+输入和输出等 如cout#include /c输入和输出等 如getch#include /窗口类操作，系统调用如清屏等#include /文件读写操作#include /控制输出流格式const MAXNUMOFBASE=10; /基础数据总量const MAXSIZE=10; /设置链表总量enum returninfosuccess,fail,overflow,underflow,range_error;/定义错误类型清单class interfacebase; / interfacebase类的申明/*开始图形界面*/const char * begin_file= ,/1 ,/2 数据结构课程设计 ,/3 ,/4 多链表基本功能操作 ,/5 ,/6 功能介绍： ,/7 1.实现多组链表数据的显示、修改、插删、增值、反转和排序。 ,/8 2.对非空文件中多组嵌套括号和逗号的数据进行读入操作。 ,/9 3.对系统中的多组数据以括号嵌套的方式写入文件。 ,/10 4.系统中可容纳的链表的总是由作者确定。 ,/11 5.及时将系统中的残余结点空间释放。 ,/12 6.数据的输入有两种方式：文件读取和从键盘输入。 ,/13 7.实验退出时，系统中的所有非空链表的数据全部保存在文件中。 ,/14 8.实验演示过程中，链表中的数据以结点链接的形式显示出来。 ,/15 ,/16 ,/17 注意事项： ,/18 1.文件中无数据时不能进行数据读入操作，否则会死机。 ,/19 2.系统内部的链表序号是从1开始到最大限的数字。 ,/20 3.显示所有链表时，L:表示第二号位置的链表数据。 ,/21 4.针对具体链表进行操作完成后会立即显示该链表的相关信息。 ,/22 ,/23 ,/24 制作：* ,/25 田田田| - 时间：*年*月 - ,/26 ,/27 ,/28;/*开始界面函数*/void begin_face()for(int j=0;j28;j+) coutsetw(5) begin_filejendl; Sleep(50); cout 提示：此时系统最多可以容纳MAXSIZE个链表，其序号为：1 MAXSIZE !endl;coutendl 阅读完毕，请按任意键继续.next=NULL; /头结点的地址域预设为空地址count=0; /计数器清零，表明开始时没有实际数据linklist:linklist() /析构函数 clearlist(); /删除所有数据，释放所有结点delete headp; /把头结点也释放掉count=0; /计数器清零，表明开始时没有实际数据returninfo linklist:create(int number)node *searchp=headp,*newnodep;int i,idataMAXNUMOFBASE;cout请依次从键盘输入number个数据（用空格隔开）：;for(i=0;iidatai; for (i=0;idata=idatai; newnodep-next=NULL;searchp-next=newnodep;searchp=searchp-next;count+;searchp-next=NULL; traverse();return success;void linklist:clearlist(void) /清空链表node *searchp=headp-next,*followp=headp; /初始化两个指针 while(searchp!=NULL) followp=searchp;searchp=searchp-next;delete followp; headp-next=NULL; /保留了最后一个结点，就是头结点，并且链域置为空count=0; /计数器也清零bool linklist:empty(void)const /是否空链if(headp-next=NULL) return true;elsereturn false;int linklist:size(void)const /求链表的长度return count; void linklist:traverse(void) /遍历某个链表中的所有元素node *searchp; /启用搜索指针if(empty()cout链表目前为空，没有数据可以显示!请按任意键继续.next;cout ; /提示显示数据开始while(searchp!=NULL) /循环显示所有数据cout data; if (searchp-next=NULL) cout |; else cout;searchp=searchp-next;coutendl链表长度为：countnext; /启用搜索指针cout ; /提示显示数据开始while(searchp!=NULL) /循环显示所有数据cout data; if (searchp-next=NULL) cout |; else cout;searchp=searchp-next;coutendl; /最后有一个回车的控制returninfo linklist:retrieve(int position, int &item) const /读取一个结点 if(empty() /处理意外return underflow;if(position=count+1) /处理意外return range_error;node *searchp=headp-next; /定义搜索指针，初始化for(int i=1; inext; /顺序访问方式，用循环，算法复杂度是O(n)item=searchp-data; /返回读取的数据return success; /本次操作成功returninfo linklist:replace(int position,const int &item) /修改一个结点if(empty() return underflow;if(position=count+1)return range_error;node *searchp=headp-next;for(int i=1; inext; searchp-data=item; /实际修改数据的语句traverse();return success;returninfo linklist:insert(int position,const int &item) /插入一个结点if(empty() return underflow;if(position=count+2) return range_error; node *newnodep=new node, *searchp=headp-next, *followp=headp;for(int i=1; inext; newnodep-data=item; /给数据赋值 newnodep-next=followp-next; /注意此处的次序相关性followp-next=newnodep;count+; /计数器加一traverse();return success;returninfo linklist:remove(int position) /删除一个结点 if(empty()return underflow;if(position=count+1)return range_error;node *searchp=headp-next,*followp=headp; /这里两个指针的初始值设计一前一后for(int i=1; inext; followp-next=searchp-next; /删除结点的实际语句delete searchp; /释放该结点 count-; /计数器减一traverse();return success;returninfo linklist:addnumber(int number) /链表所有数据增加number值node *searchp=headp-next; if(empty()return underflow;while(searchp!=NULL)searchp-data+=number;/将链表数据加上被加值numbersearchp=searchp-next;traverse();return success;returninfo linklist:invertlist(void) /链表所有数据反转规定必须要用栈，此处采用链栈方法node *top,*searchp,*newnodep,*followp;/定义一个栈，栈顶指针为topsearchp=headp-next;top=new node;top-next=NULL;while(searchp!=NULL) /进栈操作newnodep=new node;newnodep-data=searchp-data; newnodep-next=top-next; top-next=newnodep;searchp=searchp-next;clearlist(); /释放空间searchp=headp;top=top-next;while(top!=NULL) /出栈操作followp=top;newnodep=new node;newnodep-data=top-data;newnodep-next=NULL;searchp-next=newnodep;searchp=searchp-next;top=top-next; /改动栈顶指针的位置delete followp; /释放残余结点空间count+;searchp=searchp-next;traverse();return success;returninfo linklist:upinturn(void) /链表所有数据按升序排序node *followp,*searchp=headp-next; if(empty()return underflow;int i,j,item;for(i=0;inext;followp=searchp;searchp=searchp-next;for(j=0;jdata=searchp-data)item=followp-data;followp-data=searchp-data;searchp-data=item;followp=searchp;searchp=searchp-next;traverse();return success;/class interfacebase /定义一个基本操作interfacebase类private:linklist listonfaceMAXSIZE;int num; /选择需要操作的链表public:void clearscreen(void);void showmenu(void);int userchoice(void);bool write(void); /写文件操作bool read(void); /读文件操作returninfo processmenu(int menuchoice);void interfacebase:clearscreen(void) system(cls);void interfacebase:showmenu(void) cout 多链表基本功能操作菜单 endl; cout=endl;cout1.从文件中读取数据（将非空文件中数据读出）endl; cout2.输入数据（由键盘输入某一链表数据）endl; cout3.显示数据（遍历全部非空链表数据）endl; cout4.修改数据（要提供位置和新值）endl; cout5.插入数据（要提供位置和新值）endl; cout6.删除数据（要提供位置）endl;cout7.数据加值（全部数据都加值）endl;cout8.数据反转（全部数据逆序存储）endl;cout9.数据排序（全部数据升序排序）endl; cout0.结束程序（全部数据将保存在文件中）endl;cout=endl;int interfacebase:userchoice(void)int menuchoice;coutmenuchoice;return menuchoice;bool interfacebase:write(void) /文件写操作/文本文件形式ofstream out(结果文件.txt);if(!out)return false; elsefor(int i=0;inext;if(listonfacei.count!=0)out( ; /先写入(符号for (int j=0;jlistonfacei.count;j+)outdata;if(jlistonfacei.count-1)out, ;elseout )next;/关闭文件流out.close();return true;bool interfacebase:read() /文件读操作/文本文件形式ifstream in(演示结果.txt);if(!in)return false; elsewhile (!in.eof()char no;int idata;node *newnode,*searchp;for(int i=0;ino; /先读(while ( no!=) /当读出)时结束读入操作in idata no;newnode=new node;newnode-data=idata;newnode-next=NULL;searchp-next=newnode;searchp=searchp-next;listonfacei.count+;/关闭文件流in.close();return true;returninfo interfacebase:processmenu(int menuchoice)int position,item,returnvalue,i;switch(menuchoice) /根据用户的选择进行相应的操作case 1:read();/读文件操作for(i=0;iMAXSIZE;i+)if(!(listonfacei.empty()coutLi+1:;listonfacei.alltraverse(); /将从文件中读出的数据全部显示出来coutendl从文件中读取数据成功!请按任意键继续.endl;break;case 2:coutnum;cout请问你要输入数据的个数（不得超过MAXNUMOFBASEitem;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1;returnvalue=listonfacenum.create(item); if(returnvalue=success)cout建立链表操作成功!请按任意键继续.endl;break;case 3:for(i=0;iMAXSIZE;i+)if(!(listonfacei.empty()coutLi+1:;listonfacei.alltraverse(); cout系统中所有非空链表遍历操作成功!请按任意键继续.endl;break;case 4:coutnum;coutposition;coutitem;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1; /由于链表是数组存储，实际位置减1得到逻辑位置returnvalue=listonfacenum.replace(position,item);if(returnvalue=underflow) cout对不起，链表已空!请按任意键继续.endl;else if(returnvalue=range_error)cout对不起，修改的位置超出了范围!请按任意键继续.endl;elsecout修改操作成功!请按任意键继续.endl;break;case 5:coutnum;coutposition;coutitem;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1; returnvalue=listonfacenum.insert(position,item);if(returnvalue=underflow) cout对不起，链表已空!请按任意键继续.endl;else if(returnvalue=range_error)cout对不起，插入的位置超出了范围!请按任意键继续.endl;elsecout插入操作成功!请按任意键继续.endl;break;case 6:coutnum;coutposition;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1; returnvalue=listonfacenum.remove(position);if(returnvalue=underflow) cout对不起，链表已空!请按任意键继续.endl;else if(returnvalue=range_error)cout对不起，删除的位置超出了范围!请按任意键继续.endl;elsecout删除操作成功!请按任意键继续.endl;break;case 7:coutnum;coutitem;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1; returnvalue=listonfacenum.addnumber(item);if(returnvalue=underflow) cout对不起，链表已空!请按任意键继续.endl;else cout此链表所有元素加值操作成功!请按任意键继续.endl; break;case 8:coutnum;if(numMAXSIZE|num0)cout对不起，你输入的链表位置有误!endl;elsenum=num-1; returnvalue=listonfacenum.invertlist();if(returnvalue=underflow) cout对不起，链表已空!请按任意键继续.endl;else cout此