题目一：用线性表实现文具店的货品管理问题
问题描述：在文具店的日常经营过程中，存在对各种文具的管理问题。当库存文具不足或缺货时，需要进货。日常销售时需要出库。当盘点货物时，需要查询货物信息。请根据这些要求编写软件完成库存文具的管理功能。
问题分析：通过对问题的抽象，文具信息和文具分类信息可以用表1和表2来表示。可见文具信息和文具分类信息在逻辑上具有线性的关系，因此可以使用线性表来解决这个问题。由于文具信息变动较大，应该使用链式存储结构来进行表示和实现。而文具分类信息变动不大，可以使用顺序存储结构进行表示和实现。
表1 文具信息
| 文具名称 |
文具类别 |
文具数量 |
| 钢笔 |
1 |
400 |
| 日记本 |
2 |
2000 |
| 计算器 |
3 |
50 |
表2 文具分类信息
| 文具类别号 |
文具类别名 |
| 1 |
文具 |
| 2 |
纸张 |
| 3 |
工具 |
程序简介：
本程序包含两个模块
1.数据结构的设计
typedef struct //定义文具分类信息结构，代表一个结点
{
int TypeNumber; //文件类别号
char TypeName[10]; //文具类别名
}Type;
typedef struct //定义文具分类顺序表
{
Type *elem;
int length;
}sqList;
typedef struct //文具信息结构
{
int TypeNumber; //文件类别号
char StockName[10];//文具名称
int amount;//文具数量
}StockType;
typedef struct Lnode //文具信息链表数据类型
{
StockType data;
struct Lnode *next;
}Lnode,*Linklist;
主程序模块
int main( )
{
CreatTypeList(L); //创建文具分类顺序表
CreatList_R(h); //用尾插法建立文具信息链表；
while(1)
{
cout<<"文具店货品管理系统"<<endl;
cout<<"**********主菜单**********"<<endl;
cout<<" (1)文具入库"<<endl;
cout<<" (2)文具出库"<<endl;
cout<<" (3)查询文具信息"<<endl;
cout<<" (4)显示文具信息"<<endl;
cout<<" (5)添加新文具类别"<<endl;
cout<<" (0)退出系统"<<endl;
cout<<"请选择(1,2,3,4,5,0):";
cin>>choice;
if(choice<0||choice>5)
continue;
switch(choice)
{
case 1:
AddStock(h);
break;
case 2:
RemoveStock(h);
break;
case 3:
QueryStock(h);
break;
case 4:
DisplayStock(h);
break;
case 5:
AddType(L);
break;
case 0:
exit(0);
default:
break;
}
}
system("pause");
return 0;
}
2.各个函数功能
int CreatTypeList(sqList &L) //创建文具分类顺序表
void CreatList_R(Linklist &h) //尾插法建立文具链表
int AddStock(Linklist &h) //文具入库，如果该文具存在，则修改其数量，如果该文具不存在，则插入到文具链表中。
int RemoveStock(Linklist &h) //文具出库，如果出库数量大于库存数量，则从链表中删除该文具，否则只修改文具数量。
void QueryStock(Linklist h) //查询文具信息根据文具类别号输出
void DisplayStock(Linklist h) //显示文具信息
int AddType(sqList &L) //添加新文具类别
系统界面显示效果
实验要求：
- 完善给出的程序框架Test1.cpp，使之能够实现基本的功能。
- 添加文具类别显示查询出库入库添加排序的功能int SortStock(Linklist &h)，要求能够根据文具类别号对文具进行排序。
实验代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
using namespace std;
#define MAX_TYPE 100
typedef struct Type
{
int TypeNumber;
char TypeName[10];
} Type;
typedef struct
{
Type *elem;
int length;
int maxSize;
} sqList;
typedef struct StockType
{
int TypeNumber;
char StockName[10];
int amount;
}StockType;
typedef struct Lnode
{
StockType data;
struct Lnode *next;
} Lnode, *Linklist;
void CreatTypeList(sqList &L,int max)
{
L.length = max;
}
void CreatList_R(Linklist &h)
{
// 初始化链表头指针为空
h = NULL;
}
// 文具入库
int AddStock(Linklist &h, int typeNumber, const char *stockName, int amount)
{
Linklist p = h, q;
while (p != NULL)
{
if (p->data.TypeNumber == typeNumber && strcmp(p->data.StockName, stockName) == 0)
{
p->data.amount += amount;
return 1;
}
q = p;
p = p->next;
}
Linklist newNode = new Lnode;
newNode->data.TypeNumber = typeNumber;
strcpy(newNode->data.StockName, stockName);
newNode->data.amount = amount;
newNode->next = NULL;
if (h == NULL)
{
h = newNode;
}
else
{
q->next = newNode;
}
return 1;
}
// 文具出库
int RemoveStock(Linklist &h, int typeNumber, const char *stockName, int amount) {
Linklist p = h, q;
while (p != NULL)
{
if (p->data.TypeNumber == typeNumber && strcmp(p->data.StockName, stockName) == 0)
{
if (p->data.amount >= amount)
{
p->data.amount -= amount;
if (p->data.amount == 0)
{
if (p == h)
{
h = p->next;
}
else
{
q->next = p->next;
}
delete p;
}
return 1;
}
else
{
return 0;
}
}
q = p;
p = p->next;
}
return 0;
}
// 查询文具信息
void QueryStock(Linklist h, int typeNumber)
{
Linklist p = h;
while (p != NULL)
{
if (p->data.TypeNumber == typeNumber)
{
cout << "文具名称：" << p->data.StockName << "，数量：" << p->data.amount << endl;
}
p = p->next;
}
}
// 显示文具信息
void DisplayStock(Linklist h)
{
Linklist p = h;
while (p != NULL)
{
cout << "文具类别号：" << p->data.TypeNumber << "，文具名称：" << p->data.StockName << "，数量：" << p->data.amount << endl;
p = p->next;
}
}
// 添加新文具类别
int AddType(sqList &L, int typeNumber, const char *typeName)
{
if (L.length >= L.maxSize)
{
return 0;
}
for (int i = 0; i < L.length; i++)
{
if (L.elem[i].TypeNumber == typeNumber)
{
return 0;
}
}
L.elem[L.length].TypeNumber = typeNumber;
strcpy(L.elem[L.length].TypeName, typeName);
L.length++;
return 1;
}
// 根据文具类别号对文具进行排序
void SortStock(Linklist &h)
{
if (h == NULL || h->next == NULL)
return;
Linklist p, q;
for (p = h; p->next != NULL; p = p->next)
{
for (q = p->next; q != NULL; q = q->next)
{
if (p->data.TypeNumber > q->data.TypeNumber)
{
StockType temp = p->data;
p->data = q->data;
q->data = temp;
}
}
}
}
void DisplayTypeList(sqList &L)
{
for (int i = 0; i < L.length; i++)
{
cout << "文具类别号：" << L.elem[i].TypeNumber << "，文具类别名称：" << L.elem[i].TypeName << endl;
}
}
int main()
{
sqList L;
Linklist h;
CreatTypeList(L, MAX_TYPE); // 创建文具分类顺序表
CreatList_R(h); // 用尾插法建立文具信息链表；
int choice;
while (1)
{
cout << "文具店货品管理系统" << endl;
cout << "**********主菜单**********" << endl;
cout << " (1)文具入库" << endl;
cout << " (2)文具出库" << endl;
cout << " (3)查询文具信息" << endl;
cout << " (4)显示文具信息" << endl;
cout << " (5)添加新文具类别" << endl;
cout << " (6)排序" << endl;
cout << " (7)显示文具类别信息" << endl;
cout << " (0)退出系统" << endl;
cout << "请选择(1,2,3,4,5,6,7,0):";
cin >> choice;
if (choice < 0 || choice > 6)
continue;
switch (choice)
{
case 1:
{
int typeNumber, amount;
char stockName[10];
cout << "请输入文具类别号：";
cin >> typeNumber;
cout << "请输入文具名称：";
cin >> stockName;
cout << "请输入文具数量：";
cin >> amount;
if(AddStock(h, typeNumber, stockName, amount))
{
cout<<"文具入库成功"<<endl;
}
break;
}
case 2:
{
int typeNumber, amount;
char stockName[10];
cout << "请输入文具类别号：";
cin >> typeNumber;
cout << "请输入文具名称：";
cin >> stockName;
cout << "请输入文具数量：";
cin >> amount;
if(RemoveStock(h, typeNumber, stockName, amount))
{
cout<<"出库成功"<<endl;
}
else
{
cout<<"出库失败"<<endl;
}
break;
}
case 3:
{
int typeNumber;
cout << "请输入文具类别号：";
cin >> typeNumber;
QueryStock(h, typeNumber);
break;
}
case 4:
{
DisplayStock(h);
break;
}
case 5:
{
int typeNumber;
char typeName[10];
cout << "请输入文具类别号：";
cin >> typeNumber;
cout << "请输入文具类别名称：";
cin >> typeName;
AddType(L, typeNumber, typeName);
break;
}
case 6:
{
SortStock(h);
break;
}
case 7:
{
DisplayTypeList(L);
break;
}
case 0:
{
exit(0);
break;
}
default:
{
break;
}
}
}
system("pause");
return 0;
}
题目二：单循环链表Josephus问题
一、实验目的
- 学会选择合适的数据结构来解决实际问题
- 学会如何创建一个单循环链表
- 在单循环链表中如何进行查找
- 在单循环链表中如何进行删除
二 、实验内容
设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m个的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…… 如此反复直到所有的人全部出列为止。对于任意给定的n、s和m，求出按出列次序得到的n个人员的序列（要求用链表加以实现）。
三、实验步骤
- 创建由n个结点组成的不带头结点的Josephus循环单链表
- 找循环链表中的第s个结点
- 求第m个应出列的元素删除它
四、实验要求
- 绘制流程图描述算法。
- 使用“截图加文字方式”描述算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等。
五、实验代码
#include<iostream>
using namespace std;
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
void Josephus(int n,int s,int m)
{
Node *head = NULL;
head = (Node*)malloc(sizeof(Node));
if(head==NULL)
{
return;
}
Node *p=NULL,*a=NULL;
head->data=1;
head->next=NULL;
p=head;
for(int i=2;i<=n;i++)
{
a=(Node*)malloc(sizeof(Node));
a->data=i;
a->next=NULL;
p->next=a;
p=a;
}
p->next=head;
p=head;
for(int i=1;i<s;i++)
{
p=p->next;
}
while(p->next!= p)
{
for(int i=1;i<m;i++)
{
a=p;
p=p->next;
}
cout<<p->data<<" ";
a->next=p->next;
p=p->next;
}
cout<<p->data<<endl;
}
int main()
{
int n, s, m;
cout<<"输入总人数n、第s个人开始报数和报数间隔m：";
cin>>n>>s>>m;
cout<<"按出列次序得到的人员序列为：";
Josephus(n, s, m);
return 0;
}
六、思考题
如何用顺序表解决josephus问题？
代码如下：
#include<iostream>
using namespace std;
void Josephus(int n, int s, int m)
{
int *arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = i + 1;
}
int count = 0;
int index = s - 1;
while (count < n - 1)
{
index = (index + m - 1) % (n - count);
cout << arr[index] << " ";
for (int i = index; i < n - count - 1; i++)
{
arr[i] = arr[i + 1];
}
count++;
}
cout << arr[0] << endl;
delete[] arr;
}
int main()
{
int n, s, m;
cout << "输入总人数n、第s个人开始报数和报数间隔m：";
cin >> n >> s >> m;
cout << "按出列次序得到的人员序列为：";
Josephus(n, s, m);
return 0;
}