数据结构课程设计报告(仓库管理系统、通讯录管理系统、猴子选大王、.docx

数据结构课程设计报告
目录
第一章 设计目的 3
第二章 设计任务及要求 3
一、 基本要求 3
二、 内容 3
第三章 题目分析与解答 4
一、 仓库管理系统 4
1. 题目要求 4
2. 应用程序功能 4
3. 输入数据类型、格式和内容限制 6
4. 主要模块的算法描述 6
5. 源程序代码 7
二、 通讯录管理系统 13
1. 题目要求 13
2. 应用程序功能 13
3. 输入数据类型、格式和内容限制 15
4. 主要算法模块描述 16
5. 源程序代码 16
三、 猴子选大王 22
1. 题目要求： 22
2. 应用程序功能 22
3. 输入数据类型、格式和内容限制 23
4. 主要算法模块描述 23
5. 源程序代码 23
四、 二叉树运算2 26
1. 题目要求 26
2. 应用程序功能 26
3. 输入数据类型、格式和内容限制 26
4. 主要算法模块描述 26
5. 源程序代码 28

第一章 设计目的
一、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。
二、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。
三、培养学生初步的软件设计及软件测试的能力。
第二章 设计任务及要求
一、 基本要求
学生必须仔细阅读《数据结构》课程设计指导书，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。
学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。
课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。
根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。
每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准。
二、 内容
本次课程设计完成如下模块：仓库管理系统、通讯录管理系统、猴子选大王及二叉树运算2。

第三章 题目分析与解答
一、 仓库管理系统
1. 题目要求
设计一个仓库管理系统，可以按照顺序和货物名称查询仓库的存储情也可以增加或删除货物。
struct node
{
char NO; //商品编号
char name[max]; //商品名称
char count; //商品数量
};
2. 应用程序功能
开始运行时界面如下：

仓库管理链表建立界面如下：

仓库管理链表插入界面如下：

仓库管理链表查询界面如下：

按商品编号查询界面如下：

按商品名称查询界面如下：

仓库管理链表删除界面如下：

仓库管理链表输出界面如下：

3. 输入数据类型、格式和内容限制
输入数据类型为字符型，但在输入过程中不可出现空格，如在输入商品名称时不可出现空格。
4. 主要模块的算法描述
流程图：

5. 源程序代码
#include<stdio.h>
#include"iostream"
int flag1=0;
#include "string.h"
#include "stdlib.h"
#include "windows.h"
using namespace std;
typedef struct { //仓库管理结点类型
char NO[10]; //商品编号
char name[30]; //商品名称
char count[5]; //商品数量
} DataType;
typedef struct node { //结点类型定义
DataType data; //结点数据域
struct node *next; //结点指针域
} ListNode;
typedef ListNode *LinkList;
LinkList head;
ListNode *p;

LinkList CreateList(void);
void InsertNode(LinkList head,ListNode *p);
ListNode *ListFind(LinkList head);
void DelNode(LinkList head);
void PrintList(LinkList head);

/*******尾插法建立带头结点的仓库管理链表算法*******/
LinkList CreateList(void)
{
LinkList head=(ListNode *)malloc(sizeof(ListNode)); //申请头结点
ListNode *p,*rear;
char flag='y'; //int flag=0; //结束标志置0
rear=head; //尾指针初始指向头结点
while (flag=='y')
{
p=(ListNode *)malloc(sizeof(ListNode)); //申新结点
printf(" 商品编号(10) 商品名称(30) 商品数量(5) \n");
printf("-----------------------------------------------\n");
printf("\n添加商品编号:\n");
cin>>p->data.NO;
printf("\n添加商品名称:\n");
cin>>p->data.name;
printf("\n添加商品数量:\n");
cin>>p->data.count;
rear->next=p; //新结点连接到尾结点之后
rear=p; //尾指针指向新结点
printf("继续添加记录?(y/n):");
cin>>flag;
}
rear->next=NULL; //终端结点指针置空
return head; //返回链表头指针
}

/*********在仓库管理链表head中插入结点************/
void InsertNode(LinkList head,ListNode *p)
{
ListNode *p1,*p2;
p1=head;
p2=p1->next;
while(p2!=NULL && strcmp(p2->data.NO,p->data.NO)<0)
{
p1=p2; //p1指向刚访问过的结点
p2=p2->next; //p2指向表的下一个结点
}
p1->next=p; //插入p所指向的结点
p->next=p2; //连接表中剩余的结点
}

/**********有序仓库管理链表的查找 ****************/
ListNode *ListFind(LinkList head)
{
ListNode *p;
char num[10];
char name[9];
char pp;
printf("==================\n");
printf(" a. 按商品编号查询 \n");
printf(" b. 按商品名称查询 \n");
printf("==================\n");
printf(" 请 选 择： ");
p=head->next;
cin>>pp;
getchar();
if (pp=='a'||pp=='A')
{
printf("请输入要查找的商品编号：");
cin>>num;
while (p&&strcmp(p->data.NO,num)<0) p=p->next;
if ((p==NULL)||strcmp(p->data.NO,num)>0) p=NULL; //没有查到要查找的通讯信息
}
else
if (pp=='b'||pp=='B')
{
printf(" 请输入要查找的商品名称：");
cin>>name;
while(p&&strcmp(p->data.name,name)!=0) p=p->next;
}
return p;
}

/********仓库管理链表上的结点删除*****************/
void DelNode(LinkList head)
{
char jx;
ListNode *p,*q;
p=ListFind(head); //调用查找函数
if (p==NULL)
{
printf("没有查到要删除的商品信息!\n");
return;
}
if(p!=NULL) printf("真的要删除该商品吗？（y/n）:");
cin>>jx;
if (jx=='y'||jx=='Y')
{
q=head;
while ((q!=NULL)&&(q->next!=p)) q=q->next;
q->next=p->next; //删除结点
free(p); //释放被删结点空间
printf("删除成功！\n");
}
}

/********仓库管理链表的输出函数 **********/
void PrintList(LinkList head)
{
ListNode *p;
p=head->next;
printf(" 商品编号 商品名称 商品数量 \n");
printf("--------------------------------------------------------------------------------\n");
while (p!=NULL)
{
printf("%15s%20s%23s\n",p->data.NO,p->data.name,p->data.count);
printf("---------------------------------------------------------------------------------\n");
p=p->next; //后移一个结点
}
}

void main()
{
int choice,j=1;
char Choice;
while(j)
{
printf("\n\n\n\n\n");
printf("\t\t\t\t仓库管理系统\n");
printf("\n\t\t\t******************************");
printf("\n\t\t\t* 1--- 仓库管理链表建立 *");
printf("\n\t\t\t* 2--- 仓库管理链表插入 *");
printf("\n\t\t\t* 3--- 仓库管理链表查询 *");
printf("\n\t\t\t* 4--- 仓库管理链表删除 *");
printf("\n\t\t\t* 5--- 仓库管理链表输出 *");
printf("\n\t\t\t* 0--- 退出仓库管理系统 *");
printf("\n\t\t\t******************************");
printf("\n\t\t\t请选择菜单号(0--5):");
cin>>choice;
getchar();
switch(choice)
{
case 1:
{
printf("**********************************\n");
printf("* 仓库管理链表建立 *\n");
printf("**********************************\n");
head=CreateList( );
flag1=1;
system("cls");
break;
}
case 2:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
printf("**********************************\n");
printf("* 仓库管理链表插入 *\n");
printf("**********************************\n");
printf("商品编号(10) 商品名称(30) 商品数量\n");
printf("************************************* \n");
p=(ListNode *)malloc(sizeof(ListNode)); //申请新结点
printf("\n添加商品编号:\n");
cin>>p->data.NO;
printf("\n添加商品名称:\n");
cin>>p->data.name;
printf("\n添加商品数量:\n");
cin>>p->data.count;
InsertNode(head,p);
system("cls");
break;
}
case 3:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
else
{
printf("***********************************\n");
printf("* 仓库管理链表查询 *\n");
printf("***********************************\n");
p=ListFind(head);
if (p!=NULL)
{
printf("商品编号 商品名称 商品数量 \n");
printf("--------------------------------------------------\n");
printf("%s,%s,%s\n",p->data.NO,p->data.name,p->data.count);
printf("---------------------------------------------------\n");
}
else printf("没有查到要查询的商品信息！\n");
}
break;
}
case 4:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
else
{
printf("***********************************\n");
printf("* 仓库管理链表删除 *\n");
printf("***********************************\n");
DelNode(head); //删除结点
}
break;
}
case 5:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
else
{
printf("************************************\n");
printf("* 仓库管理链表输出 *\n");
printf("************************************\n");
PrintList(head);
}
break;
}
case 0:j=0;system("cls");break;
default:printf("\t\t\n 输入有错，请重新输入!\n");Sleep(1500);system("cls");break;
}
}
}
二、 通讯录管理系统
1. 题目要求
通讯录一般包括通讯者的编号、姓名、性别、电话及地址等信息，设计一个通讯录要求实现通讯者的插入、查询、删除、更新、排序操作。
struct node
{
char num[5]; //编号
char name[8]; //姓名
char sex; //性别
char tel[8]; //电话
char address[100]; //地址
};
2. 应用程序功能
开始运行时界面如下：

