数据结构练习题之--查找特定位置节点&&根据位置插入新结点

2024-02-01 20:07:10

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

输入样式：

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

输出样式：

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

代码；

//查找最爱图书
#include<iostream>
#include<string>
#include<iomanip>
#include<string.h>
#define OK 1
using namespace std;

typedef struct
{
	string IBNS;
	string NAME;
	float PRICE;
}Book;

typedef struct LNode
{
	int length;
	Book data;
	struct LNode* next;
}LNode, * LinkList;

int Init(LinkList& L);//初始化链表
int Insert(LinkList& L);//尾插法插入
int Traveral(LinkList& L);//遍历函数
int Print(LinkList L);
int Find(LinkList L);

int main()
{
	LinkList L;
	Init(L);
	Insert(L);
	Traveral(L);
	Find(L);
	//Print(L);
	return 0;
}

int Init(LinkList& L)
{
	L = new LNode;
	L->next = NULL;
	return OK;
}

int Find(LinkList L)//寻找最爱图书
{
	int n;
	cin >> n;
	LinkList p = L->next;//指针p指向首元结点
	int flag = 0;
	while (n--)
	{
		cout << n;
		int m;
		cin >> m;
		if (m<1 || m>L->length)
			cout << "Sorry，the book on the best position doesn't exist!" << endl;
		else
		{
			for (int i = 0; i < m-1; i++)//for循环寻找特定位置的结点，找错了的话就稍微改变一下循环结束条件即可
				p = p->next;
			cout << p->data.IBNS << " " << p->data.NAME << " " << fixed << setprecision(2) << p->data.PRICE << endl;
		}
		p = L->next;//执行完一次循环之后将指针指向首元结点，这是一个好习惯
	}
	return OK;
}

int Insert(LinkList& L)//头插法
{
	LinkList p = L;//p存储链表L的头指针，指向头结点
	string IBNS;
	string NAME;
	float PRICE;
	int n;
	cin >> n;
	while (n--)
	{
		LinkList q = new LNode;
		cin >> IBNS >> NAME >> PRICE;
		q->data.IBNS = IBNS;
		q->data.NAME = NAME;
		q->data.PRICE = PRICE;
		q->next = NULL;
		p->next = q;
		p = q;//p指向NewNode
	}
	return OK;
}

int Traveral(LinkList& L)
{
	LinkList p = L;//定义头指针，指向头结点
	L->length = 0;
	while (p->next)
	{
		L->length++;
		p = p->next;
	}
	return OK;
}

int Print(LinkList L)
{
	LinkList p = L;//定义头指针指向头结点
	while (p->next)
	{
		cout << p->next->data.IBNS << " " << p->next->data.NAME << " " << fixed << setprecision(2) << p->next->data.PRICE << endl;
		p = p->next;
	}
	return OK;
}

第二题 根据位置插入新结点

输入样式：

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

输出样式：

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

代码；

//查找最爱图书
#include<iostream>
#include<string>
#include<iomanip>
#include<string.h>
#define OK 1
using namespace std;

typedef struct
{
	string IBNS;
	string NAME;
	float PRICE;
}Book;

typedef struct LNode
{
	int length;
	Book data;
	struct LNode* next;
}LNode, * LinkList;

int Init(LinkList& L);//初始化链表
int Insert(LinkList& L);//尾插法插入
int Traveral(LinkList& L);//遍历函数
int Print(LinkList L);
int Insert_Pos(LinkList& L);

int main()
{
	LinkList L;
	Init(L);
	Insert(L);
	Traveral(L);
	Insert_Pos(L);
	return 0;
}


int Insert_Pos(LinkList& L)//根据位置插入新结点
{
	LinkList q = new LNode;//创建一个新的结点
	LinkList p = L;
	int n;
	cin >> n;
	cin >> q->data.IBNS >> q->data.NAME >> q->data.PRICE;//输入新结点的数据元素
	n--;
	if (n<1 || n>L->length)
		cout << "Sorry，the position to be inserted is invalid!" << endl;
	else
	{
		while (n--)//移动指针到第n-1个元素位置上
			p = p->next;
		q->next = p->next;//将新节点连接到L上
		p->next = q;//
		Print(L);
		return OK;
	}
}
int Init(LinkList& L)
{
	L = new LNode;
	L->next = NULL;
	return OK;
}


