数据结构课程设计实验报告.doc

设计题目：一 单位员工通讯录管理系统一、 题目要求为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。二、 概要设计本程序通过建立通讯录链表，对员工信息进行记录，并建立一个系统的联系。三、 主要代码及分析这里面关于链表的主要的操作有插入，查询，删除。则这里只列出这几项的主代码。1、通过建立通讯录结构体，对信息进行存储，建立链表，建立信息之间的联系。typedef struct DataType;结构体来存储通讯录中的基本信息typedef struct node DataType data; /*结点的数据域*/struct node *next; /*结点的指针域*/ListNode,*LinkList;2、信息插入操作，将信息查到链表的后面。void ListInsert(LinkList list) /信息插入ListNode *w;w=list-next;while(w-next!=NULL)w=w-next;ListNode *u=new ListNode;u-next=NULL;coutu-data.num;;coutu-data.call;coutu-data.email;coutu-data.phone;w-next=u;w=w-next;3、信息删除操作void ListDelete(LinkList list) /删除ListNode *c1;ListNode *c2;ListNode *c3;c1=list;c2=list;int s=0;char Schax20;cout-endl;coutSchax;while(strcmp(Schax,c1-data.num)s+;c1=c1-next；for(int j=0;jnext;c3=c2-next;c2-next=c3-next;4、查询void Traverse(LinkList list) /查询ListNode *s;s=list-next;int a=0;coutnum;doif(!(strcmp(num,s-data.num)/Q=H，strcmp(Q,H) =0;QH, strcmp(Q,H) = 1;QH, strcmp(Q,H) = -1; cout员工编号：data.numendl;cout员工姓名：endl;cout手机号码：data.callendl;cout员工邮箱：data.emailendl;cout办公室电话号码：data.phonenext!=NULL,s=s-next);if (a=0)cout小凤温馨提示您输入的信息不存在！ch;if(ch=#)T=NULL;return 0;elseif(!(T=(BitNode *)malloc(sizeof(BitNode)cout存储分配失败data=ch;if(CreatBiTree(T-lchild)T-LTag=Link;else T-LTag=Thread;if(CreatBiTree(T-rchild) T-RTag=Link;else T-RTag=Thread;return 1;2、 中序线索遍历二叉树。void InThreading(Bitree p)/中序遍历线索化二叉树，如果一个结点没有左孩子，则将其指向其前驱，如果没有右孩子，则将其指向其后继。if(p!=NULL)InThreading(p-lchild);/左子树线索化if(p-lchild=NULL)/前驱线索p-LTag=Thread;p-lchild=pre;if(pre-rchild=NULL)/后继线索pre-RTag=Thread；pre-rchild=p；pre=p;/保持pre指向p的前驱InThreading(p-rchild);/右子树线索化int InOrderThreading(Bitree &Thrt,Bitree T)/中序遍历线索化二叉树T,并将其中序线索化,Thrt指向头节点Thrt=(Bitree)malloc(sizeof(BitNode);/申请头结点地址if(Thrt=NULL) exit(1);Thrt-LTag=Link;/建立头结点Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指if(T=NULL) Thrt-lchild=Thrt;/若二叉树为空，则左指针回指elseThrt-lchild=T;/头结点指向树的根pre=Thrt;InThreading(T);/中序遍历线索化二叉树pre-rchild=Thrt;/二叉树的最后一个结点的后继结点指向thrt.pre-RTag=Thread;/最后一个结点的线索化Thrt-rchild=pre;return 1;3、 输出各结点前驱和后继Bitree InPre(Bitree p)/前驱，Bitree q;q=p-lchild;/遍历其左子树。if(p-LTag=Thread)/若标志为1，则左链为线索，只是其前驱。return(p-lchild);if(q=NULL)/如果左链为空，则无前驱。return NULL;while(q-RTag=Link)/遍历左子树最后访问的一个结点，即左子树中最右下的结点。q=q-rchild;return (q);/后继Bitree InNext(Bitree p)/遍历右子树时访问的第一个结点。Bitree q;q=p-rchild;/遍历其右子树。if(p-RTag=Thread)return(p-rchild);if(q=NULL)return NULL;while(q-LTag!=Thread)q=q-lchild;return(q);/InNext/输出前驱和后继值函数。int Traverse_Thr(Bitree T)int i=0;Bitree p;p=T-lchild;cout前驱 节点 后继 顶点序号LTag=Link) p=p-lchild;/找中序遍历的第一个点,并输出其前驱和后继。coutdata ;/找其前驱并输出。coutdata ;pointi+;coutdata ;/去找其后继并输出。coutiRTag=Thread&p-rchild!=T)/寻找后继结点，并输出其前驱和后继。p=p-rchild;/p=其右继。coutdata ;coutdata ;pointi+;coutdata ;coutirchild;/whilereturn i;a四、 运行结果及分析cbgfed以先序遍历次序来输入二叉树，#代表其左子树或者右子树为空。五、 设计心得体会通过这次设计，熟悉了线索二叉树的基本理念和算法，铜过深究线索二叉树的图例，进行了算法的编写，很有本题看着挺简单，但是算法写读起来却比较绕，稍微不留神就会出错，所以经过多次修改才得以成功，在算法方面有了很大的提高。设计题目：三宿舍管理查询软件一、 题目要求为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：（1）采用交互工作方式（2）可以增加、删除、修改信息（3）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(选择、快速排序、堆排序等任选一种)(4) 查询 : a.按姓名查询 ;b.按学号查询 ;c按房号查询(5) 打印任一查询结果（可以连续操作）要求：上述查询功能中，学号、房号用折半查找，姓名查找用哈希查找。二、 概要设计建立学生宿舍信息的结构体，对其进行各种操作，学号，房号用折半查找，折半查找则是先找其中间值进行比较，大了则再与前一半比，小了就和后一半比。姓名用哈希查找，哈希查找则需要先对姓名进行转换，用一个数组来记录姓名字符，对其进行查找。排序进行用的是快速排序，每趟过后关键字会把信息分为两半，一半比其小，一半比其大，经过n趟后，就形成了有序的序列。三、 主要代码及分析1、 折半查找/学号折半查找int Search_Bin_num(int num) int low=1,mid,high=student_num; while(low=high) mid=(low+high)/2;if(num=smid.num)/与中间的信息比，相等则直接输出。cout姓名： 学号：smid.num 宿舍：smid.roomendl;return mid;else if(numsmid.num)/如果不相等，小于中间数，则high变。high=mid-1;else low=mid+1;/大于中间数，则low变。cout不存在该学生endl;return 0;2、 哈希查找/哈希表int Hash(int num)return num%(student_num+30);void InitHashTable()for(int i=0;i(student_num+30);i+) =NULLKEY;void InsertHashTable () int addr; char *pstr; for(int i=1;i=student_num;i+) ; pstr=(char *)malloc(sizeof(.length()+1); strcpy(pstr,.c_str(); addr=Hash(pstr0+pstr1);/pstr指代姓名的字符信息。 while(pare(NULLKEY)!=0)/判断哈希表该位置是否为空位，若不是，则进行线性探测。 addr=(addr+1)%(student_num+30); shashaddr=si;/将信息插入哈希表中。 free(pstr); int SearchHash()string name;coutname;int addr;char *pstr;pstr = (char*)malloc(name.length()+1);strcpy(pstr,name.c_str();addr=Hash(pstr0+pstr1);/直接确定索要查找的信息在哈希表中的位置。free(pstr);while(pare(NULLKEY)!=0)if(pare(name)=0)cout姓名：学号：shashaddr.num宿舍：shashaddr.roomendl;return 1;elseaddr=(addr+1)%(student_num+30);cout不存在此学生的信息endl;return 0;3、 快速排序/按学号快速排序int Partition_num(int low,int high)int pivotkey;s0=slow;pivotkey=slow.num;/记录关键字。while(lowhigh)while(low=pivotkey)high-;slow=shigh; /从右向左搜索while(lowhigh&slow.num=pivotkey)low+;shigh=slow;slow=s0;return low;void QSort_num(int low,int high)int pivotloc;if(low=graph1.vexnum-1) int k=1;/初始化从第一个结点开始建立生成树 int kk=0;/记录当前最小权值。 for(int i=1;i=graph1.vexnum;i+)/辅助数组初始化 if(i!=k)closedgei.adjvex=1;closedgei.lowcost=graph1.arcski; closedgek.lowcost=0; for(int j=1;jgraph1.vexnum;j+)/循环找到剩余的n-1个生成树的结点 kk=maxnum;for(i=2;i=graph1.vexnum;i+)/找到当前最小权值 if(closedgei.lowcost!=0) kk=(kkclosedgei.lowcost)?kk:closedgei.lowcost; for(i=2;i=graph1.vexnum;i+)/定位最小权值所在的结点位置 if(closedgei.lowcost=kk) k=i; break; coutgraph1.vexsclosedgek.adjvex,graph1.vexsk权值为：graph1.arcsclosedgek.adjvexk ;/输出信息closedgek.lowcost=0;/标志该结点已被找到for(int m=2;m=graph1.vexnum;m+)/对其他节点的连入结点及最小连入权值进行修改 if(graph1.arcskmclosedgem.lowcost) closedgem.adjvex=k; closedgem.lowcost=graph1.arcskm; coutendl;elsecout输入错误!=graph1.vexnum-1)int acrvisited100;/标记被访问过还是未被访问。未被访问是0.访问过是100.int i,j,k=0;for(i=1;i=graph1.vexnum;+i)for(j=i+1;j=graph1.vexnum;+j)if(graph1.arcsij!=-1)Klusik.R=i;Klusik.RN=graph1.vexsi;Klusik.L=j;Klusik.LN=graph1.vexsj;Klusik.lowcost=graph1.arcsij;+k;int x,y,m,n;/x,y记录当前最小权值的起点和终点。int buf,edf;for(i=0;i=graph1.arcnum;+i)acrvisitedi=0;for(j=0;j=graph1.arcnum;+j)m=1000000;for(i=0;i!=graph1.arcnum;+i)if(Klusii.lowcostm)m=Klusii.lowcost;x=Klusii.R;y=Klusii.L;n=i;buf=find(acrvisited,x);edf=find(acrvisited,y);Klusin.lowcost=1000000;/被访问过的边将其权值掷为最大。if(buf!=edf)acrvisitedx=100;/将被访问过的结点的标志记作100.acrvisitedy=100;coutx,y权值为：m;cout;coutendl;break;四、 运行结果及分析五、 设计心得体会通过这个设计，我掌握了克鲁斯卡尔和普里姆的基本算法，体会到这两种算法的基本理念，并且感受到克鲁斯卡尔的算法适合求边稀疏的网的最小生成树，而普里姆的则适合求一些复杂的网的生成树，两者优缺互补。设计题目：五校园导游咨询一、 题目要求设计一个校园导游程序，为来访的客人提供各种信息查询服务。（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。二、 概要设计以迪杰斯特拉为算法，首先输入一个起点v0，然后在与起点相连的点取出权值最小的一条边，记录该顶点v1，然后再选择与v1相连的权值最小的一条边，顶点为v2，比较若v0-v2有直连的线，则比较v1-v2的权值和v0-v2的权值哪个小，如果前者小，则替换其原来的权值。依此类推，把从起点到其他所有的点的路径都得出来。然后与输入的终点对应的路径输出，变得出了校园导游。三、 主要代码及分析void ShortPath_D(MGraph G,int v0,int vf)/迪杰斯特拉算法int v,w,i,j,min;memset(p,0,sizeof(p);memset(D,0,sizeof(D);/将数组所占内存赋0for(v=1;v10;v+)/初始化。finalv=false;Dv=G.arcsv0v;if(DvINF)pvv0=true;pvv=true;/若pvw为true，则w是v0到v求的的最短路径上的顶点 Dv0=0; finalv0=true; for(i=1;i10;i+)/G.vexnum-1,循环次数 min=INF; for(w=1;w10;w+)/找到与起点最近的点 if(!finalw)/判断w是否已经被加入S集。已经加入过则不再进行以下操作。 if(Dwmin) v=w; min=Dw; finalv=true;/离v0最近的