数据结构课程设计-9

《数据结构》课程设计报告学号姓名班级指导教师安徽工业大学计算机学院2010年6月建立二叉树和线索二叉树问题描述：分别用以下方法建立二叉树并用图形显示出来：用先序遍历的输入序列用层次遍历的输入序列用先序和中序遍历的结果设计思路：分三个方式去实现这个程序的功能，第一个实现先序遍历的输入数列建立二叉树；第二个是用层次遍历的方法输入序列；第三个是用先序和后序遍历的结果来建立二叉树；三种方法建立二叉树后都进行输出。关键是将这三个实现功能的函数写出来就行了；最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历（不使用栈）。数据结构设计：该程序的主要目的就是建立二叉树和线索二叉树，所以采用树的存储方式更能完成这个程序；结点的结构如下：typedefstructbnode{DataTypedata; intltag,rtag;structbnode*lchild,*rchild;}Bnode,*BTree;功能函数设计：BTreeCreateBinTree()用先序遍历的方法讲二叉树建立；BTreeCREATREE()用队列实现层次二叉树的创建；voidCreatBT()；用先序和中序遍历的结果建立二叉树；voidInThread(BTreet,BTreepre)中序线索化；编码实现：#include<iostream.h>#include<stdlib.h>#definemax100typedefstructbnode{ chardata; intltag,rtag; structbnode*lchild,*rchild;}Bnode,*BTree;BTreeQ[max];BTreeCREATREE(){ charch; intfront=1,rear=0; BTreeroot,s; root=NULL; cout<<"'@'表示'空','#'表示'结束'"<<endl; cin>>ch; while(ch!='#') { s=NULL; if(ch!='@') { s=(BTree)malloc(sizeof(Bnode)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } cin>>ch; } returnroot;}intsearch(charino[],charpre)//在中序序列中查找先序中该元素所在位置{ inti=0; while(ino[i]!=pre&&ino[i]) i++; if(ino[i]==pre) returni; else return-1;}voidCreatBT(BTree&T,charpre[],charino[],intps,intis,intn){ intk; if(n==0) T=NULL; else { k=search(ino,pre[ps]); if(k==-1) cout<<"error!"; else { T=(Bnode*)malloc(sizeof(Bnode)); T->data=pre[ps]; if(k==is) T->lchild=NULL; else CreatBT(T->lchild,pre,ino,ps+1,is,k-is); if(k==is+n-1) T->rchild=NULL; else CreatBT(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1); } }}BTreeCreateBinTree(){ BTreeT; charch; cin>>ch; if(ch=='#')T=NULL; else { T=(BTree)malloc(sizeof(Bnode)); T->data=ch; T->ltag=T->rtag=0; T->lchild=CreateBinTree(); T->rchild=CreateBinTree(); } returnT;}voidPreorder(BTreeT){ if(T) { cout<<T->data<<""; Preorder(T->lchild); Preorder(T->rchild); }}voidInorder(BTreeT){ if(T) { Inorder(T->lchild); cout<<T->data<<""; Inorder(T->rchild); }}voidPostorder(BTreeT){ if(T) { Postorder(T->lchild); Postorder(T->rchild); cout<<T->data<<""; }}voidInThread(BTreet,BTreepre)//中序线索化{ if(t) { InThread(t->lchild,pre); if(t->lchild==NULL) { t->ltag=1; t->lchild=pre; } if(t->rchild==NULL) t->rtag=1; if((pre)&&(pre->rtag==1)) pre->rchild=t; pre=t; InThread(t->rchild,pre); }}BTreeInPostNode(BTreep){ BTreepost; post=p->rchild; if(p->rtag==1) returnpost; elsewhile(post->ltag==0) post=post->lchild; returnpost;}voidInOrderTh(BTreet)//中序线索化遍历{ BTreep; if(t) { p=t; while(p->ltag==0) p=p->lchild; while(p) { cout<<p->data; p=InPostNode(p); } }}voidmain(){ BTreeT; intchoice1,choice2; cout<<"建立二叉树的方式："<<endl; cout<<"-----------------------"<<endl; cout<<"1、先序遍历的输入序列："<<endl; cout<<"2、层次遍历的输入序列："<<endl; cout<<"3、先序和中序遍历的结果："<<endl; cout<<"0、退出"<<endl; cout<<"-----------------------"<<endl; while(1){ cout<<"你的选择:"; cin>>choice1; switch(choice1) { case1: cout<<"请输入结点的信息："<<endl; T=CreateBinTree(); do{ cout<<endl; cout<<"请选择：1.先序遍历2.中序遍历3.后序遍历(输入0结束)"<<endl; cin>>choice2; switch(choice2){ case1:Preorder(T); break; case2:Inorder(T); break; case3:Postorder(T);break; case0:break; } }while(choice2!=0); cout<<endl; cout<<"中序线索化的实现："<<endl; InThread(T,NULL); InOrderTh(T); cout<<endl; break; case2: BTreetree; tree=CREATREE(); do{ cout<<endl; cout<<"请选择：1.先序遍历2.中序遍历3.后序遍历(输入0结束)"<<endl; cin>>choice2; switch(choice2){ case1:Preorder(tree); break; case2:Inorder(tree); break; case3:Postorder(tree);break; case0:break; } }while(choice2!=0); cout<<endl; break; case3: charpre[max],ino[max]; cout<<"输入先序序列：(提示：ABDECF)"; cin>>pre; cout<<"输入中序序列：(提示：DBEAFC)"; cin>>ino; BTreeTR; TR=NULL; CreatBT(TR,pre,ino,0,0,7); cout<<"先序遍历的二叉树："; Preorder(TR); cout<<endl; cout<<"中序遍历的二叉树："; Inorder(TR); cout<<endl; cout<<"后序遍历的二叉树："; Postorder(TR); cout<<endl; break; case0: exit(0); } }}运行与测试：选择1.用先序遍历的输入序列选择2.用层次遍历的输入序列选择3.用先序和中序遍历的结果学生成绩查询系统问题描述：编写程序完成学生成绩记录的查询若按学号进行顺序查找，例如：输入99070103，则输出该学生的信息；按学号排序后对学号进行折半查找；随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。设计思路：该系统主要有三个选择；第一个就是用顺序表来存储，对学号进行顺序查找，找到你所找的学号就输出该学生的信息；第二个就是对学号进行排序后进行折半查找；第三个就是随机输入以学号为关键字的信息，同时建立二叉排序树，最后对该树进行二叉排序树查找。数据结构设计：typedefintKeyType;/*整型*/typedefstruct{KeyTypekey;charname[10];intscore;}DataType;顺序表结构：typedefstruct{DataTyper[maxsize];/*数据元素存储空间*/intlength;/*表的长度*/}Sqlist,*PSqlist;结点结构：typedefstructbnode{ DataTypedata; structbnode*lchild,*rchild;}Bnode,*BTree;功能函数设计：PSqlistCreate()建立顺序表SeqSearch()顺序表的查找StraightInsertSort(p)直接插入排序BinSearch(p,x)折半查找BSTreeInert(&Tree,P)建立二叉排序树BSTreeSearch(Tree,y)二叉排序树的查找编码实现：/*学生成绩查询系统*/#include<iostream>#include<string>usingnamespacestd;#definemaxsize100/*查找表最大长度*/typedefintKeyType;/*整型*/typedefstruct{KeyTypekey;charname[10];intscore;}DataType;typedefstruct{DataTyper[maxsize];/*数据元素存储空间*/intlength;/*表的长度*/}Sqlist,*PSqlist;typedefstructbnode{ DataTypedata; structbnode*lchild,*rchild;}Bnode,*BTree;voidBSTreeInert(BTree*t,DataTypep){ BTreer; if(*t==NULL) { r=(BTree)malloc(sizeof(Bnode)); r->data.key=p.key; strcpy(r->,); r->data.score=p.score; r->lchild=r->rchild=NULL; *t=r; } else if(p.key<(*t)->data.key) BSTreeInert(&(*t)->lchild,p); else BSTreeInert(&(*t)->rchild,p);}BTreeBSTreeSearch(BTreet,KeyTypek){ if(t==NULL)returnNULL; if(t->data.key==k)return(t); if(t->data.key>k) returnBSTreeSearch(t->lchild,k); else returnBSTreeSearch(t->rchild,k); }intSeqSearch(PSqlists,KeyTypek){inti;for(i=0;i<=s->length;i++)if(s->r[i].key==k) return(i);/*查找成功*/return(-1);/*查找失败*/}PSqlistCreate(){ PSqlistL; inti=1; L=(PSqlist)malloc(sizeof(Sqlist)); cout<<"请输入学生信息："<<endl; cout<<"学号"<<""<<"姓名"<<""<<"成绩"<<endl; do { cin>>L->r[i].key; cin>>L->r[i].name; cin>>L->r[i].score; i++; }while(L->r[i-1].key!=0); L->length=i-1; returnL; }PSqlistStraightInsertSort(PSqlistS)//直接插入排序{ inti,j; for(i=2;i<=S->length;i++) { S->r[0]=S->r[i]; j=i-1; while(S->r[0].key<S->r[j].key) { S->r[j+1]=S->r[j]; j--; } S->r[j+1]=S->r[0]; } returnS;}intBinSearch(PSqlists,KeyTypek){intlow,mid,high;low=1;high=s->length;while(low<=high){ mid=(low+high)/2; if(s->r[mid].key==k)return(mid);else { if(s->r[mid].key>k) high=mid-1; elselow=mid+1; }}return(-1);}voidmain(){ PSqlistp; inti; intchoice,x; p=Create(); cout<<"学生表建立完成"<<endl; for(i=1;i<p->length;i++) { cout<<p->r[i].key<<""; cout<<p->r[i].name<<""; cout<<p->r[i].score<<""; cout<<endl; } cout<<"----------------------------------"<<endl; cout<<"成绩管理系统"<<endl; cout<<"1.按顺序查找"<<endl; cout<<"2.按学号排序后对学号进行折半查找"<<endl;cout<<"3.构建二叉排序树二叉排序树查找"<<endl; cout<<"0.退出！！"<<endl; cout<<"----------------------------------"<<endl; do{ cout<<"请输入你的选择："; cin>>choice; switch(choice) { case1: intt; cout<<"请输入你要找的学生的学号："; cin>>x; t=SeqSearch(p,x); if(t!=-1) cout<<p->r[t].name<<""<<p->r[t].score<<endl; elsecout<<"查找失败！"<<endl; break; case2: PSqlistT; intx; T=StraightInsertSort(p); cout<<"排序后："<<endl; f