算法大作业

常熟理工学院 计算机科学与工程学院 大作业

2018-2019 学年第 1 学期

1 / 17

实验名称 学生查询系统 熟悉链表的创建、删除、添加节点的相关知识，以及链实验目的 表排序算法的相关内容 PC机 实验设备 实验日期 2018年12月12日 2 / 17

一、实验预习 二、实验内容 (原理、方法、框图) 利用链表(堆，AVL 平衡树)实现下述功能: 1、学生信息录入功能，即链表插入新节点，新节点至少包 含学号、英语成绩字段；链表可以是单向或者双向链表； 2、学生信息按照学号排序；采用冒泡、插入或者快速排序 法； 3、学生信息按照英语成绩排序；采用冒泡、插入或者快速 排序法；排序方法与 2 不同； 4、利用折半法查询学号和英语成绩功能，并显示信息； 5、学生信息删除功能，即从链表中删除节点； 6、学生信息修改功能，即修改链表节点中的某些属性，并 完成排序； 7、学生信息添加功能，即增加链表节点，并完成排序； 3 / 17

#include #include #include #include #include #include #define Esc 27 #define LEN sizeof(struct student) /* 单链表 插入节点 链表排序 1、按照学号进行冒泡排序2、按照英语成绩进行选择排序 查询节点折半查找查询学号与英语并显示信息 删除节点 修改节点修改属性并完成排序 添加节点完成排序 */ //函数的声明 struct student *createLinkList(); void printInof(struct student *head); struct student *deleteNodes(struct student *head, int num); struct student *insert1(struct student *head, struct student *stud); struct student *bubbleSort(struct student *head); struct student *bubbleSortByEnglishScore(struct student *head); struct student *search1(struct student *head, int num); struct student *modify(struct student *head, int num); float getAvg(struct student *p); void start(); void goon(); void exit1(); void menu(); struct student { int num; //学号 char name[20]; //姓名 char major[20]; //专业 float algorithmScore; //算法课程成绩 float englishScore; //大学英语课程成绩 float mathScore; //高等数学课程成绩 float avgScore; //平均成绩 4 / 17

struct student *next; }; int n; //全局变量，统计学生记录的个数 int main() { struct student *head,*stu; int Delete_num; int lookup_num; int Modify_num; char ckey='a'; int istate=0; do { system(\ //vc++清屏函数，包含在#include中 menu(); ckey=getch(); if(ckey=='1') //创建 { system(\ head=createLinkList(); printInof(head); istate=1; //记录链表是否有数据 goon(); } else if((istate==0)&&(ckey!=Esc)) { printf(\错误：你必须先输入学生信息！！！\ goon(); } else if(ckey=='2') //显示 { system(\ printInof(head); goon(); } else if(ckey=='3') //查找 { system(\ printf(\ \\n\\t请输入你要查找的学生学号：\ scanf(\ head=search1(head,lookup_num); 5 / 17

goon(); } else if(ckey=='4') //修改 { system(\ printf(\ \\n\\t请输入你要修改学生信息的学号：\ scanf(\ head=modify(head,Modify_num); goon(); } else if(ckey=='5') //插入 { system(\ printf(\ \\n\\t请输入你要插入的学生信息：\\n\\n\ stu=(struct student*)malloc(LEN); printf(\请输入学生信息,格式为（每输入一项回车）\\n\ printf(\请输入学生学号：\ scanf(\ printf(\请输入学生姓名：\ scanf(\ printf(\请输入学生专业：\ scanf(\ printf(\请输入算法设计成绩：\ scanf(\ printf(\请输入大学英语成绩：\ scanf(\ printf(\请输入高等数学成绩：\ scanf(\ stu->avgScore=getAvg(stu); //求stu的平均分数 head=insert1(head,stu); goon(); } else if(ckey=='6') //删除 { system(\ printf(\请输入你要删除的学生学号\ scanf(\ head=deleteNodes(head,Delete_num); goon(); } else if(ckey=='7') //学生信息按照学号排序并输出 { system(\ printf(\学生信息按照学号排序并输出\6 / 17

head=bubbleSort(head); printInof(head); goon(); } else if(ckey=='8') //学生信息按照英语成绩排序并输出 { system(\ printf(\学生信息按照英语成绩排序并输出\ head=bubbleSortByEnglishScore(head); printInof(head); goon(); } } while(ckey!=Esc); //按键盘上的Esc键退出！！！ exit1(); return 0; } //创建链表，输入学生信息 struct student *createLinkList() { struct student *head; struct student *pl; n=0; pl=(struct student*) malloc(LEN); printf(\请输入学生的信息: \\n\ printf(\输入格式为：(每输入一项回车，以学号为0退出!)\\n\ printf(\请输入学生学号:\ scanf(\ printf(\请输入学生姓名:\ scanf(\ printf(\请输入学生专业:\ scanf(\ printf(\请输入算法课程成绩:\ scanf(\ printf(\请输入大学英语成绩:\ scanf(\ printf(\请输入高等数学成绩:\ scanf(\ head=NULL; while(pl->num!=0) { pl->avgScore =getAvg(pl); //求pl的平均值 head=insert1(head,pl); //创建链表 7 / 17

