数据结构课程设计报告2

1、数据结构课程设计报告学 号姓 名班 级计091指导教师安徽工业大学计算机学院2011年6月一学生成绩查询实验要求： 若按学号进行顺序查找，例如：输入99070103，则输出 56 。 按学号排序后对学号进行折半查找。 随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。设计思路： 顺序表建立学生信息，包括double学号，sting名字，int分数，然后进行学号顺序查找，折半查找。 建立二叉排序树，对二叉排序树进行学号查找，显示出相应的信息。2.代码#include#include#include#define maxsize 100typedef double key

2、type;typedef int datatype;typedef struct keytype key; datatype;typedef structchar dmaxsize;int leng;seqstring; typedef struct keytype key; seqstring name; int score; datatype1;typedef struct binstreenodedatatype elem;seqstring name;int score;struct binstreenode *lchild,*rchild;*binstree;typedef stru

3、ctdatatype1 r maxsize;int length;seqlist; int display(seqstring s) int i; s.leng=5; for(i=0;i5;i+) printf(%c,s.di); return 1; int seqsearch(seqlist s,keytype k) int i; for(i=0;is.length;i+) if(s.ri.key=k) printf(%.0ft,s.ri.key) ; display(); printf( %dn,s.ri.score); return (i); return (-1);

4、int binsearch(seqlist s,keytype k) int low,mid,high; low=0;high=s.length-1; while(lowk) high=mid-1; else low=mid+1; return (-1); binstree create_binstree(void) /*新建二叉结点*/ binstree t; t=( binstree)malloc(sizeof(struct binstreenode); t-lchild=t-rchild=null; return t; binstree binstreesearch(binstree t

5、,keytype k) /*判断结点是否存在*/if(t=null)return null;if(t-elem.key=k) return (t);if(t-elem.keyk) binstreesearch(t-lchild,k);binstreesearch(t-rchild,k);return null; void binstreeinsert(binstree *t,keytype k,seqstring name1,int score1) /*插入二叉排序结点*/ binstree r; if(*t=null) r=(binstree)malloc(sizeof(struct bin

6、streenode); r-elem.key = k; r-name=name1; r-score=score1; r-lchild= r-rchild= null; *t=r; return ; else if(kelem.key) binstreeinsert( &(*t)-lchild), k,name1,score1); else binstreeinsert( &(*t)-rchild), k,name1,score1); void search(binstree *bt,keytype k) /* 查找二叉排序结点*/ binstree p; p=*bt; while(p&p-el

7、em.key!=k) if(p-elem.keyk) p=p-lchild; else p=p-rchild; display(p-name); printf( score is %d,p-score); int bstreedelete(binstree *bt,keytype k) /* 删除二叉排序结点*/ binstree f,p,q,s; p=*bt; f=null; while(p&p-elem.key!=k) f=p; if(p-elem.keyk) p=p-lchild; else p=p-rchild; if(p=null)return (0); if(p-lchild=nu

8、ll) if(f=null) *bt=p-rchild; else if (f-lchild=p) f-lchild=p-lchild; else f-rchild=p-rchild; free(p); else q=p;s=p-lchild; while(s-rchild) q=s; s=s-rchild; if(q=p) q-lchild = s-lchild; else q-rchild = s-lchild; p-elem.key= s-elem.key; free(s); return (1); return 1; void inorder(binstree t) if(t) ino

9、rder(t-lchild); printf(%.0ft,t-elem.key) ; display(t-name); printf( %dn,t-score); /* printf(%.0f %c %dn,t-elem.key,t-name,t-score); */ inorder(t-rchild); main() int a=70,76,98,65,67,86,87,98,76,i,n=9; seqstring c=张华,1,李华,2,赵广,3,黄晓,4,王三,5,李四,6,陆逊,7,实践,8,胡斯; keytype b=99074001,99074002,99074003,990740

10、04,99074005,99074006,99074007,99074008,99074009; binstree t; seqlist s; s.length=0; printf(顺序建立成绩表:n); for(i=0;in;i+) s.ri.key=bi; =ci; s.ri.score=ai; s.length+; for(i=0;is.length;i+) printf(%.0ft,s.ri.key) ; display(); printf( %dn,s.ri.score); /* printf(%.0f %s %dn,s.ri.key,s.ri.n

11、ame,s.ri.score); */ printf(顺序查找:); seqsearch(s, b4); printf(折半查找:); binsearch( s,b5); t=create_binstree(); for(i=0;in;i+) if(binstreesearch(t,bi)=null) binstreeinsert( &t,bi,ci,ai); else continue ; printf(二叉树建立:n); inorder(t); printf(二叉树查找:); search(&t,b3); printf(n); printf(删除%.0f成绩：n,b4); bstreede

