数据结构实验：基于线性表的图书信息管理.doc

X X X X X 大 学11学年12学年第2学期数据结构实验报告书专 业： 班 级： 姓 名： 学 号： 实验地点： 计算中心B6机房 任课教师： 实验题目： 基于线性表的图书信息管理 实验环境： Visual Studio 6.0 实验目的：1、掌握线性表的定义；2、掌握线性表的基本操作，如建立、查找、插入和删除等。实验内容：1、必做分别定义一个包含图书信息（书号，书名，定价）的顺序表和链表，使其具有如下功能：(1) 从给定的文件book.txt逐个读入图书信息；(2) 逐个显示图书表中所有图书的相关信息；(3) 统计表中图书个数；(4) 输出图书价格最高的图书信息（考虑可能有多个）；(5) 计算所有图书的平均价格；(6) 根据书名进行查找，返回相应书名的图书的书号和定价（考虑重名情况）； (7) 根据指定的位置，返回相应位置的图书的全部信息；(8) 给定一本图书相关信息，插入到表中指定的位置，将插入后的结果重新写入文件book.txt；(9) 删除指定位置的图书记录，将删除后的结果重新写入文件book.txt；(10) 将图书表信息逆序存储，将逆序的图书信息存入文件book_inverser.txt中。2、选做（1）按照图书价格进行排序，将排序的结果以格式（定价，书号，书名）存入文件book_sort.txt中。（2）实现两个一元多项式的加法、减法、乘法运算。实现方法、实验结果及结论分析等：（一）实现方法1. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）/定义一个结构体Bookstruct Book /定义结构体char no30; /编码char name30; /书名int price; /价格;/顺序表的定义typedef struct LNode /定义顺序表struct Book *elem; /指向数据元素的基地址int length; /顺序表当前长度SqList;/链表的定义typedef struct LNode /定义链表struct Book data; /数据域struct LNode *next; /指针域LNode, *LinkList;/一元二次多项式的定义typedef struct PNodefloat coef; /参数int expn; /指数struct PNode *next; /指针域PNode, *Polynomial;2. 自定义函数的名称及其功能说明/函数声明（顺序表）Status InitList( SqList &L )； /顺序表初始化void Input( SqList &L )； /输入函数void Output( SqList L )； /输出函数void Count( SqList L )； /输出数据长度函数void pare( SqList L )； /比较价格函数void Average( SqList L )； /求平均价格函数void Search_name( SqList L )； /按名字查找图书信息函数void Search_no( SqList L )； /按输入图书位置查找图书信息void Insert( SqList &L )； /插入函数void Delete( SqList &L )； /删除函数void Inverse( SqList &L )； /逆转函数/函数声明（链表）Status InitList( LinkList &L )； /初始化链表void Input( LinkList &L )； /输入函数void Output( LinkList &L )； /输出函数void Count( LinkList L )； /输出数据个数的函数void pare( LinkList L )； /比较价格函数void Average( LinkList L )； /求平均价格函数void Search_name( LinkList L )； /按照书名查找图书信息的函数Status Search_no( LinkList L )； /按照输入位置查找图书信息Status Insert( LinkList &L )； /插入函数Status Delete( LinkList &L )； /删除函数Status Inverse( LinkList &L )； /逆序函数Status Sort( LinkList &L )； /排序函数/函数声明（一元多项式）Status InitPolyn( Polynomial &P )； /初始化一元多项式void CreatePolyn( Polynomial &P )； /创建一元多项式void CopyPolyn( Polynomial &P1, Polynomial &P2 )； /一元多项式的拷贝void AddPolyn( Polynomial &PA, Polynomial &PB )； /一元多项式相加函数void MinusPolyn( Polynomial &PA, Polynomial &PB )；/一元多项式相减void MultiplyPolyn( Polynomial &Pa, Polynomial &Pb )；/一元多项式相乘3. 主要功能算法的时间复杂度顺序表函数名称时间复杂度Status InitList( SqList &L )；/顺序表初始化O(1)void Input( SqList &L )；/输入函数O(n)void Output( SqList L )；/输出函数O(n)void Count( SqList L )； /输出数据长度函数O(1)void pare( SqList L )；/比较价格函数O(n)void Average( SqList L )；/求平均价格函数O(n)void Search_name( SqList L )；/按照书名查找O(n)void Search_no( SqList L )；/按照输入位置查找O(1)void Insert( SqList &L )；/插入函数O(n)void Delete( SqList &L )；/删除函数O(n)void Inverse( SqList &L )；O(n)链表函数名称时间复杂度Status InitList( LinkList &L )；/初始化链表O(1)void Input( LinkList &L )；/输入函数O(n)void Output( LinkList &L )；/输出函数O(n)void Count( LinkList L )；/输出数据个数的函数O(1)void pare( LinkList L )；/比较价格函数O(n)void Average( LinkList L )；/求平均价格函数O(n)void Search_name( LinkList L )；/按照书名查找O(n)Status Search_no( LinkList L )；/按照输入位置查找O(n)Status Insert( LinkList &L )；/插入函数O(n)Status Delete( LinkList &L )；/删除函数O(n)Status Inverse( LinkList &L )；/逆序函数O(n)Status Sort( LinkList &L )；/排序函数O(n*n)一元多项式函数名称时间复杂度Status InitPolyn( Polynomial &P )；/初始化一元多项式O(1)void CreatePolyn( Polynomial &P )； /创建一元多项式O(n)void CopyPolyn( Polynomial &P1, Polynomial &P2 )； O(n)void AddPolyn( Polynomial &PA, Polynomial &PB )；O(m+n)void MinusPolyn( Polynomial &PA, Polynomial &PB )； O(m+n)void MultiplyPolyn( Polynomial &Pa, Polynomial &Pb )； O(m*n*m*n)4. 实验任务书中要求画的流程图链表根据指定位置进行查找的算法流程图链表插入算法的流程图（二）实验结果1顺序表（1）菜单：当输入超出菜单所给的数字时出现提示（2）输出函数：输出全部图书信息（3）统计图书个数（4）找出价格最高的图书，并输出其信息。当出现多个价格同时最高的图书时依然可以正确输出 （5）求出所有图书的平均价格（6）按书名查找图书，并输出其信息；当没有此书时会有提示 （7）按照指定的位置查找图书信息，当输入非法时有提示 （8）在指定位置插入图书信息，当位置不合法或者空间不足时有提示 （9）删除指定位置的图书信息，当输入位置不合法是提示（10）图书信息逆序2. 链表（1）当输入超出菜单所给选项的数字时有提示 （2）输出所有的图书信息 （3）统计图书个数（4）查找价格最高的图书，如果有多本书同时为最高价可全部输出 （5）计算所有图书的平均价格 （6）按书名查找图书，可查找多本同名图书，当无查找书籍信息时有提示 （7）按输入位置查找图书信息，当位置不合法是有提示 （8）在指定位置插入信息，当位置不合法是有提示 （9）删除指定位置的图书信息，当位置不合法是有提示 （10）将所有图书信息逆序 （11）将所有图书信息按照价格由高到低排序3一元多项式（1）创建一元多项式（2）弹出菜单，当输入错误选项时有提示，还有选项可以跳出菜单（3）一元多项式相加（4）一元多项式相减 （5）一元多项式相乘 （三）结论分析1. 问题与解决方法在写菜单的代码时，我设法让菜单能够循环，但是也要有出口，所以选择了一个循环；在选择菜单选项时，由于选项较多，用if语句进行选择会套用多层if语句，而且对于非选项的数字处理也较麻烦，于是我选择了switch语句。但是要菜单不断重复，只是在选择退出菜单选项时停止循环，所以我选择了while循环语句，并让条件永远为真，当保存选项的变量为退出菜单选项时，用break终止循环。2. 收获和体会在一元多项式乘法运算的编写中，遇到了几个困难，我通过调试，逐步跟踪数据的变化，找到了出错位置，并及时改正。这让我进一步体会到了多重循环及判断语句套用时应注意的细节，以及指针的再次使用重赋值问题。与此同时，我对于调试也进一步熟悉起来，对于日后的程序编写检查错误积累了经验。3. 尚存在的问题对于步骤复杂的函数编写容易出错，程序的健壮性仍有欠缺，尤其是对于一元多项式的不同情况的问题应进一步改进。