第三次数据结构课程实验

必做●SubString (&Sub, S, pos, len)求子串●Index (S, T, pos)字符串查找#include <stdio.h>#include <stdlib.h>#define INTERLENGTH 100#define INCREASE 10#define OK 1#define ERROR -1#define overflow -2typedef struct{char *data;int length;int size;}Sqlist;int cj(Sqlist &L){L.data=(char *)malloc(INTERLENGTH*sizeof(char));if(L.data==NULL)exit(overflow);L.length=0;L.size=INTERLENGTH;return OK;}int AgainMalloc(Sqlist &L){char *newbase;newbase=(char *)realloc(L.data,(INCREASE+L.size)*sizeof(char)); if(newbase==NULL)exit(overflow);L.data=newbase;L.size+=INCREASE;return OK;}int insert(Sqlist &L,char a){if(L.length==L.size){AgainMalloc(L);}L.data[L.length]=a;L.length++;return OK;int travel(Sqlist &L){for(int i=0;i<L.length;i++)printf("%c",L.data[i]);printf("\n");return OK;}int clear(Sqlist &L){L.length=0;return OK;}int SubString(Sqlist &L,int pos,int len,Sqlist &sub) {if(pos<1||pos>L.length||len<0||len>L.length-pos+1) {printf("²»ºÏ·¨ ");exit(overflow);}cj(sub);clear(sub);int i;for(i=pos-1;i<pos+len-1;i++){insert(sub,L.data[i]);}return OK;}int index(Sqlist &L,Sqlist &sub){int i=0;int j=0;while(i<L.length&&j<sub.length){if(L.data[i]==sub.data[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=sub.length)return i-sub.length+1;elsereturn ERROR;}int main(){Sqlist L,sub;cj(L);char c;printf("请输入字符串：\n");while((c=getchar())!='\n'){insert(L,c);}printf("求得从2位置开始4位自串如下：\n"); SubString(L,2,4,sub);travel(sub);clear(sub);printf("请输入待查找字符串；\n");while((c=getchar())!='\n'){insert(sub,c);}int a= index(L,sub);printf("%d",a);}。

数据结构实验报告三数据结构实验报告三引言：数据结构是计算机科学中的重要内容之一，它研究的是如何组织和存储数据以便高效地访问和操作。

本实验报告将介绍我在数据结构实验三中的实验过程和结果。

实验目的：本次实验的主要目的是熟悉并掌握树这种数据结构的基本概念和操作方法，包括二叉树、二叉搜索树和平衡二叉树等。

实验内容：1. 实现二叉树的创建和遍历在本次实验中，我首先实现了二叉树的创建和遍历。

通过递归的方式，我能够方便地创建一个二叉树，并且可以使用前序、中序和后序遍历方法对二叉树进行遍历。

这些遍历方法的实现过程相对简单，但能够帮助我们更好地理解树这种数据结构的特点。

2. 实现二叉搜索树的插入和查找接下来，我实现了二叉搜索树的插入和查找操作。

二叉搜索树是一种特殊的二叉树，它的左子树上的节点的值都小于根节点的值，右子树上的节点的值都大于根节点的值。

通过这种特性，我们可以很方便地进行插入和查找操作。

在实现过程中，我使用了递归的方法，通过比较节点的值来确定插入的位置或者进行查找操作。

3. 实现平衡二叉树的插入和查找平衡二叉树是为了解决二叉搜索树在某些情况下可能会退化成链表的问题而提出的。

它通过在插入节点的过程中对树进行旋转操作来保持树的平衡。

在本次实验中，我实现了平衡二叉树的插入和查找操作。

通过对树进行左旋、右旋等操作，我能够保持树的平衡，并且能够在O(log n)的时间复杂度内进行插入和查找操作。

实验结果：通过本次实验，我成功地实现了二叉树、二叉搜索树和平衡二叉树的相关操作。

我编写了测试代码，并对代码进行了测试，结果表明我的实现是正确的。

我能够正确地创建二叉树，并且能够使用前序、中序和后序遍历方法进行遍历。

对于二叉搜索树和平衡二叉树，我能够正确地进行插入和查找操作，并且能够保持树的平衡。

实验总结：通过本次实验，我深入了解了树这种数据结构的特点和操作方法。

二叉树、二叉搜索树和平衡二叉树是树的重要应用，它们在实际开发中有着广泛的应用。

数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。

具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。

二、实验原理树是一种非线性的数据结构，由结点和边组成。

树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。

树的基本操作包括插入、删除和查找。

在本次实验中，我们采用二叉树作为实现树的数据结构。

二叉树是一种特殊的树，每个结点最多只有两个子结点。

根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。

三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。

然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。

2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。

我们可以通过递归的方式实现插入操作。

具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。

如果当前结点为空，则将新的结点作为当前结点。

3. 实现删除操作删除操作是将指定的结点从树中移除的过程。

我们同样可以通过递归的方式实现删除操作。

具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。

如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。

- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。

- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。

4. 实现查找操作查找操作是在树中寻找指定值的过程。

同样可以通过递归的方式实现查找操作。

具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。

数据结构实验报告实验名称：实验三——栈和队列学生姓名：班级：班内序号：学号：日期：1.实验要求1.1 实验目的通过选择下面两个题目之一进行实现，掌握如下内容：➢掌握二叉树基本操作的实现方法➢了解赫夫曼树的思想和相关概念➢学习使用二叉树解决实际问题的能力1.2 实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 二叉链表2.2 二叉树的二叉链表存储示意图2.3 关键算法分析2.3.1算法1：void create(Binode<T> *&R, T data[], int i);[1] 算法功能：创建一个二叉树[2] 算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数create()创建二叉树，关于函数create()的伪代码：1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。

