数据结构实验报告.docx
- 文档编号:7316945
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:54
- 大小:304.54KB
数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告.docx(54页珍藏版)》请在冰点文库上搜索。
数据结构实验报告
南昌大学实验报告
学生姓名:
吕金石学号:
6100408024专业班级:
数字媒体081班
实验类型:
■验证□综合□设计□创新实验日期:
2010.3.26实验成绩:
实验1:
线性表及其应用
一、实验目的
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。
二、问题描述
1、构造一个空的线性表L。
2、在线性表L的第i个元素之前插入新的元素e;
3、在线性表L中删除第i个元素,并用e返回其值。
三、实验要求
1、分别利用顺序和链表存储结构实现线性表的存储,并设计出在不同的存储结构中线性表的基本操作算法。
2、在实验过程中,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
#include
#include
#defineMAXNUM100
#defineINCREMENT10
typedefstruct{
int*elem;
intlength;
intlistsize;
}SqList;
voidCreatList(SqList&l)
{intn;
cout<<"请输入数据的个数:
";
cin>>n;
l.elem=(int*)malloc(MAXNUM*sizeof(int));
for(inti=0;i {cout<<"第"< "; cin>>l.elem[i]; l.length=n; l.listsize=MAXNUM; } } voidPrintList(SqList&l) { cout<<"顺序为表: "; for(inti=0;i cout< cout< } voidListInsert(SqList&l,intj,intx) { int*newbase; int*q,*p; cout<<"请输入要插入的位置: "; cin>>j; cout<<"要插入的元素是: "; cin>>x; cout<<"在第"< "< if(l.length>=l.listsize) { newbase=(int*)realloc(l.elem,(l.listsize+INCREMENT)*sizeof(int)); l.elem=newbase; l.listsize+=INCREMENT; } q=&(l.elem[j-1]); for(p=&(l.elem[l.length-1]);p>=q;--p)*(p+1)=*p; *q=x; ++l.length; } voidPrintInsert(SqList&l) { cout<<"插入后的顺序为: "; for(inti=0;i cout< cout< } voidListDelete(SqList&l,intj) {int*p,*q;intx; cout<<"请输入要删除的位置: "; cin>>j; p=&(l.elem[j-1]); q=l.elem+l.length-1; for(++p;p<=q;++p) *(p-1)=*p; --l.length; x=l.elem[j-2]; cout<<"要删除第"< "< } voidPrintDelete(SqList&l) {cout<<"删除后的顺序表为: "; for(inti=0;i cout< cout< } voidmain() {SqListl; intj=0; intx=0; cout<<"创建顺序表"< CreatList(l); PrintList(l); ListInsert(l,j,x); PrintInsert(l); ListDelete(l,j); PrintDelete(l); } 六、实验结果 七、实验总结 未实现倒数第二行的“要删除第二个元素: ”输出数字与程序的一致,删除的位置不同,输出的元素不同。 南昌大学实验报告 学生姓名: 吕金石学号: 6100408024专业班级: 数字媒体081班 实验类型: □验证□综合■设计□创新实验日期: 2010.5.29实验成绩: 实验2: 串及其应用 一、实验目的 掌握串类型的实现方法和文本模式匹配方法,熟悉一般文字处理软件的设计方法。 二、问题描述 全屏幕文本编辑器通过终端对文本文件进行创建、插入、删除、修改、存储等操作。 用户可完成对文本的插入、删除、修改等功能。 三、实验要求 1、对光标实现如下操作: 上、下、左、右移动一个字符位置;向前、后翻页;光标移至文件首、尾;光标移至本行首、尾。 2、实现基本编辑命令: I----在当前光标前插入内容,按ESC结束 F----在当前光标后插入内容,按ESC结束 D----删除光标所在行 ND---删除光标位置开始的n行 N-----删除光标上的字符 W----将修改后的文本保存下来 Q----退出编辑状态。 四、实验环境 PC微机 DOS操作系统或Windows操作系统 TurboC程序集成环境或VisualC++程序集成环境 五、实验步骤 1、在内存开辟可容纳80行大小的编辑工作区和buffer的修改缓冲区。 2、要求用户输入编辑文件名,对读入的文件建立相应的页表和行表,在文本编辑程序中设立页指针、行指针、字符指针,分别指示当前操作的页、行、字符。 3、执行插入、删除、修改操作时,将本次操作内容放到缓冲区; 4、操作确定后,将修改后的文本存到文件中。 六、测试数据 自行设定。 七、算法设计 串的基本操作: 一、串赋值: StatusStrAssign(HString&T,char*chars) {//生成一个其值等于串常量chars的串T inti,j; if(T.ch) free(T.ch);//释放T原有空间 i=strlen(chars);//求chars的长度i if(! i) {//chars的长度为0 T.ch=NULL; T.length=0; } else {//chars的长度不为0 T.ch=(char*)malloc(i*sizeof(char));//分配串空间 if(! T.ch)//分配串空间失败 exit(OVERFLOW); for(j=0;j T.ch[j]=chars[j]; T.length=i; } returnOK; } 二、串初始化 voidInitString(HString&T) {//初始化(产生空串)字符串T。 另加 T.length=0; T.ch=NULL; 八、实验内容和过程 实验程序: #include #include #include #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 typedefintStatus;//Status是函数的类型,其值是函数结果状态代码,如OK等 structHString { char*ch;//若是非空串,则按串长分配存储区,否则ch为NULL intlength;//串长度 }; /***************文本编辑器的程序**********************/ #defineMAX_LEN50//文件最大行数 #defineLINE_LEN80//每行字符数最大值+1 #defineNAME_LEN20//文件名最大长度(包括盘符、路径)+1 StatusStrAssign(HString&T,char*chars) {//生成一个其值等于串常量chars的串T inti,j; if(T.ch) free(T.ch);//释放T原有空间 i=strlen(chars);//求chars的长度i if(! i) {//chars的长度为0 T.ch=NULL; T.length=0; } else {//chars的长度不为0 T.ch=(char*)malloc(i*sizeof(char));//分配串空间 if(! T.ch)//分配串空间失败 exit(0); for(j=0;j T.ch[j]=chars[j]; T.length=i; } returnOK; } voidInitString(HString&T) {//初始化(产生空串)字符串T。 另加 T.length=0; T.ch=NULL; } voidStrPrint(HStringT) {//输出T字符串。 另加 inti; for(i=0;i printf("%c",T.ch[i]); printf("\n"); } //全局变量 HStringT[MAX_LEN]; charstr[LINE_LEN],filename[NAME_LEN]=""; FILE*fp; intn=0;//文件行数 voidOpen() {//打开文件(新或旧) inti; if(filename[0])//文件已打开 printf("已存在打开的文件\n"); else { printf("请输入文件名(可包括盘符、路径,不超过%d个字符): ",NAME_LEN-1); scanf("%s%*c",filename); fp=fopen(filename,"r"); if(fp)//已存在此文件 { do { fgets(str,LINE_LEN,fp); i=strlen(str); str[i-1]=0;//将10强制改为0 i--; if(i>0) { StrAssign(T[n],str); n++; if(n>MAX_LEN) { printf("文件太大\n"); return; } } }while(i>0); fclose(fp); } else printf("新文件\n"); } } voidList() {//显示文件内容 inti; for(i=0;i { printf("%d: ",i+1); StrPrint(T[i]); } getchar(); } voidInsert() {//插入行 inti,k,m; printf("从第K行开始插插入m行,请输入k和m的值: "); scanf("%d%d%*c",&k,&m); if(n+m>MAX_LEN) { printf("插入行太多\n"); return; } if(n>=k-1&&k>0) { for(i=n-1;i>=k-1;i--) T[i+m]=T[i]; n+=m; printf("请顺序输入待插入内容: \n"); for(i=k-1;i { gets(str); InitString(T[i]); StrAssign(T[i],str); } } else printf("行超出范围\n"); } voidDelete() {//删除行 inti,k,m; printf("从第k行起删除m行,请输入km: "); scanf("%d%d%*c",&k,&m); if(n>=k+m-1&&k>0) { for(i=k-1+m;i T[i-m]=T[i]; for(i=n-m;i InitString(T[i]); n-=m; } else printf("行超出范围\n"); } voidSave() {//存盘 inti; getchar(); fp=fopen(filename,"w"); if(fp) { for(i=0;i { T[i].ch[T[i].length]=0; fputs(T[i].ch,fp); fputc(10,fp); } fputc(10,fp); fclose(fp); } else printf("存盘失败\n"); } voidmain() { Statuss=TRUE; inti; chark; for(i=0;i InitString(T[i]); while(s) { printf("******************************************\n"); printf("请选择相关的操作: \n"); printf("O.打开文件L.显示文件内容\n"); printf("I.插入相应的内容D.删除相应的某几行\n"); printf("W.将修改后的文本保存下来Q.退出编辑状态\n"); printf("******************************************\n"); k=getchar(); switch(k) { case'O': Open();break; case'L': List();break; case'I': Insert();break; case'D': Delete();break; case'W': Save(); case'Q': s=FALSE; } } }/***************文本编辑器的程序**********************/ 测试数据: 测试文档XLQ测试前: 打开文件: 显示文件内容: 插入相应内容: 删除某几行: 保存文本: 退出编辑状态: 测试后文本: 九、实验总结 在经过对串的学习后,我们需要进行实际上机实验,运行程序,达到理论联系实际的目的,使我们更好的掌握该算法。 这次实验要求我们熟悉串的基本操作,掌握串类型的实现方法和文本模式匹配方法,熟悉一般文字处理软件的设计方法。 要求全屏幕文本编辑器通过终端对文本文件进行创建、插入、删除、修改、存储等操作,用户可完成对文本的插入、删除、修改等功能。 这次编的程序可以实现创建串、比较串、合并串和截取串的目的。 函数中共有StrAssign()(串的创建)、StrCompare()(串的比较)、Comcat()(串的合并)、SubString()(返回串的一部分)四个实现函数以及一个print()函数用来方便的输出整个串。 在主函数中对他们分别进行调用,使整个程序脉络比较清晰,可读性加强,但用的函数较少,整个程序相对比较复杂。 南昌大学实验报告 学生姓名: 吕金石学号: 6100408024专业班级: 数字媒体081班 实验类型: □验证□综合■设计□创新实验日期: 2010.6.7实验成绩: 实验3: 二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构,本单元的实验达到熟悉二叉树的存储结构的特性,以及如何应用树结构解决具体问题。 二、问题描述 首先,掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。 其次,以二叉树表示算术表达式的基础上,设计一个十进制的四则运算的计算器。 如算术表达式: a+b*(c-d)-e/f 三、实验要求 1、如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树,分别计算 a)统计叶子结点的个数。 b)求二叉树的深度。 2、十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、自动完成求值运算和输出结果。 四、实验环境 PC微机 DOS操作系统或Windows操作系统 TurboC程序集成环境或VisualC++程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树; 2、设计求叶子结点个数算法和树的深度算法; 3、根据表达式建立相应的二叉树,生成表达式树的模块; 4、根据表达式树,求出表达式值,生成求值模块; 5、程序运行效果,测试数据分析算法。 设计程序代码如下: #include #include #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 #defineERROR0 #defineNUMBER1 #defineSIMBLE2 intOP[8]={'+','-','*','/','(',')','#',0}; typedefunion { intOperator;//操作符 floatOperand;//操作数 }Int_Float; //表达式树 typedefstructBinaryTreeNode { Int_FloatData; intIsOperator; structBinaryTreeNode*RChild; structBinaryTreeNode*LChild; }BiTreeNode,*lpBiTreeNode; //栈 typedefstruct{ lpBiTreeNode*base; lpBiTreeNode*top; intstacksize; }SqStack; intInitStack(SqStack&s) { s.base=(lpBiTreeNode*)malloc(STACK_INIT_SIZE*sizeof(lpBiTreeNode)); if(! s.base) return0; s.top=s.base; s.stacksize=STACK_INIT_SIZE; return1; } intPush(SqStack&s,lpBiTreeNodee) { if(s.top-s.base>=s.stacksize) { s.base=(lpBiTreeNode*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(lpBiTreeNode)); if(! s.base) return0; s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top=e; s.top++; return1; } intPop(SqStack&s,lpBiTreeNode&e) { if(s.top==s.base) return0; s.top--; e=*s.top; return1; } lpBiTreeNodeGetTop(SqStacks) { lpBiTreeNodee; if(s.top==s.base) returnNULL; e=*(s.top-1); returne; } intIsEmpty(SqStacks) { if(s.top==s.base) return1; else return0; } intIn(intc,int*op)//判断c是否在op中,op为以结尾的数组 { while(*op! =0) { if(c==*op) return1; op++; } return0; } intPrecede(inttheta1,inttheta2) { inti,j; intop_look[7][7]= {{'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',''}, {'>','>','>','>','','>','>'}, {'<','<','<','<','<','','='} }; switch(theta1) { case'+': i=0; break; case'-': i=1; break; case'*': i=2; break; case'/': i=3; break; case'(': i=4; break; case')': i=5; break; case'#': i=6; break; default: return0; } switch(theta2) { case'+': j=0; break; case'-': j=1; break; case'*': j=2; break;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告