线性表

实验目的： 1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：分别定义一个包含图书信息（书号，书名，定价）的顺序表和链表，使其具有如下功能：

(1) 从给定的文件book.txt逐个读入图书信息；

(2) 逐个显示图书表中所有图书的相关信息；

(3) 统计表中图书个数；

(4) 输出图书价格最高的图书信息（考虑可能有多个）；

(5) 计算所有图书的平均价格；

(6) 根据书名进行查找，返回相应书名的图书的书号和定价（考虑重名情况）；

(7) 根据指定的位置，返回相应位置的图书的全部信息；

(8) 给定一本图书相关信息，插入到表中指定的位置，将插入后的结果重新写入文件book.txt；

(9) 删除指定位置的图书记录，将删除后的结果重新写入文件book.txt；

(10) 将图书表信息逆序存储，将逆序的图书信息存入文件book_inverser.txt中。

实现方法、实验结果及结论分析等：

顺序表：

#include

#include

#include //输出控制符setw()函数

#include

using namespace std;

#define SIZE 1000

typedef struct { //struct结构体将图书信息整在一起

char no[15]; //书号 数组大小至少比实际的大一，因为最后\\n

char name[50]; //书名

float price; //定价

}Book; //图书信息定义

typedef struct{

Book *BK; //指针

int length; //定义图书表的图书记录个数

}SqList;

void Input(SqList &L) //从book.txt 中读取图书数据

