数据结构实验数据Word下载.docx
《数据结构实验数据Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验数据Word下载.docx（63页珍藏版）》请在冰点文库上搜索。
熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；
掌握设计算法的步骤和算法分析方法；
掌握数据结构在排序等常用算法中的应用。
通过上机实践训练，培养学生的数据抽象能力和程序设计的能力。
四、主要仪器设备
386以上微机TurboC2.0或Win-TC、VC6
五、实验项目及教学安排
序号
实验项目名称
实验基本方法和内容
项目
学时
类型
每组
人数
教学要求
1
熟悉C语言
使用C语言编程语言环境；
自主设计、编译一基本C语言程序。
2
基础
必修
线性表
利用顺序及链式存储实现线性表，并实现其基本操作。
3
栈和队列
利用顺序或链式存储实现栈和队列，并实现其基本操作。
利用堆栈完成表达式求值的算法操作等
串
建立串的数据类型，并实现其基本操作。
完成串的文本模式匹配算法。
选修
5
数组和广义表
建立数组的存储结构，并实现其基本操作。
6
树的操作
建立树的数据类型并实现其基本操作；
实现二叉树的建立、遍历、输出查找、更新、插入、删除等算法。
实现哈夫曼树及其操作。
7
图的操作
实现图及其操作；
实行图的深度、广度遍历算法；
实现最短路径算法，拓扑排序算法。
实现AOE网关键路径。
8
查找
实现折半查找的算法；
实现二叉排序树的查找算法算法。
9
排序
实现插入和选择排序算法；
实现交换和归并排序算法。
综合
10
综合实验
利用所学到的知识设计出合适的存储结构解决相关的实际问题。
实现Joseph环、赫夫曼树的建立算法。
六、考核方式及成绩评定
考核方式
1、实验平时成绩：
（1）实验考勤：
每次考勤分出勤（2分）；
请假、迟到、早退（1分）；
旷课（0分）记分。
（2）预习报告：
要求写明实验目的、主要实验设备名称、实验原理和内容。
分优秀（4分）、良好（3分）、中等（2分）、及格（1分）和不及格（0分）记分。
（3）实验报告：
要求写明实验设备名称和型号、实验步骤、实验分析及注意事项。
实验平时成绩最后折算成100分。
2、实验考试：
上机考试，满分为100分。
成绩评定：
总实验成绩占本课程成绩的20%。
总实验成绩=实验平时成绩×
50%+实验考试成绩×
50%。
七、实验教科书、参考书
1．实验教科书
数据结构（C语言版），严蔚敏，清华大学出版社，2003
2．实验参考书
（1）数据结构，魏开平，清华大学出版社，2005
（2）数据结构实验，徐孝凯，中央电大出版社，2005
实验O熟悉C语言
一、实验目的
1．复习C语言中数组的使用
2．复习C语言中指针的使用
3．复习C语言中结构体的使用
二、实验内容
1.学习C语言数组示例，写出程序结果
2.学习C语言指针示例，写出程序结果
3.学习C语言结构体示例，写出程序结果
三、实验实例
数组示例：
#include"
stdio.h"
#defineN4
main（）
{
inti,j,k,a[N];
printf（"
Pleaseinput4numbers:
\n"
）;
for（i=0;
i<
N;
i++）
scanf（"
%d"
&
a[i]）;
for（i=N-1;
i>
1;
i--）
{
for（j=1;
j<
=i;
j++）
if（a[j-1]>
a[j]）
k=a[j-1];
a[j-1]=a[j];
a[j]=k;
}
i++）printf（"
%d"
a[i]）;
}
思考题：
说出上述程序的功能
指针示例1：
#include
<
stdio.h>
main（）
{
int
a,b;
*point_1,*point_2,*temp_point;
%d,%d"
a,&
b）;
point_1=&
a;
point_2=&
b;
if
（a<
b）
temp_point=point_1;
point_1=point_2;
point_2=temp_point;
}
*point_1,*point_2）;
指针示例2：
*point_1,*point_2;
point_1
=
&
point_2
compositor（point_1,point_2）;
a,b）;
static
compositor（p1,p2）
*p1,*p2;
temp;
（*p1<
*p2）
temp
*p1;
*p1
*p2;
*p2
比较指针示例1和指针示例2说出他们的区别，并分别说出他们的功能
结构体例子：
structstudent
{charnum[6];
//学生编号
charname[8];
//学生姓名
intscore[3];
//学生三门课程分数
floatavr;
}stu[5];
//共有五个学生
{inti,j,sum;
/*input*/
5;
i++）
{printf（"
\npleaseinputNo.%dscore:
i）;
stuNo:
"
%s"
stu.num）;
name:
stu.name）;
sum=0;
for（j=0;
3;
j++）
score%d."
j+1）;
stu.score[j]）;
sum+=stu.score[j];
stu.avr=sum/3.0;
这是关于学生成绩运算的一个结构体函数，写出函数功能
四、实验报告要求
1.上机前完成所有的函数编写
2.主要实验设备（软件）部分填写：
装有Win—TC软件的普通PC机
3.实验记录部分填写编写主函数调用所写所有函数的屏幕输出
4.设备名称填写PC机，型号可空，编号填写所使用计算机编号，运行情况填写良好
5.实验总结部分填写对该次实验所编写函数的运行情况，和在实验过程中对线性表的认识和实现情况
实验0（附）熟悉C语言
1.编写C语言函数，完成输出九九乘法表（提示：
使用二维数组完成）
2.编写C语言函数，使用指针完成一个二十位整型数组的遍历，并将数组中的各位分别增1
注意：
若对C语言比较熟悉，可进行实验0（附）中的实验项目编写，若不熟悉，则可完成对实验一中问题的回答
实验一
（1）线性表及其应用
1.掌握实现线性表的基本操作方法;
2.掌握线性表的基本操作:
建表,插入,删除,输出等运算在顺序存储结构和链式存储结构上的实现.
通过本次实习加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现
1.编写生成线性表的函数,线性表的元素从键盘输入,分别使用顺序和链式存储结构存储;
2.编写在线性表中插入一元素的函数;
3.编写在线性表中删除一元素的函数;
4.编写输出线性表的函数;
5.编写主函数,调用以上各函数,以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出.
三、实验报告要求
6.上机前完成所有的函数编写
7.主要实验设备（软件）部分填写：
8.实验记录部分填写编写主函数调用所写所有函数的屏幕输出
9.设备名称填写PC机，型号可空，编号填写所使用计算机编号，运行情况填写良好
10.实验总结部分填写对该次实验所编写函数的运行情况，和在实验过程中对线性表的认识和实现情况
四、实验原理
（一）线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。
例如26个英文元素的字母表：
（A，B，C，D，·
·
）。
其数据结构的描述为：
Linear_list=（D,R）其中：
D={ai|ai属于D0,i=1,2,3,·
}R={N},N={<
ai-1,ai>
|i=2,3,4,·
}。
本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：
LOC（ai+1）=LOC（ai）+m。
其中m是存放每个元素所占的内存字数。
LOC（ai）=LO+m·
（i-1）。
其中LO是ai的地址，即首地址。
（二）实验程序说明
插入一个新元素到第i个位置，既把元素ai向后移一个位置，成为元素ai+1，把新元素放入到第i个位置，其他元素依次后移。
存一新元素到第i个位置是把元素ai冲掉后存上新值。
删除第i个元素就是把余后的元素依次向前移一个位置。
即：
以元素ai+1，ai+2，·
，依次取代ai，ai+1，·
。
删除后的表长是n-1（n是原表长）。
三、程序流程图
五、参考程序
conio.h"
#defineMaxLine100/*顺序存储的最大个数*/
typedefintElemType;
typedefstruct
ElemTypedata[MaxLine];
/*存放顺序表的数组*/
intlength;
/*顺序表的长度*/
}SqList,*L;
/*初始化顺序表*/
voidInitList（SqList*L）
L->
length=0;
/*得到顺序表的长度*/
intGetLength（SqList*L）
returnL->
length;
/*得到顺序表中的第i个元素*/
ElemTypeGetElem（SqList*L,inti）
if（i<
1||i>
length）
{
printf（"
error"
exit
（1）;
}
data[i-1];
voidListInsert（SqList*L,inti,ElemTypex）
/*添加线性表中第i个位置上的元素,i从1开始*/
intj;
length+1）/*检查添加位置的合法性*/
if（L->
length==MaxLine）
overflow!
j=L->
while（j<
i-1）
data[j]=L->
data[j-1];
j--;
data[i-1]=x;
length++;
voidListDelete（SqList*L,inti）/*删除线性表中第i个位置上的元素*/
if（i<
1||i>
L->
length）/*检查空表及删除位置的合法性*/
{
printf（"
不存在第i个元素"
exit（0）;
for（j=i;
=L->
length-1;
data[j-1]=L->
data[j];
/*向前移动元素*/
length--;
SqList*L;
intt=1,d=1;
ElemTypedata;
InitList（L）;
for（t=1;
t<
=8;
t++）
Pleaseinputthe%dthlistelem:
t）;
scanf（"
d）;
ListInsert（L,t,d）;
thelengthofListis%d\n"
GetLength（L））;
data=GetElem（L,1）;
%d\n"
data）;
ListDelete（L,1）;
getch（）;
六、实验步骤
1．参考实验程序自己编出程序，上机调试。
2．对调试好的程序进行以下实验
七、思考题
1．有序表，有哪些显著的特点和优点？
实验一
（2）单链表及其应用
一、实验目的
了解单链表的基本概念、结构的定义及在单链表上的基本操作（插入、删除、查找以及线性表合并），通过在TurboC实现以上操作更好的了解书本上的内容并体会线性表的两种存储结构的区别。
二、实验预备知识
⑴复习C语言中指针的用法，特别是结构体的指针的用法；
⑵了解单链表的概念，单链表的定义方法；
单链表是线性表的链式存储表示，是用一组任意的存储单元依次存储线性表的数据元素。
因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），而这部分就是用指针来完成的。
⑶掌握线性表在链式存储结构上实现基本操作：
查找、插入、删除的算法；
在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：
在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出错误提示）。
在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，原因同实验一，其次要注意插入的时候语句的顺序不可颠倒，否则出错。
例如：
p
s
s所指向结点要插入在p所指向的结点之后，则：
正确形式：
s->
next=p->
next
p->
next=s
错误形式：
p->
s->
next（因为此时p->
next已经指向s了）
在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；
其次在删除后要回收空间。
删除如上图所示s所指向的结点
next->
frees
三、实验内容
⑴单链表的插入算法
⑵单链表的删除算法
⑶循环链表的插入和删除算法（选做）
四、部分实验代码
⑴单链表的结构定义：
#include<
typedefintelemtype;
typedefstructlnode
{elemtypedata;
structlnode*next;
}*linklist;
⑵建立单链表的算法
intn;
/*n作为整个程序的全局变量*/
linklist*creat（void）
{linklist*head,*p1,*p2;
n=0;
p1=p2=（linklist*）malloc（sizeof（linklist））;
scanf（“%d”,&
p1->
data）;
head=null;
while（p1->
data!
=0）
{n=n+1;
if（n==1）head=p1;
elsep2->
next=p1;
p2=p1;
p1=（linklist*）malloc（sizeof（linklist））;
p2->
next=null;
return（head）;
⑶单链表的插入算法
intinsert（linklist*head,inti,elemtypee）
{linklist*p,*s;
p=head;
j=0;
while（p&
j<
i-1）
{p=p->
next;
++j;
if（!
p||j>
{printf（“无法插入”）；
return0;
s=（linklist*）malloc（sizeof（lnode））;
data=e;
next=s;
return1;
⑷单链表的删除算法
intdeltree（linklist*head,inti,elemtypee）
{linklist*p,*q;
l
p=head;
while（p->
next&
++j;
（p->
next）||j>
{printf（“无法删除”）;
return0;
q=p->
next=q->
e=q->
data;
free（q）;
return1;
实验二
（1）栈及其应用
1.掌握实现栈的基本操作方法
2.掌握栈的基本操作：
建栈，Push，Pop等运算在顺序存储结构上的实现
通过本次实习加深对高级语言C语言的使用，熟悉串的基本运算顺序结构上的实现
1.编写生成栈的函数，栈的元素从键盘输入
2.编写在栈中压入一个元素的函数
3.编写在栈中弹出一个元素的函数
4.编写主函数，调用以上各函数，以便能观察出各函数的屏幕输出。
5.实验总结部分填写对该次实验所编写函数的运行情况，和在实验过程中对栈的认识和实现情况
四、参考程序
#defineMaxSize100/*栈中的元素的最大个数*/
ElemTypedata[MaxSize];
/*存放堆栈的数组*/
inttop;
/*栈顶元素*/
}Stack,*S;
/*堆栈的初始化*/
voidInitStack（Stack*S）
/*指向的是最顶端的元素
取值范围为从0~MaxSize-1
为-1时说明为空栈*/
S->
top=-1;
/*判栈空操作*/
intStackEmpty（Stack*S）
return（S->
top==-1?
1:
0）;
/*压栈操作*/
voidPush（Stack*S,ElemTypex）
inti;
if（S->
top==MaxSize-1）
Stackisfull"
/*elseS->
data[++S->
top]=x;
*/
else
top=S->
top+1;
i=S->
top;
data[i]=x;
/*出栈操作*/
intPop（Stack*S）
inti;
if（StackEmpty（S））
\nStacki
升级会员 