实习题目一【共享精品-doc】

实习题目一【共享精品-doc】 实习题目一 学生成绩管理系统 【需求规格说明】 学生成绩管理是高等学校教务管理的重要组成部分，主要包括学生注册、考试成绩的录入及修改、成绩的统计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 等等。设计一个系统实现对学生成绩的管理。 【基本要求】 要求系统应具有以下基本功能: (1)学生注册登记; (2)增加、删除某一班级的学生数; (3)成绩录入:输入学生的考试成绩; (4)成绩修改:若输入错误可进行修改; (5)统计分析:对某个班级学生的单科成绩进行统计，求出平均成绩;求出成绩处于指定分数段内的学生人数;求出每个学生一学期各科的平均成绩等; (6)查找:查找某个学生的某门课程成绩，查找某门课程成绩处于指定分数段内的学生名单等等。 (7)打印:打印一个班级学生的单科成绩;打印某一课程成绩处于指定分数段内的学生名单;打印学生在某一学期的成绩 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 单; (8)排序:按照学生成绩的总分排序学生记录。 【算法设计】 (1)设计思想: 本题的核心操作是查询，因为哈希表的查找效率很高，应此在实现该系统的时候考虑到应用哈希表这样一种数据结构. 哈希函数的设计采用除留余数法，解决碰撞冲突采用线性探测在散列的方法。另外考虑到要排序，而且为了实现排序算法的时间复杂度尽可能低，采用了二叉排序树的数据结构解决排序问题。 由于哈希表的关键字项只能有一项，为了实现按学号或按姓名查找和按班级插入和删除学生信息，设计了三个哈希表来实现该学生管理系统，其中学号哈希表存放所有的学生信息，包括学号.姓名.班号.C语言成绩.数学成绩.英语成绩.总分以及平均分，其中学号哈希表的表项关键字为学号;姓名哈希表以学生姓名的ASCII码值为表项关键字，其中该姓名哈希表存放了学生的学号作为索引项;班级哈希表以班号为表项关键字，该班级哈希表用一个数组存放了该班所有学生的学号。 二叉排序树以学生成绩的总分作为关键字项，另外存放了学生的学号与姓名作为索引信息，排序时，将学生的学号，姓名和总分依次插入二叉排序树，按照成绩总分排序只要中序遍历此二叉树便可得到。 实现按学号和按姓名查找，并且实现三个表的动态的修改即(插入和删除)，当插入(删除)学生信息到学号哈希表时，先到学号哈希表去查找学生的相关信息，未找到时(找到时)就在学号哈希表中插入(删除)该学生的所有信息，同时也要把学生的信息反映到姓名哈希表和班级哈希表中。当从姓名哈希表插入(删除)学生信息时，计算该学生姓名的ASCII码值作为关键字到姓名哈希表中时，到哈希表中去对应信息，如果找不到(找到)就在姓名哈希表中插入(删除)姓名的ASCII码关键字的值，同时在姓名哈希表中插入(删除)该学生的学号。当从班级哈希表中插入(删除)学生信息时，把班号作为关键字到班级哈希表中去查找对应的信息，如果找不到就提示不存在该班级，找到该班号就在班号哈希表的班级数组中插入该学生的学号，增加该班级的学生人数。 三个哈希表及二叉树之间的对应关系见下图: 数据结构课程设计 学号哈希表 关键字项 数据项 学号 班号 姓 名 其它信息 2006 0010 huang 2007 0008 kai 2008 0002 tao 2009 0003 liu 姓名哈希表 2010 0004 zhang 班号哈希表 关键字 学号 2011 0009 li 班编号 zhang 2025 2012 0002 wang 0005 wang 2027 2013 0006 chen 0008 yang 2030 2014 0008 wen 0002 song 2031 2015 0007 yang 0010 kai 2022 2016 0006 song 。。。。 huang 2021 2017 0008 jiang 0003 wen 2029 2018 0005 xu 0006 。。。 。。。 2019 0006 ren 0001 ren 2034 2020 0010 hu 0007 lai 2014 。。。。 。。。。 。。。 jiang 2032 。。。。 。。。。 。。。 xun 2018 2006 0007 lai 2007 0006 lei 2008 0004 long 2009 0002 jun 2010 0001 xun 2011 0003 mei 2012 0001 ling 2013 0002 ri 2014 二叉排序树 2018 关键字 数据项 2010 总分 学号 姓名 2016 256 2006 lai 2017 258 2009 jun 2018 260 2012 wang 2040 267 2013 ri 2104 268 2011 mei 2205 269 2010 xun 2030 。。。 。。。 。。。 2031 - 1 - 280 2015 yang 2034 2108 2109 2204 2008.7 数据结构课程设计 (2)数据结构设计: /*****************学号哈希表*****************/ typedef struct { DataType number;//学号 char name[10];//姓名 int classnumber;//班号 int cgrade;//语言成绩 int mgrade;//数学成绩 int egrade;//英语成绩 DataType total;//总分 float ave;//平均分 kindofitem info;//当前状态(是否被访问的标志) }Hashitemnum; typedef struct { Hashitemnum *ht;// 学号哈希表数组 int tablesize;//表长 int currentsize;//当前表的长度 }Hashtablenum;//建立的关键字为学号的学号哈希表 /*****************姓名哈希表*****************/ typedef struct { DataType na;//存放姓名的ascii码的关键字(相当于索引项) int number;//班号 kindofitem info;//当前状态 }Hashitemname; typedef struct { Hashitemname *ht;// 姓名哈希表数组 int tablesize; int currentsize; }Hashtablename;//建立的关键字为姓名的姓名哈希表 /*****************班级哈希表*****************/ typedef struct { DataType classnumber;//存放班号的关键字 int number[50];//存放本班学生学号的数组(相当于索引项) int size;//本班学生的人数 kindofitem info; //当前状态 }Hashitemclassnumber; typedef struct - 2 - 数据结构课程设计 { Hashitemclassnumber *ht;// 班级哈希表数组 int tablesize; int currentsize; }Hashtableclassnumber;//建立的关键字为班号的班级哈希表 /*************二叉排序树的数据结构**************/ typedef struct tree { DataType data;//关键字域 int number;//学号 char name[10];//姓名 struct tree *leftchild;//左孩子 struct tree *rightchild;//右孩子 }bitree;//二叉树 (3)详细设计说明: 三个哈希表的总体设计:结构体哈希表由哈希表数组，数组个数和当前哈希表项个数三部分组成，其中哈希表数组中每个表项的数据类型是结构体HashItem。结构体HashItem由数据元素和表项状态两部分组成，其中数据元素仅包括一个关键字域，表项状态的数据类型为枚举类型，表项状态有Empty，Active和Deleted三种状态，分别表示表项的空，已占用和被删除三种状态。 数据结构定义如下:哈希表项包括三个，一个是数据元素关键字项，一个是元素的其它信息，还有一个是元素项的当前状态(info).数据元素的当前状态有三种:空，占用(或称活动)和删除，因此，需要定义一个有三个取值Empty，Active和Deleted的枚举类型KindofItem。 存放三个哈希表的数组采用动态数组，初始化时哈希表的表的表长采用总人数的1.5倍。 本题的核心算法是哈希表的插入，查找和删除。其中，插入和删除操作首先需要查找数据元素是否在哈希表中存在。查找函数共有三种情况:查找到，返回数据元素的哈希地址(值为正);未查找到，返回一个负值(插入操作可在哈希表的该返回值的绝对值位置插入数据元素);未找到，且哈希表已满无法插入，此时返回为-tablesize. 插入函数首先调用查找函数，返回值(设为i)为负(说明数据原素不存在)且返回值不等于 - tablesize(说明哈希表未满)时，在哈希表的-i位置插入数据元素。 【函数模块】 create(Hashitemnum*num,int &m,DataType a[],int b[]) Initiatenum(Hashtablenum*hash,int msize) Initiatenumber(Hashtableclassnumber*hash,int msize) Findnum(Hashtablenum *hash,DataType x) Insertnum(Hashtablenum *hash,Hashitemnum*num) Findname(Hashtablename *hash,char p[]) Deletenum(Hashtablenum *hashnum,DataType x,Hashtablename *hashname) Insertname(Hashtablename *hash,char p[],int number) Deletename(Hashtablename *hashname,char *p,Hashtablenum *hashnum,int&m) Findnumber(Hashtableclassnumber *hash,DataType x) Insertclassnumber(Hashtableclassnumber *hash,Hashtablenum *hashnum,DataType x,int b[]) Deletenumber(Hashtableclassnumber *hash,int i,int number) Add(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) Deletebynum(Hashtableclassnumber*hashnumber，Hashtablenum*hashnum,Hashtablename*hashna - 3 - 2008.7 数据结构课程设计 me);Deletebyname(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) Delete(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) xiugai(Hashtablenum *hashnum,Hashtablename *hashname) Tongji(Hashtableclassnumber *hashnumber,Hashtablenum *hashnum,Hashtablename *hashname) chazhao(Hashtableclassnumber*hashnumber,Hashtablenum*hashnum,Hashtablename*hashname,Ha shitemnum*num,int m) print(Hashtableclassnumber*hashnumber,Hashtablenum*hashnum,Hashtablename*hashname,Hash itemnum*num) printmidan(Hashtablenum *hashnum,int b[],int&h) insert(bitree **root,Hashitemnum item) Traverse(bitree*root) 程序执行中函数调用关系和流程如下: 学生信息的登记 Initiatenum() Create() 与成绩录入 Initiatename() Initiatenumber() Insertnum () 完成对三个表 Insertname () 的创建 Insertnum () ; Insertname (); Insertclassnumber()Insertclassnumber(); ((( () 增加学生记录 Add() Deletebynum (); Findnumber() 删除学生记录 Delete() Deletebyname() Deletenumber() Deletename() xiugai() Findnumber();Findnum(); 修改学生记录 Deletenum() 统计学生记录 tongji() Findnumber();Findnum() 查找学生记录 chazhao() Findname();Findnum(); 打印学生记录 print() insert(bitree**root,Hashitemnm item) Traverse(bitree*root) 排序学生记录 Paixu() 【测试数据】 *****************欢迎使用学生成绩管理系统************************** *********************** 菜 单*********************** * a 学生登记注册与学生成绩录入 b 增加某一班的学生记录 * * c 删除某一班的学生记录 d 修改学生成绩 * * e 统计学生记录 f 查找学生记录 * * g 打印学生记录 h 排序学生记录 * * j 退出 * *************************************************** - 4 - 数据结构课程设计 请输入全校学生的班级个数:25 请输入您要进行的操作:a 请输入学生的信息: 学生的学号:2008 学生的姓名:huang 该学生所在的班号:1 学生的数学成绩:84 学生的英语成绩:85 学生的C语言成绩:86 继续输入?(Y/N)Y 学生的学号:2006 学生的姓名:lei 该学生所在的班号:1 学生的数学成绩:85 学生的英语成绩:86 学生的C语言成绩:87 继续输入?(Y/N)Y 学生的学号:2010 学生的姓名:kai 该学生所在的班号:2 学生的数学成绩:84 学生的英语成绩:85 学生的C语言成绩:96 继续输入?(Y/N)Y 学生的学号:2012 学生的姓名:wei 该学生所在的班号:2 学生的数学成绩:84 学生的英语成绩:85 学生的C语言成绩:87 继续输入?(Y/N)N 学生的信息正在被录入之中.......请稍后 请输入您要进行的操作:1 请输入您要进行的操作:2040 请输入您要进行的操作:you 请输入您要进行的操作:b 请输入您要增加的学生的所在班级的班号:1 请输入您要增加的学生的学号:2040 请输入您要增加的学生姓名:you 学生的数学成绩:88 学生的英语成绩:84 学生的C语言成绩:85 该学生已成功增加到信息系统中! 继续输入?(Y/N)N - 5 - 2008.7 数据结构课程设计 请输入您要进行的操作:c 按学号删除 0 按姓名删除 1 请选择删除方式0/1:0 请输入您要删除的学生的所在班级的班号:1 请输入您要删除的学生的学号:2008 该学生已被成功删除! 请输入您要进行的操作:d 按姓名修改 0 按学号修改 1 请选择修改方式:0 请输入要修改的学生的姓名:you 请输入您要修改的学生的某一项的成绩: 修改数学成绩 0 修改英语成绩 1 修改C语言成绩 2 请选择修改方式:0 请修改后的数学成绩:99 修改成功! 请输入您要进行的操作:e 请输入您要统计的学生的所在班级的班号:1 统计数学成绩 0 统计英语成绩 1 统计C语言成绩 2 请输入您要统计哪一项的成绩:0 请输入您要查询的统计的分数段max~min: 请输入max的值:99 请输入min的值:68 NO.1学生的平均成绩是92.00 处于99~68之间的学生人数是:2 请输入您要进行的操作:f 按姓名查找 0 按学号查找 1 请选择查找方式:0 请输入要查找的学生的姓名:you 查找数学成绩 0 查找英语成绩 1 查找C语言成绩 2 请选择查找方式:0 该学生的数学成绩的是:99 查找指定的分数段的数学成绩 0 查找指定的分数段的英语成绩 1 查找指定的分数段的C语言成绩 2 请选择查找方式:0 - 6 - 数据结构课程设计 请输入您要查询的数学成绩指定的分数段max1~min1 请输入max1的值:99 请输入min1的值:68 成绩指定的分数段99~68的学生名单是: kai you lei wei 请输入您要进行的操作:g 请输入您要打印的学生的所在班级的班号:1 请输入您要打印哪一项的成绩: 打印数学成绩 0 打印英语成绩 1 打印C语言成绩 2 请选择打印方式:0 学号 姓名 数学 2006 lei 85 2040 you 99 学号 姓名 数学 英语 C语言 2010 kai 84 85 96 2040 you 99 84 85 2006 lei 85 86 87 2012 wei 84 85 87 请输入您要进行的操作:h 2012 wei 256 2006 lei 258 2010 kai 265 2040 you 268 请输入您要进行的操作:j Press any key to continue 【调试报告】 1、开始时，增加学生记录时可以增加成功，但是到后来在查询的时候却显示该学生记录不存在， 设置断点调试后，发现查找函数的状态记录不正确，修改后实现了查找成功。 2、在打印学生的姓名时开始打印出来的姓名是乱码，后来调试进行跟踪发现字符串末尾没有添 加结束符号0，添加后打印成功。 3、用二叉排序树对学生信息进行排序时发现，总分必须作为关键字项，因此又将学号哈希表的 总分项改成了DataType类型，成功将问题解决。 【用户手册】 根据提示输入相应的学生信息即可，可以任意输入班级个数，学生人数和添加与删除学生信息。 【附录】 代码 清单 安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载 : #include "stdio.h" #include "stdlib.h" - 7 - 2008.7 数据结构课程设计 #include "string.h" typedef int keytype; #define Max 1000; typedef enum { Empty, Active, Deleted }kindofitem; typedef struct { keytype key; }DataType; typedef struct { DataType number; char name[10]; int classnumber; int cgrade; int mgrade; int egrade; DataType total; float ave; kindofitem info; }Hashitemnum; typedef struct { DataType na; char name[10]; int number; kindofitem info; }Hashitemname; typedef struct { DataType classnumber; int number[50]; int size; kindofitem info; }Hashitemclassnumber; typedef struct { Hashitemnum *ht; int tablesize; int currentsize; }Hashtablenum; typedef struct { Hashitemname *ht; - 8 - 数据结构课程设计 int tablesize; int currentsize; }Hashtablename; typedef struct { Hashitemclassnumber *ht; int tablesize; int currentsize; }Hashtableclassnumber; typedef struct tree { DataType data; int number; char name[10]; struct tree *leftchild; struct tree *rightchild; }bitree; void create(Hashitemnum*num,int &m,DataType a[],int b[]) { int i=0; char flag='y'; printf("\n请输入学生的信息:\n"); while(flag=='y'||flag=='Y') { printf("学生的学号:"); scanf("%d",&num[i].number.key); b[i]=num[i].number.key; printf("学生的姓名:"); scanf("%s",num[i].name); printf("该学生所在的班号:"); scanf("%d",&num[i].classnumber); a[i].key=num[i].classnumber; printf("学生的数学成绩:"); scanf("%d",&num[i].mgrade); printf("学生的英语成绩:"); scanf("%d",&num[i].egrade); printf("学生的C语言成绩:"); scanf("%d",&num[i].cgrade); i++; printf("继续输入?(Y/N)"); scanf("%s",&flag); } m=i; - 9 - 2008.7 数据结构课程设计 } void copy(char p[],char q[]) { int i=0; while(1) { q[i]=p[i]; if(p[i]==0) break; else i++; } } int Initiatenum(Hashtablenum*hash,int msize) { hash->tablesize=msize; hash->ht=(Hashitemnum*)malloc(sizeof(Hashitemnum)*msize); if(hash->ht==NULL) return 0 ; else { hash->currentsize=0; return 1; } } int Initiatename(Hashtablename*hash,int msize) { hash->tablesize=msize; hash->ht=(Hashitemname*)malloc(sizeof(Hashitemname)*msize); if(hash->ht==NULL) return 0 ; else { hash->currentsize=0; return 1; } } int Initiatenumber(Hashtableclassnumber*hash,int msize) { hash->tablesize=msize; hash->ht=(Hashitemclassnumber*)malloc(sizeof(Hashitemclassnumber)*msize); if(hash->ht==NULL) return 0 ; - 10 - 数据结构课程设计 else { hash->currentsize=0; return 1; } } int Findnum(Hashtablenum *hash,DataType x) { int i=x.key%hash->tablesize; int j=i; while(hash->ht[j].info==Active&&hash->ht[j].number.key!=x.key) { j=(j+1)%hash->tablesize; if(j==i) return -hash->tablesize; } if(hash->ht[j].info==Active) return j; else return -j; } int Insertnum(Hashtablenum *hash,Hashitemnum*num) { int i=Findnum(hash,num->number); if(i>0) return 0; else if(i!=-hash->tablesize) { hash->ht[-i].number=num->number; copy(num->name,hash->ht[-i].name); hash->ht[-i].classnumber=num->classnumber; hash->ht[-i].mgrade=num->mgrade; hash->ht[-i].egrade=num->egrade; hash->ht[-i].cgrade=num->cgrade; hash->ht[-i].info=Active; hash->currentsize++; return 1; } else return 0; } int Findname(Hashtablename *hash,char p[]) { DataType x; x.key=0; int k=0; - 11 - 2008.7 数据结构课程设计 while(1) { x.key+=(int)(p[k]); k++; if(p[k]==0) break; } int i=x.key%hash->tablesize; int j=i; while(hash->ht[j].info==Active&&hash->ht[j].na.key!=x.key) { j=(j+1)%hash->tablesize; if(j==i) return -hash->tablesize; } if(hash->ht[j].info==Active) return j; else return -j; } int Findname1(Hashtablename *hash,char p[]) { DataType x; x.key=0; int k=0; while(1) { x.key+=(int)(p[k]); k++; if(p[k]==0) break; } int i=x.key%hash->tablesize; int j=i; while(hash->ht[j].na.key!=x.key) { j=(j+1)%hash->tablesize; if(j==i) return -hash->tablesize; } if(hash->ht[j].info==Active) return j; else return -j; } int Deletenum(Hashtablenum *hashnum,DataType x,Hashtablename *hashname) - 12 - 数据结构课程设计 { int i=Findnum(hashnum,x); if(i>=0) { int j=Findname(hashname,hashnum->ht[i].name); if(j>=0) { hashname->ht[j].info=Deleted; hashname->currentsize--; } hashnum->ht[i].info=Deleted; hashnum->currentsize--; return 1; } else return 0; } int Insertname(Hashtablename *hash,char p[],int number) { DataType x; x.key=0; int j=0; while(1) { x.key+=(int)(p[j]); j++; if(p[j]==0) break; } int i=Findname(hash,p); if(i>0) return 0; else if(i!=-hash->tablesize) { hash->ht[-i].na=x; hash->ht[-i].number=number; hash->ht[-i].info=Active; hash->currentsize++; return 1; } else return 0; } int Deletename(Hashtablename *hashname,char *p,Hashtablenum *hashnum,int&m) { int i=Findname(hashname,p); - 13 - 2008.7 数据结构课程设计 if(i>=0) { DataType x; x.key=hashname->ht[i].number; x.key=m; int j=Findnum(hashnum,x); if(j>=0) { hashnum->ht[j].info=Deleted; hashnum->currentsize--; } hashname->ht[i].info=Deleted; hashname->currentsize--; return 1; } else return 0; } int Findnumber(Hashtableclassnumber *hash,DataType x) { int i=x.key%hash->tablesize; int j=i; while(hash->ht[j].info==Active&&hash->ht[j].classnumber.key!=x.key) { j=(j+1)%hash->tablesize; if(j==i) return -hash->tablesize; } if(hash->ht[j].info==Active) return j; else return -j; } int Insertclassnumber(Hashtableclassnumber *hash,Hashtablenum *hashnum,DataType x,int b[]) { int j=0,k=0,m; DataType y; int i=Findnumber(hash,x); if(i>0) return 0; else if(i!=-hash->tablesize) { hash->ht[-i].classnumber=x; for(j=0;b[j]!=-1;j++) { - 14 - 数据结构课程设计 y.key=b[j]; m=Findnum(hashnum,y); if(m>=0) { if(hashnum->ht[m].classnumber==x.key) { hash->ht[-i].number[k]=b[j]; k++; } } } hash->ht[-i].size=k; hash->ht[-i].info=Active; hash->currentsize++; return 1; } else return 0; } void Insertclassnumber1(Hashtableclassnumber *hash,Hashtablenum *hashnum,DataType x,int b[]) { int j=0,k=0,m,h; DataType y; int i=Findnumber(hash,x); if(i>=0) { h=hash->ht[i].size-1; for(j=0;b[j]!=-1;j++) { y.key=b[j]; m=Findnum(hashnum,y); if(m>=0) { if(hashnum->ht[m].classnumber==x.key) { hash->ht[i].number[h]=b[j]; h++; k++; } } } hash->ht[i].size+=k-1; hash->ht[-i].info=Active; hash->currentsize++; - 15 - 2008.7 数据结构课程设计 return 1; } else return 0; } int Deletenumber(Hashtableclassnumber *hash,int i,int number) { int j=0; int k; int i=Findnumber(hash,x); if(i>=0) { for(j=0;jht[i].size;j++) { if(hash->ht[i].number[j]==number) break; } for(k=j;kht[i].size;k++) hash->ht[i].number[k]=hash->ht[i].number[k+1]; hash->ht[i].size--; return 1; } else return 0; } void Add(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) { int i,n,j=0,k; Hashitemnum num; DataType x1; int b[50]; for(k=0;k<50;k++) b[k]=-1; char flag='y'; while(flag=='y'||flag=='Y') { printf("请输入您要增加的学生的所在班级的班号:"); scanf("%d",&n); x1.key=n; num.classnumber=n; i=Findnumber(hashnumber,x1); if(i<0) printf("对不起，该班号不存在"); if(i>=0) - 16 - 数据结构课程设计 { hashnumber->ht[i].size++; printf("请输入您要增加的学生的学号:"); scanf("%d",&num.number); b[j]=num.number.key; printf("请输入您要增加的学生姓名:"); scanf("%s",num.name); printf("学生的数学成绩:"); scanf("%d",&num.mgrade); printf("学生的英语成绩:"); scanf("%d",&num.egrade); printf("学生的C语言成绩:"); scanf("%d",&num.cgrade); Insertnum(hashnum,&num); Insertname(hashname,num.name,num.number.key); //Deletenum(hashnum,num.number,hashname); printf("该学生已成功增加到信息系统中!\n"); printf("继续输入?(Y/N)"); scanf("%s",&flag); j++; } } Insertclassnumber1(hashnumber,hashnum,x1,b); } void Deletebynum(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) { int n,m; DataType x1,x2; printf("请输入您要删除的学生的所在班级的班号:"); scanf("%d",&n); x1.key=n; printf("请输入您要删除的学生的学号:"); scanf("%d",&m); x2.key=m; int i=Findnumber(hashnumber,x1); if(i<0) printf("对不起，该学生不存在"); else if(i>=0) { //hashnumber->ht[i].size--; Deletenum(hashnum,x2,hashname); Deletenumber(hashnumber,i,m); printf("该学生已被成功删除!\n"); - 17 - 2008.7 数据结构课程设计 } } void Deletebyname(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) { int n,m; char p[10]; DataType x; printf("请输入您要删除的学生的所在班级的班号:\n"); scanf("%d",&n); x.key=n; printf("请输入您要删除的学生姓名:"); scanf("%s",&p); int i=Findnumber(hashnumber,x); if(i<0) printf("对不起，该学生不存在"); else if(i>=0) { hashnumber->ht[i].size--; Deletename(hashname,p,hashnum,m); Deletenumber(hashnumber,i,m); printf("该学生已被成功删除!"); } } void Delete(Hashtableclassnumber *hashnumber, Hashtablenum *hashnum,Hashtablename *hashname) { int select; printf("按学号删除 0\n"); printf("按姓名删除 1\n"); printf("请选择删除方式0/1:"); scanf("%d",&select); if(select==0) Deletebynum(hashnumber,hashnum,hashname); if(select==1) Deletebyname(hashnumber,hashnum,hashname); } void xiugai(Hashtablenum *hashnum,Hashtablename *hashname) { int select1,select2,num,i,k; int math,english,c; char p[10]; printf("按姓名修改 0\n"); printf("按学号修改 1\n"); - 18 - 数据结构课程设计 printf("请选择修改方式:"); scanf("%d",&select1); if(select1==0) { DataType x; printf("请输入要修改的学生的姓名:"); scanf("%s",p); k=Findname1(hashname,p); x.key=hashname->ht[k].number; i=Findnum(hashnum,x); } if(select1==1) { DataType x; printf("请输入要修改的学生的学号"); scanf("%d",num); x.key=num; i=Findnum(hashnum,x); } if(i<0) printf("对不起，该学生不存在"); else if(i>=0) { printf("请输入您要修改的学生的某一项的成绩:\n"); printf("修改数学成绩 0\n"); printf("修改英语成绩 1\n"); printf("修改C语言成绩 2\n"); printf("请选择修改方式:"); scanf("%d",&select2); if(select2==0) { printf("请修改后的数学成绩:"); scanf("%d",&math); hashnum->ht[i].mgrade=math; } else if(select2==1) { printf("请修改后的英语成绩:"); scanf("%d",&english); hashnum->ht[i].egrade=english; } else if (select2==2) { printf("请修改后的C语言成绩:"); - 19 - 2008.7 数据结构课程设计 scanf("%d",&c); hashnum->ht[i].cgrade=c; } printf("修改成功!\n"); } } void Tongji(Hashtableclassnumber *hashnumber,Hashtablenum *hashnum,Hashtablename *hashname) { int j,n,i,select2,zhiding=0; int max,min; DataType x; float sum=0.0; printf("请输入您要统计的学生的所在班级的班号:"); scanf("%d",&n); x.key=n; i=Findnumber(hashnumber,x); if(i>=0) { printf("\n"); printf("统计数学成绩 0\n"); printf("统计英语成绩 1\n"); printf("统计C语言成绩 2\n"); printf("请输入您要统计哪一项的成绩:"); scanf("%d",&select2); printf("请输入您要查询的统计的分数段max~min:\n"); printf("请输入max的值:"); scanf("%d",&max); printf("请输入min的值:"); scanf("%d",&min); if(select2==0) { for(j=0;jht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; int k=Findnum(hashnum,x1); if(k>=0&&hashnum->ht[k].classnumber==n) { sum+=hashnum->ht[k].mgrade; hashnum->ht[k].total.key=hashnum->ht[k].mgrade+hashnum ->ht[k].egrade+hashnum->ht[k].mgrade; hashnum->ht[k].ave=(float)(hashnum->ht[k].total.key/3); if(hashnum->ht[k].mgrade>=min&&hashnum->ht[k].mgrade<=max) - 20 - 数据结构课程设计 zhiding++; } } sum=sum/hashnumber->ht[i].size; printf("NO.%d学生的平均成绩是%.2f",n,sum); printf("\n"); printf("处于%d~%d之间的学生人数是:%d",max,min,zhiding); printf("\n"); } else if(select2==1) { for(j=0;jht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; int k=Findnum(hashnum,x1); if(k>=0) { sum+=hashnum->ht[k].egrade; hashnum->ht[k].total.key=hashnum->ht[k].mgrade+hashnum->ht[k].egrade+hash num->ht[k].mgrade; hashnum->ht[k].ave=(float)(hashnum->ht[k].total.key/3); if(hashnum->ht[k].egrade>=min&&hashnum->ht[k].egrade<=max) zhiding++; } } sum=sum/hashnumber->ht[i].size; printf("NO.%d学生的平均成绩是%.2f",n,sum); printf("\n"); printf("处于%d~%d之间的学生人数是:%d",max,min,zhiding); printf("\n") } else if (select2==2) { for(j=0;jht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; int k=Findnum(hashnum,x1); if(k>=0) { sum+=hashnum->ht[k].cgrade; - 21 - 2008.7 数据结构课程设计 hashnum->ht[k].total.key=hashnum->ht[k].mgrade+hashnum->ht[k].egrade+hash num->ht[k].mgrade; hashnum->ht[k].ave=(float)(hashnum->ht[k].total.key/3); if(hashnum->ht[k].cgrade>=min&&hashnum->ht[k].cgrade<=max) zhiding++; } } sum=sum/hashnumber->ht[i].size; printf("NO.%d学生的平均成绩是%.2f",n,sum); printf("\n"); printf("处于%d~%d之间的学生人数是:%d",max,min,zhiding); printf("\n") } } } void chazhao(Hashtableclassnumber *hashnumber,Hashtablenum *hashnum,Hashtablename *hashname,Hashitemnum*num,int m) { int select1, select2,i,j,k,n; int max1,min1; Hashitemnum nu[1000]; char p[10]; printf("按姓名查找 0\n"); printf("按学号查找 1\n"); printf("请选择查找方式:"); scanf("%d",&select1); if(select1==0) { printf("请输入要查找的学生的姓名:"); scanf("%s",p); i=Findname1(hashname,p); if(i<0) printf("对不起，该学生不存在"); else if(i>=0) { DataType x; x.key=hashname->ht[i].number; j=Findnum(hashnum,x); } if(j<0) printf("对不起，该学生不存在"); else if(j>=0) - 22 - 数据结构课程设计 { printf("查找数学成绩 0\n"); printf("查找英语成绩 1\n"); printf("查找C语言成绩 2\n"); printf("请选择查找方式:"); scanf("%d",&select2); if(select2==0) printf("该学生的数学成绩的是:%d",hashnum->ht[j].mgrade); printf("\n"); if(select2==1) printf("该学生的英语成绩的是:%d",hashnum->ht[j].egrade); printf("\n"); if(select2==2) printf("该学生的C语言成绩的是:%d",hashnum->ht[j].cgrade); printf("\n"); } } if(select1==1) { DataType x; printf("请输入要查找的学生的学号:"); scanf("%d",&n); x.key=n; i=Findnum(hashnum,x); if(i<0) printf("对不起，该学生不存在"); else if(i>=0) { printf("查找数学成绩 0\n"); printf("查找英语成绩 1\n"); printf("查找C语言成绩 2\n"); printf("请选择查找方式:"); scanf("%d",&select2); if(select2==0) printf("该学生的数学成绩的是:%d",hashnum->ht[i].mgrade); else if(select2==1) printf("该学生的英语成绩的是:%d",hashnum->ht[i].egrade); else if(select2==2) printf("该学生的C语言成绩的是:%d",hashnum->ht[i].cgrade); } } printf("查找指定的分数段的数学成绩 0\n"); printf("查找指定的分数段的英语成绩 1\n"); printf("查找指定的分数段的C语言成绩 2\n"); - 23 - 2008.7 数据结构课程设计 printf("请选择查找方式:"); scanf("%d",&select2); if(select2==0) { printf("请输入您要查询的数学成绩指定的分数段max1~min1\n"); printf("请输入max1的值:"); scanf("%d",&max1); printf("\n"); printf("请输入min1的值:"); scanf("%d",&min1); printf("\n"); for(k=0,i=0;i<40;i++) { if(hashnum->ht[i].info==Active) { if(hashnum->ht[i].mgrade>=min1&&hashnum->ht[i].mgrade<=max1) nu[k]=hashnum->ht[i]; k++; } } } if(select2==1) { printf("请输入您要查询的英语成绩指定的分数段max~min\n"); printf("请输入max1的值:"); scanf("%d",&max1); printf("\n"); printf("请输入min1的值:"); scanf("%d",&min1); printf("\n"); //hash->ht[-i].info=Active; for(k=0,i=0;i<40;i++) { if(hashnum->ht[i].info==Active) { if(hashnum->ht[i].egrade>=min1&&hashnum->ht[i].egrade<=max1) nu[k]=hashnum->ht[i]; k++; } } } if(select2==2) - 24 - 数据结构课程设计 { printf("请输入您要查询的C语言成绩指定的分数段max1~min1:\n"); printf("请输入max1的值:"); scanf("%d",&max1); printf("\n"); printf("请输入min1的值:"); scanf("%d",&min1); printf("\n"); for(k=0,i=0;iht[i].info==Active)//hashnum->ht[k].number { if(hashnum->ht[i].cgrade>=min1&&hashnum->ht[i].cgrade<=max1) nu[k]=hashnum->ht[i]; k++; } } } printf("成绩指定的分数段%d~%d的学生名单是:\n",max1,min1); for(i=0;iht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; k=Findnum(hashnum,x1); if(k>=0) { printf("%-10d%s%4d",hashnum->ht[k].number,hashnum->ht[k].name,hashnum->h t[k].mgrade); printf("\n"); } } } else if(select2==1) { printf("学号 姓名 英语"); printf("\n"); for(j=0;jht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; k=Findnum(hashnum,x1); if(k>=0) { printf("%-10d%s%4d",hashnum->ht[k].number,hashnum->ht[k].name,hashnum->h t[k].egrade); printf("\n"); } } } else if (select2==2) { printf("学号 姓名 C语言"); printf("\n"); for(j=0;jht[i].size;j++) { DataType x1; x1.key=hashnumber->ht[i].number[j]; k=Findnum(hashnum,x1); if(k>0) - 26 - 数据结构课程设计 { printf("%-10d%s%4d",hashnum->ht[k].number,hashnum->ht[k].name,hashnum->h t[k].cgrade); printf("\n"); } } } } void printmidan(Hashtablenum *hashnum,int b[],int&h) { int i; for(h=0,i=0;itablesize;i++) if(hashnum->ht[i].info==Active) { b[h]=i; h++; } printf("学号 姓名 数学 英语 C语言"); printf("\n"); for(i=0;iht[b[i]].total.key=hashnum->ht[b[i]].mgrade+hashnum->ht[b[i]].egrad e+hashnum->ht[b[i]].cgrade; printf("%-10d%s %4d %4d %4d",hashnum->ht[b[i]].number,hashnum->ht[b[i]] .name,hashnum->ht[b[i]].mgrade,hashnum->ht[b[i]].egrade,hashnum->ht[b[i]].cgr ade); printf("\n"); } } int insert(bitree **root,Hashitemnum item) { bitree *p; bitree *current; bitree *parent=NULL; current=*root; while(current!=NULL) { if(current->data.key==item.total.key) return 0; parent=current; - 27 - 2008.7 数据结构课程设计 if(current->data.keyrightchild; else current=current->leftchild; } p=(bitree*)malloc(sizeof(bitree)); p->data=item.total; p->number=item.number.key; copy(item.name,p->name); p->rightchild=NULL; p->leftchild=NULL; if(parent==NULL) *root=p; else if(item.total.keydata.key) parent->leftchild=p; else parent->rightchild=p; return 1; } void Traverse(bitree*root) { if(root==NULL) return; if(root->leftchild!=NULL) Traverse(root->leftchild); printf("%d %s %d",root->number,root->name,root->data.key); printf("\n"); if(root->rightchild!=NULL) Traverse(root->rightchild); } void menu(int&n) { system("cls"); printf("*****************欢迎使用学生成绩管理系统 **************************\n"); printf("******************************************************\n"); printf("*********************** 菜 单 ***********************\n"); printf(" * a 学生登记注册与学生成绩录入 b 增加某一班的学生记录 * \n"); printf(" * c 删除某一班的学生记录 d 修改学生成绩 * \n"); printf(" * e 统计学生记录 f 查找学生记录 * \n"); printf(" * g 打印学生记录 h 排序学生记录 * \n"); printf(" * j 退出 * \n"); printf(" ***************************************************\n"); - 28 - 数据结构课程设计 printf("请输入全校学生的班级个数:"); scanf("%d",&n); } void main() { int n,i=0,m,h; char ch; int b[100]; int c[10000]; Hashtablenum numhashtable; Hashtablename namehashtable; Hashtableclassnumber classhashtable; Hashitemnum num[1000]; DataType a[100]; menu(n); for(i=0;i<100;i++) { b[i]=-1; a[i].key=-1; } while(1) { printf("请输入您要进行的操作:"); scanf("%s",&ch); if(ch=='j') break; switch(ch) { case 'a': { create(num,m,a,b); printf("学生的信息正在被录入之中.......请稍后\n"); Initiatenum(&numhashtable,(int)(1.5*m)); Initiatename(&namehashtable,(int)(1.5*m)); Initiatenumber(&classhashtable,(int)(1.5*n)); for(i=0;i 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 进行哈夫曼编码并存储入文件(涉及到创建哈夫曼树，进行哈夫曼编码和写文 件); ?对编码文件进行译码(涉及到哈夫曼译码和写文件)。 ? 由三个功能块可将程序划分为几个模块(即实现程序功能所需的函数): ?读文件函数 ?写文件函数 ?统计字符频率函数 ?创建哈夫曼树函数 ?编码函数 ?译码函 数六个模块。 【算法设计】 总体思想是利用哈夫曼算法建立霍夫曼树，然后再对统计的字符集编码，译码，并打印相 关内容。要用的数据结构是树。 - 31 - 2008.7 数据结构课程设计 第一步——确定要压缩的文件 1、 首先运行的时候，用户界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的选项， 需依次进行，因为各个环节之间有先后顺序。 2、 第一步为输入压缩软件的名称，由键盘输入文件名称，读入字符数组中，打开该文件，若打不 开，继续输入;否则，按照提示进行压缩。 第二步——读文件并计算字符频率 文件将信息存放在字符数组中;计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。 第三步——根据字符的频率，利用Huffman编码思想创建Huffman树 将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。 第四步——由创建的Huffman树来决定字符对应的编码，进行文件的压缩 1、 根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。 2、 读取文件，依次将每个字符用他们的编码表示，即完成一次编码。 第五步——解压缩即根据Huffman树进行译码 读取编码文件，依据创建的Huffman树，定义一个指针指向根结点，从根结点开始，每读一个字符，则指针变化一次(当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子)，直至该指针所指结点为叶子结点时结束(即当结点的左右孩子均为空时)。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件结束时为止。 哈夫曼编码的基本思想如下: ,,w,w,...w1.根据给定的n个权值，把它们看成由n棵只有1个结点的二叉树所组成 12n ,,T,T,T....TTw的集合。F=，其中每一棵二叉树中只有一个带权为的根结点，其左右子树均空。 123nii 2.在F中选取两棵根结点的权值最小的二叉树作为左右子树构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左，右子树根结点的权值之和。 3.在F中删除这两棵二叉树，同时将新的二叉树加入F中。 4.重复2和3，直到F只含有一棵树为止。这棵树便是Huffman树。 5.根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1 建树过程以及编码过程如图示: - 32 - 数据结构课程设计 第四步 (2)数据结构设计表示 - 33 - 2008.7 数据结构课程设计 整个程序中的存储结构: 记载字符信息的存储结构:将字符的信息存放在一个结构体数组中，该结构体包含了三个部分， 字符型变量，整型字符的权值和字符的哈夫编码～ 创建哈夫曼树的存储结构:哈夫曼树的结点结构用结构体定义，包含结点的权值，左孩子指针 (指向左子树的指针)，右孩子指针(指向右子树的指针) typedef struct { char data;//字符 int weight;//权值 int flag;//标记 int parent;//双亲结点下标 int leftChild;//左孩子下标 int rightChild;//右孩子下标 }HaffNode;//哈夫曼树的结点结构 typedef struct {char bit[MaxN];//存放编码的数组 int start;//编码的起始下标 int weight;//字符的权值 }Code;//哈夫曼编码的结构 (3)详细设计表示: 【函数模块】 1. Initialiation(int &n,HaffNode hafftree[])/*初始化哈夫曼树模块*/ Haffmantree(int n,HaffNode haffTree[])/*创建哈夫曼树模块*/ Coding(HaffNode haffTree[],int n,Code haffCode[])/*编码模块*/ Decoding(int n,HaffNode haffTree[],Code haffCode[])/*译码模块*/ Printcode()/*格式化打印编码模块*/ Treeprinting(int n,HaffNode haffTree[])/*打印哈夫曼树模块*/ PrintTree(HaffNode huf[],int n,int p,FILE *fp)/*打印哈夫曼树时调用的函数模块*/ print()/*打印哈夫曼树时调用的函数模块*/ - 34 - 数据结构课程设计 2.程序执行中函数调用关系和流程如下: Initialiation(int&n,HaffNode fftree[]) 初始化 Haffmantree()(建树) (CreatTree() 编码 Coding() 译码 Decoding() 打印代码 Printcode() 打印哈夫 曼树 Treeprinting() PrintTree(HaffNode huf[],int n,int p,FILE *fp) 【测试数据】 请输入要编码的电文(输入#结束):acccdddddeeeeeee# ******************************************************************************* ***** ***** ***** ***** ********************欢迎使用哈夫曼编,译码器*********************************** ***** ***** *************************菜单*************************************************** ***** C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 ***** ***** ***** ******************************************************************************* 请输入要执行的操作: C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 请输入要执行的操作: C 字符 权值 对应编码 a 1 100 c 3 101 d 5 11 e 7 0 - 35 - 2008.7 数据结构课程设计 请输入要执行的操作: C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 请输入要执行的操作: D acccdddddeeeeeee 译码过程完成!已将结果存入textfile中. 请输入要执行的操作: C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 请输入要执行的操作: T -----d -----@ -----c -----@ -----a -----@ -----e 打印哈夫曼树过程完成!同时已将结果存入treeprint中. 请输入要执行的操作: C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 请输入要执行的操作: P 10010110110111111111110000000 打印代码过程完成!已将结果存入codeprint中请输入要执行的操作: C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 请输入要执行的操作: E 谢谢使用哈夫曼译码器! 【调试报告】 1.开始时，从电文中读取字符串时，开始读取时始终读取字符串时始终不成功。 2(用代码while (feof(fp)==0)表示文件结束时，在写入文件时，始终会多读如一个字符串， 后来改用ch=fgetc(fp2);while (ch!=EOF)时，读取文件成功，并且译码文件也成功。 【用户手册】 1、输入的电文字符串被存在tobetrans.txt中，以输入‘#’为结束标志，建立的哈夫曼树存 于文件hfmtree.txt中，编码的结果存在文件codefile.txt中, 译码结果存入文件textfile.txt中, 印代码 文件存在codeprint.txt中, 打印哈夫曼树字符形式的哈夫曼树写入文件treeprint.txt中. 【附录】 源程序清单: #include #include #define MaxValue 10000 #define Maxbit 10 #define MAX 53 #define MaxN 100 - 36 - 数据结构课程设计 typedef struct { char data; int weight; int flag; int parent; int leftChild; int rightChild; }HaffNode; typedef struct { char bit[MaxN]; int start; int weight; }Code; void Initialiation(int &n,HaffNode hafftree[]) { int i,j,m=0; FILE *fp; char ch; hafftree[0].data=' '; hafftree[0].weight=0; for(i=1;i<27;i++) { hafftree[i].data='A'+i-1; hafftree[i].weight=0; } for(j=0;j<26;j++) { hafftree[i+j].data='a'+j; hafftree[i+j].weight=0; } fp=fopen("tobetrans.txt","w"); printf("请输入要编码的电文(输入#结束):"); while(1) { scanf("%c",&ch); if(ch=='#') break; fprintf(fp,"%c",ch); if(ch==' ') hafftree[0].weight++; if(ch>='A'&&ch<='Z') hafftree[ch-64].weight++; if(ch>='a'&&ch<='z') - 37 - 2008.7 数据结构课程设计 hafftree[ch-70].weight++; } fclose(fp); for(i=0;i<53;i++) { if(hafftree[i].weight==0) { m++; for(j=i;j<53;j++) hafftree[j]=hafftree[j+1]; i--; } } n=53-m; } void Haffmantree(int n,HaffNode haffTree[]) { int i,j,m1,m2,x1,x2; for (i=0;i<2*n-1;i++) { haffTree[i].parent=-1; haffTree[i].flag=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1; if(i>=n) haffTree[i].weight=0; } for(i=0;istart=n-1; cd->weight=haffTree[i].weight; child=i; parent=haffTree[child].parent; while(parent!=-1) { if(haffTree[parent].leftChild==child) cd->bit[cd->start]='0'; else cd->bit[cd->start]='1'; cd->start--; child=parent; parent=haffTree[child].parent; } for(j=cd->start+1;jbit[j]; haffCode[i].start=cd->start+1; haffCode[i].weight=cd->weight; - 39 - 2008.7 数据结构课程设计 } FILE *fp,*fp1,*fp2; fp=fopen("codefile.txt","w+"); fp1=fopen("codefile1.txt","w+"); fp2=fopen("tobetrans.txt","r"); ch=fgetc(fp2); while (ch!=EOF) { for (i=0;i=0&&huf[n].rightChild==-1) { printf("-----"); printf("%c\n",huf[n].data); //如果此结点为叶子结点，则将此结点输出; fprintf(fp,"-----%c\n",huf[n].data); } else { printf("-----@\n"); //如果此结点为非叶子结点，则输出"@"; fprintf(fp,"-----@\n"); } PrintTree(huf,huf[n].leftChild,p+1,fp); } void Treeprinting(int n,HaffNode haffTree[]) //打印哈夫曼树的操作 { FILE *fp; fp=fopen("huffman.txt","r"); fp=fopen("treeprint","w+"); PrintTree(haffTree,2*n-2,0,fp); fclose(fp); printf("打印哈夫曼树过程完成!同时已将结果存入treeprint中.\n\n"); } void print() { printf("************************************************************** *****************\n"); printf("***** *****\n"); printf("***** *****\n"); - 42 - 数据结构课程设计 printf("********************欢迎使用哈夫曼编,译码器 ***********************************\n"); printf("***** *****\n"); printf("*************************菜单 ***************************************************\n"); printf("***** C.编码 D.译码 T.印哈夫曼树 P.印代码文件 E.退出 *****\n"); printf("***** *****\n"); printf("************************************************************** *****************\n"); } int main() { int n=0; char ch; HaffNode*myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*MAX+1)); Code*myHaffCode=(Code*)malloc(sizeof(Code)*MAX); Initialiation(n,myHaffTree); print(); Haffmantree(n,myHaffTree); while (1) { printf("请输入要执行的操作:\nC.编码 D.译码 T.印哈夫曼树 P. 印代码文件 E.退出\n"); printf("请输入要执行的操作:\n"); scanf("%s",&ch); if (ch=='E') { printf("谢谢使用哈夫曼译码器!"); break; } switch (ch) { case 'C':Coding(myHaffTree,n,myHaffCode);break; //执行编码操作 case 'D':Decoding(n,myHaffTree,myHaffCode);break; //执行译码操作 case 'P':Printcode();break; //打印代码文件 case 'T':Treeprinting(n,myHaffTree);break; //打印哈夫曼树 } } return 0; } - 43 - 2008.7 数据结构课程设计 实习题目三 全国道路交通模拟咨询 【需求及规格说明】 出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 【基本要求】 (1)提供对城市信息进行编辑(如添加或删除)的功能。 (2)城市之间有两种交通工具:火车和飞机。提供对列车时刻表和飞机航班进行编辑(增设或删除)的功能。 (3)提供两种最优决策:最快到达或最省钱到达。全程只考虑一种交通工具。 (4)旅途中耗费的总时间应该包括中转站的等候时间。 (5)咨询以用户和计算机的对话方式进行。 【算法设计】 1、总体设计 (1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。 (2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间(要包括中转站的等候时间)或旅费。 (3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里采用邻接表作为数据的存储结构。 (4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面。 (5) 最优决策功能模块(fast or province)。 ? 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息;表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。 ? 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为?，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队列)中只有出发地城市，随着对栈(队列)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队列)中，则进栈(队列)，直至栈(队列)为空，本题采用队列实现。 ? 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈(队列)，再逐一出栈栈(队列)中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地;最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。 (6) 主程序可以有系统界面、菜单;也可用命令提示方式;选择功能模块执行，要求在程序运行过程中可以反复操作。 2.详细设计思想: - 44 - 数据结构课程设计 本题所要求的交通系统是一个有向带权图结构，考虑到要求该系统有动态增加飞机和列车航班的功能，因而采用邻接表的形式存储:对每个顶点建立一个单链表，单链表中的子结点表示以该顶点连接的弧，单链表中子结点的顺序可以按权值递增的顺序排列，表头结点按顺序存储。题目中提到要提供三种策略，最快到达，最省钱到达和最少中转次数策略，前两种策略采用迪杰斯特拉算法思想，其中最快到达的权值为到达两城市所需的最短时间，最省钱到达的权值为到达两城市所需的费用，后一种采用广度优先算法的思想，只需求的两城市所在的层数，就可以求的到达两城市所需的最少中转次数。 迪杰斯特拉(Dijkstra)算法的基本思想是: 设置两个顶点的集合S和T,V,S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。 下面讨论基于邻接表的存储结构求两点间最短路径的方法: 根据迪杰斯特拉(Dijkstra)算法所依据的原理:若按长度递增的次序生成从源点V0到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点的最短路径看作是已生成的源点到其自身的长度为0的路径)。 按照这一思想，构造以下算法: 设S=S’=U={}，建立数组PATH[n]，用来存储V0到各终点的最短路径，初值均置为空集。建立数组BOOL F[n]，F[i]表示序号为i的表头结点的单链表中所有子结点已或未全部找到，初值置为FALSE。建立数组float dist[n]，dist[i]表示序号为i的表头结点到V0的最短权值(这里是时间或费用)，显然dist[V0]=0,其他顶点的dist初值置为?。建立数组BOOL IS[n]，IS[i]表示序号为i的顶点是否在S中，初值均置为FALSE。 (1)VX=V0;最短的最短路径为PATH[0]=[V0] (2)S=S+VX;(集合的并计算) IS[VX]=TRUE; S’=S’+VX ; (3)对S’中的所有顶点: { do{ 由邻接表中该表头结点开始依次找单链表的下一子结点(沿链域指针依次访问); if(该子结点?S)//IS[该子结点的邻接点序号]==TRUE if(子结点链域指针指向NULL) F=TRUE;S’=S’-该表头结点; break; else continue; else break; } while(); 如F=FALSE,则U=U+该子结点; } 如果S’=空集，则结束; (4)下一次短路径的终点必?U。比较U中子结点到V0的dist值(其值为U中结点的弧的权值+其表头结点的dist值)，由dist值最小的子结点的邻接点域确定次短路径的终点VX， - 45 - 2008.7 数据结构课程设计 PATH[ VX]=PATH[该子结点的表头结点]+[VX](集合的并计算)。dist[VX]=VX所属子结点的弧的权值+其表头结点的dist值。 U={}; 如果VX为所要找的顶点，则结束; 回到2执行。 广度优先搜索遍历图类似于树的按层次遍历，其基本思想是:首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk„„，并均标记为已访问过，然后再按照Vj、Vk„„的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。 算法的流程图: - 46 - 数据结构课程设计 全部节点已处 理标志置假求得路途所耗 时间time1 计算当前节点k 到其它未处理 节点j的直接距达到目标根据k中得arrivalTime挑所有城市节点离distance节点标志选一个最近航班，求得初始化处理置假所需等待时间time2 起源节点处全部节点已上一步求得得距理:前驱节点Y处理标志置离值distance小于求得time3=k节点置空，处理标真INFINITE(表示得minTim志置位，距离有直达班车)置零 对所有未处理 起源节点设为的节点I处理i节点更新Ytime1+time2+ti当前节点k相关属性比较计算节点me3vertex加入队列置E已访问标志Y N YNp->vertex是否置P为p=p->next;P==NULL?已访问,E的邻接表头指针 (2)数据结构设计表示: /*************图的邻接表结构**********/ typedef struct { int number;//飞机或列车编号 float expenditure;//费用 int begintime[2];//出发时间 int arrivetime[2];//到达时间 }Vehide; typedef struct { Vehide stata[MAX_ROUTE_NUM]; int last; }infolist; typedef struct ArcNode { int adjvex;//该边依附或弧所指向的顶点位置 struct ArcNode *nextarc;//指向下一条边或弧 infolist info;//该边或弧相关的信息 }ArcNode; typedef struct VNode { char cityname[10];//顶点信息 ArcNode *planefirstarc,*trainfirstarc;//指向第一条依附于该顶点的弧 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices;//邻接表 int vexnum,planearcnum,trainarcnum;//顶点数，边数 }ALGraph; - 48 - 数据结构课程设计 /*******基于邻接表的广度优先(链式的队列)处理最少旅行中转次数处理******/ typedef struct { QNode *front; QNode *rear; }LinkQueue; (3)详细设计表示: \【测试数据】 *************请选择程序功能:************* ******1=管理员管理 ******2=用户咨询 ******3=显示交通系统 ******4=退出 选择?1 ************请选择管理项目:************ ******1=初始化交通系统 ******2=城市编辑 ******3=飞机航班编辑 ******4=列车车次编辑 ******5=返回上一级菜单 选择?1 ************请选择初始化方式:************ ******1=键盘 ******2=文档 选择?1 请输入城市名称的信息: 城市名称:wuhan beijing shanghai tianjing 继续输入?(Y/N)N 请输入飞机航班的信息: 飞机航班编号:102 起始城市:wuhan 目的城市:beijing 航班费用:2500 起飞时间:5:10 到达时间:7:24 继续输入?(Y/N)Y 请输入飞机航班的信息: 飞机航班编号:104 起始城市:beijing 目的城市:shanghai 航班费用:2300 起飞时间:7:30 到达时间:8:45 继续输入?(Y/N)Y - 49 - 2008.7 数据结构课程设计 请输入飞机航班的信息: 飞机航班编号:106 起始城市:shanghai 目的城市:tianjing 航班费用:1200 起飞时间:8:40 到达时间:9:52 继续输入?(Y/N)Y 请输入飞机航班的信息: 飞机航班编号:108 起始城市:wuhan 目的城市:tianjing 航班费用:2400 起飞时间:10:12 到达时间:11:45 继续输入?(Y/N)N 请输入列车车次的信息: 列车车次编号:201 起始城市:wuhan 目的城市:beijing 车次费用:500 发车时间:5:10 到达时间:7:45 继续输入?(Y/N)Y 请输入列车车次的信息: 列车车次编号:203 起始城市:wuhan 目的城市:tianjing 车次费用:300 发车时间:8:10 到达时间:9:35 继续输入?(Y/N)Y 请输入列车车次的信息: 列车车次编号:205 起始城市:beijing 目的城市:shanghai 车次费用:200 发车时间:8:00 到达时间:9:15 继续输入?(Y/N)Y 请输入列车车次的信息: 列车车次编号:207 起始城市:shanghai 目的城市:tianjing - 50 - 数据结构课程设计 车次费用:120 发车时间:9:20 到达时间:10:45 继续输入?(Y/N)Y 请输入列车车次的信息: 列车车次编号:209 起始城市:wuhan 目的城市:shanghai 车次费用:210 发车时间:10:10 到达时间:11:55 继续输入?(Y/N)N ************请选择管理项目:************ ******1=初始化交通系统 ******2=城市编辑 ******3=飞机航班编辑 ******4=列车车次编辑 ******5=返回上一级菜单 选择?2 请输入新增城市的名称:changsha 确认?(Y/N)Y ************请选择管理项目:************ ******1=初始化交通系统 ******2=城市编辑 ******3=飞机航班编辑 ******4=列车车次编辑 ******5=返回上一级菜单 选择?3 请选择飞机航班编辑项目: 1=新增航班 2=删除航班 选择?1 请输入新增飞机航班的信息: 飞机航班编号:124 起始城市:wuhan 目的城市:changsha 航班费用:1000 起飞时间:10:20 到达时间:11:31 确认?(Y/N)Y ************请选择管理项目:************ ******1=初始化交通系统 ******2=城市编辑 ******3=飞机航班编辑 - 51 - 2008.7 数据结构课程设计 ******4=列车车次编辑 ******5=返回上一级菜单 选择?4 请选择列车车次编辑项目: 1=新增车次 2=删除车次 选择?1 请输入新增列车车次的信息: 列车车次编号:111 起始城市:wuhan 目的城市:changsha 车次费用:100 发车时间:11:15 到达时间:12:25 确认?(Y/N)Y ************请选择管理项目:************ ******1=初始化交通系统 ******2=城市编辑 ******3=飞机航班编辑 ******4=列车车次编辑 ******5=返回上一级菜单 选择?5 请选择程序功能: 1=管理员管理 2=用户咨询 3=显示交通系统 4=退出 请选择2 请选择咨询项目: 1=最少旅行费用 2=最少旅行时间 3=最少旅行中转次数 4=返回上一级菜单 选择?1 请选择旅行起始城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?0 请选择旅行到达城市: 0=wuhan 1=beijing - 52 - 数据结构课程设计 2=shanghai 3=tianjing 4=changsha 选择?3 请选择交通工具: 1=列车 2=飞机 选择?1 确认? (Y/N)Y 旅行路线是: 乘坐No.203列车车次在8:10从wuhan到tianjing 最少旅行费用是300.000000元 按回车继续 请选择咨询项目: 1=最少旅行费用 2=最少旅行时间 3=最少旅行中转次数 4=返回上一级菜单 选择?2 请选择旅行起始城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?0 请选择旅行到达城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?3 请选择交通工具: 1=列车 2=飞机 选择?2 确认? (Y/N)Y 旅行路线是: 乘坐No.108飞机航班在10:12从wuhan到tianjing 最少旅行时间是1:33 按回车继续 请选择咨询项目: 1=最少旅行费用 - 53 - 2008.7 数据结构课程设计 2=最少旅行时间 3=最少旅行中转次数 4=返回上一级菜单 选择?3 请选择旅行起始城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?0 请选择旅行到达城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?3 请选择交通工具: 1=列车 2=飞机 选择?2 确认? (Y/N)Y 旅行路线是: 乘坐No.108飞机航班在10:12从wuhan到tianjing 最少中转次数是0次 按回车继续 请选择咨询项目: 1=最少旅行费用 2=最少旅行时间 3=最少旅行中转次数 4=返回上一级菜单 选择?3 请选择旅行起始城市: 0=wuhan 1=beijing 2=shanghai 3=tianjing 4=changsha 选择?0 请选择旅行到达城市: 0=wuhan 1=beijing 2=shanghai - 54 - 数据结构课程设计 3=tianjing 4=changsha 选择?3 请选择交通工具: 1=列车 2=飞机 选择?1 确认? (Y/N)Y 旅行路线是: 乘坐No.203列车车次在8:10从wuhan到tianjing 最少中转次数是0次 按回车继续 请选择咨询项目: 1=最少旅行费用 2=最少旅行时间 3=最少旅行中转次数 4=返回上一级菜单 选择?4 请选择程序功能: 1=管理员管理 2=用户咨询 3=显示交通系统 4=退出 请选择3 请选择显示项目: 0=显示城市 1=显示飞机航班 2=显示列车车次 3=返回上一级菜单 选择?0 城市: wuhan beijing shanghai tianjing changsha 请选择显示项目: 0=显示城市 1=显示飞机航班 2=显示列车车次 3=返回上一级菜单 选择?1 飞机航班: wuhan---->changsha number:124 expenditure:1000.00 begintime:10:20 arrivetime:11:31 wuhan---->tianjing number:108 expenditure:2400.00 - 55 - 2008.7 数据结构课程设计 begintime:10:12 arrivetime:11:45 wuhan---->beijing number:102 expenditure:2500.00 begintime:5:10 arrivetime:7:24 beijing---->shanghai number:104 expenditure:2300.00 begintime:7:30 arrivetime:8:45 number:120 expenditure:2000.00 begintime:11:10 arrivetime:12:25 shanghai---->tianjing number:106 expenditure:1200.00 begintime:8:40 arrivetime:9:52 请选择显示项目: 0=显示城市 1=显示飞机航班 2=显示列车车次 3=返回上一级菜单 选择?2 列车车次: wuhan---->changsha number:111 expenditure:100.00 begintime:11:15 arrivetime:12:25 wuhan---->shanghai number:209 expenditure:210.00 begintime:10:10 arrivetime:11:55 wuhan---->tianjing number:203 expenditure:300.00 begintime:8:10 arrivetime:9:35 wuhan---->beijing number:201 expenditure:500.00 begintime:5:10 arrivetime:7:45 beijing---->shanghai number:205 expenditure:200.00 begintime:8:0 arrivetime:9:15 shanghai---->tianjing number:207 expenditure:120.00 begintime:9:20 arrivetime:10:45 请选择显示项目: 0=显示城市 1=显示飞机航班 2=显示列车车次 3=返回上一级菜单 选择?3 请选择程序功能: - 56 - 数据结构课程设计 1=管理员管理 2=用户咨询 3=显示交通系统 4=退出 请选择4 【调试报告】: 1.开始时，不知道怎样用基于邻接表的迪杰斯特算法来写最快到达或最省钱到达函数，后查 找资料重新根据迪杰斯特拉思想写出。 2.在显示交通系统时，出现时间不能显示错误的情况，后进经过修改发现打印方式是错误的， 调试后将打印方式修改，最后程序能正确显示时间。 【用户手册】 首先是管理员初始化交通系统，然后才是用户咨询交通系统界面，本系统提供了三种咨询方式， 即最少旅行费用到达,最少旅行时间到达,最少旅行中转次数到达,有两种交通工具(飞机和火车),同时此系统还可以实时显示交通系统。 【函数模块】 void Administer(ALGraph *G); void cityedit(ALGraph *G); void CopyTimeTree(TimeTree p,TimeTree q); void createcityfile(); void CreateGraph(ALGraph *G); void createplanefile(); void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM]); void createtrainfile(); int DeleteplaneArc(ALGraph *G); void DeleteQueue(LinkQueue *Q,int *x); int DeletetrainArc(ALGraph *G); void DeleteVertex(ALGraph *G); void DemandDispose(int n,ALGraph G); void DestoryTimeTree(TimeTree p); void EnterplaneArc(ALGraph *G); void EnterQueue(LinkQueue *Q,int x); void EntertrainArc(ALGraph *G); void EnterVertex(ALGraph *G); void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final); void flightedit(ALGraph *G); void initgraph(ALGraph *G); void InitQueue(LinkQueue *Q); int IsEmpty(LinkQueue *Q); int LocateVertex(ALGraph *G,char *v); void MinExpenditure(infolist arcs,float *expenditure,int *route); void MinTime(infolist arcs,int *time,int *route); void PrintGraph(ALGraph *G); int save(ALGraph *G); - 57 - 2008.7 数据结构课程设计 void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final); void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM]); void trainedit(ALGraph *G); void TransferDispose(int k,infolist(*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1); void UserDemand(ALGraph G); void VisitTimeTree(TimeTree p); 【附录】 代码清单: #define MAX_VERTEX_NUM 18 #define NULL 0 #define MAX_ARC_SIZE 100 #define MAX_ROUTE_NUM 5 #define False 0 #define True 1 #define INFINITY 10000 #include"stdio.h" #include"stdlib.h" #include"string.h" typedef struct { int number;//飞机或列车编号 float expenditure;//费用 int begintime[2];//出发时间 int arrivetime[2];//到达时间 }Vehide; typedef struct { Vehide stata[MAX_ROUTE_NUM]; int last; }infolist; /*************图的邻接表结构**********/ typedef struct ArcNode { int adjvex;//该边依附或弧所指向的顶点位置 struct ArcNode *nextarc;//指向下一条边或弧 infolist info;//该边或弧相关的信息，如权值 }ArcNode; typedef struct VNode { char cityname[10];//顶点信息 ArcNode *planefirstarc,*trainfirstarc;//指向第一条依附于该顶点的弧 }VNode,AdjList[MAX_VERTEX_NUM]; - 58 - 数据结构课程设计 typedef struct { AdjList vertices;//邻接表 int vexnum,planearcnum,trainarcnum;//顶点数，边数 }ALGraph; typedef struct Node { int adjvex; int route; struct Node *next; }Node; typedef struct QNode { int adjvex; struct QNode *next; }QNode; /*******基于邻接表的广度优先(链式的队列)处理最少旅行中转次数处理******/ typedef struct { QNode *front; QNode *rear; }LinkQueue; typedef struct TimeNode { int adjvex; int route; int begintime[2]; int arrivetime[2]; struct TimeNode *child[MAX_ROUTE_NUM]; }TimeNode,*TimeTree; struct arc { int co; char vt[10];//起始城市 char vh[10];//目标城市 int bt[2];//出发时间 int at[2];//到达时间 float mo; }a[MAX_ARC_SIZE]; char city[MAX_VERTEX_NUM][10]; int TTime[2]; int time[2]; int time1[2]; int time2[2]; - 59 - 2008.7 数据结构课程设计 int c[MAX_VERTEX_NUM]; int d[MAX_VERTEX_NUM]; void Administer(ALGraph *G); void cityedit(ALGraph *G); void CopyTimeTree(TimeTree p,TimeTree q); void createcityfile(); void CreateGraph(ALGraph *G); void createplanefile(); void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM]); void createtrainfile(); int DeleteplaneArc(ALGraph *G); void DeleteQueue(LinkQueue *Q,int *x); int DeletetrainArc(ALGraph *G); void DeleteVertex(ALGraph *G); void DemandDispose(int n,ALGraph G); void DestoryTimeTree(TimeTree p); void EnterplaneArc(ALGraph *G); void EnterQueue(LinkQueue *Q,int x); void EntertrainArc(ALGraph *G); void EnterVertex(ALGraph *G); void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final); void flightedit(ALGraph *G); void initgraph(ALGraph *G); void InitQueue(LinkQueue *Q); int IsEmpty(LinkQueue *Q); int LocateVertex(ALGraph *G,char *v); void MinExpenditure(infolist arcs,float *expenditure,int *route); void MinTime(infolist arcs,int *time,int *route); void PrintGraph(ALGraph *G); int save(ALGraph *G); void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final); void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM]); void trainedit(ALGraph *G); void TransferDispose(int k,infolist(*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1); void UserDemand(ALGraph G); void VisitTimeTree(TimeTree p); /*******************显示程序功能选择界面***************/ int main() { ALGraph G; int i; printf("*************请选择程序功能:*************\n"); - 60 - 数据结构课程设计 printf("******1=管理员管理\n******2=用户咨询\n******3=显示交通系统\n******4=退出\n"); printf("选择?"); scanf("%d",&i); getchar(); while(i!=4) { switch(i) { case 1:Administer(&G);break; case 2:UserDemand(G);break; case 3:PrintGraph(&G);break; } printf("\n请选择程序功能:\n"); printf("1=管理员管理\n2=用户咨询\n3=显示交通系统\n4=退出\n"); printf("请选择"); scanf("%d",&i); getchar(); } return 1; } /****************显示管理员管理项目选择界面**********/ void Administer(ALGraph *G) { int i; printf("\n************请选择管理项目:************\n"); printf("******1=初始化交通系统\n******2=城市编辑\n******3=飞机航班编辑\n******4= 列车车次编辑\n******5=返回上一级菜单\n"); printf("选择?"); scanf("%d",&i); getchar(); while(i!=5) { switch(i) { case 1:initgraph(G); //初始化交通系统 break; case 2:cityedit(G); //城市编辑 break; case 3:flightedit(G); //飞机航班编辑 break; case 4:trainedit(G); //列车车次编辑 break; } printf("\n************请选择管理项目:************\n"); - 61 - 2008.7 数据结构课程设计 printf("******1=初始化交通系统\n******2=城市编辑\n******3=飞机航班编辑 \n******4=列车车次编辑\n******5=返回上一级菜单\n"); printf("选择?"); scanf("%d",&i); getchar(); } } /*************初始化交通系统方式选择界面**************/ void initgraph(ALGraph *G) //初始化交通系统 { int i; printf("\n************请选择初始化方式:************\n"); printf("******1=键盘\n******2=文档\n"); printf("选择?"); scanf("%d",&i); getchar(); switch(i) { case 1: createcityfile(); createplanefile(); createtrainfile(); CreateGraph(G); break; case 2:CreateGraph(G); break; } } /*****************创建城市名称文档*****************/ void createcityfile() { int i=0; int j; char flag='y'; FILE *fp; printf("\n请输入城市名称的信息:\n"); while(flag=='y'||flag=='Y') { printf("城市名称:"); gets(city[i]); i++; printf("继续输入?(Y/N)"); scanf("%c",&flag); getchar(); } - 62 - 数据结构课程设计 printf("\n"); if((fp=fopen("city.txt","w+"))==NULL) { printf("无法打开文件!\n"); return; } for(j=0;j=24||bt[1]<0||bt[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); } - 63 - 2008.7 数据结构课程设计 printf("到达时间:"); //输入航班的到达时间at scanf("%d:%d",&at[0],&at[1]); getchar(); while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&at[0],&at[1]); getchar(); } a[count].co=code; // a 为程序头部定义的结构体 strcpy(a[count].vt,vt); strcpy(a[count].vh,vh); a[count].bt[0]=bt[0]; a[count].bt[1]=bt[1]; a[count].at[0]=at[0]; a[count].at[1]=at[1]; a[count].mo=money; count++; //计数值count+1 printf("继续输入?(Y/N)"); //提示"是否要继续输入航班信息:" scanf("%c",&flag); getchar(); printf("\n"); } if((fp=fopen("plane.txt","wb"))==NULL) //航班文件不能以读写形式打开 printf("\n无法打开文件!\n"); //提示"无法打开文件" fprintf(fp,"%d",count); //将计数值count写入航班车文件 for(i=0;i=24||bt[1]<0||bt[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); } printf("到达时间:"); scanf("%d:%d",&at[0],&at[1]); getchar(); while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&at[0],&at[1]); getchar(); } a[count].co=code; strcpy(a[count].vt,vt); strcpy(a[count].vh,vh); a[count].bt[0]=bt[0]; a[count].bt[1]=bt[1]; a[count].at[0]=at[0]; a[count].at[1]=at[1]; a[count].mo=money; count++; printf("继续输入?(Y/N)"); scanf("%c",&flag); getchar(); printf("\n"); } if((fp=fopen("train.txt","wb"))==NULL) - 65 - 2008.7 数据结构课程设计 printf("\n无法打开文件!\n"); fprintf(fp,"%d",count); for(i=0;ivexnum;k++) if(strcmp(G->vertices[k].cityname,v)==0) //第k个结点中的城市名与传过来的城市名相同 { j=k; /*记录位置*/ break; } return(j); } /*用city，plan，train三个文档创建城市交通系统*/ void CreateGraph(ALGraph *G) { int i,j,k; int arc_num; int count1,count2; int m,t; ArcNode *p,*q; FILE *fp; i=0; if((fp=fopen("city.txt","r"))==NULL) //打开城市文件，文件指针返回值为空 { printf("\n无法打开文件!\n"); return; } while(!feof(fp)) //文件不为空 { fscanf(fp,"%10s",city[i]); i++; } fclose(fp); //关闭文件 j=0; while(jvertices[j].cityname,city[j]);//将 city[i] 中的内容复制到图的结构体的结点数组 中; G->vertices[j].planefirstarc=NULL; // 图的结构体其他项赋初值; G->vertices[j].trainfirstarc=NULL; j++; } G->vexnum=i; if((fp=fopen("plane.txt","r"))==NULL) printf("\n无法打开文件!\n"); k=0; fscanf(fp,"%d",&count1); //打开航班信息文件"plane.txt" while(kvertices[i].planefirstarc; m=0; while(q!=NULL) { if(q->adjvex==j) //弧 q中的邻接顶点与j相等 { t=q->info.last+1; // 将数组a[i] 中的内容都复制到弧q中 q->info.stata[t].number=a[k].co; q->info.stata[t].expenditure=a[k].mo; q->info.stata[t].begintime[0]=a[k].bt[0]; q->info.stata[t].begintime[1]=a[k].bt[1]; q->info.stata[t].arrivetime[0]=a[k].at[0]; q->info.stata[t].arrivetime[1]=a[k].at[1]; q->info.last=t; m=1; break; } q=q->nextarc; } if(m==0) - 67 - 2008.7 数据结构课程设计 { p=(ArcNode*)malloc(sizeof(ArcNode)); //开辟一个弧结点 p->adjvex=j; //将数组a[i]中的内容都复制到新的弧结点中 p->info.stata[0].number=a[k].co; p->info.stata[0].expenditure=a[k].mo; p->info.stata[0].begintime[0]=a[k].bt[0]; p->info.stata[0].begintime[1]=a[k].bt[1]; p->info.stata[0].arrivetime[0]=a[k].at[0]; p->info.stata[0].arrivetime[1]=a[k].at[1]; p->info.last=0; p->nextarc=G->vertices[i].planefirstarc; G->vertices[i].planefirstarc=p; // 将弧结点连接到适当的位置中去 arc_num++; } k++; } G->planearcnum=arc_num; if((fp=fopen("train.txt","r"))==NULL) { printf("\n无法打开文件!\n"); return; } k=0; fscanf(fp,"%d",&count2); //打开列车信息文件"plane.txt" while(kvertices[i].trainfirstarc; m=0; while(q!=NULL) { if(q->adjvex==j) //弧 q中的邻接顶点与j相等 { t=q->info.last+1; //将数组a[i] 中的内容都复制到弧q中 - 68 - 数据结构课程设计 q->info.stata[t].number=a[k].co; q->info.stata[t].expenditure=a[k].mo; q->info.stata[t].begintime[0]=a[k].bt[0]; q->info.stata[t].begintime[1]=a[k].bt[1]; q->info.stata[t].arrivetime[0]=a[k].at[0]; q->info.stata[t].arrivetime[1]=a[k].at[1]; q->info.last=t; m=1; break; } q=q->nextarc; } if(m==0) { p=(ArcNode*)malloc(sizeof(ArcNode)); //开辟一个弧结点 p->adjvex=j; //将数组a[i]中的内容都复制到新的弧结点中 p->info.stata[0].number=a[k].co; p->info.stata[0].expenditure=a[k].mo; p->info.stata[0].begintime[0]=a[k].bt[0]; p->info.stata[0].begintime[1]=a[k].bt[1]; p->info.stata[0].arrivetime[0]=a[k].at[0]; p->info.stata[0].arrivetime[1]=a[k].at[1]; p->info.last=0; p->nextarc=G->vertices[i].trainfirstarc; G->vertices[i].trainfirstarc=p; //将弧结点连接到适当的位置中去 arc_num++; } k++; } G->trainarcnum=arc_num; } /*************保存城市交通系统到相应的文档****************************/ int save(ALGraph *G) { int i,j,k,t; ArcNode *q; FILE *fp; j=0; while(jvexnum) { strcpy(city[j],G->vertices[j].cityname); j++; } i=0; - 69 - 2008.7 数据结构课程设计 if((fp=fopen("city.txt","w"))==NULL) printf("\n错误,无法打开文件!\n"); while(ivexnum) { fprintf(fp,"%10s",city[i]); i++; } fclose(fp); k=0; for(i=0;ivexnum;i++) { q=G->vertices[i].planefirstarc; while(q!=NULL) { for(t=0;t<=q->info.last;t++) { strcpy(a[k].vt,G->vertices[i].cityname); strcpy(a[k].vh,G->vertices[q->adjvex].cityname); a[k].co=q->info.stata[t].number; a[k].mo=q->info.stata[t].expenditure; a[k].bt[0]=q->info.stata[t].begintime[0]; a[k].bt[1]=q->info.stata[t].begintime[1]; a[k].at[0]=q->info.stata[t].arrivetime[0]; a[k].at[1]=q->info.stata[t].arrivetime[1]; k++; } q=q->nextarc; } } if((fp=fopen("plane.txt","wb"))==NULL) { printf("\n无法打开文件!\n"); return 0; } i=0; fprintf(fp,"%d",k); while(ivexnum;i++) { q=G->vertices[i].trainfirstarc; while(q!=NULL) { for(t=0;t<=q->info.last;t++) { strcpy(a[k].vt,G->vertices[i].cityname); strcpy(a[k].vh,G->vertices[q->adjvex].cityname); a[k].co=q->info.stata[t].number; a[k].mo=q->info.stata[t].expenditure; a[k].bt[0]=q->info.stata[t].begintime[0]; a[k].bt[1]=q->info.stata[t].begintime[1]; a[k].at[0]=q->info.stata[t].arrivetime[0]; a[k].at[1]=q->info.stata[t].arrivetime[1]; k++; } q=q->nextarc; } } if((fp=fopen("train.txt","wb"))==NULL) { printf("\n无法打开文件!\n"); return 0; } i=0; fprintf(fp,"%d",k); while(i=0&&ivexnum) { printf("\n错误～此城市已存在\n"); return; } else { printf("\n确认?(Y/N)"); c=getchar(); getchar(); if(c=='Y'||c=='y') { i=G->vexnum; strcpy(G->vertices[i].cityname,v); G->vertices[i].planefirstarc=NULL; G->vertices[i].trainfirstarc=NULL; G->vexnum=i+1; save(G); } else return; } } /************** 删除城市****************/ void DeleteVertex(ALGraph *G) // G是程序头部定义的结构体 { int i,j,k,n; char v[10],c; - 72 - 数据结构课程设计 ArcNode *p,*q,*m; printf("\n请输入删除的城市:"); //提示"输入删除城市名" gets(v); printf("\n确认?(Y/N)"); //提示"是否确定要删除(Y/N)" c=getchar(); getchar(); if(c=='Y'||c=='y') { n=0; //0是记数标志，控制循环次数 while(nvexnum&&strcmp(G->vertices[n].cityname,v)!=0) //n<图G表头接点总个 数&&图G的存储城市名与v不同,G表头结点总个数比实际大1 n++; //记数值n+1 if(n==G->vexnum) //n==图G表头结点总个数 printf("\n错误～无法找到此城市!\n"); //提示"无法找到此城市" else { i=LocateVertex(G,v); //利用G函数找到此城市名所处在G中位置 p=G->vertices[i].planefirstarc; while(p!=NULL) { q=p; p=p->nextarc; free(q); //删除从此结点出发的所有航班弧 } p=G->vertices[i].trainfirstarc; while(p!=NULL) { q=p; p=p->nextarc; free(q); //删除从此结点出发的所有列车弧 } for(j=i;jvexnum-1;j++) { strcpy(G->vertices[j].cityname,G->vertices[j+1].cityname); //将G第j个结点的信息依前移1位 G->vertices[j].planefirstarc=G->vertices[j+1].planefirstarc; G->vertices[j].trainfirstarc=G->vertices[j+1].trainfirstarc; } G->vertices[j].planefirstarc=NULL; //将G第j个结点的信息置空 G->vertices[j].trainfirstarc=NULL; for(k=0;kvexnum-1;k++) //以下是删除所有指向此结点的航班弧 { p=G->vertices[k].planefirstarc; while(p!=NULL) { - 73 - 2008.7 数据结构课程设计 if(p->adjvex>i) { p->adjvex=p->adjvex-1; q=p; p=p->nextarc; //p指向下一条飞机弧 } else if(p->adjvex==i) //该弧指向的顶点位置(p->adjvex )== i { if(p==G->vertices[k].planefirstarc) //p指向图G中k结点的第一条飞机弧 { m=p; G->vertices[k].planefirstarc=p->nextarc; //将图G中k结点的第二条飞机弧改为第一弧 p=p->nextarc; //p指向下一条飞机弧 free(m); //释放(m) } else { q->nextarc=p->nextarc; //将p的下一条弧赋给q的下一条弧 m=p; p=p->nextarc; //p指向下一条飞机弧 free(q); //释放(q) } } else { q=p; p=p->nextarc; //p指向下一条飞机弧 } } } for(k=0;kvexnum-1;k++) ///*以下是删除所有指向此结点的列车弧*/ { p=G->vertices[k].trainfirstarc; //p指向图G中k结点的第一条列车弧 while(p!=NULL) { if(p->adjvex>i) //该弧指向的顶点位置(p->adjvex)>i { p->adjvex=p->adjvex-1; //将该弧指向顶点位置-1 q=p; p=p->nextarc; //p指向下一条列车弧 } else if(p->adjvex==i) //该弧指向的顶点位置(p->adjvex)==i { if(p==G->vertices[k].trainfirstarc)//p指向图G中k结点的第一条列车 - 74 - 数据结构课程设计 { m=p; G->vertices[k].trainfirstarc=p->nextarc; //将图G 中k结点的第二条列车弧改为第一弧 p=p->nextarc; free(m); } else { q->nextarc=p->nextarc; m=p; p=p->nextarc; free(q); } } else { q=p; p=p->nextarc; } } } } G->vexnum--; save(G); } else return; } /**********************飞机航班编辑项目选择界面**********************/ void flightedit(ALGraph *G) { int i; // char q; printf("\n请选择飞机航班编辑项目:\n"); printf("1=新增航班\n2=删除航班\n"); printf("选择?"); scanf("%d",&i); getchar(); if(i==1) EnterplaneArc(G); if(i==2) DeleteplaneArc(G); } - 75 - 2008.7 数据结构课程设计 /************* 列车车次编辑项目选择界面**************/ void trainedit(ALGraph *G) { int i; //char q; printf("\n请选择列车车次编辑项目:\n"); printf("1=新增车次\n2=删除车次\n"); printf("选择?"); scanf("%d",&i); getchar(); if(i==1) EntertrainArc(G); if(i==2) DeletetrainArc(G); } /************** 增加飞机航班************************/ void EnterplaneArc(ALGraph *G) { int i,j,bt[2],at[2]; int code; float money; int m,t; char vt[10],vh[10],c; ArcNode *p,*q; printf("\n请输入新增飞机航班的信息:\n"); printf("飞机航班编号:"); scanf("%d",&code); getchar(); printf("起始城市:"); gets(vt); printf("目的城市:"); gets(vh); printf("航班费用:"); scanf("%f",&money); getchar(); printf("起飞时间:"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); } - 76 - 数据结构课程设计 printf("到达时间:"); scanf("%d:%d",&at[0],&at[1]); getchar(); while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&at[0],&at[1]); getchar(); } printf("\n确认?(Y/N)"); c=getchar(); getchar(); if(c=='Y'||c=='y') { i=LocateVertex(G,vt); j=LocateVertex(G,vh); if(i==-1) { printf("\n错误～无法找到起始城市\n"); return; } if(j==-1) { printf("\n错误～无法找到到达城市\n"); return; } q=G->vertices[i].planefirstarc; m=0; while(q!=NULL) { if(q->adjvex==j) { t=q->info.last+1; q->info.stata[t].number=code; q->info.stata[t].expenditure=money; q->info.stata[t].begintime[0]=bt[0]; q->info.stata[t].begintime[1]=bt[1]; q->info.stata[t].arrivetime[0]=at[0]; q->info.stata[t].arrivetime[1]=at[1]; q->info.last=t; m=1; break; } q=q->nextarc; - 77 - 2008.7 数据结构课程设计 } if(m==0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info.stata[0].number=code; p->info.stata[0].expenditure=money; p->info.stata[0].begintime[0]=bt[0]; p->info.stata[0].begintime[1]=bt[1]; p->info.stata[0].arrivetime[0]=at[0]; p->info.stata[0].arrivetime[1]=at[1]; p->info.last=0; p->nextarc=G->vertices[i].planefirstarc; G->vertices[i].planefirstarc=p; G->planearcnum++; } save(G); } else return; } /****************增加列车车次**************/ void EntertrainArc(ALGraph *G) { int i,j,bt[2],at[2]; int code; float money; int m,t; char vt[10],vh[10],c; ArcNode *p,*q; printf("\n请输入新增列车车次的信息:\n"); printf("列车车次编号:"); scanf("%d",&code); getchar(); printf("起始城市:"); gets(vt); printf("目的城市:"); gets(vh); printf("车次费用:"); scanf("%f",&money); getchar(); printf("发车时间:"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); - 78 - 数据结构课程设计 while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&bt[0],&bt[1]); getchar(); } printf("到达时间:"); scanf("%d:%d",&at[0],&at[1]); getchar(); while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60) { printf("\n时间输入有误，请重新输入\n"); scanf("%d:%d",&at[0],&at[1]); getchar(); } printf("\n确认?(Y/N)"); c=getchar(); getchar(); if(c=='Y'||c=='y') { i=LocateVertex(G,vt); j=LocateVertex(G,vh); if(i==-1) { printf("\n错误～无法找到起始城市\n"); return; } if(j==-1) { printf("\n错误～无法找到到达城市\n"); return; } q=G->vertices[i].trainfirstarc; m=0; while(q!=NULL) { if(q->adjvex==j) { t=q->info.last+1; q->info.stata[t].number=code; q->info.stata[t].expenditure=money; q->info.stata[t].begintime[0]=bt[0]; q->info.stata[t].begintime[1]=bt[1]; q->info.stata[t].arrivetime[0]=at[0]; - 79 - 2008.7 数据结构课程设计 q->info.stata[t].arrivetime[1]=at[1]; q->info.last=t; m=1; break; } q=q->nextarc; } if(m==0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info.stata[0].number=code; p->info.stata[0].expenditure=money; p->info.stata[0].begintime[0]=bt[0]; p->info.stata[0].begintime[1]=bt[1]; p->info.stata[0].arrivetime[0]=at[0]; p->info.stata[0].arrivetime[1]=at[1]; p->info.last=0; p->nextarc=G->vertices[i].trainfirstarc; G->vertices[i].trainfirstarc=p; G->trainarcnum++; } save(G); } else return; } /****************删除飞机航班***************************/ int DeleteplaneArc(ALGraph *G) { int i,j; int code; char vt[10],vh[10],c; int n; int k; ArcNode *p,*q; printf("\n请输入删除飞机航班的信息:\n"); printf("飞机航班的编号:"); scanf("%d",&code); getchar(); printf("起始城市:"); gets(vt); printf("目的城市:"); gets(vh); - 80 - 数据结构课程设计 printf("\n确认?(Y/N)"); c=getchar(); getchar(); if(c=='Y'||c=='y') { i=LocateVertex(G,vt); j=LocateVertex(G,vh); if(i==-1) { printf("\n错误～无法找到起始城市\n"); return 0; } if(j==-1) { printf("\n错误～无法找到目的城市\n"); return 0; } p=G->vertices[i].planefirstarc; q=p; while(p!=NULL) { if(p->adjvex==j) { n=-1; for(k=0;k<=p->info.last;k++) { if(p->info.stata[k].number==code) { n=k; break; } } if(n!=-1) if(p->info.last==0) { if(q==p) G->vertices[i].planefirstarc=p->nextarc; else q->nextarc=p->nextarc; free(p); } else { for(k=n;kinfo.last;k++) - 81 - 2008.7 数据结构课程设计 { p->info.stata[k].number=p->info.stata[k+1].number; p->info.stata[k].expenditure=p->info.stata[k+1].expenditure; p->info.stata[k].begintime[0]=p->info.stata[k+1].begintime[0]; p->info.stata[k].begintime[1]=p->info.stata[k+1].begintime[1]; p->info.stata[k].arrivetime[0]=p->info.stata[k+1].arrivetime[0]; p->info.stata[k].arrivetime[1]=p->info.stata[k+1].arrivetime[1]; } p->info.last=p->info.last-1; } else printf("\n在此两城市之间无法找到No.%d飞机航班\n",code); save(G); return 0; } q=p; p=p->nextarc; } if(p==NULL) printf("\n在此两城市之间无飞机航班存在\n"); } else return 1; return 1; } /***************删除列车车次********************/ int DeletetrainArc(ALGraph *G) { int i,j; int code; char vt[10],vh[10],c; int n; int k; ArcNode *p,*q; printf("\n请输入删除列车车次的信息:\n"); printf("列车车次的编号:"); scanf("%d",&code); getchar(); printf("起始城市:"); gets(vt); printf("目的城市:"); gets(vh); printf("\n确认?(Y/N)"); c=getchar(); - 82 - 数据结构课程设计 getchar(); if(c=='Y'||c=='y') { i=LocateVertex(G,vt); j=LocateVertex(G,vh); if(i==-1) { printf("\n错误～无法找到起始城市\n"); return 0; } if(j==-1) { printf("\n错误～无法找到目的城市\n"); return 0; } p=G->vertices[i].trainfirstarc; q=p; while(p!=NULL) { if(p->adjvex==j) { n=-1; for(k=0;k<=p->info.last;k++) { if(p->info.stata[k].number==code) { n=k; break; } } if(n!=-1) if(p->info.last==0) { if(q==p) G->vertices[i].trainfirstarc=p->nextarc; else q->nextarc=p->nextarc; free(p); } else { for(k=n;kinfo.last;k++) { p->info.stata[k].number=p->info.stata[k+1].number; - 83 - 2008.7 数据结构课程设计 p->info.stata[k].expenditure=p->info.stata[k+1].expenditure; p->info.stata[k].begintime[0]=p->info.stata[k+1].begintime[0]; p->info.stata[k].begintime[1]=p->info.stata[k+1].begintime[1]; p->info.stata[k].arrivetime[0]=p->info.stata[k+1].arrivetime[0]; p->info.stata[k].arrivetime[1]=p->info.stata[k+1].arrivetime[1]; } p->info.last=p->info.last-1; } else printf("\n在此两城市之间无法找到No.%d列车车次\n",code); save(G); return 0; } q=p; p=p->nextarc; } if(p==NULL) printf("\n在此两城市之间无列车车次存在\n"); } else return 0; return 1; } /**************用户咨询项目选择界面************************/ void UserDemand(ALGraph G) { int i; char q; printf("\n请选择咨询项目:\n"); printf("1=最少旅行费用\n2=最少旅行时间\n3=最少旅行中转次数\n4=返回上一级菜单\n"); printf("选择?"); scanf("%d",&i); getchar(); while(i!=4) { switch(i) { case 1:DemandDispose(1,G);break; /*最少费用，时间，中转 次数*/ case 2:DemandDispose(2,G);break; case 3:DemandDispose(3,G);break; } printf("按回车继续\n"); scanf("%c",&q); scanf("%c",&q); - 84 - 数据结构课程设计 printf("请选择咨询项目:\n"); printf("1=最少旅行费用\n2=最少旅行时间\n3=最少旅行中转次数\n4=返回上一级菜单 \n"); printf("选择?"); scanf("%d",&i); getchar(); } return ; } /********************用户咨询选择信息输入界面,通过该子程序调用其他咨询子程序 ***************/ void DemandDispose(int n,ALGraph G) { char q; ArcNode *plane,*train; infolist planearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM],trainarcs[MAX_VERTEX_NUM][MAX_VE RTEX_NUM]; int i,j,k,final[MAX_VERTEX_NUM],T[MAX_VERTEX_NUM][2]; float M[MAX_VERTEX_NUM]; for(i=0;iadjvex]=plane->info; - 85 - 2008.7 数据结构课程设计 plane=plane->nextarc; } while(train!=NULL) { trainarcs[i][train->adjvex]=train->info; train=train->nextarc; } } printf("\n请选择旅行起始城市:\n"); for(k=0;kfront=(QNode *)malloc(sizeof(QNode)); Q->rear=Q->front; Q->front->next=NULL; } /************** 入队操作，插入元素x为Q的新的队列元素******************/ void EnterQueue(LinkQueue *Q,int x) { QNode *newnode; newnode=(QNode *)malloc(sizeof(QNode)); newnode->adjvex=x; newnode->next=NULL; Q->rear->next=newnode; Q->rear=newnode; } /******************** 出队操作**************************/ void DeleteQueue(LinkQueue *Q,int *x) { QNode *p; p=Q->front->next; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; *x=p->adjvex; free(p); } /***********************队列判空操作*************************/ int IsEmpty(LinkQueue *Q) { if(Q->front==Q->rear) return(1); else return(0); } /******************采用基于邻接表的广度优先算法最少旅行中转次数处理 ********************/ void TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1) { - 87 - 2008.7 数据结构课程设计 int visited[MAX_VERTEX_NUM],v,w,n=1; LinkQueue Q; ArcNode *t; Node *p,*q,*r,*s; p=(Node *)malloc(G.vexnum*sizeof(Node)); for(v=0;vadjvex=v0; q->next=NULL; p[v0].next=q; EnterQueue(&Q,v0); while(!IsEmpty(&Q)) //队列不空 { DeleteQueue(&Q,&v); if(k==1) t=G.vertices[v].trainfirstarc; else t=G.vertices[v].planefirstarc; while(t!=NULL) { w=t->adjvex; //w为与城市v相连的第一个城市 if(!visited[w]) //城市w未访问 { visited[w]=1; //将城市w设为已访问 q=&p[w]; s=p[v].next; while(s!=NULL) { r=(Node *)malloc(sizeof(Node)); r->adjvex=s->adjvex; q->next=r; q=r; s=s->next; } r=(Node *)malloc(sizeof(Node)); r->adjvex=w; r->next=NULL; q->next=r; - 88 - 数据结构课程设计 if(w==v1) //w等于v1 { q=p[w].next; r=q->next; printf("\n旅行路线是:\n"); while(r!=NULL) { if(k==1) printf("乘坐No.%d列车车次在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begi ntime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices [r->adjvex].cityname); else printf("乘坐No.%d飞机航班在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begi ntime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices [r->adjvex].cityname); q=r; r=r->next; n++; } printf("最少中转次数是%d次\n\n",n-2); for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); return; } EnterQueue(&Q,w); // 将城市w入队 } t=t->nextarc; //w等于城市v相连的下一个城市 } } for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); if(k==1) printf("\n不存在列车车次从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); else printf("\n不存在飞机航班从%s到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); } /********** 两直达城市之间最少旅行费用和相应路径************/ void MinExpenditure(infolist arcs,float *expenditure,int *route) { int i; *expenditure=arcs.stata[0].expenditure; if(*expenditureadjvex=v0; s->adjvex=v; s->route=route; p[v].next=q; q->next=s; s->next=NULL; } } *(M+v0)=0; // 城市v0到城市v0的最少费用为0 *(final+v0)=True; //城市v0设为已求得最少费用 for(i=1;inext; printf("\n旅行路线是:\n"); while(r!=NULL) { if(k==1) printf("乘坐No.%d列车车次在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[ r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex ].cityname,G.vertices[r->adjvex].cityname); else printf("乘坐No.%d飞机航班在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[ r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex - 91 - 2008.7 数据结构课程设计 ].cityname,G.vertices[r->adjvex].cityname); q=r; r=r->next; } printf("最少旅行费用是%f元\n\n",m); for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); return; } else if(v!=-1) { *(final+v)=True; //将城市v设为已求得最少费用 for(w=0;w-1) { MinExpenditure(*(*(arcs+v)+w),&expenditure,&route); if(*(M+w)>m+expenditure) { *(M+w)=m+expenditure; q=p[w].next; while(q!=NULL) { s=q; q=q->next; free(s); } q=&p[w]; s=p[v].next; while(s!=NULL) { r=(Node *)malloc(sizeof(Node)); r->adjvex=s->adjvex; r->route=s->route; q->next=r; - 92 - 数据结构课程设计 q=r; s=s->next; } r=(Node *)malloc(sizeof(Node)); r->adjvex=w; r->route=route; r->next=NULL; q->next=r; } } } } for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); if(k==1) printf("\n不存在列车车次从%s 到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); else printf("\n不存在飞机航班从%s 到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); } /*******************两直达城市之间最少旅行时间和相应路径**********************/ void MinTime(infolist arcs,int *time,int *route) { int i,t[2]; time[0]=arcs.stata[0].arrivetime[0]-arcs.stata[0].begintime[0]; time[1]=arcs.stata[0].arrivetime[1]-arcs.stata[0].begintime[1]; if(time[0]<0) time[0]=time[0]+24; if(time[1]<0) { time[0]--; time[1]=time[1]+60; } - 93 - 2008.7 数据结构课程设计 *route=0; for(i=1;i<=arcs.last;i++) { t[0]=arcs.stata[i].arrivetime[0]-arcs.stata[i].begintime[0]; t[1]=arcs.stata[i].arrivetime[1]-arcs.stata[i].begintime[1]; if(t[0]<0) t[0]=t[0]+24; if(t[1]<0) { t[0]--; t[1]=t[1]+60; } if(t[0]next; while(p!=NULL) { EnterQueue(&Q,p->adjvex); p=p->next; } DeleteQueue(&Q,&i); root->adjvex=i; DeleteQueue(&Q,&j); CreateTimeTree(root,i,j,&Q,arcs); for(n=0;n<=(*(*(arcs+i)+j)).last;n++) { time1[0]=0; - 94 - 数据结构课程设计 time1[1]=0; time2[0]=root->child[n]->begintime[0]; time2[1]=root->child[n]->begintime[1]; time[0]=INFINITY; time[1]=INFINITY; VisitTimeTree(root->child[n]); if(time[0]next; while(p!=NULL) { p->route=d[p->adjvex]; p=p->next; } } } DestoryTimeTree(root); } /*****************创建时间树********************/ void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM]) { int n,x,y; TimeTree q; q=(TimeNode *)malloc(sizeof(TimeNode)); q->adjvex=j; q->begintime[0]=(*(*(arcs+i)+j)).stata[0].begintime[0]; q->begintime[1]=(*(*(arcs+i)+j)).stata[0].begintime[1]; q->arrivetime[0]=(*(*(arcs+i)+j)).stata[0].arrivetime[0]; q->arrivetime[1]=(*(*(arcs+i)+j)).stata[0].arrivetime[1]; q->route=0; p->child[0]=q; for(n=1;n<=(*(*(arcs+i)+j)).last;n++) { q=(TimeNode *)malloc(sizeof(TimeNode)); q->adjvex=j; q->begintime[0]=(*(*(arcs+i)+j)).stata[n].begintime[0]; q->begintime[1]=(*(*(arcs+i)+j)).stata[n].begintime[1]; q->arrivetime[0]=(*(*(arcs+i)+j)).stata[n].arrivetime[0]; q->arrivetime[1]=(*(*(arcs+i)+j)).stata[n].arrivetime[1]; q->route=n; p->child[n]=q; } - 95 - 2008.7 数据结构课程设计 while(nchild[n]=NULL; n++; } x=j; if(!IsEmpty(Q)) { DeleteQueue(Q,&y); CreateTimeTree(p->child[0],x,y,Q,arcs); for(n=1;n<=(*(*(arcs+i)+j)).last;n++) CopyTimeTree(p->child[n],p->child[0]); } else { for(n=0;nchild[0]->child[n]=NULL; for(n=1;n<=(*(*(arcs+i)+j)).last;n++) CopyTimeTree(p->child[n],p->child[0]); } return ; } /******************************复制时间树***********************************/ void CopyTimeTree(TimeTree p,TimeTree q) { TimeTree r; int n=0; while(q->child[n]!=NULL) { r=(TimeNode *)malloc(sizeof(TimeNode)); r->adjvex=q->child[n]->adjvex; r->begintime[0]=q->child[n]->begintime[0]; r->begintime[1]=q->child[n]->begintime[1]; r->arrivetime[0]=q->child[n]->arrivetime[0]; r->arrivetime[1]=q->child[n]->arrivetime[1]; r->route=q->child[n]->route; p->child[n]=r; CopyTimeTree(p->child[n],q->child[n]); n++; } while(nchild[n]=NULL; n++; - 96 - 数据结构课程设计 } return ; } /****************** 访问时间树界面***********************/ void VisitTimeTree(TimeTree p) { int n,x[2],y[2]; //TimeTree q; x[0]=time1[0]; x[1]=time1[1]; y[0]=time2[0]; y[1]=time2[1]; if(p->begintime[0]>time2[0]||(p->begintime[0]==time2[0]&&p->begintime[1]>=time2[1])) { time1[0]=time1[0]+p->begintime[0]-time2[0]; time1[1]=time1[1]+p->begintime[1]-time2[1]; if(time1[1]<0) { time1[1]=time1[1]+60; time1[0]--; } if(time1[1]>=60) { time1[1]=time1[1]-60; time1[0]++; } } else if(p->begintime[0]begintime[0]==time2[0]&&p->begintime[1]begintime[0]-time2[0]+24; time1[1]=time1[1]+p->begintime[1]-time2[1]; if(time1[1]<0) { time1[1]=time1[1]+60; time1[0]--; } if(time1[1]>=60) { time1[1]=time1[1]-60; time1[0]++; } } if(p->arrivetime[0]>p->begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]>=p->begint - 97 - 2008.7 数据结构课程设计 ime[1])) { time1[0]=time1[0]+p->arrivetime[0]-p->begintime[0]; time1[1]=time1[1]+p->arrivetime[1]-p->begintime[1]; if(time1[1]<0) { time1[1]=time1[1]+60; time1[0]--; } if(time1[1]>=60) { time1[1]=time1[1]-60; time1[0]++; } } else if(p->arrivetime[0]begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]beginti me[1])) { time1[0]=time1[0]+p->arrivetime[0]-p->begintime[0]+24; time1[1]=time1[1]+p->arrivetime[1]-p->begintime[1]; if(time1[1]<0) { time1[1]=time1[1]+60; time1[0]--; } if(time1[1]>=60) { time1[1]=time1[1]-60; time1[0]++; } } time2[0]=p->arrivetime[0]; time2[1]=p->arrivetime[1]; c[p->adjvex]=p->route; if(p->child[0]==NULL) { if(time1[0]child[n]!=NULL) { VisitTimeTree(p->child[n]); n++; } } time1[0]=x[0]; time1[1]=x[1]; time2[0]=y[0]; time2[1]=y[1]; } /************************* 销毁时间树*********************************/ void DestoryTimeTree(TimeTree p) { if(p!=NULL) { DestoryTimeTree(p->child[0]); DestoryTimeTree(p->child[1]); DestoryTimeTree(p->child[2]); DestoryTimeTree(p->child[3]); DestoryTimeTree(p->child[4]); p->child[0]=NULL; p->child[1]=NULL; p->child[2]=NULL; p->child[3]=NULL; p->child[4]=NULL; free(p); } return ; } /**************************采用基于邻接表的迪杰特斯拉算法最少旅行时间处理 *****************************************************/ void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final) { int v,w,i,route,m[2]; Node *p,*q,*r,*s,*t; p=(Node *)malloc(G.vexnum*sizeof(Node)); for(v=0;vadjvex=v0; s->adjvex=v; s->route=route; p[v].next=q; q->next=s; s->next=NULL; } } *(*(T+v0)+0)=0; // 城市v0到城市v0的最少时间为0 *(*(T+v0)+1)=0; *(final+v0)=True; //城市v0设为已求得最少时间 for(i=1;inext; printf("\n旅行路线是:\n"); while(r!=NULL) { if(k==1) printf("乘坐No.%d列车车次在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[ r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex ].cityname,G.vertices[r->adjvex].cityname); - 100 - 数据结构课程设计 else printf("乘坐No.%d飞机航班在%d:%d从%s 到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[ r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex ].cityname,G.vertices[r->adjvex].cityname); q=r; r=r->next; } printf("最少旅行时间是%d:%d\n\n",m[0],m[1]); for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); return ; } else if(v!=-1) { *(final+v)=True; for(w=0;w-1) { t=p[w].next; q=&p[w]; s=p[v].next; while(s!=NULL) { r=(Node *)malloc(sizeof(Node)); r->adjvex=s->adjvex; r->route=s->route; q->next=r; q=r; s=s->next; } r=(Node *)malloc(sizeof(Node)); r->adjvex=w; r->route=route; - 101 - 2008.7 数据结构课程设计 r->next=NULL; q->next=r; TimeTreeDispose(&p[w],arcs); if(*(*(T+w)+0)>TTime[0]||(*(*(T+w)+0)==TTime[0]&&*(*(T+w)+1)>TTime[1])) { *(*(T+w)+0)=TTime[0]; *(*(T+w)+1)=TTime[1]; while(t!=NULL) { q=t; t=t->next; free(q); } } else { q=p[w].next; while(q!=NULL) { r=q; q=q->next; free(r); } p[w].next=t; } } } } for(v=0;vnext; free(s); } p[v].next=NULL; } free(p); if(k==1) printf("\n不存在列车车次从%s 到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); - 102 - 数据结构课程设计 else printf("\n不存在飞机航班从%s 到%s\n\n",G.vertices[v0].cityname,G.vertices[v1].cityname); } /******************************* 显示城市交通系统 ************************************************/ void PrintGraph(ALGraph *G) { int i,j,k; ArcNode *q; printf("\n请选择显示项目:\n"); printf("0=显示城市\n1=显示飞机航班\n2=显示列车车次\n3=返回上一级菜单\n"); printf("选择?"); scanf("%d",&i); getchar(); while(i!=3) { switch(i) { case 0:printf("\n城市:\n"); for(j=0;jvexnum;j++) printf("%s ",G->vertices[j].cityname); printf("\n"); break; case 1:printf("\n飞机航班:\n"); for(j=0;jvexnum;j++) { q=G->vertices[j].planefirstarc; while(q!=NULL) { printf("%s---->%s\n",G->vertices[j].cityname,G->vertices[q->adjvex].cityname); for(k=0;k<=q->info.last;k++) { printf(" number:%d expenditure:%5.2f \n",q->info.stata[k].number,q->info.stata[k].expenditure); printf("begintime:%d:%d arrivetime:%d:%d\n",q->info.stata[k].begintime[0],q->info.stata[k].begintime[1],q->info.stata[k].arrivetim e[0],q->info.stata[k].arrivetime[1]); } q=q->nextarc; } } break; - 103 - 2008.7 数据结构课程设计 case 2:printf("\n列车车次:\n"); for(j=0;jvexnum;j++) { q=G->vertices[j].trainfirstarc; while(q!=NULL) { printf("%s---->%s\n",G->vertices[j].cityname,G->vertices[q->adjvex].cityname); for(k=0;k<=q->info.last;k++) { printf(" number:%d expenditure:%5.2f \n",q->info.stata[k].number,q->info.stata[k].expenditure); printf("begintime:%d:%d arrivetime:%d:%d\n",q->info.stata[k].begintime[0],q->info.stata[k].begintime[1],q->info.stata[k].arrivetim e[0],q->info.stata[k].arrivetime[1]); } q=q->nextarc; } } break; } printf("\n请选择显示项目:\n"); printf("0=显示城市\n1=显示飞机航班\n2=显示列车车次\n3=返回上一级菜单\n"); printf("选择?"); scanf("%d",&i); getchar(); } } - 104 - 数据结构课程设计 - 105 -