《数据结构》实验报告.docx
- 文档编号:13223442
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:46
- 大小:128.19KB
《数据结构》实验报告.docx
《《数据结构》实验报告.docx》由会员分享,可在线阅读,更多相关《《数据结构》实验报告.docx(46页珍藏版)》请在冰点文库上搜索。
《数据结构》实验报告
《数据结构》实验报告
姓名:
关宏新
学号:
089074114
班级:
计084班
指导教师:
储岳中
实验一 线性表基本操作的实现
一、实验目的
1、掌握使用TurboC2.0上机调试线性表的基本方法;
2、掌握线性表的基本操作:
插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。
二、实验要求
1、链表插入、删除和查找算法的代码;
2、程序运行结果及分析;
3、实验总结。
三、实验内容
1、认真阅读和掌握本实验的参考程序。
2、上机运行本程序,并完善删除、查找等运算。
3、保存程序的运行结果,并结合程序进行分析。
4、按照你对链表操作需要,重新改写算法并运行,实现链表的插入、删除、查找等运算,并保存运行结果。
四、程序流程图、算法及运行结果
1-1
#include"stdio.h"
#include"stdlib.h"
#defineMAXSIZE100
structSeqList
{
intdata[MAXSIZE];
intlength;
};
typedefstructSeqList*PSeqList;
PSeqListcreaeNullList_seq()
{
PSeqListpalist=(PSeqList)malloc(sizeof(structSeqList));
if(palist!
=NULL)
{
palist->length=0;
return(palist);
}
printf("Outofspace!
!
\n");
returnNULL;
}
intisNullList_seq(PSeqListpalist)
{
return(palist->length==0);
}
intinsertPre_seq(PSeqListpalist,intp,intx)
{
intq;
if(palist->length>=MAXSIZE)
{
printf("overflow!
\n");
return(0);
}
if(p<0||p>palist->length)
{
printf("Notexist!
\n");
return(0);
}
if(isNullList_seq(palist))
{
palist->data[0]=x;
palist->length=1;
return
(1);
}
for(q=palist->length-1;q>=p;q--)
palist->data[q+1]=palist->data[q];
palist->data[p]=x;
palist->length=palist->length+1;
return
(1);
}
voidmain()
{
inti;
PSeqListlist;
list=creaeNullList_seq();
printf("插入前的顺序表为:
\n");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf("%d",list->data[i]);
}
insertPre_seq(list,5,55);
printf("\n插入后的顺序表为:
\n");
for(i=0;i
printf("%d",list->data[i]);
printf("\n");
getch();
}
1-2
#include"stdio.h"
#include"stdlib.h"
#defineMAXSIZE100
structSeqList
{
intdata[MAXSIZE];
intlength;
};
typedefstructSeqList*PSeqList;
PSeqListcreaeNullList_seq()
{
PSeqListpalist=(PSeqList)malloc(sizeof(structSeqList));
if(palist!
=NULL)
{
palist->length=0;
return(palist);
}
printf("Outofspace!
!
\n");
returnNULL;
}
intisNullList_seq(PSeqListpalist)
{
return(palist->length==0);
}
/*插入*/
intinsertPre_seq(PSeqListpalist,intp,intx)
{
intq;
if(palist->length>=MAXSIZE)
{
printf("overflow!
\n");
return(0);
}
if(p<0||p>palist->length)
{
printf("Notexist!
\n");
return(0);
}
if(isNullList_seq(palist))
{
palist->data[0]=x;
palist->length=1;
return
(1);
}
for(q=palist->length-1;q>=p;q--)
palist->data[q+1]=palist->data[q];
palist->data[p]=x;
palist->length=palist->length+1;
return
(1);
}
/*删除*/
intdeletePre_seq(PSeqListpalist,inti)
{
intj;
if(!
palist)
{
printf("表不存在");
return(-1);
}
if(i<1||i>palist->length)
{
printf("删除位置不合法");
return(0);
}
for(j=i;j
palist->data[j-1]=palist->data[j];
palist->length--;
return
(1);
}
/*检索ElementType*/
intlocationPre_seq(PSeqListpalist,intx)
{
inti=0;
if(!
palist)
{
printf("表不存在");
return(-1);
}
while(i
=x)
i++;
if(i>=palist->length)return0;
elsereturn(i+1);
}
voidmain()
{
inti;
PSeqListlist;
list=creaeNullList_seq();
printf("插入前的顺序表为:
\n");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf("%d",list->data[i]);
}
insertPre_seq(list,5,55);
printf("\n插入后的顺序表为:
\n");
for(i=0;i
printf("%d",list->data[i]);
printf("\n");
printf("删除前的顺序表为:
\n");
for(i=0;i<=9;i++)
{
insertPre_seq(list,i,i*i);
printf("%d",list->data[i]);
}
deletePre_seq(list,5);
printf("\n删除后的顺序表为:
\n");
for(i=0;i<=8;i++)
printf("%d",list->data[i]);
printf("\n");
if(locationPre_seq(list,9)==0)
printf("检索的内容不存在!
");
if(locationPre_seq(list,9)!
=0&&locationPre_seq(list,9)!
=-1)
printf("检索的内容下标为:
%d",locationPre_seq(list,9));
printf("\n");
getch();
}
实验二栈的基本操作
一、实验目的
掌握栈的基本操作:
初始化栈、判栈为空、出栈、入栈等运算。
二、实验要求
1.认真阅读和掌握本实验的算法。
2.上机将本算法实现。
3.保存程序的运行结果,并结合程序进行分析。
三、实验内容
利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
算法为:
1、定义栈的顺序存取结构
2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等)
3、定义一个函数用来实现上面问题:
(1)十进制整数X和R作为形参
(2)初始化栈
(3)只要X不为0重复做下列动作
将X%R入栈, X=X/R
(4)只要栈不为空重复做下列动作
栈顶出栈,输出栈顶元素
四、程序流程图、算法及运行结果
2-1
#include
#include
#include
#definestack_init_size100
#definestackincrement10
typedefstructsqstack
{
int*base;
int*top;
intstacksize;
}sqstack;
intStackInit(sqstack*s)
{
s->base=(int*)malloc(stack_init_size*sizeof(int));
if(!
s->base)
return0;
s->top=s->base;
s->stacksize=stack_init_size;
return1;
}
intPush(sqstack*s,inte)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(int*)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int));
if(!
s->base)
return0;
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
}
*(s->top++)=e;
returne;
}
intPop(sqstack*s,inte)
{
if(s->top==s->base)
return0;
e=*--s->top;
returne;
}
intstackempty(sqstack*s)
{
if(s->top==s->base)
{
return1;
}
else
{
return0;
}
}
intconversion(sqstack*s)
{
intn,e=0,flag=0;
printf("输入要转化的十进制数:
\n");
scanf("%d",&n);
printf("要转化为多少进制:
2进制、8进制、16进制填数字!
\n");
scanf("%d",&flag);
printf("将十进制数%d转化为%d进制是:
\n",n,flag);
while(n)
{
Push(s,n%flag);
n=n/flag;
}
while(!
stackempty(s))
{
e=Pop(s,e);
switch(e)
{
case10:
printf("A");
break;
case11:
printf("B");
break;
case12:
printf("C");
break;
case13:
printf("D");
break;
case14:
printf("E");
break;
case15:
printf("F");
break;
default:
printf("%d",e);
}
}
printf("\n");
return0;
}
intmain()
{
sqstacks;
StackInit(&s);
conversion(&s);
return0;
}
2-2
#include
#defineMAXSIZE100
structstack
{
intdata[MAXSIZE];
inttop;
};
voidinit(structstack*s)
{
s->top=-1;
}
intempty(structstack*s)
{
if(s->top==-1)return1;
elsereturn0;
}
voidpush(structstack*s,inti)
{
if(s->top==MAXSIZE-1){
printf("Stackisfull.\n");
return;
}
s->top++;
s->data[s->top]=i;
}
intpop(structstack*s)
{
if(empty(s)){
printf("Stackisempty.");
return-1;
}
return(s->data[s->top--]);
}
voidtrans(intnum)
{
structstacks;
intk;
init(&s);
while(num){
k=num%16;
push(&s,k);
num=num/16;
}
while(!
empty(&s)){
k=pop(&s);
if(k<10)
printf("%d",k);
else
printf("%c",k+55);
}
printf("\n");
}
main()
{
intnum;
clrscr();
printf("Inputanum(-1toquit):
\n");
scanf("%d",&num);
while(num!
=-1){
trans(num);
scanf("%d",&num);
}
getch();
}
实验三串的模式匹配
一、实验目的
1.利用顺序结构存储串,并实现串的匹配算法。
2.掌握简单模式匹配思想,熟悉KMP算法。
二、实验要求
1.认真理解简单模式匹配思想,高效实现简单模式匹配;
2.结合参考程序调试KMP算法,努力算法思想;
3.保存程序的运行结果,并结合程序进行分析。
三、实验内容
1、通过键盘初始化目标串和模式串,通过简单模式匹配算法实现串的模式匹配,匹配成功后要求输出模式串在目标串中的位置;
2、参考程序给出了两种不同形式的next数组的计算方法,请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法,并与简单模式匹配算法进行比较。
四、程序流程图、算法及运行结果
3-1
#include
#include
#defineMAXSIZE100
intStrIndex_BF(chars[MAXSIZE],chart[MAXSIZE])
{
inti=1,j=1;
while(i<=s[0]&&j<=t[0])
{
if(s[i]==t[j]){
i++;
j++;
}
else{
i=i-j+2;
j=1;
}
}
if(j>t[0])
return(i-t[0]);
else
return-1;
}
intmain()
{
chars[MAXSIZE];
chart[MAXSIZE];
intanswer,i;
printf("SString-->\n");
gets(s);
printf("TString-->\n");
gets(t);
printf("%d",StrIndex_BF(s,t));/*验证*/
if((answer=StrIndex_BF(s,t))>=0)
{
printf("\n");
printf("%s\n",s);
for(i=0;i printf(""); printf("%s",t); printf("\n\nPatternFoundatlocation: %d\n",answer); } else printf("\nPatternNOTFOUND.\n"); getch(); return0; } 3-2 #include #include #defineMAXSIZE100 voidget_nextval(unsignedcharpat[],intnextval[]) { intlength=strlen(pat); inti=1; intj=0; nextval[1]=0; while(i { if(j==0||pat[i-1]==pat[j-1]) { ++i; ++j; if(pat[i-1]! =pat[j-1])nextval[i]=j; elsenextval[i]=nextval[j]; } elsej=nextval[j]; } } intIndex_KMP(unsignedchartext[],unsignedcharpat[],intnextval[]) { inti=1; intj=1; intt_len=strlen(text); intp_len=strlen(pat); while(i<=t_len&&j<=p_len) { if(j==0||text[i-1]==pat[j-1]){++i;++j;} elsej=nextval[j]; } if(j>p_len)returni-1-p_len; elsereturn-1; } intmain() { unsignedchartext[MAXSIZE]; unsignedcharpat[MAXSIZE]; intnextval[MAXSIZE]; intanswer,i; printf("\nBoyer-MooreStringSearchingProgram"); printf("\n===================================="); printf("\n\nTextString-->"); gets(text); printf("\nPatternString-->"); gets(pat); get_nextval(pat,nextval); if((answer=Index_KMP(text,pat,nextval))>=0) { printf("\n"); printf("%s\n",text); for(i=0;i printf(""); printf("%s",pat); printf("\n\nPatternFoundatlocation%d\n",answer); } else printf("\nPatternNOTFOUND.\n"); getch(); return0; } 3-3 #include"stdio.h" voidGetNext1(char*t,intnext[]) { inti=1,j=0; next[1]=0; while(i<=9) { if(j==0||t[i]==t[j]) {++i;++j;next[i]=j;} else j=next[j]; } } voidGetNext2(char*t,intnext[]) { inti=1,j=0; next[1]=0; while(i<=9) { while(j>=1&&t[i]! =t[j]) j=next[j]; i++;j++; if(t[i]==t[j])next[i]=next[j]; elsenext[i]=j; } } voidmain() { char*p="abcaababc"; inti,str[10]; GetNext1(p,str); printf("Putout: \n"); for(i=1;i<10;i++) printf("%d",str[i]); GetNext2(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); printf("\n"); getch(); } 实验四二叉树操作 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。 3.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的参考程序。 2.按照对二叉树的操作需要,在创建好二叉树后再通过遍历算法验证创建结果。 3.保存程序的运行结果,并结合程序进行分析。 三、实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树,并通过遍历来验证二叉树创建正确与否,但不能创建非完全二叉树,请认真研究该程序,然后模仿教材例6.4初始化方式创建二叉树: 所有的空指针均用#表示,如教材图6-13对应的二叉树,建立时的初始序列为: AB#D##CE##F##。 四、程序流程图、算法及运行结果 4-1 #include"
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告