简易家谱系统.docx

简易家谱系统.docx

《简易家谱系统.docx》由会员分享，可在线阅读，更多相关《简易家谱系统.docx（36页珍藏版）》请在冰点文库上搜索。

简易家谱系统

编号：

学号：

课程设计

教学院

计算机学院

课程名称

数据结构课程设计

题目

简易家谱系统

专业

计算机科学与技术

班级

2015专升本

姓名

xxx

同组人员

Xxx

指导教师

xxx

2015

年

12

月

29

日

目录

一概述2

1.课程设计的目的2

2.课程设计的要求2

二总体方案设计3

三详细设计4

3.数据节点定义4

4.存储节点定义4

5.统计总人数4

6.统计从事某一职业的总人数7

四程序的调试与运行结果说明8

五课程设计总结11

参考文献13

一概述

1.课程设计的目的

1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。

2．培养综合运用所学知识独立完成课题的能力。

3．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。

4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。

2.课程设计的要求

设计要求：

输入家族成员情况，建立树结构，统计家族成员人数，能查询家族成员辈份情况。

系统功能：

1.输入、修改与删除家谱信息功能

2.查询功能：

1）某家谱成员的所有子孙的集合

2）某家谱成员的所有祖先的集合

3）某家谱成员的所有同辈成员的集合

4）求某家谱成员的所有上一辈成员的集合

5）统计族谱人数

6）统计某一职业人数

二总体方案设计

1.简单家谱系统整体设计思路

此次课程设计的整体思路是采用树型结构存储采用遍历算法来统计族谱中的人数与从事某一职业的人数。

树型结构采用三个指针域，父指针兄弟指针第一个孩子指针构成，方便查找和快速查找到树形结构的任何一个一层的某一个节点。

极大的优化了遍历算法的时间复杂度

统计人数采用层序遍历算法遍历每一层的每一个节点，每找到一个节点计数器加一，直到找到最后一个节点。

统计职业同样采用层序遍历算法，每次与数组中已经存在的职业进行比较。

如果没有则保存有则继续查找下一个节点，直到找到最后一个节点。

程序所有数据保存在内存中，断电丢失。

由于时间原因没有做太多优化，开始设计方案是使用hash表也改成了数组检测重复。

因为构建hash表的时间原因放弃了很多优秀的设计

2.简单家谱系统的主要特点及功能

本系统的主要特点是算法简洁，易于阅读，用户交互界面良好。

主要实现功能：

1.输入、修改与删除家谱信息功能

2.查询功能：

1）某家谱成员的所有子孙的集合

2）某家谱成员的所有祖先的集合

3）某家谱成员的所有同辈成员的集合

4）求某家谱成员的所有上一辈成员的集合

5）统计族谱人数

6）统计某一职业人数

三详细设计

1.总体流程图

2.统计族谱中总人数

该部分程序所完成的具体功能是统计族谱中的人数，采用的数据结构是树型结构，利用广度优先遍历算法依次统计每一层的节点的个数相加得到总人数从根节点开始

intcount（Tree*tree）{

intresult=0;

QUEUE*que=QUEUEinit（M）;

Node*head=tree;

QUEUEenqueue（que,head）;

while（QUEUEempty（que）==0）{

Node*deque;

QUEUEdequeue（que,&deque）;

result++;

deque=deque->firstChild;

while（deque）{

QUEUEenqueue（que,deque）;

deque=deque->nextSibling;

}

}

returnresult;

}

3.统计族谱中从事某一职业的人数

该部分程序所完成的具体功能是统计族谱中从事某一职业的人数，与统计人数算法相同采用广度优先遍历算法遇到与搜索的职业匹配，每匹配到一个人计数器加一最终返回计数器

voidstatistical（Tree*tree）{

printf（"请输入要查找的职业\r\n"）;

char*post=（char*）util_malloc（M）;

scanf（"%s",post）;

intresult=0;

QUEUE*que=QUEUEinit（M）;

Node*head=tree;

QUEUEenqueue（que,head）;

while（QUEUEempty（que）==0）{

Node*deque;

QUEUEdequeue（que,&deque）;

if（strcmp（post,deque->item->post）==0）

{

result++;

}

deque=deque->firstChild;

while（deque）{

QUEUEenqueue（que,deque）;

deque=deque->nextSibling;

}

}

printf（"从事%s的人数共%d",post,result）;

}

