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

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 //定义结构体 { };

//顺序表的定义

typedef struct LNode //定义顺序表 {

struct Book *elem; //指向数据元素的基地址 int length; //顺序表当前长度 char no[30]; //编码 char name[30]; //书名 int price; //价格

}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 )；//顺序表初始化 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 )；//按照书名查找

时间复杂度 O(1) O(n) O(n) O(1) O(n) O(n) O(n) 时间复杂度 O(1) O(n) O(n) O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n)

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 )；

4. 实验任务书中要求画的流程图

⑴链表根据指定位置进行查找的算法流程图

开始O(n) O(n) O(n) O(n) O(n*n) 时间复杂度 O(1) O(n) O(n) O(m+n) O(m+n) O(m*n*m*n)

定义指向结点的指针变量p，并令p指向头结点定义整型变量i,n输入查找信息的位置n判断是否有位置n是i=0否p指向下一个结点i=i+1是i

开始定义指向结点的指针变量p、r，并令r指向头结点定义整型变量i，n输入插入图书信息的位置 …… 此处隐藏：1460字，全部文档内容请下载后查看。喜欢就下载吧 ……