课程设计《数据结构》.docx

上传人:b****1 文档编号:10743058 上传时间:2023-05-27 格式:DOCX 页数:38 大小:58.63KB
下载 相关 举报
课程设计《数据结构》.docx_第1页
第1页 / 共38页
课程设计《数据结构》.docx_第2页
第2页 / 共38页
课程设计《数据结构》.docx_第3页
第3页 / 共38页
课程设计《数据结构》.docx_第4页
第4页 / 共38页
课程设计《数据结构》.docx_第5页
第5页 / 共38页
课程设计《数据结构》.docx_第6页
第6页 / 共38页
课程设计《数据结构》.docx_第7页
第7页 / 共38页
课程设计《数据结构》.docx_第8页
第8页 / 共38页
课程设计《数据结构》.docx_第9页
第9页 / 共38页
课程设计《数据结构》.docx_第10页
第10页 / 共38页
课程设计《数据结构》.docx_第11页
第11页 / 共38页
课程设计《数据结构》.docx_第12页
第12页 / 共38页
课程设计《数据结构》.docx_第13页
第13页 / 共38页
课程设计《数据结构》.docx_第14页
第14页 / 共38页
课程设计《数据结构》.docx_第15页
第15页 / 共38页
课程设计《数据结构》.docx_第16页
第16页 / 共38页
课程设计《数据结构》.docx_第17页
第17页 / 共38页
课程设计《数据结构》.docx_第18页
第18页 / 共38页
课程设计《数据结构》.docx_第19页
第19页 / 共38页
课程设计《数据结构》.docx_第20页
第20页 / 共38页
亲,该文档总共38页,到这儿已超出免费预览范围,如果喜欢就下载吧!
下载资源
资源描述

课程设计《数据结构》.docx

《课程设计《数据结构》.docx》由会员分享,可在线阅读,更多相关《课程设计《数据结构》.docx(38页珍藏版)》请在冰点文库上搜索。

课程设计《数据结构》.docx

课程设计《数据结构》

《数据结构与算法设计》课程设计选题

数据结构课程设计实施方案

1、设计要求

本课程设计是为了配合《数据结构与算法设计》课程而开设的。

目的是通过设计一完整的程序,使学生掌握数据结构的应用、算法的编写。

能熟练地将算法转换成C程序,具有上机调试的基本能力。

为了达到上述目的,要求如下:

(1)要充分认识课程设计对学习软件编程的重要性,认真做好课程设计前的各项准备工作。

(2)既要虚心接受老师的指导,又要独立思考,充分发挥自己的主观能动性。

结合课题,努力钻研、勤于实践,勇于创新。

(3)独立按时完成规定的工作任务。

(4)在设计过程中,要严格要求自己,树立严肃、严密、严谨的科学态度,必须按时、按质、按量完成课程设计。

(5)小组成员之间要分工明确,但要保持联系畅通,密切合作,培养良好地相互帮助和团队协作精神。

2、适用专业

软件工程、计算机科学与技术、电子信息工程等工科专业。

3、课程设计的一般步骤

课程设计大体分5个步骤:

(1)选题与收集资料:

2-3人为一组进行选题,进行课程设计课题的资料收集。

(2)分析与概要设计:

根据收集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,在此基础上进行实现程序功能的算法设计。

(3)程序设计:

运用C语言编写程序,实现程序的各个模块功能。

(4)调试与测试:

自行调试程序,成员交叉测试程序,并记录测试情况。

(5)课程设计报告:

编写课程设计报告。

4、课程设计内容与要求

掌握课程设计的每个步骤,在此基础上设计出所要求的数据结构、功能模块和完整的主程序。

(1)完整的问题描述。

(2)程序所要完成的基本要求。

(3)算法实现(写出算法的基本思想)。

(4)程序实现(用C语言将算法实现)

5、上机任务

(1)选择合适的数据结构,并定义数据结构的结构体。

(2)根据程序所要完成的基本要求和程序实现提示,设计出完整的算法。

