国开计算机本科《数据结构》网核实践活动2

最新国开计算机本科

《数据结构》网核实践活动2试题与答案

1.线性表的链式存储结构

实验目的

掌握线性表的链式存储结构及基本操作，深入了解顺序表的

基本特性。

问题描述

某项比赛中，评委们给某参赛者的评分信息存储在一个带头

结点的单向链表中，编写程序：

（1）显示在评分中给出最高分和最低分的评委的有关信息

（姓名、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均

成绩。

实验要求

(1)建立一个评委打分的单向链表。

(2)显示删除相关结点后的链表信息。

(3)显示要求的结果。

请认真阅读以上实验的问题描述，按照实验要求认真独立完

成实验。如果在实验过程中遇到困难，你可以通过以下辅助

方式，顺利完成本实验。

如果对于本实验无从下手，你可以通过查看“设计思路”，

帮助你开拓思维。设计思路

(1)评委信息结点用结构变量存储，包含三个成员项，即

姓名、年龄、评分。结构类型定义如下：

〃定义评委信息

structpw

charname[8];〃姓名

shortage;〃年龄

floatscore;//评分

)；

(2)用头插法或尾插法建立带头结点的单链表，本实验采

用尾插法。

(3)遍历链表并逐次比较求最高分和最低分。

(4)在链表中物理删除，即实际删除最高分和最低分结点；

也可以进行逻辑删除，即在被删结点的数据域设置一个删除

标记，本实验采用物理删除的方法。

(5)遍历链表，累加求和，计算总分及平均分，并输出相

关信息。

如果对于自己编写好的程序不知道是否正确，你可以查看

“实验程序”进行核查。

如果对于自己编写的程序不知道是否正确，你可以通过查看

“实验设计”进行核查。实验设计

程序代码如下：

〃实验1.1线性表的链接存储结构

#include

#include

#include

#definePWRS5〃定义评委人数

〃定义评委信息

structpw

charname[8];〃姓名

shortage;〃年龄

floatscore;〃评分

)；

typedefstructpwPW;

〃定义链表结点

structnode

(

PWdata;

structnode*next;

);

typedefstructnodeNODE;

NODE*create(intn);〃建立单链表

voidinput(NODE*sjnti);〃输入第i个评委信息

voidoutput(NODE*s);〃输出评委信息

voidtraverse(NODE*head);〃遍历链表

voidcalc(NODE*head);〃计算及数据处理

voidmain()

(

NODE*head=NULL;

head=create(PWRS);〃建立评委信息单链表

printf("\n所有评委的评分信息如下:\n");

traverse(head);〃输出所有评委的评分信息

calc(head);〃计算成绩

printf("该参赛者去掉一个最高分和一个最低分后的有效评

委的评分信息如下:VT);

traverse(head);〃输出有效评委的评分信息

)

〃尾插法建立带头结点的单链表

NODE*create(intn)

NODE*head,*pz*q;

inti;

p=(NODE*)malloc(sizeof(NODE));

head=p;q=p;p->next=NULL;

for(i=l;i<=n;i++)

p=(NODE*)malloc(sizeof(NODE));

input(pzi);

p->next=NULL;

q->next=p;

q=p;

)

return(head);

)

〃输入评委信息，包括姓名、年龄和评分

voidinput(NODE*sjnti)

(

printf("请输入第%d个评委的姓名、年龄和评分："J);

scanf("%s%d%f"/&s->/&s->data.age/&s->data.score);

)

〃输出评委信息

voidoutput(NODE*s)

printf("评委姓名：%6s年龄：%d评

分：

%6.2f\n"/s->/s->data.age,s->data.score);

)

〃遍历链表，输出所有评委的评分信息

voidtraverse(NODE*head)

(

NODE*p=head->next;//指向第一个结点

while(p!=NULL)

(

output(p);

p=p->next;

)

printf("\n");

)

〃输出最高分及最低分评委信息，删除最高分及最低分结点

并计算参赛者的最后平均分

voidcalc(NODE*head)

NODE*q,*p,*pmin,*pmax;

floatsum=0;〃总分

floatave=0;〃平均分

〃查找最高分和最低分并计算总分

p=head->next;

pmin=pmax=p;

while(p!=NULL)

(

sum+=p->data.score;

if(p->data.score>pmax->data.score)pmax=p;//pmax指向最高

分结点

if(p->data.scoredata.score)pmin=p;//pmin指向最低分结点

p=p->next;

)

〃输出最高分及最低分评委信息

printf("给出最高分的评委姓名：%6s年龄：%d评

分：

%6.2f\n"/pmax->,pmax->data.age/pmax->data.s

core);

printf("给出最低分的评委姓名：%6s年龄：%d评

分

：%6.2f\n"/pmin->/pmin->data.age/pmin->data.sc

ore);

printf("\n");

〃去掉一个最高分和一个最低分，计算并输出参赛者的最后

平均分

sum-=pmax->data.score;

sum-=pmin->data.score;

ave=sum/(PWRS-2);

printf("该参赛者去掉一个最高分和一个最低分后的平均得

分为：

%6.2f\n"zave);

printf("\n");

〃在链表中删除最高分和最低分结点

for(q=headzp=head->next;p!=NULL;q=pzp=p->next)

if(p==pmin){q->next=p->next;p=q;}〃删除最低分结点

if(p==pmax){q->next=p->next;p=q;}//册(J除最高分结点

)

)

