数据结构课与算法课程课程设计高校社团管理设计,二叉树的应用(附全代码).doc

目 录 引 言41 需求分析41.1任务与分析41.2测试数据52 概要设计52.1 ADT描述52.2程序模块结构62.3各功能模块73详细设计73.1结构体定义83.2 初始化83.3 插入操作83.4创建113.5查询123.6修改153.7统计173.8删除184 调试分析224.1问题分析和解决224.2算法的时间复杂度分析224.3经验和体会225用户使用说明236测试结果23结 论32致 谢33数据结构课与算法课程 设 计 任 务 书学院名称： 课程代码：_ _专 业： 年 级： 一、设计题目高校社团管理二、 主要内容在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：具体操作：1.画出社团结构的二叉树2给出数据结构 应考考虑树中结点如何表示社团和成员3实现下列操作（1）初始化存储社团和会员的二叉树;(2)建立以二叉链存储的社团； （3）查询：输入社团名称或社团中团员姓名，在二叉树中进行查找，若找到则显示相应信息；否则显示未找到信息； （4）修改：输入社团名称或社团中团员姓名，修改找到的社团或会员的相关信息； （5）插入：输入新的社团名称，在二叉树中增加一个社团；（6）会员插入：输入新的会员姓名，在指定的社哮中增加一个会员；（7）统计:统计每个社团中的成员数，并显示结果；（8）删除：输入会员，删除相关社团中指定的会员；(9)社团删除：输入社团名称，删除指定的社团。三、具体要求及应提交的材料用C/C+语言编程实现上述内容，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：1)课程设计说明书打印稿一份2)课程设计说明书电子稿一份；3)源程序电子文档一份。四、主要技术路线提示社团管理部门、社团和社团成员构成了完整的二叉树，二叉树选用二叉链表作为存储结构。五、进度安排按教学计划规定，数据结构与算法课程设计为2周，其进度及时间大致分配如下：序号设计内容天数1分析问题，给出数学模型，选择数据结构22设计算法，给出算法描述13给出源程序清单24编辑、编译、调试源程序25编写课程设计报告3总 计10六、推荐参考资料1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。 2 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。3唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年9月4 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月5胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日摘 要 随着计算机的普及，计算机的应用越来越广泛，多用于复杂事物的管理。该说明书主要是对高校社团管理系统进行描述，准确清楚的阐述了本系统的功能。本次课程设计实现了对社团和会员的录入、查询、修改、插入、统计、删除等功能，功能详细全面。关键词：社团；功能；管理； 引 言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。课程设计是实践性教学中的一个重要环节，它是以课程为基础可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。1 需求分析1.1任务与分析在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：具体操作：1.画出社团结构的二叉树2给出数据结构 应考考虑树中结点如何表示社团和成员3实现下列操作（1）初始化存储社团和会员的二叉树;(2)建立以二叉链存储的社团； （3）查询：输入社团名称或社团中团员姓名，在二叉树中进行查找，若找到则显示相应信息；否则显示未找到信息； （4）修改：输入社团名称或社团中团员姓名，修改找到的社团或会员的相关信息； （5）插入：输入新的社团名称，在二叉树中增加一个社团；（6）会员插入：输入新的会员姓名，在指定的社哮中增加一个会员；（7）统计:统计每个社团中的成员数，并显示结果；（8）删除：输入会员，删除相关社团中指定的会员；(9)社团删除：输入社团名称，删除指定的社团。ruanjian11.2测试数据 ayingyu10fedcb00000图1-1测试数据2 概要设计2.1 ADT描述 ADT LeagueManage数据对象：D具有相同特征的数据元素的有限集合;数据关系：RH; R如D为空，则R也为空，LeagueManage为空二叉树。 否则D不为空，则R=H，H详细描述如下：1. D中存在唯一的称之为跟root的节点，它在关系H下无前驱；2. 若D-root不为空，则D-root=D1,Dr，切D1,Dr互不相交；3. （D1，H1）和（Dr，Hr）都是二叉树，分别是跟root的左子树和右子树。基本操作： Face():选择用户要执行的操作；CreatBTree（）：创建社团，录入会员；Find():查找社团和会员；Alter():修改社团和会员；Insert():插入社团和会员；Statistic(Member *):统计社团中的成员数；DeleteNode():删除社团和会员2.2程序模块结构图1-2程序模块结构图2.2.1结构体定义 struct MemberElemType name;int tag;Member *lch;Member *rch;2.3各功能模块Face():选择用户要执行的操作；CreatBTree（）：创建社团，录入会员；Find():查找社团和会员；Alter():修改社团和会员；Insert():插入社团和会员；Statistic(Member *):统计社团中的成员数；DeleteNode():删除社团和会员3详细设计3.1结构体定义 struct MemberElemType name;int tag;Member *lch;Member *rch;3.2 初始化 LeagueManage()root=NULL;3.3 插入操作 插入社团：if(order=1)char x;cout<<"请输入新社团的名字："cin>>m->name;m->tag=1;m->lch=m->rch=NULL;while(p->lch!=NULL&&p->rch!=NULL)p=p->lch;if(p->lch=NULL)p->lch=m;elsep->rch=m;cout<<"插入社团成功！"<<endl;cout<<"是否为新的社团录入会员(y/n)："cin>>x;while(x!='y'&&x!='Y'&&x!='n'&&x!='N')cout<<"输入错误！请重输："cin>>x;if(x='y'|x='Y')Member *p,*s30;ElemType name;int tag;int i=2,j;s1=m;cout<<"请输入标识符、名字："cin>>tag>>name;while(pare("0")p=new Member;p->name=name;p->tag=tag;p->lch=p->rch=NULL;si=p;j=i/2;if(i%2)=0)sj->lch=p;elsesj->rch=p;i+;cout<<"标识符、名字："cin>>tag>>name;cout<<"录入成功！"<<endl;system("pause");system("cls"); 插入会员：else if(order=2)cout<<"请输入新会员的名字："cin>>m->name;m->tag=0;m->lch=m->rch=NULL;cout<<"请输入新会员所属社团的名字："cin>>name;FindLeague(root,name,isfind,p);if(isfind=false)cout<<"没有找到该社团！"elsewhile(p->lch!=NULL&&p->rch!=NULL)p=p->lch;if(p->lch=NULL)p->lch=m;elsep->rch=m;cout<<"插入会员成功！"<<endl;system("pause");system("cls");3.4创建void LeagueManage:CreatBTree() /创建Member *p,*s30;ElemType name;int tag=0;int i=1,j;cout<<"请按照二叉树的层序，自上而下自左至右顺序输入数据。"<<endl;cout<<"标识符 0：会员 1：社团,输入会员名为0时结束录入。"<<endl;cout<<"请输入标识符、名字："cin>>tag>>name;while(pare("0")if(i=1)while(tag=0)cout<<"输入错误，请先创建一个社团！请重新输如："cin>>tag>>name;p=new Member;p->name=name;p->tag=tag;p->lch=p->rch=NULL;si=p;if(i=1)root=p;elsej=i/2;if(i%2)=0)sj->lch=p;elsesj->rch=p;i+;cout<<"标识符、名字："cin>>tag>>name;3.5查询查询社团： if(order=1)cout<<"请输入社团名字："cin>>name;FindLeague(root,name,isfind,m);if(!isfind)cout<<"未找到该社团！"<<endl;elsecout<<"社团："<<m->name<<"，旗下会员有："Display(m->lch,i);Display(m->rch,i);cout<<endl;system("pause");system("cls");void LeagueManage:FindLeague(Member *p,string name,bool &isfind,Member *&m) /查找社团if(p!=NULL)if(p->tag=0)FindLeague(p->lch,name,isfind,m);FindLeague(p->rch,name,isfind,m);else if(pare(p->name)FindLeague(p->lch,name,isfind,m);FindLeague(p->rch,name,isfind,m);else if(!pare(p->name)isfind=true;m=p;查询会员：else if(order=2)cout<<"请输入会员名字："cin>>name;FindMember(root,name,isfind,e,m);if(!isfind)cout<<"未找到该会员！"<<endl;system("pause");system("cls");void LeagueManage:FindMember(Member *p,string name,bool & isfind, ElemType e,Member *&m) /查找会员if(p!=NULL)if(p->tag=1)e=p->name;FindMember(p->lch,name,isfind,e,m);FindMember(p->rch,name,isfind,e,m);else if(pare(p->name)FindMember(p->lch,name,isfind,e,m);FindMember(p->rch,name,isfind,e,m);else if(!pare(p->name)isfind=true;cout<<"会员姓名："<<p->name<<"，所属社团："<<e<<endl;m=p;void LeagueManage:Display(Member *p,int &i) /遍历输出if(p!=NULL&&p->tag=0)i+;cout<<p->name<<" "Display(p->lch,i);Display(p->rch,i);3.6修改修改社团：if(order=1)cout<<"请输入社团名字："cin>>name;FindLeague(root,name,isfind,m);if(!isfind)cout<<"未找到该社团！"<<endl;elsecout<<"社团："<<m->name<<"，旗下会员有："Display(m->lch,i);Display(m->rch,i);cout<<"n请输入要修改的社团名字："cin>>m->name;cout<<"修改成功！"<<endl;system("pause");system("cls");修改会员：else if(order=2)cout<<"请输入会员名字："cin>>name;FindMember(root,name,isfind,e,m);if(!isfind)cout<<"未找到该会员！"<<endl;elsecout<<"请输入要修改的会员名字："cin>>m->name;cout<<"修改成功！"<<endl;system("pause");system("cls");3.7统计void Statistic()Statistic(root);void LeagueManage:Statistic(Member *p)if(p!=NULL)if(p->tag=0)Statistic(p->lch);Statistic(p->rch);elseint i=0;cout<<"社团："<<p->name<<"，旗下会员有："Display(p->lch,i);Display(p->rch,i);cout<<"总计："<<i<<"人"<<endl;Statistic(p->lch);Statistic(p->rch);3.8删除删除社团：if(order=1)cout<<"请输入要删除的社团："cin>>name;FindAlter(name,isfind,p,q,m,n);if(isfind=false)cout<<"没有该社团！"<<endl;elsecout<<"社团："<<m->name<<"，旗下会员有："Display(m->lch,i);Display(m->rch,i);cout<<"n是否删除该社团（y/n）:"cin>>yn;if(yn='y'|yn='Y')if(m=root)Destroy(root);root=NULL;elseif(n->lch=m)Destroy(m);n->lch=NULL;elseDestroy(m);n->rch=NULL;cout<<"删除社团成功！"<<endl;system("pause");system("cls");删除会员：else if(order=2)cout<<"请输入要删除的会员名字："cin>>name;FindAlter(name,isfind,p,q,m,n);if(isfind=false)cout<<"没有该会员！"<<endl;elsecout<<"是否删除该会员（y/n）:"cin>>yn;if(yn='y'|yn='Y')DeleteMember(root,m,n);system("pause");system("cls");void LeagueManage:DeleteMember(Member *t,Member *p,Member *q) /删除会员bool b=1;Member *s,*m;if(p->lch=NULL)s=p->rch;else if(p->rch=NULL)s=p->lch;elsem=p;s=p->rch;while(s->lch!=NULL)m=s;s=s->lch;if(m=p)m->rch=s->rch;elsem->lch=s->rch;p->name=s->name;p->tag=s->tag;delete s;b=0;if(b=1)if(p=root)t=s;else if(q->lch=p)q->lch=s;elseq->rch=s;delete p;cout<<"删除会员成功！"<<endl;void LeagueManage:FindAlter(string name,bool &isfind,Member *p,Member *q,Member *&m,Member *&n) /找双亲，用于删除if(p!=NULL)if(p->name=name)isfind=true;m=p;n=q;elseq=p;FindAlter(name,isfind,p->lch,q,m,n);FindAlter(name,isfind,p->rch,q,m,n);4 调试分析4.1问题分析和解决 主要问题就是怎么区分社团和会员。我用的是一个标识符tag来区分。当tag=0时表示是会员，当tag=1时表示是社团。4.2算法的时间复杂度分析创建：因为创建是按二叉树的层次，从上到下从左到右依次录入，唯一所消耗的时间就是计算所插入节点的双亲节点，所以时间复杂度为O（1）；插入：此算法就是找到要插入子树的最左边的节点，所以时间复杂度是O（n）；查询：查询就是查找要查询的节点，所以时间复杂度是O（n）；修改：与查询一样，时间复杂度是O（n）；删除：与查询一样，时间复杂度是O（n）；统计：使用递归来遍历输出，所以时间复杂度是O（n）。4.3经验和体会 链表操作要注意指针，当指针没用好，很有可能就出现错误。使用二叉链表能很容易的实现一些基本操作。而且只要能熟练的使用递归都能完成一些常用的算法，二叉树的算法主要的就是递归的使用。5用户使用说明用户登录系统后根据屏幕上的提示进行相应的操作就可王城一切功能的实现。6测试结果主界面图 1-3 主界面创建图 1-4 创建查询主界面图 1-5 查询主界面查询社团图 1-6 查询社团查询会员图 1-7 查询会员修改主界面图 1-8 修改主界面修改社团图 1-9 修改社团修改会员图 1-10 修改会员插入主界面图 1-11 插入主界面插入社团图 1-12 插入社团插入会员图 1-13 插入会员统计图 1-14 统计界面删除主界面图 1-15 删除主界面删除社团图 1-16 删除社团删除会员图 1-17 删除会员退出图 1-18 退出界面结 论过本次课程设计可以得出链表的操作就是更改指针的指向，但就是因为就是改变指针的指向，所以才做时更应该小心指针的指向位置。链表存储具有非常大的优势，在内存足够的情况下，没有个数限制；而且对链表的操作除了查找，其它的操作都非常节约时间。高校社团管理系统总体上完成了对社团的管理工作，圆满的完成了所有要求。 致 谢在本次课程设计过程中，首先感谢周立章老师，其次感谢我的同学们。他们都给了我很多帮助，让我顺利的完成了本次课程设计。参考文献1杨宝刚.开展企业管理信息化工作的步骤J.企业管理.2002.（11）.12152 朱战立.数据结构(C+语言描述)（第二版本）.高等出版社出版.2004年4月3 王立柱.C/C+与数据结构.北京：清华大学出版社，20024 顾元刚.数据结构简明教程.南京：东南大学出版社等，20035 郭福顺，王晓芬，李莲治数据结构（修订本），大连理工大学出版社，19976 美Mark Allen Weiss，数据结构与算法分析C语言描述(英文版第2版)，人民邮电出版社，2005.87 李春葆著，数据结构教程，清华大学出版社，2005.1所有代码：#include<iostream>#include<string>using namespace std;typedef string ElemType;struct MemberElemType name; /姓名int tag; /标识符,tag=0表示是会员，tage=1表示是社团Member *lch;Member *rch;class LeagueManageprivate:Member *root;public:LeagueManage()root=NULL;LeagueManage()Destroy(root);root=NULL;void CreatBTree(); /建立以二叉链存储的社团void Find(); /输入社团名称或社团中团员姓名查询void Alter(); /修改void Insert(); /插入void Statistic()Statistic(root); /统计每个社团中的成员数void DeleteNode(); /删除private:void FindMember(Member*,string,bool&,ElemType,Member*&); /查找会员void FindLeague(Member*,string,bool&,Member*&); /查找社团void FindAlter(string,bool&,Member*,Member*,Member*&,Member *&);/找双亲void Insert(Member*,string); /插入void Statistic(Member *p);void DeleteMember(Member*,Member*,Member*); /删除会员void Destroy(Member*); /删除所有节点void Display(Member*,int&); /遍历输出;void LeagueManage:CreatBTree() /创建Member *p,*s30;ElemType name;int tag=0;int i=1,j;cout<<"请按照二叉树的层序，自上而下自左至右顺序输入数据。"<<endl;cout<<"标识符 0：会员 1：社团,输入会员名为0时结束录入。"<<endl;cout<<"请输入标识符、名字："cin>>tag>>name;while(pare("0")if(i=1)while(tag=0)cout<<"输入错误，请先创建一个社团！请重新输如："cin>>tag>>name;p=new Member;p->name=name;p->tag=tag;p->lch=p->rch=NULL;si=p;if(i=1)root=p;elsej=i/2;if(i%2)=0)sj->lch=p;elsesj->rch=p;i+;cout<<"标识符、名字："cin>>tag>>name;void LeagueManage:Find() /查找int order=-1;int i=0;Member *m=NULL;ElemType e;bool isfind=false;string name;cout<<" *"<<endl;cout<<" * 1、查询社团 *"<<endl;cout<<" * 2、查询会员 *"<<endl;cout<<" * 3、退出 *"<<endl;cout<<" *"<<endl;cout<<"请输入查询方式："cin>>order;while(order!=1&&order!=2&&order!=3)cout<<"输入错误，请重输："cin>>order;if(order=1)cout<<"请输入社团名字："cin>>name;FindLeague(root,name,isfind,m);if(!isfind)cout<<"未找到该社团！"<<endl;elsecout<<"社团："<<m->name<<"，旗下会员有："Display(m->lch,i);Display(m->rch,i);cout<<endl;system("pause");system("cls");else if(order=2)cout<<"请输入会员名字："cin>>name;FindMember(root,name,isfind,e,m);if(!isfind)cout<<"未找到该会员！"<<endl;system("pause");system("cls");elsesystem("cls");void LeagueManage:FindLeague(Member *p,string name,bool &isfind,Member *&m) /查找社团if(p!=NULL)if(p->tag=0)FindLeague(p->lch,name,isfind,m);FindLeague(p->rch,name,isfind,m);else if(pare(p->name)FindLeague(p->lch,name,isfind,m);FindLeague(p->rch,name,isfind,m);else if(!pare(p->name)isfind=true;m=p;void LeagueManage:FindMember(Member *p,string name,bool &isfind,ElemType e,Member *&m) /查找会员if(p!=NULL)if(p->tag=1)e=p->name;FindMember(p->lch,name,isfind,e,m);FindMember(p->rch,name,isfind,e,m);else if(pare(p->name)FindMember(p->lch,name,isfind,e,m);FindMember(p->rch,name,isfind,e,m);else if(!pare(p->name)isfind=true;cout<<"会员姓名："<<p->name<<"，所属社团："<<e<<endl;m=p;void LeagueManage:Alter() /修改int order=-1;int i=0;ElemType e;bool isfind=false;Member *m=NULL;string name;cout<<" *"<<endl;cout<<" * 1、修改社团 *"<<endl;cout<<" * 2、修改会员 *"<<endl;cout<<" * 3、退出 *"<<endl;cout<<" *"<<endl;cout<<"请输入修改方式："