(3)设计出主程序(main函数),使其成为完整的程序

6、考核方式与成绩评定

课程设计结束,要进行验收与评分。

指导教师对每个小组所开发的系统及每个成员开发的模块进行综合验收,再结合设计报告,根据课程设计成绩的评定方法,评出课程设计的成绩。

设计报告与程序源码作为考核的内容,成绩计分按A+、A、B+、B、C+、C、D+、D、F五段九级评定。

实验内容分设计型基础实验、综合型实验、综合型课程设计项目三大类。

一、设计型基础实验

1.八皇后问题

2.k阶斐波那契序列,要求满足fn≤max而fn+1>max。

(循环队列的容量仅为k或k+1)

3.约瑟夫环:

编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。

一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。

报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止。

编程打印出列顺序。

4.按先序扩展序列建立二叉树

5.先序、中序、后序遍历的递归算法

6.中序遍历的非递归算法

7.先序遍历的非递归算法

8.后序遍历的非递归算法

9.层次的非递归算法

10.求二叉树的深度(后序遍历)

11.求树的深度

12.编写DFS算法的非递归函数

13.用普里姆(Prim)算法构造最小生成树

14.简单选择排序

15.折半插入排序

16.冒泡排序

17.顺序查找

18.折半查找

二、综合型实验

1.猴子选大王

2.迷宫求解(用二维矩阵定义迷宫)

3.回文游戏:

顺读与逆读字符串一样(不含空格)

4.地图四染色问题

5.原四则表达式求值(带圆括号的)

6.从原四则表达式求得后缀式

7.后缀表达式求值

8.从原四则表达式求得中缀表达式

9.从原四则表达式求得前缀表达式

10.前缀表达式求值

11.统计二叉树中叶子结点的个数

12.统计二叉树中度为1的结点的个数

13.统计二叉树中结点的总数

14.求二叉树的宽度(具有结点数最多的层上的结点数)

15.求树中的叶子结点数

16.已知二叉树中序遍历和后序遍历序列,求二叉树的二叉链表结构

17.已知二叉树中序遍历和先序遍历序列,求二叉树的二叉链表结构

18.编写BFS算法。

19.用克鲁斯卡尔(kruskal)算法构造最小生成树

20.快速排序

21.堆排序

22.按关键字输入顺序,建立二叉排序树,进行二叉查找。

三、综合型课程设计

课程设计一:

通信录管理系统

1、问题描述

通信录是人们日常生活中经常用到的通信管理工具,它以文件的方式保存用户录入的数据,并提供查询的功能供用户查询和使用通信录信息。

本设计要求用C语言实现的简易通信录管理系统,它支持基本的录入、删除、查找、修改和文件读写功能。

如图所示。

修改

删除

录入

列表

查找

程序结束

主菜单

初始化

 

图1.1通信录管理系统

2、功能描述

通信录要求实现最基本的功能,包括录入、删除、查找和修改,为此需要首先定义记录项的格式,其基本属性包括编号、姓名、性别、住址、联系电话等。

整个系统由如下几大功能模块组成:

(1)通信录的建立。

该模块主要完成将数据存入数组中的工作。

记录可以从文本形式存储的数据文件中读入,也可以从键盘逐个输入记录。

(2)通信录的查询。

用户可以按联系人的姓名或电话号码查询。

若找到满足查询条件的记录,则以表格的形式显示此记录的信息;否则,显示未找到记录的提示信息。

(3)通信录的维护。

实现对记录的修改、删除、插入和排序操作。

(4)通信录的输出。

实现屏幕显示和将数组中存储的记录信息写入数据文件中。

3、设计

(1)程序总体结构

程序主要包括三大模块:

输入输出模块、管理模块和文件操作模块。

输入输出模块的主要功能是人机交互,包括程序界面显示、用户输入响应、结果输出等;管理模块从输入输出模块读取用户命令并进行相应的操作,包括插入、删除、修改、查找、列表等;文件操作模块获取管理模块中的数据或命令,然后进行存储文件的读写,最后将结果返回给管理模块。

