数据结构先修知识-C语言复习大作业-（二）链表实现
|
作业

第9关：采用链表实现图书浏览

任务描述
读取book.txt文件中信息并输出。

编程要求
输入要求
book.txt。

输出要求
依次输出所有图书信息（书号、书名、价格），包括文件前两行的标题说明信息。

测试说明
平台会对你编写的代码进行测试：

输入样例：
无
输出样例：
全部文件信息

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化
    L=new LNode;
    L->next=NULL;
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filepath.c_str(),ios::in);

    LinkList tail=L;

    string line;
    
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);


    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;

        LinkList newNode=new LNode;
        newNode->data=b;
        
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    
    }
}
void Print(LinkList &L){
	LinkList p;
	p = L->next;
	if(!p)
		return;
	cout << "北京林业大学图书馆计算机类图书采购列表" << endl;
	cout << "ISBN" << " ";
	cout << "书名" << " ";
	cout << "定价" << endl; 					//打印表头
	while (p){
		cout << p->data.no << " ";
		cout << p->data.name << " ";
		cout << p->data.price << endl; 			//输出p->data的数据
		p = p->next;						   	//p指向下一个结点
	}
}
int main(){
	LinkList L;
	string filepath = "/data/workspace/myshixun/book.txt";
    InitList(L);
	ReadFile(L, filepath);
	Print(L);
    FreeList(L);
	return 0;
}


第10关：采用链表实现图书统计

任务描述
读取book.txt文件中的图书信息并统计图书总数。

编程要求
输入要求
book.txt。

输出要求
输出一行数据，为图书的总数。

测试说明
平台会对你编写的代码进行测试：

输入样例：
无
输出样例：
103

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L=new LNode;
    L->next=NULL;
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filepath.c_str(),ios::in);

    LinkList tail=L;

    string line;

    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);

    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;

        LinkList newNode=new LNode;
        newNode->data=b;

        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }

}

int CountBook(LinkList &L){
//返回图书总数
    int count=0;
    LinkList p=L;
    while(p->next!=NULL){
        p=p->next;
        count++;
    }
    return count;
}
int main()
{
	LinkList L;
	string filepath = "/data/workspace/myshixun/book.txt";
    InitList(L);
	ReadFile(L, filepath);
	int count=CountBook(L);
	cout << count << endl;
    FreeList(L);
	return 0;
}

第11关：采用链表实现图书插入

输入要求
输入四行数据。其中，第1行为插入位置pos（1≤pos≤n+1），第2行到第4行分别为待插入的图书书号、书名和价格。

输出要求
输出一行数据，为插入的图书信息。

测试说明
平台会对你编写的代码进行测试：

输入样例：
1
9787115578567
数据结构上机指导（C语言版）
69.9
输出样例：
9787115578567 数据结构上机指导（C语言版） 69.9

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L=new LNode;
    L->next=NULL;
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filepath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newNode=new LNode;
        newNode->data=b;
 
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }
}

void SaveFile(LinkList &L, string filepath) {
//保存图书信息到文件
    fstream f;
    f.open(filepath.c_str(),ios::out);

    f<<"北京林业大学图书馆计算机类图书采购列表"<<endl<<"ISBN\t"<<"书名\t"<<"定价"<<endl;
    
    LinkList p=L->next;

    while(p!=NULL){
        f<<p->data.no<<"\t"<<p->data.name<<"\t"<<p->data.price<<endl;
        p=p->next;
    }

    f.close();
}

bool InsertBook(LinkList &L, int pos, Book *book){
//插入图书信息，输入图书的书号、书名和价格，将该图书的基本信息插入到链表中的指定位置
//如果插入成功，返回true，否则，返回false
    int count=0;
    LinkList p=L;
    while(p->next!=NULL){
        p=p->next;
        count++;
    }
    if(pos<1||pos>count+1)
        return 0;
    
    LinkList newNode=new LNode;
    newNode->data=*book;

    if(pos==1){
        newNode->next=L->next;
        L->next=newNode;
        return 1;
    }

    p=L->next;//p=L;？？？
    for(int i=1;i<=pos-1;i++){
        p=p->next;
    }

    newNode->next=p->next;
    p->next=newNode;

    return 1;
}

