1112数据结构实验教案.docx
《1112数据结构实验教案.docx》由会员分享，可在线阅读，更多相关《1112数据结构实验教案.docx（41页珍藏版）》请在冰点文库上搜索。
1112数据结构实验教案
11-12学年第一学期
《数据结构》
实验教案
辅导教师：
目录
实验一线性表及其应用1
实验二栈和队列及其应用11
实验三二叉树及其应用14
实验四综合实验（用户标识符统计）27
实验一线性表及其应用
实验目的：
利用线性表解决集合并运算
实验内容：
编制一个利用有序链表实现集合并运算的程序，例如Set1=”magazine”，Set2=”Paper”，则Set1∪Set2=”aegimnprz”，要求：
集合的元素限定为小写字母字符；演示程序以用户和计算机的对话方式执行。
实验步骤：
一需求分析
1集合的元素限定为小写字母字符，所以如果输入非法字符，程序应能自动滤去。
输出的结果不包含重复字符和非法字符
2程序以对话方式执行，计算机输出提示信息，用户用键盘选择要执行的操作
3程序执行的命令包括：
构造集合Set1,构造集合Set2，求并集，显示集合中的元素，结束
4测试数据，包括合法的测试数据以及非法数据（自己写一些测试数据）
二概要设计
为实现以上功能，可用有序链表表示集合，所以，可定义如下的抽象数据类型定义ADT
1ADTOrderList{
数据对象：
D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：
R1=｛|ai-1,aiD,i=2,…,n｝
基本操作：
InitLinkedList（&L）
操作结果：
构造一个空的线性表L.
Insert（&L,x）
初始条件：
线性表L已存在。
操作结果：
插入一个元素x，使得插入后L仍保持有序性。
ListTraverse（q,visit（））
初始条件：
线性表L已经存在，q指示L中一个元素
操作结果：
依次对L中q指示的元素开始的每个元素调用visit（）
LocateElem（L,x）
初始条件：
线性表L已经存在
操作结果：
如果L中存在与x相等的元素，则返回真，否则返回假
}ADTList
2本程序包括三个模块
主程序模块
Voidmain（）
{初始化；
Do
{接受命令；处理命令；}
}while（不是退出命令）
}
有序表单元模块：
实现有序表的抽象数据类型定义；
结点结构单元模块：
定义有序表的结点结构
模块之间的调用关系如下：
三详细设计
typedefcharElemType;//元素类型
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;//结点类型、指针类型
部分操作的伪代码实现如下：
StatusMakeNode（LinkList&p,ElemTypee）
{p=（LinkList）malloc（sizeof（LNode））;
If（!
p）returnERROR;
p->data=e;p->next=NULL;
returnOK;
}
StatusInitLinkedList（LinkList&L）
{MakeNOde（L,0）；//建立头结点，数据域没有实际含义，在这里设为0
returnOK
}
StatusInsert（LinkList&L,ElemTypex）
{MakeNode（r,x）;
p=L->next;q=L;
if（p==NULL）L->next=r;
else
{while（p!
=NULL&&x>p->data）{q=p;p=p->next;}
q->next=r;r->next=p;
}
returnOK;
}
StatusPrintElement（ElemTypee）
{printf（"%c",e）;returnOK;}
StatusListTraverse（LinkListL,Status（*visit）（ElemTypee））
{p=L->next;
while（p）
{visit（p->data）;p=p->next;}
returnOK;
}
StatusLocateElem（LinkListL,ElemTypex）
{p=L->next;
if（p==NULL）returnFALSE;
while（p!
=NULL&&x!
=p->data）p=p->next;
if（p==NULL）returnFALSE;
returnOK;
}
voidMergeList（LinkList&La,LinkList&Lb,LinkList&Lc）{LinkListpa,pb,pc;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while（pa&&pb）
{
if（pa->data<=pb->data）
{pc->next=pa;pc=pa;if（pa->data==pb->data）pb=pb->next;
pa=pa->next;
}
else
{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?
pa:
pb;
free（Lb）;
}
StatusCreateList（LinkList&L,char*s）
{InitLinkedList（L）;
for（i=0;i<=strlen（s）-1;i++）
if（islower（s[i]）&&!
LocateElem（L,s[i]））
Insert（L,s[i]）;
returnOK;
}
main（）
{do
{printf（"pleasechoose:
\ncreateset1
（1）\ncreateset2
（2）output2set（3）\nMergeList（M）\noutputmerge（P）\nQuit（Q）"）;
ch=getchar（）;
getchar（）;
switch（ch）
{
case'1':
gets（a）;CreateList（s1,a）;ListTraverse（s1,PrintElement）;break;
case'2':
gets（a）;CreateList（s2,a）;ListTraverse（s2,PrintElement）;break;
case'M':
MergeList（s1,s2,s3）;ListTraverse（s3,PrintElement）;break;
}
}while（ch!
='Q'）;
}
测试结果：
学生可以根据main的设计自己写一些测试数据
四实验分析与总结：
容易忽略&,注意定义函数时需在变量前加上&，调用时不需要
容易混淆.运算符和->运算符
时间复杂度分析：
CreateSet:
O（n2）
MergeList:
O（m+n）
缺点：
可以将LocateElem函数设计的功能更强大，不但可以在CreateSet函数中使用，还可以在Insert中使用；没有将集合和有序集合分开设计，这样使得代码的可重用性差。
另外，为方便学生解决此问题，可先引导学生学会使用顺序表和链表的程序设计，顺序表的示例使用如下：
#include"stdio.h"
#include"stdlib.h"
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefintElemType;
typedefintstatus;
#defineOK1
#defineOVERFLOW-1
#defineERROR0
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
statusInitList（SqList&L）
{
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）
exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
statusListInsert_Sq（SqList&L,inti,ElemTypee）
{
ElemType*newbase,*p,*q;
if（i<1||i>L.length+1）returnERROR;
if（L.length>=L.listsize）
{newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）exit（OVERFLOW）;
L.elem=newbase;
L.listsize=L.listsize+LISTINCREMENT;
}
q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;
*q=e;
L.length++;
returnOK;
}
statusListDelete_Sq（SqList&L,inti,ElemType&e）
{
ElemType*p,*q;
if（（i<1）||i>L.length）returnERROR;
p=&L.elem[i-1];
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）
*（p-1）=*p;
--L.length;
returnOK;
}//ListDelete_Sq
main（）
{
SqListL;
inti;
ElemTypee;
InitList（L）;
for（i=0;i<5;i++）
L.elem[i]=i+1;
L.length=5;
for（i=0;i<5;i++）
printf（"%d",L.elem[i]）;
ListInsert_Sq（L,1,0）;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
ListDelete_Sq（L,1,e）;
for（i=0;iprintf（"%d",L.elem[i]）;
}
链表的示例使用如下：
#include"stdio.h"
#include"stdlib.h"
#defineOK1
#defineERROR0
typedefintstatus;
typedefintElemType;
typedefstructLnode
{ElemTypedata;
structLnode*next;
}Lnode,*Linklist;
statusCreateList_L（Linklist&L,intn）
{
inti;
Linklistp;
L=（Linklist）malloc（sizeof（Lnode））;
L->next=NULL;
for（i=n;i>0;--i）
{
p=（Linklist）malloc（sizeof（Lnode））;
scanf（"%d",&p->data）;
p->next=L->next;
L->next=p;
}
returnOK;
}//createList_L
statusListInsert_L（Linklist&L,inti,ElemTypee）
{
Linklistp,s;
intj;
p=L;j=0;
while（p&&jnext;++j;}
if（!
p||j>i-1）returnERROR;
s=（Linklist）malloc（sizeof（Lnode））;
s->data=e;
s->next=p->next;p->next=s;
returnOK;
}//ListInsert_L
/*
statusCreateList_L（Linklist&L,intn）
{Linklistr;
L=（Linklist）malloc（sizeof（LNode））;
L->next=NULL;
r=L;
for（i=1;i<=n;++i）
{
p=（Linklist）malloc（sizeof（LNode））;
scanf（"%d",&p->data）;
r->next=p;r=p;
};
r->next=NULL;
};//createList_L
*/
statusListdelete_L（Linklist&L,inti,ElemType&e）
{
Linklistp,q;
intj;
p=L;j=0;
while（p->next&&jnext;++j;}
if（!
（p->next）||j>i-1）returnERROR;
q=p->next;p->next=q->next;
e=q->data;free（q）;
returnOK;
}//Listdelete_L
main（）
{
Linklistp,L;
ElemTypee;
CreateList_L（L,5）;
p=L->next;
while（p!
=NULL）
{printf（"%4d",*p）;p=p->next;}
ListInsert_L（L,1,9）;
p=L->next;
while（p!
=NULL）
{printf（"%4d",*p）;p=p->next;}
Listdelete_L（L,1,e）;
printf（"%4d",e）;
p=L->next;
while（p!
=NULL）
{printf（"%4d",*p）;p=p->next;}
}
实验二栈和队列及其应用
实验目的：
利用栈实现数制转换
实验内容：
编制一个利用栈求十进制数转换为八进制数的程序，例如输入1348，则输出2504，要求：
演示程序以用户和计算机的对话方式执行。
实验步骤：
一需求分析
本程序用TC30编写或者VC6.0。
1输入：
只能输入非负的十进制数，如输入非法，应报错。
2输出：
输出转换后的八进制数。
3程序所能达到的功能：
输入合法的数；输出转换后的数。
4测试数据，包括合法的测试数据（1348）以及非法数据（-15）。
二概要设计
1为实现以上功能，可用栈的思想，所以，可定义如下的抽象数据类型定义ADT
ADTStack{
数据对象：
D={ai|aiElemSet，i=1，2，...，n，n>=0}
数据关系：
R={|ai-1，aiD，i=2,...,n}
约定an端为栈顶，a1端为栈底。
基本操作：
基本操作：
{InitStack（&S）
StackEmpty（S）
Push（&S,e）
Pop（&S,&e）
}
2本程序包括二个模块
主程序模块
Voidmain（）
{调用转换函数
}
栈单元模块：
实现栈的抽象数据类型定义；
模块之间的调用关系如下：
三详细设计
typedefintSElemType;//元素类型
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
部分操作的伪代码实现如下：
StatusInitStack（SqStack&S）{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack
StatusPush（SqStack&S,SElemTypee）{
if（S.top-S.base>=S.stacksize）//栈满
{S.base=（SElemType*）realloc
（S.base,（S.stacksize+STACKINCREMENT）
*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*S.top++=e;returnOK;}//Push
StatusPop（SqStack&S,SElemType&e）{
if（S.top==S.base）returnERROR;
e=*--S.top;
returnOK;
}//Pop
StatusStackEmpty（SqStackS）
{
if（S.base==S.top）
returnTRUE;
returnFALSE;
}
voidconversion（）
{intN,e;
SqStackS;
InitStack（S）;
scanf（"%d",&N）;
while（N）{Push（S,N%8）;N=N/8;}
while（!
StackEmpty（S））
{Pop（S,e）;printf（"%d",e）;}
}//conversion
main（）
{
conversion（）;
}
测试结果：
可以根据main的设计自己写一些测试数据，类似于习题集
实验分析与总结：
容易忽略引用调用的&,注意定义函数时需在变量前加上&，调用时不需要，输入时应带有&，表示取地址
特别注意判断栈空的实现方式，如果没有returnFALSE语句，则最后程序输出不正确，可引导学生用分步调试的方法来分析错误的原因
缺点：
也可以不用栈的思想实现，对于此问题，利用栈反倒浪费了内存空间，但是利用栈解决问题容易理解，降低了问题的复杂度。
实验三二叉树及其应用
实验题目：
二叉树及其应用
实验目的：
利用二叉树的中序遍历和后序遍历，实现求表达式的值以及逆波兰式（可选）
实验内容：
编制程序实现二叉树的中序遍历和后序遍历。
实验步骤：
一需求分析
本程序用TC30编写或者VC6.0。
1输入：
输入字符或者整型数。
2输出：
输出中序遍历结果和后序遍历结果，并把中序遍历结果的值求出（选做）。
3程序所能达到的功能：
建立二叉树，中序遍历，后序遍历，表达式求值（选做）。
4测试数据，包括合法的测试数据以及非法数据
二概要设计
1为实现以上功能，利用二叉树的思想，所以，可定义如下的抽象数据类型定义ADT
ADT定义
ADTTree{
数据对象D：
D是具有相同特性的数据元素的集合；
数据关系R：
若D只含一个数据元素或为空集，则R为空集；否则，R={H};H为如下二元关系：
（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱
（2）若D-{root}不为空，则存在D-{root}的一个划分D1，D2，…Dm
（m>0），
且对任意的I（1<=I<=m）唯一存在数据元素
（3）对应于D-{root}的划分，H-{…}，有唯一的一个划分H1，H2，…Hm（m>0），对任意一对
且对任意I（1<=I<=m）Hi是Di上的二元关系，（Di,{Hi}）是一棵符合本定义的树，称它为root的子树。
树的基本操作：
InitTree（&T）初始化操作，置T为空树
CreateTree（&T,defination）建立树函数
Parent（T,x）求双亲函数求树中结点x的比亲结点
TreeDepth（T）求树深度函数
Root（T）求根函数求树的根或结点x所在树的根。
RightSibing（T,Cur_e）求右兄弟函数
InsertChild（&T,&p,i,c）插入子树操作
DeleteChild（&T,&p,i）删除子树操作
TraverseTree（T,Visit（））遍历操作
ClearTree（&T）清空结构操作
}//ADTTree
2本程序包括二个模块
主程序模块
Voidmain（）
{调用二叉树函数
}
二叉树模块：
实现二叉树的抽象数据类型定义；
模块之间的调用关系如下：
三详细设计
里面可设计多个文件，其中stack.h如下：
#include"stdlib.h"
#include"stdio.h"
#defineTRUE1
#defineFALSE0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefcharSElemType;
typedefintStatus;
#defineOVERFLOW-1
#defineOK1
#defineERROR0
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
StatusInitStack（SqStack&S）{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack
StatusPush（SqStack&S,SElemTypee）{
if（S.top-S.base>=S.stacksize）//栈满
{S.base=（SElem
升级会员 