通讯录链表建立界面如下：

通讯录链表插入界面如下：

通讯录链表查询界面如下：

按编号查询界面如下：

按姓名查询编号如下:

通讯录链表删除界面如下：

通讯录链表输出界面如下：

3. 输入数据类型、格式和内容限制
输入数据类型为字符型，但在输入过程中不可包含空格，如输入地址过程中不可出现空格！
4. 主要算法模块描述
流程图：
5. 源程序代码
#include<stdio.h>
#include "iostream"
int flag1=0;
#include "string.h"
#include "stdlib.h"
#include "windows.h"
using namespace std;
typedef struct { //通讯录结点类型
char num[5]; //编号
char name[9]; //姓名
char sex[3]; //性别
char phone[13]; //电话
char addr[31]; //地址
} DataType;
typedef struct node { //结点类型定义
DataType data; //结点数据域
struct node *next; //结点指针域
} ListNode;
typedef ListNode *LinkList;
LinkList head;
ListNode *p;

LinkList CreateList(void);
void InsertNode(LinkList head,ListNode *p);
ListNode *ListFind(LinkList head);
void DelNode(LinkList head);
void PrintList(LinkList head);

/*******尾插法建立带头结点的通讯录链表算法*******/
LinkList CreateList(void)
{
LinkList head=(ListNode *)malloc(sizeof(ListNode)); //申请头结点
ListNode *p,*rear;
char flag='y'; //int flag=0; //结束标志置0
rear=head; //尾指针初始指向头结点
while (flag=='y')
{
p=(ListNode *)malloc(sizeof(ListNode)); //申新结点
printf("编号(4) 姓名(8) 性别 电话(11) 地址(31)\n");
printf("-----------------------------------------------\n");
printf("\n添加的编号:\n");
cin>>p->data.num;
printf("\n添加的姓名:\n");
cin>>p->data.name;
printf("\n性别:\n");
cin>>p->data.sex;
printf("\n电话:\n");
cin>>p->data.phone;
printf("\n地址:\n");
cin>>p->data.addr;
rear->next=p; //新结点连接到尾结点之后
rear=p; //尾指针指向新结点
printf("继续建表?(y/n):");
cin>>flag;
}
rear->next=NULL; //终端结点指针置空
return head; //返回链表头指针
}

