数据结构实验指导书Word文件下载.docx
- 文档编号:938498
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:25
- 大小:26.67KB
数据结构实验指导书Word文件下载.docx
《数据结构实验指导书Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验指导书Word文件下载.docx(25页珍藏版)》请在冰点文库上搜索。
if(L->
length==-1)
exit();
{for(j=i+1;
j<
L->
length;
list[j-1]=L->
length--;
实验二、树型结构的遍历
树的遍历是树的算法中最具有典型的,它的特点为递归,树的其它算法如:
求树的高度、求叶子数等,都同该算法同出一辙,另外树的遍历算法应用比较广泛。
编写前序遍历、中序遍历、后序遍历二叉树的程序。
1、掌握二叉树的特点及其存储方式。
2、掌握二叉树的创建和显示方法。
3、掌握二叉树遍历的基本方法:
前序(DLR)、中序(LDR)、后序(LRD)
按下图的二叉树进行操作。
1、按上图建立二叉树,输入方法为:
请输入按先序建立二叉树的结点序列:
说明:
‘0’代表后继结点为空,请逐个输入,按回车键输入下一个结点。
请输入根结点:
a
请输入a结点的左子结点:
b
请输入b结点的左子结点:
d
请输入d结点的左子结点:
0
请输入d结点的右子结点:
请输入b结点的右子结点:
请输入a结点的右子结点:
c
请输入c结点的左子结点:
e
请输入e结点的左子结点:
请输入e结点的右子结点:
请输入c结点的右子结点:
f
请输入f结点的左子结点:
请输入f结点的右子结点:
2、检查前序、中序、后序算法的正确。
例:
该二叉树前序遍历序列为:
abdcef
该二叉树中序遍历序列为:
dbaecf
该二叉树后序遍历序列为:
dbefca
3、遍历算法(递归过程)
(1)前序遍历
若二叉树为空,遍历结束。
否则
A、访问根结点。
B、前序遍历根结点的左子树。
C、前序遍历根结点的右子树。
voidpreorder(BT*T)
{if(T!
=NULL)
{printf(“%c”,T->
data);
preorder(T->
lchild);
rchild);
(2)中序遍历
A、中序遍历根结点的左子树。
B、访问根结点。
C、中序遍历根结点的右子树。
{preorder(T->
printf(“%c”,T->
preorder(T->
(3)后序遍历
若二叉树为空,遍历结束。
A、后序遍历根结点的左子树。
B、后序遍历根结点的右子树。
C、访问根结点
实验三、图型结构算法及应用
图有二个存储结构:
邻接矩阵和邻接表,邻接矩阵的实验可以借鉴于实验一,邻接表的实验类似于单链表,图是最复杂的一种数据结构,掌握它有一定的代表意义。
邻接表表示图,并进行深度优先遍历
了解什么是邻接表,什么是深度优先遍历
1、定义数据类型
#define
MAX_VERTEX_NUM
20
//最大顶点数
#define
MAX_EDGE_NUM
40
//最大边数
int
visited[
MAX_VERTEX_NUM];
typedef
VertexType
;
//顶点数据类型
struct
ArcNode
{
adjvex;
weight;
*nextarc;
}ArcNode;
VNode
data;
*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
AdjList
vertices;
vexnum,arcnum;
kind;
}ALGraph;
2、创建一个图
void
CreateDG(ALGraph
&
G)
i,j,k;
*p;
cout<
<
"
创建一个图:
endl;
顶点数:
;
cin>
>
G.vexnum;
cout<
边数:
G.arcnum;
for(i=0;
i<
i++)
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=0;
k<
k++)
请输入第"
k+1<
条边:
i>
j;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->
adjvex=j;
nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
3、输出图
Disp(ALGraph
G)
i,j;
输出图为:
p=G.vertices[i].firstarc;
j=0;
while(p!
=NULL)
("
"
p->
adjvex<
)"
p=p->
nextarc;
j=1;
if(j==1)
4、图的深度优先遍历
dfs(ALGraph
G,int
v)
//深度优先遍历
v<
"
visited[v]=1;
p=G.vertices[v].firstarc;
{if(!
visited[p->
adjvex])
dfs(G,p->
adjvex);
return
void
dfs1(ALGraph
i;
if(visited[i]==0)
dfs(G,i);
5、主函数
main()
ALGraph
G;
CreateDG(G);
v;
Disp(G);
输入顶点:
v;
深度优先序列:
dfs1(G);
实验四、查找算法应用
查找是日常经常使用的一种操作,掌握各种数据结构的查找算法有十分重要的意义。
通过本次实验掌握顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现。
设有关键字序列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(k<
st[mid].key)
high=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<
bub[mid],high=mid-1;
转2
(2)若key>
bub[mid],low=mid+1;
(3)若key=bub[mid],返回数据元素在表中位置。
实验五、排序算法应用
掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想及实现。
将一组数据(97、49、65、76、49、13、38、27)进行大堆排序
1、只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间
2、掌握堆的概念
什么是堆?
n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时,称之为堆。
关系一:
ki<
=k2i关系二:
=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((j<
m)&
(r[j].key>
r[j1].key))j;
if(x<
=r[j].key)
finished:
=TRUE;
else{r[i]=r[j];
i=j;
r[i]=t;
HeapSort(ListType&
r)
for(i=n/2;
0;
i--)sift(r,i,n);
for(i=n;
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,功能:
查询学生成绩*/
struct*p1,*p2;
printf("
输入要查询的学生的学号,"
);
scanf("
%d"
&
number);
while(number!
=0)
if(head==NULL)
{printf("
\n没有任何学生资料!
\n"
return(head);
-----------------------------------------\n"
|学号\t|姓名\t|语文\t|英语\t|数学\t|\n"
/*打印表格域*/
p1=head;
=p1->
number&
p1->
next!
{p2=p1;
p1=p1->
next;
}
if(number==p1->
number)
|%d\t|%s\t|%.1f\t|%.1f\t|%.1f\t|\n"
p1->
number,p1->
name,p1->
yuwen,p1->
yingyu,p1->
shuxue);
}/*打印表格域*/
%d不存在此学生!
number);
已经退出了!
5、删除学生资料
struct*del2311(struct*head)/*函数del2311,功能:
删除学生资料*/
intnumber;
输入要删除的学生的学号(输入0时退出):
getchar();
=0)/*输入学号为0时退出*/
/*p1指向的不是所要找的首结点,并且后面还有结点*/
p2=p1;
}/*p1后移一个结点*/
/*找到了*/
if(p1==head)
head=p1->
/*若p1指向的是首结点,把地二个结点地址赋予head*/
p2->
next=p1->
/*否则将下一个结点地址赋给前一结点地址*/
删除:
%d\n"
n=n-1;
/*找不到该结点*/
输入要删除的学生的学号:
#ifdefDEBUG
#endif
现在的学生数为:
%d个!
n);
6、定义排序函数
struct*taxis2311(struct*head)
/*定义排序函数。
此函数带回一个指向链表头的指针*/
{struct*p,*max;
inti,j,x;
floatfen;
chart[10];
\n没有任何学生资料,请先建立链表!
}/*链表为空*/
max=p=head;
for(i=0;
80;
i)
*"
1按学生学号排序\t2按学生姓名排序\t3按语文成绩排序\n"
4按英语成绩排序\t5按数学成绩排序\t\n"
请选择操作:
x);
/*选择操作*/
switch(x)/*用switch语句实现功能选择*/
{case1:
for(i=1;
n;
for(j=i1;
j<
=n;
j)
max=p;
p=p->
if(max->
number>
number)
k=max->
number;
max->
number=p->
number=k;
/*交换前后结点中的学号值,使得学号大者移到后面的结点中*/
scpy(t,max->
name);
scpy(max->
name,p->
scpy(p->
name,t);
/*交换前后结点中的姓名,使之与学号相匹配*/
fen=max->
yuwen;
yuwen=p->
yuwen=fen;
/*交换前后结点中的语文成绩,使之与学号相匹配*/
yingyu;
yingyu=p->
yingyu=fen;
/*交换前后结点中的英语成绩,使之与学号相匹配*/
shuxue;
shuxue=p->
shuxue=fen;
/*交换前后结点中的数学成绩,使之与学号相匹配*/
max=head;
p=head;
/*重新使max,p指向链表头*/
print2311(head);
break;
/*打印值排序后的链表内容*/
case2:
for(i=1;
if(scmp(max->
name)>
0)/*scmp=>
字符串比较函数*/
/*scpy=>
字符串复制函数*/
/*交换前后结点中的姓名,使得姓名字符串的值大者移到后面的结点中*/
/*交换前后结点中的学号值,使之与姓名相匹配*/fen=max->
/*交换前后结点中的语文成绩,使之与姓名相匹配*/
/*交换前后结点中的英语成绩,使之与姓名相匹配*/
/*交换前后结点中的数学成绩,使之与姓名相匹配*/
case3:
{for(j=i1;
{max=p;
yuwen>
yuwen)
/*交换前后结点中的语文成绩,使得语文成绩高者移到后面的结点中*/
/*交换前后结点中的学号,使之与语文成绩相匹配*/
scpy
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 指导书