BJFU数据结构C语言第二版课后OJ练习链表部分

目录

• • • 214、基于链式存储结构的图书信息表的创建和输出
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
        • AC 代码
    • 215、基于链式存储结构的图书信息表的排序
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 216、基于链式存储结构的图书信息表的修改
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 217、基于链式存储结构的图书信息表的逆序存储
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 218、基于链式存储结构的图书信息表的最贵图书的查找
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 219、基于链式存储结构的图书信息表的最爱图书的查找
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 220、基于链式存储结构的图书信息表的最佳位置图书的查找
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 221、基于链式存储结构的图书信息表的新图书的入库
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码
    • 222、基于链式存储结构的图书信息表的旧图书的出库
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • 输入样例 2
        • 输出样例 2
        • AC 代码
    • 223、基于链存储结构的图书信息表的图书去重
    • • • 描述
        • 输入
        • 输出
        • 输入样例 1
        • 输出样例 1
        • AC 代码

214、基于链式存储结构的图书信息表的创建和输出 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后统计图书表中的图书个数，同时逐行输出每本图书的信息。

输入

输入n+1行，其中前n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。最后第n+1行是输入结束标志：0 0 0（空格分隔的三个0）。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计n+1行，第1行是所创建的图书表中的图书个数，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔。其中价格输出保留两位小数。

输入样例 1

9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
0 0 0

输出样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

AC 代码

前插法：

#include 
#include 

using namespace std;

struct Book // 创建书类数据类型
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode // 创建结点类型
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

bool InitList(linkList &L) // 注意这里的参数等价于LNode * &L,返回值为bool值表示状态
{
    L = new LNode;
    L -> next = NULL;
    return true; // 表示初始化成功
}

int main()
{
    // 1、创建一个链表（先创建一个头结点），用linkList用来强调这是一个链表
    linkList L; 
    
    // 2、初始化链表
    InitList(L);
    
    // 3、前插法创建单链表(注意创建完后是倒序)
    int cnt = 0;
    while (1)
    {
        LNode *tmp1;
        tmp1 = new LNode;
        cin >> tmp1 -> data.ibsn >> tmp1 -> data.name >> tmp1 -> data.price;
        
        if (tmp1 -> data.price == 0) break;
        
        tmp1 -> next = L -> next;
        L -> next = tmp1;
        
        cnt ++;
    }
    
    cout << cnt << endl;
    // 4、循环倒序输出
    while (cnt --)
    {
        LNode *tmp2;
        tmp2 = new LNode;
        tmp2 = L -> next;
        for (int i = 0; i < cnt; i ++) // 注意是循环cnt次，目的是使得指针最后指向尾结点
            tmp2 = tmp2 -> next;
        
        cout << tmp2 -> data.ibsn << " " << tmp2 -> data.name << " ";
        printf("%.2lfn", tmp2 -> data.price);
    }
    
    return 0;
}

尾插法：

AC 代码

#include 
#include 

using namespace std;

struct Book // 创建书类数据类型
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode // 创建结点类型
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

bool InitList(linkList &L) // 注意这里的参数等价于LNode * &L,返回值为bool值表示状态
{
    L = new LNode;
    L -> next = NULL;
    return true; // 表示初始化成功
}

int main()
{
    // 1、创建一个链表（先创建一个头结点），用linkList用来强调这是一个链表
    linkList L; 
    
    // 2、初始化链表
    InitList(L);
    
    // 3、尾插法创建单链表(注意创建完后是正序)
    int cnt = 0;
    
    LNode *r; // 创建尾指针
    r = new LNode;
    r = L;
    while (1)
    {
        LNode *tmp1; // 创建临时结点
        tmp1 = new LNode;
        
        cin >> tmp1 -> data.ibsn >> tmp1 -> data.name >> tmp1 -> data.price;
        
        if (tmp1 -> data.price == 0) break;
        
        tmp1 -> next = NULL;
        r -> next = tmp1;
        r = tmp1;

        cnt ++;
    }
    
    cout << cnt << endl;

    LNode *tmp2; // 创建输出使用的临时指针
    tmp2 = new LNode;
    tmp2 = L -> next;
    
    // 4、正序输出
	while(tmp2 != r -> next) // 注意，是遍历到r -> next,即尾结点后面那个结点，因为tmp2 = tmp2 -> next 在cout语句后面
	{
		cout << tmp2 -> data.ibsn << " " << tmp2 -> data.name << " ";
        printf("%.2lfn", tmp2 -> data.price);
		tmp2 = tmp2 -> next;
	}
    
    return 0;
}
z

