实验内容参考.doc

实验内容：
一共4个实验，写在实验报告单上。
实验一：线性表的链式存储结构
1．问题描述：某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：
（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）
（2）在链表中删除一个最高分和一个最低分的结点。
（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
2．基本要求：
（1）建立一个评委打分的单向链表。
（2）显示删除相关结点后的链表的信息。
（3）显示要求的结果。
3．测试数据

4．实现提示
（1）结点用结构变量存储，至少包含三个成员项，即姓名、评分、年龄。
（2）用头插法或尾插法建立链表。
（3）用扫描链表并逐次比较求最高分和最低分。
程序代码参考：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char name[10];
float score;
int age;
node *next;
};
typedef struct node NODE;
#define NULL 0
NODE *creat1(int n);
void main()
{
NODE *p,*pa,*p1,*p2,*p3,*flagmax,*flagmin;
int n=5;
float max,min;

p1=creat1(n);
p=p1;
p1=p1->next;
p2=p1->next;
p3=p1->next;
max=p2->score;
min=p3->score;

while(p2!=NULL)
{

if (max<p2->score)
{
max=p2->score;
flagmax=p2;
printf("%f",flagmax->score);
}
p2=p2->next;
};
printf("ceshi2222222222222\n");
//删除最大值结点
printf("%f",flagmax->score);
pa=p;
while (pa->next!=flagmax)
{
pa=pa->next;
}
pa->next=flagmax->next;
free(flagmax);

//
while(p3!=NULL)
{

if(min>p3->score)
{
min=p3->score;
flagmin=p3;
}
p3=p3->next;
};
printf("ceshi000\n");
//删除最小值结点
pa=p;
while (pa->next!=flagmin)
{
pa=pa->next;
}
pa->next=flagmin->next;
free(flagmin);
//
printf("ceshi11111\n");
do
{
printf("%s\n",p1->name);
printf("%f\n",p1->score);
printf("%d\n",p1->age);
p1=p1->next;
}while (p1!=NULL);

}

NODE *creat1(int n)
{
NODE *head,*p,*q;
char a[10];
float b;
int c,i;
p=(NODE*)malloc(sizeof(NODE));
head=p;
q=p;
p->next=NULL;
for(i=1;i<=n;i++)
{
p=(NODE*)malloc(sizeof(NODE));
scanf("%s",&a);

scanf("%f",&b);

scanf("%d",&c);
strcpy(p->name,a);
p->score=b;
p->age=c;
p->next=NULL;
q->next=p;
q=p;

}
return (head);

}

实验二：栈、队列、递归程序设计
问题描述：编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。
基本要求：
（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。
（2）程序中要体现出建栈过程和取栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。
测试数据：
实现提示：
（1）采用顺序栈，即用数组存储栈元素。
（2）设定一个临时队列，用来存放从初始栈中出栈的元素。
（3）取出栈底元素后，要将队列中的元素逐一出队并压入出始栈中。
参考程序：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int b[10];
int top=9;
int bottom=0;
int front=0;
int rear=0;
//将数组a中的元素出栈，并将出栈元素送入队列b
do
{
b[rear]=a[top];
top=top-1;
rear=rear+1;
}while top=0;
printf("%d",a[top]);
top=top-1;
do
{
top=top+1;
a[top]=b[front];
front=front+1;
}while front=rear;
}

实验5：查找
某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按照平均成绩有序。
[基本信息]
（1）建立现有学生信息表，平均成绩已有序。
（2）输入插入学生的记录信息。
（3）用折半查找找到插入位置，并插入记录。
（4）显示插入后的信息表。
测试数据
实现提示
（1）用结构数组存储成绩信息表。
（2）对记录中的平均成绩进行折半查找。
程序参考：
#include <stdio.h>
#include <stdlib.h>
Struct NODE
{
Int score;
Char name[10];
};
Int Binary_search(NODE a[],int n,NODE k)
{
Int flag=Flag1=flag2=0;
Int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
If (a[mid].score==k.score)
Return mid;
else if (a[mid].score<k.score)
{
Low=mid+1;
Flag1=1;
}
else
{high=mid-1;
flag2=1;
}
}
If (flag1==1)
flag=low;
else if (flag2==1)
flag=high;
for (int i=n;i>=flag;i--)
{
a[i-1]=a[i-2];
}
a[flag].name=k.name;
a[flag].score=k.score;
for (int i=0;i<=n;i++)
{
printf(“%s”,a[i].name);
printf(“%d”,a[i].score);
}
}
Void main()
{
NODE b[8];
NODE c;
b[0].name=”lili”;
b[0].score=90;
b[1].name=”zhangsan”;
b[1].score=89;
b[2].name=”wangli”;
b[2].score=86;
b[3].name=”zhanglili”;
b[3].score=80;
b[4].name=”panhong”;
b[4].score=70;
c.name=”wangwangwang”;
c.score=85;
Binary_search(b,5,c);
}

实验4 哈夫曼树

构造哈夫曼树，并打印哈夫曼树。
参考答案：教材P116页的程序和运行结果。