数据结构课程设计 .doc

数据结构课程设计报告 问题名称1.算术表达式求值【问题描述】由键盘输入一表达式字符串，该表达式由数字、+、-、*、/、 (、)组成，输出这个表达式的值【存储结构】typedef struct char base50; int top;SqchStack;typedef struct int base100; int top;SqdataStack;【主要算法】int EvaluateExpression() SqchStack OPTR; SqdataStack OPND; char c,x,theta; int t,s,a,b; InitchStack(&OPTR); InitdataStack(&OPND); PushchStack(&OPTR,'#'); c=getchar(); while(c!='#'|GetTopchStack(&OPTR)!='#') if(!In(c,op) t=c-'0's=t;c=getchar();while(!In(c,op) t=c-'0' s=s*10+t; c=getchar();PushdataStack(&OPND,s); switch(Precede(GetTopchStack(&OPTR),c) case '<':PushchStack(&OPTR,c); c=getchar(); break; case '=':PopchStack(&OPTR,&x); c=getchar();break; case '>': PopchStack(&OPTR,&theta); PopdataStack(&OPND,&b); PopdataStack(&OPND,&a); PushdataStack(&OPND,Operate(a,theta,b); break; return GetTopdataStack(&OPND);【测试和结果分析】2. 约瑟夫环问题【问题描述】编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从它在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【存储结构】typedef struct LNode int num,code; struct LNode *next;LNode, *LinkList;【主要算法】void creatcircle(LinkList *L) int n,i; LNode *p,*r; scanf("%d",&n); for(i=1;i<=n;i+) p=(LinkList)malloc(sizeof(LNode); p->num=i; scanf("%d",&p->code); if(*L=NULL) *L=p;r=p; else r->next=p;r=p; r->next=*L;*L=r;void Josephcircle(LinkList *L) LNode *pre,*p; int j,m; scanf("%d",&m); pre=*L; p=pre->next; while(pre->next!=pre) j=1; while(j<m) pre=p; p=p->next; j+; pre->next=p->next; printf("%dn",p->num); m=p->code; free(p); p=pre->next; printf("%dn",p->num); free(pre);【测试和结果分析】6. 拓扑排序【问题描述】自己设计一个有向无环图，求其拓扑序列。【存储结构】typedef struct node int adjvex; struct node *next;Arcnode;typedef struct vnode vertextype data; Arcnode *firstedge; int indegree;vnode,adjlistMAX_VERTEX_NUM;typedef struct adjlist vertices; int vertexnum,arcnum;Algraph;typedef struct selemtype *base; selemtype *top; int stacksize;sqstack;【主要算法】status createDG(Algraph *G) int i,k,j; Arcnode *p; printf("vnum,arcnumn"); scanf("%d",&(G->vertexnum); scanf("%d",&(G->arcnum); for(i=0;i<G->vertexnum;i+) scanf("%c",&(G->verticesi.data); G->verticesi.firstedge=NULL;G->verticesi.indegree=0; for(k=1;k<=G->arcnum;k+) scanf("%d,%d",&i,&j); p=(Arcnode*)malloc(sizeof(Arcnode); p->adjvex=j; p->next=G->verticesi.firstedge; G->verticesi.firstedge=p; return 0;void topsort(Algraph *G) sqstack S;int j,k; int i=0,count=0; Arcnode *p; Initstack(&S); for(;i<G->vertexnum;i+) if(G->verticesi.indegree=0) push(&S,i); while(!emptystack(&S) pop(&S,&j); printf("%c ",G->verticesj.data); count+; p=G->verticesj.firstedge; while(p) k=p->adjvex; G->verticesk.indegree-; if(G->verticesk.indegree=0) push(&S,k); p=p->next; if(count<G->vertexnum) printf("there is a circlen");【测试和结果分析】7. 最小生成树问题【问题描述】在n个城市之间建设通讯网络，只需保证连通即可，用prim算法求最经济的架设方法。【存储结构】typedef struct Arccell int w;Arccell,AdjmatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct char data; vertextype;typedef struct vertextype vexsMAX_VERTEX_NUM; Adjmatrix arcs; int vexnum,arcnum;Mgraph;【主要算法】void createUDN(Mgraph *G) int vexnum,arcnum,i,j,k,weight7; printf("please input vexnum and arcnum:n"); scanf("%d",&vexnum); scanf("%d",&arcnum); for(i=0;i<vexnum;i+) scanf("%c",&(G->vexsi.data); for(i=0;i<G->vexnum;i+) for(j=0;j<G->vexnum;j+) G->arcsij.w=MAX; for(k=1;k<=G->arcnum;k+) scanf("%d,%d,%d",&i,&j,&weight); G->arcsij.w=weight; int MinEdge(int lowcost,int m) int i, t; for(i=0,t=0;i<m;i+) if(lowcosti+1<lowcosti) t=i+1; return t; void prim(Mgraph *G) int lowcost6;char Adjvex6;int weight; int i,j,k; for(i=0;i<G->vexnum;i+) lowcosti=G->arcs0i.w; Adjvexi=G->vexsi.data; for(i=1;i<=G->vexnum;i+) k=MinEdge(lowcost,G->vexnum); printf("k=%d,adjvexk=%d,lowcostk=%d",k,Adjvexk,lowcostk); lowcostk=MAX; for(j=1;j<G->vexnum;j+) if(G->arcskj.w<lowcostj) lowcostj=G->arcskj.w; Adjvexj=k; 【测试和结果分析】8. 图书信息管理系统【问题描述】开发一个简单的图书信息管理系统。【存储结构】typedef struct int bno; char bname21; int namenext; char author9; int authnext; char press11; int prenext; char sortno4; int storenum; int borrownum;BookRecType;typedef struct BookRecType BookDbaseBookSize; int len;BookDbaseFile;typedef struct int bno; int RecNo;BidxRecType;typedef struct BidRecType BnoIdxBookSize; int len;BnoIdxFile;typedef struct char bname21; int lhead; int RecNum;BNRecType;typedef struct BNRecType LHFrec1BLHnum; int len1;LHFile1;typedef struct char author9; int lhead; int RecNum;BARecType;typedef struct BARecType LHFrec2BLHnum; int len2;LHFile2;typedef struct char press11; int lhead; int RecNum;BPRecType;typedef struct BPRecType LHFrec3BLHnum; int len3;LHFile3;typedef struct int rno; char name8; int bn1; int bn2;RRecType;typedef struct RRecType ReadRecRRnum; int len;ReadFile;typedef struct int rno; int bno; char data19; char data29;BbookRecType;typedef struct BbookRecType BbookBookSize; int len;BbookFile;【主要算法】BookDbaseFile AppeDBaseRec(BookDbaseFile df) int i; i=+df.len; printf("shuhao shuming zhuzheming chubanshe fenlei cangshuliangn"); scanf("%d%s",&df.BookDbasei.bno,df.BookDbasei.bname); scanf("%s%s",df.BookDbasei.author,df.BookDbasei.press); scanf("%s %d",df.BookDbasei.sortno,&df.BookDbasei.storenum); df.BookDbasei.borrownum=0; return df;BnoIdxFile ChangeBnoIdxFile df,BnoIdxFile bif) int i,j,k=1; i=df.len; j=bif.len; while(j>=1) if(df.BookDasei.bno>bif.BnoIdxj.bno) k=j+1;break; j-; if(bif.len>0) for(j=bif.len;j>=k;j-) bif.BnoIdxj+1=bif.BnoIdxj; bif.BnoIdxk.bno=df.BookDbasei.bno; bif.BnoIdxk.RecNo=i; bif.len+; return bif;LHFile ChangeLinkHeadF1(BookDbaseFile *df,LHFile1 lhf1) int i,j,k,m; char sm21; i=df->len; strcpy(sm,df->BookDbasei->bname); j=1;k=0; while(j<=lhf1.len1) if(strcmp(sm,lhf1.LHFrec1j.bname)=0) k=j;break; j+; if(k!=0) df->BookDbasei.namenext=lhf1.LHFrec1k.lhead; lhf1.LHFrec1k.lhead=i; lhf1.KHFrec1k.RecNum+; else m=+lhf1.len1; df->BookDbasei.namenext=0; lhf1.LHFrec1m.lhead=i; lhf1.LHFrec1m.RecNum=1; strcpy(lhf1.LHFrec1m.bname,sm); return lhf1;LhFile2 ChangeLinkHeadF2(BookDbaseFile *df,LHFile2 lhf2) int i,j,k,m; char zz9; i=df->len; strcpy(zz,df.BookDbasei.author); j=1;k=0; while(j<=lhf2.len2) if(strcmp(zz,lhf2.LHFrec2j.author)=0 k=j;break; j+; if(k!=0) df->BookDbasei.authnext=lhf2.LHFrec2k.lhead; lhf2.LHFrec2k.lhead=i; lhf2.LHFrec2k.RecNum+; else m=+lhf2.len2; df->BookDbasei.authnext=0; lhf2.LHFrec2m.lhead=i; lhf2.LHFrec2m.RecNum=1; strcpy(lhf2.LHFrec2m.author,zz); return lhf2;LHFile3 ChangeLinkHeadF3(BookDbaseFile *df,LHFile3 lhf3) int i,j,k,m; char cbs11; i=df->len; strcpy(cbs,df.BookDbasei.press); j=1;k=0; while(j<=lhf3.len3) if(strcmp(cbs,lhf3.LHFrec3j.press)=0 k=j;break; j+; if(k!=0) df->BookDbasei.prenext=lhf3.LHFrec3k.lhead; lhf3.LHFrec3k.lhead=i; lhf3.LHFrec3k.RecNum+; else m=+lhf3.len3; df->BookDbasei.prenext=0; lhf3.LHFrec3m.lhead; lhf3.LHFrec3m.RecNum=1; strcpy(lhf3.LHFrec3m.press,cbs); return lhf3;int BinSearch(BnoIdxFile bif,int key) int low,high,mid; low=1; high=bif.len; while(low<=high) mid=(low+high)/2; if(key=bif.BnoIdxmid.bno) return bif.BnoIdxmid.RecNo; else if(key<bif.BnoIdxmid.bno) high=mid-1; else low=mid+1; return 0;int BnameFind(LHFile1 lhf1,char key) int i,k=0; for(i=1;i<lhf1.len1;i+) if(strcmp(key,lhf1.LHFreci.bname)=0) k=lhf1.LHFrec1i.lhead;break; return k;int BauthFind(LHFile2 lhf2,char key) int i,k=0; for(i=1;i<=lhf2.len2;i+) if(strcmp(key,lhf2.LHFrec2i.author)=0) k=lhf2.LHFrec2i.lhead;break; int BnameFind(LhFile3 lhf3,char key) int i,k=0; for(i=1;i<=lhf3.len3;i+) if(strcmp(key,lhf3.LHFrec3i.press)=0) k=lhf3.LHFrec3i.lhead;break; return k;void ShowRec(BookDbaseFile df,int i) printf("shuhao shuming zuozheming chubanshe fenleihao kejieshun"); printf("=n"); printf("%d%12s",df.BookDbasei.bno,df.BookDbasei.bname); printf("%8s%12s",df.BookDbasei.author,df.BookDbasei.press); printf("%6s",df.BookDbasei.sortno); printf("%4dn",df.BookDbase.i,storenum-df.BiikDbasei.borrownum); printf("=n");void SearchBook(BookDbaseFile df,BnoIdxFile bif,LHFile1 f1,LHFile2 f2,LHFile3 f3) char sm21,zz9,cbs11; int i,k,choose=1; int sh; while(choose>=1&&choose<=5) printf("tushuchaxunzixitongn"); printf("-n"); printf("1.shuhao 2.shumingn"); printf("3.zuozhe 4.chubanshen"); printf("5.tuichuchaxunn"); printf("-n"); printf("qingyonghuxuanze:n"); scanf("%d",&choose); switch(choose) case 1: printf("shurushuhao:");scanf("%d",&sh); k=BinSearch(bif,sn); if(k=0) printf("meiyouyaochazhaodetushu,shifoushuruyoucuon"); break; ShowRec(df,k); break; case 2: printf("shurushuming:n");scanf("%s",sm); k=BnameFind(f1,sm); if(k=0) printf("meiyou,shieuyoucuon"); break; for(i=k;i=df.BookDbasei.namenext) ShowRec(df,i); break; case 3: printf("shuruzuozheming:n);scanf("%s",zz); k=BaythFind(f2,zz); if(k=0) printf("meiyou,shuruyoucuon"); break; for(i=k;i;i=df.BookDbasei.authnext) ShowRec(df,i); break; case 4: printf("shuruchubanshen");scanf("%s",cbs); k=BnameFind(f3,cbs); if(k=0) printf("meiyou,shuruyoucuon"); break; for(i=k;i;i=df.BookDbasei.prenext) ShowRec(df,i); break; case 5:return; void BorrowBook(BookDbaseFile *bf,BnoIdxFile bif,BbookFile *bbf,ReadFile *rf) char jyrq9; int sh,dzh; int i,j,k=0; printff("input duzhehao shuhao jieshuriqin"); scanf("%d%d%s",&dzh,&sh,jyrq); for(i=1;i<=rf->len;i+) if(dzh=rf->ReadReci.rno) k=i;break; if(k=0)printf("feifeduzhe!n");return; if(rf->ReadReck.bn2>=rf->BookDbasej.storenum) printf("shuyiman!n");return; j=BinSearch(bif,sh); if(j=0)printf("feifashuhao!n");return; if(bf->BookDbasej.boorownum>=bf_>BookDbasej.storenum) printf("shuyijiechun");return; i=+bbf->len; bbf->Bbooki.rno=dzh; bbf->Bbooki.bno=sh; strcopy(bbf->Bbooki.date1,jyrq); rf->ReadReck.bn2+; bf->BookDbasej.borrownum+; printf("jieshuchenggong!n");void BackBook(BookDbaseFile *bf,BnoIdxFile bif,BbookFile *bbf,ReadFile *rf) char hsrq8; int sh,dzh; int i,j,k=0,m=0; printf("duzhehao shuhao huanshuriqin"); scanf("%d%d%s",&dzh,&sh,hsrq); for(i=1;i<=rf_>len;i+) if(dzh=rf->ReadReci.rno) k=i;break; if(k=0)printf("feifaduzhe!n");return; for(i=1;i<=bbf->len;i+) if(sh=bbf->Bbooki.bno) m=i;break; if(m=0)printf("feifashuhao!n");return; j=BinSearch(bif,sh); if(j=0)printf("feifashuhao!n");return; rf->ReadReck.bn2-; bf->BookDbasej.borrow-; strcpy(bbf->Bbookm.date2,hsrq); printf("huanshuchenggong!n");ReadFile ReaderManage(ReadFile rf) int i;char yn='y' i=+rf.len; while(yn='y'|yn='Y') printf("shuruduzhehao duzheming kejietushushun"); scanf("%d %s",&rf.ReadReci.rno,rf.ReadReci.name); scanf("%d",&&rf.ReadReci.bn1; rf.ReadReci.bn2=0; printf("jixushuruma?y/n:"); getchar(); scanf("%c",&yn);i+; rf.len=i-1; return rf;void writefile(BookDbaseFile bf,BnoIdxFile bif,LHFile1 f1,LHFile2 f2,LHFile3 f3,ReadFile rf,BbookFile bbf) FILE*fp;int i; fp=fopen("book","wb"); for(i=1;i<L=bf.len;i+) fwrite(&bf.BookDbasei,sizeof(BookRecType),1,fp); fclose(fp); fp=fopen("bidx","wb"); for(i=1;i<=bif.len;i+) fwrite(&bif.BnoIdxi,sizeof(BidxRecType),1,fp); fclose(fp); fp=fopen("nidx","wb"); for(i=1;i<=f1.len;i+) fwrite(&f1.LHFrec1i,sizeof(BNRecType),1,fp); fclose(fp); fp=fopen("aidx","wb"); for(i=1;i<=f2.len2;i+) fwrite(&f2.LHFrec2i,sizeof(BARecType),1,fp); fclose(fp); fp=fopen("pidx","wb"); for(i=1;i<=f3.len3i,sizeof(BPRecType),1,fp); fclose(fp); fp=fopen("read","wb"); for(i=1;i<=rf.ReadReci,sizeof(RRecType),1,fp); fclose(fp); fp=fopen("bbff","wb"); for(i=1;i<=bbf.len;i+) fwrite(&bbf.Bbooki,sizeof(BbookRecType),1,fp); fclose(fp);void readfile(BookDbaseFile *bf,BnoIdxFile *bif,LHFile1 *f1,LHFile2 *f2,LHFile3 *f3,ReadFile *rf,BbookFile *bbf) FILE *fp;int i; FP=fopen("book","rb"); i=1; while(!feof(fp) fread(&bf->BookDbasei,sizeof(BookRecTYpe),i,fp); i+;if(feof(fp)break; bf->len=i-2;fclose(fp); fp=fopen("bidx","rb"); i=1; while(!feof(fp) fread(&bif->BnoIdxi,sizeof(BidxRecType),1,fp); i+; bif->len=i-2;fclose(fp); fp=fopen("nidx","rb"); i=1; while(feof(fp) fread(&f1->LHFrec1i,sizeof(BNRecType)1,fp); i+; f1->len1=i-2;fclose(fp); fp=fopen("aidx","rb"); i=1; while(!feof(fp) fread(&f2->LHFrec2i,sizeof(BARecType),1,fp); i+; fp->len2=i-2; fclose(fp); fp=fopen("pidx","rb"); i=1; while(!feof(fp) fread(&f3->LHFrec3i,sizeof(BPRecType),1,fp); i+; f3->len3=i-2;fclose(fp);