四程序的调试与运行结果说明

本程序输入只有两种方式一种为姓名+空格+职业一种为只输入姓名

初始化系统

输入姓名职业

进入主界面

选择功能

插入功能

修改功能

查询功能

查找族谱中子孙功能

查找同辈功能

查找祖先功能

统计总人数功能

统计从事某一职业总人数功能

删除功能

五课程设计总结

本组的课程任务为简易家谱，经过我们共同的努力，本程序主要任务已基本完成。

另外本程序功能完善，具有良好的交互性，可以满足用户多种需求。

美中不足的是本系统没有采用之前我所设想的递归，我们这次改用队列来建树、查找等，这样代码少有一定的冗余，如果时间充分，我们会更加精进，争取采用代码量相对较少的递归算法，另外更加完善一些功能，包括增加日志功能，给不同级别的人员设置管理权限，比如说家谱管理员在获得本族长的同意下修改某个成员的信息，而其他成员只具备浏览的功能。

在本程序简易家谱的创作过程中，我们组员各抒己见，意见很不一致，包括是采用递归算法，还是采用队列；数据成员的结构如何定义，甚至包括成员的名字，大家的意见都不统一。

但是在探讨的过程中，我们也理解自己思维的不足，也见识了另外不同的编程思想，这也让我体会到了交流的魅力。

只有我们大家坦诚布公的把自己想法说出来，然后我们在理性的分析算法的优劣与可行性，这样就能结合大家共同的智慧，组织大家共同的力量，为共同的目标努力奋斗。

次大作业的推荐学时是20个学时，但回想起来，光这篇报告就写了有三四个学时，由于我本身编程能力不强，构思，写代码，修改，调试的时间加起来绝对是有余了。

虽然付出不少，但在前期的设计组织中，中期的代码编写和后期的修改调试中都学到了不少。

起初我的家谱中数据并不是以结构的形式打包，读入，写出操作的时候代码异常繁琐，这是恰好看到一本编程书上有用结构输入输出的范例，深深感到结构化确实是方便多了，而且读写不容易出错。

当时我的代码本已经写了有一大半，思虑再三，还是决定进行大换血，家谱数据的改变让程序来了个大换血，提高了效率的同时，代码几乎变了一多半。

我想，当时唯一不变的就只有对整个程序越来越清醒地认识和对将要完成的代码的更准确地把握。

代码完成之后，一编译，至少有五六十个错误提示，而且最末debug一行栏的最后一行提示因为先前的错误而中断编译，有的是指针指向错误，有的是忘了分号，括号，更多的是一些赋值错误，前面的错误都好改，赋值错误就比较麻烦了，因为要使用赋值的地方太多，逐行改代码虽然也可以，但实在是一个巨大工程。

所谓巧招必是险招——至少对我是这样——说来惭愧，我只有尝试着写以前从未是过的运算符重载函数，为此专门翻找出了大一的C++教材，温习了一番运算符重载才战战兢兢地搞定了赋值问题。

试运行时出现了更多的问题，而且更具有隐蔽性，几次为了一个逻辑错误而来回反复地翻看代码，嘿嘿，再加上网上有代码的传说，让人有想直接放弃的冲动，但一想到写代码的辛苦，觉得放弃了实在可惜。

那几天吃饭，睡觉，走路，看电视，随时随地，都记挂着那几处错误，脑子都会浮现出代码的影子，不自觉地开始找错误。

哎~那种感觉！

~不知道是充实还是急迫地烦恼，最后终于找到了，根本来不急高兴，只有松了一口气和一阵的疲惫。

现在程序终于完成了，心里的石头也下了地。

至于成绩，不想了~~

另外，通过本次课程设计，我觉得自己最大的收获就是：

（1）学会了怎样将课堂所学知识运用到较为实际的应用中来

由于对二叉链表的存储比较感兴趣，我选做的是家谱，开始觉得无从下手，但是经过仔细分析后，渐渐找到一点思路（首先创建，然后分别实现各个功能，最后利用菜单实现选择功能并输出结果）。

（2）锻炼提出问题、解决问题和自学的能力

