Java教程

《算法与数据结构实践专题》

本文主要是介绍《算法与数据结构实践专题》，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

写在前面：

数据结构什么的早就不是问题，就当自己巩固一下基础吧，后期同学们也要一个一个细节问啊问怎么搞，任务本来就要求写一个就好了，鬼知道我的学号对应的是最简单的，无趣，那么还是全部做一遍吧，供同学们参考一些细节呀，千万要独立思考，不要抄袭啊QWQ，不然以后还是不会做的。全部代码都在GCC 9.2.0通过。安装一个Dev c++即可以运行代码，有些可能要一点的gcc版本哦！

一、实践专题目的

熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

二、实践专题要求

在本次实践专题过程中要求学生：
（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；
（2）按照实践专题的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者本次实践专题课程成绩皆以零分计。凡发现实验报告或源程序雷同，涉及的全部人员本次实践专题的课程成绩皆以零分计。
（3）认真撰写实践专题报告。

三、实践专题设计步骤

1、问题分析和任务定义；
2、数据类型和系统设计；
3、编码实现；
4、上机调试；
5、总结和整理课程设计报告。

四、考核方式和成绩评定

考核分为两个部分：

  • 程序运行情况：按规定时间运行程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚。
  • 实验报告：是否按规定撰写实践专题报告的各项内容。

1. 集合运算 (单循环链表)

问题描述：
设有两个带头结点的单循环链表存储的集合A、B，其元素类型是int且以非递减方式存储，其头结点分别为ha、hb。要求下面各问题中的结果集合同样以非递减方式存储，结果集合不影响原集合。
实现要求：

  1. 编写集合元素测试函数IN_SET，如果元素已经在集合中返回0，否则返回1；
  2. 编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单循环链表中；
  3. 编写求集合A、B的交C=A∩B的函数，并输出集合C的元素；
  4. 编写求集合A、B的并D=A∪B的函数，并输出集合D的元素；
  5. 求集合A与B的对称差E=(A-B)∪(B-A) 的函数，并输出集合D的元素；
  6. 设计一个菜单，具有输入集合元素、求集合A、B的交C、求集合A、B的并D、求集合A与B的对称差E、退出等基本的功能。

测试数据： 由同学们自定，但集合A、B的元素个数不得少于16个。

#include<bits/stdc++.h>

using namespace std;

const int N=1000;

struct SET{
	struct Node{ 
		int val;
		int prev,nex;
	}node[N];//数组模拟链表 
	int head,tail;
	int tot=0;
	SET(){tot=0;init();}
	void init(){
		tot=2;
		head=1,tail=2;
		node[head].nex=tail;
		node[tail].prev=head;
	}
	void insert(int p,int val){//指定位置插入 
		int q=++tot;
		node[q].val=val;
		node[node[p].nex].prev=q;
		node[q].nex=node[p].nex;
		node[p].nex=q;
		node[q].prev=p;
	}
	void insert(int val){//插入 
		for(int i=node[head].nex;i!=tail;i=node[i].nex){
			if(node[i].val>val){
				insert(node[i].prev,val);
				return;
			}
		}
		insert(node[tail].prev,val);
	} 
	void remove(int p){//删除 
		node[node[p].prev].nex=node[p].nex;
		node[node[p].nex].prev=node[p].prev;
	}
	void clear(){//清空 
		memset(node,0,sizeof(node));
		head=tail=0;
	}
	bool in_set(int val){//是否存在 
		for(int i=node[head].nex;i!=tail;i=node[i].nex){
			if(node[i].val==val) return true;
		}
		return false;
	}
	void output(){
		for(int i=node[head].nex;i!=tail;i=node[i].nex)
			printf("%d ",node[i].val);
		puts("");
	}
	SET operator | (const SET &A) const {//集合的并 
		SET C;
		for(int i=A.node[head].nex;i!=A.tail;i=A.node[i].nex)
			C.insert(A.node[i].val);
		for(int i=node[head].nex;i!=tail;i=node[i].nex){
			if(!C.in_set(node[i].val)){
				C.insert(node[i].val);
			}
		}
		return C;
		
	}
	SET operator & ( SET &A)  const {////集合的交 
		SET C;
		for(int i=node[head].nex;i!=tail;i=node[i].nex){
			if(A.in_set(node[i].val)){
				C.insert(node[i].val);
			}
		} 
		return C;
	}
	SET operator - ( SET &A) const {//集合的差 
		SET C;
		for(int i=node[head].nex;i!=tail;i=node[i].nex){
			if(!A.in_set(node[i].val)){
				C.insert(node[i].val);
			}
		} 
		return C;
	} 
}; 

void menu(){
	printf("1.输入集合A,B\n"); 
	printf("2.A与B的并\n");
	printf("3.A与B的交\n");
	printf("4.A与B的差\n");
	printf("5.A与B的对称差\n");
	printf("0.退出\n"); 
	printf("输入选择："); 
} 


void run(){
	int ch;
	SET A,B,C;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				int n;
				printf("输入集合A的元素个数：");
				cin>>n;
				for(int i=1;i<=n;i++){
					int val;cin>>val;
					if(!A.in_set(val)) A.insert(val);
				} 
				printf("集合A：");A.output();
				printf("输入集合B的元素个数：");
				cin>>n;
				for(int i=1;i<=n;i++){
					int val;cin>>val;
					if(!B.in_set(val)) B.insert(val);
				} 
				printf("集合B：");B.output();
				break;
			case 2:printf("A|B: ");C=A|B;C.output();break;
			case 3:printf("A&B: ");C=A&B;C.output();break;
			case 4:printf("A-B: ");C=A-B;C.output();break;
			case 5:printf("A对称差B: "); C=(A-B)|(B-A);C.output(); break;
		} 
	}while(ch);
}

int main(){
	run(); 
	return 0;
}

2. 成绩排序（本人学号%15+1对应的题目）

问题描述
假设某年级有4个班，每班有n(n>40)名同学。本学期有5门课程考试，每门课程成绩是百分制。假定每个同学的成绩记录包含：学号、各门课程的成绩共6项，其中学号是一个12位的字符串(参照同学们的学号)，每个学生都有唯一的学号，并且这4个班的成绩分别放在4个数组中，完成以下操作要求：
实现要求：

  1. 编写一个成绩生成函数，使用随机数方法，利用随机函数生成学生的各门课程的成绩（每门课程的成绩都是0∽100之间的整数），通过调用该函数生成全部学生的成绩；
  2. 编写一个平均成绩计算函数，计算每个同学的平均成绩并保存在成绩数组中；
  3. 用希尔排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
  4. 用堆排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
  5. 用快速排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
  6. 用基数排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；
  7. 设计一个菜单，至少具有上述操作要求的基本功能。

测试数据：
由同学们自己输入。

#include<bits/stdc++.h>

using namespace std;
const int N=10000;

#define pb push_back

struct Person {
	long long id;
	int ma,en,sc,bg,ph,sum;
	double avg;
}p[N];
//随机数 
int random(){
	return (long long)rand()*rand()%101;
}
//产生学生成绩 
void create_student(int m,int n){
	long long id=201841404100;
	for(int i=1;i<=n*m;i++){
		p[i].id=++id;
		if((id%100)>=n) id=(id/100+1)*100;
		p[i].bg=random();
		p[i].en=random();
		p[i].ma=random();
		p[i].ph=random();
		p[i].sc=random();
		p[i].sum=p[i].bg+p[i].en+p[i].ma+p[i].ph+p[i].sc;
		p[i].avg=1ll*p[i].sum/5;
	}
}

//希尔排序 
void shellsort(int n){
	for(int len=n/2;len;len>>=1)
		for(int i=len+1;i<n;i++){
			Person tmp=p[i];
			int j=i;
			if(p[j].avg>p[j-len].avg){
				for(;tmp.avg>p[j-len].avg&&j-len>0;j-=len){
					p[j]=p[j-len];
				}
				p[j]=tmp;
			}
		}
				
}

//堆排序 
void heapify(int n,int i){
	if(i>=n) return;
	int c1=i<<1;
	int c2=i<<1|1;
	int maxn=i;
	if(c1<n&&p[c1].avg<p[maxn].avg) maxn=c1;
	if(c2<n&&p[c2].avg<p[maxn].avg) maxn=c2;
	if(maxn!=i){
		swap(p[maxn],p[i]);
		heapify(n,maxn);
	}
} 

void build_heap(int n){
	int last=n;
	int pa=n/2;
	for(int i=pa;i>=1;i--) heapify(n,i);
}

void heapsort(int n){
	build_heap(n);
	for(int i=n;i;i--){
		swap(p[i],p[1]);
		heapify(i,1);
	}	
		
}


//快速排序 
void quicksort(int l,int r){
	if(l<r){
		int i=l,j=r;
		Person tmp=p[l];
		while(i<j){
			while(i<j&&p[j].avg<=tmp.avg) j--;
			if(i<j) p[i++]=p[j];
			while(i<j&&p[i].avg>=tmp.avg) i++;
			if(i<j) p[j--]=p[i];
		}
		p[i]=tmp;
		quicksort(l,i-1);
		quicksort(i+1,r);
	} 
}

void dispaly(int x,int n){
	printf("第%d班的成绩表如下：\n",x); 
	for(int i=1;i<=n;i++){
		if((p[i].id)%1000/100==x)
			printf("%13lld %4d %4d %4d %4d %4d %5.2lf\n",p[i].id,p[i].bg,p[i].en,p[i].ma,p[i].ph,p[i].sc,p[i].avg);
	}
}

