数据结构实习报告.docx
- 文档编号:14470043
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:19
- 大小:298.48KB
数据结构实习报告.docx
《数据结构实习报告.docx》由会员分享,可在线阅读,更多相关《数据结构实习报告.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构实习报告
PracticeReportforDataStructuresandAlgorithmAnalysis
DataStructuresCourseReport
Candidate:
关亚军
StudentNumber:
20121002868
Major:
CommunicationEngineering
Supervisor:
Wurangzhong
ChinaUniversityofGeosciences(Wuhan)
Wuhan,Hubei430074,P.R.China
Jan10,2014
ChinaUniversityofGeosciences,FacultyofMechanicsandElectronicInformation
目录
一、数组实现线性表
1.1 程序功能
1.2 算法分析
1.3 运行结果
二、堆栈与队列
2.1 实验目的
2.2 程序内容
2.3 问题描述与分析
三、稀疏矩阵
4.1 程序功能
4.2 算法分析
4.3 运行结果
四、AVL树算法的实现
4.1程序要求
4.2 程序功能
4.3 算法分析
4.4 运行结果
五、字符串的模式匹配
5.1 程序功能
5.2 算法分析
5.3 运行结果
六、查找与排序
6.1 程序功能
6.2 算法分析
6.3 运行结果
七、路由算法
7.1 程序功能
7.2 算法分析
7.3 运行结果
八、实习心得
一、数组实现线性表
1、程序功能:
用c语言用c语言编写一个演示程序,首先建立一个空表,然后根据用户选择,能够在线性表的任意位置实现插入元素、删除元素、初始化线性表、查找某一元素在线性表中的位置等功能。
(1)建立线性表的功能
输入的形式和输入的范围:
调用出入函数,输入插入的位置和数值。
输出的形式:
调用输出函数,按顺序输出线性表所插入的值,以及所对应功能的值。
(2)插入功能
输入的形式和输入值的范围:
输入一个表示位置的正整数和一个表示插入元素值的正整数,两个正整数之间用逗号隔开,出入位置的和法取值范围是1 输出的形式: 如果输入的参数合法,则按顺序显示插入后的线性表,否则显示错误。 (3)删除功能 输入的形式和输入值的范围: 输入一个表示删除位置或要删除的元素值的正整数,删除位置或删除元素值的取值范围是1 输出的形式: 如果输入参数合法,则按顺序显示删除后线性表中的各个元素值,否则显示参数错误的信息。 (4)打印功能 输出的形式: 调用输出函数,按顺序输出线性表所插入的值,以及所对应功能的值。 (5)查找功能 输入的形式和输入值的范围: 输入一个要查找的元素值,元素值的合法取值范围是正整数。 输出的形式: 如果存在要查找的元素,则显示要查找元素的位置,否则显示参数错误信息 2、算法分析: (1)为了实现上述程序功能,需要定义一个简化的线性表抽象数据类型: typedefintElemType; typedefstructSqList { ElemTypedata[MaxLine];/*存放顺序表的数组*/ intlength;/*顺序表的长度*/ }L; 基本操作: (1)初始化线性表voidInitList(SqList&L) 操作前提: L是一个未初始化的线性表 操作结果: 将L初始化成一个空的线性表获得线性表的长度GetLength(SqList&L) 操作前提: 线性表L存在 操作结果: 返回线性表的长度 获得线性表中指定位置元素ElemTypeGetElem(SqList&L,inti) 向空表指定位置插入元素voidListInsert(SqList&L,inti,ElemTypex) 操作前提: L是一个还有位置的线性表 操作结果: 将元素插入到指定位子并返回线性表的长度 删除指定位置的元素值voidListDelete(SqList&L,inti) 操作前提: 线性表L存在 操作结果: 将线性表中指定位置的元素值删除,并返回线性表的长度 查找线性表中的元素ListFind(SqList&L,inti) 操作前提: 线性表L存在 操作结果: 在线性表L中查找指定元素e,若存在该元素返回该元素在表中的位置,否则提示错误 输出线性表元素ListPrintf(SqList&L) 操作前提: 线性表存在操作结果: 输出整线性表L的所有元素值 (2)本程序共有6函数: 主函数main() 菜单函数menu() 初始化线性表函数voidInitList(SqList&L)获得线性表的长度函数GetLength(SqList&L) 插入函数voidListInsert(SqList&L,inti,ElemTypex) 删除函数voidListDelete(SqList&L,inti) 查找函数ListFind(SqList&L,inti) 打印函数ListPrintf(SqList&L) 各函数的关系如下: 主函数Main()调用菜单函数menu() 菜单函数menu()调用初始化线性表函数InitList()、获得线性表的长度函数GetLength(SqList&L)、插入函数voidListInsert(SqList&L,inti,ElemTypex)、删除函数voidListDelete(SqList&L,inti)、查找函数ListFind(SqList&L,inti)、打印函数ListPrintf(SqList&L) 3、运行结果: 插入部分: 二、堆栈与队列 一.实验目的: 1. 会定义顺序栈和链栈的结点类型。 2. 掌握栈的插入和删除结点在操作上的特点。 3. 熟悉对栈的一些基本操作和具体的函数定义。 4. 会定义顺序队列和链队列的结点类型。 二.程序内容: 程序1 该程序的功能是实现顺序栈的定义和操作。 该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。 typedef int DataType; /* 定义DataType为int类型 */ #define MAXSIZE1024 typedef struct {DataType data[MAXSIZE]; int top; }SeqStack; /* 栈的结点类型 */ 程序2: 试利用堆栈将队列中的元素逆置。 程序3: 编写括号匹配算法。 1、队列的抽象数据类型定义: ADT Queue{数据对象: D={|∈ElemSet, i=1,2,...,n, n>=0} 数据关系: R1={<,>|,∈D, i=2,...,n} 基本操作: InitQueue(&Q) 构造一个空队列Q QueueEmpty(Q) 判断队列是否为空 QueueLenght(Q) 返回队列Q的元素个数,即队列的长度 GetHead(Q,&e) 取队列Q的队头元素,并用e返回 EnQueue(&Q,e)将元素e入队列 DeQueue(&Q,&e) 删除非空队列Q的队头元素,并用e返回其值 }ADT Queue 2、队列的表示: 队列有两种表示方法: 链队列、循环队列(顺序队列)。 (1)链队列的表示: typedef struct QNode{ QElemType data; struct QNode *next;}QNode,*QueuPtr;typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; (2) 循环队列的表示 编写一个程序,其功能是实现顺序栈的定义和操作。 该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。 利用堆栈将队列中的元素逆置。 编写括号匹配算法 假设有几个作业运行。 如果都需要请求CPU,则可以让作业按先后顺序排队,每当CPU处是完一个作业后,就可以接受新的作业,这时队列中队头的作业先退出进行处理。 后来的作业排在队尾。 此题算法跟模拟服务台前的排队现象问题相似,假定只有一个CPU,但为了防止一个作业占用CPU太久,可规定每个作业一次最长占用CPU的时间(称时间片),如果时间片到,作业未完成,则此作业重新进入等待队列,等到下次占有CPU时继续处理。 三.问题描述和分析: 1、实现顺序栈的定义和操作共有如下几个环节: a) 初始化顺序栈 b) 检查顺序栈是否为空 c) 置为空栈 d) 把元素压入栈,使其成为新的栈顶元素 e) 把栈顶元素弹出 f) 取栈顶元素 g) 输出顺序栈中的元素 2.利用堆栈队列的元素逆置的流程图如下 3. 括号匹配问题的转化: 在算法中设置一个栈,每读入一个括号,若是右括号,则或者使 置于栈顶的最急迫的期待得以消解,或者是不合法的情况,若是左括号,则作为一个新的更急迫的期待压入栈中,自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。 三、稀疏矩阵 1、程序功能: 用c语言用c语言编写一个演示程序,根据用户选择,能够实现稀疏矩阵的表示、转置和乘法。 (1)初始化 (2)创建三元组 (3)快速转置 (4)打印 (5)乘法 2、算法分析: (1)为了实现上述程序功能,需要定义一个简化的抽象数据类型: typedefstruct{ inti,j;//位置 inte;//数据元素 }Triple;//三元组 #defineMAXSIZE100 typedefstruct{ Tripledata[MAXSIZE+1]; intrpos[MAXSIZE+1]; intmu,nu,tu;//mu行数nu列数tu总长度 }Tsmatrix;//矩阵 基本操作: 1.初始化Tsmatrix*Init(Tsmatrix*M,introw,intcol,intnum) 操作结果: 创建稀疏矩阵M 2.创建三元组Tsmatrix*creatarray(Tsmatrix*M,introw,intcol) 操作条件: 存在稀疏矩阵M 操作结果: 创建三元组 3.快速转置Tsmatrix*fasttrans(Tsmatrix*M,Tsmatrix*T) 操作条件: 存在稀疏矩阵M 操作结果: 求稀疏矩阵M转置矩阵T 4.打印voidprint(Tsmatrix*T,intx,inty) 操作条件: 存在稀疏矩阵M 操作结果: 输出稀疏矩阵M 5.乘法Tsmatrix*Cheng(Tsmatrix*M,Tsmatrix*T,Tsmatrix*G) 操作条件: 稀疏矩阵M的列数等于T的行数 操作结果: 求稀疏矩阵的乘积G=M*T (2)本程序共有6函数: 主函数main() 菜单函数menu() 初始化函数Tsmatrix*Init(Tsmatrix*M,introw,intcol,intnum) 创建三元组函数Tsmatrix*creatarray(Tsmatrix*M,introw,intcol) 快速转置函数Tsmatrix*fasttrans(Tsmatrix*M,Tsmatrix*T) 打印函数voidprint(Tsmatrix*T,intx,inty) 乘法函数Tsmatrix*Cheng(Tsmatrix*M,Tsmatrix*T,Tsmatrix*G) 各函数的关系如下: 主函数Main()调用菜单函数menu() 菜单函数menu()调用初始化函数Tsmatrix*Init(Tsmatrix*M,introw,intcol,intnum) 、创建三元组函数Tsmatrix*creatarray(Tsmatrix*M,introw,intcol)、快速转置函数Tsmatrix*fasttrans(Tsmatrix*M,Tsmatrix*T)、打印函数voidprint(Tsmatrix*T,intx,inty) 、乘法函数Tsmatrix*Cheng(Tsmatrix*M,Tsmatrix*T,Tsmatrix*G) 3、运行结果: 创建转置矩阵 乘法矩阵: 四、实现AVL树的各种算法 一、程序要求: 1、输入形式及输入值范围 : 输入形式: 当树没创建时,先在第一行输入树的节点数目n,第二行再输入n个大于0的不重复整数,以空格隔开。 删除结点时,直接输入要删除结点的值。 输入范围: 所有int类型的大于零的值,注意不能重复输入。 2、输出形式 输出形式: 各种遍历形式输出均用空格隔开,删除结点时,若成功,打印成功信息,若失败,则打印失败的信息。 二、程序功能 : 程序里面的函数可以实现平衡二叉树的以下功能: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (递归) (3) 前序、中序、后序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字 (6) 交换各结点的左右子树 (7) 求二叉树的深度 (8) 叶子结点数 (9) 删除某结点 三、算法分析 : 1、使用的测试数据: 第一组: 输入顺序是54321,树的三种遍历是42135,12345,13254.正确。 删除结点5后是2143,1234,1342.正确。 第二组: 输入顺序是76543218,树的三种遍历是42136578,12345678,13258764.删除结点7后是4213568,1234658,1326854。 第三组: 输入顺序是45 12 33 60 10.树的三种遍历是33 12 10 45 60,10 12 33 45 60, 10 12 60 45 33.删除60后是33 12 10 45,10 12 33 45,10 12 45 33. 2、算法的效率分析和改进设想: 删除和插入的算法均是用了二叉排序树的性质来进行,故算法的效率大概为O(lgn)。 而遍历的非递归算法均是以栈结构实现。 故应该以O(n)的效率进行。 由于算法设计的不完善,删除和插入函数的旋转操作都可以进一步提升效率,判断情况也可以尽量减少冗余。 这样可以让时间复杂度前面的系数变小,从而提高算法整体效率。 四、运行结果: 五、字符串的模式匹配 1、程序功能: 用c语言用c语言编写一个演示程序,实现字符串的模式匹配。 2、算法分析: (1)为了实现上述程序功能,需要定义一个简化的抽象数据类型: typedefstruct { charch[maxsize]; intlen; }sqstring; 基本操作: 1.创建串voidstrassign(sqstring&str,charcstr[]) 操作结果: 创建串str 2.输出串voiddispstr(sqstrings) 操作条件: 存在串s 操作结果: 输出串s 3.用kmp算法进行模式匹配 操作条件: 存在串s,t 操作结果: 进行模式匹配,返回t在s中的位置 (2)本程序共有6函数: 主函数main() 创建串函数voidstrassign(sqstring&str,charcstr[]); 输出串函数voiddispstr(sqstrings); 模式串求next的值函数voidgetnext(sqstringt,intnext[]); kmp算法函数intkmpindex(sqstrings,sqstringt); 求nextval的值函数voidgetnextval(sqstringt,intnextval[]); 3、程序展示: #include #include #include"Kmp.h" voidmain() { inti,j; intnext[maxsize],nextval[maxsize]; sqstrings,t; strassign(s,"abkcabcdabcdeabcdefabcdefg"); strassign(t,"abcdeabcdefab"); printf("串S: ");dispstr(s); printf("串t: ");dispstr(t); getnext(t,next); getnextval(t,nextval); printf("i"); for(i=0;i printf("%4d",i); printf("\n"); printf("t[i]"); for(i=0;i printf("%4c",t.ch[i]); printf("\n"); printf("next"); for(i=0;i printf("%4d",next[i]); printf("\n"); printf("nextval"); for(i=0;i printf("%4d",nextval[i]); printf("\n"); printf("kmp算法: \n"); j=kmpindex(s,t); if(j==-1)printf("串匹配失败\n"); elseprintf("t在s中的位置%d\n",j); } 4、运行结果: 串s: abcabcdabcdeabcdefabcdefg 串t: abcdeabcdefab 六、查找和排序算法 1、程序功能 实现比较高效的排序,冒泡排序,插入排序效率比较低,shell排序可以在很短的时间内将顺序排列好。 2、算法分析 用随机数的方法产生我们所需的数组,然后再通过shell排序来实现快速的对这些数进行排序shell排序通过计较一定间隔的元素来工作,各趟计较所用的距离随着算法的的进行而减小,直到只比较相邻元素的最后一趟排序为止。 因此希尔排序也叫做缩小增量排序。 七、路由算法 1、程序功能 1、采用邻接矩阵,完成网的建立; 2、利用普里母算法求网的最少生成树,并输出结果。 2、算法分析 1.设计思想 克鲁斯卡尔算法思想是: 假设连通图N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。 在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。 以此类推,直至T中所有顶点都在同一连通分量上为止。 2.程序说明 intLocateVex(MgraphG,Vertexu),矩阵求点u所在位置; voidCreateGraph(Mgraph/ALGraph&G),建立带权邻接矩阵; voidkruskal(MGraphG),邻接矩阵的克鲁斯卡尔算法; intminimum(ALGraph/MGraphG,structarrywq[]),邻接表/邻接矩阵求最小的权值; 邻接矩阵的储存结构如下 typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/ structMGraph {Vertexvexs[MAX_VERTEX_NUM];/*顶点向量*/ AdjMatrixarcs;/*邻接矩阵*/ intvexnum,arcnum;/*顶点数和弧数*/ }; 三、运行结果: 8、实习心得: 数据结构确实是一门很难的课程,开始时感觉完全无从下手,但是通过短暂的两次实习,让本来基础不是很好的我有了很大的提高。 不仅让我对c语言进行了一轮复习,更重要的是对数据结构的几章重要内容有了深刻的认识并学会了如何在实践中运用上课学到的理论知识,在实习过程中,加深了对这些知识的理解,学会了对其的运用。 同时锻炼了自己的总体分析解决问题的能力,对c语言的编程能力也得到了一定的提高。 总之,我们需要通过实习锻炼出理论与实际相结合来解决问题的能力,在解决问题的过程中一定要细心,做实验时,一定要亲力亲为,务必要将每个步骤,每个细节弄准确。 因为个别的细节问题导致我们在某个问题上浪费很多不必要的时间,所以说细心很重要! 感谢实习过程中同学和吴老师的指导,数据结构的课程实习结束了,我需要学习的知识还有很多,我会继续努力了解新知识,提高自己解决这方面问题的能力!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实习 报告