数据结构课程设计报告

1、数据结构课程设计报告 身份证信息管理系统 学院：理学院专业：信息与计算科学班级：学号：3姓名：指导老师：姜俊坡需求分析 通过学习数据结构这门课程，我们学习了很多存储数据的方法，当然不同的方法对于对数据的查找有不同的效率。本课题要求建立一个身份证信息管理系统，并使其能够进行身份证的录入、查找、修改、删除。身份证信息管理系统可以由多种方法构造，如进行散列表的建立、查找、打印等。但是由于身份证号码的唯一性，考虑到查找的效率，采用二叉排序树可以获得较高的查找效率，所以我采用二叉排序树进行身份证信息的存储。根据分析，本课题需要完成的具体功能有：（1） 能够进行身份证号码及相关信息的录入，相关信息包括姓名

2、、地址和手机号码；（2） 能够尽快进行身份证号码的查询，并输入出相关信息；（3） 可以修改身份证号码对应的其他信息，如姓名、地址；（4） 可以完成身份证信息的删除。 总体设计 根据需求分析结果确定程序的总体设计，首先在每个功能中都有输入和输出，所以设计时需要采用交互方式。通过编写一个主菜单功能来实现添加身份信息、修改身份证信息、删除身份证信息、查询身份证信息等各个功能模块的调用，从而更好地协调各个功能模块之间的关系。根据功能分析确定的系统功能模块如下图所示。 主界面 添加身份证信息删除身份证信息 修改身份证信息查找身份证信息输出全部信息退出系统 设计思路1. 利用到的知识点（1） 二叉排序树的

3、建立；（2） 二叉排序树的查找；（3） 二叉排序树的删除。2. 详细的设计思想（1） 采用的数据结点和存储结构经过分析，身份证相关信息需要包括身份证号、姓名、地址和电话。身份证号码采用18位字符，姓名考虑采用10位字符，地址采用20位字符，电话不是必须填写的，采用字符存储。二叉排序树或者是一颗空树，或者是具有下列性质的二叉树： 如果左子树不空，则左子树上所有结点的值均小于它的根结点的值； 如果右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左右子树也分别为二叉排序树。对于一个记录集合，可以用一颗二叉排序树来表示，树中的一个结点对应与集合中 的一个记录，整棵树表示该记录集合。二叉排

4、序树中每个结点所存储的记录，其关键字都大于它的左子树上所有结点存储的记录的关键字，而小于它的右子树上所有结点存储的记录的关键字。用二叉排序树表示记录集合时，不但容易进行动态查找，而且对二叉排序树进行中序遍历时还可以得到记录集合中各记录的有序排列。 二叉排序树的存储结构采用二叉链表存储方式。本课题中存储身份证信息时的结点和存储结构如下图所示： 身份证号姓名住址电话 身份证号姓名住址电话身份证号姓名住址电话 （2）采用的算法查找算法。由于身份证号码的唯一性，查找算法以身份证号码为关键字进行。a） 当二叉排序树为空时，查找失败。b）如果二叉排序树根结点的关键字等于要查找的关键字时，则查找成功。c）如

5、果二叉排序树根结点的关键字小于要查找的关键字，则有同样的方法继续在根结点的右子树上查找。d）如果二叉排序树根结点的关键字大于要查找的关键字，则有同样的方法继续在根结点的左子树上查找。 在根结点为p的二叉排序树中，查找身份证号码为id的结点，算法流程图如下所示：开始 结束p=p-rchild p=p-lchild查找不成功，返回结点空指针p平PPPPP-KONGP指针P查找成功，返回结点指针pId大于所指的结点id的？p不空？ 否 id小于所指的结点id的？ 是 否 是 是对含有n个结点的二叉排序树来说，在树上查找结点的关键字等于某个给定值的过程走的是一条从根结点到该结点的路径，所需要做的比较次