void Check(LinkList L, Book *book, int pos){
//结果检查
	int j = 0;
	LinkList p = L;
	while (p && j < pos){
		p = p->next;
		j++;
	}
	if(!strcmp(p->data.no, book->no)&&!strcmp(p->data.name, book->name)&&(p->data.price==book->price))
		cout<< book->no << " " << book->name << " "<< book->price <<endl;
}
int main(){
	LinkList L;
	string filepath = "/data/workspace/myshixun/book.txt";
    string newpath = "/data/workspace/myshixun/2.3-采用链表实现图书插入/book-new.txt";
	int pos;
	cin >> pos;
	Book *book = new Book();
	cin >> book->no >> book->name >> book->price;
	InitList(L);
	ReadFile(L, filepath);
	bool flag=InsertBook(L, pos, book);
    if(flag){
        SaveFile(L, newpath);
        LinkList L2;
        InitList(L2);
        ReadFile(L2, newpath);
        Check(L2, book, pos);
        FreeList(L2);
    }
    else
        cout<<"插入失败"<<endl;
	FreeList(L);
	return 0;
}

链表插入标准一点的写法：

bool InsertBook(LinkList &L, int pos, Book *book){
//插入图书信息，输入图书的书号、书名和价格，将该图书的基本信息插入到链表中的指定位置
//如果插入成功，返回true，否则，返回false
    LinkList p = L;
    int index=0;


    while(p!=NULL&&index<pos-1){
        p=p->next;
        index++;
    }

    if(p==NULL||pos<1)
        return 0;

    LinkList newNode=new LNode;
    newNode->data=*book;

    newNode->next=p->next;
    p->next=newNode;

    return 1;
}

第12关：采用链表实现图书删除

任务描述
根据指定位置删除book.txt文件中该位置上的图书信息。

编程要求
输入要求
输入一行数据，为删除位置pos（1≤pos≤n）。

输出要求
依次输出删除后的所有图书信息（书号、书名、价格），包括文件前两行的标题说明信息。

测试说明
平台会对你编写的代码进行测试：

输入样例：
6
输出样例：
删除后的全部文件信息

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L=new LNode;
    L->next=NULL;
}
 
void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}
 
void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filepath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newNode=new LNode;
        newNode->data=b;
 
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }
}
 
void SaveFile(LinkList &L, string filepath) {
//保存图书信息到文件
    fstream f;
    f.open(filepath.c_str(),ios::out);
 
    f<<"北京林业大学图书馆计算机类图书采购列表"<<endl<<"ISBN\t"<<"书名\t"<<"定价"<<endl;
    
    LinkList p=L->next;
 
    while(p!=NULL){
        f<<p->data.no<<"\t"<<p->data.name<<"\t"<<p->data.price<<endl;
        p=p->next;
    }
 
    f.close();
}

bool DeleteBook(LinkList &L, int pos) { 				
//删除指定图书信息
//如果删除成功，返回true，否则，返回false
    LinkList p = L;
    int index=0;
 
 
    while(p!=NULL&&index<pos-1){
        p=p->next;
        index++;
    }
 
    if(p==NULL||pos<1)
        return 0;

    p->next=p->next->next;
    return 1;
}
void Print(LinkList &L) {
    LinkList p;
    p = L->next;
    if (!p) {
        cout << "无图书信息，请添加图书信息。" << endl;
        return;
    }
    cout << "北京林业大学图书馆计算机类图书采购列表" << endl;
    cout << "ISBN" << " ";
    cout << "书名" << " ";
    cout << "定价" << endl;
    while (p) {
        cout << p->data.no << " ";
        cout << p->data.name << " ";
        cout << p->data.price << endl;
        p = p->next;
    }
    return;
}

int main() {
	LinkList L;
    LinkList L1;
	int pos;
	cin>>pos;
    InitList(L);
    InitList(L1);
	ReadFile(L, "/data/workspace/myshixun/book.txt");
	bool flag = DeleteBook(L, pos);
    if (flag) {
        SaveFile(L, "/data/workspace/myshixun/2.4-采用链表实现图书删除/book-new.txt");
        ReadFile(L1, "/data/workspace/myshixun/2.4-采用链表实现图书删除/book-new.txt");
        Print(L1);
    }
	else {
        cout << "删除失败" << endl;
    }
    FreeList(L);
	FreeList(L1);
	return 0;
}

第13关：采用链表实现图书查找

任务描述
用两种方式实现对book.txt文件中的图书查找：
① 按位置进行查找并输出；
② 按书名进行查找并输出（如果有多本，则全部输出）。

编程要求
输入要求
输入两行数据。其中，第1行为查找的类型，输入“1”表示按位置查找，输入“2”表示按书名查找。第2行根据第1行的类型输入相应的位置和或书名。

输出要求
依次输出查找的所有图书信息（书号、书名、价格）

测试说明
平台会对你编写的代码进行测试：