(2)界面设计

程序的主界面是一个文本方式的菜单,用户通过键盘输入数字,选取相应的操作指令。

(3)数据结构设计

通信录中的记录项用结构体TELEBOOK表示,包含4个属性:

NUM属性是记录项的唯一编号,NAME、PHONENUM、ADDRESS分别代表用户的姓名、联系电话和地址。

Typedefstructtelebook{

Charnum[4];

Charname[10];

Charphonenum[15];

Charaddress[20];

}telebook;

(4)功能函数设计

通信录程序采用结构化程序设计的思想。

程序中除了主函数外,共设计12个函数:

1)printheader()

函数原型:

voidprintheader()

功能:

用于以表格形式显示记录时,打印输出表头信息。

2)printdata()

函数原型:

voidprintdata(TELEBOOKpp)

功能:

用于以表格形式显示记录时,打印输出单个数组元素PP中的记录信息。

3)disp()

函数原型:

voiddisp(TELEBOOKtemp[],intn)

功能:

用于显示temp数组中存储的n条记录,内容为telebook结构中定义的内容。

4)stringinput()

函数原型:

voidstringinput(char*t,intlens,char*notice)

功能:

stringinput()函数用于输入字符串,并进行字符串长度验证(长度

notice用于保存printf()中输出的提示信息。

5)locate()

函数原型:

intlocate(TELEBOOKtemp[],intn,charfindmess[],charnameorphonenum[])

功能:

locate()函数用于单位数组中符合要求的元素,并返回该数组元素的下标值。

参数findmess[]保存要查找的家庭信息,nameorphonenum[]表示按姓名或电话号码字段在数组temp中查找。

6)add()

函数原型:

intadd(TELEBOOKtemp[],intn)

功能:

add()函数用于在数组temp中增加电话簿记录,并返回数组中的当前记录数。

7)qur()

函数原型:

voidqur(TELEBOOKtemp[],intn)

功能:

qur()函数用于在数组temp中按姓名或电话号码查找满足条件的记录,并显示出来。

8)del()

函数原型:

intdel(TELEBOOKtemp[],intn)

功能:

del()函数用于在数组temp中找到满足条件的记录,然后删除该记录。

9)modify()

函数原型:

voidmodify(TELEBOOKtemp[],intn)

功能:

modify()函数用于在数组temp中修改记录。

10)insert()

函数原型:

intinsert(TELEBOOKtemp[],intn)

功能:

insert()函数用于在数组temp中插入记录,并返回数组中的当前记录数。

11)selectsort()

函数原型:

voidselectsort(TELEBOOKtemp[],intn)

功能:

selectsort()函数利用选择排序算法在数组temp中完成数组的升序排序。

12)save()

函数原型:

voidsave(TELEBOOKtemp[],intn)

功能:

save()函数将电话薄数组temp中的n个元素写入磁盘数据文件中。

课程设计二、电子投票系统

功能需求描述如下:

分投票人模块和管理员模块两部分

1、投票人主要功能模块

(1)投票人的投票方式:

在系统提示符下输入要选举的候选人编号,即可完成投票。

(2)投票人了解候选人的方式:

浏览候选人列表、输入序号查询候选人介绍。

2、管理员模块的主要功能

(1)初始化候选人信息:

在系统投入使用前先将需要投票选举的候选人信息录入系统中,以便投票和查看。

即将候选人的序号、姓名和简介等录入系统。

(2)浏览候选人简介:

管理员有权浏览候选人简介,浏览的顺序按照候选人序号进行。

(3)修改候选人简介:

当候选人信息有变化时,输入候选人序号对其信息进行修改。

(4)查询投票情况:

管理员有权查询当前各个候选人得票情况,以便得出最终被选出的候选人信息。

(5)清除投票信息:

当投票工作结束后,管理员选择清除投票信息,即清除系统中所有候选人的票数,使之归零。

(6)安全管理:

管理员可以对投票人进行管理,投票人只有用管理员规定的用户名和密码才能进入系统进行投票。