215、基于链式存储结构的图书信息表的排序 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后统计图书表中的图书个数，同时逐行输出每本图书的信息。

输入

输入n+1行，其中前n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。最后第n+1行是输入结束标志：0 0 0（空格分隔的三个0）。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计n+1行，第1行是所创建的图书表中的图书个数，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔。其中价格输出保留两位小数。

输入样例 1

9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
0 0 0

输出样例 1

9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787302164340 Operating-System 50.00
9787822234110 The-C-Programming-Language 38.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257646 Data-Structure 35.00
9787302219972 Software-Engineer 32.00

AC 代码

#include 

using namespace std;

struct Book // 创建书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode // 创建结点
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数,通过头结点指向空
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建链表函数
void createList_tail(linkList &L, int &cnt)
{
    LNode *r; // 创建尾指针，使得尾指针一开始指向头结点
    r = new LNode;
    r = L;
    

    while (1)
    {
        LNode *tmp1; // 创建一个临时结点
        tmp1 = new LNode;
        cin >> tmp1 -> data.ibsn >> tmp1 -> data.name >> tmp1 -> data.price;
        
        if (tmp1 -> data.price == 0) break;
        
        tmp1 -> next = NULL;
        r -> next = tmp1;
        r = tmp1;
        
        cnt ++;
    }
}

// 输出函数
void show(linkList L)
{
    LNode *tmp2;
    tmp2 = new LNode;
    tmp2 = L -> next;
    
    while (tmp2)
    {
        cout << tmp2 -> data.ibsn << " " << tmp2 -> data.name << " ";
        printf("%.2lfn", tmp2 -> data.price);
        tmp2 = tmp2 -> next;
    }
}

// 降序的冒泡排序
void listSort(linkList &L, int cnt)
{
    LNode *tmp3;
    
    for (int i = 0; i < cnt; i ++)
    {
        int j = 0;
        tmp3 = L -> next; // 由于第一个结点是最大的，因此，每次冒泡排序的开始都应该是从头开始
        
        while (tmp3 && j < cnt -i - 1)
        {
            if (tmp3 -> data.price < tmp3 -> next -> data.price)
            {
                Book t = tmp3 -> data;
                tmp3 -> data = tmp3 -> next -> data;
                tmp3 -> next -> data = t;
            }
            
            j ++;
            
            tmp3 = tmp3 -> next;
        }
    }
}

int main()
{
    // 1、创建链表（通过创建一个头结点）并初始化
    linkList L;
    InitList(L);
    
    // 2、利用尾插法进行创建一个链表（注意是正序输出）
    int cnt = 0;
    createList_tail(L, cnt);
    
    // 3、进行排序，利用双指针的冒泡排序
    listSort(L, cnt);
    
    // // 4、进行正序输出
    show(L);
    
    return 0;
}

216、基于链式存储结构的图书信息表的修改 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后统计图书表中的图书个数，同时逐行输出每本图书的信息。

输入

输入n+1行，前n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。最后第n+1行是输入结束标志：0 0 0（空格分隔的三个0）。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计n+1行，第1行是修改前所有图书的平均价格，后n行是价格修改后n本图书的信息，每本图书信息占一行，书号、书名、价格用空格分隔。其中价格输出保留两位小数。

输入样例 1

9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
0 0 0

输出样例 1