输入样例：
1
6
输出样例：
9787811234923 汇编语言程序设计教程 21

输入样例：
2
计算机数学
输出样例：
9787302131304 计算机数学 20
9787302162834 计算机数学 30

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;


void InitList(LinkList &L){   							
//使用动态内存分配new进行初始化 
    L=new LNode;
    L->next=NULL;
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

void ReadFile(LinkList &L, string filepath) {
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filepath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newnode =new LNode;
        newnode->data=b;

        tail->next=newnode;
        tail=newnode;
        newnode->next=NULL;
    }
}

LinkList SearchBook(LinkList &L, int type) {
//图书信息查找，返回包含查找图书信息的链表，如果查找失败，返回nullptr
    LinkList t=L;

	if(type == 1){
		int pos;
		cin >> pos;

        if(pos<1)
            return nullptr;
        int count=0;
        while(t){ 
            if(count==pos){
                LinkList nl=new LNode;
                InitList(nl);
                nl->next=t;
                nl->next->next=NULL;
                return nl;
            }
            t=t->next;
            count++;
        }
        return nullptr;    
	}
	if(type == 2){
		char name[50];
		cin >> name;
        
        LinkList nl=new LNode;
        InitList(nl);
        LinkList tail =nl; 

        while(t){
            if(strcmp(t->data.name,name)==0){
                LinkList newnode =new LNode;
                newnode->data=t->data;

                tail->next=newnode;
                tail=newnode;
                newnode->next=NULL;
            }
            t = t->next;
        }

        return nl;

	}
}
int main() {
	LinkList L;
    int type;
    cin >> type;
    InitList(L);
	ReadFile(L, "/data/workspace/myshixun/book.txt");
	LinkList t=SearchBook(L, type);
    if (t != nullptr) {
        LinkList p=t->next;
        while(p){
            cout << p->data.no << " ";
            cout << p->data.name << " ";
            cout << p->data.price << endl;
            p=p->next;
        }
    }
    else
        cout << "查找失败" << endl;
    FreeList(L);
	return 0;
}

第14关：采用链表实现图书价格更新

任务描述
将book.txt文件中价格小于45元的图书价格提高20%，价格大于等于45元的图书价格提高10%，将修改后的图书信息重新写入新文件book-newprice.txt中。

编程要求
输入要求
book.txt。

输出要求
依次输出更新后的所有图书信息（书号、书名、价格），包括文件前两行的标题说明信息。

测试说明
平台会对你编写的代码进行测试：

输入样例：
无
预期输出：
更新后的全部文件信息

#include <bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L=new LNode();
    L->next;
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

void ReadFile(LinkList &L, string filePath) {
//从文件中读取图书信息，利用尾插法构建链表
    fstream f;
    f.open(filePath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newNode=new LNode;
        newNode->data=b;
 
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }
}
 
void SaveFile(LinkList &L, string filepath) {
//保存图书信息到文件
    fstream f;
    f.open(filepath.c_str(),ios::out);
 
    f<<"北京林业大学图书馆计算机类图书采购列表"<<endl<<"ISBN\t"<<"书名\t"<<"定价"<<endl;
    
    LinkList p=L->next;
 
    while(p!=NULL){
        f<<p->data.no<<"\t"<<p->data.name<<"\t"<<p->data.price<<endl;
        p=p->next;
    }
 
    f.close();
}

void UpdateBook(LinkList &L) {
//图书信息更新
    LNode* t=L->next;
    while(t){
        if(t->data.price<45)
            t->data.price*=1.2;
        else
            t->data.price*=1.1;

        t=t->next;
    }
}
void Print(LinkList &L) {
    LinkList p;
    p = L->next;
    if (!p) {
        cout << "无图书信息，请添加图书信息。" << endl;
        return;
    }
    cout << "北京林业大学图书馆计算机类图书采购列表" << endl;
    cout << "ISBN" << " ";
    cout << "书名" << " ";
    cout << "定价" << endl;
    while (p) {
        cout << p->data.no << " ";
        cout << p->data.name << " ";
        cout << p->data.price << endl;
        p = p->next;
    }
    return;
}

int main() {
	LinkList L;
    LinkList L1;
    InitList(L);
    InitList(L1);
	ReadFile(L, "/data/workspace/myshixun/book.txt");
	UpdateBook(L);
	SaveFile(L, "/data/workspace/myshixun/2.6-采用链表实现图书价格更新/book-newprice.txt");
    ReadFile(L1, "/data/workspace/myshixun/2.6-采用链表实现图书价格更新/book-newprice.txt");
    Print(L1);
    FreeList(L);
    FreeList(L1);
	return 0;
}

