数据结构报告.docx
《数据结构报告.docx》由会员分享,可在线阅读,更多相关《数据结构报告.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构报告
计算机与控制工程学院
课程设计
(数据结构与OOP)
设计题目:
1八皇后问题
2表达式的求值问题
3图书管理系统
班级
姓名
学号
指导教师
成绩
二○一四年六月二十九日
内容包括:
1、 课程设计题目:
1八皇后问题
2表达式求值问题
3图书管理系统
2、 课程设计内容:
1八皇后问题
八皇后问题,是一个古老而著名的问题。
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:
在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
2表达式求值问题
当用户输入一个合法的算术表达式后,能够返回正确的结果。
能够计算的运算符包括:
加、减、乘、除、括号;能够计算的操作数要求在实数范围内。
3图书管理系统
设计一个计算机管理系统完成图书管理基本业务。
基本要求
1)每种书的登记内容包括书号、书名、著作者、现存量和库存量;
2)对书号建立索引表(线性表)以提高查找效率;
3)系统主要功能如下:
*采编入库:
新购一种书,确定书号后,登记到图书帐目表中,如果表中已有,则只将库存量增加;
*借阅:
如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;
*归还:
注销对借阅者的登记,改变该书的现存量。
3、 算法设计:
1八皇后问题
1)主要的函数
(1)intprint_Chessboard(intchessboard[][8])
//打印的棋盘其中打印1的位置是皇后的位置,0空位。
这里因为在控制台看不到全部,所以做了在文件中输出所有的解
(2)intcheck_Chessboard(intchessboard[][8],introw,intcolumn)
//检测是否摆放成功,若皇后放入成功则返回1,失败则返回0首先查行数和列数是否已经超出棋盘的局限,若超出了说明前边都符合位置,此时返回成功系数1然后检查在这一列上是否有皇后,正上方最后检查在左上和右上斜对角上是否有皇后若以上3种情况检查后是成功的就循环的检查下一行的每个位置2)流程图
2表达式求值问题
1)数据类型设计
任何一个表达式都是由操作符,运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符。
栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置,base为栈底指针,在顺序栈中,它始终指向栈底,即top=base可作为栈空的标记,每当插入新的栈顶元素时,指针top增1,删除栈顶元素时,指针top减1。
typedefstruct
{char*base;
char*top;
intstacksize;
}SqStackchar;
typedefstruct
{
float*base;
float*top;
intstacksize;
}SqStackint;
2)概要说明
为实现上述程序功能
1.首先置操作数栈和运算符栈为空栈,
2.依次输入表达式中每个字符,若是操作数则进操作数栈;若是运算符,则进运算符栈。
最后以#作为表达式的结尾。
3.输入的运算符要判断优先级,以此来确定四则运算的先后顺序
3)判断运算符优先权,返回优先权高的。
算符间的优先关系如下:
+
-
*
/
(
)
#
+
>
<
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=
)
>
>
>
>
>
>
3)主要函数
//构造空栈
SqStackcharInitStackchar()
SqStackintInitStackint()
//进栈
SqStackcharPushchar(SqStackchar&S,charc)
SqStackintPushint(SqStackint&S,floatc)
//获得栈顶元素
charGetTopchar(SqStackcharS)
floatGetTopint(SqStackintS)
//出栈操作
charPopchar(SqStackchar&S)
floatPopint(SqStackint&S)
//判断该字符是数字的还是操作符
intIn(charc)
//运算函数
floatOperate(floata,chartheta,floatb)
//判断操作符的优先级
charPrecede(chara,charb)
3图书管理系统
1)数据类型
图书图书有很多信息需要描述,其中包含图书的编号、名称、作者、现有量、库存量,整个全部我们定义一个BK类型的结构体,该结构体定义的代码如下:
typedefstructbook
{
charbook_num[10];//图书编号
charbook_name[20];//图书名称
charbook_writer[10];//图书作者
intbook_xy;//现有量
intbook_kc;//库存量
structbook*next;
}BK;
借书信息其中包含借书书号、借书日期。
这里我们定义一个类型BO的结构体来描述他。
定义的结构体代码如下
typedefstructborrow
{
charborrow_book_num[10];//借书书号
charlimit_date[8];//借书日期
}BO;
读者读者有很多信息需要使用,其中包含读者的书证号、姓名、权限、最多借书量。
这里我们定义一个RD类型的结构体来描述他。
定义的结构体代码如下:
typedefstructreader
{
charreader_num[10];//读者书证号
charreader_name[10];//读者姓名
intright;
BOborrow[Max];//最多借书量
structreader*next;
}RD;
数据通过每个节点的“next”指针来链接,是单线性链表,只可以从头部查询数据,所以要记录好该链表的头结点位置,不要拿该节点的头结点参与运算,否则在程序中可能会修改该链表的头结点的信息,导致后续程序无法运行。
2)主要函数
voidLogin();//登陆界面
intMenu();//主菜单
voidInit();//初始化
voidMenu_select();//主菜单选择函数
voidInsert_New_Book();//新书入库
voidadd_reader();//添加读者
voidPrint_reader();//查询读者信息
voidPrint_book();//查询图书信息
voidBorrow_Book();//借书模块
voidReturn_Book();//还书模块
voidSave();//保存信息
voidSave_Book();//保存图书信息
voidSave_Reader();//保存读者信息
voidLoad();//加载信息
voidLoad_Reader();//加载读者信息
voidLoad_Book();//加载图书信息
3)流程图
进入系统后首先进行图书初始化,输入图书的信息。
初始化之后,进入系统,显示功能列表,可选择任意系统,但在借书之前先要输入读者信息。
采编入库
登记借书信息
查询图书信息
查询读者信息
还书
借阅图书
四 程序正确性验证(指边界测试数据,即程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果):
1八皇后问题程序运行时不需要输入其他数据,直接运行结果,结果显示正确。
由于在控制台看不到全部的结果,所以做了在文件中输出所有的解。
2表达式求值问题测试数据如下第一组测试:
第二组测试
第三组测试
第四组测试
3图书管理系统
5、 课程设计过程中出现的主要问题、原因及解决方法:
1对学过的知识掌握的不够牢固,通过看课本和查询资料又有了进一步的理解。
这次的程序设计中我运用了很多栈还有链表的知识。
2八皇后问题
开始的时候想到要用递归来实现皇后的摆放算法,但是如何编写程序却没有一点思路,然后通过阅读C++课本中递归那一章节的知识点和例题,还有数据结构教程中的一些运用了递归思想的算法,自己才有了一些思绪。
经过多次调试与修改,终于可以完成功能了
3表达式求值问题
这个程序中运用了栈的知识点,进栈、获得栈顶元素、出栈、构造空栈等,还要判断运算符的优先级。
在编写过程中容易出现一些参数没有定义或者重复定义的问题。
4图书管理系统
1)其中用到了对数据文件的操作,开始的时候,程序不可以运行,经过检查是文件的打开文件的方式不正确。
调整好后,发现文件显示数据乱码,原来是以二进制方式保存的,字无法显示,就乱码了。
不过系统的功能并没有因此而受到影响。
2)在运行程序时也遇到了一些问题,借书时只能借一本书,再借书就不能显示是借了还是不能借,把最多能借书的数量改了一下还是不行,最后在每一个判断输出之后都加了gotoend借书,就能正常借书了。
六 课程设计的主要收获:
这次课程设计是对我们所学知识的一次总结,也是一次检验,更是我们对我们自己的一次挑战。
通过本次课程设计,让我对数据结构这门学科对有了进一步的认识,掌握了链表和栈的基本操作和应用。
在这个过程中遇到了很多问题,自己开始没有思路还很烦恼,心情很是糟糕,但是静下心来想想没有做不到的事情只有愿不愿意去做而已。
之后凭借那闪现在眼前的点点思路,慢慢在琢磨,参考网上的一些资料大体的程序内容终于成型了。
然后一个一个函数的思考,一步一步的编写,调试,做起来也就越来越顺手了。
函数功能也得到了进一步的完善。
!
当然,我离将设计做得很完美的程度,还是存在非常之大的差距。
所以遇到问题要学会去解决,只有这样才能将事顺利办得越快越好。
这次课程设计,会为我以后步入社会留下宝贵的经验。
我相信在今后的学习真的我会更加努力,积累经验,使自己在编程等各方面得到提高。
七 对今后课程设计的建议:
我想说只有不断实践才是成功的关键!
从这次的锻炼中,我学到了很多东西。
所以我认为应该多一些上机实验的机会,这样才可以将理论与实践相结合。
当然,在设计过程中也遇到过不少的问题,每当遇到问题就必须自己去寻找解决的方案,在寻找解决方法的过程中也提升了自己应对问题的能力,进一步巩固了基础知识。
希望以后可以分组进行课程设计,这样不仅可以感受默契合作的重要性,而且可以从其他同学身上取长补短。
在今后的学习中,我们需要不断提高对自身的要求,及时掌握新的知识,多多参与实践,在实践中锻炼和提高自己的能力。