数据结构课程设计报告2
数据结构课程设计报告学 号姓 名班 级计091指导教师安徽工业大学计算机学院2011年6月一学生成绩查询实验要求: 若按学号进行顺序查找,例如:输入99070103,则输出 56 。 按学号排序后对学号进行折半查找。 随机输入以学号为关键字的学生信息并构建二叉排序树,对学号进行二叉排序树查找。设计思路: 顺序表建立学生信息,包括double学号,sting名字,int分数,然后进行学号顺序查找,折半查找。 建立二叉排序树,对二叉排序树进行学号查找,显示出相应的信息。2.代码#include<stdio.h>#include<stdlib.h>#include<string.h>#define Maxsize 100typedef double Keytype;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 structDatatype1 r Maxsize;int length;seqList; int display(seqstring s) int i; s.leng=5; for(i=0;i<5;i+) printf("%c",s.di); return 1; int seqSearch(seqList s,Keytype k) int i; for(i=0;i<s.length;i+) if(s.ri.key=k) printf("%.0ft",s.ri.key) ; display(s.ri.name); printf(" %dn",s.ri.score); return (i); return (-1); int BinSearch(seqList s,Keytype k) int low,mid,high; low=0;high=s.length-1; while(low<=high) mid= (low+high)/2; if(s.rmid.key=k) printf("%.0ft",s.rmid.key) ; display(s.rmid.name); printf(" %dn",s.rmid.score); return (mid); else if(s.rmid.key>k) 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,Keytype k) /*判断结点是否存在*/if(t=NULL)return NULL;if(t->elem.key=k) return (t);if(t->elem.key>k) 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 BinStreenode); r->elem.key = k; r->name=name1; r->score=score1; r->lchild= r->rchild= NULL; *t=r; return ; else if(k<(*t)->elem.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->elem.key!=k) if(p->elem.key>k) 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.key>k) p=p->lchild; else p=p->rchild; if(p=NULL)return (0); if(p->lchild=NULL) 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) InOrder(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,99074004,99074005,99074006,99074007,99074008,99074009; BinStree t; seqList s; s.length=0; printf("顺序建立成绩表:n"); for(i=0;i<n;i+) s.ri.key=bi; s.ri.name=ci; s.ri.score=ai; s.length+; for(i=0;i<s.length;i+) printf("%.0ft",s.ri.key) ; display(s.ri.name); printf(" %dn",s.ri.score); /* printf("%.0f %s %dn",s.ri.key,s.ri.name,s.ri.score); */ printf("顺序查找:"); seqSearch(s, b4); printf("折半查找:"); BinSearch( s,b5); t=Create_BinStree(); for(i=0;i<n;i+) if(BinStreeSearch(t,bi)=NULL) BinStreeInsert( &t,b