6、数等于该结点所在的层数。因此，平均查找长度不仅和结点的个数n有关,更为重要的是树的形态有关。在最好的情况下，二叉排序树的形态和折半查找的判定树相同，其平均查找长度为0(log2n),在最坏的情况下(单枝树)，平均查找长度为(n+1)/2。所以在构造二叉树排序树时的输入顺序也很重要，一般来说，输入的顺序越无序，构造出的二叉树排序树越利于查找。 插入算法。在二叉排序树中插入新的结点时，必须要保证插入后的二叉树任然满足二叉排序树的定义。因此，插入时必须首先找出合适的插入位置。实际上，待插入结点的位置就会死在查找过程中所查找的最后一个结点的左孩子或右孩子，新插入的结点一定是叶子结点。因此，仍可采用上述

7、查找算法。当查找失败时，在二叉排序树中插入关键字等于给定值的结点。插入的过程如下：a） 若二叉排序树为空树，则将新插入的结点作为根结点插入。b） 若二叉排序树的根结点关键字值等于要插入的结点的关键字，则返回。c） 若要插入结点的关键字小于根结点关键字，则把要插入的结点插入到左子树中。d） 若要插入结点的关键字大于根结点关键字，则把要插入的结点插入到右子树中。 在子树中插入的方法与在整棵树中插入的方法是相同的，如此下去，直到把要插入的结点插入到二叉排序树中或发现树中已有此关键字为止。 删除算法。与在二叉排序树上做插入操作的要求一样，从二叉排序树中删除一个结点，要保证删除后的二叉树仍然是一颗二叉排

8、序树。根据二叉排序树的结构特征，可以分一下4种情况来考虑。a） 待删除的结点都是叶结点。直接删除该结点。b） 待删除的结点只有左子树，而无右子树。根据二叉排序树的特点，在这种情况下可以直接将其左子树的根结点放到被删除结点的位置。c） 待删除的结点只有右子树，而无左子树。根据二叉排序树的特点，在这种情况下可以直接将其右子树的根结点放到被删除结点的位置。 d）待删除的结点同时有左、右子树。根据二叉排序树的特点，可以将其右子树放到被删除结点的位置上，再把被删除的结点的左子树链接到被删除结点右子树的最左子树的左孩子结点上；也可以直接将被删除结点的左孩子代替被删除的结点，同时将被删除的结点的右子树收为被

9、删除结点左子树中序尾结点的右孩子。 程序代码.数据结构设计根据分析确定结点数据结点的数据结构包含4部分，即身份证号码、姓名、地址和电话。typedef struct char id19; char name11; char address21; char phone12;Keytype;存储时采用二叉排序树，结点包含身份证系统的信息以及左子树指针和右子树指针。typedef struct BSNode Keytype key;struct BSNode*lchild;struct BSNode*rchild;bsnodetype;.功能函数设计btree bssearch(btree p,ch

10、ar *id) /二叉树排序中查询结点的查找算法void insert(btree *root,char*id) /插入算法void inorder(btree t) /按照中序遍历的方式输出二叉树btree createbtree(void) /创建二叉树的算法btree Delete(btree bt,char *id) /删除结点的算法.程序实现#include#include#includetypedef struct char id19; char name11; char address21; char phone12;Keytype;typedef struct BSNode K