管理员还可以更改用户名、密码和权限,并对投票人信息进行增加、删除、查询、排序和初始化等操作。

课程设计三、家庭财务管理系统

家庭财务管理系统是为用户进行家庭成员的收支构成及信息管理的应用软件。

功能描述如下:

(1)用户登录:

系统根据家庭成员的用户名和密码登录后,根据权限判断该家庭成员是家长还是普通成员,不同成员可以使用不同的功能。

普通成员的用户只有浏览权限而不能进行实质性改动。

(2)给家庭成员提供功能选择界面:

不同的家庭成员对应不同的功能选择界面。

功能选择界面包括输入功能选项、调用相应程序两大需求。

管理员和普通用户对应的功能选择界面是不同的。

(3)创建收支选项文件:

根据提示用户输入家庭成员的序号、姓名、各项财务信息,如收入、支出、合计。

可一次性输入多条家庭成员的收支信息。

系统将家庭成员收支信息记录存储在系统磁盘中,以便进行管理、查找和备份。

(4)增加家庭成员收支信息:

可在原有收支信息的基础上增加新的家庭成员财务信息记录,保存在磁盘上,将增加后的文件存储状态显示给用户。

在增加新家庭成员收支记录的过程中,系统提示输入收入、支出两个财务构成项,最终合计,要求系统自动计算获得,并同样作为财务构成项存入文件对应的记录中。

(5)删除家庭成员收支信息:

提示用户输入要进行删除操作的家庭成员序号,如果在文件中有该家庭成员的收支信息存在,则将该序号所对应的姓名、序号、各种收入构成等在对应文件中加以删除,由系统提示是否继续删除操作,家长可进行多次删除操作。

(6)修改家庭成员收支信息:

提示用户输入要进行修改操作的家庭成员序号,如果在文件中有该家庭成员的收支信息存在,则提示用户输入该序号对应的家庭成员姓名、收入和支出构成等相应修改的选项,并将修改结果存储在文件中。

该部分需求也要提示用户选择是否进行修改操作。

修改操作中的合计部分,也需要由系统修改后的收入、支出项目自动计算修改后的合计财务数额,并连同用户输入的其他修改项一起存入磁盘文件中。

(7)查询家庭成员财务情况:

分为根据姓名和序号分别进行查询两种情况,分别提示用户输入要查询家庭成员信息的序号或姓名,如果在磁盘文件中有对应的家庭成员财务信息,则提示用户已找到,并逐项列出该家庭成员的收支状态。

在该功能中,也需要提示用户是否需要继续查找,如果不再继续查找,则返回主界面。

(8)家庭成员收支排行浏览:

要求根据家庭成员的合计项进行排行,以便用户对家庭成员收入状况有较直观方便的了解。

由于在磁盘存储的家庭成员收支文件可能有多个,所以提示用户要浏览的具体文件名,然后根据合计项从大到小进行排列,显示家庭成员序号、姓名和各项财务构成。

(9)家庭成员管理:

家长对普通家庭成员的管理也需要进行家庭成员的创建、增加、删除、修改和浏览,家长创建的家庭成员记录存储在“用户”的磁盘文件中,每当有家庭成员登录系统时,系统都会根据该文件中的用户名和密码进行核实判断,用户才能顺利登陆,家长还具有增加新家庭成员的功能。

新增家庭成员的登陆名、密码及权限等也被继续存储在用户文件中。

当某些家庭成员不再使用该系统时,还可以进行删除操作,并且家长具有修改家庭成员权限的功能。

课程设计四:

航空客运订票系统

1、问题描述:

航空客运订票的业务活动包括:

查询航线和客票预订的信息、客票预订和办理退票等事项。

设计一个计算机程序,使上述任务能借助计算机来完成。

2、系统必须存储的数据信息

(1)航线信息:

飞机抵达城市、航班号、飞机号、起降时间、航班票价、票价分析、总位置、剩余位置、已订票的客户名单。

(2)客户信息:

客户姓名、证件号、座位号。