43.88
9787302257646 Data-Structure 42.00
9787302164340 Operating-System 55.00
9787302219972 Software-Engineer 38.40
9787302203513 Database-Principles 43.20
9787810827430 Discrete-Mathematics 43.20
9787302257800 Data-Structure 68.20
9787811234923 Compiler-Principles 68.20
9787822234110 The-C-Programming-Language 45.60

AC 代码

#include 

using namespace std;

struct Book // 建立书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建函数
void createList_tail(linkList &L, int &len, double &sum) // len是指长度
{
    LNode *tail;
    tail = new LNode;
    tail = L;                               // 创建尾指针，一开始指向头结点
    
    while (1)
    {
        LNode *tmp;                         // 创建一个临时结点
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
        
        if (tmp -> data.price == 0) break; // 情况特判
    
        sum += tmp -> data.price;           // 算出总价格
    
        tmp -> next = NULL;
        tail -> next = tmp;
        tail = tmp;
        
        len ++;
    }
}

// 改变价格函数
void changePrice(linkList &L, double ave)
{
    LNode *p;
    p = new LNode;
    p = L;
    
    while (p)
    {
        if (p -> data.price < ave) p -> data.price *= 1.2;
        else p -> data.price *= 1.1;
        p = p -> next;
    }
}

// 输出函数
void show(linkList L)
{
    LNode *tmp2;
    tmp2 = new LNode;
    tmp2 = L -> next;
    
    while (tmp2)
    {
        cout << tmp2 -> data.ibsn << " " << tmp2 -> data.name << " ";
        printf("%.2lfn", tmp2 -> data.price);
        tmp2 = tmp2 -> next;
    }
}

int main()
{
    // 1、通过创建一个头结点创建链表
    linkList L;
    
    // 2、通过将头结点指向NULL进行初始化
    InitList(L);

    // 3、利用尾插法建立链表
    int len = 0;
    double sum = 0;
    createList_tail(L, len, sum);
    
    // 4、按照题意改变价格
    double ave = sum / len;
    printf("%.2lfn", ave);
    changePrice(L, ave);
    
    // 5、输出
    show(L);
    
    return 0;
}

217、基于链式存储结构的图书信息表的逆序存储 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后将读入的图书逆序存储，逐行输出逆序存储后每本图书的信息。

输入

输入n+1行，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计n行，第i行是原有图书表中第n-i+1行的图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔。其中价格输出保留两位小数。

输入样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

输出样例 1

9787822234110 The-C-Programming-Language 38.00
9787811234923 Compiler-Principles 62.00
9787302257800 Data-Structure 62.00
9787810827430 Discrete-Mathematics 36.00
9787302203513 Database-Principles 36.00
9787302219972 Software-Engineer 32.00
9787302164340 Operating-System 50.00
9787302257646 Data-Structure 35.00

AC 代码

#include 

using namespace std;

struct Book // 建立书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建函数
void createList_tail(linkList &L, int n) // len是指长度
{
    LNode *tail;
    tail = new LNode;
    tail = L;                           
    
    while (n --)
    {
        LNode *tmp;                         // 创建一个临时结点
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
    
        tmp -> next = NULL;
        tail -> next = tmp;
        tail = tmp;
        
    }
}

// 输出函数
void show(linkList L, int n)
{

    
    while (n --)
    {
        LNode *tmp2;
        tmp2 = new LNode;
        tmp2 = L -> next;
        
        for (int i = 0; i < n; i ++)
            tmp2 = tmp2 -> next;
        
        cout << tmp2 -> data.ibsn << " " << tmp2 -> data.name << " ";
        printf("%.2lfn", tmp2 -> data.price);
    }
}

int main()
{
    // 1、通过创建一个头结点创建链表
    linkList L;
    
    // 2、通过将头结点指向NULL进行初始化
    InitList(L);

    // 3、利用尾插法建立链表
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、按照题意改变价格
    // double ave = sum / len;
    // printf("%.2lfn", ave);
    // changePrice(L, ave);
    
    // 5、逆序输出
    show(L, n);
    
    return 0;
}

