一、设计目的
本课程设计是软件工程学生的必修课程，数据结构与算法课程设计既是一门基础课程，又是一门实践性课程。通过本实训课程的学习和训练，使同学学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理；加深理解数据结构中的逻辑结构和物理结构，掌握其基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后续课程打好基础。
二、设计任务及要求
项目一：学生信息管理
项目简介：
学生信息管理是学校教务部门日常工作的重要组成部分。本项目是对学生信息管理的简单模拟，包含两个模块：基本信息查询和成绩管理。
数据要求：
每个学生的信息包括：学号、姓名、性别、出生年月、电话、住址。成绩设置为五门课程成绩，后续可扩展。数据可直接输入输出，也可以采用文件存储。
功能要求：
至少包含下列基本功能，可增加功能计入加分项，缺少功能减分
1：学生基本信息的增加。
2：通过输入学号或者姓名实现基本信息的查询、修改、删除。
3：通过输入学号或者姓名实现成绩的输入、查询、修改。
4：对成绩进行降序排列，要求可以按照总分或者某一门指定课程排序。
界面要求：
根据系统功能要求设计。应有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
设计思路：
本项目的实质是完成对学生成绩信息的建立、查找、插入、修改、删除、排序等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
数据结构：
本项目的数据是一组学生的信息，这组信息具有相同特性，属于同一数据对象，相邻数据元素之间通过学号存在序偶关系。由此可以看出，这些数据具有线性表中数据元素的性质，所以该系统的数据可以采用线性表来存储。
模块功能：
结构体：
typedef struct student//学生信息结构体
{
char sno[15];
char sname[20];
int sex;//0表示女性，1表示男性
char birthday[15];
char tnum[15];
char address[20];
int score[10];
}student;
typedef struct listnode//链表结点
{
student data;
struct listnode *next;
}listnode;
函数：
void Add_student()//添加学生信息
void Browse_student()//浏览学生信息
void query_student()//查询学生信息
void alter_student()//修改学生信息
void delete_student()//删除学生信息
void Add_score()//添加成绩信息
void Browse_score()//浏览成绩信息
void query_score()//查询成绩信息
void alter_score()//修改成绩信息
void sort_score()//排序成绩信息
void alter_scorenum()//修改成绩数目
void meau1();//学生基本信息页
void meau2();//学生成绩页
void meau0()//首页
程序截图：
主菜单界面：
基本信息管理页面
成绩管理页面
源码：
#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct student//学生信息结构体 {char sno[15];char sname[20];int sex;//0表示女性，1表示男性char birthday[15];char tnum[15];char address[20]; int score[10];}student;typedef struct listnode//链表结点 {student data;struct listnode *next;}listnode;struct listnode *head;int count=0;//学生记录总数 int scorecount=5;void Add_student()//添加学生信息{int num; int i;while(1){printf("录入学生信息，请选择：1.输入数据 0.返回\n"); scanf("%d",&num);if(num==1){struct listnode *temp=(struct listnode*)malloc(sizeof(struct listnode));temp->next=head->next;//头插法 head->next=temp;count++; printf("学号："); scanf("%s",temp->data.sno); printf("姓名：");scanf("%s",temp->data.sname);while(1){printf("性别(0表示女性，1表示男性)：");scanf("%d",&temp->data.sex);if(temp->data.sex!=1 && temp->data.sex!=0)printf("请输入正确的性别序号!\n");elsebreak;}printf("出生日期(如-01-01)：");scanf("%s",temp->data.birthday);printf("电话：");scanf("%s",temp->data.tnum);printf("地址：");scanf("%s",temp->data.address);for(i=1;i<=scorecount;i++)//学生成绩初始化为0 temp->data.score[i]=0;}else if(num==0){system("cls");meau1();return;}elseprintf("请输入正确的序号！\n");};} void Browse_student()//浏览学生信息 {struct listnode *p=head;printf("学号 姓名 性别 生日 电话 地址\n"); while(p->next!=NULL){p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);if(p->data.sex==1)printf("男");else if(p->data.sex==0)printf("女");printf("%-18s",p->data.birthday);printf("%-16s",p->data.tnum);printf("%-20s",p->data.address);printf("\n");}getchar();getchar();//小黑窗停留}void query_student()//查询学生信息{int num;char sno[15];char sname[20];struct listnode *p=head;printf("1.输入学号查询2.输入姓名查询0.返回\n");scanf("%d",&num);if(num==0){system("cls");meau1();return;}else if(num==1){printf("请输入待查找的学号：");scanf("%s",sno);while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){printf("学号 姓名 性别 生日 电话 地址\n"); p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);if(p->data.sex==1)printf("男");else if(p->data.sex==0)printf("女");printf("%-18s",p->data.birthday);printf("%-16s",p->data.tnum);printf("%-20s",p->data.address);printf("\n");query_student();return;}p=p->next;} printf("没找到\n");query_student();return;p=head;//初始化头指针 }else if(num==2){printf("请输入待查找的姓名：");scanf("%s",sname); while(p->next!=NULL){if(strcmp(p->next->data.sname,sname)==0){printf("学号 姓名 性别 生日 电话 地址\n"); p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);if(p->data.sex==1)printf("男");else if(p->data.sex==0)printf("女");printf("%-18s",p->data.birthday);printf("%-16s",p->data.tnum);printf("%-20s",p->data.address);printf("\n");query_student();return;}p=p->next;} printf("没找到\n");query_student();return;}else{printf("请输入正确的序号！\n");query_student();return;}} void alter_student()//修改学生信息{int num;char sno[15];char sname[20];struct listnode *p=head;printf("1.输入学号修改2.输入姓名修改0.返回\n");scanf("%d",&num);if(num==0){system("cls");meau1();return;}else if(num==1){printf("请输入待修改记录的学号：\n"); scanf("%s",sno); while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){printf("请输入要修改的选项(学号1，姓名2，性别3，生日4，电话5，地址6)\n");scanf("%d",&num);switch(num){case 1:scanf("%s",p->next->data.sno);break;case 2:scanf("%s",p->next->data.sname);break;case 3:scanf("%d",&p->next->data.sex);break;case 4:scanf("%s",p->next->data.birthday);break;case 5:scanf("%s",p->next->data.tnum);break;case 6:scanf("%s",p->next->data.address);break;}printf("修改成功，记录更新为：\n");printf("学号 姓名 性别 生日 电话 地址\n"); p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);if(p->data.sex==1)printf("男");else if(p->data.sex==0)printf("女");printf("%-18s",p->data.birthday);printf("%-16s",p->data.tnum);printf("%-20s",p->data.address);printf("\n"); alter_student();return;}p=p->next;} printf("没找到\n");alter_student();p=head;//初始化头指针 }else if(num==2){printf("请输入待修改记录的姓名："); scanf("%s",sname);while(p->next!=NULL){if(strcmp(p->next->data.sname,sname)==0){printf("请输入要修改的选项(学号1，姓名2，性别3，生日4，电话5，地址6)\n");scanf("%d",&num);switch(num){case 1:scanf("%s",p->next->data.sno);break;case 2:scanf("%s",p->next->data.sname);break;case 3:scanf("%d",&p->next->data.sex);break;case 4:scanf("%s",p->next->data.birthday);break;case 5:scanf("%s",p->next->data.tnum);break;case 6:scanf("%s",p->next->data.address);break;}printf("修改成功，记录更新为：\n");printf("学号 姓名 性别 生日 电话 地址\n"); p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);if(p->data.sex==1)printf("男");else if(p->data.sex==0)printf("女");printf("%-18s",p->data.birthday);printf("%-16s",p->data.tnum);printf("%-20s",p->data.address);alter_student();return;}p=p->next;} printf("没找到\n");alter_student();}else{printf("请输入正确的序号！\n");alter_student();}} void delete_student()//删除学生信息 {struct listnode *p=head;int num; char sno[15];char sname[20];printf("1.输入学号删除记录2.输入姓名删除记录0.返回\n"); scanf("%d",&num);if(num==0){system("cls");meau1();return;} else if(num==1){if(p->next==NULL){printf("暂无学生信息\n");delete_student();return;}else{scanf("%s",sno);while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){p->next=p->next->next;printf("已删除学号为%s的记录\n",sno);delete_student();return;}p=p->next;} printf("没找到\n");delete_student();return;}}else if(num==2){if(p->next==NULL){printf("暂无学生信息\n");delete_student();return;}else{scanf("%s",sname);while(p->next!=NULL){if(strcmp(p->next->data.sname,sname)==0){p->next=p->next->next;printf("已删除姓名为%s的记录\n",sname);alter_student();return;}p=p->next;} printf("没找到\n");delete_student();return;}}else{printf("请输入正确的序号！\n");delete_student();return;}}void Add_score()//添加成绩信息{char sno[15];struct listnode *p=head;int i;printf("请输入要录入成绩的学生学号：\n");scanf("%s",sno);while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){printf("请输入%d门成绩\n",scorecount);for(i=1;i<=scorecount;i++)scanf("%d",&p->next->data.score[i]); printf("输入成功！\n");printf("请按任意键继续...");getchar();getchar();system("cls");meau2();return;}p=p->next;} printf("没找到该学号学生\n");printf("请按任意键继续...");getchar(); getchar();system("cls");meau2();return;}void Browse_score()//浏览成绩信息 {struct listnode *p=head;int i;printf("学号 姓名 "); for(i=1;i<=scorecount;i++)printf("成绩%d",i);printf("\n");while(p->next!=NULL){p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);for(i=1;i<=scorecount;i++)printf("%-8d",p->data.score[i]);printf("\n");}getchar();getchar();//小黑窗停留system("cls");meau2();return;}void query_score()//查询成绩信息{int num;char sno[15];char sname[20];int i;struct listnode *p=head;printf("1.输入学号查询2.输入姓名查询0.返回\n");scanf("%d",&num);if(num==0){system("cls");meau2();return;}else if(num==1){printf("请输入待查找的学号：");scanf("%s",sno);while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){printf("学号 姓名 "); for(i=1;i<=scorecount;i++)printf("成绩%d",i);printf("\n");p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);for(i=1;i<=scorecount;i++)printf("%-8d",p->data.score[i]);printf("\n");getchar();getchar();system("cls"); meau2();return;}p=p->next;} printf("没找到该学号的成绩\n");query_score();p=head;//初始化头指针 return;}else if(num==2){printf("请输入待查找的姓名：");scanf("%s",sname);while(p->next!=NULL){if(strcmp(p->next->data.sname,sname)==0){printf("学号 姓名 "); for(i=1;i<=scorecount;i++)printf("成绩%d",i);printf("\n");p=p->next;printf("%-17s",p->data.sno);printf("%-16s",p->data.sname);for(i=1;i<=scorecount;i++)printf("%-8d",p->data.score[i]);printf("\n");getchar();getchar();system("cls"); meau2();return;}p=p->next;} printf("没找到该姓名的成绩\n");query_score();p=head;//初始化头指针 return;}else{printf("请输入正确的序号！\n");query_student();return;}}void alter_score()//修改成绩信息{int num;char sno[15];char sname[20];struct listnode *p=head;printf("1.输入学号修改2.输入姓名修改0.返回\n");scanf("%d",&num);if(num==0){system("cls");meau2();return;}else if(num==1){printf("请输入待修改成绩的学号：\n"); scanf("%s",sno); while(p->next!=NULL){if(strcmp(p->next->data.sno,sno)==0){printf("请输入要修改的分数序列(序号从1开始)\n");scanf("%d",&num);printf("原成绩为%d,请输入新的成绩：",p->next->data.score[num]); scanf("%d",&p->next->data.score[num]);printf("修改成功，记录已更新!\n");alter_score();return;}p=p->next;} printf("没找到\n");alter_score();p=head;//初始化头指针 }else if(num==2){printf("请输入待修改成绩的姓名："); scanf("%s",sname);while(p->next!=NULL){if(strcmp(p->next->data.sname,sname)==0){printf("请输入要修改的分数序列(序号从1开始)\n");scanf("%d",&num);printf("原成绩为%d,请输入新的成绩：",p->next->data.score[num]); scanf("%d",&p->next->data.score[num]);printf("修改成功，记录已更新!\n");alter_score();return;}p=p->next;} printf("没找到\n");alter_score();return;}else{printf("请输入正确的序号！\n");alter_score();return;}}void sort_score()//排序成绩信息{struct listnode *p=head;student sort[100];student temp;int num; int s=1;int i,j;int sum[100]={0};int k;//排序科目序号 while(p->next!=NULL)//把所有学生信息存到一个数组 {i=1;sort[s]=p->next->data;for(i=1;i<=scorecount;i++)//计算成绩总分 sum[s]=sum[s]+sort[i].score[i];p=p->next;s++;//记录长度 }p=head;//初始化头指针 printf("1.根据姓氏排序2.根据总分排序3.根据某门课程排序0.返回\n");scanf("%d",&num);if(num==1){if(p->next==NULL)//空记录情况 {printf("不存在学生记录，无法排序！\n");printf("请按回车键继续..."); getchar();getchar();system("cls");meau2(); return; }printf("请输入排序方式（降序0，升序1）\n"); scanf("%d",&num); if(num==1){for(i=1;i<=s-1;i++)//升序 {for(j=1;j<=s-1-i;j++){printf("*");if(strcmp(sort[j].sname,sort[j+1].sname)>0)//第一个大于第二个 {temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}} else if(num==0){for(i=1;i<=s-1;i++)//降序 {for(j=1;j<=s-1-i;j++){if(strcmp(sort[j].sname,sort[j+1].sname)<0){temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}}}else if(num==2){if(p->next==NULL)//空记录情况 {printf("不存在学生记录，无法排序！\n");printf("请按回车键继续..."); getchar();getchar();system("cls");meau2(); return; }printf("请输入排序方式（降序0，升序1）\n"); scanf("%d",&num); if(num==1){for(i=1;i<=s-1;i++)//升序 {for(j=1;j<=s-1-i;j++){if(sum[j]>sum[j+1])//第一个大于第二个 {temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}} else if(num==0){for(i=1;i<=s-1;i++)//降序 {for(j=1;j<=s-1-i;j++){if(sum[j]<sum[j+1]){temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}}}else if(num==3){if(p->next==NULL)//空记录情况 {printf("不存在学生记录，无法排序！\n");printf("请按回车键继续..."); getchar();getchar();system("cls");meau2(); return; }printf("请输入排序科目序号（从1开始）：");scanf("%d",&k); printf("请输入排序方式（降序0，升序1）\n"); scanf("%d",&num); if(num==1){for(i=1;i<=s-1;i++)//升序 {for(j=1;j<=s-1-i;j++){if(sort[j].score[k]>sort[j+1].score[k])//第一个大于第二个 {temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}} else if(num==0){for(i=1;i<=s-1;i++)//降序 {for(j=1;j<=s-1-i;j++){if(sort[j].score[k]<sort[j+1].score[k]){temp=sort[j];sort[j]=sort[j+1];sort[j+1]=temp;}}}}}else if(num==0){system("cls");meau2();return;}else{printf("请输入正确的序号！\n");sort_score();return;}printf("学号 姓名 "); for(i=1;i<=scorecount;i++)printf("成绩%d",i);printf("\n");for(i=1;i<s;i++){printf("%-17s",sort[i].sno);printf("%-16s",sort[i].sname);for(j=1;j<=scorecount;j++)printf("%-7d ",sort[i].score[j]);printf("\n");}getchar();getchar();system("cls");meau2();}void alter_scorenum()//修改成绩数目 {struct listnode *p=head;int i;int nowcount=scorecount;printf("请输入要修改为几门成绩：");scanf ("%d",&scorecount);while(p->next!=NULL){for(i=nowcount+1;i<=scorecount;i++)//把新增的几门成绩初始化为0 ，原有的成绩不作修改 p->next->data.score[i]=0;p=p->next;}printf("修改成功！\n");printf("请按回车键返回！");getchar();getchar();system("cls");meau2();}void meau1();//学生基本信息页 void meau2();//学生成绩页 void meau0()//首页 {int num;do{printf("\n");printf("\n");printf("*****************欢迎进入学生信息管理系统******************\n");printf("\n");printf("1.基本信息管理\n");printf("2.成绩管理\n");printf("0.退出\n");printf("\n");printf("*************************谢谢使用*************************\n");printf("\n");printf("请输入序号：");scanf("%d",&num);switch(num){case 1:system("cls");meau1();break;case 2:system("cls");meau2();break;case 0:exit(1);default:system("cls"); printf("输入的序号有误，请重新输入！\n");} }while(num!=0 && num!=1 && num!=2);}void meau1()//学生基本信息管理页面 {int num;do{printf("\n");printf("\n");printf("*********************学生基本信息管理*********************\n");printf("\n");printf("1.添加学生信息2.浏览学生信息\n");printf("3.查询学生信息4.修改学生信息\n");printf("5.删除学生信息0.退出\n");printf("\n");printf("*************************谢谢使用*************************\n");printf("\n");printf("请输入序号：");scanf("%d",&num);switch(num){case 1:Add_student();//添加学生信息break;case 2:Browse_student();//浏览学生信息 system("cls");meau1();break;case 3:query_student();//查询学生信息break;case 4:alter_student();//修改学生信息break;case 5:delete_student();//删除学生信息break;case 0:system("cls");meau0(); //返回到首页菜单 break;default:system("cls");printf("输入的序号有误，请重新输入！\n");} }while(num!=0 && num!=1 && num!=2 && num!=3 && num!=4 && num!=5);}void meau2()//学生成绩管理页面 {int num;do{printf("\n");printf("\n");printf("***********************学生成绩管理***********************\n");printf("\n");printf("1.添加成绩信息2.浏览成绩信息\n");printf("3.查询成绩信息4.修改成绩信息\n");printf("5.排序成绩信息6.修改成绩数量\n");printf("0.退出\n");printf("\n");printf("*************************谢谢使用*************************\n");printf("\n");printf("请输入序号：");scanf("%d",&num);switch(num){case 1:Add_score();//添加成绩信息break;case 2:Browse_score();//浏览成绩信息 break;case 3:query_score();//查询成绩信息break;case 4:alter_score();//修改成绩信息break;case 5:sort_score();//排序成绩信息break;case 6:alter_scorenum();break;case 0:system("cls");meau0(); //返回到首页菜单 break;default:system("cls");printf("输入的序号有误，请重新输入！\n");} }while(num!=0 && num!=1 && num!=2 && num!=3 && num!=4 && num!=5 && num!=6);}int main(){head=(struct listnode*)malloc(sizeof(struct listnode));//链表头指针head->next=NULL;meau0();return 0;}
项目二 简易停车场管理
项目简介：
设停车场是一个可以停放n辆汽车的南北方向的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
数据要求：
车辆信息包括：车牌号。
功能要求：
至少包含下列基本功能，可增加功能计入加分项，缺少功能减分
1：进场前显示剩余车位。
2：输出每辆车到达后的停车位置（停车场或便道上）。
3：统计输出某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。
4：对于错误操作能给出相应说明，如某个车牌未在停车场内，进行出场操作给出相应提示。
界面要求：
根据系统功能要求设计。应有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
设计思路：
停车场的管理流程如下：
①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进入停车场；如果停车场已满，则车辆进入便道等候。
②当车辆要求出栈时，先让在它之后进入停车场的车辆退出停车场为它让路，再让该车退出停车场，让路的所有车辆再按其原来进入停车场的次序进入停车场。之后，再检查在便道上是否有车等候，有车则让最先等待的那辆车进入停车场。
数据结构：
由于停车场只有一个大门，当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，先进停车场的后退出，后进车场的先退出，符合栈的“后进先出，先进后出”的操作特点，因此，可以用一个栈来模拟停车场。而当停车场满后，继续来到的其它车辆只能停在便道上，根据便道停车的特点，先排队的车辆先离开便道进入停车场，符合队列的“先进先出，后进后出”的操作特点，因此，可以用一个队列来模拟便道。排在停车场中间的车辆可以提出离开停车场，并且停车场内在要离开的车辆之后到达的车辆都必须先离开停车场为它让路，然后这些车辆依原来到达停车场的次序进入停车场，因此在前面已设的一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，由于先退出停车场的后进入停车场，所以很显然保存让路车辆的场地也应该用一个栈来模拟。因此，本题求解过程中需用到两个栈和一个队列。
模块功能：
数据结构：
typedef struct Node //数据
{
char number[10];
char time[10];
}Node;
typedef struct QueueNode //队列结点
{
struct Node data; //数据域
struct QueueNode * next;//指针域
}*QueueNode;
typedef struct LinkQueue //链队列
{
struct QueueNode * front;//头
struct QueueNode * rear;//尾
}LinkQueue;
typedef struct stack //栈结点
{
struct Node data;
struct stack *next;
}*StackNode;
typedef struct LinkStack //链栈
{
StackNode top;//栈顶
int count;//栈总容量
}LinkStack;
函数：
void menu(LinkQueue *road,LinkStack *park,LinkStack *move,char num[],char t[]);//菜单
int init(LinkQueue *road,LinkStack *park,LinkStack *move);//初始化
int linklength(LinkQueue q);//计算队列长度
int inqueue(LinkQueue *q,char num[],char t[]);//入队
int outqueue(LinkQueue *q,char *num,char *t);//出队
int push(LinkStack *s,char num[],char t[]);//入栈
int pop(LinkStack *s,char *num,char *t);//出栈
void inpark(LinkQueue *road,LinkStack *park,LinkStack *move);//停车场入车
void outpark(LinkQueue *road,LinkStack *park,LinkStack *move);//停车场出车
void view(LinkQueue *road,LinkStack *park,LinkStack *move);//查看停车场状态
void query(LinkQueue *road,LinkStack *park,LinkStack *move);//查询车辆入场时间
void add(LinkQueue *road,LinkStack *park,LinkStack *move);//新增停车场车位
void vip(LinkQueue *road,LinkStack *park,LinkStack *move);//vip模块
void money(LinkQueue *road,LinkStack *park,LinkStack *move);
程序截图：
源码：
#include <stdio.h>#include <stdlib.h>#include <string.h>int parkcount=0;//车位数量 char vipcar[100][10];//存放vip车牌号 int vipcount;//vip数量 int tick=5;typedef struct Node //数据{char number[10];char time[10]; }Node;typedef struct QueueNode //队列结点{struct Node data; //数据域 struct QueueNode * next;//指针域 }*QueueNode;typedef struct LinkQueue //链队列{struct QueueNode * front;//头 struct QueueNode * rear;//尾 }LinkQueue;typedef struct stack //栈结点{struct Node data;struct stack *next;}*StackNode;typedef struct LinkStack//链栈{StackNode top;//栈顶 int count;//栈总容量 }LinkStack;void menu(LinkQueue *road,LinkStack *park,LinkStack *move,char num[],char t[]);//菜单int init(LinkQueue *road,LinkStack *park,LinkStack *move);//初始化 int linklength(LinkQueue q);//计算队列长度 int inqueue(LinkQueue *q,char num[],char t[]);//入队 int outqueue(LinkQueue *q,char *num,char *t);//出队 int push(LinkStack *s,char num[],char t[]);//入栈 int pop(LinkStack *s,char *num,char *t);//出栈 void inpark(LinkQueue *road,LinkStack *park,LinkStack *move);//停车场入车 void outpark(LinkQueue *road,LinkStack *park,LinkStack *move);//停车场出车void view(LinkQueue *road,LinkStack *park,LinkStack *move);//查看停车场状态 void query(LinkQueue *road,LinkStack *park,LinkStack *move);//查询车辆入场时间 void add(LinkQueue *road,LinkStack *park,LinkStack *move);//新增停车场车位 void vip(LinkQueue *road,LinkStack *park,LinkStack *move);//vip模块 void money(LinkQueue *road,LinkStack *park,LinkStack *move);void menu(LinkQueue *road,LinkStack *park,LinkStack *move,char num[],char t[])//菜单{int s;do{printf(" ** 停车场管理程序 **\n");printf("=========================================================\n");printf("** **\n");printf("** 1 --- 汽车进车场 2 --- 汽车出车场 **\n");printf("** 3 --- 查看停车场状态 4 --- 查询汽车入场时间 **\n");printf("** 5 --- 新增停车场车位 6 --- vip **\n");printf("** 7 --- 修改价格 0 --- 退出程序 **\n");printf("** **\n");printf("** 停车场剩余%-1d车位，每小时收费%d元 **\n",parkcount-park->count,tick);printf("=========================================================\n");printf("请输入序号：");scanf("%d",&s);if(s==0){exit(1);}else if(s==1){inpark(road,park,move);}else if(s==2){outpark(road,park,move);} else if(s==3){view(road,park,move);}else if(s==4){query(road,park,move);} else if(s==5){add(road,park,move);} else if(s==6){vip(road,park,move);}else if(s==7){money(road,park,move);}else{system("cls");printf("请输入正确的序号！\n");}}while(s!=1 && s!=2 && s!=3 && s!=4 && s!=5 && s!=6 && s!=7);}int init(LinkQueue *road,LinkStack *park,LinkStack *move){QueueNode node = (QueueNode)malloc(sizeof(struct QueueNode));if(node==NULL){return 0;}node->next = NULL;//初始化等待队列 road->front = node;road->rear = node;move->top = NULL;//初始化移动车辆栈 move->count = 0;park->top=NULL;//初始化停车栈 park->count=0;}int linklength(LinkQueue q)//计算队列长度 {int i = 0;while(q.front != q.rear){i++;q.front = q.front->next;}return i;}int inqueue(LinkQueue *q,char num[],char t[])//入队 {QueueNode node = (QueueNode)malloc(sizeof(struct QueueNode));if(NULL == node){return 0;}strcpy(node->data.number,num);strcpy(node->data.time,t);node->next = NULL;q->rear->next = node;q->rear = node;return 1;}int outqueue(LinkQueue *q,char *num,char *t)//出队 {if(q->front == q->rear){return 0;}strcpy(num,q->front->next->data.number);strcpy(t,q->front->next->data.time);QueueNode temp = q->front->next;//存放待删除结点的地址 q->front->next = q->front->next->next;if(temp->next == NULL)//只剩下头尾两个结点的情况，删除尾结点，把头尾指针都指向头结点 {q->rear = q->front;}free(temp);return 1;}int push(LinkStack *s,char num[],char t[])//入栈 {StackNode node = (StackNode)malloc(sizeof(struct stack));if(node==NULL){return 0;}strcpy(node->data.number,num);strcpy(node->data.time,t);node->next = s->top;s->top = node;s->count++;return 1;}int pop(LinkStack *s,char *num,char *t)//出栈 {if(s->count==0){return 0;}strcpy(num,s->top->data.number);strcpy(t,s->top->data.time);StackNode temp = s->top;s->top = s->top->next;free(temp);s->count--;return 1;}void inpark(LinkQueue *road,LinkStack *park,LinkStack *move)//停车场入车 {int s=0;char num[10];char t[10];int flag;StackNode p;QueueNode r;do{flag=0;p=park->top;r=road->front;printf("请输入入场车辆的车牌号：");scanf("%s",num);while(p!=NULL){if(strcmp(p->data.number,num)==0)//检查停车场里是否已存在相同车牌号的汽车 {flag=1;printf("停车场已存在相同车牌号的汽车，请检查车牌号输入是否正确！\n");}p=p->next;}while(r->next!=NULL){if(strcmp(r->next->data.number,num)==0)//检查停车场里是否已存在相同车牌号的汽车 {flag=1;printf("等候区已存在相同车牌号的汽车，请检查车牌号输入是否正确！\n");}r=r->next;}}while(flag==1);while(1){printf("请输入汽车入场时间(格式hh:ss)：");scanf("%s",t);if((t[0]-'0')>=2 && (t[1]-'0')>3 || t[2]!=':' || (t[3]-'0')>=6&& (t[4]-'0')>=0)printf("请按正确的格式输入入场时间！\n");elsebreak;}if( park->count >=parkcount)//停车场内车已停满 {printf("停车场已满，进入等待区！\n");inqueue(road,num,t);//进入便道等候区 printf("请按任意键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}else{push(park,num,t);//入栈 printf("该车已进入停车场%d号车道\n",park->count); printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}}void outpark(LinkQueue *road,LinkStack *park,LinkStack *move)//停车场出车{ char num[10],snum[10];char t[10],st[10];StackNode p=park->top;StackNode m=move->top;int stay;int flag=0;//标记 int f=0;//标记 int i;do{flag=0; p=park->top;printf("请输入出场汽车车牌：");scanf("%s",num);while(p!=NULL){if(strcmp(p->data.number,num)==0)//检查停车场里是否已存在相同车牌号的汽车 flag=1;p=p->next;}if(flag==0){printf("停车场内不存在该车牌，请确认输入的车牌号是否正确！\n");printf("按回车键继续...");getchar();getchar();system("cls");menu(road,park,move,num,t);}}while(flag==0);while(park->top!=NULL){pop(park,snum,st);push(move,snum,st);if(strcmp(snum,num)==0) {pop(move,snum,st);while(1){printf("请输入汽车出场时间(格式hh:ss)：");scanf("%s",t);if((t[0]-'0')>=2 && (t[1]-'0')>3 || t[2]!=':' || (t[3]-'0')>=6 && (t[4]-'0')>=0)printf("请按正确的格式输入出场时间！\n");else if((t[0]-'0')*10+(t[1]-'0')<=(st[0]-'0')*10+(st[1]-'0') && (t[3]-'0')*10+(t[4]-'0')<(st[3]-'0')*10+(st[4]-'0'))//当出场时间大于入场时间 printf("出场时间不得早与入场时间！\n");elsebreak;}for(i=0;i<=strlen(vipcar);i++){if(strcmp(num,vipcar[i])==0)f=1; }if(f==1){printf("该车为vip车辆，享受八折优惠!\n");stay=((t[0]-'0')*10+(t[1]-'0')-(st[0]-'0')*10-(st[1]-'0'))*60+((t[3]-'0')*10+(t[4]-'0')-(st[3]-'0')*10-(st[4]-'0'));//停留时间 printf("收 据\n");printf("================================ 车牌号: %s===============================\n",num);printf("=========================================================================\n");printf("|进车场时刻 | 出车场时刻 | 停留时间(分钟) | 应付（元）|\n");printf("| %s|%s|%d | %d\n",st,t,stay,(stay%60?(stay/60)*tick+tick:(stay/60)*tick)*4/5);printf("注：不足一小时按一小时计算\n");printf("=========================================================================\n");}else{stay=((t[0]-'0')*10+(t[1]-'0')-(st[0]-'0')*10-(st[1]-'0'))*60+((t[3]-'0')*10+(t[4]-'0')-(st[3]-'0')*10-(st[4]-'0'));//停留时间 printf("收 据\n");printf("================================ 车牌号: %s===============================\n",num);printf("=========================================================================\n");printf("|进车场时刻 | 出车场时刻 | 停留时间(分钟) | 应付（元）|\n");printf("| %s|%s|%d | %d\n",st,t,stay,stay%60?(stay/60)*tick+tick:(stay/60)*tick);printf("注：不足一小时按一小时计算\n");printf("=========================================================================\n");}while(move->count){pop(move,snum,st);push(park,snum,st);}if(road->front != road->rear )//等候区存在车辆{outqueue(road,snum,st);push(park,snum,st);} printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);return;}}printf("未找到此车牌的汽车\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}void view(LinkQueue *road,LinkStack *park,LinkStack *move)//查看停车场状态 {char num[10];char t[10];QueueNode r=road->front;StackNode p=park->top;printf("停车场中有%d辆汽车，车牌号分别是：",park->count); while(p!=NULL){if(p->next==NULL)printf("%s",p->data.number);elseprintf("%s,",p->data.number);p=p->next;}printf("\n");printf("等候区中有%d辆汽车，车牌号分别是：",linklength(*road)); while(r->next!=NULL){if(r->next->next==NULL)printf("%s",r->next->data.number);elseprintf("%s,",r->next->data.number);r=r->next;}printf("\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}void query(LinkQueue *road,LinkStack *park,LinkStack *move){int s;StackNode p=park->top;char num[10];char t[10];printf("1.查询停车场全部车辆入场时间\n");printf("2.查询某辆车的入场时间\n");printf("0.返回\n"); printf("请输入序号：");scanf("%d",&s);if(s==1){printf("车牌号入场时间\n");while(p!=NULL){printf("%s",p->data.number);printf(" ");printf("%s",p->data.time);printf("\n");p=p->next;} p=park->top;//初始化 }else if(s==2){printf("请输入查询汽车的车牌号：");scanf("%s",num); while(p!=NULL){if(strcmp(p->data.number,num)==0){printf("入场时间：%s",p->data.time);break;}p=p->next;} }else if(s==0){system("cls");menu(road,park,move,num,t);}printf("\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}void add(LinkQueue *road,LinkStack *park,LinkStack *move){int s;char num[10];char t[10];int i;printf("请输入要新增的车位:");scanf("%d",&s);parkcount=parkcount+s;for(i=0;i<s;i++){outqueue(road,num,t);push(park,num,t);}printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}void vip(LinkQueue *road,LinkStack *park,LinkStack *move){int s;int i;int flag=0;char num[10];char t[10];printf("1.购买vip2.查询全部vip车辆3.查询某辆汽车是否vip\n");scanf("%d",&s);if(s==1){do{flag=0;if(flag==0){printf("请输入购买vip的车牌号:");scanf("%s",num);}for(i=0;i<strlen(vip);i++){if(strcmp(vipcar[i],num)==0){printf("此车牌号已是vip，不可重复购买\n");flag=1;}}}while(flag==1);strcpy(vipcar[vipcount],num);vipcount++;printf("购买成功！\n"); printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}else if(s==2){printf("vip车牌号：");for(i=0;i<=strlen(vipcar);i++){if(i==strlen(vipcar))printf("%s",vipcar[i]);elseprintf("%s,",vipcar[i]);}printf("\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}else if(s==3){printf("请输入待查询的车牌号：");scanf("%s",num);for(i=0;i<=strlen(vipcar);i++){if(strcmp(vipcar[i],num)==0){printf("是\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);return; }}printf("否\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);} }void money(LinkQueue *road,LinkStack *park,LinkStack *move){char num[10];char t[10];printf("请输入要修改的票价："); scanf("%d",&tick);printf("修改成功\n");printf("请按回车键继续..."); getchar();getchar();system("cls");menu(road,park,move,num,t);}int main(){LinkQueue road;//便道 LinkStack park;//停车场通道 LinkStack move;//移动车辆 char num[10];char t[10];init(&road,&park,&move);menu(&road,&park,&move,num,t);return 0;}
项目三 家谱管理
项目简介：
家谱（或称族谱）是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本项目对家谱管理进行简单的模拟。
数据要求：
每个成员信息包括：代目、姓名、性别、生日、住址、婚否、是否健在、死亡日期（如果已死亡）。
功能要求：
至少包含下列基本功能，可增加功能计入加分项，缺少功能减分
1：显示家谱信息，统计代目和总人数。
2：显示第n代所有人的信息。
3：根据姓名查找显示成员信息。
4：添加家谱成员。
5：删除家谱成员。
6：修改成员信息。
界面要求：
根据系统功能要求设计。应有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
设计思路：
本项目的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，将家谱的树型结构转换为二叉树存储。然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
数据结构：
因为家族中的成员之间存在一个对多个的层次结构关系，家谱从形状上看像一颗倒长的树，所以用树结构来表示家谱比较适合。树型结构是一类非常重要的非线性数据结构，直观看来，树是以分支关系定义的层次结构。可以二叉链表作为树的存储结构。链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，固该表示法又称二叉树表示法，或孩子兄弟表示法。孩子兄弟表示法是一种链式存储结构，它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其具体的结点结构为：
其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点下一个兄弟，elem是数据元素内容，举例如下：
其存储形式定义如下：
typedef struct CSLinklist{
Elemtype data;
struct CSLinklist *firstchild,*nextsibling;
} CSLinklist,*CSTree;
模块功能：
数据结构：
typedef struct data{
char name[20];
char birthday[20];
int sex;//0女生，1男生
int marry;//0未婚，1已婚
char address[20];
char death_date[20];
int generation;//第几代
}data;
typedef struct node{
data person;
struct node *lchild,*rbrother;
}node,*tree;
typedef struct{ //循环队列的定义
tree queue[100];
int front,rear;
}queue;
函数：
int countnum(tree T); //计算共有几人
int BirthdayPreOrderTraverse(tree T);//查找生日前序遍历
int NamePreOrderTraverse(tree T,char name[20]);//查找姓名前序遍历
int AddPreOrderTraverse(tree T,char name[20]);//添加孩子前序遍历
void printfinfo(tree p);//打印结点信息
void Qinit(queue *Q);//初始化队列
void inqueue(queue *Q,tree e);//入队
void outqueue(queue *Q,tree *e);//出队
int empty(queue Q);//判队空
int full(queue Q);//判队满
int TreeDepth(tree T);//返回二叉树深度
void Tinit();//初始化二叉树
void today_birthday();//显示今天生日的成员
void show();//显示家谱
void shownum();//显示第几代人的信息
void lookupname();// 根据姓名查找成员
void Addchildren();//为成员添加孩子
void deletemember();//删除成员
void modifymember();//修改成员信息
void determinemember();//确定成员的关系
程序截图：
源码 ：
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<time.h> typedef struct data{char name[20];char birthday[20];int sex;//0女生，1男生 int marry;//0未婚，1已婚 char address[20];char death_date[20];int generation;//第几代 }data;typedef struct node{data person;struct node *lchild,*rbrother;}node,*tree;typedef struct{ //循环队列的定义tree queue[100];int front,rear;}queue;tree BT;int count=0;int flag=0;//标记int countnum(tree T); //计算共有几人 int BirthdayPreOrderTraverse(tree T);//查找生日前序遍历 int NamePreOrderTraverse(tree T,char name[20]);//查找姓名前序遍历 int AddPreOrderTraverse(tree T,char name[20]);//添加孩子前序遍历 void printfinfo(tree p);//打印结点信息 void Qinit(queue *Q);//初始化队列 void inqueue(queue *Q,tree e);//入队void outqueue(queue *Q,tree *e);//出队int empty(queue Q);//判队空int full(queue Q);//判队满int TreeDepth(tree T);//返回二叉树深度 void Tinit();//初始化二叉树 void today_birthday();//显示今天生日的成员 void show();//显示家谱 void shownum();//显示第几代人的信息 void lookupname();// 根据姓名查找成员 void Addchildren();//为成员添加孩子 void deletemember();//删除成员 void modifymember();//修改成员信息 void determinemember();//确定成员的关系 void menu();int countnum(tree T) //计算共有几人 {if (T == NULL){return 0;}else{count++;countnum(T->lchild);countnum(T->rbrother);}}int BirthdayPreOrderTraverse(tree T)//查找生日前序遍历 {time_t timep;struct tm *p;time (&timep);p=gmtime(&timep);int m=0;int d=0;if (T == NULL){return 0;}else{m=(T->person.birthday[5]-'0')*10+(T->person.birthday[6]-'0');d=(T->person.birthday [8]-'0')*10+(T->person.birthday[9]-'0');if(m==1+p->tm_mon && d==p->tm_mday){flag=1;printf("%s ",T->person.name);}BirthdayPreOrderTraverse(T->lchild);BirthdayPreOrderTraverse(T->rbrother);}}int NamePreOrderTraverse(tree T,char name[20])//查找姓名前序遍历 {if (T == NULL){return 0;}else{if(strcmp(name,T->person.name)==0){flag=1;printf("此人为家谱第%d代成员，其信息为：\n",T->person.generation);printfinfo(T);printf("他的孩子信息为：\n"); if(T->lchild){T=T->lchild;printfinfo(T);while(T->rbrother){T=T->rbrother;printfinfo(T); }}}NamePreOrderTraverse(T->lchild,name);NamePreOrderTraverse(T->rbrother,name);}}int AddPreOrderTraverse(tree T,char name[20])//添加孩子前序遍历 {tree p=(tree)malloc(sizeof(struct node));int num;//孩子排行 int i;if (T == NULL){return 0;}else{if(strcmp(name,T->person.name)==0){flag=1;printf("请输入添加孩子的排行(从1开始计数)：");scanf("%d",&num);if(T->lchild)//如果左孩子存在 {p->person.generation=T->person.generation+1;if(num==1)//排行第一代 ，则把结点放在父结点的左孩子 {p->rbrother=T->lchild;T->lchild=p;}else{num--;T=T->lchild;num--;//排在第几代需取第几代前一代的数 while(T->rbrother && num>0){T=T->rbrother;num--;}p->rbrother=T->rbrother;T->rbrother=p;}}else//左孩子不存在先创建左孩子 {p->person.generation=T->person.generation+1;T->lchild=p;}printf("请输入添加孩子的姓名:");scanf("%s",&p->person.name);do{if(strlen(p->person.birthday)!=10 && strlen(p->person.birthday)!=0)printf("请输入正确的日期格式\n");printf("请输入添加孩子的出生年月(格式形如: -01-01):");scanf("%s",&p->person.birthday);} while(strlen(p->person.birthday)!=10); printf("请输入添加孩子的家庭住址:");scanf("%s",&p->person.address);printf("请输入添加孩子的婚姻状况 0/1 (0表示未婚，1表示已婚):"); scanf("%d",&p->person.marry);printf("请输入添加孩子的去世时间 (在世填0-0-0):");scanf("%s",&p->person.death_date); printf("请输入添加孩子的性别 0/1 (0表示女，1表示男):"); scanf("%d",&p->person.sex); }AddPreOrderTraverse(T->lchild,name);AddPreOrderTraverse(T->rbrother,name);}}int DeletePreOrderTraverse(tree T,char name[20])//删除孩子前序遍历 {if(strcmp(name,BT->person.name)==0)//删除根节点情况 {flag=1;if(BT->rbrother!=NULL)//根结点不存在右兄弟 {BT=BT->rbrother;return 0; }else if(BT->rbrother==NULL)//根节点存在右兄弟 {BT=NULL;return 0;} }if (T == NULL){return 0;}else{if(T->lchild!=NULL)if(strcmp(name,T->lchild->person.name)==0)//当前结点的左孩子 {flag=1;T->lchild=T->lchild->rbrother;//当前结点左孩子等于左孩子的右兄弟 }if(T->rbrother!=NULL)if(strcmp(name,T->rbrother->person.name)==0){flag=1;T->rbrother=T->rbrother->rbrother;}DeletePreOrderTraverse(T->lchild,name);DeletePreOrderTraverse(T->rbrother,name);}}int modifyPreOrderTraverse(tree T,char name[20])//修改成员信息前序遍历{int num;if (T == NULL){return 0;}else{if(strcmp(name,T->person.name)==0){flag=1;printf("请选择要修改%s的哪项数据:\n",T->person.name);printf("1.修改姓名\n");printf("2.修改出生年月\n");printf("3.修改家庭住址\n");printf("4.修改婚姻状况\n");printf("5.修改在世情况\n");printf("6.修改性别\n");printf("7.返回上一级\n");scanf("%d",&num);switch(num){case 1:printf("请输入修改后的姓名：");scanf("%s",T->person.name);break;case 2:do{if(strlen(T->person.birthday)!=10 && strlen(T->person.birthday)!=0)printf("请输入正确的日期格式\n");printf("请输入修改后的出生年月(格式形如: -01-01)：");scanf("%s",&T->person.birthday);} while(strlen(T->person.birthday)!=10); break;case 3:printf("请输入修改后的家庭住址：");scanf("%s",T->person.address);break;case 4:printf("请输入修改后的婚姻状况(0未婚，1已婚)：");scanf("%d",&T->person.marry) ;break;case 5:printf("请输入修改后的在世情况(在世填0-0-0)：");scanf("%d",&T->person.death_date);break;case 6:printf("请输入修改后的性别(0女生，1男生)：");scanf("%d",&T->person.sex);break;case 7:return 0;}}modifyPreOrderTraverse(T->lchild,name);modifyPreOrderTraverse(T->rbrother,name);}} int deterPreOrderTraverse(tree T,char name[20],int *gen)//确定成员的关系前序遍历 {if (T == NULL){return 0;}else{if(strcmp(name,T->person.name)==0){flag=1;*gen=T->person.generation;}deterPreOrderTraverse(T->lchild,name,gen);deterPreOrderTraverse(T->rbrother,name,gen);}}void printfinfo(tree p)//打印结点信息 {printf("%s ",p->person.name);printf("出生于：%s ",p->person.birthday);printf("%s ",p->person.address);if(p->person.marry==1)printf("已婚 ");elseprintf("未婚 "); if(p->person.sex==1)printf("男 ");elseprintf("女 ");if(strcmp(p->person.death_date,"0-0-0")==0)printf("健在\n");elseprintf("死亡日期：%s\n",p->person.death_date);}void new_left(tree p,data d)//创建左孩子 {tree q=(tree)malloc(sizeof(node));q->person=d;q->lchild=q->rbrother=NULL;p->lchild=q;}void new_right(tree p,data d)//创建右兄弟 {tree q=(tree)malloc(sizeof(node));q->person=d;q->lchild=q->rbrother=NULL;p->rbrother=q;}int Generation(tree T)//返回代数 {if(T==NULL)return 0;if(T)return Generation(T->lchild)+1;}void Tinit()//初始化二叉树 {data initdata[10]={{"A","1960-06-12",1,1,"厦门集美","-10-01",1},{"B","1980-06-12",1,1,"厦门集美","0-0-0",2},{"C","1981-06-18",1,1,"厦门集美","0-0-0",2},{"D","1982-06-12",1,1,"厦门集美","0-0-0",2},{"E","-06-12",1,1,"厦门集美","0-0-0",3},{"F","-06-12",1,1,"厦门集美","0-0-0",3},{"G","-06-12",1,1,"厦门集美","0-0-0",3},{"H","-06-12",1,1,"厦门集美","0-0-0",3}, {"I","-06-12",1,1,"厦门集美","0-0-0",3},{"J","-06-12",1,1,"厦门集美","0-0-0",3}};BT=(tree)malloc(sizeof(node));BT->person=initdata[0];BT->lchild=BT->rbrother=NULL;new_left(BT,initdata[1]);new_left(BT->lchild,initdata[4]);new_right(BT->lchild->lchild,initdata[5]);new_right(BT->lchild->lchild->rbrother,initdata[7]);new_right(BT->lchild,initdata[2]);new_left(BT->lchild->rbrother,initdata[6]);new_right(BT->lchild->rbrother->lchild,initdata[8]);new_right(BT->lchild->rbrother,initdata[3]);new_left(BT->lchild->rbrother->rbrother,initdata[9]);}void today_birthday()//显示今天生日的成员 {flag=0;time_t timep;struct tm *p;time (&timep);p=gmtime(&timep);printf("今天日期是%d-%d，今天生日成员：",1+p->tm_mon,p->tm_mday); BirthdayPreOrderTraverse(BT);printf("\n");if(flag==0)printf("家谱中没有成员过生日\n");printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void show()//显示家谱 {queue *q=(queue *)malloc(sizeof(queue));q->front=q->rear=0;count=0;if(BT!=NULL)//计算BT共有多少人 countnum(BT);system("cls");printf("共计%d代，%d人\n",Generation(BT),count);printf("\n");int d=1;tree p=BT;tree n=(tree)malloc(sizeof(struct node));//分隔符 strcpy(n->person.name,"NULL");n->lchild=n->rbrother=NULL; if(p){printf("第1代\n");q->queue[q->rear++]=p;//根结点入队 while(p->rbrother)//把根结点所有右兄弟入队 {p=p->rbrother;q->queue[q->rear++]=p;}q->queue[q->rear++]=n;//分隔符入队 while(q->front!=q->rear)//队列不为空 {p=q->queue[q->front++];//取队头结点 if(strcmp(p->person.name,"NULL")==0 && q->front!=q->rear)//为分割号表示一代结束 {printf("第%d代\n",++d);q->queue[q->rear++]=n;//加入分割号区分代各代 }else if(q->front!=q->rear){printfinfo(p);}if(p->lchild)//如果左孩子存在 {p=p->lchild;q->queue[q->rear++]=p;//把左孩子所有右兄弟入队，表示一代 while(p->rbrother){p=p->rbrother;q->queue[q->rear++]=p;}}}}printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void shownum()//显示第几代人 {int num;printf("请输入需要查询的第几代人：");scanf("%d",&num); queue *q=(queue *)malloc(sizeof(queue));q->front=q->rear=0;system("cls");int d=1;tree p=BT;tree n=(tree)malloc(sizeof(struct node));//分隔符 strcpy(n->person.name,"NULL");n->lchild=n->rbrother=NULL; if(p){q->queue[q->rear++]=p;//根结点入队 while(p->rbrother)//把根结点所有右兄弟入队 {p=p->rbrother;q->queue[q->rear++]=p;}q->queue[q->rear++]=n;//分隔符入队 while(q->front!=q->rear)//队列不为空 {p=q->queue[q->front++];//取队头结点 if(strcmp(p->person.name,"NULL")==0 && q->front!=q->rear)//为分割号表示一代结束 {d++;q->queue[q->rear++]=n;//加入分割号区分代各代 }else if(q->front!=q->rear && num==d){printfinfo(p);}if(p->lchild)//如果左孩子存在 {p=p->lchild;q->queue[q->rear++]=p;//把左孩子所有右兄弟入队，表示一代 while(p->rbrother){p=p->rbrother;q->queue[q->rear++]=p;}}}}printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void Addchildren() //为成员添加孩子 {char name[20];printf("请输入要添加孩子成员的姓名：");scanf("%s",name); flag=0;AddPreOrderTraverse(BT,name);if(flag==0)printf("没有这个人\n");printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void lookupname()//根据姓名查找成员 {char name[20];flag=0; printf("请输入要查询人的姓名:");scanf("%s",name);NamePreOrderTraverse(BT,name);if(flag==0)printf("对不起，找不到此人的信息\n");printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void deletemember()//删除成员 {flag=0;char name[20];printf("请输入要删除成员的姓名："); scanf("%s",name);DeletePreOrderTraverse(BT,name);if(flag==0)printf("对不起，找不到此人的信息\n");elseprintf("删除成功！");printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void modifymember()//修改成员信息 {flag=0; char name[20]; printf("请输入要修改人的姓名："); scanf("%s",name);modifyPreOrderTraverse(BT,name);if(flag==0)printf("对不起，找不到此人的信息\n");elseprintf("修改成功！\n");printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void determinemember()//确定成员的关系 {int i;int firstgen=0;//第一个人代数 int secondgen=0;//第二个人代数 char name1[20],name2[20]; flag=0;printf("请输入第一个人的姓名：");scanf("%s",name1);deterPreOrderTraverse(BT,name1,&firstgen);if(flag==0)printf("家谱无此人，请重新进入！\n");else{flag=0;printf("请输入第二个人的姓名：");scanf("%s",name2);deterPreOrderTraverse(BT,name2,&secondgen);if(flag==0)printf("家谱无此人，请重新进入！\n");elseif(secondgen>firstgen){printf("%s比%s大%d辈\n",name1,name2,secondgen-firstgen);for(i=0;i<secondgen-firstgen;i++){} }else if(secondgen<firstgen)printf("%s比%s小%d辈\n",name1,name2,firstgen-secondgen);else if(secondgen==firstgen)printf("%s和%s同辈\n",name1,name2); }printf("请按回车键继续..."); getchar();getchar(); system("cls");menu();}void menu(){int num;printf("\n");printf(" 欢迎进入家谱管理系统\n");printf(" 1.显示今天生日成员 2.显示家谱\n");printf(" 3.显示第n代所有人的信息4.根据姓名查找成员\n");printf(" 5.为成员添加孩子 6.删除成员\n");printf(" 7.修改成员信息8.确定两个人的关系\n");printf(" 0.退出程序\n");do{printf("请输入序号：");scanf("%d",&num);switch(num){case 0:exit(1);case 1:today_birthday();break;case 2:show();break;case 3:shownum();break;case 4:lookupname();break;case 5:Addchildren();break;case 6:deletemember();break;case 7:modifymember();break;case 8:determinemember();break;default:printf("请输入正确的序号！\n");}}while(num!=0 && num!=1 && num!=2 && num!=3 && num!=4 && num!=5 && num!=6 && num!=7 && num!=8);}int main(){Tinit();//初始化二叉树 menu();return 0;}
项目四 校园导游系统
项目简介：
设计一个校园地图导游程序，提供景点增删改查等信息查询服务。
数据要求：
根据学校平面图，选择不少于10个景点。根据地图位置，模拟各景点位置和景点间路径，存储路径长度。校园内各景点信息包括：景点编号、名称、简介等信息。
功能要求：
至少包含下列基本功能，可增加功能计入加分项，缺少功能减分
1：提供图中任意景点相关信息的查询。
2：新增景点信息和路径信息。
3：修改景点信息。
4：删除景点信息。
5：求一个景点到所有景点的最短路径。
6：求任意的两个景点之间的最短路径。
界面要求：
根据以下厦门理工学院地图，抽象出各个景点（至少10个）以及其大体距离和位置关系，模拟出系统的地图信息。
要求显示模拟的地图，设计合理的查询界面和功能菜单。
厦门理工学院地图（可自行百度地图查看）
设计思路：
本项目的实质是对带权图的操作，包含对图顶点和边的增删改查，以及最短路径问题应用。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。最优路径问题不仅包括最短路径问题，还有可能涉及到最少时间问题、最少收费（存在收费公路）问题、或者是几个问题的综合，这时将必须考虑道路级别、道路流量、道路穿越代价（如红灯平均等待时间）等诸多因素。但是必须指出的是，一般来说最优路径在距离上应该是最短的，但最短路径在行驶时间和能源消耗的意义上未必是最优的。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。
数据结构：
带权无向图存储可采用邻接矩阵或者邻接表结构存储。
模块功能：
数据结构：
typedef struct
{
int num;
char name[20];
char info[50];
}data;
typedef struct
{
data vexs[max];//结点
int arcs[max][max];//邻接矩阵
int vexnum,arcnum;//结点数，边数
}MGrapt;
函数：
void initG();// 初始化图
void menu();//显示菜单
void queryinfo();//景点信息查询
void addinfo();//新增景点信息
void modifyinfo();//修改景点和道路信息
void deleteinfo();//删除景点和道路信息
void Pathquery();//求任意两点的路径查询
void onetoallpath();//求一个到所有的最短路径
void twopath();//求两个之间的最短路径
void netting();//最佳布网方案
void ergodic();// 求任意一点走遍全校最短路径
程序截图：
源码：
#include<stdio.h>#include<string.h>#define max 100typedef struct{int num;char name[20];char info[50];}data;typedef struct{data vexs[max];//结点 int arcs[max][max];//邻接矩阵 int vexnum,arcnum;//结点数，边数 }MGrapt; int DFSvisited[max]={0};//结点访问标记 int DFSsave[max]={0}; int djsave[max];int count;int shortlength[max];int primqueue[max]={0};int s;MGrapt TG;//理工地图int Infinity=65536;//无穷大 void initG();// 初始化图void menu();//显示菜单 void queryinfo();//景点信息查询 void addinfo();//新增景点信息 void modifyinfo();//修改景点和道路信息void deleteinfo();//删除景点和道路信息void Pathquery();//求任意两点的路径查询void onetoallpath();//求一个到所有的最短路径void twopath();//求两个之间的最短路径 void netting();//最佳布网方案 void ergodic();// 求任意一点走遍全校最短路径 void initG()// 初始化图{int i,j; TG.vexnum=14;//14个结点 TG.arcnum=20;//20条边data temp[100]={{1,"北门","这里是北门"},{2,"一期食堂","这里是一期食堂"}, {3,"旧操场","这里是旧操场"},{4,"明理9","这里是明理9"},{5,"博学苑","这里是博学苑"},{6,"艺术会堂","这里是艺术会堂"},{7,"医务室","这里是医务室"},{8,"风洞实验室","这里是风洞实验室"},{9,"创新创业园","这里是创新创业园"},{10,"计算机学院","这里是计算机与信息工程学院"},{11,"材料学院","这里是材料科学与工程学院"},{12,"图书馆","这里是图书馆"},{13,"新操场","这里是新操场"},{14,"体育馆","这里是体育馆"},};for(i=0;i<TG.vexnum;i++)TG.vexs[i]=temp[i];for(i=0;i<TG.vexnum;i++)TG.arcs[i][i]=Infinity;for(i=0;i<max;i++)//邻接矩阵所有元素初始化为无穷大 ，无路径就为无穷大 for(j=0;j<max;j++)TG.arcs[i][j]=Infinity; TG.arcs[0][1]=140;TG.arcs[0][2]=176;TG.arcs[1][3]=276;TG.arcs[2][5]=310;TG.arcs[2][13]=184;TG.arcs[3][4]=110;TG.arcs[3][6]=224;TG.arcs[4][5]=100;TG.arcs[5][6]=230;TG.arcs[5][7]=150;TG.arcs[5][10]=210;TG.arcs[5][11]=240;TG.arcs[6][8]=180;TG.arcs[6][7]=203;TG.arcs[7][8]=176;TG.arcs[8][9]=146;TG.arcs[9][10]=120;TG.arcs[10][12]=500;TG.arcs[11][12]=337;TG.arcs[12][13]=157;for(i=0;i<TG.vexnum;i++)for(j=0;j<TG.vexnum;j++)TG.arcs[j][i]=TG.arcs[i][j];}void menu(){int num; do{printf("\n");printf("************欢迎使用厦门理工学院导游咨询系统***********");printf("\n");printf("1.景点信息查询\n");printf("2.新增景点信息\n");printf("3.修改景点和道路信息\n");printf("4.删除景点和道路信息\n");printf("5.任意两个景点的路径查询\n");printf("6.求一个景点到所有景点的最短路径\n");printf("7.求任意两个景点之间的最短路径\n");printf("8.最佳布网方案\n");printf("0.退出系统\n");printf("*******************************************************\n");printf("请输入序号：");scanf("%d",&num);if(num!=0 && num!=1 && num!=2 && num!=3 && num!=4 && num!=5 && num!=6 && num!=7 && num!=8){system("cls"); printf("请输入正确的序号！");}}while(num!=0 && num!=1 && num!=2 && num!=3 && num!=4 && num!=5 && num!=6 && num!=7 && num!=8);switch(num){case 0: exit(0);case 1: queryinfo();break;case 2: addinfo();break;case 3: modifyinfo();break;case 4: deleteinfo();break;case 5: Pathquery();break;case 6: onetoallpath();break;case 7: twopath();break;case 8: netting();break;//case 9: }}void queryinfo()//景点信息查询 {int num;int i,j;int flag=0;char name[20];system("cls");do{printf("\n");printf("1：按照景点编号查询\n");printf("2：按照景点名称查询\n");printf("3：列出所有景点和道路信息\n");printf("0：返回上一级\n");printf("请输入序号：");scanf("%d",&num);if(num!=0 && num!=1 && num!=2 && num!=3 ){system("cls"); printf("请输入正确的序号！");}}while(num!=0 && num!=1 && num!=2 && num!=3);if(num==1){flag=0;printf("请输入景点编号：");scanf("%d",&num);for(i=0;i<TG.vexnum;i++){if(TG.vexs[i].num==num){flag=1;printf("景点编号：%d\n",TG.vexs[i].num);printf("景点名称：%s\n",TG.vexs[i].name);printf("景点介绍：%s\n",TG.vexs[i].info);printf("\n");printf("该景点路径信息：\n");for(j=0;j<TG.vexnum;j++){if(TG.arcs[i][j]!=Infinity)printf("到景点%d--%s的距离为%d\n",TG.vexs[j].num,TG.vexs[j].name,TG.arcs[i][j]);}}}if(flag==0)printf("对不起，无此编号！"); getchar();getchar();system("cls");queryinfo();}else if(num==2){flag=0;printf("请输入景点名称：");scanf("%s",name);for(i=0;i<TG.vexnum;i++){if(strcmp(name,TG.vexs[i].name)==0){flag=1;printf("景点编号：%d\n",TG.vexs[i].num);printf("景点名称：%s\n",TG.vexs[i].name);printf("景点介绍：%s\n",TG.vexs[i].info);printf("\n");printf("该景点路径信息：\n");for(j=0;j<TG.vexnum;j++){if(TG.arcs[i][j]!=Infinity)printf("到景点%d--%s的距离为%d\n",TG.vexs[j].num,TG.vexs[j].name,TG.arcs[i][j]);}}}if(flag==0)printf("对不起，无此名称！"); getchar();getchar();system("cls");queryinfo();}else if(num==3){printf("景点编号景点名称景点介绍\n");for(i=0;i<TG.vexnum;i++)printf("%-16d%-16s%s\n",TG.vexs[i].num,TG.vexs[i].name,TG.vexs[i].info);printf("\n");printf("道路信息：\n");for(i=0;i<TG.vexnum;i++){for(j=i;j<TG.vexnum;j++){if(TG.arcs[i][j]!=Infinity)printf("景点%d--%s和景点%d--%s存在道路，距离为%d\n",TG.vexs[i].num,TG.vexs[i].name,TG.vexs[j].num,TG.vexs[j].name,TG.arcs[i][j]);}}getchar();getchar();system("cls");queryinfo();}else if(num==0){system("cls");menu();}}void addinfo()//新增景点信息 {int num;char name[20];char info[50];int flag=0;int i;printf("请输入待新增的景点信息：\n");do{printf("景点编号：");scanf("%d",&num);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==num)flag=1;if(flag==1){printf("该编号已存在！"); getchar();getchar();system("cls");menu();}}while(flag==1); printf("景点名称：");scanf("%s",name);printf("景点介绍：");scanf("%s",info); TG.vexs[TG.vexnum].num=num;strcpy(TG.vexs[TG.vexnum].name,name);strcpy(TG.vexs[TG.vexnum].info,info);TG.vexnum++;printf("新增景点信息成功！"); getchar();getchar();system("cls");menu();}void modifyinfo()//修改景点和道路信息{int num;char name[20];char info[50];int i;int flag;int x,y;int first,second,length;system("cls");do{printf("\n");printf("1：输入景点编号修改景点信息\n");printf("2：输入景点名称修改景点信息\n");printf("3：修改路径信息，如原无路径则新增\n");printf("0：返回上一级\n");printf("请输入序号：");scanf("%d",&num);if(num!=0 && num!=1 && num!=2 && num!=3){system("cls"); printf("请输入正确的序号！");}}while(num!=0 && num!=1 && num!=2 && num!=3);if(num==0){system("cls");menu();}else if(num==1){flag=0; do{printf("请输入景点编号：");scanf("%d",&num);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==num){x=i;flag=1;}if(flag==0){printf("对不起，无此编号！"); getchar();getchar();system("cls");modifyinfo();}}while(flag==0); printf("请输入修改后的名称：");scanf("%s",name);strcpy(TG.vexs[x].name,name);printf("请输入修改后的介绍："); scanf("%s",info);strcpy(TG.vexs[x].info,info);printf("景点信息修改成功！"); getchar();getchar();system("cls");modifyinfo();}else if(num==2){flag=0; do{printf("请输入景点名称：");scanf("%s",name);for(i=0;i<TG.vexnum;i++)if(strcmp(TG.vexs[i].name,name)==0){x=i;flag=1;}if(flag==0){printf("对不起，无此名称！"); getchar();getchar();system("cls");modifyinfo();}}while(flag==0); printf("请输入修改后的名称：");scanf("%s",name);strcpy(TG.vexs[x].name,name);printf("请输入修改后的介绍："); scanf("%s",info);strcpy(TG.vexs[x].info,info);printf("景点信息修改成功！"); getchar();getchar();system("cls");modifyinfo();}else if(num==3){flag=0;printf("请输入待修改的路径信息，如无路径则新增\n");printf("格式形如(1-2,60),表示编号 1 2，路径长度60：\n");scanf("%d-%d,%d",&first,&second,&length);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==first){x=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");modifyinfo();}flag=0;for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==second){y=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");modifyinfo();}TG.arcs[x][y]=length;TG.arcs[y][x]=length;printf("修改信息成功！"); getchar();getchar();system("cls");modifyinfo();}}void deleteinfo()//删除景点和道路信息{int num;char name[20];char info[50];int i;int flag;int x,y;int first,second,length;system("cls");do{printf("\n");printf("1：输入景点编号删除景点信息\n");printf("2：输入景点名称删除景点信息\n");printf("3：删除道路信息\n");printf("0：返回上一级\n");printf("请输入序号：");scanf("%d",&num);if(num!=0 && num!=1 && num!=2 && num!=3){system("cls"); printf("请输入正确的序号！");}}while(num!=0 && num!=1 && num!=2 && num!=3);if(num==0){system("cls");menu();}else if(num==1){flag=0; do{printf("请输入景点编号：");scanf("%d",&num);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==num){x=i;flag=1;}if(flag==0){printf("对不起，无此编号！"); getchar();getchar();system("cls");deleteinfo();}}while(flag==0); for(i=x;i<TG.vexnum;i++)TG.vexs[i]=TG.vexs[i+1];TG.vexnum--;printf("景点删除成功！");getchar();getchar();system("cls");deleteinfo();}else if(num==2){flag=0; do{printf("请输入景点名称：");scanf("%s",name);for(i=0;i<TG.vexnum;i++)if(strcmp(TG.vexs[i].name,name)==0){x=i;flag=1;}if(flag==0){printf("对不起，无此名称！"); getchar();getchar();system("cls");deleteinfo();}}while(flag==0); for(i=x;i<TG.vexnum;i++)TG.vexs[i]=TG.vexs[i+1];TG.vexnum--;getchar();getchar();system("cls");deleteinfo();}else if(num==3){flag=0;printf("请输入待删除的路径信息\n");printf("格式形如(1-2),表示编号 1 2\n");scanf("%d-%d,%d",&first,&second);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==first){x=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");deleteinfo();}flag=0;for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==second){y=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");deleteinfo();}TG.arcs[x][y]=Infinity;TG.arcs[y][x]=Infinity;printf("删除成功！"); getchar();getchar();system("cls");deleteinfo();}}void DFS(int m,int start, int end)//深搜 {int i,j; for(i = 0; i < TG.vexnum; i++){if(TG.arcs[start][i] !=Infinity && DFSvisited[i] == 0)//起始结点到i存在路径且i未被访问 {DFSvisited[i] = 1;if(i == end)//等于目标结点时打印 {count++;printf("★%d.",count);for(j = 0; j < m; j++) {printf("%s->", TG.vexs[DFSsave[j]].name);}printf("%s\n", TG.vexs[end].name);DFSvisited[i] = 0;}else //不等则存储结点 {DFSsave[m] = i;m++;DFS(m,i, end);m--;DFSvisited[i] = 0;//递归把这条路径上所有结点初始化为未访问 }}}}void Pathquery()//求任意两点的路径查询{int flag=0; int start,end;int x,y;int i;for(i=0;i<TG.vexnum;i++)//初始化访问 {DFSvisited[i]=0;DFSsave[i]=0;}printf("请输入起始景点编号和终点景点编号，用空格隔开：");scanf("%d %d",&start,&end);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==start){flag=1;x=i;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");menu(); }flag=0;for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==end){flag=1;y=i;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");menu(); }DFSsave[0]=x;//开始结点 DFSvisited[x]=1;DFS(1,x,y);getchar();getchar();system("cls");menu(); }void onetoallpath()//求一个到所有的最短路径{int start;int i,j;int flag=0;int x=0;int stack[max]={-1};int s=0;printf("请输入起始景点编号：");scanf("%d",&start);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==start){flag=1;x=i;}if(flag==0){printf("输入的编号不存在！"); getchar();getchar();system("cls");menu();}Dijkstra(x);printf("%s到其他各景点的最短距离如下：\n",TG.vexs[x].name);for(i=0;i<TG.vexnum;i++){if(i!=x){s=0;stack[0]=djsave[i]; //终点的前一个结点下标值放入数组 printf("%s->",TG.vexs[x].name);/*for(i=0;i<TG.vexnum;i++)printf("%d、",djsave[i]);*/for(j=1;j<TG.vexnum;j++){stack[j]=djsave[stack[j-1]];//每次存储上一个结点的前一个结点下标 }for(j=0;j<TG.vexnum;j++){if(stack[j]==-1) break;s++;//计算共有多少结点（不包括开始和结束）}for(j=s-1;j>=0;j--)printf("%s->",TG.vexs[stack[j]].name);printf("%s\n",TG.vexs[i].name);printf("距离为：%dm\n",shortlength[i]);}}getchar();getchar();system("cls");menu();}int Dijkstra(int start){int visited[max]={0};int min,i,j,k;int s=0;for(i=0;i<TG.vexnum;i++)//记录起点所有邻接结点权值 {shortlength[i]=TG.arcs[start][i];visited[i]=0;//初始化为未访问 djsave[i]=-1;}shortlength[start]=0;visited[start]=1;//开始结点标记已访问 for(i=0;i<TG.vexnum;i++){k=-1;min=Infinity;for(j=0;j<TG.vexnum;j++)//找出最短路径 {if(visited[j]==0 && shortlength[j]<min)//j结点未被访问，起点到j结点的权值小于最小值 {min=shortlength[j];k=j;}}visited[k]=1;for(j=0;j<TG.vexnum;j++){if(visited[j]==0 && TG.arcs[k][j]+shortlength[k]<shortlength[j])//修正最短路径 {shortlength[j]=TG.arcs[k][j]+shortlength[k];djsave[j]=k;}} }}void twopath()//求两个之间的最短路径 {int flag=0; int start,end;int x=0,y=0;int i=0;int stack[max]={-1};int s=0;printf("请输入起始景点编号和终点景点编号，用空格隔开：");scanf("%d %d",&start,&end);if(start==end){printf("起点和终点不能相同！");getchar();getchar();system("cls");menu(); }for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==start){x=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");menu();}flag=0; for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==end){y=i;flag=1;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");menu();}Dijkstra(x);printf("从%s到%s的最短路径是：\n",TG.vexs[x].name,TG.vexs[y].name);stack[0]=djsave[y]; //终点的前一个结点下标值放入数组 printf("%s->",TG.vexs[x].name);/*for(i=0;i<TG.vexnum;i++)printf("%d、",djsave[i]);*/for(i=1;i<TG.vexnum;i++){stack[i]=djsave[stack[i-1]];//每次存储上一个结点的前一个结点下标 }for(i=0;i<TG.vexnum;i++){if(stack[i]==-1) break;s++;//计算共有多少结点（不包括开始和结束） }for(i=s-2;i>=0;i--)printf("%s->",TG.vexs[stack[i]].name);printf("%s\n",TG.vexs[y].name);printf("距离为：%dm",shortlength[y]);getchar();getchar();system("cls");menu();}int prim(int start){int lowcost[max]={0};int min;int i,k,j;int cost=0;s=0;//全局变量 for(i=0;i<TG.vexnum;i++){if(i!=start){primqueue[i]=start;lowcost[i]=TG.arcs[start][i];//把1结点的邻接结点对应的权值记录下来}}//lowcost[start]=0;//1结点赋值为0表示已访问for(i=0;i<TG.vexnum-1;i++){min=99999;j=0;k=0;while(j<TG.vexnum){if(lowcost[j]!=0 && lowcost[j]<min)//找出权值最下的且记录该下标{min=lowcost[j];k=j;}j++;}cost=cost+min;//把最小结点权值加入printf("从%s---%s:%d m\n", TG.vexs[primqueue[k]].name,TG.vexs[k].name,lowcost[k]);//printf("%d\n",cost);lowcost[k]=0;//该结点标记为已访问// primqueue[s++]=k;for(j=0;j<TG.vexnum;j++)//更新顶点集到其他结点的路径{if(j!=k && lowcost[j]!=0 && TG.arcs[k][j]<lowcost[j])//已访问的结点就不需要找到该结点的最短路径{lowcost[j]=TG.arcs[k][j];primqueue[j]=k;}}}return cost;}void netting()// 求任意一点走遍全校最短路径{int start; int i;int x;int flag=0;int length=0;printf("请输入景点编号：");scanf("%d",&start);for(i=0;i<TG.vexnum;i++)if(TG.vexs[i].num==start){flag=1;x=i;}if(flag==0){printf("输入的编号不存在！");getchar();getchar();system("cls");menu();}length=prim(x);printf("总长度为：%dm ",length);getchar();getchar();system("cls");menu();}int main(){initG();menu();return 0; }