3、系统能实现的操作和功能

(1)承办订票业务:

根据客户提出的要求(飞机抵达城市、起降时间、订票数量)查询该航班信息(包括票价、折扣和剩余位置),若满足要求,则为客户办理订票手续,输出座位号。

(2)查询功能:

1)查询航班信息:

根据降落地点、输出航班号、飞机号、起降时间、航班票价、票价折扣和剩余位置等信息。

2)查询客户预订信息:

根据客户证件号,输出航班号、房间号、座位等信息。

课程设计五:

学生成绩管理系统

1、问题描述

学生成绩管理系统是学校教学工作中处理学生信息的工具。

它利用计算机实现学生成绩信息管理工作的系统化与自动化,提高工作效率。

本课程设计要求使用单链表作为存储结构,用C语言实现学生成绩管理系统,它支持基本的录入、删除、查找、修改、统计和文件的读写功能。

2、功能描述

整个系统由以下几大功能模块组成:

(1)输入记录:

学生纪录由学生的基本信息和成绩信息字段组成。

该模块主要完成将数据存入单链表中。

记录可以从二进制形式存储的数据文件读入,也可以从键盘逐个输入记录。

(2)查询记录:

用户可以按照学生的姓名或学号在单链表中查找。

若找到满足查询条件的记录,则返回指向该学生记录的指针;否则,返回值为NULL的空指针,显示未找到记录的提示信息。

(3)更新记录:

实现对指定姓名或学号的学生信息进行修改、删除、插入和排序操作。

(4)统计记录:

完成对各门功课最高分和不及格人数的统计功能。

(5)输出记录:

实现屏幕显示单链表中的记录信息和将单链表中存储的记录信息写入数据文件的功能。

3、设计

(1)界面设计

程序的主界面是一个文本方式的菜单,用户通过键盘输入数字,选取相应的操作指令。

(2)数据结构设计

1)学生成绩信息结构体

结构体student用于存储学生的基本信息,作为单链表的数据域。

Typedefstructstudent

{

Charnum[10];/*学号*/

Charname[15];/*姓名*/

Intcgrade;/*课程一成绩*/

Intmgrade;/*课程二成绩*/

Integrade;/*课程三成绩*/

Inttotal;/*总成绩*/

Floataverage;/*平均成绩*/

};

2)单链表node结构体

next为单链表的指针域,结构体student作为单链表的数据域。

Typedefstructnode

{

Structstudentdata;

Structnode*next;

}node,*link;

(3)功能函数设计

程序中除了主函数外,共设计13个函数。

1)printheader()

函数原型:

voidprintheader()

功能:

用于在以表格形式显示记录时,打印输出表头信息。

2)printdata()

函数原型:

voidprintdata(node*pp)

功能:

用于在以表格形式显示记录时,打印输出单链表中某一结点pp的记录信息。

3)display()

函数原型:

voiddisplay(linkL)

功能:

用于显示单链表L中存储的学生记录,内容为student结构中定义的内容。

4)stringinput()

函数原型:

voidstringinput(char*t,intlens,char*notice)

功能:

用于输入字符串,并进行字符串长度验证(长度

Notice用于保存printf()中输出的提示信息。

5)insert()

函数原型:

voidinsert(linkL)

功能:

用于在单链表L中增加学生纪录。

6)query()

函数原型:

voidquery(linkL,charfindmess[],charnameorphonenum[])

功能:

用于在单链表L中按姓名或学号查找满足条件的记录,nameorphonenum[]存储要查找的学生姓名或学号,findmess[]保存查找到的学生信息。

7)delete()

函数原型:

voiddelete(linkL,charnameorphonenum[])

功能:

用于在单链表L中找到满足条件的记录,然后删除该记录。

nameorphonenum[]存储要删除的学生姓名或学号。

8)modify()

函数原型:

voidmodify(linkL)

功能:

用于在单链表L中修改记录。

9)tongji()

函数原型:

voidtongji(linkL)

功能:

用于在单链表L中统计总分第一名、单科第一名、平均成绩最低的学生信息和各科不及格人数。