12、lete( &t, b4); inorder(t); getchar(); return 0; 3.功能设计seqsearch(seqlist s,keytype k) 顺序查找学生学号bstreedelete(binstree *bt,keytype k) /* 删除二叉排序结点*/binsearch(seqlist s,keytype k)二叉排序树查找学生学号create_binstree(void) /*新建二叉结点*/binstreesearch(binstree t,keytype k) /*判断结点是否存在*/binstreeinsert(binstree *t,keytype

13、k,seqstring name1,int score1) /*插入二叉排序结点*/search(binstree *bt,keytype k) /* 删除二叉排序结点*/bstreedelete(binstree *bt,keytype k) /* 删除二叉排序结点*/inorder(binstree t)中序遍历display(seqstring s)显示学生名字mian() 二大数相乘实验要求：输入第一个数为：13286754398172586，输入第二个数为：2397567453241147则程序运行后输出13286754398172586*2397567453241147=正确答案。

14、设计思路；建立两个字符数组，并将其转换成数，两个转换后的数相乘得出所要的正确答案。2.代码#include#include#include#define n 100void revert(char t) int i,len; char temp; len=strlen(t); for(i=1;in|strlen(b)n); char *mutiply(char a,char b) char *p; unsigned int i,j,x,y,r1,r2,r3; p=(char *)malloc(1+strlen(a)+strlen(b); pstrlen(a)+strlen(b)=0; for(

15、i=0;istrlen(p);i+) pi=0; for(i=0;istrlen(b);i+) y=bi-0; for(j=0;j=0)&(pi-1=0);i-) pi-1=0; return (p); void main() char an,bn,c2*n; input(a,b); revert(a); revert(b); strcpy(c,mutiply(a,b); revert(a); revert(b); revert(c); printf(%s * %s = %sn,a,b,c); system(pause); 3.功能设计mutiply(char a,char b)将a,b相乘r

16、evert(char t)转换字符串input(char a,char b)输入字符串a，b实验要求：输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出；设计思路：利用二维数组建立迷宫，赋予相应的值，再利用move()函数来选择方向，一步一步的达到终点，利用栈来记录所走的路径，再利用出栈来显示走出迷宫的路径。2.代码#include#includemalloc.h#define maxsize 100#define m 6#define n 8typedef int datatype;typedef struct int x,y; item; item mo

17、ve4; typedef struct int x,y,d; datatype;int mazem+2n+2;typedef struct datatype datamaxsize; int top; seqstack,*pseqstack; pseqstack init_seqstack() pseqstack s; s=( pseqstack)malloc(sizeof( seqstack); if(s) s-top=-1; return s; int empty_seqstack(pseqstack s) if(s-top=-1) return 1; else return 0; int

18、 push_seqstack(pseqstack s,datatype x) if(s-top=maxsize-1) return 0; else s-top+; s-datas-top=x; return 1; int pop_seqstack(pseqstack s,datatype *x) if(empty_seqstack (s) return 0; else *x=s-datas-top; s-top-; return 1; void destroy_seqstack(pseqstack *s) if(*s) free(*s); *s=null; return ; int mazep

19、ath(int mazen+2,item move,int x0,int y0,int a,int b) pseqstack s; datatype temp; int x,y,d,i,j,count=0; temp.x=x0; temp.y=y0; temp.d=-1; s=init_seqstack(); if(!s) printf(can not init); return (0); push_seqstack(s,temp); while(!empty_seqstack(s) pop_seqstack(s,&temp); x=temp.x; y=temp.y; d=temp.d+1;

20、while(d4) i=x+moved.x; j=y+moved.y; if(mazeij=0) temp.x=x; temp.y=y; temp.d=d; push_seqstack(s,temp); x=i; y=j; mazexy=-1; if(x=a&y=b) while(!empty_seqstack(s) pop_seqstack(s,&temp); printf(%d ,%d)- ,temp.x,temp.y); count+; if(count%5=0) printf(n); destroy_seqstack(&s); return 1; else d=0; else d+;

21、destroy_seqstack(&s); return 0; main() int i,j,x0=1,y0=1,count=0; int a=6,b=8,step=0; move0.x=0;move0.y=1; move1.x=1;move1.y=0; move2.x=0;move2.y=-1; move3.x=-1;move3.y=0; for(i=0;im+2;i+) for(j=0;jn+2;j+) mazeij=1; for(i=0;im+2;i+) for(j=0;jn+2;j+) maze11=0; maze13=0; maze15=0; maze21=0; maze22=0;

22、maze24=0; maze26=0; maze31=0; maze32=0; maze33=0; maze37=0; maze41=0; maze42=0; maze43=0; maze45=0; maze47=0; maze51=0; maze53=0; maze54=0; maze55=0; maze56=0; maze61=0; maze62=0; maze66=0; maze67=0; maze68=0; printf(n); for(i=0;im+2;i+) for(j=0;jn+2;j+) printf(%d ,mazeij); count+; if(count%10=0) printf(n); printf(n); mazepath(maze,move,x0,y0,a,b); printf(n); path( maze, move, x0, y0, step); getch(); retu