家谱的实现要求读、写文件，于是“如何将文件从文档中读出”，“怎么写入文件”都是要满足要求必须解决的问题。

为此，我查找了很多资料，最后自学、解决这一问题

（3）增加了对编程的热爱和兴趣

本次编写家谱程序的过程中，我体验到了编程的酸甜苦辣：

开始，由于即将运用所学知识设计实际问题而激动兴奋；后来编写程序过程中，在想不出算法如何实现或者追求空间、时间上高效率的算法时会比较纠结；以及遇到BUG时，追踪数据的痛苦；当然，还有解决问题后的激动与自豪。

所有这些都增强了我对编程的热爱、提高了我对计算机专业的兴趣。

参考文献

[1]严蔚敏，数据结构与算法，北京，清华大学出版社，2000年9月。

完整代码：

//多叉树的建立、层次遍历、深度遍历

//摘自

#include

#include

#include

#defineM100+1//宏定义，定义最大名字字母长度

typedefstructelem{

char*name;

char*post;

}element;

//双亲孩子表示法

typedefstructtree{

element*item;

intlevel;

intchildNum;

structtree*parent;

structtree*nextSibling;

structtree*prevSibling;

structtree*firstChild;

}Node,Tree;

//实现一个栈，用于后续操作

typedefstructstack_t

{

Node**array;//array是个数组，其元素为Node*型指针

intindex;//指示栈顶元素

intsize;//栈的大小

}STACK;//重命名

//实现一个队列，用于后续操作

typedefstructqueue_t

{

Node**array;//array是个数组，其内部元素为Node*型指针

inthead;//队列的头

inttail;//队列的尾

intnum;//队列中元素的个数

intsize;//队列的大小

}QUEUE;

//这里的栈和队列，都是用动态数组实现的，另一种实现方式是用链表

//内存分配函数

void*util_malloc（intsize）

{

void*ptr=malloc（size）;

if（ptr==NULL）//如果分配失败，则终止程序

{

printf（"Memoryallocationerror!

\n"）;

exit（EXIT_FAILURE）;

}

//分配成功，则返回

returnptr;

}

//字符串赋值函数

//对strdup函数的封装，strdup函数直接进行字符串赋值，不用对被赋值指针分配空间

//比strcpy用起来方便，但其不是标准库里面的函数

//用strdup函数赋值的指针，在最后也是需要free掉的

char*util_strdup（char*src）

{

char*dst=strdup（src）;

if（dst==NULL）//如果赋值失败，则终止程序

{

printf（"Memroyallocationerror!

\n"）;

exit（EXIT_FAILURE）;

}

//赋值成功，返回

returndst;

}

//对fopen函数封装

FILE*util_fopen（char*name,char*access）

{

FILE*fp=fopen（name,access）;

if（fp==NULL）//如果打开文件失败，终止程序

{

printf（"Erroropeningfile%s!

\n",name）;

exit（EXIT_FAILURE）;

}

//打开成功，返回

returnfp;

}

//实现一些栈操作

//栈的初始化

STACK*STACKinit（intsize）//初始化栈大小为size

{

STACK*sp;

sp=（STACK*）util_malloc（sizeof（STACK））;

sp->size=size;

sp->index=0;

sp->array=（Node**）util_malloc（size*sizeof（Node*））;

returnsp;

}

//检测栈是否为空

//如果为空返回1，否则返回0

intSTACKempty（STACK*sp）

{

if（sp==NULL||sp->index<=0）//空

{

return1;

}

return0;

}

//压栈操作

intSTACKpush（STACK*sp,Node*data）

{

if（sp==NULL||sp->index>=sp->size）//sp没有被初始化，或者已满

{

return0;//压栈失败

}

sp->array[sp->index++]=data;//压栈

return1;

}

//弹栈操作

intSTACKpop（STACK*sp,Node**data_ptr）

{

if（sp==NULL||sp->index<=0）//sp为初始化，或者为空没有元素

{

return0;

}

*data_ptr=sp->array[--sp->index];//弹栈

return1;

}

//将栈消毁

voidSTACKdestroy（STACK*sp）

{

free（sp->array）;

free（sp）;

}

//以上是栈的操作

//实现队列的操作

QUEUE*QUEUEinit（intsize）