218、基于链式存储结构的图书信息表的最贵图书的查找 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后查找价格最高的图书，输出相应图书的信息。

输入

总计输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计输出m+1行，其中，第一行是最贵图书数目（价格最高的图书可能有多本），后m行是最贵图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，其中价格输出保留两位小数。

输入样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

输出样例 1

2
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00

AC 代码

#include 

using namespace std;

struct Book // 建立书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建函数
void createList_tail(linkList &L, int n) 
{
    LNode *tail;
    tail = new LNode;
    tail = L;                           
    
    while (n --)
    {
        LNode *tmp;                         // 创建一个临时结点
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
    
        tmp -> next = NULL;
        tail -> next = tmp;
        tail = tmp;
    }
}

void listSort(linkList &L, int n)                                                   // 冒泡排序
{
    LNode * tmp;
    
    for (int i = 0; i < n; i ++)
    {
        tmp = L -> next;
        
        int j = 0;
        while (tmp && j < n - i - 1)
        {
            if (tmp -> data.price < tmp -> next -> data.price)
            {
                Book t = tmp -> data;
                tmp -> data = tmp -> next -> data; 
                tmp -> next -> data = t;
            }
            
            j ++;
            tmp = tmp -> next;
        }
    }
}


// 输出函数
void show(linkList L, int n)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    int count = 0;                                                                  // 存储最贵图书数量
    n -= 1;                                                                         // 由于tmp是从首元结点开始遍历，因此需要先减去 1
    while (n --)
    {
        if (tmp -> data.price == tmp -> next -> data.price)                         // 注意这里不要用浮点数的相等判断，因为输入的值时固定的
            count ++;
        tmp = tmp -> next;
    }
 
    
    cout << count << endl;
    while (count --)
    {
        cout << L -> next -> data.ibsn << " " << L -> next -> data.name << " ";
        printf("%.2lfn", L -> next -> data.price);   
        L = L -> next;
    }
}

int main()
{
    // 1、通过创建一个头结点创建链表
    linkList L;
    
    // 2、通过将头结点指向NULL进行初始化
    InitList(L);

    // 3、利用尾插法建立链表
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、进行降序排序
    listSort(L, n);
    
    // 5、输出最贵图书信息
    show(L, n);
    
    return 0;
}

219、基于链式存储结构的图书信息表的最爱图书的查找 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后根据指定的最爱图书的名字，查找最爱的图书，输出相应图书的信息。

输入

总计n+m+2行。首先输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。然后输入m+1行，其中，第一行是一个整数m，代表查找m次，后m行是每次待查找的最爱图书名字。

输出

若查找成功： 总计输出m*（k+1）行，对于每一次查找，第一行是最爱图书数目（同一书名的图书可能有多本），后k行是最爱图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，其中价格输出保留两位小数。 若查找失败： 只输出以下提示：抱歉，没有你的最爱！

输入样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
2
Java-Programming-Language
Data-Structure

输出样例 1

Sorry，there is no your favourite!
2
9787302257646 Data-Structure 35.00
9787302257800 Data-Structure 62.00

AC 代码

#include 

using namespace std;

struct Book // 建立书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建函数
void createList_tail(linkList &L, int n) 
{
    LNode *tail;
    tail = new LNode;
    tail = L;                           
    
    while (n --)
    {
        LNode *tmp;                         // 创建一个临时结点
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
    
        tmp -> next = NULL;
        tail -> next = tmp;
        tail = tmp;
    }
}

// 输出最爱图书函数
void findFavorite(linkList L, string name, int n)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    int count = 0;                                                                  // 存储最爱图书数量
    n -= 1;                                                                         // 由于tmp是从首元结点开始遍历，因此需要先减去 1
    while (n --)
    {
        if (tmp -> data.name == name)                                               
            count ++;
        tmp = tmp -> next;
    }
 
    if (!count)                                                                     // 表示没有找到最爱图书
    {
        cout << "Sorry，there is no your favourite!" << endl;
        return ;                                                                    // 函数返回值类型类void
    }
    else
    {
        cout << count << endl;
        
        LNode *tmp1;
        tmp1 = new LNode;
        tmp1 = L -> next;
        
        while (tmp1)                                                                // 遍历
        {
            if (name == tmp1 -> data.name)
            {
                cout << tmp1 -> data.ibsn << " " << tmp1 -> data.name << " ";
                printf("%.2lfn", tmp1 -> data.price);                   
            }
            tmp1 = tmp1 -> next;
        }
    }
}