/*********在通讯录链表head中插入结点************/
void InsertNode(LinkList head,ListNode *p)
{
ListNode *p1,*p2;
p1=head;
p2=p1->next;
while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0)
{
p1=p2; //p1指向刚访问过的结点
p2=p2->next; //p2指向表的下一个结点
}
p1->next=p; //插入p所指向的结点
p->next=p2; //连接表中剩余的结点
}

/**********有序通讯录链表的查找 ****************/
ListNode *ListFind(LinkList head)
{
ListNode *p;
char num[5];
char name[9];
char pp;
printf("==================\n");
printf(" a. 按编号查询 \n");
printf(" b. 按姓名查询 \n");
printf("==================\n");
printf(" 请 选 择： ");
p=head->next;
cin>>pp;
if (pp=='a'||pp=='A')
{
printf("请输入要查找者的编号：");
cin>>num;
while (p&&strcmp(p->data.num,num)<0) p=p->next;
if ((p==NULL)||strcmp(p->data.num,num)>0) p=NULL; //没有查到要查找的通讯信息
}
else
if (pp=='b'||pp=='B')
{
printf(" 请输入要查找者的姓名：");
cin>>name;
while(p&&strcmp(p->data.name,name)!=0) p=p->next;
}
return p;
}

/********通讯录链表上的结点删除*****************/
void DelNode(LinkList head)
{
char cho;
ListNode *p,*q;
p=ListFind(head); //调用查找函数
if (p==NULL)
{
printf("没有查到要删除的通讯者!\n");
return;
}
else if(p!=NULL)
{
printf("真的要删除该结点吗？（y/n）");
cin>>cho;
if (cho=='y'||cho=='Y')
{
q=head;
while ((q!=NULL)&&(q->next!=p)) q=q->next;
q->next=p->next; //删除结点
free(p); //释放被删结点空间
printf("删除成功！\n");
}
}
}

