中央电大本科数据结构实验报告
实验名称:实验一 线性表
线性表的链式存储结构
【问题描述】
某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序:
(1) 显示在评分中给出最高分和最低分的评委的有关信息(姓名、年龄、所给分数等)。
(2) 在链表中删除一个最高分和一个最低分的结点。 (3) 计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
【基本要求】
(1) 建立一个评委打分的单向链表;
(2) 显示删除相关结点后的链表信息。
(3) 显示要求的结果。
【实验步骤】
(1) 运行PC中的Microsoft Visual C++ 6.0程序， (2) 点击“文件”?“新建” ?对话窗口中“文件” ?“c++ Source File” ?在“文件名”中输入“X1.cpp”
?在“位置”中选择储存路径为“桌面” ?“确定”， (3) 输入程序代码，
程序代码如下:
#include
#include #include #include #include
#define NULL 0
#define PWRS 5 //定义评委人数
struct pw //定义评委信息
{ char name[6];
float score;
int age;
};
typedef struct pw PW; struct node //定义链表结点
{struct pw data;
struct node * next; };
typedef struct node NODE; NODE *create(int m); //创建单链表
int calc(NODE *h); //计算、数据处理
void print(NODE *h); //输出所有评委打分数据 void input(NODE *s);//输入评委打分数据
void output(NODE *s);//输出评委打分数据 void main()
{
NODE *head;
float ave=0;
float sum=0;
head=create(PWRS);
printf("所有评委打分信息如下:\n");
print(head);//显示当前评委打分
calc(head);//计算成绩
printf("该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n");
print(head);//显示去掉极限分后的评委打分
}
void input(NODE *s)
{
printf("请输入评委的姓名: ");
scanf("%S",&s->data.name);
printf("年龄: ");
scanf("%d",&s->data.age);
printf("打分: ");
scanf("%f",&s->data.score);
printf("\n");
}
void output(NODE *s)
{
printf("评委姓名: %8s ,年龄: %d,打分: %2.2f\n",s->data.name,s->data.age,s->data.score);
}
NODE *create(int m)
{
NODE *head,*p,*q;
int i;
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);
}
void print(NODE *h)
{ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){
h=h->next;
output(h); }
printf("\n");
}
int calc(NODE *h)
{
NODE *q,*p,*pmin,*pmax;
float sum=0;
float ave=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.scoredata.score) pmin=p;
sum+=p->data.score;
}
cout<<"给出最高分的评委姓名:"<data.name<<"年龄: "<data.age<<"分值:
"<data.score<data.name<<"年龄: "<data.age<<"分值:
"<data.score<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<<"该选手的最后得分是:"< #include #include #include #include #include //包含库函数strcpy的头文件
#define NULL 0
struct student //定义学生信息
{ char name[8];
int sex; //0 女: 1:男
int age;
};
typedef struct student STD;
int create(STD *m); //创建顺序表
int calc(STD *m,STD *n,STD *r,float &Fage,float &Mage); //计算、数据处理
void print(STD *m); const int MAX=100; //定义人数
void main()
{
STD A[MAX];
STD B[MAX];
STD C[MAX];
float age1=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);
}
int create(STD *m) {
int n;
printf ("请输入班级总人数:\n ");
scanf ("%d",&n);
m[0].age=n; //置顺序表 长度
printf("请输入学生信息:\n");
for(int i=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");
}
return 1;
}
int calc(STD *m,STD *n,STD *r,float &Fage,float &Mage)
{ int i,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<<"女生的平均年龄是:"<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中的Microsoft Visual C++ 6.0程序， (5) 点击“文件”?“新建” ?对话窗口中“文件” ?“c++ Source File” ?在“文件名”中输入“X1.cpp”
?在“位置”中选择储存路径为“桌面” ?“确定”， (6) 输入程序代码，
程序代码如下:
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈顶指针
} SeqStack;//定义栈
typedef struct
{
ElemType elem[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;//定义队列
//---初始栈函数
void InitStack(SeqStack *&s) {
s=(SeqStack *)malloc(sizeof(SeqStack));
s->top=-1;
}
//----进栈函数
int Push(SeqStack *&s,ElemType e) {
if (s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
//---显示栈函数
void DispStack(SeqStack *s) {
int i;
for (i=s->top;i>=0;i--)
printf("%c ",s->data[i]);
printf("\n");
}
//---显示栈底元素
void DispBottomStack(SeqStack *s)
{
printf("%c ",s->data[0]);//先进后出,栈底元素为第一个元素,即data[0]
printf("\n");
}
//---判空栈函数
int StackEmpty(SeqStack *s) {
return(s->top==-1);
}
//---出栈函数
int Pop(SeqStack *&s,ElemType &e)
{
if (s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
//---初始队列函数
void InitQueue(SqQueue *&q) {
q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
//---入队列函数
int InQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) //队满
return 0;
q->rear=(q->rear+1)%MaxSize;
q->elem[q->rear]=e;
return 1;
}
//---出队列函数
int OutQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) //队空
return 0;
q->front=(q->front+1)%MaxSize;
e=q->elem[q->front];
return 1;
}
//---判空队列函数
int QueueEmpty(SqQueue *q) {
return(q->front==q->rear); }
//-----主程序
void main()
{
ElemType e;
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中的Microsoft Visual C++ 6.0程序， 点击“文件”?“新建” ?对话窗口中“文件” ?“c++ Source File” ?在“文件名”中(2)输入“X1.cpp”
?在“位置”中选择储存路径为“桌面” ?“确定”，
(3) 输入程序代码
程序代码如下:
#include #include void out(int n,int i)//从高位到低位输出函数 {
int x,y;
y=int(pow(10,i)); if (n!=0)
{
x=n/y;
n=n-x*y;
printf("%d ",x); }
else printf("0 "); i--;
if(i>=0) out(n,i); }
void out1(int m,int j)//从低位到高位输出函数 {
int x,z;
if (m!=0)
{
x=int(m/10);
z=m-x*10;
m=x;
printf("%d ",z); }
else printf("0 "); j--;
if(j>=0) out1(m,j); }
void main()
{
int m,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中的Microsoft Visual C++ 6.0程序， (8) 点击“文件”?“新建” ?对话窗口中“文件” ?“c++ Source File” ?在“文件名”中输入“X1.cpp”
?在“位置”中选择储存路径为“桌面” ?“确定”， (9) 输入程序代码，
程序代码如下:
#include
#include
#include
#include
#include
#define MaxSize 10
typedef struct node
{
char data;
struct node *left,*right; }NODE;
void Creab(char *tree,int n,int i,NODE *p);
void Inorder(NODE *p);
void main()
{
NODE *p;
char tree[MaxSize];
int n=1;
int i=1;
printf("请输入完全二叉数的节点值(连续输入字符，以回车结束输入。):");
while((tree[n] = getchar( )) != '\n') n++;
tree[n] ='\n';
p=NULL;
Creab(tree,n,i,p);
Inorder(p);
}
void Creab(char *tree,int n,int i,NODE *p)
{
if(i>=n) p=NULL;
else
{
p=(NODE *)malloc(sizeof(NODE));
p->data=tree[i];
printf("%c ",p->data );
Creab(tree,n,2*i,p->left);
Creab(tree,n,2*i+1,p->right);
}
}
/*中序遍历树*/
void Inorder(NODE *p)
{
if(p!=NULL) {
Inorder(p->left);
printf("%c ",p->data);
Inorder(p->right);
}
}
程序运行结果如下:
3.1 二叉树的遍历
【问题描述】
设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。 【基本要求】
(1) 掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。 (2) 能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。 【实验步骤】
(1)运行PC中的Microsoft Visual C++ 6.0程序，
点击“文件”?“新建” ?对话窗口中“文件” ?“c++ Source File” ?在“文件名”中(2)输入“X1.cpp”
?在“位置”中选择储存路径为“桌面” ?“确定”， (3) 输入程序代码
程序代码如下:
void FirstOrderAccess1(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c“t",p->order,p->data);
if(p->rchild!=NULL)
stack[++top] = p->rchild;
p = p->lchild;
}
if(top!=0)
p = stack[top--];
}while((top>0)||(p!=NULL)); }
实验名称:实验四 图的存储方式和应用
4.1建立图的邻接矩阵
【问题描述】
根据图中顶点和边的信息编制程序建立图的邻接矩阵。
【基本要求】
(4) 程序要有一定的通用性。
(5) 直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵
【测试用例】
【实现提示】
(1) 对图的顶点编号。
(2) 在上图中，以顶点1为例，因为顶点2,3,4与顶点1关联，可以输入信息1 2 3 4，然后设法求出与顶
点1关联的结点，从而求得邻接矩阵中相应与顶点1的矩阵元素。
2
1
5
3
4
实验 图4-1
, 设计程序代码如下:
#include
#define MaxVertexNum 5
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int VertexType;
typedef VertexType vexlist [MaxVertexNum];
typedef int adjmatrix [MaxVertexNum] [MaxVertexNum];
void Createl(vexlist Gv,adjmatrix GA,int n,int e)
{
int i,j,k,w;
%d个顶点数据\n",n); printf("输入
for(i=0;i #include #define N 5
struct student{
char name[10];
float avg;
}
void insort(struct student s[],int n)
{
int low,hight,mid,k;
char y[10];
float x;
low=1;
hight=n;
strcpy(y,s[0].name );
x=s[0].avg ;
while(low<=hight)
{
mid=(low+hight)/2;
if(x>s[mid].avg )
hight=mid-1;
else
low=mid+1;
}
for(k=0;k
#include
#define MAX 5
typedef struct Bnode
{
int key;
struct Bnode *left;
struct Bnode *right; }Bnode;
Bnode * btInsert(int x,Bnode *root);
void Inorder(Bnode *root); void main()
{
int i;
int a[MAX]={60,40,70,20,80};
Bnode * root=NULL;
printf("按关键字序列建立二叉排序树\n");
for(i=0;ikey=x;
p->right=p->left=NULL;
if(root==NULL)
{ root=p; return p; }
q=root;
while(flag==0)
{
if(q->key>x)
{
if(q->left!=NULL)
q=q->left;
else
{
q->left=p;
flag=1;
}
}
else
{
if(q->right!=NULL)
q=q->right;
else
{
q->right=p;
flag=1;
}
}
}
return root;
}
void Inorder(Bnode *root)
{
if(root!=NULL) {
Inorder(root->left);
printf("%d ",root->key);
Inorder(root->right);
}
}
, 程序运行结果如下:
实验名称:实验六 排序
6.1 泡沫法排序的改进算法
【问题描述】
某班学生成绩信息表中每个学生的记录包括各门功课的成绩和平均成绩，以及按平均成绩的排名等信息，
要求从键盘输入每个学生各门功课的成绩，计算出平均成绩，按平均成绩由高到低对信息的记录重新排序，
并定出每位同学的名次，打印排序后的信息表。
【基本要求】
(9) 建立学生成绩信息表，计算平均成绩。
(10) 用泡沫法对平均成绩排序，程序中要求一旦序列被排好序就结束相应排序操作。 【测试数据】
自行设计
实验提示】 【
(1) 用结构数组存放学生成绩信息表。
(2) 在某趟泡沫中没有发生元素间的交换则说明已排好序
6.2 堆排序
【问题描述】
阅读筛选和建堆的程序，针对某一个待排序的序列，通过人工跟踪程序的执行，完成排序的全过程
【基本要求】
(1) 掌握建堆、筛选的基本原理和算法步骤。
(2) 写出主函数，试运行堆排序的程序。
(3) 掌握堆排序的算法程序，能针对实例按步骤人工完成建堆和排序的过程。 【测试数据】
自行设计。
【实验提示】
(1) 筛选是建堆的基本算法。
(2) 把要排序序列看成一棵完全二叉树，用循环方式从最后一个非叶结(设序号为k)开始，逐次对序
号为k, k-1, … 的结点，直至根结点调用筛选算法，完成建堆。 (3) 不断通过堆顶元素与堆中最后一个元素的交换并筛选，完成排序。 实验报告内容:
实验6.1 冒泡法排序的改进
, 设计程序代码如下:
#include
#include
#define MAX 3
struct student{
char name[10];
float cs;
float ms;
float es;
float avg;
};
void sort(struct student s[],int n);
void sort(struct student s[],int n)
{
struct student temp;
int i,j;
for(i=1; i
#define N 8
struct NODE
{
int date;
};
void heapshift(struct NODE a[],int i,int n)
{
struct NODE temp;
int j;
temp=a[i];
j=2*i;
while(ja[j+1].date )
j++;
if(temp.date >a[j].date )
{
a[i]=a[j];
i=j;
j=2*i;
}
else
break;
}
a[i]=temp;
}
void heapsort(struct NODE a[],int n)
{
int i;
struct NODE temp;
for(i=n/2;i>=1;i--)
heapshift(a,i,n);
for(i=n;i>1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
heapshift(a,1,i-1);
}
}
void main()
{
struct NODE b[N]={40,80,65,100,14,30,55,50};
struct NODE a[N];
int i;
printf("初始数据序列:");
for(i=0;i
本文档为【中央电大本科数据结构实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483