实验指导书Word下载.docx
《实验指导书Word下载.docx》由会员分享，可在线阅读，更多相关《实验指导书Word下载.docx（64页珍藏版）》请在冰点文库上搜索。
用类C语言或用框图描述。
3、调试报告：
调试过程中遇到的问题是如何解决的；
对设计和编码的讨论和分析。
4、算法分析与改进：
算法的时间复杂度和空间复杂度分析；
算法改进的设想。
5、经验和体会
附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。
四、实验时间
16学时。
实验一线性表顺序存储结构
一、实验目的
1、掌握使用TurboC2.0/C++/VC环境上机调试线性表的基本方法；
2、掌握线性表的基本操作：
插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。
二、实验要求
1、认真阅读和掌握本实验的程序。
2、上机运行本程序。
3、保存和打印出程序的运行结果，并结合程序进行分析。
4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、注意事项：
在磁盘上创建一个目录，专门用于存储数据结构实验的程序。
四、实验内容
实验题目1：
线性表基本操作的实现
这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。
程序如下（Turbo2.0环境下程序示例）：
#include<
stdio.h>
stdlib.h>
//顺序表的定义
#defineListSize100
typedefstruct
{intdata[ListSize];
/*向量data用于存放表结点*/
intlength;
/*当前的表长度*/
}SeqList;
voidmain（）
{voidCreateList（SeqList*L,intn）;
voidPrintList（SeqList*L,intn）;
intLocateList（SeqList*L,intx）;
voidInsertList（SeqList*L,intx,inti）;
voidDeleteList（SeqList*L,inti）;
SeqListL;
inti,x;
intn=10;
/*THELENGTHOFLIST*/
L.length=0;
//clrscr（）;
CreateList（&
L,n）;
/*CREATTHELIST*/
PrintList（&
/*PRINTTHELIST*/
printf（"
INPUTTHERESEARCHELEMENT"
）;
scanf（"
%d"
&
x）;
i=LocateList（&
L,x）;
theresearchpositionis%d\n"
i）;
/*顺序表查找*/
inputthepositionofinsert:
\n"
i）;
inputthevalueofinsert\n"
InsertList（&
L,x,i）;
/*顺序表插入*/
/*打印顺序表*/
inputthepositionofdelete\n"
DeleteList（&
L,i）;
/*顺序表删除*/
getchar（）;
/*打印顺序表*/
}
/*顺序表的建立：
*/
voidCreateList（SeqList*L,intn）
{inti;
printf（"
pleaseinputnnumbers\n"
for（i=1;
i<
=n;
i++）
{scanf（"
L->
data[i]）;
length=n;
/*顺序表的打印：
voidPrintList（SeqList*L,intn）
thesqlistis\n"
%d"
L->
/*顺序表的查找：
intLocateList（SeqList*L,intx）
=10;
if（（L->
data[i]）==x）return（i）;
return（0）;
/*顺序表的插入：
voidInsertList（SeqList*L,intx,inti）
{intj;
for（j=L->
length;
j>
=i;
j--）
data[j+1]=L->
data[j];
data[i]=x;
length++;
/*顺序表的删除：
voidDeleteList（SeqList*L,inti）
{intj;
for（j=i;
j<
=（L->
length）-1;
j++）
data[j]=L->
data[j+1];
实验题目2：
集合求并
说明：
分别用两个线性表对集合进行表示，将其中一个集合并到另一个集合。
程序如下（C＋＋/VC环境）
#defineINITSIZE10
#defineINCREASEMENT2
#defineOVERFLOW-1
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#include"
iostream.h"
#include"
stdio.h"
stdlib.h"
malloc.h"
typedefintStatus;
typedefcharElemType;
typedefstruct{
ElemType*elem;
intlistsize;
}SqList;
StatusInitList（SqList&
L）{
L.elem=（ElemType*）malloc（INITSIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize=INITSIZE;
returnOK;
}//InitList
StatusListInsert（SqList&
L,inti,ElemTypee）{
if（L.length>
=L.listsize）{
L.elem=（ElemType*）realloc（L.elem,（L.listsize+INCREASEMENT）*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize=L.listsize+INCREASEMENT;
}
L.elem[i]=e;
L.length++;
}//ListInsert
StatusCreateList（SqList&
ElemTypee;
cin>
>
e;
while（e!
='
!
'
）{
L.elem[L.length++]=e;
cin>
}//CreateList
StatusGetElem（SqListL,inti,ElemType&
e）{
if（i<
1||i>
L.length）returnERROR;
e=L.elem[i-1];
Statusequal（ElemTypea,ElemTypeb）{
if（a==b）returnTRUE;
elsereturnERROR;
}//equal
StatusElemLocate（SqListL,ElemTypee,Status（*compare）（ElemType,ElemType））{
inti;
for（i=1;
=L.length;
if（（*compare）（e,L.elem[i-1]））returnTRUE;
returnERROR;
}//ElemLocate
voidUnion（SqListLa,SqListLb,SqList&
Lc）{
inti,j,k;
i=j=k=0;
ElemTypea,b;
while（i<
La.length）{
GetElem（La,i+1,a）;
i++;
（ElemLocate（La,b,equal）））
ListInsert（Lc,k++,a）;
while（j<
Lb.length）{
GetElem（Lb,j+1,b）;
j++;
ListInsert（Lc,k++,b）;
return;
voidmain（void）{
SqListLa,Lb,Lc;
InitList（La）;
InitList（Lb）;
InitList（Lc）;
cout<
<
"
PleaseCreateListA:
;
CreateList（La）;
ShowtheendA:
for（i=0;
La.length;
cout<
La.elem[i]<
'
\n'
PleaseCreateListB:
CreateList（Lb）;
ShowtheendB:
Lb.length;
Lb.elem[i]<
Union（La,Lb,Lc）;
ShowtheendC:
for（i=0;
Lc.length;
Lc.elem[i]<
}//main
实验题目3：
报数问题
编号为1，2，·
·
，n的n个人围坐在一圆桌旁，从第s个人开始报数，报到第m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。
例如，设s=1，m=4，n=8，则退席的人的编号依次为4，8，5，2，1，3，7，6。
1、存储结构
（1）以顺序表为存储结构
（2）以循环链表为存储结构
typedefstructlnode{
intdata;
structlnode*next;
}lnode；
2、算法设计
（1）voidjosephus_1（intp[],intm,intn）{
inti,j,t;
=n-1;
i++）p[i]=i+1;
//p[0]..p[n-1]：
n个人
t=0;
//第一次报数的位置（第一人的位置）
for（i=n;
i>
=1;
i--）{
t=（t+m-1）%i;
//t：
定位于第m人，i：
当前圆桌上的人数，%：
实现环（圆桌）的处理
p[t]<
"
//输出第m人信息（第m人报数）
for（j=t+1;
=i-1;
j++）
p[j-1]=p[j];
//元素前移（第m人退席，删除第m人）
（2）voidjosephus_2（lnode*r,intm,intn）{
//r：
（不带头结点的）单向循环链表的尾指针
Lnode*p=r;
//p：
指向尾指针for（i=1;
++i）{
for（j=1;
=m-1;
++j）
p=p->
next;
//p后移m-1次，定位于m-1处（要退席的人之前）
s=p->
//s定位于m人（要退席的人）
cout<
p->
data<
//第m人报数
p->
next=s->
deletes;
//第m人退席，删除第m人
实验二链表应用
1．掌握握单链表的基本操作：
插入、删除、查找等运算。
1．认真阅读和掌握本实验的程序。
2．上机运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、实验内容
单链表基本操作的实现
这个程序中演示了单链表的创建、插入、删除和查找。
程序如下：
#include<
malloc.h>
typedefstructnode{
intdata;
structnode*next;
}NODE;
/******************创建链表************************/
NODE*Create（）{
NODE*p,*head;
intx;
head=（NODE*）malloc（sizeof（NODE））;
head->
next=null;
Inputdata,-1toEnd!
while（x!
=-1）{
p=（NODE*）malloc（sizeof（NODE））;
data=x;
next=head->
next=p;
return（head）;
/*****************单链表的输出*************************/
voidOutput（NODE*head）{
NODE*p;
p=head;
BegintodumptheLinkList...\n"
while（p->
next!
=NULL）{
->
p->
next->
data）;
\nTheLinkListended!
/*******************统计单链表的长度***********************/
intListlen（NODE*head）{
inti=0;
NODE*p=head;
return（i）;
/******************单链表的定位,取第i个结点输出************************/
intGet（NODE*head,inti）{
intj=0;
NODE*p=head;
while（p->
next&
&
i）{
j++;
p=p->
if（!
next||j>
i）return（0）;
elsereturn（p->
/******************单链表的删除************************/
voidDel（NODE*head,inti）{
i-1）{
i-1）printf（"
thepositioniswrong\n"
else
next=p->
/******************单链表的插入************************/
voidIns（NODE*head,inti,inte）{
NODE*p=head,*q;
Wrongposition\n"
）;
else{
q=（NODE*）malloc（sizeof（NODE））;
q->
data=e;
next=q;
/*******************主函数***********************/
voidmain（）{
NODE*head;
inti,element;
head=Create（）;
Output（head）;
length=Listlen（head）;
thelengthofthelinkis%d\n"
length）;
inputtheorder:
element=Get（head,i）;
theelementoftheorderis%d\n"
element）;
inputthedelposition\n"
Del（head,i）;
Inputtheinsertposionandelement:
%d%d"
i,&
element）;
Ins（head,i,element）;
线性表归并的链式表示实现（C＋＋/VC环境）
typedefintstatus;
typedefintElemType;
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
statusInitList（LinkList&
L=（LinkList）malloc（sizeof（LNode））;
L）exit（-2）;
L->
next=NULL;
returnOK;
voidCreateList（LinkList&
L,intn）{
LNode*p,*q;
L->
q=L;
n;
++i）{
p=（LinkList）malloc（sizeof（LNode））;
data;
q->
q=p;
statusMergesort（LinkList&
A,LinkList&
B,LinkList&
C）{
LNode*Pa,*Pb;
Pa=A->
Pb=B->
while（Pa&
Pb）{
if（Pa->
Pb->
data）{A->
next=Pa->
//把Pa结点从链表A中删除
Pa->
next=C->
C->
next=Pa;
//把*Pa逆位序加入链表C
//取链表A的下一个结点
else{B->
next=Pb->
//把Pb结点从链表B中删除
Pb->
next=Pb;
//把*Pb逆位序加入链表C
Pb=B->
//取链表B的下一个结点
while（Pa）{A->
whi
升级会员 