X X X X X 大 学
11学年—12学年第2学期数据结构实验报告书
专    业：                      班    级：           
姓    名：                    学    号：             
实验地点： 计算中心B6机房     任课教师：             
实验题目：      基于线性表的图书信息管理             
实验环境：        Visual Studio 6.0                 
实验目的：
1、掌握线性表的定义；
2、掌握线性表的基本操作，如建立、查、插入和删除等。
实验内容：
1、必做
分别定义一个包含图书信息（书号，书名，定价）的顺序表和链表，使其具有如下功能：
(1) 从给定的文件逐个读入图书信息；
(2) 逐个显示图书表中所有图书的相关信息；
(3) 统计表中图书个数；
(4) 输出图书价格最高的图书信息（考虑可能有多个）；
(5) 计算所有图书的平均价格；
(6) 根据书名进行查，返回相应书名的图书的书号和定价（考虑重名情况）；
(7) 根据指定的位置，返回相应位置的图书的全部信息；
(8) 给定一本图书相关信息，插入到表中指定的位置，将插入后的结果重新写入文件；
(9) 删除指定位置的图书记录，将删除后的结果重新写入文件；
(10) 将图书表信息逆序存储，将逆序的图书信息存入文件中。
2、选做
（1）按照图书价格进行排序，将排序的结果以格式（定价，书号，书名）存入文件中。
（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 Compare( 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 Compare( 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 Compare( 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 Compare( 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）菜单：当输入超出菜单所给的数字时出现提示

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。