国家开放大学电大《数据结构》实验报告.docx
- 文档编号:8991408
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:50
- 大小:378.42KB
国家开放大学电大《数据结构》实验报告.docx
《国家开放大学电大《数据结构》实验报告.docx》由会员分享,可在线阅读,更多相关《国家开放大学电大《数据结构》实验报告.docx(50页珍藏版)》请在冰点文库上搜索。
国家开放大学电大《数据结构》实验报告
数据结构形成性考核册
实验名称:
实验一线性表
线性表的链式存储结构
【问题描述】
某项比赛中,评委们给某参赛者的评分信息存储在一个带头结点的单向链表中,编写程序:
(1)显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。
(2)在链表中删除一个最高分和一个最低分的结点。
(3)计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
【基本要求】
(1)建立一个评委打分的单向链表;
(2)显示删除相关结点后的链表信息。
(3)显示要求的结果。
【实验步骤】
(1)运行PC中的MicrosoftVisualC++6.0程序,
(2)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”,
(3)输入程序代码,
程序代码如下:
#include
#include
#include
#include
#include
#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.score>pmax->data.score)pmax=p;
if(p->data.score
sum+=p->data.score;
}
cout<<"给出最高分的评委姓名:
"<
"<
"< cout<<"给出最低分的评委姓名: "< "< "< 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<<"该选手的最后得分是: "< 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)输入程序代码, 程序代码如下: #include #include #include #include #include #include #defineNULL0 structstudent//定义学生信息 {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<<"女生的平均年龄是: "< "< 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); } } l程序运行结果如下: 实验结束。 实验结论: 线性表采用链式存储(链表)时: 以结构变量存储结点,动态生成结点,以指针链接结点,能有效利用存储空间,插入删除方便,但不能随机访问.单向链表可从某结点访问到后继结点。 单向链表操作的关键步骤: 建立链表的头插法: 指针变量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)输入程序代码, 程序代码如下: #include #include #defineMaxSize100 typedefcharElemType; 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"); } //---判空栈函数 intStackEmpty(SeqStack*s) { return(s->top==-1); } //---出栈函数 intPop(SeqStack*&s,ElemType&e) { if(s->top==-1) return0; e=s->data[s->top]; s->top--; return1; } //---初始队列函数 voidInitQueue(SqQueue*&q) { q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0; } //---入队列函数 intInQueue(SqQueue*&q,ElemTypee) { if((q->rear+1)%MaxSize==q->front)//队满 return0; q->rear=(q->rear+1)%MaxSize; q->elem[q->rear]=e; return1; } //---出队列函数 intOutQueue(SqQueue*&q,ElemType&e) { if(q->front==q->rear)//队空 return0; q->front=(q->front+1)%MaxSize; e=q->elem[q->front]; return1; } //---判空队列函数 intQueueEmpty(SqQueue*q) { return(q->front==q->rear); } //-----主程序 voidmain() { ElemTypee; SeqStack*s; printf(" (1)初始化栈s\n"); InitStack(s); printf(" (2)栈为%s\n",(StackEmpty(s)? "空": "非空")); printf("(3)依次进栈元素a,b,c,d,e\n"); Push(s,'a');//入栈元素1 Push(s,'b');//入栈元素2 Push(s,'c');//入栈元素3 Push(s,'d');//入栈元素4 Push(s,'e');//入栈元素5 printf("(4)栈为%s\n",(StackEmpty(s)? "空": "非空")); printf("(5)从栈顶到栈底元素: ");DispStack(s); printf("(6)栈底元素为: ");DispBottomStack(s); printf("(7)出栈/入队列序列: "); SqQueue*q; InitQueue(q); while(! StackEmpty(s)) { Pop(s,e);//出栈 printf("%c",e); InQueue(q,e);//入队 } printf("\n"); printf("(8)栈为%s,",(StackEmpty(s)? "空": "非空")); printf("队列为%s\n",(QueueEmpty(q)? "空": "非空")); printf("(9)出队列/入栈序列: "); while(! QueueEmpty(q)) {OutQueue(q,e);//出队 Push(s,e);//入栈 printf("%c",e); } printf("\n"); printf("(10)栈为%s,",(StackEmpty(s)? "空": "非空")); printf("队列为%s\n",(QueueEmpty(q)? "空": "非空")); free(q);//释放队列 printf("(11)从栈顶到栈底元素: ");DispStack(s); free(s);//释放栈 } 程序运行结果如下: 2.2递归程序设计 【问题描述】 给定一个5位的十进制正整数,用递归法分别编制程序: (1)要求从低位到高位逐次输出各位数字。 (2)要求从高位到低位逐次输出各位数字。 【基本要求】 (1)比较题中两种不同要求的递归程序设计和执行过程差别。 (2)正确理解递归程序的执行过程。 (3)显示计算结果。 【实验步骤】 (1)运行PC中的MicrosoftVisualC++6.0程序, 点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中 (2)输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”, (3)输入程序代码 程序代码如下: #include #include voidout(intn,inti)//从高位到低位输出函数 { intx,y; y=int(pow(10,i)); if(n! =0) { x=n/y; n=n-x*y; printf("%d",x); } elseprintf("0"); i--; if(i>=0)out(n,i); } voidout1(intm,intj)//从低位到高位输出函数 { intx,z; if(m! =0) { x=int(m/10); z=m-x*10; m=x; printf("%d",z); } elseprintf("0"); j--; if(j>=0)out1(m,j); } voidmain() { intm,n,o,x,i,j; printf("输入需要排列的数字: \n"); scanf("%d",&o); m=n=o; x=n; i=-1; while(x! =0) { x=x/10; i++; }//求出i为十进制正整数位数 j=i; printf("\n"); printf("从高位到低位逐次输出各位数字: "); out(n,i); printf("\n"); printf("从低位到高位逐次输出各位数字: "); out1(m,j); printf("\n"); } 程序运行结果如下: 实验结论: 栈和队列是运算受限制的线性表 栈: 后进先出(LIFO) 例: 进栈b,c,d,e,f出栈可能为f,e,d,c,b;b,c,d,e,f;c,b,e,d,f•••但不可能是e,d,f,b,c 队列: 先进先出(FIFO) 例: 入队1,2,3,4,5出队1,2,3,4,5 实验名称: 实验三二叉树 3.1二叉树的顺序存储结构和链式存储结构 【问题描述】 设一棵完全二叉树用顺序存储方法存储于数组tree中,编写程序: (1)根据数组tree,建立与该二叉树对应的链式存储结构。 (2)对该二叉树采用中序遍历法显示遍历结果。 【基本要求】 (1)在主函数中,通过键盘输入建立设定的完全二叉树的顺序存储结构。 (2)设计子函数,其功能为将顺序结构的二叉树转化为链式结构。 (3)设计子函数,其功能为对给定二叉树进行中序遍历,显示遍历结果。 (4)通过实例判断算法和相应程序的正确性。 【实验步骤】 (7)运行PC中的MicrosoftVisualC++6.0程序, (8)点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”, (9)输入程序代码, 程序代码如下: #include #include #include #include #include #defineMaxSize10 typedefstructnode { chardata; structnode*left,*right; }NODE; voidCreab(char*tree,intn,inti,NODE*p); voidInorder(NODE*p); voidmain() { NODE*p; chartree[MaxSize]; intn=1; inti=1; printf("请输入完全二叉数的节点值(连续输入字符,以回车结束输入。 ): "); while((tree[n]=getchar())! ='\n')n++; tree[n]='\n'; p=NULL; Creab(tree,n,i,p); Inorder(p); } voidCreab(char*tree,intn,inti,NODE*p) { if(i>=n)p=NULL; else { p=(NODE*)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 国家 开放 大学 电大 实验 报告