//基数排序
void radixsort(int n){
	int maxn=p[1].sum;
	for(int i=1;i<=n;i++)
		if(maxn<p[i].sum) maxn=p[i].sum;
	int exp=1;
	while(maxn/exp){
		vector<Person> box[11];
		for(int i=1;i<=n;i++)
			box[(p[i].sum/exp)%10].pb(p[i]);
		for(int k=0,j=9;j>=0;j--)
			for(auto e:box[j])
				p[++k]=e;
		exp*=10;
	} 
} 

void menu(){
	printf("1.希尔排序\n");
	printf("2.堆排序\n");
	printf("3.快速排序\n");
	printf("4.基数排序\n");
	printf("5.打印某班成绩信息\n");
	printf("输入你的选择："); 
}
void run(int m,int n){
	int ch;
	int x;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				shellsort(n*m);break;
			case 2:
				heapsort(n*m);
				break;
			case 3:
				quicksort(1,n*m);break;
			case 4:
				radixsort(n*m);
				break;
			case 5:
				printf("输入班级:");
				cin>>x; 
				dispaly(x,n*m);
				break;
		}
	}while(ch);
}

int main(){
	int n,m;
	printf("请输入班级个数，以及班级人数:"); 
	cin>>m>>n;
	create_student(m,n);
	run(m,n);
	return 0;
}

3. 二叉树的操作

题目描述：
二叉树的操作。
基本要求：
定义实现以下二叉树操作的函数（要求用非递归方式）

  1. 输入一棵完全二叉树，将该树保存一维数组AT[N]中，AT[N]中存放的是各结点的值，设计一个算法，从AT[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示，返回所建立的二叉链表表示的树的根结点
    的指针
  2. 根据二叉链表表示的树计算该二叉树中值最大的第1个结点的指针及最大值；
  3. 根据二叉链表表示的树，返回指定值的结点的父结点的指针，若没有，返回NULL；
  4. 计算二叉树的高度；
  5. 计算二叉树的宽度，即在二叉树各层上，具有结点数最多的那一层上的结点数。
  6. 根据二叉链表表示的树，交换二叉树中每个结点的两个子结点。
#include<bits/stdc++.h>

using namespace std;

const int N=1000;
int at[N];
int n;


void menu(){
	printf("\n1.根据二叉链表表示的树计算该二叉树中值最大的第1个结点的指针及最大值\n");
	printf("2.计算二叉树的高度\n");
	printf("3.计算二叉树的宽度\n");
	printf("4.交换每个节点的两个子节点\n");
	printf("5.输出二叉树序列\n");
	printf("0.退出\n");
	printf("输入你的选择:"); 
}
//高度 
int h(int n){
	if(n==8) return 4; //计算机表示不了？ 计算机log(8)/log(2)+1居然等于3？ 
	return log(n)/log(2)+1;
}
//最大宽度 
int b(int n){
	if(n==1) return 1;
	if(n==(1<<h(n))-1) return 1<<(h(n)-1);
	else{
		if(n-((1<<(h(n)-1))-1)>((1<<(h(n)-2))))
			return n-((1<<(h(n)-1))-1);
		else return (1<<(h(n)-2));	
	}
}
//交换左右节点 （不是交换左右子树） 
//非递归版
void SW(){
	for(int i=1;i<=n;i++){
		if(at[i<<1|1]&&at[i<<1])
			swap(at[i<<1],at[i<<1|1]);
	}
}
 
//递归版(供给大家理解) 
void SWAP(int p){
	if(at[p<<1]) SWAP(p<<1);
	if(at[p<<1|1]) SWAP(p<<1|1);
	if(at[p<<1|1]&&at[p<<1])
		swap(at[p<<1],at[p<<1|1]);
}
//输出序列 
void output(){
	printf("AT:"); 
	for(int i=1;i<=n;i++)
		printf("%d ",at[i]);
	puts("");
}
//寻找最大 
int findmax(){
	int maxid=1,maxn=at[1];
	for(int i=1;i<=n;i++)
		if(maxn<at[i]){
			maxid=i;
			maxn=at[i];
		}
	return maxid;
}

void run(){
	int ch;
	int id;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				id=findmax(); 
				printf("最大值为:%d 及其左指针:%d，右指针:%d\n",at[id],id<<1,id<<1|1);
				break;
			case 2:
				printf("高度为%d\n",h(n));break;
			case 3:
				printf("宽度为%d\n",b(n));break;
			case 4:
				SW();break;
			case 5:
				output();break; 
		}
	}while(ch);
}


int main(){
	printf("输入节点个数：");
	cin>>n;
	printf("输入节点内容："); 
	for(int i=1;i<=n;i++)
		cin>>at[i];
	run();
	return 0;
}

4. 树的建立及其操作

基本要求：

  1. 树的建立：以(结点编号,结点数据，父结点编号)的形式从键盘输入一棵n叉树（n≥3），根结点的父结点编号为-1，将树按双亲表示法存储在一位数组中。
  2. 树的输出：将所建立的按双亲表示法存储的树转换形成按孩子—兄弟链表法的形式保存并输出。
  3. 树的先序遍历：按先序遍历方式对树进行遍历，输出对应的遍历序列。
  4. 树的后序遍历：按后序遍历方式对树进行遍历，输出对应的遍历序列。
  5. 树的层次遍历：按层次遍历方式对树进行遍历，输出对应的遍历序列。
  6. 树中结点度的统计：分别统计树中度为0、1、2…的结点数目。
  7. 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
#include<bits/stdc++.h>

using namespace std;

const int N=1000;

#define poly vector<int>
#define pb push_back

struct parent{
	int pa;
	string dat;
}p[N];
int vis[N];
int deg[N];//度数 
poly g[N];
int root;//根节点
int n;//结点总数+1; 

void add(int u,int v){g[u].pb(v);deg[v]++;}
//层次遍历 
void bfs(int root){
	 memset(vis,0,sizeof(vis));
	 queue<int> q;
	 q.push(root);
	 while(!q.empty()){
	 	int x=q.front();q.pop();
	 	vis[x]=1;
	 	cout<<p[x].dat<<" ";
	 	for(int i=0;i<g[x].size();i++){
	 		int y=g[x][i]; 
			if(!vis[y]){
	 			vis[y]=1;
	 			q.push(y);
			}
		}
	 }
	 puts("");
}
//双亲表示法 
void outputPa(){
	printf("数组下标 data parent\n"); 
	for(int i=0;i<=n;i++)
		cout<<i<<" "<<p[i].dat<<" "<<p[i].pa<<endl; 
} 
//孩子表示法 
void ouputson(){
	printf("孩子表示法：\n");
	for(int x=0;x<=n;x++){
		cout<<p[x].dat<<": ";
		for(int i=0;i<g[x].size();i++)
			printf("%d ",g[x][i]);
		puts("");
	}
 
}
//输出度数 
void outputDeg(){
	for(int i=0;i<=n;i++)
		cout<<p[i].dat<<"的度数为："<<deg[i]<<endl; 
} 

//先序 
void Firorder(int x){
	vis[x]=1;
	cout<<p[x].dat<<" ";
	for(int i=0;i<g[x].size();i++){
	 	int y=g[x][i]; 
		if(!vis[y]){
			Firorder(y);
		}
	}
} 
//后序 
void Lasorder(int x){
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
	 	int y=g[x][i]; 
		if(!vis[y]){
			Lasorder(y);
		}
	}
	cout<<p[x].dat<<" ";
}

void menu(){
	printf("\n1.双亲表示法\n");
	printf("2.孩子兄弟表示法\n");
	printf("3.树的先序遍历\n");
	printf("4.树的后序遍历\n");
	printf("5.树的层次遍历\n");
	printf("6.节点度数统计\n");
	printf("输入你的选择："); 
}

void run(){
	int ch;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				outputPa();break; 
			case 2:
				ouputson();break;
			case 3:
				memset(vis,0,sizeof(vis));
				Firorder(root);
				puts(" "); 
				break; 
			case 4:
				memset(vis,0,sizeof(vis));
				Lasorder(root);
				break;
			case 5:bfs(root);break; 
			case 6:outputDeg();break; 
		}
	}while(ch);
}
int main(){
	int u,v;
	string val;
	while(1){
		printf("输入结点编号，结点数据，父亲结点编号(当输入-999中断)：");
		cin>>v;
		if(v==-999) break;
		cin>>val;cin>>u;
		p[v]={u,val};
		
		n=max(n,max(u,v));//记录最大结点编号 
		if(u==-1){
			root=v;
			continue;
		}
		add(u,v);
		add(v,u);
	}
	run();
}
//测试数据 
/*
0 R -1
1 A 0
2 B 0
3 C 0
4 D 1
5 E 1
6 F 3
7 G 6
8 H 6
9 K 6
-999 
*/

5. 哈夫曼编/译码系统

