数据结构课设（线性表，栈和队列，链表，图，排序查找）
发布日期：2021-05-07 23:24:19
浏览次数：16
分类：原创文章
本文共 70659 字，大约阅读时间需要 235 分钟。
数据结构
一. 图（行车路线）
【1】题目
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=16+2+4=22。
现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。
输入格式
输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。
接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。
【2】输出格式
输出格式
输出一个整数，表示最优路线下小明的疲劳度。
样例输入
6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1
样例输出
76
【3】样例说明
从1走小道到2，再走小道到3，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。
【4】数据规模和约定
对于30%的评测用例，1≤n≤8，1≤m≤10；
对于另外20%的评测用例，不存在小道；
对于另外20%的评测用例，所有的小道不相交；
对于所有评测用例，1≤n≤500，1≤m≤105，1≤a, b≤n，t是0或1，c≤105。保证答案不超过106。
【5】代码
#include <stdio.h>#include <stdlib.h>#include <string.h>#define maxx 9999typedef struct MyGraph//用邻接矩阵来表示{ int arcnum; //边的数量 int vexnum; //顶点的数量 int **A; //大街道邻接矩阵 int **B; //小街道邻接矩阵}GH;void creatgraph(GH *G); //以邻接矩阵的形式创建图void showgraph(GH *G); //以邻接矩阵的形式显示图void pilao(GH *G,int start,int end,int n);int main(){ int start,end; GH G; creatgraph(&G);//创建并展示图 printf("\n请输入你的起点："); scanf("%d",&start); printf("\n请输入你的终点："); scanf("%d",&end); pilao(&G,start-1,end-1,G.vexnum); return 0;}void creatgraph(GH *G)//创建图{ int i,j; int k,m,n,t; int a,b,c;scanf("%d %d",&n,&m); G->vexnum=n; G->arcnum=m; G->A=(int **)malloc(n*sizeof(int *)); G->B=(int **)malloc(n*sizeof(int *)); for(i=0;i<n;i++) { G->A[i]=(int *)malloc(n*sizeof(int)); G->B[i]=(int *)malloc(n*sizeof(int)); for(j=0;j<n;j++) { G->A[i][j]=maxx; G->B[i][j]=maxx; } G->A[i][i]=0; G->B[i][i]=0; } for(i=0;i<m;i++) { scanf("%d %d %d %d",&t,&a,&b,&c); if(!t)//A为大道 { G->A[a-1][b-1]=c; G->A[b-1][a-1]=c; } else//B为小道 { G->B[a-1][b-1]=c; G->B[b-1][a-1]=c; } } showgraph(G); //显示图 for(k=0;k<n;k++) //求每个点之间小道的最短距离 for(i=0;i<n;i++) for(j=0;j<n;j++) if(G->B[i][j]>G->B[i][k]+G->B[k][j]) G->B[i][j]=G->B[i][k]+G->B[k][j];}void showgraph(GH *G)//显示图{ int i,j; for(i=0;i<G->vexnum;i++) { printf("%d号路口",i+1); for(j=0;j<G->vexnum;j++) { if(G->A[i][j]<maxx&&G->A[i][j]) printf("-->%d号路口(走大道，距离：%d)",j+1,G->A[i][j]); else if(G->B[i][j]<maxx&&G->B[i][j]) printf("-->%d号路口(走小道，距离：%d)",j+1,G->B[i][j]); } printf("\n\n"); } printf("\n");}void pilao(GH *G,int start,int end,int n){ int i,k,head=0,rear=0; int dis[n],dis1[n],v,f[n]; rear++; int q[n]; for(i=0;i<n;i++)//初始化 { f[i]=0; dis[i]=maxx; dis1[i]=maxx; } f[start]=1; q[0]=start;//把第一个结点入队 dis[start]=0;//除了起始点以外其余全部赋给无穷大 dis1[start]=0; while(head!=rear)//判断队列是否为空 { k=q[head++];//队首出队 f[k]=0;//f数组是一个标记函数，如果是0那么队列中没有，如果是1那么队列中存在 if(head>=n) head=0;//防止队列溢出 for(i=0;i<n;i++)//各点循环 { if(i==k)//如果是自己到自己那么不运行下面的 continue; v=G->A[k][i];//取出 if(dis[i]>dis[k]+v)//走大道 { dis[i]=dis[k]+v; if(!f[i])//判断是否在队列中，已经存在就不入队 { f[i]=1; q[rear++]=i; if(rear>=n) rear=0; } } if(dis[i]>dis1[k]+v)//走小道 { dis[i]=dis1[k]+v; if(!f[i]) { f[i]=1; q[rear++]=i; if(rear>=n) rear=0; } } if(G->B[i][k]<maxx)//小道权值的判断 { v=G->B[i][k]*G->B[i][k]; if(dis1[i]>dis[k]+v) { dis1[i]=dis[k]+v; if(!f[i]) { f[i]=1; q[rear++]=i; if(rear>=n) rear=0; } } } } } printf("\n从%d号路口到%d号路口的最小疲劳值：%d\n",start+1,end+1,dis[end]>dis1[end]?dis1[end]:dis[end]); printf("\n------------------------------起点%d号路口到各路口的最小疲劳值------------------------------\n",start+1); for(i=0;i<n;i++) printf("\n从%d号路口到%d号路口的最小疲劳值：%d\n",start+1,i+1,dis[i]>dis1[i]?dis1[i]:dis[i]);}【6】运行样式
二. 链表
【1】一元多项式计算
#include<cstdio>#include<cstdlib>#include<cmath>#include<algorithm>using namespace std;typedef struct node{ int coe; int exp; struct node *next;}Node;class poly//多项式(polynomial){ private: Node *head; int len;public: poly();//构造函数，生成头结点 int getlen();//获得链表长度，有时会很有用 void input(int tag);//输入多项式 void Insert(int index,int x1,int x2);//插入结点（此题中在尾部插入） void add(poly a,poly b);//加法 void sub(poly a,poly b);//减法 void mul(poly a,poly b);//乘法（最难搞） void dif(poly a);//求导（注意不要影响到原来的多项式） void val(float v);//求值 void clr();//清空多项式 void show();//输出多项式};poly::poly()//构造函数，生成头结点{ head=new Node; if(head==NULL) { printf("memory allocation error!"); exit(1); } head->next=NULL; len=0;}int poly::getlen()//获得链表长度，有时会很有用{ return len;}void poly::input(int tag)//输入多项式{ int a,b; Node *p=head; scanf("%d",&a); scanf("%d",&b); while(a!=0) { Node*t=new Node; if(t==NULL) { printf("memory allocation error!"); exit(1); } t->coe=a; t->exp=b; p->next=t; p=t; len++; scanf("%d",&a); if(a==0)break; scanf("%d",&b); } p->next=NULL;}void poly::Insert(int index,int x1,int x2)//插入结点（此题中在尾部插入）{ if(index>len+1||index<0) { printf("not insert!"); exit(1); } int i=0; Node *p=head; while(p->next!=NULL&&i<=index-2) { p=p->next; i++; } Node *t=new Node; t->coe=x1; t->exp=x2; t->next=p->next; p->next=t; len++;}void poly::add(poly a,poly b)//加法{ if(a.getlen()==0||b.getlen()==0) { printf("error!\n"); return; } Node *t1,*t2; int k=0; t1=a.head->next; t2=b.head->next; while(t1!=NULL&&t2!=NULL) { if(t1->exp<t2->exp) { Insert(++k,t1->coe,t1->exp); t1=t1->next; } else if(t1->exp>t2->exp) { Insert(++k,t2->coe,t2->exp); t2=t2->next; } else { if(t1->coe+t2->coe!=0)Insert(++k,t1->coe+t2->coe,t2->exp); t1=t1->next; t2=t2->next; } } while(t1!=NULL) { Insert(++k,t1->coe,t1->exp); t1=t1->next; } while(t2!=NULL) { Insert(++k,t2->coe,t2->exp); t2=t2->next; }}void poly::sub(poly a,poly b)//减法{ if(a.getlen()==0||b.getlen()==0) { printf("error!\n"); return; } Node *t1,*t2; int k=0; t1=a.head->next; t2=b.head->next; while(t1!=NULL&&t2!=NULL) { if(t1->exp<t2->exp) { Insert(++k,t1->coe,t1->exp); t1=t1->next; } else if(t1->exp>t2->exp) { Insert(++k,-t2->coe,t2->exp); t2=t2->next; } else { if(t1->coe-t2->coe!=0)Insert(++k,t1->coe-t2->coe,t2->exp); t1=t1->next; t2=t2->next; } } while(t1!=NULL) { Insert(++k,t1->coe,t1->exp); t1=t1->next; } while(t2!=NULL) { Insert(++k,-t2->coe,t2->exp); t2=t2->next; }}void poly::mul(poly a,poly b)//乘法（最难搞）{ if(a.getlen()==0||b.getlen()==0) { printf("error!\n"); return; } Node*t1,*t2,*t3; t1=a.head->next; t2=b.head->next; int k=0,x,y; while(t2!=NULL) { Insert(++k,t1->coe*t2->coe,t1->exp+t2->exp); t2=t2->next; } t1=t1->next; while(t1!=NULL) { t2=b.head->next; t3=head->next; while(t2!=NULL) { x=t1->coe*t2->coe; y=t1->exp+t2->exp; while(t3->next!=NULL&&t3->exp<y) { if(t3->next->exp<=y)t3=t3->next; else break; } if(t3->next==NULL)Insert(++k,x,y); else { if(t3->exp==y) { if(t3->coe+x!=0)t3->coe+=x; else { Node *t=new Node; t=t3->next; t3->next=t->next; delete t; } } else if(t3->exp<y) { Node *temp=new Node; temp->coe=x; temp->exp=y; temp->next=t3->next; t3->next=temp; t3=t3->next; } } t2=t2->next; } t1=t1->next; } t1=head; while(t1->next!=NULL) { t2=t1->next; while(t2->next!=NULL) { if(t1->next->exp==t2->next->exp) { if(t1->next->coe+t2->next->coe==0) { Node *t,*t0; t=t1->next; t1->next=t->next; delete t; len--; t0=t2->next; t2->next=t0->next; delete t0; len--; } else { t1->next->coe+=t2->next->coe; Node*t; t=t2->next; t2->next=t->next; delete t; len--; } } t2=t2->next; } t1=t1->next; }}void poly::dif(poly a)//求导（注意不要影响到原来的多项式）{ if(a.getlen()==0) { printf("error!\n"); return; } Node *t; int k=0; t=a.head; while(t->next!=NULL) { if(t->next->exp!=0)Insert(++k,t->next->coe*t->next->exp,t->next->exp-1); t=t->next; } t->next=NULL;}void poly::val(float v)//求值{ float sum=0; Node*t5; t5=head->next; while(t5!=NULL) { sum+=t5->coe*pow(v,t5->exp); t5=t5->next; } printf("%.2f\n",sum);}void poly::clr()//清空多项式{ Node *t; while(head->next!=NULL) { t=head->next; head->next=t->next; delete t; len--; }}void poly::show()//输出多项式{ Node*t; int k=1; t=head->next; printf("C(x)="); while(t!=NULL&&k<=len) { if(t->coe==-1)printf("-"); else if(t->coe!=1) { if(t->coe>0&&t!=head->next)printf("+"); if(t->coe!=0)printf("%d",t->coe); } if(t->exp!=0) { printf("x"); if(t->exp!=1)printf("^%d",t->exp); } t=t->next; k++; } printf("\n");}int main(){ char op[5]; float v; poly a,b,cadd,csub,cmul,cdiff; while(true) { scanf("%s",op); if(op[0]=='C') { if(a.getlen()==0) { a.input(0); } else a.clr(); if(b.getlen()==0) { b.input(0); } else b.clr(); if(cadd.getlen()!=0)cadd.clr(); if(csub.getlen()!=0)csub.clr(); if(cmul.getlen()!=0)cmul.clr(); if(cdiff.getlen()!=0)cdiff.clr(); } else if(op[0]=='S') { csub.sub(a,b); csub.show(); } else if(op[0]=='P') { cadd.add(a,b); cadd.show(); } else if(op[0]=='M') { cmul.mul(a,b); cmul.show(); } else if(op[0]=='D') { cdiff.dif(a); cdiff.show(); } else if(op[0]=='V') { scanf("%f",&v); a.val(v); } else if(op[0]=='X')exit(0); } return 0;}#include <stdio.h>#include <stdlib.h>#define ERROR -1//多项式表示typedef struct PolyNode *Poly;struct PolyNode{ int coef;//系数 int expon;//指数 Poly Link;//指针};void Attach(int c,int e,Poly *pReal){ Poly p; p=(Poly)malloc(sizeof(struct PolyNode)); p->coef=c; p->expon=e; p->Link=NULL; (*pReal)->Link=p; *pReal=p;}Poly ReadPoly()//读入多项式{ int N,c,e; Poly p,t,Real; p=(Poly)malloc(sizeof(struct PolyNode)); p->Link=NULL; Real=p; scanf("%d",&N); while(N--) { scanf("%d %d",&c,&e); Attach(c,e,&Real); } t=p; p=p->Link; free(t); return p;}Poly Mult(Poly p1,Poly p2)//相乘{ Poly t1,t2,p,Real,t; int c,e; if(!p1||!p2)return NULL; t1=p1;t2=p2; p=(Poly)malloc(sizeof(struct PolyNode)); p->Link=NULL; Real=p; while(t2)//t2的每一项去成t1的第一项 { Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Real); t2=t2->Link; } t1=t1->Link;//t1h后移一项 while(t1) { t2=p2; Real=p; while(t2) { c=t1->coef*t2->coef; e=t1->expon+t2->expon; while(Real->Link&&Real->Link->expon>e)//寻找比他次数小的就退出循环 Real=Real->Link; if(Real->Link&&Real->Link->expon==e)//如果次数相等，判断相加是否为0 { if(!(c+Real->Link->coef))//相加等于0，删除 { t=Real->Link; Real->Link=t->Link; free(t); } else { Real->Link->coef+=c; } } else//次数不相等插入 { t=(Poly)malloc(sizeof(struct PolyNode)); t->coef=c; t->expon=e; t->Link=NULL; t->Link=Real->Link; Real->Link=t; Real=Real->Link; } t2=t2->Link; } t1=t1->Link; } t2=p;p=p->Link; free(t2); return p;}void PrintPoly(Poly p)//输出多项式{ int f=0;//用来判断第一项 if(!p) { printf("0 0\n"); return; } while(p) { if(f==0) f=1; else printf(" "); printf("%d %d",p->coef,p->expon); p=p->Link; } printf("\n");}Poly Add(Poly p1,Poly p2)//相加{ Poly p,Real,t1,t2,t; int c,e; t1=p1;t2=p2; p=(Poly)malloc(sizeof(struct PolyNode)); p->Link=NULL; Real=p; while(t1&&t2) { if(t1->expon==t2->expon) { if(t1->coef+t2->coef==0) { t1=t1->Link; t2=t2->Link; } else { c=t1->coef+t2->coef; e=t1->expon; Attach(c,e,&Real); t1=t1->Link; t2=t2->Link; } } else if(t1->expon>t2->expon) { c=t1->coef; e=t1->expon; Attach(c,e,&Real); t1=t1->Link; } else { c=t2->coef; e=t2->expon; Attach(c,e,&Real); t2=t2->Link; } } while(t1) { c=t1->coef; e=t1->expon; Attach(c,e,&Real); t1=t1->Link; } while(t2) { c=t2->coef; e=t2->expon; Attach(c,e,&Real); t2=t2->Link; } t=p; p=p->Link; free(t); return p;}int main(){ Poly p1,p2,pp,ps; p1=ReadPoly(); p2=ReadPoly(); pp=Mult(p1,p2); PrintPoly(pp); ps=Add(p1,p2); PrintPoly(ps);}一元计算器
【2】学生管理系统
#include <stdio.h>#include <string.h>#include <conio.h>#include <time.h>#include <stdlib.h>#define HEADER2 " **********************************************************************\n * 学号 姓名 学科1 学科2 学科3 学科4 学科5 总分 平均 *\n **********************************************************************\n"#define FORMAT " * %8s %7s %5d %5d %5d %5d %5d %5d %.2f *\n **********************************************************************\n"#define DATA p->data.num,p->data.name,p->data.grade[0],p->data.grade[1],p->data.grade[2],p->data.grade[3],p->data.grade[4],p->data.total,p->data.aveint saveflag=0; /*是否需要存盘的标志变量*/int sortflag=0; /*是是否已经排序的标志变量*/time_t now;/*系统时间*/struct student { char num[20]; /*学号*/ char name[15]; /*姓名*/ int grade[5]; /*学科成绩*/ int total; /*总分*/ float ave; /*平均分*/};typedef struct node{ //定义每条记录或结点的数据结构 struct student data; /*数据域*/ struct node *next; /*指针域*/}Node,*Link; /*Node为node类型的结构变量，*Link为node类型的指针变量*/void menu() { now = time (NULL); printf(" 学生成绩管理系统 \n"); printf("\n"); printf(" *************************************************************\n"); printf(" * *\n"); printf(" * 1 输入成绩 2 删除成绩 *\n"); printf(" * *\n"); printf(" * 3 查询成绩 4 修改成绩 *\n"); printf(" * *\n"); printf(" * 5 排序成绩 6 保存记录 *\n"); printf(" * *\n"); printf(" * 7 不及格学生 8 优秀学生 *\n"); printf(" * *\n"); printf(" * 9 显示所有 0 退出系统 *\n"); printf(" * *\n"); printf(" *************************************************************\n"); printf(" * 10 切换登录模式 11 修改管理员信息 *\n"); printf(" *************************************************************\n"); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf("\n *************************************************************\n"); printf(" * 请您选择操作命令(0~11):"); /*显示提示信息*/}void menu2(){ now = time (NULL); system("cls"); //清屏 printf("\n 来宾模式\n\n\n"); printf(" 学生成绩管理系统 \n"); printf("\n"); printf(" *************************************************************\n"); printf(" * *\n"); printf(" * 1 查询成绩 2 排序成绩 *\n"); printf(" * *\n"); printf(" * 3 不及格学生 4 优秀学生 *\n"); printf(" * *\n"); printf(" * 5 显示所有 0 退出系统 *\n"); printf(" * *\n"); printf(" *************************************************************\n"); printf(" * 6 切换登录模式 *\n"); printf(" *************************************************************\n"); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf("\n *************************************************************\n"); printf(" * 请您选择操作命令(0~6):"); /*显示提示信息*/}void sortmenu(){ now = time (NULL); system("cls"); //清屏 printf("\n 学生成绩管理系统 \n"); printf("\n"); printf(" ****************************排序菜单*************************\n"); printf(" * *\n"); printf(" * 1 按学号从小到大 2 按学号从大到小 *\n"); printf(" * *\n"); printf(" * 3 按总分从小到大 4 按总分从大到小 *\n"); printf(" * *\n"); printf(" * 5 按学科1从小到大 6 按学科1从大到小 *\n"); printf(" * *\n"); printf(" * 7 按学科2从小到大 8 按学科2从大到小 *\n"); printf(" * *\n"); printf(" * 9 按学科3从小到大 10 按学科3从大到小 *\n"); printf(" * *\n"); printf(" * 11 按学科4从小到大 12 按学科4从大到小 *\n"); printf(" * *\n"); printf(" * 13 按学科5从小到大 14 按学科5从大到小 *\n"); printf(" * *\n"); printf(" * 0 按姓名字典序排序 *\n"); printf(" *************************************************************\n"); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf("\n *************************************************************\n"); printf(" * 请您选择操作命令(0~14):"); /*显示提示信息*/}void printheader(){ printf(HEADER2);} /*格式化输出表头*/void printdata(Node *pp) { Node* p; p=pp; printf(FORMAT,DATA);}/*格式化输出表中数据*/void Wrong() { printf("\n"); printf(" *************************************************************\n"); printf(" * 错误:输入不合法!!! *\n"); printf(" *************************************************************\n"); getch();}/*输出按键错误信息*/void Nofind(){ /*输出未查找此学生的信息*/ printf("\n"); printf(" *************************************************************\n"); printf(" * 没有该学生!!! *\n"); printf(" *************************************************************\n");}void Disp(Link l){ /*显示单链表l中存储的学生记录，内容为student结构中定义的内容*/ system("cls"); //清屏 Node *p; p=l->next; /*l存储的是单链表中头结点的指针，该头结点没有存储学生信息，指针域指向的后继结点才有学生信息*/ printf("\n 学生成绩管理系统 \n"); if(!p) /*p==NULL,NUll在stdlib中定义为0*/ { printf(" ***************************学生记录**************************\n"); printf(" * 无学生记录！ *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); return; } printheader(); /*输出表格头部*/ while(p) /*逐条输出链表中存储的学生信息*/ { printdata(p); p=p->next; /*移动直下一个结点*/ } now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now));}Node *Locate(Link l,char findmess[],char nameornum[]){ Node *r; if(strcmp(nameornum,"num")==0) /*按学号查询*/ { r=l->next; while(r) { if(strcmp(r->data.num,findmess)==0) /*若找到findmess值的学号*/ return r; r=r->next; } } else if(strcmp(nameornum,"name")==0) /*按姓名查询*/ { r=l->next; while(r) { if(strcmp(r->data.name,findmess)==0) /*若找到findmess值的学生姓名*/ return r; r=r->next; } } return 0; /*若未找到，返回一个空指针*/}void failStu(Link l){ Node *r; int q,sum=0; system("cls"); now = time (NULL); printf("\n 学生成绩管理系统 \n"); printheader(); r=l->next; while(r) { int i; q=0; for(i=0;i<5;i++) if(r->data.grade[i]<60) { q=1; break; } if(q) { printdata(r); } sum+=q; r=r->next; } if(sum) printf(" * 共有%d名学生不及格 *\n",sum); else printf(" * good,没有同学不及格 *\n",sum); printf(" **********************************************************************\n"); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); getchar();}void prefectStu(Link l){ Node *r; int q,sum=0; system("cls"); now = time (NULL); printf("\n 学生成绩管理系统 \n"); printheader(); r=l->next; while(r) { int i; q=0; for(i=0;i<5;i++) if(r->data.grade[i]>=90) { q=1; break; } if(q) { printdata(r); } sum+=q; r=r->next; } if(sum) printf(" * 共有%d名学生优秀 *\n",sum); else printf(" * poor,没有同学是优秀的 *\n",sum); printf(" **********************************************************************\n"); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); getchar();}void stringinput(char *t,int lens,char *notice){ /*输入字符串信息*/ char n[255]; do { printf(notice); /*显示提示信息*/ scanf("%s",n); /*输入字符串*/ if(strlen(n)>lens) /*进行长度校验，超过lens值重新输入*/ { printf("\n"); printf(" *************************************************************\n"); printf(" * 超出长度!!! *\n"); printf(" *************************************************************\n"); } }while(strlen(n)>lens); strcpy(t,n); /*将输入的字符串拷贝到字符串t中*/}int numberinput(char *notice){ /*输入分数信息*/ int t=0; do { printf(notice); /*显示提示信息*/ scanf("%d",&t); /*输入分数*/ if(t>100 || t<0) //分数校验 { printf("\n"); printf(" *************************************************************\n"); printf(" * 分数必须在0~100之间!!! *\n"); printf(" *************************************************************\n"); } }while(t>100 || t<0); return t;}void Add(Link l){ /*在表尾添加学生信息*/ Node *p,*r,*s; int i; char ch,flag=0,num[10]; r=l; system("cls"); Disp(l); /*先打印出已有的学生信息*/ while(r->next!=NULL) r=r->next; /*将指针移至于链表最末尾，准备添加记录*/ while(1) /*一次可输入多条记录，直至输入学号为0的记录结点添加操作*/ { s=l->next; while(1) { printf(" **********************************************************************\n"); stringinput(num,10," * 学号(按0退出):"); /*格式化输入学号并检验*/ flag=0; if(strcmp(num,"0")==0) /*输入为0，则退出添加操作，返回主界面*/ return ; s=l->next; while(s) /*查询该学号是否已经存在，若存在则要求重新输入一个未被占用的学号*/ { if(strcmp(s->data.num,num)==0) { flag=1; break; } s=s->next; } if(flag==1) /*提示用户是否重新输入*/ { getchar(); printf(" **********************************************************************\n"); printf(" * 学号%s已存在，是否重新输入?(y/n)\a",num); scanf("%c",&ch); if(ch=='y'||ch=='Y') continue; else return ; } else break; } p=(Node *)malloc(sizeof(Node)); strcpy(p->data.num,num); /*将字符串num拷贝到p->data.num中*/ printf(" **********************************************************************\n"); stringinput(p->data.name,15," * Name:"); printf(" **********************************************************************\n"); p->data.grade[0]=numberinput(" * 学科1[0-100]:"); printf(" **********************************************************************\n"); p->data.grade[1]=numberinput(" * 学科2[0-100]:"); printf(" **********************************************************************\n"); p->data.grade[2]=numberinput(" * 学科3[0-100]:"); printf(" **********************************************************************\n"); p->data.grade[3]=numberinput(" * 学科4[0-100]:"); printf(" **********************************************************************\n"); p->data.grade[4]=numberinput(" * 学科5[0-100]:"); printf(" **********************************************************************\n"); for(i=0,p->data.total=0;i<5;i++) p->data.total+=p->data.grade[i]; /*计算总分*/ p->data.ave=(float)(p->data.total*1.0/5); /*计算平均分*/ p->next=NULL; while(r->next!=NULL) r=r->next; r->next=p; saveflag=1; }}void Qur(Link l){ /*按学号或姓名，查询学生记录*/ system("cls"); int select; /*1:按学号查，2：按姓名查，其他：返回主界面（菜单）*/ char searchinput[20]; /*保存用户输入的查询内容*/ Node *p; if(!l->next) /*若链表为空*/ { printf("\n 学生成绩管理系统 \n\n"); printf(" ***************************查询成绩**************************\n"); printf(" * 暂无学生记录,查询失败 *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); getchar(); return; } printf("\n 学生成绩管理系统 \n\n"); printf(" ***************************查询成绩**************************\n"); printf(" * *\n"); printf(" * 1 通过学号查找 2 通过姓名查找 *\n"); printf(" * *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf("\n"); printf(" *************************************************************\n"); printf(" * 请选择[1,2]:"); scanf("%d",&select); if(select==1) /*按学号查询*/ { stringinput(searchinput,10," * 请输入要查找的学号:"); p=Locate(l,searchinput,"num");/*在l中查找学号为searchinput值的节点，并返回节点的指针*/ if(p) /*若p!=NULL*/ { printheader(); printdata(p); printf(" *************************************************************\n"); } else Nofind(); } else if(select==2) /*按姓名查询*/ { stringinput(searchinput,15," * 请输入学生姓名:"); p=Locate(l,searchinput,"name"); if(p) { printheader(); printdata(p); printf(" *************************************************************\n"); } else Nofind(); } else Wrong(); system("PAUSE");}void Del(Link l){ //删除学生记录：先找到保存该学生记录的节点，然后删除该节点 int sel; Node *p,*r; char findmess[20]; if(!l->next) { system("cls"); printf("\n"); printf(" 学生成绩管理系统 \n"); printf("\n"); printf(" *************************************************************\n"); printf(" * 暂无学生记录!!! *\n"); printf(" *************************************************************\n"); getch(); return; } system("cls"); Disp(l); printf(" *************************************************************\n"); printf(" * 1 通过学号删除 2 通过姓名删除 *\n"); printf(" * 请选择[1,2]:"); scanf("%d",&sel); if(sel==1) { stringinput(findmess,10," * 请输入学号:"); p=Locate(l,findmess,"num"); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); /*释放内存空间*/ printf(" *************************************************************\n"); printf(" * 删除成功!!! *\n"); printf(" *************************************************************\n"); saveflag=1; } else Nofind(); } else if(sel==2) /*先按姓名查询到该记录所在的节点*/ { stringinput(findmess,15," * 请输入学生姓名："); p=Locate(l,findmess,"name"); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); printf(" *************************************************************\n"); printf(" * 删除成功!!! *\n"); printf(" *************************************************************\n"); saveflag=1; } else Nofind(); } else Wrong(); getchar();}void Modify(Link l){ //修改学生记录.先按输入的学号查询到该记录,然后提示用户修改学号之外的值,学号不能修改 Node *p; int i; char findmess[20]; if(!l->next) { system("cls"); printf("\n 学生成绩管理系统 \n\n"); printf(" *************************************************************\n"); printf(" * 没有学生记录!!! *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); getchar(); return; } system("cls"); printf("修改学生记录"); Disp(l); printf(" **********************************************************************\n"); stringinput(findmess,10," * 请输入学号:"); /*输入并检验该学号*/ printf(" **********************************************************************\n"); p=Locate(l,findmess,"num"); /*查询到该节点*/ if(p) /*若p!=NULL,表明已经找到该节点*/ { printf(" * 学号:%s\n",p->data.num); printf(" * 姓名:%s *\n",p->data.name); stringinput(p->data.name,15," * 输入新姓名:"); printf(" * 学科1:%d *\n",p->data.grade[0]); p->data.grade[0]=numberinput(" * 学科1[0-100]:"); printf(" * 学科2:%d *\n",p->data.grade[1]); p->data.grade[1]=numberinput(" * 学科2[0-100]:"); printf(" * 学科3:%d *\n",p->data.grade[2]); p->data.grade[2]=numberinput(" * 学科3[0-100]:"); printf(" * 学科4:%d *\n",p->data.grade[3]); p->data.grade[3]=numberinput(" * 学科4[0-100]:"); printf(" * 学科5:%d *\n",p->data.grade[4]); p->data.grade[4]=numberinput(" * 学科5[0-100]:"); for(i=0,p->data.total=0;i<5;i++) p->data.total+=p->data.grade[i]; /*计算总分*/ p->data.ave=(float)(p->data.total*1.0/5); printf(" **********************************************************************\n"); printf(" * 修改成功!!! *\n"); printf(" **********************************************************************\n%"); getchar(); saveflag=1; } else Nofind(); getchar();}void Sort(Link l){ system("cls"); Link ll; Node *p,*rr,*s; int i=0,select; if(l->next==NULL) { printf("\n 学生成绩管理系统 \n"); printf(" *************************************************************\n"); printf(" * 暂无学生记录!请输入学生记录后再进行排序 *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); getchar(); getchar(); return ; } sortmenu(); scanf("%d",&select); printf(" *************************************************************\n"); switch(select) { case 1:/*按学号从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.num<p->data.num) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 2:/*按学号从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.num>=p->data.num) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 3:/*按总分从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.total<p->data.total) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 4:/*按总分从大到小*/ { ll=(Node*)malloc(sizeof(Node)); /*用于创建新的节点*/ ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); /*显示排序前的所有学生记录*/ // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); /*新建节点用于保存从原链表中取出的节点信息*/ s->data=p->data; /*填数据域*/ s->next=NULL; /*指针域为空*/ rr=ll; /*rr链表于存储插入单个节点后保持排序的链表，ll是这个链表的头指针,每次从头开始查找插入位置*/ while(rr->next!=NULL && rr->next->data.total>=p->data.total) { rr=rr->next; } /*指针移至总分比p所指的节点的总分小的节点位置*/ if(rr->next==NULL)/*若新链表ll中的所有节点的总分值都比p->data.total大时，就将p所指节点加入链表尾部*/ rr->next=s; else /*否则将该节点插入至第一个总分字段比它小的节点的前面*/ { s->next=rr->next; rr->next=s; } p=p->next; /*原链表中的指针下移一个节点*/ } l->next=ll->next; /*ll中存储是的已排序的链表的头指针*/ p=l->next; /*已排好序的头指针赋给p，准备填写名次*/ while(p!=NULL) /*当p不为空时，进行下列操作*/ { i++; /*结点序号*/ p=p->next; /*指针后移*/ } break; } case 5:/*按学科1从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[0]<p->data.grade[0]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 6:/*按学科1从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[0]>=p->data.grade[0]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 7:/*按学科2从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[1]<p->data.grade[1]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 8:/*按学科2从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[1]>=p->data.grade[1]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 9:/*按学科3从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[2]<p->data.grade[2]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 10:/*按学科3从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[2]>=p->data.grade[2]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 11:/*按学科4从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[3]<p->data.grade[3]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 12:/*/*按学科4从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[3]>=p->data.grade[3]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; /*增加学生记录*/ } case 13:/*按学科5从小到大*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[4]<p->data.grade[4]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 14:/*按学科5从大到小*/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.grade[4]>=p->data.grade[4]) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } case 0:/**/ { ll=(Node*)malloc(sizeof(Node)); ll->next=NULL; printf("当前状态：\n"); // puts("错误不在这！"); Disp(l); // system("PAUSE"); p=l->next; while(p) /*p!=NULL*/ { s=(Node*)malloc(sizeof(Node)); s->data=p->data; s->next=NULL; rr=ll; while(rr->next!=NULL && rr->next->data.name>=p->data.name) { rr=rr->next; } if(rr->next==NULL) rr->next=s; else { s->next=rr->next; rr->next=s; } p=p->next; } l->next=ll->next; p=l->next; while(p!=NULL) { i++; p=p->next; } break; } default: Wrong();getch();break; /*按键有误，必须为数值0-9*/ } printf("\n*********************************************\n");// puts("错误不在这！"); Disp(l); saveflag=1; printf(" **********************************************************************\n"); printf(" * 排序完成!!! *\n"); printf(" **********************************************************************\n"); sortflag=1; system("PAUSE");}void Save(Link l){ //数据存盘,若用户没有专门进行此操作且对数据有修改,在退出系统时,会提示用户存盘 FILE* fp1, *fp2; Node *p; int count=0; fp1=fopen("stu.c","w+");/*以只写方式打开二进制文件*/ fp2=fopen("stu-sort.c","w+");/*以只写方式打开二进制文件*/ if(sortflag==0) { p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp1)==1) { p=p->next; count++; } else break; } if(count>0) { printf("\n\n\n\n\n"); printf(" *************************************************************\n"); printf(" * 保存完毕，当前有%d名学生记录 *\n",count); printf(" *************************************************************\n"); saveflag=0; } else printf("空文件，保存失败!!\n"); fclose(fp1); //关闭此文件 getch(); } else { p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp2)==1) { p=p->next; count++; } else break; } if(count>0) { printf("\n\n\n\n\n 保存完毕，当前有%d名学生记录\n",count); saveflag=0; } else printf("空文件，保存失败!!\n"); fclose(fp2); //关闭此文件 getch(); sortflag=0; }}int login(){ FILE *fp1,*fp2; int state; char str1[20],str2[20],str_z[20],str_m[20]; if((fp1=fopen("admin.txt","rb"))==NULL) { printf("\n 学生成绩管理系统 \n\n"); printf(" *************************创建管理员账号**********************\n"); printf(" * 本系统无管理员，请创建！ *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf(" *************************************************************\n"); printf(" * 请输入管理员账号:"); scanf("%s",str_z); printf(" * 请输入密码: "); scanf("%s",str_m); printf(" *************************************************************\n"); fp2=fopen("admin.txt","wb"); fprintf(fp2,"%s%c",str_z,'\n'); fprintf(fp2,"%s%c",str_m,' '); fclose(fp2); } fp1=fopen("admin.txt","rb"); fscanf(fp1,"%s",str1); fscanf(fp1,"%s",str2); fclose(fp1); while(1) { system("cls"); printf("\n 学生成绩管理系统 \n\n"); printf(" ****************************登录方式*************************\n"); printf(" * *\n"); printf(" * 1.管理员模式 0.来宾模式 *\n"); printf(" * *\n"); printf(" *************************************************************\n"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); printf(" *************************************************************\n"); printf(" * 请你选择(0-1):"); scanf("%d",&state); printf(" *************************************************************\n"); if(state==0) return 0; else if(state==1) { printf("\n *************************************************************\n"); printf(" * 请输入账号:"); scanf("%s",str_z); printf(" * 请输入密码:"); scanf("%s",str_m); printf(" *************************************************************\n"); if(strcmp(str1,str_z)==0&&strcmp(str2,str_m)==0) { getchar(); getchar(); return 1; } else { printf(" *************************************************************\n"); printf(" * 账号或密码错误!!! *\n"); printf(" *************************************************************\n"); system("PAUSE"); system("cls"); } } else { printf(" *************************************************************\n"); printf(" * 输入不合法!!! *\a \n"); printf(" *************************************************************\n"); system("PAUSE"); system("cls"); } }}void Modify_admin(){ FILE *fp; char str_z[20],str_m[20]; fp=fopen("admin.txt","wb"); printf(" *************************************************************\n"); printf(" * 请输入管理员账号:"); scanf("%s",str_z); printf(" * 请输入密码: "); scanf("%s",str_m); printf(" *************************************************************\n"); fprintf(fp,"%s%c",str_z,'\n'); fprintf(fp,"%s%c",str_m,' '); fclose(fp); printf("\n *************************************************************\n"); printf(" * 管理员信息更新完毕!!! *\a\n"); printf(" *************************************************************\n"); getch();}int main(){ system("color 9e");//主屏函数黄色 Link L; /*定义链表*/ FILE *fp,*fp1; /*文件指针*/ int select,State=0; /*保存选择结果变量*/ char ch,admin[20],admin_p[20]; /*保存(y,Y,n,N)*/ int count=0; /*保存文件中的记录条数（或结点个数）*/ Node *p,*r; /*定义记录指针变量*/ L=(Node*)malloc(sizeof(Node)); L->next=NULL; r=L; fp=fopen("stu.c","ab+"); fp1=fopen("stu-sort.c","ab+"); Loop:{ State=login(); } while(!feof(fp)) { p=(Node*)malloc(sizeof(Node)); if(fread(p,sizeof(Node),1,fp)==1) /*一次从文件中读取一条学生成绩记录*/ { p->next=NULL; r->next=p; r=p; /*r指针向后移一个位置*/ count++; } } fclose(fp); /*关闭文件*/ if(State==1) { while(1) { system("cls"); printf("\n 管理员模式\n\n\n"); menu(); p=r; scanf("%d",&select); printf(" *************************************************************\n"); if(select==0) { if(saveflag==1) /*若对链表的数据有修改且未进行存盘操作，则此标志为1*/ { getchar(); printf(" *************************************************************\n"); printf(" * 记录已修改,是否保存当前记录?(y/n):"); scanf("%c",&ch); printf(" *************************************************************\n"); if(ch=='y'||ch=='Y') Save(L); } printf(" *************************************************************\n"); printf(" * 谢谢您的使用!!! *\n"); printf(" *************************************************************\n"); break; } switch(select) { case 1:Add(L);break; /*增加学生记录*/ case 2:Del(L);break; /*删除学生记录*/ case 3:Qur(L);break; /*查询学生记录*/ case 4:Modify(L);break; /*修改学生记录*/ case 5:Sort(L);break; /*排序学生记录*/ case 6:Save(L);break; /*保存学生记录*/ case 7:failStu(L);break; /*不及格学生记录*/ case 8:prefectStu(L);break; /*优秀学生记录*/ case 9:Disp(L);system("PAUSE");break; /*显示学生记录*/ case 10:system("cls");goto Loop; case 11:Modify_admin();break; default: Wrong();getch();break; /*按键有误，必须为数值0-9*/ } } } else { while(1) { system("cls"); now = time (NULL); printf(" Made by ChengXiang, now time is %s\n",ctime(&now)); menu2(); scanf("%d",&select); printf(" *************************************************************\n"); if(select==0) { printf(" *************************************************************\n"); printf(" * 谢谢您的使用!!! *\n"); printf(" *************************************************************\n"); exit(1); } switch(select) { case 1:Qur(L);break; /*查询学生记录*/ case 2:Sort(L);break; /*排序学生记录*/ case 3:failStu(L);break; /*不及格学生记录*/ case 4:prefectStu(L);break; /*优秀学生记录*/ case 5:Disp(L);system("PAUSE");break; /*显示学生记录*/ case 6:system("cls");goto Loop; default: Wrong();getch();break; /*按键有误，必须为数值0-9*/ } } } return 0;}【3】约瑟夫环
#include <iostream>#include <malloc.h>#define NULL 0using namespace std;typedef struct Node{ int code,num; struct Node *next;} Lnode,*linklist;linklist Creatlist(int personnum) //尾插法建立单循环链表链表并进行初始化；{ //初始化，需要参数传递，返回头点； linklist s,r,L; L=new Lnode;; //建立头结点L; L->next=NULL; r=L; for(int i=1; i<=personnum; i++) { s=new Lnode;//逐一接受各个人的密码 cout<<"第 "<<i<<" 个人的密码为: "; cin>>s->code; s->num=i; if(L->next==NULL) L->next=s; else r->next=s; r=s; } r->next=L->next; //尾指针指向头节点； return L; //返回头结点；}void Joseph(linklist head,int m,int num) //Joseph环问题的实现；{ linklist p,s; while(num>0) { p=head; //记录头指针的位置； for(int i=1; i<=m; i++) { s=p; //记录m的前一个值 p=p->next; } m=p->code; cout<<" 更新得到的m的值 : "<<p->code<<" "; cout<<"本次除去的序号为 : "; //新的m值 cout<<p->num<<"\n"; s->next=p->next; //删除p所指的结点； head=s; //确立下一次循环开始的位置； free(p); num--; //结点数减一； }}int main(){ linklist Llist; int m,n; cout<<"请输入报数的初始上限值（整数） : "; cin>>m; cout<<"请输入报数总人数 : "; cin>>n; cout<<"请输入每个人的密码（整数） : "<<endl; Llist=Creatlist(n); cout<<"出列的序列为:"<<endl; Joseph(Llist,m,n); cout<<endl;}/*测试样例m=6 n=7密码 3，1，7，2，4，7，4*/三.栈和队列
【1】迷宫问题
#include <stdio.h>#include<stdlib.h>#include <bits/stdc++.h>#define MAX 100typedef struct{ int i;//当前方块行号 int j;//当前方块列号 int flag;//下一个可走的相邻方块的方位号} mapp; //定义方块类型typedef struct{ mapp data[100]; int top;//栈顶指针} StType; //定义顺序栈类型int mgpath(int xi,int yi,int xe,int ye)//求解路径为：(xi,yi)->(xe,ye){ int i,j,k,flag,find;int amap[MAX][MAX]; for(i=0;i<xe;i++) { for(j=0;j<ye;j++) { scanf("%d",&amap[i][j]); } }for(i=0;i<xe;i++) { for(j=0;j<ye;j++) { printf("%d ",amap[i][j]); }printf("\n"); } StType st;//定义栈st st.top=-1;//初始化栈顶指针 st.top++;//初始方块进栈 st.data[st.top].i=xi; st.data[st.top].j=yi; st.data[st.top].flag=-1; amap[xi][yi]=-1; while(st.top>-1)//栈不为空时循环 { i=st.data[st.top].i; j=st.data[st.top].j; flag=st.data[st.top].flag;//取栈顶方块 if(i==xe-2&&j==ye-2)//找到出口，输出路径 { printf("走出的路径如下：\n"); for(k=0; k<=st.top; k++) { printf("\t<%d,%d>",st.data[k].i,st.data[k].j); printf("\n"); } printf("\n"); return 1; } find=0; while(flag<4&&find==0)//站下一个可走方块 { flag++; switch(flag) { case 0://向上走 i=st.data[st.top].i-1; j=st.data[st.top].j; break; case 1://向右走 i=st.data[st.top].i; j=st.data[st.top].j+1; break; case 2://向下走 i=st.data[st.top].i+1; j=st.data[st.top].j; break; case 3://向左走 i=st.data[st.top].i; j=st.data[st.top].j-1; break; } if(amap[i][j]==0) find=1;//找下一个可走相邻方块 } if(find==1)//找到了下一个可走方块 { st.data[st.top].flag=flag;//修改原栈顶元素的di值 st.top++;//下一个可走方块进栈 st.data[st.top].i=i; st.data[st.top].j=j; st.data[st.top].flag=-1; amap[i][j]=-1;//避免重复走到该方块 } else//没有路径可走则退栈 { amap[st.data[st.top].i][st.data[st.top].j]=0;//让该位置变为其他路径可走方块 st.top--;//将该方块退栈 } } return 0;}int main(){ int n,m;//n为列数，m为行数 scanf("%d %d",&n,&m); if(!mgpath(1,1,m,n)) printf("无解"); return 0;}/*实例10 101 1 1 1 1 1 1 1 1 11 0 0 1 0 0 0 1 0 11 0 0 1 0 0 0 1 0 11 0 0 0 0 1 1 0 0 11 0 1 1 1 0 0 0 0 11 0 0 0 1 0 0 0 0 11 0 1 0 0 0 1 0 0 11 0 1 1 1 0 1 1 0 11 1 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 16 61 1 1 1 1 11 0 0 0 1 11 0 0 1 1 11 1 0 1 0 11 1 1 1 0 11 1 1 1 1 1*/四. 树
【1】树转换成二叉树
#include<iostream>#include <string>using namespace std;struct Node // 以表的形式存储的树结点{ char data; int parent; int lchild; int rchild;};struct TreeNode // 以二叉链表存储的树结点{ char data; TreeNode *l; TreeNode *r;};// 创建树的表并转化为二叉树int creattable(Node table[]){ int n, k, i, j; cout << "输入结点个数(<20): "; cin >> n; if (n > 0) { cout << "输入结点信息和双亲编号(第一个请输入根结点信息如a -1 ):" << endl; for (i = 0; i < n; i++) { cin >> table[i].data >> table[i].parent; table[i].lchild = table[i].rchild = 0; } for (i = 0; i < n; i++) { for (j = 1; j < n; j++) { if (table[j].parent == i) { if (table[i].lchild == 0) { table[i].lchild = j; k = j; } else { table[k].rchild = j; k = j; } } } } for (i = 0; i < n; i++) { cout << table[i].data << table[i].parent << table[i].lchild << table[i].rchild << endl; } } return n;}// 将表转化为二叉链表void Build(TreeNode *¤t, Node node[], int pos, int n){ if (n > 0) { if (current == 0) { current = new TreeNode; current->l = current->r = 0; } current->data = node[pos].data; if (node[pos].lchild) Build(current->l, node, node[pos].lchild, n); if (node[pos].rchild) Build(current->r, node, node[pos].rchild, n); }}// 访问结点void Visit(TreeNode *current){ cout<<current->data<<" ";}// 按先序遍历void Preorder(TreeNode *root){ TreeNode *current = root; if (current != 0) { Visit(current); Preorder(current->l); Preorder(current->r); }}int main(){ Node node[20]; int n = creattable(node); TreeNode *root = 0; Build(root, node, 0, n); if (root) { cout << "先序遍历："; Preorder(root); cout << endl; } else { cout << "空树！" << endl; } return 0;}【2】二叉树的创造
#include <iostream>#include <stdio.h>#include<stdlib.h>#include <cstring>#include <bits/stdc++.h>#define MAX 100using namespace std;typedef char Elem_Type;typedef struct BiTree{ Elem_Type data; struct BiTree *Lchild; struct BiTree *Rchild;}BiTree,*Tree;//查找元素，找到中序遍历中的各个子树的根int search_num(Elem_Type num,Elem_Type *centre,int lenth){ for(int i=0;i<lenth;i++) { if(centre[i]==num)//如果中序中的第i个和先序中的num相同，则返回序号i { return i; } }}BiTree *Creat_Tree(Elem_Type *preorder,Elem_Type *centre,int lenth){ if(lenth<=0)//如果中序序列长度为0，则说明没有节点 return NULL; BiTree *t=new BiTree; t->data=*preorder; int n; n=search_num(*preorder,centre,lenth); t->Lchild=Creat_Tree(preorder+1,centre,n); t->Rchild=Creat_Tree(preorder+n+1,centre+n+1,lenth-n-1); return t;}void preorder_Tree(BiTree *t)//前序{ if(t!=NULL) { cout<<t->data; preorder_Tree(t->Lchild); preorder_Tree(t->Rchild); }}void mid_Tree(BiTree *t)//中序{ if(t!=NULL) { mid_Tree(t->Lchild); cout<<t->data; mid_Tree(t->Rchild); }}void last_Tree(BiTree *root)//后序{ if( root != NULL) { last_Tree(root->Lchild); last_Tree(root->Rchild); cout<<root->data; }}void leveltree(BiTree *t){ Tree s[100],p; int front1,rear; front1=rear=0; p=t; if(t!=NULL) { rear++; s[rear]=p; while(front1!=rear) { front1++; p=s[front1]; cout<<p->data; if(p->Lchild) { rear++; s[rear]=p->Lchild; } if(p->Rchild) { rear++; s[rear]=p->Rchild; } } }}int main(){ Elem_Type *preorder = new Elem_Type [MAX];//前序 Elem_Type *center = new Elem_Type [MAX];//中序 cin>>preorder;cin>>center; int m; int kind; m=strlen(center); BiTree *root= Creat_Tree(preorder,center,m); cout<<"---------------2019224278张泽晨---------------"<<"\n"; cout<<"--------------欢迎进入二叉树的创建-------------"<<"\n"; cout<<"————————————如果需要前序遍历，请输入1————————"<<"\n"; cout<<"————————————如果需要中序遍历，请输入2————————"<<"\n"; cout<<"————————————如果需要后序遍历，请输入3————————"<<"\n"; cout<<"————————————如果需要层次遍历，请输入4————————"<<"\n"; cout<<"请输入你需要的功能："; cin>>kind; if(kind==1)preorder_Tree(root); else if(kind==2) mid_Tree(root); else if(kind==3) last_Tree(root); else if(kind==4) leveltree(root); return 0;}五. 二叉排序树与文件
#include <iostream>#include <stdio.h>#include<stdlib.h>#include <cstring>#include <bits/stdc++.h>using namespace std;int sum;//定义记录学生的类型struct student{ char id[20];//学号 int grade;};//定义二叉排序树节点值的类型为学生记录类型typedef struct student Elem_type;//定义二叉排序树的节点类型typedef struct Lnode{ Elem_type data; struct Lnode *Lchild; struct Lnode *Rchild;}BNode,*BiTree;void menu()//菜单函数{ printf("\n1.从键盘输入一组学生记录建立二叉排序树并存盘\n"); printf("2.中序遍历二叉排序树\n"); printf("3.求二叉排序树深度\n"); printf("4.求二叉排序树的所有节点数和叶子节点数\n"); printf("5.向二叉排序树插入一条学生记录\n"); printf("6.从二叉排序树中删除一条学生记录\n"); printf("7.从二叉排序树中查询一条学生记录\n"); printf("8.以广义表的形式输出二叉排序树\n"); printf("9.退出系统\n");}/*在根指针T所指的二叉排序树中递归地查找某关键字为key的数据元素，如果查找成功，则指针p是该数据元素结点并返回1，否则p指向查找路径上访问的最后一个结点并返回0,指针tr指向T的双亲，初值为NULL。*/int search_Tree(BiTree T,Elem_type key,BiTree tr,BiTree &p){ if(!T) //如果根指针为空，即查找失败，p置空，返回0 { p=tr; return 0; } else if(strcmp(key.id,T->data.id)==0&&key.grade==T->data.grade) //如果根指针所指结点的值就是要查找的值，p就等于T，返回1 { p=T;//指针p记录这一节点。 return 1; } else if(key.grade<T->data.grade) //如果要查的值比根节点小，就到T的左子树去找 return search_Tree(T->Lchild,key,T,p); else return search_Tree(T->Rchild,key,T,p); //如果要查的值比根节点大，就到T的左子树去找}/*当二叉排序树T中不存在关键字e时，插入e并返回1，否则返回0*/int Insert_BiTree(BiTree &T,Elem_type e){ BiTree p,s; //p为查找关键字e路径上最后一个结点的指针，或者是指向关键字e的指针 //s为插入新结点所需要开辟的空间首地址 if(!search_Tree(T,e,NULL,p)) //如果查找失败，说明要进行插入操作 { s=(BiTree)malloc(sizeof(BNode)); s->data.grade=e.grade; strcpy(s->data.id,e.id); s->Lchild=s->Rchild=NULL; //s肯定是没有孩子的 if(!p) //如果p为空，说明T就是一颗空树，直接让s当根就好了 T=s; else if(e.grade<p->data.grade) //如果e比p->data小，说明要插到p的左子树上 p->Lchild=s; else if(e.grade>p->data.grade) //如果e比p->data大，说明要插到p的右子树上 p->Rchild=s; return 1; } else //说明查找成功！那么就没有插入的必要了，直接返回0即可 return 0;}void Mid_Find(BiTree T){ if(T) { Mid_Find(T->Lchild); printf("学号：%s 成绩：%d\n",T->data.id,T->data.grade); Mid_Find(T->Rchild); }}int Depth_Tree(BiTree T){ int depth_sum,HL,HR; if(!T) depth_sum=0; else { HL=Depth_Tree(T->Lchild); HR=Depth_Tree(T->Rchild); depth_sum=1+(HL>HR?HL:HR); } return depth_sum;}void add_nodes(BiTree T,int &s1){ if(T) { s1++; add_nodes(T->Lchild,s1); add_nodes(T->Rchild,s1); }}void add_leaves(BiTree T,int &s2){ if(T) { if(T->Lchild==NULL&&T->Rchild==NULL) s2++; add_leaves(T->Lchild,s2); add_leaves(T->Rchild,s2); }}BiTree search_id(BiTree T,char F_id[]) //通过学号找到结点并返回{ BiTree l,r; if(!T) return NULL; if(strcmp(T->data.id,F_id)==0) return T; else { l=search_id(T->Lchild,F_id); r=search_id(T->Rchild,F_id); return l?l:(r?r:NULL); }}int Delete(BiTree &p){ BiTree q,s; if(!p->Rchild)//如果右子树为空 { q=p;//将q指向p p=p->Lchild;//p指向自己的左子树 free(q);//删除q } else if(!p->Lchild)//右子树不是空，但是左子树是空 { q=p; p=p->Rchild;//用右子树代替自己 free(q); } else//左右子树都不空 { q=p; s=p->Lchild; while(s->Rchild)//找到p节点的前驱，即最后一个小于p的 { q=s;//q是s的双亲节点 s=s->Rchild; } p->data=s->data;//s代替p if(q!=p) q->Rchild=s->Lchild;// else q->Lchild=s->Lchild; free(s); } return 1;}int Delete_BiTree(BiTree &T,Elem_type key){ if(!T) return 0; else { if(key.grade==T->data.grade&&strcmp(key.id,T->data.id)==0) return Delete(T); else if(key.grade<T->data.grade) return Delete_BiTree(T->Lchild,key); else return Delete_BiTree(T->Rchild,key); }}void print_BiTree( BNode *T){ /*广义表形式输出二叉树*/ if(T != NULL) /* 树为空时结束递归，否则执行如下操作 */ { cout<<T->data.id<<" "<<T->data.grade; /* 输出根结点的值 */ if(T->Lchild != NULL || T->Rchild!= NULL) { print_BiTree(T->Lchild); if(T->Rchild != NULL) { printf(","); } print_BiTree(T->Rchild); printf("\n"); } }}int main(){ int n,i,k,m,grade[10],T_depth,s1,s2; Elem_type stu[20],st; char str[20],Find_id[20],num[20][20]; BiTree T=NULL,p; LL1:menu(); printf("\n请输入你的选择：\n"); scanf("%d",&m); switch(m) { case 1: { printf("请输入学生的个数：\n"); scanf("%d",&n); sum=n; printf("请输入%d个学生的学号和成绩，中间用空格隔开：\n",n); ofstream fout("bst.txt");//自动创建一个文件 memset(num,0,sizeof(num));//将num初始化，清0 for(i=0;i<sum;i++) { scanf("%s%d",stu[i].id,&stu[i].grade); fout<<stu[i].id<<" "<<stu[i].grade<<endl;//向文件中写入键盘输入的数据 strcpy(num[i],stu[i].id);//num[i]中复制所输入的学号 grade[i]=stu[i].grade; Insert_BiTree(T,stu[i]); } goto LL1; break; } case 2: { printf("二叉排序树的中序遍历为：\n"); Mid_Find(T); goto LL1; break; } case 3: { T_depth=Depth_Tree(T); if(T_depth) printf("二叉排序树的深度为：%d\n",T_depth); else printf("二叉排序树为空！\n"); goto LL1; break; } case 4: { s1=s2=0; add_nodes(T,s1); add_leaves(T,s2); printf("二叉排序树中所有结点个数为：%d\n",s1); printf("二叉排序树中所有叶子结点个数为：%d\n",s2); goto LL1; break; } case 5: { printf("请输入新增学生的个数：\n"); scanf("%d",&n); sum+=n; printf("请输入%d个学生的学号和成绩，中间用空格隔开：\n",n); for(i=0;i<n;i++) { scanf("%s%d",stu[i].id,&stu[i].grade); Insert_BiTree(T,stu[i]); } printf("二叉排序树的中序遍历为：\n"); Mid_Find(T); goto LL1; break; } case 6: { sum--; printf("请输入你想删除的那个人的学号和成绩：\n"); scanf("%s%d",st.id,&st.grade); Delete_BiTree(T,st); printf("二叉排序树的中序遍历为：\n"); Mid_Find(T); goto LL1; break; } case 7: { printf("请输入你想查找的学号\n"); scanf("%s",Find_id); p=search_id(T,Find_id); if(!p) printf("error!\n"); printf("你查找的这个人的信息为：\n"); printf("学号：%s\n",p->data.id); printf("分数：%d\n",p->data.grade); goto LL1; break; } case 8: { print_BiTree(T); goto LL1; break; } case 9: { printf("Good bye\n"); exit(0); } default: { printf("你的输入有误，请重新输入！\n"); goto LL1; break; } }}#include <iostream>#include <stack>using namespace std; #define maxnum 20 struct node{ //边表节点的定义 int vex; node* next; //指向下一个边表节点};struct vernode{ char vex ; //存放顶点信息 node* first; //指向第一个边表节点 int indegree;};struct graph{ vernode v[maxnum]; int vnums,enums;}; //创建有向图的邻接表void creategraph(graph &g, int n , int e){ int i , j , k; g.vnums = n; g.enums = e; for(i = 1 ; i <= n ; i++) { cin >>g.v[i].vex; g.v[i].first = NULL; //初始化为空 } for( k = 1 ; k <= e; k++) { node *p ; cin >> i >> j; p = new node(); p->vex = j; p->next = g.v[i].first; g.v[i].first = p; //头插法 }} void toposort(graph &g){ std::stack<int> s; node *p; int counts = 0; int i , j ; for( i = 1 ; i <= g.vnums ; i++) g.v[i].indegree = 0 ; //初始化入度为0 for(i = 1 ; i <= g.vnums ; i++) { //计算各个顶点的入度 p = g.v[i].first; while(p) { g.v[p->vex].indegree++; //计算入度 p = p->next; } } for(i = 1 ; i <= g.vnums ; i++) if(g.v[i].indegree == 0) s.push(i); //将度为0 的顶点入栈，这里进栈的是入度为0的顶点在数组的位置 while(!s.empty()) { j = s.top(); s.pop(); //出栈 cout << g.v[j].vex << " "; //将栈顶的元素出栈且输出 counts++; p = g.v[ j ].first; //让p指向入度为0 的第一个节点 while(p) { g.v[p->vex].indegree--; if(g.v[p->vex].indegree == 0 ) s.push(p->vex); p = p->next; } } if( counts < g.vnums) cout << "图中有环" << endl;} int main(){ graph g; creategraph(g,6,8); toposort(g); return 0;}发表评论
最新留言
不错！
[***.144.177.141]2025年04月14日 02时20分03秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
c++中istringstream及ostringstream超详细说明
2021-05-08
c++中ifstream及ofstream超详细说明
2021-05-08
c++中endl操作符以及它的兄弟们
2021-05-08
c++中explicit和mutable关键字探究
2021-05-08
c语言结构体字节对齐详解
2021-05-08
linux c/c++面试知识点整理(八)
2021-05-08
linux网络编程系列(十二)--滑动窗口、拥塞控制、断线重连机制
2021-05-08
c++11&14-编译
2021-05-08
Deep residual learning for image recognition
2021-05-08
IO控制方式
2021-05-08
IO控制器
2021-05-08
LeetCode122.买卖股票的最佳时机2Golang版
2021-05-08
Java 知识点总结篇（2）
2021-05-08
Python 知识点总结篇（2）
2021-05-08
Python 知识点总结篇（3）
2021-05-08
Numpy 如何操作数组
2021-05-08
爬取网易科技滚动新闻
2021-05-08
vuex modules
2021-05-08
Java笔记：单链表
2021-05-08
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 457293348 位访客