int Insert(LinkList& L)//头插法
{
	LinkList p = L;//p存储链表L的头指针，指向头结点
	string IBNS;
	string NAME;
	float PRICE;
	int n;
	cin >> n;
	while (n--)
	{
		LinkList q = new LNode;
		cin >> IBNS >> NAME >> PRICE;
		q->data.IBNS = IBNS;
		q->data.NAME = NAME;
		q->data.PRICE = PRICE;
		q->next = NULL;
		p->next = q;
		p = q;//p指向NewNode
	}
	return OK;
}

int Traveral(LinkList& L)
{
	LinkList p = L;//定义头指针，指向头结点
	L->length = 0;
	while (p->next)
	{
		L->length++;
		p = p->next;
	}
	return OK;
}

int Print(LinkList L)
{
	LinkList p = L;//定义头指针指向头结点
	while (p->next)
	{
		cout << p->next->data.IBNS << " " << p->next->data.NAME << " " << fixed << setprecision(2) << p->next->data.PRICE << endl;
		p = p->next;
	}
	return OK;
}

第三题 根据指定位置删除结点

输入样例：

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

输出样例：

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

代码；

//查找最爱图书
#include<iostream>
#include<string>
#include<iomanip>
#include<string.h>
#define OK 1
using namespace std;

typedef struct
{
	string IBNS;
	string NAME;
	float PRICE;
}Book;

typedef struct LNode
{
	int length;
	Book data;
	struct LNode* next;
}LNode, * LinkList;

int Init(LinkList& L);//初始化链表
int Insert(LinkList& L);//尾插法插入
int Traveral(LinkList& L);//遍历函数
int Print(LinkList L);
int Insert_Pos(LinkList& L);
int Delete(LinkList& L);

int main()
{
	LinkList L;
	Init(L);
	Insert(L);
	Traveral(L);
	Delete(L);
	//Insert_Pos(L);
	return 0;
}

int Delete(LinkList& L)
{
	int n;
	LinkList p = L;
	LinkList q;
	cin >> n;
	int i = 0;
	while ((p->next) && (i < n - 1))//查找第n-1个节点，p指向该结点
	{
		p = p->next;
		++i;
	}
	if (!(p->next) || (i > n - 1))
		cout << "Sorry，the position to be deleted is invalid!" << endl;
	else
	{
		q = p->next;//临时保存删除结点的地址
		p->next = q->next;//改变删除结点前驱节点的指针指向
		delete q;
		Print(L);
	}
	return OK;

}

int Insert_Pos(LinkList& L)//根据位置插入新结点
{
	LinkList q = new LNode;//创建一个新的结点
	LinkList p = L;
	int n;
	cin >> n;
	cin >> q->data.IBNS >> q->data.NAME >> q->data.PRICE;//输入新结点的数据元素
	n--;
	if (n<1 || n>L->length)
		cout << "Sorry，the position to be inserted is invalid!" << endl;
	else
	{
		while (n--)//移动指针到第n-1个元素位置上
			p = p->next;
		q->next = p->next;//将新节点连接到L上
		p->next = q;//
		Print(L);
		return OK;
	}
}
int Init(LinkList& L)
{
	L = new LNode;
	L->next = NULL;
	return OK;
}



int Insert(LinkList& L)//头插法
{
	LinkList p = L;//p存储链表L的头指针，指向头结点
	string IBNS;
	string NAME;
	float PRICE;
	int n;
	cin >> n;
	while (n--)
	{
		LinkList q = new LNode;
		cin >> IBNS >> NAME >> PRICE;
		q->data.IBNS = IBNS;
		q->data.NAME = NAME;
		q->data.PRICE = PRICE;
		q->next = NULL;
		p->next = q;
		p = q;//p指向NewNode
	}
	return OK;
}

int Traveral(LinkList& L)
{
	LinkList p = L;//定义头指针，指向头结点
	L->length = 0;
	while (p->next)
	{
		L->length++;
		p = p->next;
	}
	return OK;
}

int Print(LinkList L)
{
	LinkList p = L;//定义头指针指向头结点
	while (p->next)
	{
		cout << p->next->data.IBNS << " " << p->next->data.NAME << " " << fixed << setprecision(2) << p->next->data.PRICE << endl;
		p = p->next;
	}
	return OK;
}

上一篇：带头的单链表-查找、插入、删除、非递减排列、删除范围值


下一篇：三：SSM框架整合思路