《数据结构》实验教学大纲文档格式.docx
《《数据结构》实验教学大纲文档格式.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验教学大纲文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
顺序与链式的进栈，出栈
队列的基本运算
顺序与链式的入队，出队
5
串基本操作
串的运算与模式匹配
6
数组
三元组的转置
7
二叉树基本算法
二叉树的遍历
8
图的存储及遍历
图的邻接矩阵和邻接表存储
9
查找
顺序查找、折半查找、分块查找
10
排序算法
插入、选择、冒泡等排序
希尔排序、快速排序
实验一顺序表的基本算法
（一）实验目的
1.理解和掌握顺序表的结构类型定义方法；
2.掌握建立、显示、插入、删除、查找、拆分、合并顺序表的基本方法。
（二）基本知识与预习
1.C程序编辑、编译和运行的过程；
2.结构类型定义方法和成员的引用。
（三）实验环境
安装DEVC++的计算机
（四）实验内容
1.理解和掌握顺序表的结构类型定义方法及应用
/*插入算法描述
（一）*/
voidInsert（SqlistV,inti,Datatypex）
{intj;
if（i<
1||i>
V.last）printf（"
infeasibleposition!
\n"
）;
else{if（V.last+1>
maxsize）printf（"
overflow!
\n"
else{for（j=V.last;
j>
=i;
j--）
V.elem[j+1]=V.elem[j];
V.elem[i]=x;
V.last++;
}
}
/*删除算法描述
（一）*/
voidDelete（SqlistV,inti）
1||i>
infeasible\n"
else{for（j=i;
j<
V.last;
j++）
V.elem[j]=V.elem[j+1];
V.last--;
1.掌握建立、显示、插入、删除、查找、拆分、合并顺序表的多种实现方法。
/*插入算法描述
（二）*/
intsq_insert（list,p_n,i,x）
intlist[],x,i,*p_n;
{intj;
if（i<
0||i>
*p_n）return
（1）;
if（*p_n==maxsize）return
（2）;
for（j=*p_n;
j>
i;
j--）
list[j]=list[j-1];
list[i]=x;
（*p_n）++;
return（0）;
/*删除算法描述
（二）*/
intsq_delete（list,p_n,i）
intlist[],*p_n,i;
=*p_n）return
（1）;
for（j=i+1;
j<
*p_n;
j++）
list[j-1]=list[j];
（*p_n）--;
return（0）;
实验二链表的基本运算
1.理解和掌握链表的结构类型定义方法；
2.掌握建立、显示、插入、删除、查找、拆分、合并链表的基本方法。
1.指针的定义和使用；
2.开辟和释放存储空间的函数及其使用；
3.单链表的建立和删除。
1．单链表的插入算法。
/*算法描述*/
voidInsetLList（LlistL,inti,Datatypex）
{Llistp,s;
intj=0;
p=L;
while（p!
=NULL&
&
i-1）{p=p->
next;
j++;
if（p==NULL||j>
i-1）printf（“Nothisposition!
\n”）;
else{s=（Llist）malloc（sizeof（Node））;
s->
data=x;
next=p->
p->
next=s;
2．单链表的删除算法。
/*算法描述2.3*/
voidDelete（LListL,inti）
{LListp,q;
p=L;
while（p!
if（p==NULL||j>
i-1）printf（"
Nothisdata!
else{q=p->
next=p->
next->
free（q）;
实验三栈的基本运算
1.掌握顺序栈和链式栈的类型定义方法。
2.掌握在顺序栈和链式栈上实现的基本算法。
1.栈的定义及基本术语；
2.栈的基本运算。
1．进栈算法
/*入栈算法*/
intpush（intx）
{if（top>
=MAXN）
return1；
stack[top]=x;
top++;
return0;
2．出栈算法
/*出栈算法*/
Intpop（int*p_y）
{if（top==0）
top--;
*p_y=stack[top];
实验四队列的基本运算
1.掌握顺序队列和链式队列的类型定义方法。
2.掌握在顺序队列和链式队列上实现的基本算法。
1.队列的定义及基本术语
2.队列的基本运算
1.进队列算法
/*入队算法*/
inten_queue（charx）
{if（tail==MAXN-1）
q[++tail]=x;
2.出队列算法
/*出队算法*/
Intde_queue（char*p_y）
{if（head==tail）
*p_y=q[++head];
实验五串基本操作演示系统
1.掌握串的表示和实现；
2.掌握串的基本算法；
3.对比两种模式匹配算法，分析各算法的时、空性能；
4.综合设计和实现串的替换算法。
1.掌握串的定义和表示方法；
2.掌握串的基本运算。
1.通过两个例题理解串函数的功能
例1：
s=′good′,t=′Iamastudent′,
1）strcat（s,t）
2）strsub（t,8,7）
3）strlen（t）
4）strstr（t,′a′）
5）strins（t,8,s）
例2：
a=′IAMASTUDENT′
b=′GOOD′
c=′MORNING′
d=′STU′e=′A′
1）strcat（b,c）,strcat（b,a）
2）strsub（a,6,9）
3）strstr（a,d）,strstr（a,e）,strstr（c,e）
4）s=strsub（a,1,7）,t=strsub（a,8,8）,
strcat（s,b）,strcat（s,t）
2.匹配算法实现：
intindex（chart[],charp[],intm,intn）
{intI,j,k;
for（i=0;
i<
=n-m;
i++）
{for（j=0,k=I;
m&
t[k]==p[j];
k++,j++）;
if（j==m）return（i）;
return（-1）;
实验六数组
1.掌握数组的表示和实现；
2.掌握特殊矩阵的压缩存储；
3.掌握广义表的定义和基本运算。
1.数据的定义和表示方法；
2.结构数组的定义和引用；
3.广义表的定义和基本运算。
1.稀疏矩阵的压缩存储---三元组顺序表的实现。
2.稀疏矩阵的转置运算。
3.广义表的的基本运算。
实验七二叉树基本算法
1.综合设计和实现二叉树的创建、遍历、求高度、统计结点数目等基本算法，掌握树结构的处理方法；
2.了解哈夫曼特性，验证哈夫曼算法。
1.掌握二叉树的定义及基本术语；
2.掌握二叉树的创建、遍历、求高度、统计结点数目等基本算法。
（四）实验内容
1.二叉树的先序遍历算法
voidpreorder（JD*bt）
{if（bt!
=NULL）
{printf（"
%d\t"
bt->
data）;
preorder（bt->
lchild）;
rchild）;
}
2.二叉树的中序遍历算法
voidmidorder（JD*bt）
{midorder（bt->
printf（"
midorder（bt->
3.二叉树的后序遍历算法
voidposorder（JD*bt）
{posorder（bt->
posorder（bt->
printf（"
实验八图的存储及遍历
1.熟悉图的常用存储结构和基本操作，分别用邻接矩阵和邻接表实现以下操作：
图的创建、遍历、插入、删除；
2.综合设计和实现图的最短路径算法，理解图的具体应用。
1.掌握图的定义、基本术语及存储方式；
2.掌握图的创建、遍历等基本算法。
1.分别用邻接矩阵和邻接表实现图的创建、遍历；
2.实现图的最短路径算法，理解图的具体应用。
实验九查找
1.分别实现顺序查找、折半查找、分块查找的算法；
2.掌握常用查找算法的特点，以便根据实际情况选择使用。
1.对比顺序查找、折半查找、分块查找的思想和算法。
2.掌握常用查找算法的特点
1.顺序查找的算法
intfun（inta[],intn,intx）
{
inti;
for（i=0;
n;
该点是%d\n"
a[i]）;
if（a[i]==x）{puts（"
找到\n"
return（i）;
}//查找到，返回位置
if（i==n）return（-1）;
//没有找到，返回-1
2.折半查找的算法
intSearch_Bin（SSTable*ST,intnumber）
intlow=1,high=ST->
length;
intmid;
while（low<
=high）
mid=（low+high）/2;
if（EQ（ST->
elem[mid].number,number））
returnmid;
elseif（LT（number,ST->
elem[mid].number））
high=mid-1;
else
low=mid+1;
return0;
3.分块查找的算法
intblksearch（sqlistr,indexidx,find=0,hb;
）//bn为块个数//
{inti,;
low=1,high1=bn,midl,find=0,hb;
while（low1<
=high1&
!
find）
{mid=（low1+high1）/2;
if（k<
idx[mid1].key）high1=mid-1;
elseif（k>
idx[mid1],key）low1=mid1+1;
else{
low=mid1;
find=1;
if（low1<
bn）//k小于索引表最大值//
{i=idx[low1].low;
hb=idx[low1].high;
while（i<
hb&
r[i].key!
=k）i++;
if（r[i].key!
=k）i=0;
return（i）;
实验十排序算法
3.分别实现直接插入排序、冒泡排序、简单选择排序，并随机生成30个数，比较各算法的时、空性能和稳定性。
4.掌握常用排序算法的特点，以便根据实际情况选择使用。
3.对比直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序，并比较各算法的时、空性能及稳定性。
4.掌握常用排序算法的特点
3.直接插入排序算法
voidinsertion_sort（a,n）
inta[],n;
{inti,j,t;
for（i=1;
{t=a[i];
for（j=i-1;
=0&
t<
a[j];
j--）
a[j+1]=a[j];
a[j+1]=t;
冒泡排序算法
voidbubble_sort（a,n）
{inti,j,t;
n--;
while（n>
0）
{j=0;
if（a[i]>
a[i+1]）
{t=a[i];
a[i]=a[i+1];
a[i+1]=t;
j=i;
n=j;
4.简单选择排序算法
voidselecttion_sort（a,n）
{inti,j,k,t;
{k=i;
if（a[k]>
a[j]）
k=j;
t=a[i];
a[i]=a[k];
a[k]=t;
}}
四、考核方式
期末课程
总评成绩构成
考核目标
考核内容
考核方式与考核次数
平时考核
100（20%）
学习态度
出勤情况
考核出勤
阶段考核成绩
100（50%）
理论应用
实际能力
综合能力
教学重点、难点
实验报告4-5份
结课考核成绩
100（30%）
学习诚信
知识掌握
实践能力
创新能力
覆盖全部教学内容
机考1次
五、实验教科书、参考书
1.教研组自编，数据结构实验指导与实验报告；
2.徐健，曾玉华主编，数据结构上机指导与习题解析，南京大学出版社，2007年。
3.汪沁、奚李峰主编，数据结构教程，清华大学出版社．
升级会员 