问题描述：
利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。对于双工信道 (即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。
基本要求：
一个完整的系统应具有以下功能：

  1. I:初始化 (Initialization)。从终端读入字符集大小n，及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。
  2. C:编码 (Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。
  3. D:解码 (Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。
  4. P:印代码文件 (Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。
  5. T:印哈夫曼树 (Tree printing)。将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

实现提示
根据题目要求把程序划成5个模块，设计成菜单方式，每次执行一个模块后返回菜单。
除了初始化(I)过程外，在每次执行时都经过一次读取磁盘文件数据。这是为了如果在程序执行后一直没有进行初始化(I)过程，为了能使后面的操作顺利进行，可以通过读取旧的数据来进行工作。比如：如果程序的工作需要的字符集和权值数据是固定的，只要在安装程序时进行一次初始(I)化操作就可以了。再在次运行程序时，不管进行哪项操作都可以把需要的数据读入到内存。
测试数据
根据实验要求，在tobetrans.dat中输入"THIS PROGRAM IS MY FAVORITE"，字符集和其频度如下：（”一”表示空格 ）
在这里插入图片描述

#include<bits/stdc++.h>

using namespace std;

#define pic pair<int,char>

const int N=1000;

pic p[N];

#define lc T[p].l
#define rc T[p].r

struct Huffman{
	int l,r;//左右孩子 
	int dat;//频数 
	char c;//字符 
	string id;//每个字符的编码id 
}T[N];
int root;
map<pic,int> ID;
int tot=0;
//分配下标 
int getid(pic a){
	if(ID.find(a)!=ID.end()) return ID[a];
	ID.insert({a,++tot}); 
	return ID[a];
} 

map<char,string> mp;

//建立huffman树 
void build(int n){
	priority_queue<pic> q;
	int ans=0;
	for(int i=1;i<=n;i++) q.push({-p[i].first,p[i].second});
	while(q.size()>1){
		pic a=q.top();q.pop();
		pic b=q.top();q.pop();
		ans=-a.first-b.first;
		if(a.first<b.first) swap(a,b);
		q.push({-ans,'#'});
		int pid=getid({-ans,'#'});
		int aid=getid(a);
		int bid=getid(b);
		T[pid].dat=ans;T[pid].c='#';T[pid].l=aid;T[pid].r=bid; 
		T[aid].dat=-a.first;T[aid].c=a.second;
		T[bid].dat=-b.first;T[bid].c=b.second;
	}
	root=getid(q.top());
}
//形成每个字符编码 
void dfs(int p){
	if(lc) {
		T[lc].id=T[p].id+'0';
		dfs(lc);
	}
	else{
		mp.insert({T[p].c,T[p].id});
	}
	if(rc){
		T[rc].id=T[p].id+'1';
		dfs(rc);
	}
	else{
		mp.insert({T[p].c,T[p].id});
	}
}
//如果想知道具体的哪个字符编码可以用这个输出 
void output(int n){
	for(int i=1;i<=n;i++)
		cout<<T[i].dat<<" "<<T[i].c<<"  "<<T[i].id<<endl;
} 
//给字符串编码 
string coding(string str){
	int len=str.length();
	string ans="";
	for(int i=0;i<len;i++)
		ans=ans+mp[str[i]];
	return ans;
}
//解码
//其实就是按照01码左右递归huffman树 
void Decode(int p,string s,int i,int len){
	if(i==len) return;
	if(!lc&&!rc) printf("%c",T[p].c);
	if(s[i+1]=='0'){
		if(lc) Decode(lc,s,i+1,len);
		else Decode(root,s,i+1,len); 
	}
	if(s[i+1]=='1'){
		if(rc) Decode(rc,s,i+1,len);
		else Decode(root,s,i+1,len);
	}
}

#undef lc 
#undef rc 

void menu(){
	printf("1.编码\n");
	printf("2.打印编码\n");
	printf("0.退出\n");
	printf("输入选择："); 
}

void run(){
	int ch;
	string code;
	char str[1000];
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入你要编码的内容：");
				getchar();
				gets(str);
				code=str;
				cout<<"编码后:"<<coding(code)<<endl; 
				break;
			case 2:
				printf("输入你要解码的内容：");
				cin>>code;
				printf("解码后:");
				Decode(root,code,0,code.length());
				puts("");
				break;
		}
	}while(ch);
}

int main(){
	int n;
	printf("请输入要读入的字符数：");
	cin>>n;
	printf("输入字符，以及频数\n"); 
	for(int i=1;i<=n;i++){
		char ch;
		int a;
		cin>>ch>>a;
		if(ch=='-'){
			p[i]={a,' '};
		} 
		else p[i]={a,ch};
	}
	build(n);
	T[root].id='0'; 
	dfs(root);
	//output(tot);
	run();
	return 0;
} 
//测试数据： 
/*
27
- 186
A 64
B 23
C 22
D 32
E 103
F 21
G 15
H 47
I 57
J 1
K 5
L 32
M 20
N 20
O 56
P 19
Q 2
R 50
S 51
T 55
U 30
V 10
W 11
X 2
Y 21
Z 2 
*/
//编码内容
/*
THIS PROGRAM IS MY FAVORITE
*/
//对应的解码内容
/*
0011101111001001001100000110100011111010000101001011111010110110110000010010011000001101100110111000011100001011011100100100001111101001001110010
*/

6. 成绩统计分析系统(大水题)

问题描述：
给出n个学生的m门课程的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计分析，并打印统计表。
基本要求：

  1. 通过键盘输入各学生的多门课程的成绩，建立相应的文件input.dat。
  2. 对文件input.dat中的数据进行处理，要求具有如下功能：
    i.按各门课程成绩排序，并生成相应的文件输出。
    ii.计算每人的平均成绩，按平均成绩排序，并生成文件。
    iii.求出各门课程的平均成绩、最高分、最低分、不及格人数、\(60 \sim69\)分人数、\(70\sim79\)分人数、\(80\sim89\)分人数、90分以上人数。
    iv.根据姓名或学号查询某人的各门课成绩，重名情况也能处理。
    测试数据
    在这里插入图片描述
    3.界面美观
  3. 选做内容 对各科成绩设置不同的权值。
#include<bits/stdc++.h>

using namespace std;

const int N=1000; 
int stunum=0;
struct Student{
	string id; 
	string s;
	int sc[4];
	int sum;
	double avg;
}p[N]; 


bool cmp_avg(Student A,Student B){
	return A.avg>B.avg||(A.avg>B.avg&&A.id<B.id);
}
bool cmp_ma(Student A,Student B){
	return A.sc[1]>B.sc[1]||( A.sc[1]==B.sc[1]&&A.id<B.id);
}
bool cmp_en(Student A,Student B){
	return A.sc[2]>B.sc[2]||( A.sc[2]==B.sc[2]&&A.id<B.id);
}
bool cmp_co(Student A,Student B){
	return A.sc[3]>B.sc[3]||( A.sc[3]==B.sc[3]&&A.id<B.id);
}

void cal_course(int x){//x表示那个学科 
	int cnt[5];//不及格，60~69,70~79,80~89,90以上
	memset(cnt,0,sizeof(cnt));
	int max_sc=p[1].sc[x],min_sc=p[1].sc[x];
	double avg_sc=0;
	for(int i=1;i<=stunum;i++){
		max_sc=max(max_sc,p[i].sc[x]);
		min_sc=min(min_sc,p[i].sc[x]);
		avg_sc+=p[i].sc[x];
		if(p[i].sc[x]<60) cnt[0]++;
		else if(p[i].sc[x]<70) cnt[1]++;
		else if(p[i].sc[x]<80) cnt[2]++;
		else if(p[i].sc[x]<90) cnt[3]++;
		else if(p[i].sc[x]<=100) cnt[4]++;
	} 
	printf("%s成绩分布如下:\n",x==1?"数学":x==2?"英语":"计算机");
	printf("最高分:%d\n",max_sc);
	printf("最低分:%d\n",min_sc);
	printf("平均分:%.2lf\n",1ll*avg_sc/stunum);
	printf("不及格人数:%d\n",cnt[0]);
	printf("60~69分人数:%d\n",cnt[1]);
	printf("70~79分人数:%d\n",cnt[2]);
	printf("80~89分人数:%d\n",cnt[3]);
	printf("90以上人数:%d\n",cnt[4]);
	
}

void input(){
	//当输入#结束 
	string id; 
	char s[30];
	int sc[4];
	printf("%5s %4s %4s %4s %4s  %15s","学号","姓名","数学","英语","计算机","(当输入#结束)\n");
	while(1){
		cin>>id;
		if(id[0]=='#') break;
		cin>>s>>sc[1]>>sc[2]>>sc[3];
		p[++stunum].id=id;
		p[stunum].s=s;
		p[stunum].sc[1]=sc[1];
		p[stunum].sc[2]=sc[2];
		p[stunum].sc[3]=sc[3];
		p[stunum].sum=sc[1]+sc[2]+sc[3];
		p[stunum].avg=1ll*p[stunum].sum/3;
	}
	printf("%5s %4s %4s %4s %4s","学号","姓名","数学","英语","计算机\n");
}

void output(){
	printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n");
	for(int i=1;i<=stunum;i++){
		cout<<p[i].id<<" "<<p[i].s<<" ";
		printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg);
	}
	puts("");
}

void search_name(char *name){
	bool find=0;
	
	for(int i=1;i<=stunum;i++){
		if(name==p[i].s){
			find=1;
			printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n");
			cout<<p[i].id<<" "<<p[i].s<<" ";
			printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg);
		}
	}
	if(!find) printf("不存在！\n"); 
	puts("");
}

void search_id(char *str){
	bool find=0;
	for(int i=1;i<=stunum;i++){
		if(str==p[i].id){
			find=1;
			printf("%5s %10s %4s %4s %4s %4s %8s","学号","姓名","数学","英语","计算机","总分","平均分\n");
			cout<<p[i].id<<" "<<p[i].s<<" ";
			printf("%4d %4d %4d %4d %.2lf\n",p[i].sc[1],p[i].sc[2],p[i].sc[3],p[i].sum,p[i].avg);
		}
	}
	if(!find) printf("不存在！\n");
	puts("");
}