pl=(struct student*)malloc(LEN); printf(\如果你想结束输入，请输入 0 !\\n\ printf(\请输入学号:\ scanf(\ if(pl->num ==0) //控制是否退出 continue; printf(\请输入学生姓名:\ scanf(\ printf(\请输入学生专业:\ scanf(\ printf(\请输入算法课程成绩:\ scanf(\ printf(\请输入大学英语成绩:\ scanf(\ printf(\请输入高等数学成绩:\ scanf(\ } return (head); } //输出链表 void printInof(struct student *head) { struct student *p; printf(\现在有%d个记录是:\\n\ p=head; printf(\学生成绩信息表------------------\\n\\n\ printf(\学号\\t姓名\\t班级\\t算法设计大学英语高等数学平均分 \\n\ if(head!=NULL) { do { printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ printf(\ p=p->next ; } while(p!=NULL); } } //根据学号来删除学生信息 8 / 17

struct student *deleteNodes(struct student *head, int num) { struct student *p1,*p2; if(head==NULL) //空链表时返回 { printf(\链表为空!\\n\ return(head); } p1=head; while(num!=p1->num &&p1->next!=NULL) { p2=p1; p1=p1->next ; } if(num==p1->num ) //链表找到相应的学号 { if(p1==head) head=p1->next ; else //表中和表尾删除 p2->next =p1->next ; printf(\你删除的学生信息为: \\n\ printf(\学号为：%d\\n\ printf(\姓名为：%s\\n\ printf(\专业为：%s\\n\ printf(\算法设计成绩为：%.2f\\n\ printf(\大学英语成绩为：%.2f\\n\ printf(\高等数学成绩为：%.2f\\n\ printf(\平均成绩为：%.2f\\n\ printf(\ n=n-1; free(p1); } else //找不到学号 printf(\学号%d没有找到!\\n\ return(head); } //插入学生信息 struct student *insert1(struct student *head, struct student *stud) { struct student *p0,*temp; p0=stud; if(head==NULL) //空链表时返回 { p0->next =NULL; 9 / 17

head=p0; } else//头插法 { temp=head->next; head->next=stud; stud->next=temp; } n=n+1; return(head); } struct student *bubbleSort(struct student *head) { struct student *cur,*tail; cur=head; tail=NULL; if(cur==NULL||cur->next==NULL){ return; } while(cur!=tail) { while(cur->next!=tail) { if(cur->num > cur->next->num) { int temp0=cur->num; cur->num=cur->next->num; cur->next->num=temp0; float temp1=cur->algorithmScore; cur->algorithmScore=cur->next->algorithmScore; cur->next->algorithmScore=temp1; float temp2=cur->avgScore; cur->avgScore=cur->next->avgScore; cur->next->avgScore=temp2; float temp3=cur->englishScore; cur->englishScore=cur->next->englishScore; cur->next->englishScore=temp3; char temp4[20]; 10 / 17

strcpy(temp4,cur->major); /*cur->major=cur->next->major;*/ strcpy(cur->major,cur->next->major); /*cur->next->major=temp4;*/ strcpy(cur->next->major,temp4); float temp5=cur->mathScore; cur->mathScore=cur->next->mathScore; cur->next->mathScore=temp5; char temp6[20]; strcpy(temp6,cur->name); strcpy(cur->name,cur->next->name); strcpy(cur->next->name,temp6); } cur=cur->next; } tail=cur; cur=head; } return(head); } /*对英语成绩进行冒泡排序*/ struct student *bubbleSortByEnglishScore(struct student *head) { struct student *cur,*tail; cur=head; tail=NULL; if(cur==NULL||cur->next==NULL){ return; } while(cur!=tail) { while(cur->next!=tail) { if(cur->englishScore < cur->next->englishScore) { int temp0=cur->num; cur->num=cur->next->num; cur->next->num=temp0; float temp1=cur->algorithmScore; 11 / 17

cur->algorithmScore=cur->next->algorithmScore; cur->next->algorithmScore=temp1; float temp2=cur->avgScore; cur->avgScore=cur->next->avgScore; cur->next->avgScore=temp2; float temp3=cur->englishScore; cur->englishScore=cur->next->englishScore; cur->next->englishScore=temp3; char temp4[20]; strcpy(temp4,cur->major); /*cur->major=cur->next->major;*/ strcpy(cur->major,cur->next->major); /*cur->next->major=temp4;*/ strcpy(cur->next->major,temp4); float temp5=cur->mathScore; cur->mathScore=cur->next->mathScore; cur->next->mathScore=temp5; char temp6[20]; strcpy(temp6,cur->name); strcpy(cur->name,cur->next->name); strcpy(cur->next->name,temp6); } cur=cur->next; } tail=cur; cur=head; } return(head); } //根据学生学号来查找学生信息 struct student *search1(struct student *head, int num) { struct student *p1; p1=head; if(head==NULL) //空链表时返回 { printf(\链表为空！\\n\12 / 17