int main()
{
    // 1、通过创建一个头结点创建链表
    linkList L;
    
    // 2、通过将头结点指向NULL进行初始化
    InitList(L);

    // 3、利用尾插法建立链表
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、输入最爱图书
    int t;
    cin >> t;
    while (t --)
    {
        string name;
        cin >> name;
        
        findFavorite(L, name, n);
    }
    
    return 0;
}

220、基于链式存储结构的图书信息表的最佳位置图书的查找 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后根据指定的最佳位置的序号，查找该位置上的图书，输出相应图书的信息。

输入

总计n+m+2行。首先输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。然后输入m+1行，其中，第一行是一个整数m，代表查找m次，后m行每行内容为一个整数，代表待查找的图书的位置序号。

输出

输出m行 若查找成功： 输出内容为第i次查询的指定位置上的一本图书的信息（书号、书名、价格），书号、书名、价格用空格分隔，其中价格输出保留两位小数。 若查找失败： 只输出以下提示：抱歉，最佳位置上的图书不存在！

输入样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
2
2
0

输出样例 1

9787302164340 Operating-System 50.00
Sorry，the book on the best position doesn't exist!

AC 代码

#include 

using namespace std;

struct Book // 建立书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool InitList(linkList &L)
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法创建函数
void createList_tail(linkList &L, int n) 
{
    LNode *tail;
    tail = new LNode;
    tail = L;                           
    
    while (n --)
    {
        LNode *tmp;                         // 创建一个临时结点
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
    
        tmp -> next = NULL;
        tail -> next = tmp;
        tail = tmp;
    }
}

// 查找函数
void find(linkList L, int site, int n)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    if (site < 1 || site > n)               // 不合法位置
    { 
        cout << "Sorry，the book on the best position doesn't exist!" << endl;
        return ;
    }
    
    site -= 1;
    while (site --)
        tmp = tmp -> next;

    cout << tmp -> data.ibsn << " " << tmp -> data.name << " ";
    printf("%.2lfn", tmp -> data.price);    
}

int main()
{
    // 1、通过创建一个头结点创建链表
    linkList L;
    
    // 2、通过将头结点指向NULL进行初始化
    InitList(L);

    // 3、利用尾插法建立链表
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、输入查找位置
    int t;
    cin >> t;
    while (t --)
    {
        int site;
        cin >> site;
        find(L, site, n);        
    }
    
    return 0;
}

221、基于链式存储结构的图书信息表的新图书的入库 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后根据指定的待入库的新图书的位置和图书的信息，将新图书插入到图书表中指定的位置上，最后输出新图书入库后的所有图书的信息。

输入

总计n+3行。首先输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。之后输入第n+2行，内容仅为一个整数，代表待入库的新图书的位置序号。最后输入第n+3行，内容为新图书的信息，书号、书名、价格用空格分隔。

输出

若插入成功： 输出新图书入库后所有图书的信息（书号、书名、价格），总计n+1行，每行是一本图书的信息，书号、书名、价格用空格分隔。其中价格输出保留两位小数。 若插入失败： 只输出以下一行提示：抱歉，入库位置非法！

输入样例 1

7
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
2
9787822234110 The-C-Programming-Language 38.00

输出样例 1

9787302257646 Data-Structure 35.00
9787822234110 The-C-Programming-Language 38.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00

AC 代码

#include 

using namespace std;

