《数据结构课程设计 .doc》由会员分享，可在线阅读，更多相关《数据结构课程设计 .doc（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告 问题名称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); InitdataSta
2、ck(&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 : PopchStack(&OPTR,&theta); PopdataStack(&OPND,&b); PopdataStack(&OPND
3、,&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;
4、struct LNode *next;LNode, *LinkList;【主要算法】void creatcircle(LinkList *L) int n,i; LNode *p,*r; scanf(%d,&n); for(i=1;inum=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-ne
5、xt!=pre) j=1; while(jnext; 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 indegr
6、ee;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;ive
7、rtexnum;i+) scanf(%c,&(G-verticesi.data); G-verticesi.firstedge=NULL;G-verticesi.indegree=0; for(k=1;karcnum;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,cou
8、nt=0; Arcnode *p; Initstack(&S); for(;ivertexnum;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(countvertexnum)
9、 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;【
10、主要算法】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;ivexsi.data); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-arcsij.w=MAX; for(k=1;karcnum;k+) scanf(%d,%d,%d,&i,&j,&weight); G-arcsij.w=weight; int MinE
11、dge(int lowcost,int m) int i, t; for(i=0,t=0;im;i+) if(lowcosti+1lowcosti) t=i+1; return t; void prim(Mgraph *G) int lowcost6;char Adjvex6;int weight; int i,j,k; for(i=0;ivexnum;i+) lowcosti=G-arcs0i.w; Adjvexi=G-vexsi.data; for(i=1;ivexnum;i+) k=MinEdge(lowcost,G-vexnum); printf(k=%d,adjvexk=%d,low
12、costk=%d,k,Adjvexk,lowcostk); lowcostk=MAX; for(j=1;jvexnum;j+) if(G-arcskj.warcskj.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;BookR
13、ecType;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;
14、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;ty
15、pedef 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 fen
16、lei 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.le
17、n; while(j=1) if(df.BookDasei.bnobif.BnoIdxj.bno) k=j+1;break; j-; if(bif.len0) 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; strc
18、py(sm,df-BookDbasei-bname); j=1;k=0; while(jBookDbasei.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(BookDbas
19、eFile *df,LHFile2 lhf2) int i,j,k,m; char zz9; i=df-len; strcpy(zz,df.BookDbasei.author); j=1;k=0; while(jBookDbasei.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.LHF
20、rec2m.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(jBookDbasei.prenext=lhf3.LHFrec3k.lhead; lhf3.LHFrec3k.lhead=i; lhf3.LHFrec3k.RecNum+; else m=+lhf3.len3; df-BookDbasei.prenext=0;
21、 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(keybif.BnoIdxmid.bno) high=mid-1; el
22、se low=mid+1; return 0;int BnameFind(LHFile1 lhf1,char key) int i,k=0; for(i=1;ilhf1.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.lhea
23、d;break; int BnameFind(LhFile3 lhf3,char key) int i,k=0; for(i=1;i=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(shuru
24、shuhao:);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; c
25、ase 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.Book
26、Dbasei.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;ilen;i+) if(dzh=rf-ReadReci.rno) k=i;break; if(k=0)
27、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-
28、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;ilen;i+) if(dzh=rf
29、-ReadReci.rno) k=i;break; if(k=0)printf(feifaduzhe!n);return; for(i=1;ilen;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(huanshuchenggo
30、ng!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; retur
31、n 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;iL=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(Bid
32、xRecType),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); f
33、p=fopen(read,wb); for(i=1;i=rf.ReadReci,sizeof(RRecType),1,fp); fclose(fp); fp=fopen(bbff,wb); for(i=1;iBookDbasei,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);
34、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);