数据结构实验 1

题目一：用线性表实现文具店的货品管理问题

问题描述：在文具店的日常经营过程中，存在对各种文具的管理问题。当库存文具不足或缺货时，需要进货。日常销售时需要出库。当盘点货物时，需要查询货物信息。请根据这些要求编写软件完成库存文具的管理功能。

问题分析：通过对问题的抽象，文具信息和文具分类信息可以用表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 100typedef 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;
}