10)numberinput()

函数原型:

intnumberinput(char*notice)

功能:

用于输入数值型数据,Notice用于保存printf()中输出的提示信息,该函数返回用户输入的整型数据。

11)sort()

函数原型:

voidsort(linkL)

功能:

用于在单链表L中利用插入排序算法实现单链表按总分字段降序排序。

12)save()

函数原型:

voidsave(linkL)

功能:

用于将单链表L中的数据写入磁盘的数据文件中。

课程设计六:

停车场管理系统

1、问题描述

假设停车场只有一个可停放几辆汽车的狭长通道,并且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达的先后顺序依次排列,如果停车场内已停满汽车,则后来的汽车只能在门外的便道上等候,一旦停车场内有车开走,排在便道上的第一辆车即可进入;当停车场内某一辆车要离开时,在它之后开入的车辆必须先退出车场为它让路,待该车辆开出大门后,为它让路的车辆再按原次序进入停车场。

每辆汽车在离开时,都要依据停留时间交费(从进入便道开始计时)。

在这里假设汽车不能从便道上开走,试设计这样一个停车场的模拟管理系统。

2、基本要求

(1)汽车的输入信息格式为(到达/离开的标志,汽车当前状态标志,汽车牌照号码,到达/离开的时刻)

(2)对于不合理的输入信息应提供适当的提示信息。

3、数据结构设计

(1)为了便于区分每辆汽车并了解当前每辆汽车所处的位置,需要记录汽车的牌照号码和汽车当前的状态,所以为汽车定义一个新的类型CAR,具体定义如下:

Typedefstruct

{

Char*license_plate;/*汽车牌照号码,定义为一个字符指针类型*/

Charstate;/*汽车当前的状态,字符S表示是停放在停车位上,字符

P表示停放在便道上,每辆车的初始状态用字符i表示*/

}CAR

(2)由于停车是一个狭长的通道,所以不允许两辆车同时进入停车场。

当有车到来要进入停车位时要依次停放,当某辆车要离开时,比它后到的车要先暂时离开停车位,而且越后到的车就越先离开停车位,显然这和栈的“后进先出”特点相吻合,所以可以用一个栈来描述停车场。

由于停车场只能停放有限的几辆车,为了便于停车场的管理,要为每个车位分配一个固定的编号,不妨设为1、2、3、4、5等,分别表示1号停车位、2号停车位、3号停车位、4号停车位、5号停车位,这与数组的下标相吻合,所以针对这种情况,使用一个顺序栈比较方便。

具体定义如下:

#defineMAX_STOP5

Typedefstruct

{

CARstop[MAX_STOP];

Inttop;

}STOPPING;

(3)当停车场的停车位上都已经停满了汽车,又有新的汽车到来时要把它调度到便道上,便道上的车辆要按照进入便道的先后顺序顺次停放在便道上,为便道上的每个位置也分配一个固定的编号,当有车从停车位离开后,便道上的第一辆汽车就立即进入停车位上的某个车位,由于问题描述中限制了便道上的汽车只能从便道上开走,即便道上的汽车只能在停车位上停放过后才能离开停车位,这样越早进入便道的汽车就越早进入停车位,而且每次进入停车位的汽车都是处于便道“最前面”的汽车,显然,这和队列的“先进先出”特点吻合,所以这里使用一个顺序队列来描述便道,可以利用数组的下标表示便道的位置。

具体定义如下:

#defineMAX_PAVE100

Typedefstruct

{

CARPAVE[MAX_PAVE];

Intfront,rear;

}PAVEMENT;

(4)当某辆车要离开停车场的时候,比它后进的停车位的车要为它让路,而且当它开走之后让路的车还要按原来的停放次序再次进入停车位的某个车位上,为了完成这项功能,再定义一个辅助栈,停车位中让路的车依次“压入”辅助栈,待提出开出请求的车开走后再从辅助栈的栈顶依次“弹出”到停车

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 工程科技 > 能源化工

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2