void menu(){
	printf("1.通过键盘输入各学生的多门课程的成绩\n");
	printf("2.按各门课程成绩排序\n");
	printf("3.计算每人的平均成绩，按平均成绩排序\n");
	printf("4.求出各门课的成绩情况\n"); 
	printf("5.根据姓名或者成绩查询某人的成绩\n");
	printf("0.退出\n"); 
	printf("输入选择："); 
}

void run(){
	int ch;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:input();break;
			case 2:printf("1.数学，2.英语，3.计算机\n");
					int x;cin>>x;
					if(x==1) {sort(p+1,p+1+stunum,cmp_ma);output();}
					else if(x==2) {sort(p+1,p+1+stunum,cmp_en);output();}
					else if(x==3) {sort(p+1,p+1+stunum,cmp_co);output();}
					break;
			case 3: sort(p+1,p+1+stunum,cmp_avg);output();break;
			case 4:printf("1.数学，2.英语，3.计算机\n");
				cin>>x;cal_course(x);break;
			case 5
			:printf("1.学号，2.姓名\n");
				cin>>x;
				if(x==1){
					char s[30];
					printf("输入学号：");
					scanf("%s",s);
					search_id(s); 
				}
				else if(x==2){
					char s[30];
					printf("输入名字：");
					scanf("%s",s);
					search_name(s); 
				}
				break; 
			
		} 
	}while(ch);
	
}

int main(){
	run();
	return 0;
}
/*
001 王放 78 70 90
002 张强 89 67 88
003 李浩 56 67 78
004 黄鹂兵 89 86 85
005 李浩 67 88 76
006 陈利风 45 54 67
007 尚晓 78 76 70
*/

7. 超市商品汇总系统

问题描述：
在数据处理中经常需要对大量数据进行汇总，将相同关键字记录的某些数据项的值叠加起来，生成一个分类汇总表。
假设某超级市场销售有m种商品，商品的基本信息保存在一个顺序表中，每件商品的基本信息包括：商品编号（为随机生成的[1000,9999]之间的4位数字字符）、商品名称（不超过12位的字符串）、单价。
该超级市场有n台前台收款机（假设收款机的编号为1，2，3，┅┅，n）进行收款，以记录的形式提供给计算机，每个记录表示某台收款机的一种商品一次交易的数量和销售额。收款记录由5个数据项组成：收款机编号、商品编号（输入并且必须在商品信息表中存在）、销售数量（输入）、单价、销售金额。构造一个结构体类型，每次销售数据以一个结构体变量保存在一个数据文件中。
实现要求：

  1. 编写实现将商品基本信息生成和输入并按商品编号有序保存在顺序表中的函数；
  2. 编写实现将数据记录插入到数据文件最后的函数；
  3. 编写以收款机为单位的数据分类处理函数。构造n个单链表，每个链表保存一台收款机的销售记录，这n个单链表的头指针存放在一个指针数组中，通过数组的下标就可以知道是哪台收款机。读取数据文件的记录，将所有的销售记录(数据文件中的全部记录)分解插入到n个单链表；
  4. 统计每台收款机的销售总额；
  5. 编写以商品为单位的数据分类处理函数。构造m个单链表，每个链表保存一种商品的销售记录，这m个单链表的头指针存放在一个指针数组中，通过数组的下标就可以知道是哪种商品。读取数据文件的记录，将所有的销售记录(数据文件中的全部记录)分解插入到m个单链表；
  6. 以商品为单位，统计每种商品的销售总额。
  7. 设计一个菜单，具有插入数据记录、按收款机统计销售总额、按商品统计销售总额、退出系统等最基本的功能。
#include<bits/stdc++.h>

using namespace std;

const int N=10000;
//随机数 
int random(){
	return ((long long)rand()*rand()+1000)%10000; 
}
int n;
//商品信息 
struct Product{
	int id;
	string name;
	int price;
}pdat[N];
map<string,int> pro;//商品映射商品编号 
//商品是否存在 
int is_exist(string a){
	return pro.find(a)==pro.end()?0:1;
}
//分配商品编号 
int getid(string a){
	if(pro.find(a)!=pro.end()) return pro[a];
	pro.insert({a,random()});
	return pro[a];
} 
//添加商品 
void addpro(int id,string na,int price){
	pdat[id].id=id;pdat[id].name=na;
	pdat[id].price=price;
}
//输出商品信息 
void output(int id){
	cout<<"商品编号："<<id<<" 商品名称："<<pdat[id].name<<" 单价："<<pdat[id].price<<endl; 
}
//交易单信息 
struct Pay{
	int id,pid;//收款机id,商品id 
	int price,times,cost;
}py[N];
int head[N],nex[N],tot=0;//链表 
int gain[N];//收款机总额 
int procost[N];//商品总额 
int Head[N],Nex[N];//链表 
//新增交易单 
void add(int id,int pid,int times){
	nex[++tot]=head[id];
	py[tot].id=id;
	py[tot].times=times,py[tot].pid=pid;
	py[tot].price=pdat[pid].price;
	py[tot].cost=times*pdat[pid].price;
	head[id]=tot;
	procost[pid]+=py[tot].cost;
	
	Nex[tot]=Head[pid];
	Head[pid]=tot;
	gain[id]+=py[tot].cost;
	/***/
}


//输出具体单信息 
void outputPy(int i){
	int x=py[i].pid; 
	cout<<"收款机编号："<<py[i].id<<"商品编号："<<x<<" 商品名称："<<pdat[x].name<<" 单价："<<pdat[x].price<<" 总价："<<py[i].cost<<endl;
}
//以收款机输出交易记录 
void DisByMac(int x){
	printf("交易记录：\n");
	for(int i=head[x];i;i=nex[i]){
		 outputPy(i);
	}
}
//以商品输出交易记录 
void DisByPro(int x){
	printf("交易记录：\n");
	for(int i=Head[x];i;i=Nex[i]){
		 outputPy(i);
	}
} 

void menu(){
	printf("\n\n1.新增商品基本信息生成和输入\n");
	printf("2.交易一次\n"); 
	printf("3.统计收款机的销售总额\n");
	printf("4.以商品为单位，统计每种商品的销售总额。\n");
	printf("5.商品销售记录\n");
	printf("6.收款机交易记录\n");
	printf("0.退出\n");
	printf("输入你的选择：");
}

void run(){
	int ch;
	int m,price,times;
	string na;
	memset(head,0,sizeof(head));
	memset(Head,0,sizeof(Head));
	memset(gain,0,sizeof(gain)); 
	memset(procost,0,sizeof(procost)); 
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入你要添加的商品的个数:");
				cin>>m;
				printf("输入商品名字,单价\n");
				for(int i=1;i<=m;i++){
					cin>>na>>price;
					addpro(getid(na),na,price);
					output(getid(na));
				} 
				break;
			case 2:
				printf("在那台机器交易(1~%d)：",n);
				cin>>m;
				if(1<=m&&m<=n){
					printf("购买商品名字，数量:");
					cin>>na>>times;
					if(is_exist(na)){
						add(m,getid(na),times);
					}
					else{
						printf("不存在该商品！\n"); 
					}
				} 
				else{
					printf("不存在该机器！\n"); 
				}
				break;
			case 3:
				printf("输入收款机编号：");
				cin>>m; 
				if(1<=m&&m<=n){
					printf("%d号收款机交易额:%d\n",m,gain[m]);
				} 
				else{
					printf("不存在该机器！\n"); 
				}
				break;
			case 4:
				printf("购买商品名字");
				cin>>na;
				if(is_exist(na)){
					cout<<"商品"<<na<<"交易额："<<procost[getid(na)]<<endl; 
				}
				else{
					printf("不存在该商品！\n"); 
				}
				break;
			case 5:
				printf("购买商品名字");
				cin>>na;
				if(is_exist(na)){
					DisByPro(getid(na));
				}
				else{
					printf("不存在该商品！\n"); 
				}
				break;
			case 6: 
				printf("输入收款机编号：");
				cin>>m; 
				if(1<=m&&m<=n){
					DisByMac(m);
				} 
				else{
					printf("不存在该机器！\n"); 
				}
				break;
		}
	}while(ch);
} 

int main(){
	printf("请输入收款机数量："); 
	cin>>n; 
	run();
	return 0;
}

8. 哈希表的设计与实现

问题描述： 设计散列表实现电话号码查找系统。
基本要求：

  1. 设每个记录有下列数据项：电话号码、用户姓名、地址；
  2. 从文件输入各记录，分别以电话号码和用户名为关键字建立散列表；（假设人名为中国人姓名的汉语拼音形式zhoukunxiao）
  3. 采用一定的方法解决冲突；（哈希函数可以用数字分析法和除留余数法构造，用线性探测再散列法或链地址法处理冲突）
  4. 查找并显示给定电话号码的记录；
  5. 查找并显示给定用户姓名的记录。

测试数据:
取班级较熟悉的30个同学记录。
{选作内容}

  1. 从课本上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的记录集合作实验）。
  2. 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音姓名一定不发生地址冲突。
  3. 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
#include<bits/stdc++.h>

using namespace std;


const int N=1000;
const int mod=99;

int head[N],nex[N];
int tot;
string Name[N];
string Phone[N];

int h(string na){
	int len=na.length();
	int ans=1;
	for(int i=0;i<len;i++)
		ans=(ans*131+na[i]-'a')%mod;
	return ans;
}

int H(string ph){
	int len=ph.length();
	int ans=0;
	for(int i=0;i<len;i++)
		ans=(ans*10+ph[i]-'0')%mod;
	return ans;
}

