数据结构实验：基于线性表的图书信息管理.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. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）
//定义一个结构体Book
struct Book //定义结构体
{
char no[30]; //编码
char name[30]; //书名
int price; //价格
};
//顺序表的定义
typedef struct LNode //定义顺序表
{
struct Book *elem; //指向数据元素的基地址
int length; //顺序表当前长度
}SqList;
//链表的定义
typedef struct LNode //定义链表
{
struct Book data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
//一元二次多项式的定义
typedef struct PNode
{
float 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. 尚存在的问题
对于步骤复杂的函数编写容易出错，程序的健壮性仍有欠缺，尤其是对于一元多项式的不同情况的问题应进一步改进。