struct Book                                                 // 定义书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode                                        // 定义结点数据类型
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool Init(linkList &L)                                      // 创建头结点并使头结点指向空
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法
void createList_tail(linkList &L, int n)                    // 利用尾插法得到链表，记得尾指针
{
    LNode *tail;
    tail = new LNode;
    tail = L;
    
    while (n --)
    {
        LNode *tmp;
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
        tail -> next = tmp;
        tmp -> next = NULL;
        tail = tmp;
    }
    
}

// 输出整个链表
void show(linkList L)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    while (tmp)                                             // 遍历
    {
        cout << tmp -> data.ibsn << " " << tmp -> data.name << " ";
        printf("%.2lfn", tmp -> data.price);
        tmp = tmp -> next;
    }
}

void add(linkList &L, int site, int n)
{
    if (site < 1 || site > n)                               // 情况特判
    {
        cout << "Sorry，the position to be inserted is invalid!" << endl;
        return ;
    }
    
    LNode *tmp;
    tmp = new LNode;
    tmp = L;
    
    site -= 1;
    while (site --)                                         // 先遍历找到待插入的位置
        tmp = tmp -> next;
        
    LNode *tmp1;                                            // 先改右指向，再改左指向
    tmp1 = new LNode;
    cin >>  tmp1 -> data.ibsn >> tmp1 -> data.name >> tmp1 -> data.price;
    
    tmp1 -> next = tmp -> next;
    tmp -> next = tmp1;
    
    show(L);                                                // 输出整个链表(内嵌函数)
}

int main()
{
    // 1、通过头结点创建一个链表
    linkList L;
    
    // 2、初始化
    Init(L);
    
    // 3、插入
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、进行入库
    int site;
    cin >> site;
    add(L, site, n);
    
    return 0;
}

222、基于链式存储结构的图书信息表的旧图书的出库 描述

定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建，然后根据指定的待出库的旧图书的位置，将该图书从图书表中删除，最后输出该图书出库后的所有图书的信息。

输入

总计n+2行。首先输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格。其中书号和书名为字符串类型，价格为浮点数类型。之后输入第n+2行，内容仅为一个整数，代表待删除的旧图书的位置序号。

输出

若删除成功： 输出旧图书出库后所有图书的信息（书号、书名、价格），总计n-1行，每行是一本图书的信息，书号、书名、价格用空格分隔。其中价格输出保留两位小数。 若删除失败： 只输出以下一行提示：抱歉，出库位置非法！

输入样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
2

输出样例 1

9787302257646 Data-Structure 35.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

输入样例 2

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00
9

输出样例 2

Sorry，the position to be deleted is invalid!

AC 代码

#include 

using namespace std;

struct Book                                                 // 定义书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode                                        // 定义结点数据类型
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool Init(linkList &L)                                      // 创建头结点并使头结点指向空
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法
void createList_tail(linkList &L, int n)                    // 利用尾插法得到链表，记得尾指针
{
    LNode *tail;
    tail = new LNode;
    tail = L;
    
    while (n --)
    {
        LNode *tmp;
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
        tail -> next = tmp;
        tmp -> next = NULL;
        tail = tmp;
    }
    
}

// 输出整个链表
void show(linkList L)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    while (tmp)                                             // 遍历
    {
        cout << tmp -> data.ibsn << " " << tmp -> data.name << " ";
        printf("%.2lfn", tmp -> data.price);               
        tmp = tmp -> next;
    }
}

void remove(linkList &L, int site, int n)
{
    if (site < 1 || site > n)                               // 情况特判
    {
        cout << "Sorry，the position to be deleted is invalid!" << endl;
        return ;
    }
    
    LNode *tmp;
    tmp = new LNode;
    tmp = L;
    
    site -= 1;
    while (site --)                                         // 先遍历找到待删除的位置
        tmp = tmp -> next;
        
    tmp -> next = tmp -> next -> next;                      // 只需要将next向后直接指两位，等价于删除一个结点
    
    show(L);                                                // 输出整个链表(内嵌函数)
}

int main()
{
    // 1、通过头结点创建一个链表
    linkList L;
    
    // 2、初始化
    Init(L);
    
    // 3、插入
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、进行出库
    int site;
    cin >> site;
    remove(L, site, n);
    
    return 0;
}

