数据结构实验教学大纲.doc

数据结构实验教学大纲
《数据结构》实验教学大纲
课程名称：数据结构实验
英文名称：
课 程 编 号：120209 开课学期：3
适用专业/对象：计算机学科各专业实验课性质：独立开课
实验学时：32实验学分：1
大纲主撰人：辛日华 制定时间：2013.08
一、实验教学目的及基本要求
数据结构是一门实践性较强的软件基础课程，它在计算机软件教学中起着承上启下的作用，通过实验使学生在基本数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及实现等方面加深对课程的理解，同时在程序设计方法以及上机操作等基本技能和科学作风方面受到较严格的训练。通过该课程的实验教学，加强学生动手能力的培养，巩固和加深学生的理论知识，提高编程技能，培养学生良好的编程风格以及分析问题、解决问题的能力。
二、主要仪器设备及型号
计算机
三、实验课程内容和学时分配
序
号
实验项目名称
实 验 内 容
学时分配
实验类别
实验
类型
实验要求
已开/未开
1
顺序表的基本算法
掌握查找、插入、删除操作
4
专业基础
实训
必修
已开
2
链表的基本运算
单链，环链的查找、插入、删除
4
专业基础
实训
必修
已开
3
栈的基本运算
顺序及链式的进栈，出栈
2
专业基础
实训
必修
已开
4
队列的基本运算
顺序及链式的入队，出队
4
专业基础
实训
必修
已开
5
串基本操作
串的运算及模式匹配
2
专业基础
实训
必修
已开
6
数组
三元组的转置
2
专业基础
实训
必修
已开
7
二叉树基本算法
二叉树的遍历
4
专业基础
实训
必修
已开
8
图的存储及遍历
图的邻接矩阵和邻接表存储
4
专业基础
实训
必修
已开
9
查找
顺序查找 、折半查找、分块查找
2
专业基础
实训
必修
已开
10
排序算法
插入、选择、冒泡等排序
希尔排序、快速排序
4
专业基础
实训
必修
已开
实验一 顺序表的基本算法
（一）实验目的
1. 理解和掌握顺序表的结构类型定义方法；
2. 掌握建立、显示、插入、删除、查找、拆分、合并顺序表的基本方法。
（二）基本知识及预习
1. C程序编辑、编译和运行的过程；
2. 结构类型定义方法和成员的引用。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 理解和掌握顺序表的结构类型定义方法及应用
/*插入算法描述（一）*/
void Insert (Sqlist V, int i, Datatype x )
{int j;
if (i<1 || i >V.last ) printf ("infeasible position! \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++;
}
}
}

/*删除算法描述（一）*/
void Delete (Sqlist V, int i)
{int j;
if (i<1 || i>V.last ) printf ("infeasible \n");
else {for (j=i; j<V.last; j++)
V.elem[j]=V.elem[j+1];
V.last--; }
}
1. 掌握建立、显示、插入、删除、查找、拆分、合并顺序表的多种实现方法。
/*插入算法描述（二）*/
int sq_insert(list,p_n,i,x)
int list[],x,i,*p_n;
{ int j;
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);
}