bool insertByna(string na,string ph){//以名字作为地址插入
	int val=h(na);
	for(int i=head[val];i;i=nex[i]){
		if(Name[i]==na) return 1;
 	}
 	++tot;
 	Name[tot]=na;
 	Phone[tot]=ph;
 	nex[tot]=head[val];
 	head[val]=tot;
 	return 0;
}

bool insertByph(string na,string ph){//以名字作为地址插入
	int val=H(ph);
	for(int i=head[val];i;i=nex[i]){
		if(Phone[i]==ph) return 1;
 	}
 	++tot;
 	Name[tot]=na;
 	Phone[tot]=ph;
 	nex[tot]=head[val];
 	head[val]=tot;
 	return 0;
}

int FindPh(string na){//查找电话 
	int val=h(na);
	for(int i=head[val];i;i=nex[i]){
		if(Name[i]==na) return i;
 	}
 	return 0;
}

int FindNa(string ph){//查找名字 
	int val=H(ph);
	for(int i=head[val];i;i=nex[i]){
		if(Phone[i]==ph) return i;
 	}
 	return 0;
}

void output(int x){
	cout<<"名字："<<Name[x]<<" 电话："<<Phone[x]<<endl; 
}


void menu(){
	printf("1.输入记录\n");
	printf("2.根据姓名查询\n");
	printf("3.根据电话查询\n");
	printf("0.退出\n");
	printf("输入你的选择:"); 
	
}

void run(){
	int ch;
	string name,phone;
	int x;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				int n;
				printf("需要插入记录的数：");cin>>n;
				printf("输入姓名和电话：");
				for(int i=1;i<=n;i++){
					cin>>name>>phone;
					insertByna(name,phone);
					insertByph(name,phone);
				}
				break;			 
			case 2:
				printf("输入姓名：");
				cin>>name;
				if((x=FindPh(name))){
					output(x); 
				}
				else{
					printf("不存在!\n");
				}
				break;
			case 3:
				printf("输入姓名：");
				cin>>phone;
				if((x=FindNa(phone))){
					output(x); 
				}
				else{
					printf("不存在!\n");
				}
				break;
		}
	}while(ch);
}

int main(){
	run();
	return 0;
}

9. 旅游区导游图系统

问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。
以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构。
基本要求：

  1. 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。
  2. 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。
  3. 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
  4. 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
  5. 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。
  6. 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define piii pair<pii,int>

const int N=1000;
int head[N],nex[N],to[N],edge[N],tot;
int pa[N];
int n,m;
int vis[N];
int dist[N];

void add(int u,int v,int w){//邻接链表 
	to[++tot]=v,nex[tot]=head[u],edge[tot]=w;
	head[u]=tot;
}

void menu(){
	printf("1.旅游景点图的输出\n");
	printf("2.相邻景点查询\n"); 
	printf("3.景点路线查询\n");
	printf("4.景点路线综合查询\n");
	printf("5.最佳旅游路线确定\n");
	printf("0.退出\n");
	printf("请输入你的选择："); 
}

void dijkstra(int st,int flag){//dijkstra算法 
	priority_queue<pii> q;
	q.push({0,st});
	memset(dist,0x3f3f3f3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[st]=0;
	while(!q.empty()) {
		pii pt=q.top();q.pop();
		int u=pt.second;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			int v=to[i];
			if(dist[v]>=dist[u]+edge[i]){
				dist[v]=dist[u]+edge[i];
				pa[v]=u;
				q.push({-dist[v],v});
				if(flag){
					printf("%d->%d",st,v); 
					printf("路径：\n");
					for(int j=v;j;j=pa[j]){
						printf("%d%s",j,j==st?" ":"<-");
					}
					printf("   长度：%d\n",dist[v]);
				}
			}
		}
	}
}


int ans=100000000;
int endp;
int dir[N];
int a[N]; //开辟路径 
int len;


//因为空间有限，开不了多维数组，采用二进制表示状态 
//s是状态  第几位为1表示去过了，为0没去过 

void dfs(int s,int u,int dist,int q){ 
	if((s==(1<<n)-1)){
		if(ans>dist){ //比当前短，保存下来 
			ans=dist;  //保存路径长度 
			memcpy(dir,a,sizeof(dir)); //保存路径 
			endp=u;  //保存最后到的点 
			len=q;   //保存路径上的点个数 
		}
		return;
	}
	for(int i=head[u];i;i=nex[i]){
		int v=to[i];
			a[q]=v;
			if(vis[v]==2) continue;//只能去两次 
			vis[v]++;
			//把s右v-1位跟1与，如第v-1位为1则ture,否则false 
			if(s>>(v-1)&1)  dfs(s,v,dist+edge[i],q+1);//去过了v点，不用改变状态 
			else  dfs(s^(1<<(v-1)),v,dist+edge[i],q+1);//把s的第v-1为变为1 
			vis[v]--;
		}
}

int Edge[N][N] ;
void to_EDGE(){
	memset(Edge,-1,sizeof(Edge));
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=nex[j]){
			Edge[i][to[j]]=edge[j];
		}
}

void run(){
	int ch;
	do{
		menu();
		cin>>ch;
		switch(ch){
			int st,en;
			case 1:
				to_EDGE();
				printf("邻接矩阵：\n"); 
				for(int i=1;i<=n;i++)
					for(int j=1;j<=n;j++)
						printf("%3d%c",Edge[i][j],j==n?'\n':' ');
				puts("");
				printf("邻接表：\n"); 
				for(int i=1;i<=n;i++){
					printf("%d:",i);
					for(int j=head[i];j;j=nex[j]){
						printf("%3d ",to[j]);
					}
					puts(" ");
				}
				break;
			case 2:
				printf("输入起点：");
				cin>>st;
				for(int i=head[st];i;i=nex[i])
					printf("%d -> %d : %d\n",st,to[i],edge[i]); 
				break;
			case 3:
				printf("输入起点：");
				cin>>st;
				dijkstra(st,1);
				break;
			case 4:
				printf("输入起点，终点：");
				cin>>st>>en;
				memset(pa,0,sizeof(pa));
				dijkstra(st,0);
				printf("路径：\n");
				for(int i=en;i;i=pa[i]){
					printf("%d ",i);
				}
				puts("");
				break; 
			case 5:
				printf("输入起点：");
				cin>>st;
				memset(pa,0,sizeof(pa)); 
				dijkstra(st,0);
				memset(vis,0,sizeof(vis));
				dfs((1<<(st-1)),st,0,1);
				dir[0]=st;
				printf("路径：\n");
				for(int i=0;i<len;i++) printf("%d ",dir[i]);
				for(int i=endp;i;i=pa[i]){
					if(i==endp) continue;
					printf("%d ",i);
				}
				printf("\n长度：%d\n",ans+dist[endp]);
				break;
		}
		
	}while(ch);
}



int main(){
	printf("输入点数，边数："); 
	cin>>n>>m;
	printf("输入起点 终点  路径长度：\n"); 
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	run();
	return 0;
}
//测试数据 
/*
4 4
1 4 1
1 2 4
2 4 5
2 3 3
*/

10. 校园路线导游系统

问题描述
用无向网表示东莞理工学院的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
基本要求

  1. 查询各景点的相关信息；
  2. 查询图中任意两个景点间的最短路径。
  3. 查询图中任意两个景点间的所有路径。
  4. 增加、删除、更新有关景点和道路的信息。

选作内容

  1. 求多个景点的最佳（最短）游览路径。
  2. 实现导游图的仿真界面。(有一说一，我不会)
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define piii pair<pii,int>

const int N=1000;
int head[N],nex[N],to[N],edge[N],tot;
int pa[N];
int n,m;
int vis[N];
int dist[N];

void add(int u,int v,int w){//邻接链表 
	to[++tot]=v,nex[tot]=head[u],edge[tot]=w;
	head[u]=tot;
}


int ans=100000000;
int endp;
int dir[N];
int a[N]; //开辟路径 
int len;

int sta=0;

void dijkstra(int st){//dijkstra算法 
	priority_queue<pii> q;
	q.push({0,st});
	memset(dist,0x3f3f3f3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[st]=0;
	while(!q.empty()) {
		pii pt=q.top();q.pop();
		int u=pt.second;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			int v=to[i];
			if(dist[v]>=dist[u]+edge[i]){
				dist[v]=dist[u]+edge[i];
				pa[v]=u;
				q.push({-dist[v],v});
			}
		}
	}
}

//因为空间有限，开不了多维数组，采用二进制表示状态 
//s是状态  第几位为1表示去过了，为0没去过 

void dfs(int s,int u,int dist,int q){ 
	if((s|sta)==s){
		if(ans>dist){ //比当前短，保存下来 
			ans=dist;  //保存路径长度 
			memcpy(dir,a,sizeof(dir)); //保存路径 
			endp=u;  //保存最后到的点 
			len=q;   //保存路径上的点个数 
		}
		return;
	}
	for(int i=head[u];i;i=nex[i]){
		int v=to[i];
			a[q]=v;
			if(vis[v]==2) continue;//只能去两次 
			vis[v]++;
			//把s右v-1位跟1与，如第v-1位为1则ture,否则false 
			if(s>>(v-1)&1)  dfs(s,v,dist+edge[i],q+1);//去过了v点，不用改变状态 
			else  dfs(s^(1<<(v-1)),v,dist+edge[i],q+1);//把s的第v-1为变为1 
			vis[v]--;
		}
}

