数 据 结 构 实 验 指 导 书Word格式.docx
《数 据 结 构 实 验 指 导 书Word格式.docx》由会员分享，可在线阅读，更多相关《数 据 结 构 实 验 指 导 书Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
//指针域
}linklist;
注意结点的建立方法及构造新结点时指针的变化。
构造一个结点需用到C语言的标准函数malloc（），如给指针变量p分配一个结点的地址：
p=（linklist*）malloc（sizeof（linklist））;
该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p中。
当结点不需要时可以用标准函数free（p）释放结点存储空间，这时p为空值（NULL）。
五、思考与提高
1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。
2.在main函数里如果去掉L=&
a语句，会出现什么结果？
实验二栈和队列
1.掌握栈的顺序表示和实现
2.掌握队列的链式表示和实现
1.编写一个程序实现顺序栈的各种基本运算。
2.实现队列的链式表示和实现。
1.初始化顺序栈
2.插入元素
3.删除栈顶元素
4.取栈顶元素
5.遍历顺序栈
6.置空顺序栈
7.初始化并建立链队列
8.入链队列
9.出链队列
10.遍历链队列
1./*定义顺序栈的存储结构*/
typedefstruct{
ElemTypestack[MAXNUM];
inttop;
}SqStack;
/*初始化顺序栈函数*/
voidInitStack（SqStack*p）
{q=（SqStack*）malloc（sizeof（SqStack）/*申请空间*/）
/*入栈函数*/
voidPush（SqStack*p,ElemTypex）
{if（p->
top<
MAXNUM-1）
{p->
top=p->
top+1;
/*栈顶+1*/
p->
stack[p->
top]=x;
}
/*数据入栈*/
}
/*出栈函数*/
ElemTypePop（SqStack*p）
{x=p->
top];
/*将栈顶元素赋给x*/
top-1;
}/*栈顶-1*/
/*获取栈顶元素函数*/
ElemTypeGetTop（SqStack*p）
{x=p->
/*遍历顺序栈函数*/
voidOutStack（SqStack*p）
{for（i=p->
top;
i>
=0;
i--）
printf（"
第%d个数据元素是：
%6d\n"
i,p->
stack[i]）;
/*置空顺序栈函数*/
voidsetEmpty（SqStack*p）
{p->
top=-1;
2./*定义链队列*/
typedefstructQnode
{
ElemTypedata;
structQnode*next;
}Qnodetype;
Qnodetype*front;
Qnodetype*rear;
}Lqueue;
/*初始化并建立链队列函数*/
voidcreat（Lqueue*q）
h=（Qnodetype*）malloc（sizeof（Qnodetype））;
/*初始化申请空间*/
h->
next=NULL;
q->
front=h;
rear=h;
for（i=1;
i<
=n;
i++）*利用循环快速输入数据*/
{
scanf（"
%d"
&
x）;
Lappend（q,x）;
}
/*利用入链队列函数快速输入数据*/
/*入链队列函数*/
voidLappend（Lqueue*q,intx）
{s->
data=x;
s->
rear->
next=s;
rear=s;
/*出链队列函数*/
ElemTypeLdelete（Lqueue*q）
{p=q->
front->
next;
next=p->
if（p->
next==NULL）
rear=q->
front;
x=p->
data;
free（p）;
}/*释放空间*/
/*遍历链队列函数*/
voiddisplay（Lqueue*q）
{while（p!
=NULL）
/*利用条件判断是否到队尾*/
printf（"
%d-->
"
p->
data）;
p=p->
}
1.读栈顶元素的算法与退栈顶元素的算法有何区别？
2.如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。
若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。
如何解决这个问题？
（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？
（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。
即双向栈共享邻接空间。
如果一个程序中要用到两个队列，能否实现？
如何实现？
实验三数组和广义表
1.掌握稀疏矩阵的压缩存储
2.掌握稀疏矩阵的转置算法
1.实现上三角阵的压缩存储。
2.用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。
1.创建一个数组。
2.输入数据
3.给定矩阵任一元素的下标，
4.打印给定下标所对应的数据。
5.创建三元组顺序表。
6.输入矩阵中的数据。
7.输出对应的矩阵。
1.对于如下对称矩阵：
将它们存入到一个线性数组中B，不存非零元素，a11存入到第1个位置，a21存入到第二个位置，则aij能存到第几个位置，我们要以用梯形公式算面积。
aij的位置是它上面的元素之和再加上左边的元素之和。
它上面的元素之和为（（1+（i-1））×
（i-1）/2，左边的元素为（j-1）
所以这个元素存储的位置为k=i（i-1）/2+j-1。
因为矩阵A为对称矩阵，（另一部分没有写出），所以另一部分的元素为
k=j（j-1）/2+i-1.
所以存在关系k=i（i-1）/2+j-1（i>
j）
和k=j（j-1）/2+i-1（i<
j）
2.结点结构
structtriple{
inti,j;
//非零元的行下标和列下标
elemtypee;
//非零元数据}
三元组顺序表存储类型
structtsmatrix{
tripledata[12500];
intmu,nu,tu;
三元顺序表的转置
方法：
（1）将矩阵行列互换，
（2）重排矩阵
1.如何存储三对角阵？
2.如何用行逻辑链接顺序表及十字链表存储稀疏矩阵？
实验四树及二叉树
1.通过实验，掌握二叉树的建立与存储
2.通过实验，掌握二叉树的遍历方法
1.练习二叉树的建立与存储
2.练习二叉树的遍历
1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。
2.建立二叉树,并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果。
建立二叉树的代码如下：
BTCHINALR
*createbt（）
BTCHINALR*q;
structnode1*s[30];
intj,i,x;
建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n"
）;
i,x="
%d,%c"
i,&
while（i!
=0&
&
x!
='
$'
）
{q=（BTCHINALR*）malloc（sizeof（BTCHINALR））;
/*建立一个新结点q*/
data=x;
lchild=NULL;
rchild=NULL;
s[i]=q;
/*q新结点地址存入s指针数组中*/
if（i!
=1）
/*i=1，对应的结点是根结点*/
{j=i/2;
/*求双亲结点的编号j*/
if（i%2==0）s[j]->
lchild=q;
/*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->
rchild=q;
/*q结点编号为奇数则挂在双亲结点j的右边*/
return
s[1];
/*返回根结点地址*/
1.如何用孩子兄弟表示法存储树？
2.熟悉并掌握赫夫曼树。
实验五图
1.掌握图的基本存储方法；
2.掌握有关图的操作算法并用高级语言实现；
3.熟练掌握图的两种搜索路径的遍历方法。
假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
1.定义结点结构，定义图结构。
2.存储图信息；
3.定义求任意两点最短路径函数；
4.写出主函数。
struct
node
no;
float
wgt;
node
*next;
}edgenode;
struct
char
vtx;
edgenode
*link;
}vexnode;
typedef
vexnode
Graph[n];
void
Floyd（GraphG,floatA[n][n],intp[n][n]）
{
i,
j,
k;
for
（i=0;
i<
n;
i++）
for（j=0;
j<
j++）
{
A[i][j]=G[i][j];
P[i][j]=-1;
}
（k=0;
k<
k++）
for（i=0;
for（j=0;
j<
j++）
if（A[i][k]+A[k][j]<
A[i][j]）
P[i][j]=k;
A[i][j]=A[i][k]+A[k][j];
1.判断两点是否可达。
2.如何对程序进行修改，找一条人最少的公交线路？
3.练习图的拓扑排序
实验六查找
1.掌握查找的不同方法，并能用高级语言实现查找算法；
2.熟练掌握二叉排序树的构造和查找方法。
3.了解静态查找表及哈希表查找方法。
设计一个算法读入一串整数，然后构造二叉排序树，进行查找。
1.从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。
2.在二叉排序树中查找某一结点。
3.用其它查找算法进行排序（课后自己做）。
1.定义结构
{int
key;
other;
struct
*lchild,*rchild;
}bstnode;
inorder（t）
{if
（t!
=Null）
{inorder（t→lchild）;
printf（“%4d”,t→key）;
inorder（t→rchild）;
}}
bstnode
*insertbst（t,s）
*s,
*t;
{bstnode
*f,
*p;
p=t;
while（p!
{f=p;
if（s→key==p→key）
t;
if（s→key<
p→key）
p=p→lchild;
else
p=p→rchild;
}
if（t==Null）
s;
f→key）
f→lchild=s;
f→rchild=s;
return
*creatord（
）
*t,*s;
t=Null;
scanf（“%d”,&
key）;
while（key!
=0）
{s=malloc（sizeof（bitree））;
s→key=key;
s→lchild=Null;
s→rchild=Null;
scanf（“%d”,&
s→other=data;
t=insertbst（t,s）;
1.用其它的查找方法完成该算法。
2.比较各种算法的时间及空间复杂度。
实验七排序
1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
3.了解各种方法的排序过程及其时间复杂度的分析方法。
统计成绩
给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
（2）按名次列出每个学生的姓名与分数。
1.定义结构体。
2.定义结构体数组。
3.定出主程序，对数据进行排序。
#define
n
30
student
{charname[8];
score;
student
R[n];
main（
num,
max,
temp;
printf（“\n请输入学生成绩:
\n”）;
{printf（“姓名:
”）;
scanf（“%s”,&
stu[i].name）;
scanf（“%4d”,&
stu[i].score）;
num=1;
{max=i;
for（j=i+1;
if（R[j].score>
R[max].score）
max=j;
if
（max!
=i）
temp=R[max];
R[max]=R[i];
R[i]=temp;
if（（i>
0）&
（R[i].score<
R[i-1].score））
num=num+1;
printf（“%4d%s%4d”,num,R[i].name,R[i].score）;
1.快速排序算法解决本问题。
2.较各种排序算法的优缺点及。
3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。
升级会员 