{

int i=0;

char BK_head1[10],BK_head2[10],BK_head3[10]; //定义数组串

L.BK=new Book[SIZE]; //申请内存空间

ifstream inFile(\"book.txt\"); //读入book的信息 文件输入流

if(!inFile)

{ //如果没有读入

cout<<\"Cannot open this file!\"<exit(1); //退出

}

inFile>>BK_head1>>BK_head2>>BK_head3;//读取文件中的标题

L.length=0;

while(!inFile.eof()) //逐行依次读取所有图书数据

{

inFile>>L.BK[i].no >>L.BK[i].name>>L.BK[i].price;

i++; //记录图书个数

}

L.length=i;

inFile.close();

cout<<\"\\n读取book.txt 信息完毕，可以通过选项(2)查看图书生信息\\n\"<}

void Output(SqList &L) //逐个显示图书表中所有图书的相关信息

{

for(int i=0;icout<<<\"\\"<cout<<\"\\n信息显示完毕\\n\"<//ofstream outFile(\"book_new.txt\");

//for( i=0;i//outFile<}

void Count_Len(SqList L) //统计表中图书个数

{

cout<<\"当前的图书总数为：\"<}

void max_price(const SqList &L)//输出图书价格最高的图书信息

{

float max ; //定义max

max=L.BK[0].price; //初始化

for(int i=0;iif(L.BK[i].price>=max) //如果后项比max大，则将其赋值给max

max=L.BK[i].price;

for(int i=0;iif(L.BK[i].price==max)

cout<}

float Count_Price(const SqList &L) //计算所有图书的平均价格；const 因为不修改

{

float sum = 0.0f;

float count_price;

for(int i=0; i{

sum += L.BK[i].price;

count_price = sum /L.length ;

}

cout<return 0;

}

Book* Search(const SqList &L) //根据书名进行查找，返回相应书名的图书的书号和定价 Book为指针类型

{

char *name;

name=new char[50]; //为指针动态分配内存

cout<<\"请输入要查找的书名:\";

cin>>name;

for(int i=0; i{

if(strcmp(name, L.BK[i].name) == 0) //比较字符串看是否相等来确定是否查找到

{

cout<<(L.BK+i)->name<<\"\\"<return L.BK+i;

//返回指针，指针对应着相应书名的书号和定价

}

}

cout<<\"没找到\"<delete [] name;

return 0;

}

void find_pos(SqList &L) //根据指定的位置，返回相应位置的图书的全部信息

{

int pos;

cout<<\"输入位置\"<while(1)

{

cin>>pos;

if(pos<1||pos>L.length)

cout<<\"输入错误，请重新输入\"; //如果输入的位置不在搜索范围内，则输出“输入错误”

else

break;

}

cout<}

void Insert(SqList &L) //给定一本图书相关信息，插入到表中指定的位置，将插入后的结果重新写入文件book.txt

{

int pos;

Book newbook;

cout<<\"输入需要插入的图书位置\"<while(1)

{

cin>>pos;

if(pos<1||pos>(L.length+1))

cout<<\"输入错误，请重新输入\";

else

break;

}

cout<<\"输入图书相关信息（书名，序号，价格）\";

cin>>newbook.name>>newbook.no>>newbook.price;

for(int i=L.length;i>pos-1;i--)

L.BK[i]=L.BK[i-1];

L.BK[pos-1]=newbook;

L.length++;

Output(L);

}

void delete_book(SqList &L) //删除指定位置的图书记录，将删除后的结果重新写入文件book.txt

{

int pos;

cout<<\"输入需要删除的图书位置\";

while(1){

cin>>pos;

if(pos<1||pos>L.length)

cout<<\"输入错误，请重新输入\";

else

break;

}

for(int i=pos;iL.BK[i-1]=L.BK[i];

L.length--;

Output(L);

}

void reverse(SqList &L) //将图书表信息逆序存储，将逆序的图书信息存入文件book_inverser.txt中

{

for(int i=0;iswap(L.BK[i],L.BK[L.length-1-i]); //交换函数 库函数

Output(L);

}

void main()

{

char no;

SqList L;

while(1)

{

cout<<\"**************************** 欢学使用图书信息管理系统！*************************\"<<\"\\n\";//菜单选项

cout<<\"(1)输入图书信息\"<<\"\\n\";

cout<<\"(2)逐个显示图书信息\"<<\"\\n\";

cout<<\"(3)统计表中图书个数\"<<\"\\n\";

cout<<\"(4)输出图书价格最高的图书信息\"<<\"\\n\";

cout<<\"(5)计算所有图书的平均价格\"<<\"\\n\";

cout<<\"(6)根据书名进行查找\"<<\"\\n\";

cout<<\"(7)根据指定位置进行查找\"<<\"\\n\";

cout<<\"(8)插入图书信息到指定位置\"<<\"\\n\";

cout<<\"(9)删除指定位置的图书记录\"<<\"\\n\";

cout<<\"(a)将图书表信息逆序存储\"<<\"\\n\"; //不能写，因为单个字符

cout<<\"(0)退出系统\"<<\"\\n\";

cout<<\"\\n\";

cout<<\"请选择您需要的服务:\";

cin>>no;

switch(no){

case '1':

Input(L);break;

case '2':

Output(L);break;

case '3':

Count_Len(L);break;

case '4':

max_price(L);break;

case '5':

Count_Price(L);break;

case '6':

Search(L);break;

case '7':

find_pos(L);break;

case '8':

Insert(L);break;

case '9':

delete_book(L);break;

case 'a':

reverse(L);break;

case '0':

cout<<\"欢迎再次使用~bye bye~\"<exit(0);break;

default :

cout<<\"请选择正确的操作！！\"<break;

//....

}

}

}

链表：

#include

#include

#include //输出控制符setw()函数

#include

using namespace std;

typedef struct {

char no[15];

char name[50];

float price;

}Book; //图书信息定义

typedef struct LNode{ //节点

Book data; //数据域

struct LNode *next; //指针域

}LNode,*LinkList;

int num;//记录图书个数

void Input(LinkList &L){ //从book.txt 中读取信息，前插法创建图书链表

char BK_head1[10],BK_head2[10],BK_head3[10];

LinkList p;

L=new LNode;

L->next=NULL;//初始化单链表

ifstream inFile(\"book.txt\");//读入book的信息 文件输入流

if(!inFile)

{

cout<<\"Cannot open this file!\"<exit(1); //退出

}

inFile>>BK_head1>>BK_head2>>BK_head3;//读取文件中的标题

num=0;

while(!inFile.eof()){ //逐行依次读取所有图书数据

p=new LNode; //生成新结点

inFile>>p->data.no>>p->data.name>>p->data.price;

p->next=L->next;

L->next=p; //插入到表头

num++; //记录图书个数

}

inFile.close();

cout<<\"文件读取完毕\"<inFile.close();

cout<<\"\\n读取book.txt 信息完毕，可以通过选项(2)查看图书信息\\n\"<}

void Output(LinkList &L){//逐个显示表中的信息

LinkList p;

p=L->next;

//for(int i=0;i// cout<data.no<<\"\\"<data.name<<\"\\"<data.score<// p=p->next;

//}

while(p){ //setw()函数,设置域宽

cout<data.no<<\"\\"<data.name<<\"\\"<data.price<p=p->next;

}

cout<<\"\\n信息显示完毕\\n\"<}

void Count_Len(LinkList L){ //统计表中图书个数

cout<<\"当前的图书总数为：\"<}

void max_price(const LinkList &L){ //输出图书价格最高的图书信息

LinkList p;

p=L->next;

if(p==NULL)

exit(1);

float max=p->data.price;

while(p!=NULL){

if(p->data.price>=max)

max=p->data.price;

p=p->next;

}

p=L->next;

while(p!=NULL){

if(p->data.price==max)

cout<data.name<<\"\\"<data.no<<\"\\"<data.price<p=p->next;

}

}

float Count_Price(const LinkList &L){ LinkList p;

float sum = 0.0f;

float count_price;

p=L->next;

if(p==NULL)

exit(1);

while(p!=NULL){

sum+=p->data.price;

//计算所有图书的平均价格

p=p->next;

}

count_price = sum /num ;

cout<return 0;

}

Book* Search(const LinkList &L) { 价 Book为指针类型

LinkList p;

p=L->next;

if(p==NULL)

exit(1);

string name;

cout<<\"请输入要查找的书名:\";

//根据书名进行查找，返回相应书名的图书的书号和定

cin>>name;

int flag=1;

while(p!=NULL)

{

if(p->data.name==name)

{

cout<data.name<<\"\\"<data.no<<\"\\"<data.price<flag=0;

}

p=p->next;

}

if (flag)

cout<<\"输入书名不存在\"<// 等同于

// if (flag==1)

// cout<<\"输入书名不存在\"<// else

// .....

}

void find_pos(LinkList &L) LinkList p;

p=L->next;

if(p==NULL) exit(1);

int pos;

while(1){

cout<<\"输入查找位置:\";

{ //根据指定的位置，返回相应位置的图书的全部信息

cin>>pos;

if(pos<1||pos>num)

cout<<\"输入错误，请重新输入\";

else

break;

}

for(int i=1;ip=p->next;

cout<data.name<<\"\\"<data.no<<\"\\"<data.price<}

void Insert(LinkList L){ //给定一本图书相关信息，插入到表中指定的位置，将插入后的结果重新写入文件book.txt

LinkList p=L;

LinkList newbook=new LNode; //new动态分配内存

int pos;

cout<<\"输入插入位置:\";

while(1)

{

cin>>pos;

if(pos<1||pos>num+1) //注意是num+1

cout<<\"输入错误，请重新输入\";

else

break;

}

cout<<\"输入图书信息（书名，序号，价格）:\";

cin>>newbook->data.name>>newbook->data.no>>newbook->data.price;

for(int i=1;ip=p->next;

newbook->next=p->next;

p->next=newbook;

num++; //此处与++num无区别，因为它不是在复合表达式中，而是一个语句

Output(L);

}

void delete_book(LinkList L){ //删除指定位置的图书记录，将删除后的结果重新写入文件book.txt

LinkList p=L;

LinkList book; //要删除的书

int pos;

if(p->next==NULL) //删除是找它的前驱结点，然后。。如果前驱结点的指针域为空，则退出

exit(1);

cout<<\"输入需要删除图书的位置:\";

while(1)

{

cin>>pos;

if(pos<1||pos>num)

cout<<\"输入错误，请重新输入\";

else

break;

}

for(int i=1;ip=p->next;

book=p->next;

p->next=book->next;

delete book;

num--;

Output(L);

}

void reverse(LinkList L){ //将图书表信息逆序存储，将逆序的图书信息存入文件book_inverser.txt中

LinkList p=L->next; //L为头指针,它指向表中第一个结点，此处p即为第一个结点

if(p==NULL) //表示头指针为空

exit(1);

LinkList q; //前插法创建单链表

L->next=NULL; //首先让L头指针指向空

while(p!=NULL)

{

q=p->next; //将L链表一个元素一个元素的取，将取出一个元素p后剩下的链表部分

先保存q中

p->next=L->next;

L->next=p; //将p插入到了L头指针后，即插入到了表头

p=q; //将上一步剩下的链表再赋给p，继续取链表头的第一个元素

}

Output(L);

}

void main(){

char no;

LinkList L;

while(1)

{

cout<<\"**************************** 欢学使用图书信息管理系统！*************************\"<<\"\\n\";//菜单选项

cout<<\"(1)输入图书信息\"<<\"\\n\";

cout<<\"(2)逐个显示图书信息\"<<\"\\n\";

cout<<\"(3)统计表中图书个数\"<<\"\\n\";

cout<<\"(4)输出图书价格最高的图书信息\"<<\"\\n\";

cout<<\"(5)计算所有图书的平均价格\"<<\"\\n\";

cout<<\"(6)根据书名进行查找\"<<\"\\n\";

cout<<\"(7)根据指定位置进行查找\"<<\"\\n\";

cout<<\"(8)插入图书信息到指定位置\"<<\"\\n\";

cout<<\"(9)删除指定位置的图书记录\"<<\"\\n\";

cout<<\"(a)将图书表信息逆序存储\"<<\"\\n\"; cout<<\"(0)退出系统\"<<\"\\n\";

cout<<\"\\n\";

cout<<\"请选择您需要的服务:\";

//不能写，因为单个字符

cin>>no;

switch(no){

case '1':

Input(L);break;

case '2':

Output(L);break;

case '3':

Count_Len(L);break;

case '4':

max_price(L);break;

case '5':

Count_Price(L);break;

case '6':

Search(L);break;

case '7':

find_pos(L);break;

case '8':

Insert(L);break;

case '9':

delete_book(L);break;

case 'a':

reverse(L);break;

case '0':

cout<<\"欢迎再次使用~bye bye~\"<exit(0);

default :

cout<<\"请选择正确的操作！！\"<break;

//....

}

}

}