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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> BJFU数据结构C语言第二版课后OJ练习链表部分 -> 正文阅读

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

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 <iostream>
#include <algorithm>

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("%.2lf\n", tmp2 -> data.price);
    }
    
    return 0;
}

尾插法：

AC 代码

#include <iostream>
#include <algorithm>

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("%.2lf\n", tmp2 -> data.price);
		tmp2 = tmp2 -> next;
	}
    
    return 0;
}
z

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

描述

输入

输出

输入样例 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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 <iostream>

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("%.2lf\n", 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;
}