223、基于链存储结构的图书信息表的图书去重 描述

出版社出版的任何一本图书的书号（ISBN）都是唯一的，即图书表中不允许包含书号重复的图书。定义一个包含图书信息（书号、书名、价格）的链表，读入相应的图书数据来完成图书信息表的创建（书号可能重复），然后进行图书的去重，即删除书号重复的图书（只保留第一本），最后输出去重后所有图书的信息。

输入

总计输入n+1行，其中，第一行是图书数目n，后n行是n本图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，价格之后没有空格（书号可能重复）。其中书号和书名为字符串类型，价格为浮点数类型。

输出

总计输出m+1行（m≤n），其中，第一行是去重后的图书数目，后m行是去重后图书的信息（书号、书名、价格），每本图书信息占一行，书号、书名、价格用空格分隔，其中价格输出保留两位小数。

输入样例 1

9
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

输出样例 1

8
9787302257646 Data-Structure 35.00
9787302164340 Operating-System 50.00
9787302219972 Software-Engineer 32.00
9787302203513 Database-Principles 36.00
9787810827430 Discrete-Mathematics 36.00
9787302257800 Data-Structure 62.00
9787811234923 Compiler-Principles 62.00
9787822234110 The-C-Programming-Language 38.00

AC 代码

#include 

using namespace std;

struct Book                                                 // 定义书类数据结构
{
    string ibsn;
    string name;
    double price;
};

typedef struct LNode                                        // 定义结点数据类型
{
    Book data;
    struct LNode *next;
}LNode, *linkList;

// 初始化函数
bool Init(linkList &L)                                      // 创建头结点并使头结点指向空
{
    L = new LNode;
    L -> next = NULL;
    return true;
}

// 尾插法
void createList_tail(linkList &L, int n)                    // 利用尾插法得到链表，记得尾指针
{
    LNode *tail;
    tail = new LNode;
    tail = L;
    
    while (n --)
    {
        LNode *tmp;
        tmp = new LNode;
        
        cin >> tmp -> data.ibsn >> tmp -> data.name >> tmp -> data.price;
        tail -> next = tmp;
        tmp -> next = NULL;
        tail = tmp;
    }
    
}

// 去重
void unique(linkList &L, int n)
{
    LNode * tmp1 = L -> next;                                               // 第一个指针从首元结点开始
    
    int cnt = 0;                                                            //  存储重复的数量
    while (tmp1)                                                            // 只要指针 1 不为空（未遍历到最后）
    {
        LNode *tmp2 = tmp1;                                                 // 让第二指针从首元结点开始，并且我们功能使用的是其next结点
        while (tmp2 -> next)                                                // 比较 n - 1次
        {
            if (tmp1 -> data.ibsn == tmp2 -> next -> data.ibsn)
            {
                LNode *tmp3 = tmp2 -> next;                                 // 创建一个临时LNode变量存储这个结点的地址，然后释放
                delete tmp3;
                tmp2 -> next = tmp2 -> next -> next;
                
                cnt ++;                                                     // 重复数量进行 ++
            }
            
            else tmp2 = tmp2 -> next;
        }
        
        tmp1 = tmp1 -> next;
    }
    
    cout << n - cnt << endl;                                                // 输出去重后的数量
}

// 输出整个链表
void show(linkList L)
{
    LNode *tmp;
    tmp = new LNode;
    tmp = L -> next;
    
    while (tmp)                                             // 遍历
    {
        cout << tmp -> data.ibsn << " " << tmp -> data.name << " ";
        printf("%.2lfn", tmp -> data.price);
        tmp = tmp -> next;
    }
}

int main()
{
    // 1、通过头结点创建一个链表
    linkList L;
    
    // 2、初始化
    Init(L);
    
    // 3、插入
    int n;
    cin >> n;
    createList_tail(L, n);
    
    // 4、去重
    unique(L, n);
    
    // 5、输出
    show(L);
    
    return 0;
}