void DFS(int u,int ed,int dist,string path){
	if(u==ed) {
		cout<<path<<"  长度为"<<dist<<endl;
		return;
	}
	for(int i=head[u];i;i=nex[i]){
		int v=to[i];
		if(!vis[v]){
			vis[v]=1;
			DFS(v,ed,dist+edge[i],path+"->"+to_string(v));
			vis[v]=0;
		}
	}
}

void search(int x){
	printf("%d景点附近景点:\n",x);
	for(int i=head[x];i;i=nex[i]){
		printf("---%d景点距离为%d\n",to[i],edge[i]);
	} 
} 

void menu(){
	printf("\n1.查询景点信息\n"); 
	printf("2.查询两点之间最短路径\n");
	printf("3.查询途中两个景点所有路径\n"); 
	printf("4.增加道路\n");
	printf("5.删除道路\n"); 
	printf("6.更新道路信息\n"); 
	printf("7.求多个景点的最佳(最短)游览路径\n");
	printf("输入选择："); 
} 


void update(int u,int v,int w){
	for(int i=head[u];i;i=nex[i]){
		if(to[i]==v){
			 edge[i]=w;break;
		}
	}
	for(int i=head[v];i;i=nex[i]){
		if(to[i]==u){
			 edge[i]=w;break;
		}
	} 
} 

void del(int u,int v){
 	int q=head[u];
 	if(to[q]==v){
 		head[u]=nex[q];
	}
	for(int i=head[u];i;i=nex[i]){
		if(to[i]==v){
			nex[q]=nex[i];
			break;
		}
		q=i;
	}
	q=head[v];
 	if(to[q]==u){
 		head[v]=nex[q];
	}
	for(int i=head[v];i;i=nex[i]){
		if(to[i]==u){
			nex[q]=nex[i];
			break;
		}
		q=i;
	}
}


void run(){
	int ch,st,en,x;
	int u,v,w;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入你要查询的景点:");
				int x;cin>>x;
				search(x); 
				break;
			case 2:
				printf("输入起点，终点：");
				cin>>st>>en;
				memset(pa,0,sizeof(pa));
				dijkstra(st);
				printf("路径：\n");
				for(int i=en;i;i=pa[i]){
					printf("%d ",i);
				}
				puts("");
				break; 
			case 3:
				printf("输入起点，终点：");
				memset(vis,0,sizeof(vis));
				cin>>st>>en;
				vis[st]=1;
				DFS(st,en,0,to_string(st));
				break;
			case 4:
				printf("输入起点，终点，长度");
				cin>>u>>v>>w;
				add(u,v,w);
				add(v,u,w);
				break;
			case 5:
				printf("输入起点，终点");
				cin>>u>>v;
				del(u,v);
				break;
			case 6:
				printf("输入起点，终点，长度\n");
				cin>>u>>v>>w;
				update(u,v,w);
				break;
			case 7:
				printf("请输入经过的点的个数:");
				int sn;cin>>sn;
				printf("请输入经过的点:");
				for(int i=1;i<=sn;i++){
					int a;
					cin>>a;
					sta|=1<<(a-1);
				}
				memset(vis,0,sizeof(vis));
				for(int st=1;st<=n;st++){
					a[0]=st;
					dfs((1<<(st-1)),st,0,1);
				}
				cout<<ans<<endl;
				printf("路径：\n");
				for(int i=0;i<len;i++) printf("%d ",dir[i]);
				break;
		}
	}while(ch);
}

int main(){
	printf("输入点数，边数："); 
	cin>>n>>m;
	printf("输入起点，终点，长度\n");
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	run();
}

//测试数据 
/*
4 4
1 4 1
1 2 4
2 4 5
2 3 3
*/

11. 地图导航查询系统(最短路径问题）

问题描述： 设计一个系统，实现地图的管理和最短路径查询
基本要求：

  1. 能够添加，删除和修改地图点和边的信息；
  2. 给出两点能够找出最短路径方案；
  3. 较好的交互界面；
  4. 地图信息的永久性保存和读取。

数据结构:
设计合适的数据结构组织数据，设计算法实现需求

在这里插入图片描述

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

#define ll long long
#define pii pair<int,int>
#define piii pair<pii,int>

const int N=1000;
int head[N],nex[N],to[N],edge[N],tot;
int pa[N];
int n,m;
int vis[N];
int dist[N];
map<string,int> city;
map<int,string> ct; 
int ccnt;
int get(string c){
	if(city.find(c)!=city.end()) return city[c];
	city[c]=++ccnt;
	ct[ccnt]=c;
	return city[c];
} 


void add(int u,int v,int w){//邻接链表 
	to[++tot]=v,nex[tot]=head[u],edge[tot]=w;
	head[u]=tot;
}


void dijkstra(int st){//dijkstra算法 
	priority_queue<pii> q;
	q.push({0,st});
	memset(dist,0x3f3f3f3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[st]=0;
	while(!q.empty()) {
		pii pt=q.top();q.pop();
		int u=pt.second;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			int v=to[i];
			if(dist[v]>=dist[u]+edge[i]){
				dist[v]=dist[u]+edge[i];
				pa[v]=u;
				q.push({-dist[v],v});
			}
		}
	}
}


void menu(){
	printf("1.查询两点之间最短路径\n");
	printf("2.添加路径\n"); 
	printf("3.删除路径\n");
	printf("4.更新路径\n");
	printf("0.退出"); 
	printf("输入你的选择:"); 
} 


void update(int u,int v,int w){
	for(int i=head[u];i;i=nex[i]){
		if(to[i]==v){
			 edge[i]=w;break;
		}
	}
	for(int i=head[v];i;i=nex[i]){
		if(to[i]==u){
			 edge[i]=w;break;
		}
	} 
} 

void del(int u,int v){
 	int q=head[u];
 	if(to[q]==v){
 		head[u]=nex[q];
	}
	for(int i=head[u];i;i=nex[i]){
		if(to[i]==v){
			nex[q]=nex[i];
			break;
		}
		q=i;
	}
	q=head[v];
 	if(to[q]==u){
 		head[v]=nex[q];
	}
	for(int i=head[v];i;i=nex[i]){
		if(to[i]==u){
			nex[q]=nex[i];
			break;
		}
		q=i;
	}
}


void run(){
	int ch;
	string st,en;
	int w;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入起点，终点：");
				cin>>st>>en;
				memset(pa,0,sizeof(pa));
				dijkstra(get(st));
				printf("路径：\n");
				for(int i=get(en);i;i=pa[i]){
					cout<<ct[i]<<" ";
				}
				printf("长度：%d\n",dist[get(en)]); 
				puts("");
				break; 
			case 2:
				printf("输入起点，终点，长度");
				cin>>st>>en>>w;
				add(get(st),get(en),w);
				add(get(en),get(st),w);
				break;
			case 3:
				printf("输入起点，终点");
				cin>>st>>en;
				del(get(st),get(en));
				break;
			case 4:
				printf("输入起点，终点，长度\n");
				cin>>st>>en>>w;
				update(get(st),get(en),w);
				break;
		}
	}while(ch);
}

int main(){
	printf("输入点数，边数："); 
	cin>>n>>m;
	string a,b;
	printf("输入起点，终点，长度\n");
	for(int i=1;i<=m;i++){
		int w;
		cin>>a>>b>>w;
		add(get(a),get(b),w);
		add(get(b),get(a),w);
	}
	run();
}

//测试数据 
/*
25 28
广州 深圳 140
广州 株洲 675
株洲 柳州 672
株洲 武汉 509
株洲 南昌 367
株洲 贵阳 902
柳州 南宁 255
柳州 贵阳 607
贵阳 昆明 639
贵阳 成都 1100
武汉 郑州 534
南昌 福州 622
南昌 上海 825
上海 徐州 651
郑州 徐州 349
郑州 西安 511
郑州 北京 695
徐州 田径 674
西安 兰州 676
兰州 西宁 216
兰州 乌鲁木齐 1892
兰州 呼和浩特 1145
呼和浩特 北京 668
天津 北京 137
天津 沈阳 704
沈阳 长春 305
沈阳 大连 397
长春 哈尔滨 242 
*/

12. 通信线路的敷设问题

问题描述
若要在下图中的13个城市之间建设通信网络，只需要敷设12条线路即可，边上的数字为两个城市之间建设线路的花费，单位：拾万元。如何以最低的经济代价建设这个通信网，是一个网的最小生成树的问题。
在这里插入图片描述
基本要求

  1. 以邻接矩阵方式保存图的数据，并以邻接链表的形式输出图的数据；
  2. 以边表方式保存图的数据，并以邻接矩阵方式的形式输出图的数据；
  3. 用Prim算法求网的最小生成树，并以邻接链表的形式显示所求得的最小生成树，然后计算敷设相应的通信网的总造价
  4. 用Kruskal算法求网的最小生成树，并以邻接链表的形式显示所求得的最小生成树，然后计算敷设相应的通信网的总造价；
  5. 整个应用设计成一个菜单，具有上述功能要求和退出系统的基本的功能；
#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int> 

const int N=1000;
int head[N],to[N],nex[N],tot=0;
int G[100][100];//邻接矩阵

int n,m; 
int vis[N];
int d[N];
void add(int a,int b){
	to[++tot]=b,nex[tot]=head[a];head[a]=tot;
}
struct rec{int x,y,z;}Edge[N];
bool cmp(rec a,rec b){return a.z<b.z;}
int fa[N],ans;
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}//并查集