第15关：采用链表实现图书价格排序

任务描述
对book.txt中图书价格升序排序，并将排序后的图书信息写入新文件book-newsort.txt中。

编程要求
输入要求
book.txt

输出要求
输出指定位置的图书信息（书号、书名、价格）。

测试说明
平台会对你编写的代码进行测试：

输入样例：
无
输出样例：
输出链表中第9个位置的图书信息
书号：9787302184898
书名：微型计算机原理与结构习题解答与实验指导
价格：21

#include<bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L=new LNode;
    L->next=NULL;
}

void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
	fstream f;
    f.open(filepath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newNode=new LNode;
        newNode->data=b;
 
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }
}

int CountBook(LinkList &L){
//求链表L的长度	
	int count=0;
    LinkList p=L;
    while(p->next!=NULL){
        p=p->next;
        count++;
    }
    return count;
}

void PriceSort(LinkList &L){
//按图书价格升序排序，采用冒泡排序
    int length=CountBook(L);
	for(int i =0;i<length;i++){
        LinkList p1=L;
        LinkList p2=p1->next;
        for(int j=0;j<length-i-1;j++){    
            if(p1->data.price>p2->data.price){
                Book t=p1->data;
                p1->data=p2->data;
                p2->data=t;
            }
            p1=p1->next;
            p2=p1->next;
        }
    }
}

void SaveFile(LinkList &L, string filepath){
//排序后的数据写入新文件"book-newsort.txt"中
	fstream f;
    f.open(filepath.c_str(),ios::out);
 
    f<<"北京林业大学图书馆计算机类图书采购列表"<<endl<<"ISBN\t"<<"书名\t"<<"定价"<<endl;
    
    LinkList p=L->next;
 
    while(p!=NULL){
        f<<p->data.no<<"\t"<<p->data.name<<"\t"<<p->data.price<<endl;
        p=p->next;
    }
 
    f.close();
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}
int main()
{	
	LinkList L;
    LinkList L1;
	InitList(L);				
	ReadFile(L,"/data/workspace/myshixun/book.txt");
	PriceSort(L);				
	SaveFile(L,"/data/workspace/myshixun/2.7-采用链表实现图书价格排序/book-newsort.txt");	
	InitList(L1);
    ReadFile(L1, "/data/workspace/myshixun/2.7-采用链表实现图书价格排序/book-newsort.txt");
    LinkList p;					//验证排序后的数组
	p = L1;
	int count = 0;
	while(count != 9){
		p = p->next;
		count++;
	}
	cout << "输出链表中第9个位置的图书信息" << endl;
	cout << "书号：" << p->data.no << endl; 
	cout << "书名：" << p->data.name << endl;
	cout << "价格：" << p->data.price<<endl;
	FreeList(L);
    FreeList(L1);
	return 0;
}

关键点：

  1. 两层循环：
    • 外层循环：负责控制整个排序的次数。因为冒泡排序需要进行多轮比较，直到链表完全有序，外层循环的次数是链表的长度减一。
    • 内层循环：负责在链表中比较和交换相邻节点的数据。每次内层循环结束后，最大的元素被放置到链表末尾，所以内层循环的比较范围会逐渐减小。
  2. 数据交换而非节点交换：冒泡排序过程中只交换相邻节点的数据，而不是交换节点本身的指针。这是因为交换节点指针会破坏链表的结构，增加复杂性。
  3. 优化（可选）：可以通过在每次外层循环中判断是否发生了数据交换，如果某一轮没有发生交换，说明链表已经有序，可以提前结束排序过程。

核心步骤：

  1. 初始化：确定链表的长度或者通过外层循环次数控制比较范围。
  2. 逐次比较和交换：
    • 在每一轮遍历中，比较相邻两个节点的数据，如果前一个节点的数据大于后一个节点的数据，交换它们的数据。
    • 通过 p1 和 p2 指针分别指向当前节点和下一个节点，进行比较和交换。
  3. 逐轮减少比较范围：每次内层循环结束后，最大的元素被放置在链表的末尾，外层循环的范围逐渐缩小。
  4. 排序结束：当所有的节点都完成比较和交换，链表数据排序完成。

第16关：采用链表实现图书信息逆序存储

任务描述
将book.txt中的全部图书信息逆序存储（即最后一本置于原第一本位置）写入新文件book-newinverse.txt中。

编程要求
输入要求
book.txt

输出要求
输出指定位置的图书信息（书号、书名、价格）。

测试说明
平台会对你编写的代码进行测试：

输入样例：
无

