数据结构及其应用(算法与数据结构课程设计)word格式.doc

数据结构及其应用一、问题描述 二叉树是一种常见的数据结构，在实际中应用十分广泛。二叉树有顺序和链式两种存储结构，可以运用递归和非递归设计算法，能够求解节点在二叉树中的层次数等问题。在实际应用中，要求以同学录为例完成系统的设计与管理。二、基本要求 1、选择合适的存储结构，完成二叉树的建立。最好采用顺序和链式两种方法。 2、在顺序二叉树中求解节点所在层次数。 3、在链式二叉树中求解节点所在层次数。 4、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。三、测试数据 1、分别以顺序和链式存储测试图示二叉树中节点E所在层次： 2、同学录的测试数据： 赵一,1979-01-010807011001 钱二,1980-02-020807011002 孙三,1981-03-030807011003 李四,1982-04-040807011004 在上表的的基础上，测试表的建立，以及记录的新增、修改、删除等。四、算法思想 1、在顺序二叉树下求节点所在层次数 本题中顺序二叉树按照满二叉树的原则建立，空节点存“0”。故节点所在层次count与节点下标m有如下关系： 1)初始层次数count=1，当m=0时，所查节点不存在 2)当m非0时，令m=m/2，count加一 3)m不为1时，返回层次数count；m为1时，重复步骤2) 2、在链式二叉树下求节点所在层次数 算法要用非递归算法求解二叉树中给定节点的深度，为实现层次非递归求解，必须借用数据结构保存将要访问的节点，在函数CengciTree(BiTreeLink T,char c)中用数组queue实现此功能。具体编程时，用变量n保存当前访问的节点的层次数目并初始化为1，front和rear是数组queue中当前正在访问的节点的下标以及可插入节点的下标，而flag起到标志作用用来表明是否要增加当前的层次数n。 算法开始时，首先判断树是否为空，若为空树退出程序；若树不为空，则先判断根节点的值是否与要查找节点的值相等，若相等则返回n，否则将当前层次n加1，并将根节点的左孩子、右孩子以及根节点本身插入到数组queue中。可能，有人会问为什么还要将根节点插入到数组queue中？这里，将根节点插入到数组queue中的目的是，当queuefront保存的是根节点的指针时，二叉树的一层节点遍历结束了，需要将当前层次数n加1并让queuerear保存根节点的指针。算法的核心部分就是while循环里面的内容，首先让标志flag值为0,如果queuefront不为空且queuefront-data的值等于要查找的值c，程序结束返回n即可；若queuefront的值是指向根节点的指针，表明当前层次上的所有节点都已经访问过了，要访问下一个层次的节点了，故要把n加1并让flag值为1以表明在数组的插入位置queuerear需要赋值为跟节点的指针；如果，均不是上述情况，则将queuefront的左孩子、右孩子都放到数组queue中，并将front指向下一个元素。重复上述循环，直到找到了要查找的值，或者遍历了所有的节点。 3、同学录的实现 本题的一个实际应用是实现同学录，我们采用二叉树存储结构，利用预置数组建立二叉树；先序方式遍历二叉树并输出；递归算法实现对同学录的查找；基于查找实现对同学录的修改和新增成员；求所要操作节点的父亲节点，从而顺利的编写对同学录的删除操作。五、模块划分：1、在顺序二叉树下求节点所在层次数（1）void Creattree()其功能是建立顺序二叉树；（2）void Cengcitree()其功能是求节点层次2、在链式二叉树下求节点所在层次数（1）int CreateBiTree(BiTreeLink *T)其功能是建立二叉树；（2）void PreOrderTraverse(BiTreeLink T) 其功能是先序遍历二叉树；（3）int CengciTree(BiTreeLink T,char c) 其功能是求层次数（1）int n=0,front=0,rear=0,flag;初始化队列；（2）(front+1)%MAXSIZE!=rear判断队列不满。3、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。（1）void CreateBiTree(DataType *items,BiTree *T)其功能是建立同学录（2）void PreOrderTraverse(BiTree T)（3）PBTNode SearchTree(BiTree T,char *ch)（4）void ModifyTree(BiTree T)（5）void DeleteTree(BiTree T)4、main()主函数，功能是调要相关函数实现问题的求解。六、数据结构：1、二叉树的抽象数据类型结构定义：typedef struct Node TElemType data; struct Node *lchild,*rchild; BiTNode, *BiTreeLink;2、同学录节点信息：typedef struct Infochar name20;/姓名char date11;/生日char phone12;/电话char StudentNum11;/学号DataType;3、同学录数据存储结构：typedef struct Node DataType data; struct Node *left,*right; BTNode, *PBTNode,*BiTree;七、源程序：1、在顺序二叉树下求节点所在层次数#define maxlen 100#includestdio.htypedef struct node char data; Bitreemaxlen;int N; Bitree T;/*建立二叉树*/void Creattree() int i; char c;printf(请输入结点数目(包括空结点)：);scanf(%d,&N);printf(请输入结点(空结点为0):);for(i=1;i=N;i+)scanf(%s,&c);Ti.data=c;/*求二叉树节点所在层次*/void Cengcitree()int i,m=0,count=1; char c;printf(请输入某一结点：); scanf(%s,&c);i=1;while(i=N)if(Ti.data=c)m=i; break; i+;if (m=0) printf(n节点不存在);while(m!=1)m=m/2;count+;printf(n节点所在层次:%dn,count);/*主函数*/void main()Creattree();Cengcitree();2、在链式二叉树下求节点所在层次数#include stdio.h#include #include #define MAXSIZE 20#define NULL 0typedef char TElemType;/* 二叉链树的类型定义*/typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode, *BiTreeLink;/*先序建立二叉树*/int CreateBiTree(BiTreeLink *T) char ch; scanf(%c,&ch); if (ch= ) *T=NULL; else *T=(BiTreeLink)malloc(sizeof(BiTNode); if (!(*T) return 0; /* 未分配到空间错误返回*/ (*T)-data=ch; CreateBiTree(&(*T)-lchild); CreateBiTree(&(*T)-rchild); return 1; /* 先序遍历二叉树*/void PreOrderTraverse(BiTreeLink T) if (T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /*求二叉树节点所在层次数*/int CengciTree(BiTreeLink T,char c)int n=1,front=0,rear=0,flag;BiTreeLink queueMAXSIZE;/if(!T)printf(树为空!n);return n;if(T-data=c)return n;queuerear+=T-lchild;queuerear+=T-rchild;queuerear+=T; n+;while(front+1)%MAXSIZE!=rear)flag=0;if(queuefront&queuefront-data=c) return n;if(queuefront=T) n+;flag=1;else if(queuefront) queuerear=queuefront-lchild;rear=(rear+1)%MAXSIZE;queuerear=queuefront-rchild;rear=(rear+1)%MAXSIZE;if(flag)queuerear=T;rear=(rear+1)%MAXSIZE;front=(front+1)%MAXSIZE;printf(n元素%c不存在。n,c);return -1;/*主函数*/int main() BiTreeLink T; int c=0; char x; printf(请输入节点n); CreateBiTree(&T); printf(n先序:); PreOrderTraverse(T); printf(n请输入节点：); getchar(); printf(n请输入要查询的字符：); scanf(%c,&x); printf(n所在层次%3dnn,CengciTree(T,x); system(pause); return 0; 3、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。#include stdio.h#include stdlib.h#include string.h/*二叉链树的类型定义*/typedef struct Infochar name20;/姓名char date11;/生日char phone12;/电话char StudentNum11;/学号DataType;typedef struct Node DataType data; struct Node *left,*right; BTNode, *PBTNode,*BiTree;/*插入（左孩子）*/PBTNode InsertLeft(PBTNode T,DataType x) PBTNode p; if(!T) return NULL; if(T-left =NULL) p=(PBTNode)malloc(sizeof(BTNode);p-data=x;p-left =NULL;p-right =NULL;T-left =p;return p; return NULL;/*插入（右孩子）*/PBTNode InsertRight(PBTNode T,DataType x) PBTNode p; if(!T) return NULL; if(T-right =NULL) p=(PBTNode)malloc(sizeof(BTNode);p-data=x;p-left =NULL;p-right =NULL;T-right =p;return p; return NULL;/*插入*/void InsertChild(PBTNode T,DataType x)if (T-left=NULL & T-right=NULL & !strcmp(T- , 无)T-data=x;else if (InsertLeft(T,x) return;elseif (InsertRight(T,x) return;else InsertChild(T-left ,x);/*建立二叉树*/void CreateBiTree(DataType *items,BiTree *T) int i; printf(本程序通过预置数组建立二叉树n); (*T)=(PBTNode)malloc(sizeof(BTNode); (*T)-left=NULL; (*T)-right=NULL; (*T)-data=items0; for(i=1;,T-data.StudentNum,T-data.date,T-data.phone); PreOrderTraverse(T-left); PreOrderTraverse(T-right); /*查找二叉树*/PBTNode SearchTree(BiTree T,char *ch)PBTNode flag=NULL;if (T)if(!strcmp(T-,ch)printf(nt%st%st%st%snn,T-,T-data.StudentNum,T-data.date,T-data.phone);flag=T; return flag;else flag=SearchTree(T-left,ch);if(flag) return flag;elseflag=SearchTree(T-right,ch);return flag;/*查找父亲节点*/PBTNode SearchFather(PBTNode r,BiTree T,int *flag) PBTNode p=NULL; if(T) if(T-left=r)(*flag)=0; p=T;return p;/flag=0表示左孩子的父亲 else if(T-right=r) (*flag)=1; p=T;return p; else p=SearchFather(r,T-left,flag); if(p) return p; else p=SearchFather(r,T-right,flag); return p;/*修改二叉树*/void ModifyTree(BiTree T) char ch20,Mod12; PBTNode ModifyNode; int caseflag; printf(请输入要修改信息的姓名:); scanf(%s,ch); ModifyNode=SearchTree(T,ch); if(!ModifyNode) printf(n查找的姓名不存在n); else while(1) printf(n1.修改生日n2.修改电话n3.修改学号n4.不修改n); scanf(%d,&caseflag); switch(caseflag) case 1: printf(请输入修改后的生日:); scanf(%s,Mod); strcpy(ModifyNode-data.date,Mod); break; case 2: printf(请输入修改后的电话:); scanf(%s,Mod); strcpy(ModifyNode-data.phone,Mod); break; case 3: printf(请输入修改后的学号:); scanf(%s,Mod); strcpy(ModifyNode-data.StudentNum,Mod); break; case 4:return; /*删除二叉树*/void DeleteTree(BiTree T) char ch20; PBTNode DelNodeFather,DelNode,p,q;int flag; printf(请输入要删除信息的姓名:); scanf(%s,ch); DelNode=SearchTree(T,ch); if(!DelNode) printf(n查找的姓名不存在n); elseif (T=DelNode)if(DelNode-left)p=DelNode-left; while(p-right)p=p-right; p-right=DelNode-right; q=DelNode-left; *DelNode=*q; q-left=NULL; q-right=NULL; free(q);else if(DelNode-right)q=DelNode-right;*DelNode=*q;q-left=NULL;q-right=NULL;free(q);else strcpy(T-, 无);strcpy(T-data.StudentNum, 无);strcpy(T-data.date, 无);strcpy(T-data.phone, 无);else DelNodeFather=SearchFather(DelNode,T,&flag); if(DelNode-left)p=DelNode-left; while (p-right)p=p-right; p-right=DelNode-right; q=DelNode-left; *DelNode=*q; q-left=NULL; q-right=NULL; free(q);elseq=DelNode-right;if(q)*DelNode=*q;q-left=NULL;q-right=NULL;free(q);elsefree(DelNode);if (flag=0) DelNodeFather-left=NULL;if (flag=1) DelNodeFather-right=NULL;printf(n删除指定姓名后的同学录n);/*主函数*/void main() BiTree T; Int caseflag;char ch20; DataType x=周五,1983-05-050807011005; DataType items4= 赵一,1979-01-010807011001, 钱二,1980-02-020807011002, 孙三,1981-03-030807011003, 李四,1982-04-040807011004; CreateBiTree(items,&T); printf(n先序遍历:n); PreOrderTraverse(T); while(1) printf(n1.按姓名查找n2.新增同学信息n3.修改同学信息n4.删除同学信息n5.退出nn); scanf(%d,&caseflag); switch(caseflag) case 1:printf(请输入要查找的姓名:); scanf(%s,ch); if(!SearchTree(T,ch) printf(n查找的姓名不存在n); break; case 2:printf(n新增:n);InsertChild(T,x);PreOrderTraverse(T);break; case 3:ModifyTree(T);PreOrderTraverse(T);break; case 4:DeleteTree(T);PreOrderTraverse(T);