/*删除算法描述（二）*/
int sq_delete(list,p_n,i)
int list[],*p_n,i;
{ int j;
if(i<0||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. 单链表的建立和删除。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1．单链表的插入算法。
/*算法描述*/
void InsetLList(Llist L, int i, Datatype x)
{Llist p, s;
int j=0;
p= L;
while (p!=NULL && j<i-1 ) {p=p->next; j++; }
if (p= = NULL || j>i-1) printf(“No this position!\n”);
else {s=(Llist) malloc (sizeof (Node) );
s->data=x;
s->next=p->next;
p->next=s;}
}
2．单链表的删除算法。
/*算法描述2.3*/
void Delete (LList L, int i)
{LList p, q;
int j=0;
p=L;
while ( p!=NULL && j<i-1 ) {p=p->next; j++; }
if ( p= = NULL || j>i-1) printf(" No this data!\n");
else { q=p->next;
p->next =p->next->next;
free (q);
}
}
实验三栈的基本运算
（一）实验目的
1. 掌握顺序栈和链式栈的类型定义方法。
2. 掌握在顺序栈和链式栈上实现的基本算法。
（二）基本知识及预习
1. 栈的定义及基本术语；
2. 栈的基本运算。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1．进栈算法
/* 入栈算法*/
int push(int x)
{ if(top>=MAXN)
return 1；
stack[top]=x;
top++;
return 0;
}
2．出栈算法
/*出栈算法*/
Int pop(int *p_y)
{ if(top==0)
return 1；
top--;
*p_y=stack[top];
return 0;
}
实验四 队列的基本运算
（一）实验目的
1. 掌握顺序队列和链式队列的类型定义方法。
2. 掌握在顺序队列和链式队列上实现的基本算法。
（二）基本知识及预习
1. 队列的定义及基本术语
2. 队列的基本运算
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 进队列算法
/*入队算法*/
int en_queue(char x)
{ if(tail==MAXN-1)
return 1；
q[++tail]=x;
return 0;
}
2. 出队列算法
/*出队算法*/
Int de_queue(char *p_y)
{ if(head==tail)
return 1；
*p_y=q[++head];
return 0;
}
实验五 串基本操作演示系统
（一）实验目的
1. 掌握串的表示和实现；
2. 掌握串的基本算法；
3. 对比两种模式匹配算法，分析各算法的时、空性能；
4. 综合设计和实现串的替换算法。
（二）基本知识及预习
1. 掌握串的定义和表示方法；
2. 掌握串的基本运算。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 通过两个例题理解串函数的功能
例1：
s=′good′,t=′I am a student′,
1)strcat(s,t)
2)strsub(t,8,7)
3)strlen(t)
4)strstr(t, ′a′)
5)strins(t,8,s)
例2：
a=′I AM A STUDENT ′
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. 匹配算法实现：
int index(char t[ ],char p[ ],int m,int n)
{ int I,j,k;
for(i=0;i<=n-m;i++)
{ for(j=0,k=I;j<m&&t[k]==p[j];k++,j++);
if(j==m) return(i);
}
return(-1);
}
实验六数组
（一）实验目的
1. 掌握数组的表示和实现；
2. 掌握特殊矩阵的压缩存储；
3. 掌握广义表的定义和基本运算。
（二）基本知识及预习
1. 数据的定义和表示方法；
2. 结构数组的定义和引用；
3. 广义表的定义和基本运算。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 稀疏矩阵的压缩存储---三元组顺序表的实现。
2. 稀疏矩阵的转置运算。
3. 广义表的的基本运算。
实验七 二叉树基本算法
（一）实验目的
1. 综合设计和实现二叉树的创建、遍历、求高度、统计结点数目等基本算法，掌握树结构的处理方法；
2. 了解哈夫曼特性，验证哈夫曼算法。
（二）基本知识及预习
1. 掌握二叉树的定义及基本术语；
2. 掌握二叉树的创建、遍历、求高度、统计结点数目等基本算法。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 二叉树的先序遍历算法
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
2. 二叉树的中序遍历算法
void midorder(JD *bt)
{ if(bt!=NULL)
{ midorder(bt->lchild);
printf("%d\t",bt->data);
midorder(bt->rchild);
}
}
3. 二叉树的后序遍历算法
void posorder(JD *bt)
{ if(bt!=NULL)
{ posorder(bt->lchild);
posorder(bt->rchild);
printf("%d\t",bt->data);
}
}
实验八图的存储及遍历
（一）实验目的
1. 熟悉图的常用存储结构和基本操作，分别用邻接矩阵和邻接表实现以下操作：图的创建、遍历、插入、删除；
2. 综合设计和实现图的最短路径算法，理解图的具体应用。
（二）基本知识及预习
1. 掌握图的定义、基本术语及存储方式；
2. 掌握图的创建、遍历等基本算法。
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 分别用邻接矩阵和邻接表实现图的创建、遍历；
2. 实现图的最短路径算法，理解图的具体应用。
实验九查找
（一）实验目的
1. 分别实现顺序查找 、折半查找、分块查找的算法；
2. 掌握常用查找算法的特点，以便根据实际情况选择使用。
（二）基本知识及预习
1. 对比顺序查找 、折半查找、分块查找的思想和算法。
2. 掌握常用查找算法的特点
（三）实验环境
安装DEV C++的计算机
（四）实验内容
1. 顺序查找的算法
int fun(int a[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
printf("该点是%d\n",a[i]);
if(a[i]==x) {puts("找到\n");return(i);}//查找到，返回位置
}
if(i==n) return(-1);//没有找到，返回-1
}
2. 折半查找的算法
int Search_Bin(SSTable *ST,int number)
{
int low=1,high=ST->length;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(EQ(ST->elem[mid].number,number))
return mid;
else if(LT(number,ST->elem[mid].number))
high=mid-1;
else
low=mid+1;
}
return 0;
}
3. 分块查找的算法
int blksearch(sqlist r,index idx,find=0,hb;) // bn为块个数 //
{ int i,;low=1,high1=bn,midl,find=0,hb;
while(low1<=high1&&!find)
{mid=(low1+high1)/2;
if(k<idx[mid1].key)high1=mid-1;
else if(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. 掌握常用排序算法的特点
（三）实验环境
安装DEV C++的计算机
（四）实验内容
3. 直接插入排序算法
void insertion_sort(a,n)
int a[],n;
{ int i,j,t;
for(i=1;i<n;i++)
{ t=a[i];
for(j=i-1;j>=0&&t<a[j];j--)
a[j+1]=a[j];
a[j+1]=t;
}
}
冒泡排序算法
void bubble_sort(a,n)
int a[],n;
{ int i,j, t;
n--;
while(n>0)
{ j=0;
for(i=0;i<n;i++)
if(a[i]>a[i+1])
{t=a[i];
a[i]=a[i+1];
a[i+1]=t;
j=i;}
n=j;}
}
4. 简单选择排序算法
void selecttion_sort(a,n)
int a[],n;
{ int i,j,k,t;
for(i=0;i<n;i++)
{ k=i;
for(j=i+1;j<n;j++)
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. 汪沁、奚李峰主编，数据结构教程，清华大学出版社．
22 / 22