实验指导书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