中央电大数据结构形成性考核册实验报告

中央电大本科数据结构形成性考核册实验报告实验名称：实验一线性表线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。（2）在链表中删除一个最高分和一个最低分的结点。（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。（3）显示要求的结果。【实验步骤】（1）运行PC中的MicrosoftVisualC++6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:#includestdio.h#includestdlib.h#includemalloc.h#includeiostream.h#includeconio.h#defineNULL0#definePWRS5//定义评委人数structpw//定义评委信息{charname[6];floatscore;intage;};typedefstructpwPW;structnode//定义链表结点{structpwdata;structnode*next;};typedefstructnodeNODE;NODE*create(intm);//创建单链表intcalc(NODE*h);//计算、数据处理voidprint(NODE*h);//输出所有评委打分数据voidinput(NODE*s);//输入评委打分数据voidoutput(NODE*s);//输出评委打分数据voidmain(){NODE*head;floatave=0;floatsum=0;head=create(PWRS);printf(所有评委打分信息如下:\n);print(head);//显示当前评委打分calc(head);//计算成绩printf(该选手去掉1最高分和1最低分后的有效评委成绩:\n);print(head);//显示去掉极限分后的评委打分}voidinput(NODE*s){printf(请输入评委的姓名:);scanf(%S,&s-data.name);printf(年龄:);scanf(%d,&s-data.age);printf(打分:);scanf(%f,&s-data.score);printf(\n);}voidoutput(NODE*s){printf(评委姓名:%8s,年龄:%d,打分:%2.2f\n,s-data.name,s-data.age,s-data.score);}NODE*create(intm){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p-next=NULL;for(i=1;i=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p-next=NULL;q-next=p;q=p;}return(head);}voidprint(NODE*h){for(inti=1;((i=PWRS)&&(h-next!=NULL));i++){h=h-next;output(h);}printf(\n);}intcalc(NODE*h){NODE*q,*p,*pmin,*pmax;floatsum=0;floatave=0;p=h-next;//指向首元结点pmin=pmax=p;//设置初始值sum+=p-data.score;p=p-next;for(;p!=NULL;p=p-next){if(p-data.scorepmax-data.score)pmax=p;if(p-data.scorepmin-data.score)pmin=p;sum+=p-data.score;}cout给出最高分的评委姓名：pmax-data.name年龄：pmax-data.age分值：pmax-data.scoreendl;cout给出最低分的评委姓名：pmin-data.name年龄：pmin-data.age分值：pmin-data.scoreendl;printf(\n);sum-=pmin-data.score;sum-=pmax-data.score;for(q=h,p=h-next;p!=NULL;q=p,p=p-next){if(p==pmin){q-next=p-next;p=q;}//删除最低分结点if(p==pmax){q-next=p-next;p=q;}//删除最高分结点}ave=sum/(PWRS-2);cout该选手的最后得分是：aveendl;return1;}程序运行结果如下:线性表的顺序存储结构【问题描述】用顺序表A记录学生的信息，编写程序：（1）将A表分解成两个顺序表B和C，使C表中含原A表中性别为男性的学生，B表中含原表中性别为女性的学生，要求学生的次序与原A表中相同。（2）分别求男生和女生的平均年龄【基本要求】（1）建立学生信息的顺序表A。（2）显示B表和C表中的相关信息。（3）显示计算结果。【实验步骤;】（1）运行PC中的MicrosoftVisualC++6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，(3)输入程序代码，程序代码如下:#includestdio.h#includestdlib.h#includemalloc.h#includeiostream.h#includeconio.h#includestring.h//包含库函数strcpy的头文件#defineNULL0structstudent//定义学生信息{charname[8];intsex;//0女:1:男intage;};typedefstructstudentSTD;intcreate(STD*m);//创建顺序表intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage);//计算、数据处理voidprint(STD*m);constintMAX=100;//定义人数voidmain(){STDA[MAX];STDB[MAX];STDC[MAX];floatage1=0,age2=0;//age1男age2女create(A);printf(学生总表A记录如下:\n);print(A);calc(A,B,C,age1,age2);printf(女生名册B记录如下:\n);print(B);printf(男生名册C记录如下:\n);print(C);}intcreate(STD*m){intn;printf(请输入班级总人数:\n);scanf(%d,&n);m[0].age=n;//置顺序表长度printf(请输入学生信息：\n);for(inti=1;i=n;i++){printf(姓名:);scanf(%s,&m[i].name);printf(性别0女1男:);scanf(%d,&m[i].sex);printf(年龄:);scanf(%d,&m[i].age);printf(\n);}return1;}intcalc(STD*m,STD*n,STD*r,float&Fage,float&Mage){inti,j=1,k=1;n[0].age=r[0].age=0;for(i=1;i=m[0].age;i++){if(m[i].sex==0){strcpy(n[j].name,m[i].name);n[j].sex=m[i].sex;n[j].age=m[i].age;n[0].age++;Mage+=m[i].age;j++;}else{strcpy(r[k].name,m[i].name);r[k].sex=m[i].sex;r[k].age=m[i].age;r[0].age++;Fage+=m[i].age;k++;}}Mage=Mage/n[0].age;Fage=Fage/r[0].age;cout女生的平均年龄是：Mage男生的平均年龄是：Fageendl;return1;}voidprint(STD*m){for(inti=1;i=m[0].age;i++){printf(姓名:%3s,性别(0女1男):%d,年龄:%d\n,m[i].name,m[i].sex,m[i].age);}}程序运行结果如下:实验结束。实验结论：线性表采用链式存储（链表）时：以结构变量存储结点，动态生成结点，以指针链接结点，能有效利用存储空间，插入删除方便，但不能随机访问.单向链表可从某结点访问到后继结点。单向链表操作的关键步骤：建立链表的头插法：指针变量p开辟单元，生成结点，指针变量q始终指向头结点，操作为：p-next=q-next;q-next=p;尾插法：指针变量q始终指向尾结点，p指针开辟单元，生成结点：q-next=p;q=p;?插入：p所指向结点的后面插入新结点s所指结点s-next=p-next;p-next=s;?删除：p，q指向相邻结点，q所指结点是p所指结点的后继，删除q所指结点，p-next=q-next;?遍历：p=p-next;实验名称：实验二栈、列队、递归程序设计2.1栈和队列的基本操作【问题描述】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。【基本要求】（1）正确理解栈的先进后出的操作特点,建立初始栈，通过相关操作显示栈底元素。（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。【实验步骤;】（4）运行PC中的MicrosoftVisualC++6.0程序，（5）点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（6）输入程序代码，程序代码如下:#includestdio.h#includemalloc.h#defineMaxSize100typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];inttop;//栈顶指针}SeqStack;//定义栈typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//队首和队尾指针}SqQueue;//定义队列//---初始栈函数voidInitStack(SeqStack*&s){s=(SeqStack*)malloc(sizeof(SeqStack));s-top=-1;}//----进栈函数intPush(SeqStack*&s,ElemTypee){if(s-top==MaxSize-1)return0;s-top++;s-data[s-top]=e;return1;}//---显示栈函数voidDispStack(SeqStack*s){inti;for(i=s-top;i=0;i--)printf(%c,s-data[i]);printf(\n);}//---显示栈底元素voidDispBottomStack(SeqStack*s){printf(%c,s-data[0]);//先进后出,栈底元素为第一个元素,即data[0]printf(\n);}//---判空栈函数intStackE