/********通讯录链表的输出函数 **********/
void PrintList(LinkList head)
{
ListNode *p;
p=head->next;
printf("编号 姓 名 性别 联系电话 地址 \n");
printf("--------------------------------------------------------------------------------\n");
while (p!=NULL)
{
printf("%s,%s,%s,%s,%s\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
printf("---------------------------------------------------------------------------------\n");
p=p->next; //后移一个结点
}
}

void main()
{
int choice,j=1;
while(j)
{
printf("\n\n\n\n\n");
printf("\t\t\t\t通 信 录 链 表 \n");
printf("\n\t\t\t******************************");
printf("\n\t\t\t* 1--- 通信录链表建立 *");
printf("\n\t\t\t* 2--- 通信录链表插入 *");
printf("\n\t\t\t* 3--- 通信录链表查询 *");
printf("\n\t\t\t* 4--- 通信录链表删除 *");
printf("\n\t\t\t* 5--- 通信录链表输出 *");
printf("\n\t\t\t* 0--- 退出管理系统 *");
printf("\n\t\t\t******************************");
printf("\n\t\t\t请选择菜单号(0--5):");
cin>>choice;
getchar();
switch(choice)
{
case 1:
{
printf("**********************************\n");
printf("* 通 讯 录 链 表 的 建 立 *\n");
printf("**********************************\n");
head=CreateList( );
flag1=1;
system("cls");
break;
}
case 2:
{
if(flag1!=1) {printf("请先建立表!");Sleep(1500); system("cls");}
printf("**********************************\n");
printf("* 通 讯 者 信 息 的 添 加 *\n");
printf("**********************************\n");
printf("编号(4) 姓名(8) 性别(3) 电话(11) 地址(31)\n");
printf("************************************* \n");
p=(ListNode *)malloc(sizeof(ListNode)); //申请新结点
printf("\n添加的编号:\n");
cin>>p->data.num;
printf("\n添加的姓名:\n");
cin>>p->data.name;
printf("\n性别:\n");
cin>>p->data.sex;
printf("\n电话:\n");
cin>>p->data.phone;
printf("\n地址:\n");
cin>>p->data.addr;
InsertNode(head,p);
system("cls");
break;
}
case 3:
{
if(flag1!=1) {printf("请先建立表!");Sleep(1500);system("cls");}
else
{
printf("***********************************\n");
printf("* 通 讯 录 信 息 的 查 询 *\n");
printf("***********************************\n");
p=ListFind(head);
if (p!=NULL)
{
printf("编号 姓 名 性别 联系电话 地址 \n");
printf("--------------------------------------------------\n");
printf("%s,%s,%s,%s,%s\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
printf("---------------------------------------------------\n");
}
else printf("没有查到要查询的通讯者！\n");
}
break;
}
case 4:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
else
{
printf("***********************************\n");
printf("* 通 讯 录 信 息 的 删 除 *\n");
printf("***********************************\n");
DelNode(head); //删除结点
}
break;
}
case 5:
{
if(flag1!=1) {printf("请先建立表!"); Sleep(1500);}
else
{
printf("************************************\n");
printf("* 通 讯 录 链 表 的 输 出 *\n");
printf("************************************\n");
PrintList(head);
}
break;
}
case 0:j=0;system("cls");break;
default:printf("\t\t\n 输入有错，请重新输入!\n");Sleep(1500);system("cls");break;
}
}
}
三、 猴子选大王
1. 题目要求：
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。
2. 应用程序功能
程序运行结果如下：

3. 输入数据类型、格式和内容限制
输入数据为整型，切勿输入整形以外数据类型，否则程序将报错。
4. 主要算法模块描述
流程图：

5. 源程序代码
#include "iostream"
#include "stdlib.h"
using namespace std;
typedef struct node{