《数据结构》课程设计指导书答案.doc

1运动会分数统计#include #include #include #includeusing namespace std; int n; /n个学校 int m; /m个男子项目 int w; /w个女子项目 struct pro /表示项目的结构体 string name; /项目名称 int snum6; /前5名学校的编号 p21; struct school /表示学校的结构体 int num; string name; /学校名称 int score; /学校总分 int male; /男子总分 int female; /女子总分 sch21; int integral5=;/前五名得分 void input() int i,j,y,x; printf(输入学校数目:); y=0; while(1) scanf(%d,&n); if(n=1&n=20)y=1; if(y)break; else printf(输入数据有误，请重新输入:); for(i=1;; schi.score=0; schi.female=0; schi.male=0; schi.num=i; printf(输入男子项目数和女子项目数:); y=0; while(1) scanf(%d%d,&m,&w); if(m=1&w=1)y=1; if(y)break; else printf(输入数据有误，请重新输入:); for(i=1;; printf(输入第%d个项目的前5名的学校编号:n,i); for(j=1;j=1&x=20)y=1; if(y)break; else printf(输入数据有误，请重新输入:); pi.snumj=x; schx.score+=integralj-1; if(i=m)schx.male+=integralj-1; else schx.female+=integralj-1; void print(int i) coutschi.numsetw(10)setw(8)schi.scoresetw(9) schi.malesetw(10)schi.femaleendl; void bianhao() /按编号排序 int i,j; school t; for(i=1;in;i+) for(j=i;jschj.num) printf(n按编号排列:n); printf(编号 学校名称 总分 男子总分 女子总分n); for(i=1;i=n;i+) print(i); void zongfen() /按学校总分排序 int i,j; school t; for(i=1;in;i+) for(j=i;j=n;j+) if(schi.scoreschj.score) printf(n按学校总分排列:n); printf(编号 学校名称 总分 男子总分 女子总分n); for(i=1;i=n;i+) print(i); ofstream fout;fout.open(运动会分数统计.txt); fout编号 学校名称 总分 男子总分 女子总分endl;for(i=1;i=n;i+) foutschi.numsetw(13)setw(8)schi.scoresetw(9) schi.malesetw(10)schi.femaleendl; fout.close(); void malezf() /按学校男总分排序 int i,j; school t; for(i=1;in;i+) for(j=i;j=n;j+) if(schi.maleschj.male) printf(n按学校男子总分排列:n); printf(编号 学校名称 总分 男子总分 女子总分n); for(i=1;i=n;i+) print(i); void femalezf() /按学校女总分排序 int i,j; school t; for(i=1;in;i+) for(j=i;j=n;j+) if(schi.femaleschj.female) printf(n按学校女子总分排列:n); printf(编号 学校名称 总分 男子总分 女子总分n); for(i=1;i=n;i+) print(i); cout=1&s=n)y=1; if(y)break; else printf(输入数据有误，请重新输入:); printf(该学校相关信息:n); printf(编号 学校名称 总分 男子总分 女子总分n); for(i=1;i=n;i+) if(schi.num=s) print(i); break; cout=1&s=n)y=1; if(y)break; else printf(输入数据有误，请重新输入:); 前5名学校编号及名称为:endl; printf(名次 编号 学校名称n); for(i=1;i=5;i+) cout i ps.snumisetw(12)sch ps.snumi .nameendl; coutendl; void solve() /菜单函数 int z; while(1) printf(n选择您需要的操作(选择序号):n); printf(1.按学校编号排序输出n); printf(2.按学校总分排序输出n); printf(3.按学校男总分排序输出n); printf(4.按学校女总分排序输出n); printf(5.查询某个学校成绩n); printf(6.查询某个项目成绩n); printf(7.结束nn); scanf(%d,&z); if(z=1)bianhao(); if(z=2)zongfen(); if(z=3)malezf(); if(z=4)femalezf(); if(z=5)cxsch(); if(z=6)cxxm(); if(z=7)break; int main() /主函数 input(); solve(); return 0; 2一元多项式计算（升幂建立，指数降序输出）#include#include#defineLENsizeof(structPolynomial)structPolynomialfloatcoef;longexpn;structPolynomial*next;intn=0,sum=0;intcmp(longa,longb)intflag;if(ab)flag=1;elseflag=0;returnflag;structPolynomial*creat(void)structPolynomial*head;structPolynomial*p1,*p2;p1=p2=(structPolynomial*)malloc(LEN);scanf(%f,%ld,&p1-coef,&p1-expn);head=NULL;while(p1-coef!=0)n+;if(n=1)head=p1;elsep2-next=p1;p2=p1;p1=(structPolynomial*)malloc(LEN);scanf(%f,%ld,&p1-coef,&p1-expn);p2-next=NULL;returnhead;structPolynomial*add(structPolynomial*ah,structPolynomial*bh)structPolynomial*pa1,*pa2,*pb1,*pb2;floatsumcoef;pa1=ah;pb1=bh;pa2=pa1-next;pb2=pb1-next;while(pa1&pb1)switch(cmp(pa2-expn,pb2-expn)case-1:pb2-next=pa2;pa2-next=pb2-next;pb2=pb2-next;pa2=pa1-next;break;case0:sumcoef=pa1-coef+pb1-coef;if(sumcoef!=0.0)pa1-coef=sumcoef;break;case1:pb1-next=pa2;pa2-next=pb2;pa2=pa1-next-next;pb2=pb2-next;break;if(pb2)pb1-next=pb2;free(bh);returnah;voiddisplay(structPolynomial*head)structPolynomial*p;printf(ThecombinatedPolynomialis:n);p=head;if(p!=NULL)doprintf(%f,x%ld,p-coef,p-expn);p=p-next;while(p!=NULL);voidmain()structPolynomial*pahead,*pbhead,*abhead;printf(InputlistPa:n);pahead=creat();sum=sum+n;printf(InputlistPb:n);pbhead=creat();sum=sum+n;abhead=add(pahead,pbhead);display(abhead);3. 迷宫求解NYNY求解迷宫输入迷宫行和列正确么输出迷宫路径提示出错结束重新输入输入迷宫数据结构设计本程序利用“栈”的形式完成，用非递归函数求出迷宫通路，把迷宫的通路压入栈，栈满足后进先出的原则，恰好满足迷宫求解的过程。主要功能逻辑过程和实现算法typedef int Status;typedef struct/迷宫中x行y列的位置int x;int y;PosType; int mg100100;/迷宫数组int zx5,zy5;/数据的方向typedef struct int ord; /通道块在路经上的序号PosType seat; /当前坐标位置int di; /往下一坐标的方向SElemType; /栈的无素类型typedef structSElemType *base; /栈基址,构造前销毁后为空SElemType *top; /定义栈底int stacksize; /定义栈的容量SqStack; /栈类型/构造一个空栈,把输入的数做进栈；Status InitStack(SqStack &s)s.base =(SElemType *)malloc(stack_init_size * sizeof(SElemType);if(!s.base) return overflow;s.top=s.base;s.stacksize=stack_init_size;return ok;4. 文章编辑#include stdio.hvoid main() char c; int english=0,number=0,space=0,others=0; /*定义字母 数字 空格及其他变量并给它们赋初值*/ printf(输出一串字符包含空格，数字，字母及其它:); while(c=getchar()!=n) /*用getchar函数输出一串字符*/ if (c=A&c=a&c=0&c=9) number+; else if (c= ) space+; else others+; printf(字母有%d个 数字有%d个 空格有%d个 其它有%d个,english,number,space,others);5. joseph环#include#includestruct CirNode/*定义每个结点的类型 */int data;/*每个人所拥有的密码*/ int num;/*每个人在圈中的位序*/ struct CirNode *next; ; int a30; /*人数要求30 */struct CirNode *CreateList(int n)/*生成n个结点的单向循环链表 */ struct CirNode *L,*p,*q; int i; int j=1; L=q=(struct CirNode*)malloc(sizeof(struct CirNode);/*建立一个不带头结点的单向循环链表 */if(!q) return ERROR; printf(shu ru mei ge ren de mi ma:n); q-num=j; printf(%d.data=,j); scanf(%d,&q-data); j+; q-next=L; for(i=1;inum=j; printf(%d.data=,j); scanf(%d,&p-data); j+; q-next=p; p-next=L; q=q-next; /*for*/return (L); /*Create*/struct CirNode *DeleteList(struct CirNode *L,int m,int n)/*报m的人出列*/ int i,j=0; int k=n; struct CirNode *p,*q,*pre; pre=p=L; do i=1; while(inext!=p) pre=pre-next; m=p-data;/*得到新的密码 */aj=p-num;/*得到出列人的序号 */q=p; pre-next=p-next; p=p-next; free(q); L=pre=p;/*让新的报1的人作为头结点 */k-;j+; /*if */else q=p-next; m=q-data; aj=q-num; p-next=q-next; p=q-next; free(q); L=pre=p; k-;j+; /*else*/while(k1); aj=p-num;/*最后一个出列人的序号 */printf(xian zai suo you ren chu lie.n); return (L); /*DeleteList*/int main() struct CirNode *L; int i,n,m; printf(=This is a Joseph problem=n); printf(qing shu ru ren shu,n=); scanf(%d,&n); if(n30|n1) printf(ERROR! Please input again,n=); scanf(%d,&n); /*if*/L=CreateList(n); printf(Please input the first code,m=); scanf(%d,&m); if(m1) printf(ERROR! Please input again,m=); scanf(%d,&m); /*if */DeleteList(L,m,n); printf(chu dui ren de shun xu31:n); for(i=0;in;i+) printf(%d ,ai); printf(n); return 0; 6. 建立二叉树，层序、先序遍历（用非递归的方法）#include #define M 1000 using namespace std; template struct Btnode /定义二叉链表结点类T d; /数据域Btnode *lchild; /左指针域Btnode *rchild; /右指针域; /二叉链表类template /类模板，T为虚拟类型class Binary_Tree private: Btnode *BT; /而叉链表根结点指针public: /成员函数 Binary_Tree()BT=NULL;return; /二叉链表初始化 void creat_Binary_Tree(T); /生成二叉链表 void pretrav_Binary_Tree(); /前序遍历二叉链表 void intrav_Binary_Tree(); /中序遍历二叉链表 void postrav_Binary_Tree(); /后序遍历二叉链表;/生成二叉链表template void Binary_Tree:creat_Binary_Tree(T end) Btnode *p; T x; cinx; if(x=end) return; p=new Btnode; p-d=x; p-lchild=NULL; p-rchild=NULL; BT=p; creat(p,1,end); creat(p,2,end); return;templatestatic creat(Btnode *p,int k,T end) Btnode *q; T x; cinx; if(x!=end) q=new Btnode; q-d=x; q-lchild=NULL; q-rchild=NULL; if(k=1) p-lchild=q; if(k=2) p-rchild=q; creat(q,1,end); creat(q,2,end); return 0;/前序遍历二叉链表templatevoid Binary_Tree:pretrav_Binary_Tree( ) Btnode *p; p=BT; pretrav(p); coutendl; return;templatestatic pretrav(Btnode *p) if(p!=NULL) coutdlchild); pretrav(p-rchild); return 0;/中序遍历二叉链表templatevoid Binary_Tree:intrav_Binary_Tree( ) Btnode *p; p=BT; intrav(p); coutendl; return;templatestatic intrav(Btnode *p) if(p!=NULL) intrav(p-lchild); coutdrchild); return 0;/后序遍历二叉链表templatevoid Binary_Tree:postrav_Binary_Tree( ) Btnode *p; p=BT; postrav(p); coutendl; return;templatestatic postrav(Btnode *p) if(p!=NULL) postrav(p-lchild); postrav(p-rchild); coutd ; return 0;int main( ) Binary_Treeb; cout输入各结点值(-1为结束符值):endl; b.creat_Binary_Tree(-1); cout前序序列:endl; b.pretrav_Binary_Tree( ); cout中序序列:endl; rav_Binary_Tree( ); cout后序序列:endl; b.postrav_Binary_Tree( ); return 0;7.#include #define N 52void main()int i,j;int cardN = 0;for (i = 2;i = N;i+) for (j = 2;j = N;j+) if (i % j = 0) if (cardi - 1) cardi - 1 = 0; else cardi - 1 = 1; printf(最后正面向上的扑克牌为:n);for (i = 0;i N;i+) if (cardi = 0) printf(第%d张,i + 1);printf(n);8.#include#includestring.h#includestdio.hconst int maxsize=100; /每种商品的最大上货量const int k=10; /商品种类#define elemtype chartypedef structint Month;int Day;int Year;DATE;typedef struct int num; /商品代号DATE date; Node;class seqstackpublic:Node stackmaxsize;int top;void inistack()top=0;void push(int x,int day,int month,int year)if(top=maxsize)cout货架已满endl;else top+;stacktop.num=x;stacktop.date.Da