数据结构实验指导书.docx
《数据结构实验指导书.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书.docx（25页珍藏版）》请在冰点文库上搜索。
数据结构实验指导书
实验一、线性结构的插入和删除
实验目的和要求：
掌握线性结构的定义、组织形式、结构特征和类型说明以及在这两种存储方式下实现的插入、删除和按值查找的算法。
循环链表、双（循环）链表的结构特点和在其上施加的插入、删除等操作。
实验内容：
实验题目
1、已知长度为n的线性表,要求将new_data插入到线性表中使之成为第j个元素。
2、已知长度为n的线性表,要求将线性表中第j个位置上的数据元素删除。
实验准备
1、思考怎样实现线性表顺序存储结构中元素的插入。
2、思考怎样实现线性表顺序存储结构中元素的删除。
实验步骤
1、将new_data插到长度为n的线性表中，使之成为第j个元素。
（1）腾位置
将自第n个位置开始至第j个位置上的所有数据元素统统往后移动一个位置。
（2）插入元素
将new_data插入到线性表中第j个位置。
（3）线性表长度增1
顺序表的类型
structseqlist
{datatypelist[max];
intlength;};
voidinsert（structseqlist*L,inti,intnew_data）
{intj;
if（L->length==max）
exit（）;
else
{for（j=L->length-1;j>=i;j++）
L->list[j+1]=L->list[j];
L->list[i]=new_data;
L->length++;}
}
2、将长度为n的线性表中第j个位置上的数据元素删除
（1）移动删除
将自第j+1个位置开始至线性表中最后一个位置的数据元素全部前移一个位置。
（2）线性表长度减1
顺序表的类型
structseqlist
{datatypelist[max];
intlength;};
voiddelete（structseqlist*L,inti,intnew_data）
{intj;
if（L->length==-1）
exit（）;
else
{for（j=i+1;jlength;j++）
L->list[j-1]=L->list[j];
L->length--;}
}
实验二、树型结构的遍历
实验目的和要求：
树的遍历是树的算法中最具有典型的,它的特点为递归,树的其它算法如：
求树的高度、求叶子数等,都同该算法同出一辙,另外树的遍历算法应用比较广泛。
实验内容：
实验题目
编写前序遍历、中序遍历、后序遍历二叉树的程序。
实验准备
1、掌握二叉树的特点及其存储方式。
2、掌握二叉树的创建和显示方法。
3、掌握二叉树遍历的基本方法：
前序（DLR）、中序（LDR）、后序（LRD）
实验步骤
按下图的二叉树进行操作。
1、按上图建立二叉树，输入方法为：
请输入按先序建立二叉树的结点序列：
说明：
‘0’代表后继结点为空，请逐个输入，按回车键输入下一个结点。
请输入根结点：
a
请输入a结点的左子结点:
b
请输入b结点的左子结点:
d
请输入d结点的左子结点:
0
请输入d结点的右子结点:
0
请输入b结点的右子结点:
0
请输入a结点的右子结点:
c
请输入c结点的左子结点:
e
请输入e结点的左子结点:
0
请输入e结点的右子结点:
0
请输入c结点的右子结点:
f
请输入f结点的左子结点:
0
请输入f结点的右子结点:
0
2、检查前序、中序、后序算法的正确。
例：
该二叉树前序遍历序列为：
abdcef
该二叉树中序遍历序列为：
dbaecf
该二叉树后序遍历序列为：
dbefca
3、遍历算法（递归过程）
（1）前序遍历
若二叉树为空，遍历结束。
否则
A、访问根结点。
B、前序遍历根结点的左子树。
C、前序遍历根结点的右子树。
voidpreorder（BT*T）
{if（T!
=NULL）
{printf（“%c”,T->data）;
preorder（T->lchild）;
preorder（T->rchild）;
}
（2）中序遍历
若二叉树为空，遍历结束。
否则
A、中序遍历根结点的左子树。
B、访问根结点。
C、中序遍历根结点的右子树。
voidpreorder（BT*T）
{if（T!
=NULL）
{preorder（T->lchild）;
printf（“%c”,T->data）;
preorder（T->rchild）;
}
（3）后序遍历
若二叉树为空，遍历结束。
否则
A、后序遍历根结点的左子树。
B、后序遍历根结点的右子树。
C、访问根结点
voidpreorder（BT*T）
{if（T!
=NULL）
{preorder（T->lchild）;
preorder（T->rchild）;
printf（“%c”,T->data）;
}
实验三、图型结构算法及应用
实验目的和要求：
图有二个存储结构：
邻接矩阵和邻接表,邻接矩阵的实验可以借鉴于实验一,邻接表的实验类似于单链表,图是最复杂的一种数据结构,掌握它有一定的代表意义。
实验内容：
实验题目
邻接表表示图，并进行深度优先遍历
实验准备
了解什么是邻接表，什么是深度优先遍历
实验步骤
1、定义数据类型
#define MAX_VERTEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
int visited[ MAX_VERTEX_NUM];
typedef int VertexType ; //顶点数据类型
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
2、创建一个图
void CreateDG（ALGraph &G）
{
int i,j,k;
ArcNode *p;
cout<<"创建一个图:
"< cout<<"顶点数:
"; cin>>G.vexnum;cout< cout<<"边数:
"; cin>>G.arcnum; cout< for（i=0;i {
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for（k=0;k {
cout<<"请输入第"<";
cin>>i>>j;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}
3、输出图
void Disp（ALGraph G）
{
int i,j;
ArcNode *p;
cout<<"输出图为:
"< for（i=0;i {
p=G.vertices[i].firstarc;
j=0;
while（p!
=NULL）
{
cout<<"（"<adjvex<<"）";
p=p->nextarc;
j=1;
}
if（j==1）
cout< }
}
4、图的深度优先遍历
void dfs（ALGraph G,int v） //深度优先遍历
{
ArcNode *p;
cout< visited[v]=1;
p=G.vertices[v].firstarc;
while（p!
=NULL）
{if（!
visited[p->adjvex]）
dfs（G,p->adjvex）;
p=p->nextarc;
}
return ;
}
void dfs1（ALGraph G）
{
int i;
for（i=0;i if（visited[i]==0）
dfs（G,i）;
}
5、主函数
void main（）
{
ALGraph G;
CreateDG（G）;
int v;
Disp（G）;
cout<<"输入顶点:
";
cin>>v;
cout<<"深度优先序列:
";
dfs1（G）;
cout< }
实验四、查找算法应用
实验目的和要求：
查找是日常经常使用的一种操作,掌握各种数据结构的查找算法有十分重要的意义。
通过本次实验掌握顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现。
实验内容：
实验题目
设有关键字序列k={5,14,18,21,23,29,31,35}查找key=21的数据元素
实验准备
1、从键盘输入上述8个整数，存放在数组bub[8]中，并输出其值。
2、从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。
2、从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。
3、具体算法
intbinarysearch（structsstablest[n+1],elemtypek）
{intlow=1,high=1;
while（low<=high）
mid=（low+high）/2;
if（k==st[mid].key）
return（mid）;
elseif（khigh=mid-1;
else
low=mid-1;
}
return（0）;
}
实验步骤
1、low=1;high=length;//设初始区间
2、当low>high时，返回查找失败信息；//表空，查找失败
3、low<=high,mid=（low+high）/2//取中点
（1）若key（2）若key>bub[mid],low=mid+1;转2
（3）若key=bub[mid]，返回数据元素在表中位置。
实验五、排序算法应用
实验目的和要求：
掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想及实现。
实验内容：
实验题目
将一组数据（97、49、65、76、49、13、38、27）进行大堆排序
实验准备
1、只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间
2、掌握堆的概念
什么是堆？
n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时，称之为堆。
关系一：
ki<=k2i关系二：
ki<=k2i1（i=1,2,...,n/2）
3、堆排序要解决两个问题：
a、如何由一个无序序列建成一个堆？
b、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
实验步骤
sift（ListType&r,intk,intm）
{
i=k;j=2*i;x=r[k].key;finished=FALSE;
t=r[k];
while（（j<=m）&&（!
finished））
{
if（（jr[j1].key））j;
if（x<=r[j].key）
finished:
=TRUE;
else{r[i]=r[j];i=j;j=2*i;}
}
r[i]=t;
}
HeapSort（ListType&r）
{
for（i=n/2;i>0;i--）sift（r,i,n）;
for（i=n;i>1;i--）{
r[1]<->r[i];
sift（r,i,i-1）
}
}
实验六、设计学生成绩管理系统
实验目的和要求：
这是一个综合性、设计性实验，是为了让大家将前面所学的知识点进行概括和总结，并能够解决实际的应用问题。
实验内容：
实验题目
利用前面所学到的知识设计出学生成绩管理系统合适的数据结构，并编程实现增加记录、删除记录、查找和排序功能。
实验准备
先复习链表结构、c语言的各种数据类型及操作语言的用法。
熟练查找和排序的多种算法。
实验步骤
1、定义学生成绩的数据结构
structnode
{intnumber;/*学号*/
charname[10];/*姓名*/
floatyuwen;/*语文成绩*/
floatyingyu;/*英语成绩*/
floatshuxue;/*数学成绩*/
structnode*next;
};
2、创建链表
3、增加学生资料,并且将所有学生资料按学号排序
4、查询学生成绩
struct*search2311（struct*head）
/*函数search2311,功能：
查询学生成绩*/
{intnumber;
struct*p1,*p2;
printf（"输入要查询的学生的学号,"）;
scanf（"%d",&number）;
while（number!
=0）
{
if（head==NULL）
{printf（"\n没有任何学生资料!
\n"）;return（head）;}
printf（"-----------------------------------------\n"）;
printf（"|学号\t|姓名\t|语文\t|英语\t|数学\t|\n"）;
printf（"-----------------------------------------\n"）;/*打印表格域*/
p1=head;
while（number!
=p1->number&&p1->next!
=NULL）
{p2=p1;p1=p1->next;}
if（number==p1->number）
{printf（"|%d\t|%s\t|%.1f\t|%.1f\t|%.1f\t|\n",p1->number,p1->name,p1->yuwen,p1->yingyu,p1->shuxue）;
printf（"-----------------------------------------\n"）;}/*打印表格域*/
else
printf（"%d不存在此学生!
\n",number）;
printf（"输入要查询的学生的学号,"）;
scanf（"%d",&number）;
}
printf（"已经退出了!
\n"）;
return（head）;}
5、删除学生资料
struct*del2311（struct*head）/*函数del2311，功能：
删除学生资料*/
{
struct*p1,*p2;
intnumber;
printf（"输入要删除的学生的学号（输入0时退出）:
"）;
scanf（"%d",&number）;
getchar（）;
while（number!
=0）/*输入学号为0时退出*/
{
if（head==NULL）
{
printf（"\n没有任何学生资料!
\n"）;
return（head）;
}
p1=head;
while（number!
=p1->number&&p1->next!
=NULL）
/*p1指向的不是所要找的首结点，并且后面还有结点*/
{
p2=p1;p1=p1->next;
}/*p1后移一个结点*/
if（number==p1->number）
/*找到了*/
{
if（p1==head）
head=p1->next;
/*若p1指向的是首结点，把地二个结点地址赋予head*/
else
p2->next=p1->next;
/*否则将下一个结点地址赋给前一结点地址*/
printf（"删除:
%d\n",number）;n=n-1;
}
else
printf（"%d不存在此学生!
\n",number）;
/*找不到该结点*/
printf（"输入要删除的学生的学号:
"）;
scanf（"%d",&number）;
getchar（）;
}
#ifdefDEBUG
printf（"已经退出了!
\n"）;
#endif
printf（"现在的学生数为:
%d个!
\n",n）;
return（head）;
}
6、定义排序函数
struct*taxis2311（struct*head）
/*定义排序函数。
此函数带回一个指向链表头的指针*/
{struct*p,*max;
inti,j,x;
floatfen;
chart[10];
if（head==NULL）
{printf（"\n没有任何学生资料，请先建立链表!
\n"）;return（head）;}/*链表为空*/
max=p=head;
for（i=0;i<80;i）
printf（"*"）;
printf（"1按学生学号排序\t2按学生姓名排序\t3按语文成绩排序\n"）;
printf（"4按英语成绩排序\t5按数学成绩排序\t\n"）;
for（i=0;i<80;i）
printf（"*"）;
printf（"请选择操作:
"）;
scanf（"%d",&x）;/*选择操作*/
getchar（）;
switch（x）/*用switch语句实现功能选择*/
{case1:
for（i=1;i{
for（j=i1;j<=n;j）
{
max=p;
p=p->next;
if（max->number>p->number）
{
k=max->number;
max->number=p->number;
p->number=k;
/*交换前后结点中的学号值，使得学号大者移到后面的结点中*/
scpy（t,max->name）;
scpy（max->name,p->name）;
scpy（p->name,t）;
/*交换前后结点中的姓名，使之与学号相匹配*/
fen=max->yuwen;
max->yuwen=p->yuwen;
p->yuwen=fen;
/*交换前后结点中的语文成绩，使之与学号相匹配*/
fen=max->yingyu;
max->yingyu=p->yingyu;
p->yingyu=fen;
/*交换前后结点中的英语成绩，使之与学号相匹配*/
fen=max->shuxue;
max->shuxue=p->shuxue;
p->shuxue=fen;
/*交换前后结点中的数学成绩，使之与学号相匹配*/
}
}
max=head;p=head;/*重新使max,p指向链表头*/
}
print2311（head）;break;/*打印值排序后的链表内容*/
case2:
for（i=1;i{
for（j=i1;j<=n;j）
{
max=p;
p=p->next;
if（scmp（max->name,p->name）>0）/*scmp=>字符串比较函数*/
{
scpy（t,max->name）;/*scpy=>字符串复制函数*/
scpy（max->name,p->name）;
scpy（p->name,t）;
/*交换前后结点中的姓名，使得姓名字符串的值大者移到后面的结点中*/
k=max->number;
max->number=p->number;
p->number=k;
/*交换前后结点中的学号值，使之与姓名相匹配*/fen=max->yuwen;
max->yuwen=p->yuwen;
p->yuwen=fen;
/*交换前后结点中的语文成绩，使之与姓名相匹配*/
fen=max->yingyu;
max->yingyu=p->yingyu;
p->yingyu=fen;
/*交换前后结点中的英语成绩，使之与姓名相匹配*/
fen=max->shuxue;
max->shuxue=p->shuxue;
p->shuxue=fen;
/*交换前后结点中的数学成绩，使之与姓名相匹配*/
}
}
p=head;
max=head;
}
print2311（head）;
break;
case3:
for（i=1;i{for（j=i1;j<=n;j）
{max=p;
p=p->next;
if（max->yuwen>p->yuwen）
{
fen=max->yuwen;
max->yuwen=p->yuwen;
p->yuwen=fen;
/*交换前后结点中的语文成绩，使得语文成绩高者移到后面的结点中*/
k=max->number;
max->number=p->number;
p->number=k;
/*交换前后结点中的学号，使之与语文成绩相匹配*/
scpy（t,max->name）;
scpy（max->name,p->name）;
scpy
升级会员 