输出样例：
输出链表中第9个位置的图书信息
书号：9787302204862
书名：软件工程
价格：23

#include<bits/stdc++.h>
using namespace std;

typedef struct{
	char no[20];					//书号 
	char name[100];					//书名 
	float price;					//价格 
}Book;

typedef struct LNode{
    Book data;                      //图书信息
    struct LNode *next;             //指向下一结点
}LNode, *LinkList;			

void InitList(LinkList &L){
//使用动态内存分配new进行初始化 
    L = new LNode;
    L->next=NULL;
}

void ReadFile(LinkList &L, string filepath){
//从文件中读取图书信息，利用尾插法构建链表
	fstream f;
    f.open(filepath.c_str(),ios::in);
 
    LinkList tail=L;
 
    string line;
 
    // 跳过已有的表头与字段名 		
	getline(f, line);
	getline(f, line);
 
    while(getline(f,line)){
        stringstream ss(line);
        Book b;
        ss>>b.no>>b.name>>b.price;
 
        LinkList newNode=new LNode;
        newNode->data=b;
 
        tail->next=newNode;
        tail=newNode;
        tail->next=NULL;
    }
}

void ReverseBook(LinkList &L){
//把图书信息逆序存储 
	LinkList pre=NULL;
    LinkList p=L->next;
    LinkList next=NULL;

    while(p){
        next=p->next;
        p->next=pre;
        pre=p;
        p=next;
    }

    L->next=pre;
}

void SaveFile(LinkList &L, string filepath){
//把逆序后的数据写入新文件"book-newinverse.txt"中 
	fstream f;
    f.open(filepath.c_str(),ios::out);
 
    f<<"北京林业大学图书馆计算机类图书采购列表"<<endl<<"ISBN\t"<<"书名\t"<<"定价"<<endl;
    
    LinkList p=L->next;
 
    while(p!=NULL){
        f<<p->data.no<<"\t"<<p->data.name<<"\t"<<p->data.price<<endl;
        p=p->next;
    }
 
    f.close();
}

void FreeList(LinkList &L){
//释放内存
    LinkList tp;
    while(L){
        tp=L;
        L=L->next;
        delete tp;
    }
}

int main()
{	
	LinkList L;
    LinkList L1;
	InitList(L);				
	ReadFile(L, "/data/workspace/myshixun/book.txt");
	ReverseBook(L);			 
	SaveFile(L, "/data/workspace/myshixun/2.8-采用链表实现图书信息逆序存储/book-newinverse.txt");				
	InitList(L1);
    ReadFile(L1, "/data/workspace/myshixun/2.8-采用链表实现图书信息逆序存储/book-newinverse.txt");
    LinkList p;					
	p = L1;
	int count = 0;
	while(count != 9){
		count++;
		p = p->next;
		
	}
	cout << "输出链表中第9个位置的图书信息" << endl;
	cout << "书号：" << p->data.no << endl; 
	cout << "书名：" << p->data.name << endl;
	cout << "价格：" << p->data.price<<endl;
	FreeList(L);
    FreeList(L1);
	return 0;
}

核心思路：

  1. 指针反转：每次遍历到一个节点时，将它的 next 指针指向前一个节点，从而改变链表的指针方向。
  2. 链表遍历：通过逐个遍历链表的每个节点来完成反转操作，直到遍历到链表的末尾（nullptr）。
  3. 保留哑节点：如果链表包含哑节点（即一个空节点作为链表头），我们只反转从 L->next 开始的节点，保留哑节点不动。

关键点：

  1. 三个指针控制反转：
    • pre：指向当前节点的前一个节点，初始为 NULL（因为第一个节点在反转后需要指向 NULL）。
    • p：指向当前节点，在每次遍历时移动到下一个节点。
    • next：用于临时保存 p->next，防止链表断开。
  2. 从有效节点开始反转：如果链表有哑节点（L），反转操作从 L->next 开始，确保不改变哑节点。
  3. 更新头节点：反转完成后，链表的头节点（L->next）需要指向反转后的第一个有效节点。
  4. 处理特殊情况：如果链表为空或者链表中只有哑节点，直接返回，不进行任何反转操作。

核心步骤：

  1. 初始化：pre 初始化为 NULL，p 初始化为 L->next（跳过哑节点）。
  2. 逐个反转：通过遍历链表，反转每个节点的 next 指针。
  3. 更新头节点：最后将 L->next 指向反转后的第一个节点 pre。

C++作业入门数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Java课内-实验2:方阵可视化遍历

							
							

							
Java课内-实验1:分数类(完全弹性碰撞)

							
							

							
-1大于4？