{

QUEUE*qp;

qp=（QUEUE*）util_malloc（sizeof（QUEUE））;

qp->size=size;

qp->head=qp->tail=qp->num=0;

qp->array=（Node**）util_malloc（size*sizeof（Node*））;

returnqp;

}

//入队列

intQUEUEenqueue（QUEUE*qp,Node*data）

{

if（qp==NULL||qp->num>=qp->size）//qp未初始化或已满

{

return0;//入队失败

}

qp->array[qp->tail]=data;//入队，tail一直指向最后一个元素的下一个位置

qp->tail=（qp->tail+1）%（qp->size）;//循环队列

++qp->num;

return1;

}

//出队列

intQUEUEdequeue（QUEUE*qp,Node**data_ptr）

{

if（qp==NULL||qp->num<=0）//qp未初始化或队列内无元素

{

return0;

}

*data_ptr=qp->array[qp->head];//出队

qp->head=（qp->head+1）%（qp->size）;//循环队列

--qp->num;

return1;

}

//检测队列是否为空

intQUEUEempty（QUEUE*qp）

{

if（qp==NULL||qp->num<=0）

{

return1;

}

return0;

}

//销毁队列

voidQUEUEdestroy（QUEUE*qp）

{

free（qp->array）;

free（qp）;

}

//以上是队列的有关操作实现

//创建元素

element*createElement（）{

element*temp=（element*）util_malloc（sizeof（element））;

printf（"请输入姓名和职业:

\r\n"）;

temp->name=（char*）util_malloc（M）;

temp->post=（char*）util_malloc（M）;

scanf（"%s%s",temp->name,temp->post）;

returntemp;

}

//初始化族谱

Tree*createTree（）{

Tree*head=（Tree*）util_malloc（sizeof（Tree））;

head->childNum=0;

head->level=0;

head->firstChild=head->parent=head->nextSibling=NULL;

head->item=createElement（）;

returnhead;

}

Node*searchNodeByName（char*name,Tree*tree）{

Node*head=tree;

Node*result=NULL;

QUEUE*que=QUEUEinit（M）;

QUEUEenqueue（que,head）;

while（QUEUEempty（que）==0&&result==NULL）{

Node*temp;

QUEUEdequeue（que,&temp）;

if（strcmp（name,temp->item->name）==0）

{

result=temp;

}

else{

temp=temp->firstChild;

while（temp!

=NULL）{

QUEUEenqueue（que,temp）;

temp=temp->nextSibling;

}

}

}

/*

if（tree!

=NULL）

{

if（strcmp（name,tree->item->name）==0）

{

temp=tree;

}

else{

while（temp!

=NULL&&tree->nextSibling!

=NULL）{

temp=searchNodeByName（name,tree->firstChild）;

}

}

}*/

returnresult;

}

Node*createNode（）{

Node*temp=（Node*）util_malloc（sizeof（Node））;

temp->childNum=0;

temp->level=0;

temp->firstChild=temp->parent=temp->nextSibling=temp->prevSibling=NULL;

temp->item=createElement（）;

returntemp;

}

//插入节点

voidinsertNode（Tree*tree）{

printf（"请输入双亲的名字:

\r\n"）;

char*parentName=（char*）util_malloc（M）;

scanf（"%s",parentName）;

Node*parent=searchNodeByName（parentName,tree）;

if（parent!

=NULL）

{

printf（"找到双亲姓名:

%s职位:

%s",parent->item->name,parent->item->post）;

Node*child=createNode（）;

child->parent=parent;

if（parent->firstChild==NULL）

{

parent->firstChild=child;

}else{

Node*lastChild=parent->firstChild;

while（lastChild->nextSibling!

=NULL）{

lastChild=lastChild->nextSibling;

}

lastChild->nextSibling=child;

child->prevSibling=lastChild;

}

printf（"插入成功\r\n"）;

}else{

printf（"没有找到双亲\r\n"）;

system（"pause"）;

}

free（parentName）;

}

voidFreeNode（Node*Node）{

free（Node->item->name）;

free（Node->item->post）;

free（Node->item）;

free（Node->firstChild）;

free（Node->parent）;

free（Node->nextSibling）;

free（Node）;

}

//倒序层次遍历从右往左-->从孩子到父亲

voidReverseTraversal（Node*nod