《数据结构》daan.docx
《《数据结构》daan.docx》由会员分享，可在线阅读，更多相关《《数据结构》daan.docx（134页珍藏版）》请在冰点文库上搜索。
《数据结构》daan
《数据结构》实验教学大纲
实验学时：
32 实验个数：
7实验学分：
1
课程性质：
专业必修课适用专业：
计算机科学与技术
教材及参考书：
1.《数据结构（C语言版）》，严蔚敏吴伟民，北京：
清华大学出版社，2004
2.《数据结构题集（C语言版）》实习题部分，北京：
清华大学出版社，2004；
3.《数据结构实验教程》，王玲刘芳等著，成都：
四川大学出版社，2002
大纲执笔人：
刘芳大纲审定人：
郭涛
一、实验课的性质与任务
本课程实验大纲是面向计算机相关专业学生开设的《数据结构》实验课计划指导大纲，是依据《数据结构》课程教学计划指导大纲编制。
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。
由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。
数据结构实验课程着眼于数据结构原理和应用的结合点，使读者学会如何将书上学到的知识用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。
本实验课程主要结合数据结构课程的教学大纲的相应内容，设计了7个实验（包括验证型、综合型、设计型实验），力求提高学生的动手能力，做到理论和实践相结合。
使学生在实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，并训练问题的综合分析能力和编程能力，形成良好的编程风格，为后续课程的学习奠定坚实的理论和实践基础。
二、实验课程目的与要求
1.实验目的
根据《数据结构》课程的任务与要求，帮助学生拓宽知识面。
并达到以下教学要求：
（1）学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；掌握各种基本数据结构的逻辑结构和存储结构及相应算法。
（2）本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力；
（3）通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。
2.实验要求
（1）熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。
（2）会书写类C语言的算法，并将算法转变为程序实现。
（3）正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较强的逻辑分析能力。
（4）针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。
三、实验内容安排：
实验一抽象数据类型的表示与实现
（基本操作、验证型实验2学时）
1.目的要求：
（1）熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；
（2）理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）；
（3）认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。
2.实验内容：
（1）编程实现对一组从键盘输入的数据，计算它们的最大值、最小值、平均值等，并输出。
要求：
将计算过程写成一个函数，并采用引用参数实现值的求解。
#include
#defineN100
floatAverage（intnumble[N],inta）
{
floatsum=0;
inti;
for（i=0;isum=sum+numble[i];
returnsum/a;
}
intMax（intnumble[N],inta）
{
inti;
intmax=numble[0];
for（i=1;i{
if（maxmax=numble[i];
}
returnmax;
}
intMin（intnumble[N],inta）
{
inti;
intmin=numble[0];
for（i=1;i{
if（min>numble[i]）
min=numble[i];
}
returnmin;
}
intmain（）
{inti=0;
intnumble[N];
printf（"请输入数字（-1结束）\n"）;
scanf（"%d",&numble[i]）;
while（numble[i]!
=-1）
{i++;
scanf（"%d",&numble[i]）;
}
printf（"平均值是:
"）;
printf（"%f\n",Average（numble,i））;
printf（"最大值是:
"）;
printf（"%d\n",Max（numble,i））;
printf（"最小值是:
"）;
printf（"%d\n",Min（numble,i））;
}
（2）编程实现抽象数据类型三元组的定义、存储和基本操作，并设计一个主菜单完成各个功能的调用。
#include"h1.h"
typedefintElemType;
typedefElemType*Triplet;
StatusInitTriplet（Triplet&t,ElemTypev1,ElemTypev2,ElemTypev3）
{
t=（ElemType*）malloc（3*sizeof（ElemType））;
if（!
t）
returnOVERFLOW;
t[0]=v1;
t[1]=v2;
t[2]=v3;
returnOK;
}
StatusDestroyTriplet（Triplet&t）
{
free（t）;
t=NULL;
returnOK;
}
ElemTypeget（Triplet&t,inti）
{
ElemTypee;
if（i<1||i>3）printf（"i值不合法\n"）;
e=t[i-1];
returne;
}
Statusput（Triplet&t,inti,ElemTypee）
{
if（i<1||i>3）printf（"i值不合法\n"）;
t[i-1]=e;
returnOK;
}
StatusIsAscending（Triplett）
{
return（t[0]<=t[1]）&&（t[1]<=t[2]）;
}
StatusIsDescending（Triplett）
{
return（t[0]>=t[1]）&&（t[1]>=t[2]）;
}
ElemTypeMax（Triplett）
{
ElemTypee;
e=（t[0]>=t[1]）?
（（t[0]>=t[2]）?
t[0]:
t[2]）:
（（t[1]>=t[2]）?
t[1]:
t[2]）;
returne;
}
ElemTypeMin（Triplett）
{
ElemTypee;
e=（t[0]<=t[1]）?
（（t[0]<=t[2]）?
t[0]:
t[2]）:
（（t[1]<=t[2]）?
t[1]:
t[2]）;
returne;
}
voidmain（）
{
Tripletp;
ElemTypex;
ElemTypev1,v2,v3;
intselect,i;
printf（"输入三个数，建立一个三元组\n"）;
scanf（"%d%d%d",&v1,&v2,&v3）;
if（InitTriplet（p,v1,v2,v3）==OVERFLOW）
printf（"分配失败，退出程序！
"）;
else
do
{
printf（"1:
取三元组第i个元素\n"）;
printf（"2:
判断三元组元素是否递增\n"）;
printf（"3:
求最大值\n"）;
printf（"4:
求最大值\n"）;
printf（"5:
置换第i个元素\n"）;
printf（"0:
结束！
\n"）;
printf（"请输入选择！
\n"）;
scanf（"%d",&select）;
switch（select）
{
case1:
printf（"\ni="）;
scanf（"%d",&i）;
printf（"第%d个元素的值为：
%d\n",i,get（p,i））;
break;
case2:
if（IsAscending（p）==1）
printf（"三元组递增有序\n"）;
else
printf（"三元组非递增有序\n"）;
if（IsDescending（p）==1）
printf（"三元组递减有序\n"）;
else
printf（"三元组非递减有序\n"）;
break;
case3:
printf（"最大值是：
%d\n",Max（p））;
break;
case4:
printf（"最小值是：
%d\n",Min（p））;
break;
case5:
printf（"\ni="）;
scanf（"%d",&i）;
printf（"\nx="）;
scanf（"%d",&x）;
put（p,i,x）;
printf（"置换第%d个元素后的3个元素分别为：
%d,%d,%d\n",i,p[0],p[1],p[2]）;
break;
case0:
printf（"操作结束！
"）;
break;
default:
printf（"输入选择出错！
\n"）;
}//结束switch
}while（select!
=0）;//结束while
DestroyTriplet（p）;
}//结束main
3.主要仪器设备及软件
（1）PC机
（2）TurboC2.0或VisualC++
实验二线性表及其实现
（基本操作、验证型实验4学时）
1.目的要求：
（1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；
（2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；
（3）掌握循环链表和双链表的定义和构造方法
2.实验内容：
（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。
链式存储：
#include\软件\C++\数据结构\head.h>
#include
intinitList（LinkList&L）;
voidlistElemOutput_L（LinkList&L）;
intlistInsert_L（LinkList&L,inti,ElemTypee）;
intlistDelete_L（LinkList&L,inti）;
intlocateElem_L（LinkList&L,inti）;
intmenu（）;
intmain（）
{
LinkListLa;
intmchioce;
mchioce=menu（）;
while（mchioce!
=0）
{
switch（mchioce）
{
case1:
initList（La）;
break;
break;
case2:
inti,j;
printf（"请输入插入的位置和元素：
"）;
scanf（"%d%d",&i,&j）;
listInsert_L（La,i,j）;
break;
case3:
intk;
printf（"请输入删除元素的位置：
"）;
scanf（"%d",&k）;
listDelete_L（La,k）;
break;
case4:
inta;
printf（"请输入所查找元素的位置：
"）;
scanf（"%d",&a）;
locateElem_L（La,a）;
break;
case5:
listElemOutput_L（La）;
break;
default:
printf（"输入错误！
！
"）;
break;
}
system（"cls"）;
mchioce=menu（）;
system（"PAUSE"）;
}
}
intinitList（LinkList&L）
{
/*构造一个空的线形链表L。
*/
Linktempp=NULL;
if（!
（tempp=（Link）malloc（sizeof（LNode））））{
printf（"allocationofmemoryfail!
"）;
returnERROR;
}
tempp->data=0;/*初始化头结点*/
tempp->next=NULL;
L.len=0;
L.head=tempp;
L.tail=tempp;
printf（"链表创建成功！
\n"）;
intj,i;
intq;
printf（"输入线性表的元素个数：
\n"）;
scanf（"%d",&j）;
printf（"输入新的元素：
\n"）;
for（i=1;i<=j;i++）
{
scanf（"%d",&q）;
Linkp;
p=（Link）malloc（sizeof（LNode））;
p->data=q;
p->next=L.tail->next;
L.tail->next=p;
L.tail=L.tail->next;
++L.len;
}
returnOK;
}
voidlistElemOutput_L（LinkList&L）
{
/*inti=1;
for（;i<=p.len;i++）
{
printf（"\t%d",p.head->next->data）;
p.head=p.head->next;
}*/
Linkq;
q=L.head->next;
while（q）
{
printf（"\t%d",q->data）;
q=q->next;
}
printf（"\n"）;
system（"PAUSE"）;
return;
}
intlistInsert_L（LinkList&L,inti,ElemTypee）{
/*在带头结点的单链表L的第i个元素之前插入元素e。
*/
LinkListp=L;
Links;
intj=0;
while（p.head&&j{
p.head=p.head->next;
++j;
}
if（!
p.head||j>i-1）
returnERROR;
s=（Link）malloc（sizeof（LNode））;
s->data=e;
s->next=p.head->next;//插入新的元素
p.head->next=s;
++L.len;
returnOK;
}
intlistDelete_L（LinkList&L,inti）
{
LinkListp=L;
Linkq;
q=（Link）malloc（sizeof（LNode））;
intj=0;
while（p.head->next&&jnext）
{
p.head=p.head->next;
++j;
}
if（!
p.head->next||j>i-1）
returnERROR;
q=p.head->next;
p.head->next=q->next;
free（q）;
--L.len;
returnOK;
}
intlocateElem_L（LinkList&L,inti）
{
LinkListp=L;
intj=0;
printf（"你要查找的元素是:
"）;
while（p.head&&j{
p.head=p.head->next;
++j;
}
printf（"\t%d",p.head->data）;
printf（"\n"）;
system（"PAUSE"）;
/*if（!
p.head）
printf（"\t%d",p.head->data）;
else
returnERROR;
printf（"\n"）;
system（"PAUSE"）;*/
returnOK;
}
intmenu（）
{inti;
printf（"\t\t\t菜单\n"）;
printf（"\t1.创建顺序链表\n"）;
printf（"\t2.插入\n"）;
printf（"\t3.删除\n"）;
printf（"\t4.查找\n"）;
printf（"\t5.打印所有元素\n"）;
printf（"\t0.退出\n"）;
printf（"\n"）;
printf（"请输入正确的序号：
"）;
scanf（"%d",&i）;
if（i==0）
{
exit（0）;
}
else
returni;
}
顺序存储：
#include\软件\C++\数据结构\head.h>
#include
voidlistElemOutput_Sq（SqList*L）;
intlistInsert_Sq（SqList*L,inti,ElemTypee）;
intlistDelete_Sq（SqList*L,inti）;
intinitList_Sq（SqList*L）;
intlocateElem_Sq（SqListL,inti）;
intmenu（）;
voidmain（）
{intmchioce;
inta=1;
SqListLa;
mchioce=menu（）;
while（mchioce!
=0）
{
switch（mchioce）
{
case1:
initList_Sq（&La）;
break;
break;
case2:
inti,j;
printf（"请输入插入的位置和元素：
"）;
scanf（"%d%d",&i,&j）;
listInsert_Sq（&La,i,j）;
break;
case3:
intk;
printf（"请输入删除元素的位置：
"）;
scanf（"%d",&k）;
listDelete_Sq（&La,k）;
break;
case4:
inta;
printf（"请输入所查找元素的位置：
"）;
scanf（"%d",&a）;
locateElem_Sq（La,a）;
break;
case5:
listElemOutput_Sq（&La）;
break;
default:
printf（"输入错误！
！
"）;
break;
}
system（"cls"）;
mchioce=menu（）;
system（"PAUSE"）;
}
}
voidlistElemInput_Sq（SqList&L）
{
intla_len;
inti;
printf（"输入线性表LA元素个数：
"）;
scanf（"%d",&la_len）;
printf（"请输入A的元素：
"）;
for（i=1;i<=la_len;i++）
{
scanf（"%d",&L.elem[i]）;
L.length++;
}
}
voidlistElemOutput_Sq（SqList*L）
{
inti=1;
printf（"\n\t输出:
\n\t"）;
for（;i<=L->length;i++）
{
printf（"\t%d",L->elem[i]）;
}
printf（"\n"）;
system（"PAUSE"）;
return;
}
intlistInsert_Sq（SqList*L,inti,ElemTypee）
{
/*在顺序表L中第i个位置之前插入新的元素e*/
/*i的合法值为1<=i<=ListLength_Sq（L）+1*/
ElemType*p,*q,*newbase;
if（i<1||i>L->length+1）returnERROR;/*i值不和法*/
if（L->length>=L->listsize）{/*当前存储空间已满，增加分配*/
newbase=（ElemType*）realloc（L->elem,（L->listsize+LISTINCREMENT）*sizeof（ElemType））;//重新分配新的内存空间
if（!
newbase）exit（OVERFLOW）;/*存储空间分配失败*/
L->elem=newbase;/*新基址*/
L->listsize+=LISTINCREMENT;
}
q=&（L->elem[i]）;/*q为插入位置*/
for（p=&L->elem[L->length];p>=q;--p）
*（p+1）=*p;
*q=e;
++（L->length）;
returnOK;
}/*ListInset_Sq*/
intlistDelete_Sq（SqList*L,inti）{
/*在顺序表L中删除第i个元素，并用e返回其值*/
/*i的合法值为1<=i<=Lis
升级会员 