数据结构串的操作实验报告
实验报告
课程数据结构实验名称实验三串
学号姓名实验日期：
串的操作
实验目的：
1. 熟悉串类型的实现方法，了解简单文字处理的设计方法；
2. 熟悉C语言的字符和把字符串处理的原理和方法；
3. 熟悉并掌握模式匹配算法。
实验原理：
顺序存储结构下的关于字符串操作的基本算法。
模式匹配算法BF、KMP
实验内容：
4-19. 在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。
4-20. 设串采用静态数组存储结构，编写函数实现串的替换Replace（S，start，T，V），即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0；并要求设计主函数进行测试。一个测试例子为：S=“I am a student”,T=“student”,V=“teacher”。程序代码：
4-19的代码：
/*静态存储结构*/
typedef struct
{
char str[MaxSize];
int length;
}String;
/*初始化操作*/
void Initiate(String *S)
{
S->length=0;
}
/*插入子串操作*/
int Insert(String *S, int pos, String T)
/*在串S的pos位置插入子串T*/
{
int i;
if(pos<0||pos>S->length)
{
printf("The parameter pos is error!\n");
return 0;
}
else if(S->length+T.length>MaxSize)
{
printf("The space of the array is not enough!\n");
return 0;
}
else
{
for(i=S->length-1; i>=pos; i--)
S->str[i+T.length]=S->str[i];
/*依次后移数据元素*/
for(i=0; i S->str[pos+i]=T.str[i]; /*插入*/ S->length=S->length+T.length; /*产生新的串长度值*/ return 1; } } /*删除子串操作*/ int Delete(String *S, int pos, int len) /*删除串S的从pos位置开始长度为len的子串值*/ { int i; if(S->length<=0) { printf("No elements deleting!\n"); return 0; } else if(pos<0||len<0||pos+len>S->length) { printf("The parameters pos and len are not correct!\n"); return 0; } else { for(i=pos+len; i<=S->length-1; i++) S->str[i-len]=S->str[i]; /*依次前移数据元素*/ S->length=S->length-len; /*产生新的串长度值*/ return 1; } } /*取子串操作*/ int SubString(String S, int pos, int len, String *T) /*取串S的从pos位置开始长度为len的子串值赋给子串T*/ { int i; if(pos<0||len<0||pos+len>S.length) { printf("The parameters pos and len are not correct!\n"); return 0; } else { for(i=0; i<=len; i++) T->str[i]=S.str[pos+i]; /*给子串T赋值*/ T->length=len; /*给子串T的长度域赋值*/ return 1; } } /*查找子串BF(Brute-Force)操作*/ int BFIndex(String S, int start, String T) /*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/ { int i= start, j=0, v; while(i { if(S.str[i]==T.str[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j==T.length) v=i-T.length; else v=-1; return v; } /*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/ int KMPIndex(String S, int start, String T, int next[]) /*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*/ /*数组Next中存放有模式串T的next[j]值*/ { int i= start, j=0, v; while(i { if(S.str[i]==T.str[j]) { i++; j++; } else if(j==0) i++; else j=next[j]; } if(j==T.length) v=i-T.length; else v=-1; return v; } /*求模式串next[j]值的操作*/ void GetNext(String T, int next[]) /*求子串T的next[j]值并存放于数组next中*/ { int j=1, k=0; next[0]=-1; next[1]=0; while(j { if(T.str[j]=T.str[k]) { next[j+1]=k+1; j++; k++; } else if(k==0) { next[j+1]=0; j++; } else k=next[k]; } } /*查找子串BF(Brute-Force)算法累计次数*/ int BFIndexC(String S, int start, String T) /*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/ { int i= start, j=0, t=0; while(i { if(S.str[i]==T.str[j]) { i++; j++; } else { i=i-j+1; j=0; } t++; } return t; } /*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/ int KMPIndexC(String S, int start, String T, int next[]) /*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*/ /*数组Next中存放有模式串T的next[j]值*/ { int i= start, j=0, t=0; while(i { if(S.str[i]==T.str[j]) { i++; j++; } else if(j==0) i++; else j=next[j]; t++; } return t; } 测试主函数： #include #define MaxSize 100 #include"SString.h" #include"BFandKMP.h" void main(void) { String S={{"cddcdc"},6}, T={{"abcde"},5}; String S1={{"aaaaaaaa"},8}, T1={{"aaaab"},5}; String S2={{"aaaaaaaaaaaaaaaaad"},18}, T2={{"aaaab"},5}; int next[20], count; count=BFIndexC(S,0,T); printf("从S中查找T的Brute-Force算法比较次数：%d\n",count); GetNext(T, next); count=KMPIndexC(S,0,T,next); printf("从S中查找T的KMP算法比较次数：%d\n",count); count=BFIndexC(S1,0,T1); printf("从S1中查找T1的Brute-Force算法比较次数：%d\n",count); GetNext(T1, next); count=KMPIndexC(S1,0,T1,next); printf("从S1中查找T1的KMP算法比较次数：%d\n",count); count=BFIndexC(S2,0,T2); printf("从S2中查找T2的Brute-Force算法比较次数：%d\n",count); GetNext(T2, next); count=KMPIndexC(S2,0,T2,next); printf("从S2中查找T2的KMP算法比较次数：%d\n",count); } 4-20的部分代码： Replace函数： /* 从主串S中查找字串T，若存在，并用串V替换串T并返回1，否则，返回0*/ int Replace(String S,int start,String T,String V) { int i,v; Initiate(&S); Initiate(&T); Initiate(&V); for(i=0; i S.length=S.length+1; for(i=0; i T.length=T.length+1; for(i=0; i V.length=V.length+1; i=BFIndex(S, 0, T); if (i!=-1) { if(Delete(&S, i, T.length)) Insert(&S, i, V); for(i=0; i printf("%c", S.str[i]); printf("\n"); return v=1; } else { printf("主串S中不存在串T\n"); return v=0; } } 测试主函数： #define MaxSize 80 #include #include #include "SString.h" int main(void) { int v; String S={"I am a student."}, T={"student"}, V={"teacher"}; v=Replace(S,0,T,V); printf("返回%d\n",v); } 总结与思考 KMP算法的比较次数比Brute-Force算法的少。KMP算法的主要特点是：消除了Brute-Force算法的主串指针在相当多个字符比较相等后，只要有一个字符不相等便回退，也就是回溯的缺点。所以从两种算法的原理和程序运行的结果来看，KMP算法比Brute-Force算法的效率更高。谢谢大家下载,本文档下载后可根据实际情况进行编辑修改.再次谢谢大家下载.翱翔在知识的海洋吧. 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） . 数据结构实验报告 图 一、实验目的 1、熟悉图的结构和相关算法。 二、实验内容及要求 1、编写创建图的算法。 2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。 三、算法描述 1、图的邻接表存储表示： 对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。 存储表示如下： typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 // InfoType *info; // 该弧相关信息的指针 } ArcNode; typedef struct VNode { char data; // 顶点信息 int data2; int sngle; ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph; 2、深度优先搜索： 假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。 2、广度优先搜索： 假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。若图中仍有未被访问的顶点，选择另一个未被访问的顶点开始，重复上述操作，直到图中所有顶点都被访问。为了使“先 实验四串 【实验目的】 1、掌握串的存储表示及基本操作； 2、掌握串的两种模式匹配算法：BF和KMP。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、串和子串的定义 串的定义：串是由零个或多个任意字符组成的有限序列。 子串的定义：串中任意连续字符组成的子序列称为该串的子串。 2、串的模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。 【实验内容和要求】 1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果： ?求“This is a boy”的串长； ?比较”abc 3”和“abcde“； 表示空格 ?比较”english”和“student“； ?比较”abc”和“abc“； ?截取串”white”，起始2，长度2； ?截取串”white”，起始1，长度7； ?截取串”white”，起始6，长度2； ?连接串”asddffgh”和”12344”； #include typedef struct { char data[MAXSIZE]; int length; } SqString; int strInit(SqString *s); /*初始化串*/ int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/ /*初始化串*/ int strInit(SqString *s) { s->length=0; s->data[0]='\0'; return OK; }/*strInit*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/ /*（1）---求串的长度*/ int strLength(SqString *s) { return s->length; }/*strLength*/ /*（2）---两个串的比较，S1>S2返回>0，s1 . 西华大学实验报告（计算机类） 开课学院及实验室：实验时间：年月日 一、实验目的 通过练习让学生对数据库、数据库和表的关系、数据词典、参照完整性和视图有较好的理解和掌握。 二、内容与设计思想 实验内容： 1.数据库设计器 2.数据库的创建 3.设定数据词典 4.参照完整性的设置 5.视图的创建和修改 三、使用环境 Windos XP操作系统；Visual ProFox 6.0 四、核心代码及调试过程 例3-27创建项目管理器SBGL，要求添入数据库sbsj，并查看该数据库。 图一 图二、“项目管理器”的数据选项卡 图三、“项目管理器”中的数据库与数据库表 例3-28从sbsj数据库所属的sb和zz两个表中抽取编号、名称和增值3个字段。，组成名称 为“我的视图”的SQL视图。 open database sbsj create sql view 我的视图; as select sb.编号,sb.名称,zz.增值from sb,zz where sb.编号=zz.编号 如有你有帮助，请购买下载，谢谢！ 例3-29根据例3-28的查询要求，用视图设计器建立视图1，然后修改其中车床的增值来更新zz表原来的增值 图一、视图设计器-视图1 图二、视图设计器-视图1 图三、增值表 图四 图五、视图设计器更新源表数据 19.根据图3.30所示数据库sbsj的永久关系，若利用参照完整性生成器来删除sb。dbf的第一个记录，对其他3个表会否产生影响，是分级、限制和忽略3中情况来说明。 图一、数据库设计器 图二、sbsj.dbc“永久关系的参照完整性生成器” 级联：相关子表中的记录将自动删除 限制：子表有相关记录，在父表中删除记录就会产生“触发器失败”的提示信息 忽略：父表删除记录，与子表记录无关 五、总结 （自己写一些收获和体会） 通过这次上机练习让我学会了怎样在数据库中添加项目管理器、表的数据完整性的概念以及视图的各种操作，让我更容易的掌握理论知识的难点和一些基本命令的使用方法，以及一些平时在课堂上不注意的问题。在上机练习的过程中需要对每个细节都要留心，认真做好每一步这样才不至于出错，这就加强了平时不注意的问题得到回应，从而加深了细节问题的处理方式。在上机的学习之后更加了解了数据库表及其数据完整性是vfp重要的一个对象，命令熟练操作直接关系到数据库的成败。 第三次的上机操作,我了解了命令的使用方式对于建立数据库表及其数据完整性很重要，要学好各种命令以及数据库表及其数据完整性的使用方法，还需在多做习题加强学习。 六、附录 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图： head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。 实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位 宁波工程学院电信学院计算机教研室 实验报告 一、实验目的 1)熟悉串的定义和串的基本操作。 2 )掌握链串的基本运算。 3 )加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C ++ 6.0的计算机。 三、实验内容 编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct sno de{ char data; struct snode *n ext; }listri ng; (1)串赋值Assig n(s,t) 将一个字符串常量赋给串s, 即生成一个其值等于t 的串s ( 2 )串复制StrCopy(s,t) 将串t 赋给串s ( 3 )计算串长度StrLength(s) 返回串s 中字符个数 ( 4 )判断串相等StrEqual(s,t) 若两个串s 与t 相等则返回 1 ；否则返回0 。 ( 5 )串连接Concat(s,t) 返回由两个串s 和t 连接在一起形成的新串。 ( 6 )求子串SubStr(s,i,j) 返回串s中从第i(1 w i w StrLength(s))个字符开始的、由连续j 个字 符组成的子串。 ( 7)插入InsStr (s,i,t) 将串t 插入到串s 的第i(1 w i w StrLength(s)+1) 个字符中,即将t 的第一个字符作为s 的第i 个字符,并返回产生的新串( 8)串删除DelStr (s,i,j) 从串s 中删去从第i(1 w i w StrLength(s)) 个字符开始的长度为j 的 子串,并返回产生的新串。 (9)串替换RepStr (s,s1,s2) 在串s 中,将所有出现的子串s1 均替换成s2 。 (10)输出串DispStr(s) 输出串s 的所有元素值 (11 )判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： (1) 建立串s= “ abcdefghijklmn ”,串s1= “xyz ”,串t =" hijk ” ( 2 ) 复制串t 到t1 ，并输出t1 的长度 ( 3) 在串s 的第9 个字符位置插入串s1 而产生串s2 ，并输出s2 ( 4) 删除s 第 2 个字符开始的 5 个字符而产生串s3 ，并输出s3 ( 5) 将串s 第 2 个字符开始的 3 个字符替换成串s1 而产生串s4 ，并输出s4 (6) 提取串s的第8个字符开始的4个字符而产生串S5，并输出S5 ( 7) 将串s1 和串t 连接起来而产生串s6 ，并输出s6 ( 8) 比较串s1 和s5 是否相等，输出结果 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 实验报告 课程数据结构实验名称实验三串 学号姓名实验日期： 串的操作 实验目的： 1. 熟悉串类型的实现方法，了解简单文字处理的设计方法； 2. 熟悉C语言的字符和把字符串处理的原理和方法； 3. 熟悉并掌握模式匹配算法。 实验原理： 顺序存储结构下的关于字符串操作的基本算法。 模式匹配算法BF、KMP 实验内容： 4-19. 在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。 4-20. 设串采用静态数组存储结构，编写函数实现串的替换Replace（S，start，T，V），即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0；并要求设计主函数进行测试。一个测试例子为：S=“I am a student”,T=“student”,V=“teacher”。程序代码： 4-19的代码： /*静态存储结构*/ typedef struct { char str[MaxSize]; int length; }String; /*初始化操作*/ void Initiate(String *S) { S->length=0; } /*插入子串操作*/ int Insert(String *S, int pos, String T) /*在串S的pos位置插入子串T*/ { int i; if(pos<0||pos>S->length) { printf("The parameter pos is error!\n"); return 0; } else if(S->length+T.length>MaxSize) 本科实验报告 课程名称：数据结构 实验项目：线性结构、树形结构、图结构、查找、排序实验地点： 专业班级：学号： 学生姓名： 指导教师： 2011年12 月24 日 实验项目：线性结构 实验目的和要求 熟练掌握线性结构的基本操作在顺序表和链式表上的实现。 二、实验内容和原理 设顺序表递增有序，编写一个程序，将x插入，使之仍然有序。 三、主要仪器设备 使用的计算机：Nopated++ 四、操作方法与实验步骤 #include A[n]=x; } else { while(A[i] 附件2： 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 实验题目图及其应用实验时间 2011.5.10 一、实验目的、意义 （1）熟悉图的邻接矩阵（或邻接表）的表示方法； （2）掌握建立图的邻接矩阵（或邻接表）算法； （3）掌握图的基本运算，熟悉对图遍历算法； （4）加深对图的理解，逐步培养解决实际问题的编程能力 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： （1）建立图的邻接矩阵（或邻接表）； （2）对其进行深度优先及广度优先遍历。 三、实验所涉及的知识点 1.创建一个图: CreateUDN(MGraph &G) 2.查找v顶点的第一个邻接点: FirstAdjVex(MGraph G,int v) 3. 查找基于v顶点的w邻接点的下一个邻接点: NextAdjVex(MGraph G,int v,int w) 4.图的矩阵输出: printArcs(MGraph G) 5:顶点定位: LocateVex(MGraph G,char v) 6. 访问顶点v输出: printAdjVex(MGraph G,int v) 7. 深度优先遍历: DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 8. 广度优先遍历BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 9. DFS,从第v个顶点出发递归深度优先遍历图G: DFS(MGraph G,int v) 四、实验记录 1.对顶点的定位其数组下标，利用了找到之后用return立即返回，在当图顶点 多的情况下节省了搜索时间，程序如下 //对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){ for (int i=0;i 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 数据结构实验报告 ――实验五简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结 构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat 中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat中读入），对文件中的正 文进行编码，然后将结果存入文件code.dat中。 3、译码。利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根 据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode 的大小设置为2n-1，描述结点的数据类型为： typedef struct { int weight;//结点权值 int pare nt; int lchild; int rchild; char inf; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链 域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #defi ne MAXBIT 10 typedef struct 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }数据结构实验报告格式
数据结构实验报告--图
数据结构实验报告-串
数据库和数据结构实验报告
数据结构实验报告
数据结构上机实验报告
数据结构实验报告全集
数据结构实验报告图实验
数据结构实验报告模板
数据结构实验报告-答案
数据结构实验报告3链串
数据结构实验报告图实验
数据结构串的操作实验报告
华仔数据结构实验报告
数据结构图及其应用实验报告+代码
数据结构实验报告及心得体会
数据结构哈夫曼编码实验报告
数据结构图实验报告