如果已运行程序得出实验结果，你可以查看“测试结果”进

行检测。测试结果

程序运行结果如下:

\Docu>entsandSettings\AllUsers\^ffi\syl_l\Debug\syl•exe

一

年

2.龄3675

名

龄

3年4880

u名

龄

年

4名90

龄

年

.和

5名e3878

分

自

信

委的

下

球

评an

心H

答

龄

4-浒

姓a

-E.86.00

告

龄

今

b-36评nx

姓E.j

二-

苟

龄75.00

ca48评E.

姓

二E.

答

a龄80.00

d52评E.

二

姓a

告

龄90.00

e38评nx

-v78.00

出

商分的评委姓名:d年龄：52评分：90.00

出

展分的评委姓名:b年龄：36评分：75.00

81.33

参

毒啻去掉一个最高分和一个最低分后的有效评委的评分信息如下:

妻

名

姓a军舲：45评分：86.00

名

姓

萋c年龄：48许分：80.00

e车舲：38滓分：78.00

'ressanykeytocontinue

点击“实验小结”，看看通过本实验的学习，你有哪些收获。

实验小结

（1）线性表采用链式存储（链表）时，用结构变量存储结

点，动态生成结点，用指针链接结点，能有效利用存储空间，

插入删除方便。

（2）链表不能随机访问，是顺序访问方式，可从某结点访

问到其后继结点，通常对单链表的遍历即从表头结点顺序访

问到表尾结点，任何在链表上做的查找运算都是在遍历的基

础上进行的。

（3）单链表操作的关键步骤包括:

1）建立链表的头插法：指针变量p开辟单元，生成结点,

指针变量q始终指向头结点；操作为：p->next=q->next;

q->next=p;

2）建立链表的尾插法：指针变量p开辟单元，生成结点,

指针变量q始终指向尾结点；操作为：q->next=p;q=p;

3）插入：p结点的后面插入新结点s；操作为：s->next=p->next;

p->next=s;

4）删除：p,q指向相邻结点，q结点是p结点的后继，删

除q结点；操作为：p->next=q->next;

5）遍历：p指向后继结点；操作为：p=p->next;

2.线性表的顺序存储结构

实验目的

掌握线性表的顺序存储结构及基本操作，深入了解顺序表的

基本特性。

问题描述

用顺序表A记录学生的信息，编写程序：

(1)将A表分解成两个顺序表B和C,使C表中含原A表

中性别为男性的学生，B表中含原表中性别为女性的学生，

要求学生的次序与原A表中相同。

(2)分别求男生和女生的平均年龄。

实验要求

(1)建立学生信息的顺序表A。

(2)显示B表和C表中的相关信息。

(3)显示计算结果。

请认真阅读以上实验的问题描述，按照实验要求认真独立完

成实验。如果在实验过程中遇到困难，你可以通过以下辅助

方式，顺利完成本实验。

如果对于本实验无从下手，你可以通过查看“设计思路”，

帮助你开拓思维。设计思路

（1）用结构数组存放学生的信息表，其中每个数组元素（结

构变量）存放一个学生的相关信息，包含三个成员项，即姓

名、性别、年龄。结构类型定义如下：

〃定义学生信息

structstudent

charname[8];〃姓名

shortsex;〃性别,1表示男,0表示女

shortage;//年龄

）；

(2)共设三个结构数组，一个用于存放所有学生信息，该

顺序表需创建，另外两个用于存放结果，即分别存放女生信

息和男生信息。表长存储在数组下标为0的单元中。

(3)通过扫描数组查询到性别信息，采用在顺序表的表尾

插入数据的方法，将结果信息分别存放到B表和C表中。

(4)分别求B表和C表中学生的平均年龄。

如果对于自己编写的程序不知道是否正确，你可以通过查看

“实验设计”进行核查。实验设计

程序代码如下：

〃实验1.2线性表的顺序存储结构

#include

defineMAX100〃定义数组大小

〃定义学生信息

structstudent

charname[8];〃姓名

shortsex;〃性别，1表示男,0表示女

shortage;//年龄

)；

typedefstructstudentList;

voidcreate(List*a);〃建立顺序表

voidtraverse(List*a);〃输出学生信息

doubleaverage(List*a);〃计算平均年龄

voidsplit(List*a,List*b,List*c);〃分解顺序表

voidmain()

Lista[MAX],b[MAX],c[MAX];〃定义三个学生信息表

create(a);

printf(”A表所有学生信息如下:\n")；

traverse(a);

split(a,b,c);〃将A表分解为B表和C表

printf("B表女生信息如下:\n")；

traverse(b);

printf("C表男生信息如下：\n");

traverse(c);

("女生平均年龄：

printf%5.0lf\n"zaverage(b));

("男生平均年龄：

printf%5.0lf\n"zaverage(c));

)

〃建立n个学生的顺序表

voidcreate(List*a)

(

intn;〃实际人数

printf(”请输入学生人数：”);

scanf(”%d”,&n);

a[0].age=n;〃设置表长

for(inti=l;i<=n;i++)

printf（"请输入第%d个学生信息（姓名、性别（1表示男,

0表示女）、年龄）："J）;

scanf("%s%d%d",a[i].namez&a[i].sex,&a[i].age);

)

printf("\n");

)

〃输出学生信息

voidtraverse(List*a)

for(inti=l;i<=a[0].age;i++)

printf("姓名：%6s性别：(%s年

龄：

%d\