void output(){
	for(int x=1;x<=n;x++){
		printf("%3d:",x);
		for(int i=head[x];i;i=nex[i])
			printf("%3d ",to[i]);
		puts("");
	}
}

void kruskal(){
	memset(head,0,sizeof(head));
	tot=0;
	sort(Edge+1,Edge+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	ans=0;
	for(int i=1;i<=m;i++){
		int x=get(Edge[i].x);
		int y=get(Edge[i].y);
		if(x==y) continue;
		fa[x]=y;
		add(Edge[i].x,Edge[i].y);
		add(Edge[i].y,Edge[i].x); 
		ans+=Edge[i].z;
	}
	cout<<" 最小生成树如下："<<endl;output();
	cout<<" 总的造价："<<ans<<endl; 
}

void prime(){
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	memset(head,0,sizeof(head));
	pii ed[N];//存最小生成树的边 
	tot=0;
	d[1]=0;
	for(int i=1;i<n;i++){
		int x=0;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&(x==0||(d[j]<d[x]))) x=j;
		vis[x]=1;
		int idx;
		for(int y=1;y<=n;y++)
			if(!vis[y]){
				if(d[y]>G[x][y]){
					 d[y]=G[x][y];
					 ed[y]={x,y};
				}
			}
	}
	ans=0;
	for(int i=2;i<=n;i++){
		ans+=d[i];
		add(ed[i].first,ed[i].second);
		add(ed[i].second,ed[i].first);
	}
	cout<<" 最小生成树如下："<<endl;output();
	cout<<" 总的造价："<<ans<<endl; 
}

void MatoEdge(){
	memset(head,0,sizeof(head));
	tot=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(G[i][j]!=0&&G[i][j]!=0x3f3f3f3f)
				add(i,j);
}

void menu(){
	printf("1.以邻接链表输出图的数据\n");
	printf("2.邻接矩阵方式输出图的数据\n");
	printf("3.Prim求最小生成树\n");
	printf("4.Kruskal算法求最小生成树\n");
	printf("0.退出\n");
	printf("输入你的选择："); 
}

void run(){
	int ch;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:MatoEdge();output();break;
			case 2:
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++)
						if(G[i][j]!=0x3f3f3f3f)printf("%3d ",G[i][j]);
						else printf("  * ");
					puts("");
				}
				break;
			case 3:
				prime();break;
			case 4:
				kruskal();break;
		}
	}while(ch);
}

int main(){
	printf("输入点数，边数："); 
	cin>>n>>m;
	printf("输入起点，终点，长度\n");
	memset(G,0x3f,sizeof(G));
	for(int i=1;i<=n;i++) G[i][i]=0;
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		Edge[i].x=x,Edge[i].y=y,Edge[i].z=z;
		G[x][y]=z,G[y][x]=z;
	}
	run();return 0;
}
//测试数据 
/*
13 25
1 2 17
1 5 32
2 3 24
2 4 22
2 7 36
5 6 12
2 12 98
3 9 78
3 7 28
4 7 19
6 7 35
6 8 54
6 12 68
7 9 46
7 8 22
8 9 23
8 10 31
8 11 24
8 12 42
9 13 54
9 10 21
10 13 14
11 13 42
11 12 12
12 13 55 
*/

13. 简单个人电话号码查询系统（二叉排序树）

问题描述
人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。
基本要求

  1. 在外存上，用文件保存电话号码信息；

  2. 在内存中，设计数据结构存储电话号码信息；

  3. 提供查询功能：根据姓名实现快速查询；

  4. 提供其他维护功能：例如插入、删除、修改等；

  5. 按电话号码进行排序。

设计思想
由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：

const int max=10;
    struct TeleNumber
    {
       string name;   //姓名
       string phoneNumber;    //固定电话号码
       string mobileNumber;   //移动电话号码
       string email;   //电子邮箱
    } Tele[max];

为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉排序树是否平衡，如何使之达到平衡。

#include<bits/stdc++.h>

using namespace std;

const int N=10000;

#define lc a[p].l
#define rc a[p].r

struct BST{
	int l,r;
	int dat;
	string name;
	string phone; 
}a[N];

int tot,root,n;

int New(string val,string na){
	a[++tot].phone=val;
	a[tot].name=na;
	a[tot].dat=rand();//随机数据为了使二叉树尽量平衡 
	return tot;
}
//初始化 
void build(){
	New(" "," ");New("99999999999"," ");
	root=1,a[1].r=2;
}

//查找 
int Get(int p,string val){
	if(p==0) return 0;//检索失败 
	if(val==a[p].phone) return p;//检索成功 
	return val<a[p].phone?Get(lc,val):Get(rc,val);
}

//左旋 
void zig(int &p){
	int q=a[p].l;
	a[p].l=a[q].r;a[q].r=p;
	p=q;
}
//右旋 
void zag(int &p){
	int q=a[p].r;
	a[p].r=a[q].l,a[q].l=p;
	p=q;
}
//插入 
void Insert(int & p,string val,string na){
	if(p==0) { p=New(val,na);return;}
	if(val==a[p].phone) return;
	if(val<a[p].phone){
		Insert(lc,val,na);
		if(a[p].dat<a[lc].dat) zig(p);
	}
	else{
		Insert(rc,val,na);
		if(a[p].dat<a[rc].dat) zag(p);
	}
}
//删除 
void Remove(int &p,string val){
	if(p==0) return;
	if(val==a[p].phone){
		if(lc||rc){
			if(rc==0||a[lc].dat>a[rc].dat) zig(p),Remove(rc,val);
			else zag(p),Remove(lc,val);
		}
		else p=0;
		return;
	}
	val<a[p].phone?Remove(lc,val):Remove(rc,val);
}

//暴力查找名字 
int GetByName(string na){
	for(int i=1;i<=tot;i++){
		if(na==a[i].name) {
			return i;
		}
	}
	return 0;
}

void menu(){
	printf("1.插入电话信息与姓名\n");
	printf("2.根据姓名查询\n");
	printf("3.删除电话信息\n");
	printf("4.修改电话信息\n"); 
	printf("5.打印所有信息(按照电话排序)\n");
	printf("0.退出\n"); 
	printf("输入选择："); 
}

void output(int p){
	cout<<"姓名： "<<a[p].name<<"  联系电话： "<<a[p].phone<<endl; 
}
//先序遍历 
void display(int p){
	if(lc) display(lc);
	output(p); 
	if(rc) display(rc);
}

#undef lc
#undef rc 

void run(){
	int ch;
	do{
		string na,phone,newphone;
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入姓名 电话：");
				cin>>na>>phone; 
				Insert(root,phone,na);
				break;
			case 2:
				printf("输入要查询姓名：");
				cin>>na;
				int x;
				if((x=GetByName(na))==0) {
					printf("不存在！\n"); 
				}
				else{
					output(x);
				}
				break;
			case 3:
				printf("输入删除的电话：");
				cin>>phone;
				Remove(root,phone);	
				break;
			case 4:
				printf("输入你要修改的手机号:");
				cin>>phone;
				printf("输入你要新的手机号:");
				cin>>newphone;
				if(Get(root,phone)==0){
					printf("不存在！\n"); 
				}
				else{
					Insert(root,newphone,a[Get(root,phone)].name);
					Remove(root,phone); 
				}
				break;
			case 5:display(root);
				break;
		}
	}while(ch);
}


int main(){
	run();
	return 0;
}

14. 图书管理系统

问题描述：
设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编号、单价、作者、存在状态、借书人姓名、性别、学号等。
基本要求：
基本功能：

  1. 新进图书基本信息的输入。
  2. 图书基本信息的查询。
  3. 对撤消图书信息的删除。
  4. 为借书人办理注册。
  5. 办理借书手续（非注册会员不能借书）。
  6. 办理还书手续。
  7. 统计图书库存、已借出图书数量。
  8. 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
#include<bits/stdc++.h>
using namespace std;

const int N=1000;
int tot=0;//馆藏 
int lencnt=0;//借出书 
//图书信息 
struct Book{
	string bookname;
	string bookid;
	int price;
	bool exist;
	string autor;
	string broswer;
	string sex;
	string stuid;
};

struct Person{
	string name;
	string sex;
	string stuid;
};
map<string,Person> persondat;//个人数据库 
map<string,Book> bookdat;//图书数据库 

//该书是否在馆 
bool isbook(string bookid){
	return bookdat.find(bookid)==bookdat.end()?0:1;
}

//撤销书籍 
void del(string bookid){
	if(!isbook(bookid)){
		printf("图书馆没有此书!\n");
		return; 
	}
	auto p=bookdat.find(bookid);
	bookdat.erase(p);
	tot--; 
}
//添加书籍 
void add(string bookname,string bookid,int price,string autor){
	bookdat.insert({bookid,{bookname,bookid,price,1,autor,"","",""}});
	tot++;
}
//还书 
void reback(string bookid){
	if(!isbook(bookid)){
		printf("图书馆没有此书!\n");
		return; 
	}
	bookdat[bookid].exist=true;
	lencnt--;
}
//借书 
void lentbook(string bookid){
	if(!isbook(bookid)){
		printf("图书馆没有此书!\n");
		return; 
	}
	if(bookdat[bookid].exist){
			bookdat[bookid].exist=false;
			lencnt++;
	}
	else{
		printf("该书已经被人借出！\n");
	}
}
//注册 
void Register(string name,string id,string sex){
	persondat.insert({id,{name,sex,id}});
}
//用户是否存在 
bool is_exist(string stuid){
	return persondat.find(stuid)==persondat.end()?0:1;
}
//输出图书信息 
void output(string p){
	cout<<"书名:"<<bookdat[p].bookname<<" 编号:"<<bookdat[p].bookid<<" 作者："<<bookdat[p].autor<<" 价格:"<<bookdat[p].price;
	printf(" 在馆状态：%s\n",bookdat[p].exist==1?"在":"不在"); 
}