[3] 算法空间、时间复杂度：O（n）[4] 代码逻辑（可用伪代码描述）：if(data[i-1]!=0){R = new Binode<T>;R->data= data[i-1];R->lch = R->rch = NULL;create(R->lch, data,2*i);create(R->rch, data, 2*i+1);}2.3.2算法2：void Destroy(Binode<T> *R);[1] 算法功能：二叉树的销毁[2] 算法基本思想：采用后序遍历的方法，释放节点。

实验报告（三）：栈及其应用专业：计算机科学与技术班级：计本班姓名：学号：日期： 2012-10-11 1实验目的1)掌握顺序栈的类型定义方法。

2)掌握在顺序栈上实现的六种基本操作。

3)掌握顺序栈的简单应用。

4)掌握链栈的实现、并能够清楚对比栈的两种实现方法的优劣。

2实验内容1)设计和实现一个栈数据结构（可以是顺序栈，链栈）。

2)实现栈数据结构的各种操作，包括栈的初始化、出入栈、清空和释放栈等。

3)在上述实现的栈的基础上，实现栈的应用：写一个算法，完成表达式的求值。

4)上述栈的实现和应用不限制顺序栈或者链式栈，两者皆可。

3实验要求1)提前预习该实验相关的内容，包括栈的两种实现方法，以及具体存储结构上的各类栈操作。

2)选择其中一种存储方法加以实现，并完成相关操作实现。

3)设计并实现算法完成实验内容中表达式的求值。

4)编写完整的程序完成实验内容，并上机调试和运行。

5)整理并上交实验报告。

6)本次实验要求在4学时内完成。

4数据结构设计4.1栈结构设计（采取单链表的结构）类图的设计：字段4.2基本操作所要实现的基本操作：1)完成表达式的求值。

5实现5.1设计实现//"public.h"#pragma once#pragma region声明#include<string.h>#include<ctype.h>//malloc() 等函数#include<malloc.h>//INT_MAX#include<limits.h>//EOF (=^Z或F6)，NULL#include<stdio.h>//atoi()#include<stdlib.h>//eof()#include<io.h>#include<math.h>//exit()#include<process.h>//cout,cin#include<iostream>using namespace std;//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status;typedef int Boolean;typedef char SElemType;#pragma endregion//"DefinitionForSqStack.h"栈的定义#pragma once#include"public.h"#define STACK_INIT_SIZE 10#define STACKINCREMENT 2//顺序栈struct SqStack{//在栈构造之前和销毁之后，base的值为NULLSElemType *base;//栈顶指针SElemType *top;//当前已经分配的存储空间，以元素为单位int stacksize;};5.2操作实现5.2.1顺序栈的操作实现//"DefinitionForSqStack.h"#pragma once#include"public.h"#define STACK_INIT_SIZE 10#define STACKINCREMENT 2Status InitStack(SqStack & s){if(!(s.base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)))){//存储分配失败exit(OVERFLOW);}s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;}Status DestroyStack(SqStack & s){//销毁栈s，s不再存在free(s.base);s.base = NULL;s.top = NULL;s.stacksize = 0;return 0;}Status ClearStack(SqStack & s){//把s置为空栈s.top = s.base;return OK;}Status StackEmpty(SqStack & s){//若栈s为空栈，则返回TRUE，否则返回FALSEif(s.top == s.base){return TRUE;}else{return FALSE;}}Status StackLength(SqStack & s){//返回s的元素个数，即栈的长度return s.top - s.base;}Status GetTop(SqStack & s,SElemType & e){//若栈不空，则用e返回s的栈顶元素，并返回OK；否则返回ERROR if(s.top > s.base){e = *(s.top - 1);return OK;}else{return ERROR;}}Status Push(SqStack & s,SElemType & e){//插入元素e为新的栈顶元素if(s.top - s.base >= s.stacksize){//栈满，新申请存储空间s.base = (SElemType *)realloc(s.base,(s.stacksize + STACKINCREMENT)*sizeof(SElemType));if(!s.base){//存储空间分配失败exit(OVERFLOW);}s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*(s.top) ++= e;return OK;}Status Pop(SqStack & s,SElemType & e){//若栈不空。

北理工数据结构实验三《数据结构与算法设计》实验报告——实验三学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固二叉树和队列的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言实现二叉树和队列的抽象数据类型；4.用C语言编写递归函数，实现生成二叉树和遍历二叉树；5.用队列实现二叉树的层次遍历；6.理论知识与实际问题相结合，利用上述基本操作用多种方式遍历二叉树。

二、实验内容1、遍历二叉树。

请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。

2、选做：按层次遍历二叉树。

三、程序设计1、概要设计为实现上述程序功能，需要建立抽象数据类型：二叉树和队列。

（1）、定义抽象数据类型二叉树的抽象数据类型定义为：ADT BinaryTree {数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系；（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；（3）若D1≠Φ，则D1中存在惟一的元素x1，∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr，∈H，且存在上的关系Hr ?H；H={,,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：CreatBiTree(BiTree &T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTree T)初始条件：二叉树T已经存在操作结果：先序遍历二叉树T ，对每个结点输出其数据元素InOrderTraverse(BiTree T)初始条件：二叉树T已经存在操作结果：中序遍历二叉树T ，对每个结点输出其数据元素PostOrderTraverse(BiTree T)初始条件：二叉树T已经存在操作结果：后序遍历二叉树T ，对每个结点输出其数据元素LevelOrderTraverse(BiTree T)初始条件：二叉树T已经存在操作结果：层次遍历二叉树T ，对每个结点输出其数据元素} ADT BinaryTree队列的抽象数据类型定义为：ADT Stack{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={ |ai∈D,i=1,2,……,n}约定其中a1端为队列头，an端为队列尾基本操作：InitQueue(&Q)功能：构造一个空队列Q。