return(head); } else { while(num!=p1->num &&p1->next !=NULL) { p1=p1->next ; } if(num==p1->num ) //找到相应的学号则显示 { printf(\你查找的学生信息为：\\n\ printf(\学号为：%d\\n\ printf(\姓名为：%s\\n\ printf(\专业为：%s\\n\ printf(\算法设计成绩为：%.2f\\n\ printf(\大学英语成绩为：%.2f\\n\ printf(\高等数学成绩为：%.2f\\n\ printf(\平均成绩为：%.2f\\n\ } else // 学号不在链表内 printf(\你输入的学号不在链表内！\\n\ } return(head); } //根据学生学号来修改学生的信息 struct student *modify(struct student *head, int num) { struct student *p1,*p2; struct student *stude; stude=(struct student*)malloc(LEN); p1=head; if(head==NULL) //链表为空时不能改变信息 { printf(\链表为空！\\n\ return(head); } else { while(num!=p1->num &&p1->next !=NULL) { p2=p1; p1=p1->next; } 13 / 17

if(num==p1->num ) // 找到相应的学号时 { if(p1==head) //表头删除 head=p1->next ; else //表中和表尾删除 p2->next =p1->next ; printf(\你要修改的学号为%d的修改前信息为：\\n\ printf(\学号为：%d\\n\ printf(\姓名为：%s\\n\ printf(\专业为：%s\\n\ printf(\ printf(\算法设计成绩为：%.2f\\n\ printf(\大学英语成绩为：%.2f\\n\ printf(\高等数学成绩为：%.2f\\n\ printf(\平均成绩为：%.2f\\n\ printf(\请输入你要改变的成绩：（格式为：每输入一次回车）\\n\ printf(\请输入算法设计成绩：\\n\ scanf(\ printf(\请输入大学英语成绩：\\n\ scanf(\ printf(\请输入高等数学成绩：\\n\ scanf(\ p1->algorithmScore =stude->algorithmScore ; p1->englishScore =stude->englishScore ; p1->mathScore =stude->mathScore ; p1->avgScore =getAvg(p1); head=insert1(head,p1); //n=n-1; } else //找不到学号时 printf(\你要修改的学号不在链表内！\\n\ } return(head); } //根据输入的各科成绩来计算平均分 float getAvg(struct student *p) { p->avgScore =(p->algorithmScore +p->englishScore +p->mathScore )/3; return p->avgScore ; } void menu() //系统主界面 { printf(\-------欢迎使用学生成绩管理系统-------\14 / 17

printf(\ <1>录入学生成绩表 \ printf(\ <2>输出学生成绩表 \ printf(\ <3>按学号查找学生成绩信息\ printf(\ <4>按姓名修改学生成绩信息 \ printf(\ <5>添加学生成绩信息 \ printf(\ <6>按学号删除学生信息 \ printf(\ <7>学生信息按照学号排序输出 \ printf(\ <8>学生信息按照英语成绩排序输出 \ printf(\ ESC.退出系统 \ printf(\ ----------请您选择操作选项------------\ printf(\ 请输入您的选择(1-8)：\} void goon() { printf(\按任意键继续！！！\ getch(); } void exit1() { system(\ printf(\= = = = = = = = = = = = = = = = = =\ printf(\= = =谢谢使用学生成绩管理系统= = =\ printf(\= = = = = = = = = = = = = = = = = = \\n\\n\} 15 / 17

四、实验结果（遇到的问题及解决方法） 0. 初始界面 1. 录入学生信息 16 / 17 五、心得体会 (实验收获) 本次实验用单链表实现学生成绩信息系统，熟悉了结构体链表的基本操作，如结构体的使用、动态申请内存、链表的创建、链表的节点的插入（我使用的是头插法）、链表节点的删除（注意释放内存）、链表冒泡排序（交换的是节点的数据域，交换指针域的话涉及四个节点的首地址）、以及链表的查找操作，收获颇丰！ 实验预习20% 实验过程20% 实验结果30% 实验报告30% 成绩 日期

17 / 17

本文来源：https://www.bwwdw.com/article/cni8.html