void menu(){
	printf("1.新进图书\n");
	printf("2.图书基本信息的查询\n");
	printf("3.撤销图书信息\n");
	printf("4.为借书人办理注册\n");
	printf("5.办理借书手续\n");
	printf("6.办理还书手续\n");
	printf("7.统计图书库存、已借出图书数量。\n"); 
	printf("0.退出\n");
	printf("输入你的选择："); 
}

void run(){
	int ch;
	string bookname,bookid,autor;
	string name,sex,stuid; 
	int price;
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入书名,编号，价格，作者：");
				cin>>bookname>>bookid>>price>>autor;
				add(bookname,bookid,price,autor);
				break;
			case 2:
				printf("输入要查询的书的编号：");
				cin>>bookid; 
				if(!isbook(bookid)){
					printf("图书馆没有此书!");
				}
				else{
					output(bookid);
				}
				break;
			case 3:
				printf("输入要撤销的书的编号：");
				cin>>bookid;
				del(bookid);
				break; 
			case 4:
				printf("输入注册人的姓名，性别，学号\n");
				cin>>name>>sex>>stuid;
				Register(name,stuid,sex);
				break;
			case 5:
				printf("输入你的学号:");
				cin>>stuid;
				if(is_exist(stuid)){
					cout<<" 你好，"<<persondat[stuid].name;
					printf("%s",persondat[stuid].sex=="男"?"男士":persondat[stuid].sex=="女"?"女士":"同学");
					printf("输入要查询的书的编号：");
					cin>>bookid; 
					lentbook(bookid);
				}
				else{
					printf("不存在该会员，请办理会员！\n");
				}
				break;
			case 6:
				printf("输入你的学号:");
				cin>>stuid;
				if(is_exist(stuid)){
					cout<<" 你好，"<<persondat[stuid].name;
					printf("%s",persondat[stuid].sex=="男"?"男士":persondat[stuid].sex=="女"?"女士":"同学"); 
					printf("输入要还的书的编号：");
					cin>>bookid; 
					reback(bookid);
				}
				else{
					printf("不存在该会员，请办理会员！\n");
				}
				break;
			case 7: 
				printf("图书库存:%d  已借出图书数量:%d\n",tot,lencnt); 
			
		}
	}while(ch);
}

int main(){
	run();
	return 0;
}

15. 简单商品销售管理系统

简单商品销售管理系统： 设计一个系统，对某个商店的商品销售进行管理.
需求描述：

  1. 商品包含编号、名称、库存量、单价等属性，通过系统可以添加新商品信息；
  2. 通过系统可以对商品基本信息进行查询；（通过各种方式查询：编号，名称等等查询商品的所有信息）
  3. 通过系统可以对某个商品信息进行修改和删除；
  4. 用户会员管理；(会员包括编号、姓名、电话、地址等属性，包括会员的增加，删除，信息修改等功能)
  5. 会员购买商品；
  6. 销售记录管理，记录销售信息，能够根据会员或者商品查询销售记录；
  7. 各种数据的永久性保存。
  8. 各种数据的永久性保存。
#include<bits/stdc++.h>

using namespace std;
//商品信息 
struct Product{
	string id;
	string name;
	int num;
	int price;
};
//会员信息 
struct Person{
	string pid;
	string name;
	string phone;
	string addres;
	int tot; 
}; 

map<string,Product>Pro;
map<string,Person>Per;
map<string,string> A;//商品到标号 
map<string,string>B;//人名到编号 
map<string,vector<string>> repro;//从会员记录买单 
map<string,vector<string>> reper;//从商品记录买单 

void add(string id,string na,int num,int pr){
	Pro.insert({id,{id,na,num,pr}});
	A.insert({na,id});
}
//商品是否存在 
bool isproduct(string id){
	return Pro.find(id)==Pro.end()?0:1;
}
//会员是否存在 
bool isperson(string pid){
	return Per.find(pid)==Per.end()?0:1;
}
//删除商品 
void delproduct(string id){
	if(isproduct(id)){
		Pro.erase(Pro.find(id));
	}
	else{
		printf("该商品不存在！\n");
	}
}
//显示商品 
void output(string id){
	cout<<"商品名称:"<<Pro[id].name<<"  商品编号："<<Pro[id].id<< " 商品库存："<<Pro[id].num<<" 商品价格："<<Pro[id].price<<endl; 
}
//新增会员 
void addperson(string na,string pid,string ph,string addres){
	Per.insert({pid,{pid,na,ph,addres}}); 
}
//删除会员 
void delperson(string pid){
	if(isperson(pid)){
		Per.erase(Per.find(pid));
	}
	else{
		printf("该会员不存在！\n");
	}
}
//购买商品 
void BuyPro(string id,string pid){
	if(isproduct(id)){
		if(Pro[id].num){
			Pro[id].num--;
		repro[id].push_back(Per[pid].name);//商品记录 
		reper[pid].push_back(Pro[id].name);//会员记录 
		}
		else{
			printf("购买失败,该商品不没库存了！\n");
		}
	}
	else{
		printf("该商品不存在！\n");
	}
} 
//显示会员名称 
void display(string id){
	cout<<" 会员名字:"<<Per[id].name<<" 会员编号："<<Per[id].pid<<" 会员地址："<<Per[id].addres<<" 会员手机："<<Per[id].phone<<endl; 
}
//修改商品信息 
void changpro(string id){
	if(isproduct(id)){
		output(id); 
		string na;
		int price,cnt;
		printf("输入要修改后的名称，库存，单价:"); 
		cin>>na>>cnt>>price;
		A.erase(A.find(Pro[id].name));
		Pro[id].name=na;Pro[id].price=price;Pro[id].num=cnt;
		A.insert({na,id});
	}
	else{
		printf("该商品不存在！\n");
		string na,ph,addres; 
		printf("输入要修改后的会员名称，手机号，地址:"); 
		cin>>na>>ph>>addres;
		Per[id].name=na;Per[id].phone=ph;Per[id].addres=addres;
	}
}
//修改会员信息 
void changper(string id){
	if(isperson(id)){
		display(id);
	}
	else{
		printf("该用户不存在！\n");
	}
}
//显示会员购买了啥 
void DisplayByPer(string id){
	if(isperson(id)){
		for(int i=0;i<reper[id].size();i++)
			cout<<"购买了"<<reper[id][i]<<endl; 
	}
	else{
		printf("该会员不存在！\n");
	}
}
//显示哪个会员购买了该商品 
void DisplayByPro(string id){
	if(isproduct(id)){
		for(int i=0;i<repro[id].size();i++)
			cout<<repro[id][i]<<"买单了。。。"<<endl; 
	}
	else{
		printf("该商品不存在！\n");
	}
}


void menu(){
	printf("1.新商品信息\n");
	printf("2.根据商品编号查询\n");
	printf("3。根据商品名称查询\n"); 
	printf("4.删除商品信息\n");
	printf("5.修改商品信息\n");
	printf("6.注册会员\n"); 
	printf("7.删除会员\n");
	printf("8.修改会员信息\n");
	printf("9.购买商品\n");
	printf("10.更具会员查看销售记录\n");
	printf("11.商品查询销售记录\n"); 
	printf("输入你的选择："); 
}

void run(){
	int ch;
	string id,pid,name,ph,addres;
	int num,price; 
	do{
		menu();
		cin>>ch;
		switch(ch){
			case 1:
				printf("输入新增的产品的名字，编号，数量，单价:");
				cin>>name>>id>>num>>price;
				add(id,name,num,price); 
				break;
			case 2:
				printf("输入商品编号：");
				cin>>id;
				if(isproduct(id)){
					output(id);
				}
				else{
					printf("该商品不存在！\n");
				}
				break;
			case 3:
				printf("输入商品名称：");
				cin>>name;
				if(A.find(name)==A.end()){
					printf("该商品不存在！\n"); 
				} 
				else{
					output(A[name]);
				}
				break;
			case 4:
				printf("输入你要删除的商品编号："); 
				cin>>id;
				delproduct(id); 
				break;
			case 5:
				printf("输入你修改的商品编号："); 
				cin>>id;
				changpro(id);
				break;
			case 6:
				printf("输入注册的名字，编号，电话，地址:");
				cin>>name>>id>>ph>>addres; 
				addperson(name,id,ph,addres);
				break;
			case 7:
				printf("输入你要删除的会员编号："); 
				cin>>id;
				delperson(id); 
				break;
			case 8:
				printf("输入你修改的会员编号："); 
				cin>>id;
				changper(id);
				break;
			case 9:
				printf("输入你的会员编号：");
				cin>>pid;
				if(isperson(pid)){
					printf("输入要购买的商品编号：");
					cin>>id;
					BuyPro(id,pid); 
				}
				else{
					printf("该用户不存在！"); 
				}
				break;
			case 10: 
				printf("输入会员编号：");
				cin>>pid;
				 DisplayByPer(pid);
				break; 
			case 11:
				printf("输入商品编号：");
				cin>>id;
				DisplayByPro(id);
				break; 
		} 
	}while(ch);
}


int main(){
	run(); 
	return 0;
}

写在最后：

最后还是希望这篇文章能够帮助到大家吧！欢迎提问！

这篇关于《算法与数据结构实践专题》的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航