第一篇：数据结构 任务调度 实验报告
实验报告
实验名称：表达式求值 任务调度 实验类型：综合性实验 班级：
学号：
姓名：
实验日期：2014.5.28
表达式求值 1.问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4-* 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计
建立栈，算数表达式的计算往往是通过栈来实现的，所以建立结构体，如下 typedef struct{ float *base;//栈底指针
float *top;//栈顶指针
int stacksize;}SqStack_f;//实数栈
typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈
3.算法设计
void Translate(char *s1)
//中缀转后缀
{ char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);
//初始化一个运算符栈
Push_c(&Optr,'(');while(s1[i]!='#'){
if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.')
{
s2[j++]=s1[i];
if((s1[i+1]<'0' || s1[i+1]>'9')&& s1[i+1]!='.')
s2[j++]=' ';
//将完整的字符型数字存入 然后存入空格
}
else
switch(s1[i])
{
case'(':Push_c(&Optr,s1[i]);break;
//遇到左括号 将其压栈
case')':Pop_c(&Optr,&t);
//遇到右括号时
将栈内运算符弹出并压入数组s2 直到遇到左括号
while(t!='(')
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环
{
Pop_c(&Optr,&t);
s2[j++]=t;
//弹出栈顶元素 并存入数组s2
}
Push_c(&Optr,s1[i]);
//将当前遇到运算符压栈
}
i++;} Pop_c(&Optr,&t);while(t!='('){
s2[j++]=t;
Pop_c(&Optr,&t);} for(i=0;i s1[i]=s2[i];s1[i]='#';s1[i+1]=' ';} void Calculate(SqStack_f *s,char *s2) //计算表达式的值 { float m,x,y,z; int p,i=0,j=0;while(s2[i]!='#'){ if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.'){ m=0; while(s2[i]!=' ' && s2[i]!='.') m=m*10+(float)(s2[i++]-'0'); if(s2[i]=='.') { j=0;i++; while(s2[i]!=' ') { m=m*10+(float)(s2[i++]-'0'); j++; } while(j>0) { m/=10; j--; } } i++; Push_f(s,m); GetTop_f(s,&m);} else { Pop_f(s,&x); Pop_f(s,&y); switch(s2[i]) { case '+':z=y+x;Push_f(s,z);break; case '-':z=y-x;Push_f(s,z);break; case '*':z=y*x;Push_f(s,z);break; case '/':if(x==0) { printf(“表达式出错，除数为‘0’，无意义n”); exit(1); } else { z=y/x; Push_f(s,z); break; } case '%':if(x==0||(int)x!=x||(int)y!=y) { printf(“表达式出错n”); exit(1); } else { p=(int)y%(int)x; Push_f(s,p); break; } } i++;} } } int precede(char Top_char,char s1_char) //比较运算符的优先级 { int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i<2;i++) switch(op[i]) { case'(':case')':pre[i]=0;break; case'+':case'-':pre[i]=1;break; case'*':case'/':case’%’:pre[i]=2;break; } if(pre[0]>=pre[1]) //栈顶元素top char>=s1 char就返回1 return 1;else return 0;} void convert(char *s,char *output) //中缀转前缀 { int j=0;int top=0; char stack[50];strcpy(output,“"); for(int i=strlen(s)-1;i>=0;) { if((s[i]>=48&&s[i]<=57)||s[i]=='.') output[j++]=s[i]; if(s[i]==')') { top++; stack[top]=s[i]; } while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%') { output[j++]=' '; if(top==0||stack[top]==')'||precede(s[i],stack[top])) { top++; stack[top]=s[i]; break; } else { output[j++]=stack[top]; top--; } } if(s[i]=='(') { while(stack[top]!=')') { output[j++]=stack[top]; top--; } top--; } i--; } while(top!=0) { output[j++]=stack[top]; top--; } } 4.界面设计 printf(”请输入算术表达式，结束前请输入#号！n“); 5.运行、测试与分析 6、实验收获与思考 1．熟练掌握栈的定义及使用。 2．了解表达式求值的转换算法。设计前、后缀表达式求值算法。 3．设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。 7、源代码 #include typedef struct{ float *base;float *top;int stacksize;}SqStack_f;//实数栈 typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈 void InitStack_f(SqStack_f *s){ s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s->base) exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void InitStack_c(SqStack_c *s){ s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char));if(!s->base) exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void GetTop_f(SqStack_f *s,float *e){ if(s->top==s->base){ printf(”ERROR!n“); exit(1);} *e=*(s->top-1);} void GetTop_c(SqStack_c *s,char *e){ if(s->top==s->base){ printf(”ERROR!n“); exit(1);} *e=*(s->top-1);} void Push_f(SqStack_f *s,float e){ if(s->top-s->base>=s->stacksize){ s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float)); if(!s->base) { printf(”OVERFLOW!n“); exit(1); } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Push_c(SqStack_c *s,char e){ if(s->top-s->base>=s->stacksize){ s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char)); if(!s->base) { printf(”OVERFLOW!n“); exit(1); } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Pop_f(SqStack_f *s,float *e){ if(s->top==s->base) exit(1);*e=*--s->top;} void Pop_c(SqStack_c *s,char *e){ if(s->top==s->base) exit(1);*e=*--s->top;} int precede(char Top_char,char s1_char) //比较运算符的优先级 { int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i<2;i++) switch(op[i]) { case'(':case')':pre[i]=0;break; case'+':case'-':pre[i]=1;break; case'*':case'/':case'%':pre[i]=2;break; } if(pre[0]>=pre[1]) //栈顶元素top char>=s1 char就返回1 return 1;else return 0;} void Translate(char *s1) //中缀转后缀 { char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr); //初始化一个运算符栈 Push_c(&Optr,'(');while(s1[i]!='#'){ if(s1[i]>='0' && s1[i]<='9' || s1[i]=='.') { s2[j++]=s1[i]; if((s1[i+1]<'0' || s1[i+1]>'9')&& s1[i+1]!='.') s2[j++]=' '; //将完整的字符型数字存入 然后存入空格 } else switch(s1[i]) { case'(':Push_c(&Optr,s1[i]);break; //遇到左括号 将其压栈 case')':Pop_c(&Optr,&t); //遇到右括号时 将栈内运算符弹出并压入数组s2 直到遇到左括号 while(t!='(') { s2[j++]=t; Pop_c(&Optr,&t); } break; default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环 { Pop_c(&Optr,&t); s2[j++]=t; //弹出栈顶元素 并存入数组s2 } Push_c(&Optr,s1[i]); //将当前遇到运算符压栈 } i++;} Pop_c(&Optr,&t);while(t!='('){ s2[j++]=t; Pop_c(&Optr,&t);} for(i=0;i s1[i]=s2[i];s1[i]='#';s1[i+1]=' ';} void Calculate(SqStack_f *s,char *s2) //计算表达式的值 { float m,x,y,z;int p,i=0,j=0;while(s2[i]!='#'){ if(s2[i]>='0' && s2[i]<='9' || s2[i]=='.') { m=0; while(s2[i]!=' ' && s2[i]!='.') m=m*10+(float)(s2[i++]-'0'); if(s2[i]=='.') { j=0;i++; while(s2[i]!=' ') { m=m*10+(float)(s2[i++]-'0'); j++; } while(j>0) { m/=10; j--; } } i++; Push_f(s,m); GetTop_f(s,&m); } else { Pop_f(s,&x); Pop_f(s,&y); switch(s2[i]) { case '+':z=y+x;Push_f(s,z);break; case '-':z=y-x;Push_f(s,z);break; case '*':z=y*x;Push_f(s,z);break; case '/':if(x==0) { printf(”表达式出错，除数为‘0’，无意义n“); exit(1); } else { z=y/x; Push_f(s,z); break; } case '%':if(x==0||(int)x!=x||(int)y!=y) { printf(”表达式出错n“); exit(1); } else { p=(int)y%(int)x; Push_f(s,p); break; } } i++;} } } void result(SqStack_f *s){ float v;GetTop_f(s,&v);printf(”The final result is:%gn“,v);} void convert(char *s,char *output) //中缀转前缀 { int j=0;int top=0; char stack[50];strcpy(output,”“); for(int i=strlen(s)-1;i>=0;) { if((s[i]>=48&&s[i]<=57)||s[i]=='.') output[j++]=s[i]; if(s[i]==')') { top++; stack[top]=s[i]; } while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%') { output[j++]=' '; if(top==0||stack[top]==')'||precede(s[i],stack[top])) { top++; stack[top]=s[i]; break; } else { output[j++]=stack[top]; top--; } } if(s[i]=='(') { while(stack[top]!=')') { output[j++]=stack[top]; top--; } top--; } i--; } while(top!=0) { output[j++]=stack[top]; top--; } } int main(){ int i;SqStack_f stack;char str[80];char output[80]; printf(”请输入算术表达式，结束前请输入#号！n“); gets(str); InitStack_f(&stack); printf(”前缀表达式为：n“); convert(str,output); for(i=strlen(output)-1;i>=0;i--) printf(”%c“,output[i]); printf(”n“); Translate(str); printf(”后缀表达式为：n“); puts(str); Calculate(&stack,str); result(&stack);} 任务调度 1.问题描述 多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。 忽略任务提交的时间差，即认为各任务同时提交。 各任务不同时提交。2.数据结构设计 struct task { }T[100];int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间 3.算法设计 同时 int cmp(const void *a,const void *b) //相同时间排序 { return(*(struct task *)a).ne>(*(struct task *)b).ne;} void sametime(int n){ double sum,sum2;int i;for(i=0;i { printf(”请输入第%d个任务所需要的时间n“,i+1); T[i].t=0; scanf(”%d“,&T[i].ne); T[i].order=i+1;} t=0;sum=0;printf(”序号 开始时间 等待时间 结束时间n“);for(i=0;i { printf(”%-7d“,i+1); printf(”%-7d“,t); printf(”%-8d“,t); t+=T[i].ne; printf(”%-8d“,t); printf(”n“); sum+=((n-i-1)*T[i].ne);} printf(”n“);printf(”序号 开始时间 等待时间 结束时间n“);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序 t=0;sum2=0;for(i=0;i { printf(”%-7d“,T[i].order); printf(”%-7d“,t); printf(”%-8d“,t); t+=T[i].ne; printf(”%-8dn“,t); printf(”n“); sum2+=((n-i-1)*T[i].ne);} printf(”顺序执行等待平均时间为 %.3lfn“,sum/n);} printf(”最短等待平均时间为 %.3lfn“,sum2/n);不同时 int comp(const void *a,const void *b)//不同时间排序 { return T[*(int *)a].ne>T[*(int *)b].ne;} void dele(){ int i;printf(”%-10d%-10d%-10d%-20dnn“,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i que[i]=que[i+1];rear--;} int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne<=0){ T[que[0]].end=t; dele(); for(i=0;i T[que[i]].wa++; return 1;} else { for(i=1;i T[que[i]].wa++; return 0;} }//时间段移动查寻当前队列 void insert(int n){ int i,rec;for(i=0;i if(T[que[i]].ne>T[n].ne) break;} rec=i;for(i=rear;i>rec;i--) que[i]=que[i-1];que[rec]=n; rear++;} void difftime(int n)//输入本来按照先后顺序 { int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i { printf(”请输入第%d个任务提交时刻和第%d个任务执行时间n“,i+1,i+1); scanf(”%d%d“,&T[i].t,&T[i].ne); T[i].order=i+1; T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(”序号 开始时间 等待时间 结束n“);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i t++;//时间移动 i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间 if(t>=T[j].t&&j { insert(j);//把任务插入到队列 j++; qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序 } if(T[que[0]].sta==-1)//给队列最前点赋起始值 T[que[0]].sta=t;} for(i=0;i sum+=T[i].wa;printf(”平均等待时间为 %.3lfsnn“,sum/n); } 4.界面设计 printf(”请输入任务数n“); 5.运行、测试与分析 同时 不同时 6.实验收获及思考 写出一个程序不仅仅是算法的考究，更是细节的较量。 从理论到实践，我学到很多很多的东西。不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。 7、源代码 同时 #include }T[100];int cmp(const void *a,const void *b) //相同时间排序 { return(*(struct task *)a).ne>(*(struct task *)b).ne;} void sametime(int n){ double sum,sum2;int i;for(i=0;i printf(”请输入第%d个任务所需要的时间n“,i+1); T[i].t=0; scanf(”%d“,&T[i].ne); T[i].order=i+1;} t=0;sum=0;printf(”序号 开始时间 等待时间 结束时间n“);for(i=0;i { printf(”%-7d“,i+1); printf(”%-7d“,t); printf(”%-8d“,t); t+=T[i].ne; printf(”%-8d“,t); printf(”n“); sum+=((n-i-1)*T[i].ne);} printf(”n“);printf(”序号 开始时间 等待时间 结束时间n“);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序 t=0;sum2=0;for(i=0;i { printf(”%-7d“,T[i].order); printf(”%-7d“,t); printf(”%-8d“,t); t+=T[i].ne; printf(”%-8dn“,t); printf(”n“); sum2+=((n-i-1)*T[i].ne);} printf(”顺序执行等待平均时间为 %.3lfn“,sum/n);printf(”最短等待平均时间为 %.3lfn“,sum2/n);} int main(){ int n;printf(”请输入任务数:n“);while(scanf(”%d“,&n)!=EOF){ if(n<=0) { printf(”输入错误,程序结束“); break; } sametime(n);} system(”pause“);return 0;} 不同时 #include }T[100];int comp(const void *a,const void *b)//不同时间排序 { return T[*(int *)a].ne>T[*(int *)b].ne;} void dele(){ int i;printf(”%-10d%-10d%-10d%-20dnn“,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i que[i]=que[i+1];rear--;} int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne<=0){ T[que[0]].end=t; dele(); for(i=0;i T[que[i]].wa++; return 1;} else { for(i=1;i T[que[i]].wa++; return 0;} }//时间段移动查寻当前队列 void insert(int n){ int i,rec;for(i=0;i if(T[que[i]].ne>T[n].ne) break;} rec=i;for(i=rear;i>rec;i--) que[i]=que[i-1];que[rec]=n; rear++;} void difftime(int n)//输入本来按照先后顺序 { int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i { printf(”请输入第%d个任务提交时刻和第%d个任务执行时间n“,i+1,i+1); scanf(”%d%d“,&T[i].t,&T[i].ne); T[i].order=i+1; T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(”序号 开始时间 等待时间 结束n“);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i t++;//时间移动 i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间 if(t>=T[j].t&&j { insert(j);//把任务插入到队列 j++; qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序 } if(T[que[0]].sta==-1)//给队列最前点赋起始值 T[que[0]].sta=t;} for(i=0;i sum+=T[i].wa;printf(”平均等待时间为 %.3lfsnn“,sum/n); } int main(){ int n;printf(”请输入任务数n“);while(scanf(”%d“,&n)!=EOF){ if(n<=0) { printf(”输入错误,程序结束“); break; } difftime(n);} system(”pause");return 0;} 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高 南京信息工程大学实验（实习）报告 实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍 系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700 3实验一顺序表的基本操作及C语言实现 【实验目的】 1、顺序表的基本操作及 C 语言实现 【实验要求】 1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。 2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。 【实验内容】 1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作； 2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重 复的元素），并求这样的两个集合的并。 【实验结果】 [实验数据、结果、遇到的问题及解决] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 数据结构实验报告 一． 题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i //数据域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子树为空重接它的左子树 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函数 printf(“ ---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示输入操作符************************:”);printf(“n”);printf(“ 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“输入要插入的节点:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“树状图为:n”); printtree(bst,layer); break; case 2: } printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst); printf(“后序遍历:n”); PostOrderNoRec(bst); printf(“树状图为:n”); printtree(bst,layer); break;case 5: printf(“程序执行完毕!”); return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include int main(){ cout<<“ 欢迎来到学生管理系统”< cout<<“该学号信息已经存在，添加失败”< break;} cout<<“重新输入添加的学号”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“谢谢使用”< 二叉排序树储存数据界面（储存学生信息略） 创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四． 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。 实验报告4 排序 一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验要求及内容 要求编写的程序所能实现的功能包括： 1、从键盘输入要排序的一组元素的总个数 2、从键盘依次输入要排序的元素值 3、对输入的元素进行快速排序 4、对输入的元素进行折半插入排序 三、实验代码及相关注释 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的结构体 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的结构体 int Partition(SqList &L, int low, int high) //1 寻找基准 { L.r[0]=L.r[low];//子表的第一个记录作基准对象 int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： （一个程序，调试运行一次，可多次进行不同序列的不同排序）第二篇：数据结构实验报告
第三篇：数据结构实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 