11、eytype key;struct BSNode*lchild;struct BSNode*rchild;bsnodetype;typedef bsnodetype *btree;btree bssearch(btree p,char *id)while(p)if(strcmp(id,p-key.id)lchild;else if(strcmp(id,p-key.id)0)p=p-rchild;elsereturn p; return p;void insert(btree *root,char*id) btree f,p;char name10,address20,phone11;f=NUL

12、L;p= *root;while(p) if(strcmp(id,p-key.id)=0)printf(该号码已经存在，不能插入n);return;f=p;p=(strcmp(id,p-key.id)lchild:p-rchild;p=(btree)malloc(sizeof(bsnodetype);strcpy(p-key.id,id);printf(请输入10个字符之内的姓名n);scanf(%s,name);strcpy(,name);printf(请输入20个字符之内的地址n);scanf(%s,address); strcpy(p-key.address,addr

13、ess);printf(请输入11个字符之内的电话n);scanf(%s,phone); strcpy(p-key.phone,phone);p-lchild=NULL;p-rchild=NULL;if(*root=NULL)*root=p;elseif(strcmp(id,)lchild=p;elsef-rchild=p;void inorder(btree t) if(t)inorder(t-lchild);printf(%s ,t-key.id); printf(%s ,); printf(%s ,t-key.address);printf(%sn

14、,t-key.phone);inorder(t-rchild);btree createbtree(void) btree root; char id19; root=NULL; printf(n如果输入结束请输入-1，如果要输入，请输入18位身份证号码：n); scanf(%s,id); while(strcmp(id,-1)!=0) while(strlen(id)!=18) printf(身份证号码不是18位，请重新输入n);scanf(%s,id); insert(&root,id); printf(n如果输入结束请输入-1，如果要输入，请输入18位身份证号码：n); scanf(%s

15、,id); return root;btree Delete(btree bt,char *id)btree p,q;if(strcmp(bt-key.id,id)=0)/该结点为要删除的点 if(bt-lchild=NULL&bt-rchild=NULL)/删除的是叶结点 free(bt); return NULL;else if(bt-lchild=NULL)/删除的是无左子树的结点p=bt-rchild; free(bt); return p; else if(bt-rchild=NULL)/删除的是无左子树的结点p=bt-lchild; free(bt); return p; else

16、 /删除的是有左、右子树的结点p=q=bt-rchild;while(q-lchild!=NULL) q=q-lchild;q-lchild=bt-lchild;free(bt);return p; else if(strcmp(bt-key.id,id)0&bt-lchild!=NULL)bt-lchild=Delete(bt-lchild,id);if(strcmp(bt-key.id,id)0&bt-rchild!=NULL)bt-rchild=Delete(bt-rchild,id);return bt;void main()btree position;int c,len;char

17、id18;btree root;char name11;char address21;char phone12;root=NULL;system(cls);do/显示主菜单 printf(- Menu -n); printf(-n); printf(tt1.插入n); printf(tt2.删除n); printf(tt3.显示n); printf(tt4.查找n); printf(tt5.修改n); printf(tt6.录入n); printf(tt7.退出n); printf(-n); printf(tt请按1-7数字选择：n); scanf(%d,&c);switch(c) case

18、1:printf(请输入要输入要插入的身份证号码：n); scanf(%d,id);len=strlen(id);if(len=18)insert(&root,id);elseprintf(输入号码不是18位，不能输入，请重新选择：n); break; case 2:if(root) printf(请输入要输入要删除的身份证号码：n); scanf(%d,id); len=strlen(id); if(len=18) position=bssearch(root,id); if(position) root=Delete(root,id); printf(删除成功。n); else print

19、f(身份证号码不存在，不能删除，请重新选择：n); else printf(输入号码不是18位，不能删除，请重新选择：n); else printf(目前没有任何身份证信息，不能删除，请重新选择：n); break; case 3:if(root=NULL) printf(目前没有任何身份证信息，请重新选择：。n); else inorder(root); break; case 4:if(root=NULL) printf(目前没有任何身份证信息，不能删除，请重新选择：n); else printf(请输入需要查找的身份证号码：n); scanf(%d,id); len=strlen(id)

20、; if(len=18) position=bssearch(root,id); if(position!=NULL) printf(要查找的信息是：n); printf(%s %s %s %sn,position-key.id,,position-key.address,position-key.phone); else printf(信息不存在：n); else printf(输入号码不是18位，不能查找，请重新选择：n); break; case 5:if(root=NULL) printf(目前没有任何身份证信息，请重新选择：n); else printf(请输入要修改信息的身份证号：n); scanf(%d,id); l