数据结构实验指导书实验5

实验五二叉树操作

一、实验目的

1．进一步掌握指针变量的含义。

2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。

3．掌握用指针类型描述、访问和处理二叉树的运算。

二、实验内容

示例程序1：广义表建立的二叉树（BTree1.cpp）

本示例程序定义了二叉树的二叉链表存储结构，并根据输入的二叉树广义表建立二叉树，实现了如下基本操作：建立(输入二叉树广义表，建立对应的二叉树存储结构)、遍历（先序遍历，中序遍历，后序遍历，按层遍历）、求二叉树所有结点数等。

程序代码如下：

#include

#include

#include

#include

#include

#define OK 1

#define TRUE 1

#define FALSE 0

#define NULL 0

#define OVERFLOW -1

typedef char ElemType; // 定义ElemType为char类型

//定义二叉树结点类型

typedef struct BTreeNode

{ ElemType data;

struct BTreeNode *left,*right;/*左右孩子指针*/

}BTreeNode,*BTree;

//二叉树基本操作说明

//初始化二叉树，即把树根指针置空

void InitBTree(BTree &T);

//根据存于字符数组a的二叉树广义表，建立对应的二叉树存储结构

//判断二叉树是否为空

bool BTreeEmpty(BTree T);

//按任意一种遍历次序输出二叉树中的所有结点

void TraverBTree(BTree T,int mark);

//求二叉树中所有结点数

int BTreeCount(BTree T);

//按照二叉树的一种表示方法输出整个二叉树

void PrintBTree(BTree T);

//清除二叉树，使之变成一棵空树

void ClearBTree(BTree &T);

//二叉树基本操作的实现

//初始化二叉树，即把树根指针置空

void InitBTree(BTree &T)

{T=NULL;}

//根据存于字符数组a的二叉树广义表，建立对应的二叉树存储结构void CreateBTree(BTree &T,char *a)

{BTree s[10];//s数组作为存储二叉树中根结点指针的栈

int top=-1; //top作为s栈的栈顶指针

T=NULL; //将树根指针置空

BTree p; //定义p为指向二叉树结点的指针

int k; //用k作为处理结点的左子树和右子树的标记，

//k=1处理左子树，k=2处理右子树

istrstream ins(a);//把字符串a定义为输入字符串流对象ins

char ch;

ins>>ch; //从ins流对象顺序读入一个字符

while(ch!='@')

{//每循环一次处理一个读入的字符，直到扫描到'@'字符为止

switch(ch)

{case '(':top++;s[top]=p;k=1;break;

case ')':top--;break;

case ',':k=2;break;

default:

p=new BTreeNode;

p->data=ch;

p->left=p->right=NULL;

if(T==NULL) T=p;

else {

if(k==1) s[top]->left=p;

else s[top]->right=p;

}

}

ins>>ch;

}

}

//判断二叉树是否为空

bool BTreeEmpty(BTree T)

{return T==NULL;}

//按任意一种遍历次序输出二叉树中的所有结点

void TraverBTree(BTree T,int mark)

{if(mark==1)//先序遍历

{if(T!=NULL)

{cout<data<<" ";

TraverBTree(T->left,mark);

TraverBTree(T->right,mark);

}

}

else if(mark==2)//中序遍历

{if(T!=NULL)

{TraverBTree(T->left,mark);

cout<data<<" ";

TraverBTree(T->right,mark);

}

}

else if(mark==3)//后序遍历

{if(T!=NULL)

{TraverBTree(T->left,mark);

TraverBTree(T->right,mark);

cout<data<<" ";

}

}

else if(mark==4)//按层遍历

{const MaxLength=30;

//定义存储二叉树结点指针的数组空间作为队列使用

BTree Q[MaxLength];

//定义队列头指针和队尾指针，初始值均置为0，表示空队列int front=0,rear=0;

BTree p;

if(T!=NULL)

{rear=(rear+1)%MaxLength;//后移队尾指针

Q[rear]=T;//将树根结点指针进队

}

while(front!=rear)

{//当队列空时执行循环

front=(front+1)%MaxLength;//后移队头指针

p=Q[front];//删除队头结点

cout<data<<" ";//输出队头结点的值

if(p->left!=NULL)

{//若结点存在左孩子，则左孩子结点指针进队

rear=(rear+1)%MaxLength;

Q[rear]=p->left;

}

if(p->right!=NULL)

{//若结点存在右孩子，则右孩子结点指针进队

rear=(rear+1)%MaxLength;

Q[rear]=p->right;

}

}

}

else{ cout<<"mark的值无效！遍历失败!"<

exit(1);

}

}

//求二叉树中所有结点数

int BTreeCount(BTree T)

{if(T==NULL) return 0;//对于空二叉树，返回0并结束递归

else

return BTreeCount(T->left)+BTreeCount(T->right)+1;

}

//按照二叉树的一种表示方法输出整个二叉树

void PrintBTree(BTree T)

{//输出二叉树的广义表表示

if(T==NULL) return;

else {//否则执行如下操作

cout<data;//输出根结点的值

if(T->left!=NULL||T->right!=NULL)

{cout<<"(";//输出左括号

PrintBTree(T->left);//输出左子树

if(T->right!=NULL)

cout<<",";//若右子树不为空则输出逗号分隔符

PrintBTree(T->right);//输出右子树

cout<<")";//输出右括号

}

}

}

//清除二叉树，使之变成一棵空树

void ClearBTree(BTree &T)

{if(T!=NULL)

{//当二叉树非空时进行如下操作

ClearBTree(T->left);//删除左子树

ClearBTree(T->right);//删除右子树

free(T);//删除根结点

T=NULL;//置根指针为空

}

}

//进行二叉树操作的主程序

void main()

{//定义指向二叉树结点的指针，并用它作为树根指针

BTree bt;

//初始化二叉树，即置根指针为空

InitBTree(bt);

//定义一个用于存放二叉树广义表的字符数组

char b[50];

//从键盘向字符数组b输入以'@'结束的二叉树广义表

cout<<"输入以'@'作为结束符的二叉树广义表表示,如：A(B(C,D),E(F,G))@ "<

//建立以bt作为树根指针的二叉树的链接存储结构

CreateBTree(bt,b);

//以广义表形式输出二叉树

PrintBTree(bt);

cout<

//前序遍历以bt为树根指针的二叉树

cout<<"前序：";

TraverBTree(bt,1);cout<

//中序遍历以bt为树根指针的二叉树

cout<<"中序：";

TraverBTree(bt,2);cout<

//后序遍历以bt为树根指针的二叉树

cout<<"后序：";

TraverBTree(bt,3);cout<

//按层遍历以bt为树根指针的二叉树

cout<<"按层：";

TraverBTree(bt,4);cout<

//求出以bt为树根指针的二叉树中所有结点数

cout<<"二叉树中所有结点数为:";

cout<

//清除以bt为树根指针的二叉树

ClearBTree(bt);

}

示例程序2：先序遍历生成二叉树（BTree2.cpp）

本示例程序演示了二叉树存储结构定义及的基本操作的实现。实现的基本操作有：建立(先序遍历生成二叉树)、先序遍历，中序遍历，后序遍历等。

程序代码如下：

#include

#include

#include

//定义二叉链表存储结构

typedef char Elemtype;

typedef struct BiTnode

{ Elemtype data;

struct BiTnode *lchild,*rchild; /*左右孩子指针*/

} BiTNode,*BiTree;

//二叉树基本操作的说明

BiTree CreateBiTree();//先序遍历生成二叉树的递归算法

void PreOrder(BiTree bt);//二叉树先序遍历的递归算法

void InOrder(BiTree bt);//二叉树中序遍历的递归算法

void PostOrder(BiTree bt);//二叉树后序遍历的递归算法

//二叉树基本操作的实现

//先序遍历生成二叉树的递归算法

BiTree CreateBiTree()

{ char ch; BiTree T;

scanf("%c",&ch);

if (ch=='#') T=NULL;

else { if(!(T=(BiTNode *) malloc (sizeof(BiTNode))))

exit (1);

T->data=ch;

T->lchild = CreateBiTree();

T->rchild = CreateBiTree();

}

return T;

}

//二叉树先序遍历的递归算法

void PreOrder(BiTree bt)

{ /*先序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

printf("%c",bt->data); /*访问结点的数据域*/

PreOrder(bt->lchild);

/*先序递归遍历bt的左子树*/ PreOrder(bt->rchild);

/*先序递归遍历bt的右子树*/

}

//二叉树中序遍历的递归算法

void InOrder(BiTree bt)

{ /*中序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

InOrder(bt->lchild);

/*中序递归遍历bt的左子树*/ printf ("%c",bt->data); /*访问结点的数据域*/

InOrder(bt->rchild);

/*中序递归遍历bt的右子树*/

}

//二叉树后序遍历的递归算法

void PostOrder(BiTree bt)

{ /*后序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

PostOrder(bt->lchild);

/*后序递归遍历bt的左子树*/ PostOrder(bt->rchild);

/*后序递归遍历bt的右子树*/ printf("%c",bt->data); /*访问结点的数据域*/

}

void main()

{

BiTree T;

printf("按先序输入序列建立一棵二叉树\n");

T=CreateBiTree();

printf("\n二叉树前序遍历序列：");

PreOrder(T);

printf("\n二叉树中序遍历序列：");

InOrder(T);

printf("\n二叉树后序遍历序列：");

PostOrder(T);

printf("\n");

}

三、实验要求

1.上机运行所有示例程序，打印出程序的运行结果，并作必要的说明。

2.选择一个示例程序，按照二叉树的操作需要，在程序中至少添加4个关

于二叉树的操作，并重新改写主程序（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数及修改后的主函数）和运行结果。

关于二叉树的操作可考虑如下问题（1－4为必做题）：

（1）求二叉树非终端结点的个数

（2）求二叉树叶子结点的个数

（3）求二叉树的深度

（4）求树的某个结点的度

（5）二叉树的中序线索化

（6）查找任意节点的中序前驱节点

（7）查找任意节点的中序后继节点

（8）哈夫曼树的构造

（9）哈夫曼编码的实现

3.根据上述要求撰写实验报告，并简要给出算法设计小结和心得。

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出

现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的

数据结构实验8实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序

6.37： #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar(); if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } typedef struct{ bitree *base; bitree *top; int stacksize; }sqstack; void initstack(sqstack &S){ S.base=(bitree*)malloc(STACK_INIT_SIZE *sizeof(bitree)); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,bitree e){ if(s.top - s.base >= s.stacksize){ s.base =

数据结构实验

实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include using namespace std; int main() { int arraay[10]={1,2,3,4,5,6,7,8,9,10}; int binary_search(int a[10],int t); cout<<"Enter the target:"; int target; cin>>target; binary_search(arraay,target); return 0; } int binary_search(int a[10],int t) { int bottom=0,top=9; while(bottom

cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode; void inseart(PNode* root, keyType key) { PNode p = (PNode)malloc(sizeof(Node)); p -> key = key;

数据结构实验报告代码

线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {

数据结构实验五-查找与排序的实现

实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计

3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;ir[j+1]){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; move++; flag=true; } } } System.out.println("排序后的数组为："); for(int i=0;i

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验一的源代码

#include #include typedef struct Node { int key;//密码 int num;//编号 struct Node *next;//指向下一个节点 } Node, *Link; void InitList(Link &L) //创建一个空的链表{ L = (Node *)malloc(sizeof(Node)); if (!L) exit(1); L->key = 0; L->num = 0; L->next = L; } void Creatlinklist(int n, Link &L) //初始化链表{ Link p, q; q = L; for (int i = 1; i <= n; i++) { p = (Node *)malloc(sizeof(Node)); if (!p) exit(1); scanf("%d", &p->key); p->num = i; L->next = p; L = p; } L->next = q->next; free(q); } Link Locate_m(Link &p, int m)//找到第m个 { Link q; for (int j = 1; jnext; q = p->next; m = q->key;

return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); }

数据结构实验报告

姓名： 学号： 班级： 2010年12月15日

实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include #include typedef struct LPeople { int num; struct LPeople *next; }peo; void Joseph(int n,int m) //用循环链表实现 { int i,j; peo *p,*q,*head; head=p=q=(peo *)malloc(sizeof(peo)); p->num=0;p->next=head; for(i=1;inum=i;q->next=p;p->next=head; } q=p;p=p->next; i=0;j=1; while(i

数据结构实验程序

顺序表的基本操作 #include using namespace std; typedef int datatype; #define maxsize 1024 #define NULL -1 typedef struct { datatype *data; int last; }sequenlist; void SETNULL(sequenlist &L) { L.data=new datatype[maxsize]; for(int i=0;i>https://www.doczj.com/doc/9214556475.html,st; cout<<"请输入"<>L.data[i]; } int LENGTH(sequenlist &L) { int i=0; while(L.data[i]!=NULL) i++; return i; } datatype GET(sequenlist &L,int i) { if(i<1||i>https://www.doczj.com/doc/9214556475.html,st) { cout<<"error1"<

int j=0; while(L.data[j]!=x) j++; if(j==https://www.doczj.com/doc/9214556475.html,st) { cout<<"所查找值不存在！"<=maxsize-1) { cout<<"overflow"; return NULL; } else if(i<1||(i>https://www.doczj.com/doc/9214556475.html,st)) { cout<<"error2"<=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; https://www.doczj.com/doc/9214556475.html,st++; } return 1; } int DELETE(sequenlist &L,int i) { int j; if((i<1)||(i>https://www.doczj.com/doc/9214556475.html,st+1)) { cout<<"error3"<

数据结构实验五

1. 实验步骤： 先定义顺序表的结点： typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; 然后定义一个随机取数的函数，存到顺序表中： void CreateList(SqList &L,int n) 然后定义一个显示顺序表的函数，将顺序表中的数据显示出来： void ListTraverse(SqList L) 然后通过排序函数，将所有的数据按照从大到小的顺序排列： void BubbleSort(SqList &L) 实验结果： 测试数据： 38 86 9 88 29 18 58 27 排序后： 9 18 27 29 38 58 86 88 BubbleSort排序方法中数据的比较次数为：27 疑难小结： 这个程序的难点在于排序函数，总是把从第几个数开始排序以及怎样循环弄错。 源代码： #include using namespace std; #include typedef int KeyType; typedef char * InfoType; typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; int CmpNum; void CreateList(SqList &L,int n) { int i;

数据结构实验

长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/9214556475.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：

（1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 （1）进一步掌握指针变量的用途和程序设计方法。 （2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。 （3）掌握构造二叉树的基本方法。 （4）掌握二叉树遍历算法的设计方法。 3．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）掌握一个实际二叉树的创建方法。 （3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4．实验内容 （1）定义二叉链存储结构。

数据结构实验五A

《数据结构与算法分析》 实验报告书 学期：2014 － 2015 学年第 2 学期 班级：信息管理与信息系统2班 学号： 1310030217 姓名：田洪斌 实验类别：（★）基础型（）设计型 实验时间： 成绩： 信息管理系

一、实验内容 实现程序，按满二叉树给元素编号并输入的方式构造二叉树。 二、实验目的 1、掌握二叉树的静态及操作特点； 2、掌握二叉树的各种遍历方法； 3、掌握二叉树的存储、线索化等在C语言环境中的实现方法； 4、掌握哈夫曼树的构造方法及编码方法。 三、需求分析 用二叉树结构表示来完成输入、编辑、调试、运行的全过程。并规定： a.手动输入数字建立二叉树 b.程序可以输入、调试、运行、显示、遍历 c.测试数据：用户手动输入的数据 四、系统设计 1．数据结构设计 在本程序中对二叉树的存储主要用的是顺序存储结构，将二叉树存储在一个一维数组中。数据的输入输出都是采用整型数据进行。在主函数中只是定义数据类型，程序的实现功能化主要是在主函数中通过给要调用的函数参数来实现程序要求的功能。 2．程序结构设计 （1）程序中主要函数功能： main()/////////////////////////////////////////////主函数 menu()/////////////////////////////////////////////菜单 BiTree CreateBiTree()///////////////////////先序建立二叉树 （2）函数调用关系 见图4-1。

图4-1 函数关系图 五、 调试分析 1.算法和函数中出现了一些系统无法识别的变量，照成程序出现了错 误。原因是没有注意算法与源程序的区别。算法是简单的对源程序进行描述 的，是给人阅读的，所以有些变量没有定义我们就能看懂。而程序中的变量一定要先定义才能够被引用，才能被计算机识别。 2.在调试过程中遇到问题是利用C++程序进行调试的，找出错误并改正。 3.数据输出函数运行不正常，经检查程序，发现是定义错误，更改后错误排除； 六、 测试结果 1．运行时输入正确密码进入主界面，系统根据输入的数字选项来调用相应的函数。主要实现“功能选择”的界面，在这个界面里有显示系统的五大功能，根据每个功能前面的序号进行选择。以下为该界面： main BiTree CreateB iTree() meun()

数据结构-实验五-图

数据结构与算法课程实验报告实验五：图的相关算法应用 姓名：cll 班级： 学号：

【程序运行效果】 一、实验内容： 求有向网络中任意两点之间的最短路 实验目的： 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 二、问题描述： 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现： 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称

}DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路： 用邻接矩阵的方法表示各城市直接路线的图，之后用Floyd算法求解两点直接的最短距离，并用递归的方法求出途经的城市。 主要源程序代码： #include #include #define MAXVEX 50 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //创建临接矩阵 void CreatGraph(AdjMetrix g,int m[][MAXVEX],DataType d[],int n){ /*g表示邻接矩阵，m[][MAXVEX]表示输入的邻接矩阵，d[]表示各城市的名称，n表示城市数目*/ int i,j; g->vexs = n; for(i=0;i < g->vexs;i++){ g->data[i] = d[i]; for(j=0;jvexs;j++){ g->arcs[i][j] = m[i][j]; } } } //求最短路径 void Floyd(AdjMetrix g,int F[][10],int path[][10]){ int i,j,k; for(i=0;ivexs;i++){ for(j=0;jvexs;j++){

数据结构上机实验线性表单链表源代码

#include template class LinearList { public: virtual bool IsEmpty()const=0; virtual int Length()const=0; virtual bool Find(int i,T& x)const=0; virtual int Search(T x)const=0; virtual bool Insert(int i,T x)=0; virtual bool Update(int i,T x)=0; virtual bool Delete(int i)=0; virtual void Output(ostream& out)const=0; protected: int n; }; #include "linearlist" template class SeqList:public LinearLisr { public: SeqList(int mSize); ~SeqList(){delete [] elements;} bool IsEmpty()const; bool Find(int i,T& x)const; int Length()const; int Search(T x)const; bool Insert(int i,T x); bool Update(int i,T x); bool Delete(int i); void Output(ostream& out)const; private: int maxLength; T *elements; }; template SeqList::SeqList(int mSize) { maxLength=mSize;

数据结构课程实验报告-实验5

数据结构课程实验报告-实验5

HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名康小雪 学生学号 20090810310 专业班级计科三班 指导老师李晓鸿 完成日期2010-10-24

一、需求分析 1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将 其转化为后缀表达式，并计算其结果，否则说明该表达式错误 2．.输入的表达式包含数字和运算符及括号，之间用空格隔开 3．数字可以为整数和小数 4．运算结果保留两位小数 输入输出举例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 二、概要设计 在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree {

数据对象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,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存 在唯一的元素，xr，∈H，且 存在Dr上的关系Hr∈ H;H={,,H1,Hr}; （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵 符合本定义的二叉树，称为根的右子树基本操作P: InitBiTree（&T）

数据结构实验(七种排序算法的实现)题目和源程序

1、直接插入排序 2、希尔排序 3、2-路归并排序 4、折半插入排序 5、冒泡排序 6、快速排序 7、堆排序 /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘2011年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include #include using namespace std; #define MAXSIZE 20 typedefintKeyType; typedefstruct{ KeyType key; //关键字项 KeyType data; //数据项 }RedType; //记录类型 typedefstruct{ RedTypearr[MAXSIZE+1]; //arr[0]闲置或用作哨兵单元int length; //顺序表长度 }SqList; //顺序表类型typedefSqListHeapType; //对顺序表L做一趟希尔插入排序 //前后记录位置的增量是dk //r[0]只是暂存单元 //当j<=0时，插入位置已找到 voidshellInsert(SqList&L, intdk) {

int i, j; for (i = dk + 1; i <= L.length; i++) { if (L.arr[i].key 0 &&L.arr[0].key = high + 1; j--) L.arr[j + 1] = L.arr[j];//记录后移 L.arr[high + 1] = L.arr[0];//插入 }//for }//BInsertSort //直接插入排序

数据结构实验报告3543435

合肥师范学院实验报告册 2013 / 2014 学年第2 学期 系别计算机科学与技术系 实验课程数据库原理 专业计算机软件 班级软件一班 姓名周锦 学号1210431081 指导教师潘洁珠

实验一——数据库基本操作 一、实验目的 1.熟悉MS SQL SERVER运行界面，掌握服务器的基本操作。 2.掌握界面操作方法完成用户数据库建立、备份和还原。 3.建立两个实验用的数据库，使用企业管理器和查询分析器对数据库和表进行基本操作。 二、实验预习内容 在认真阅读教材及实验指导书的基础上，上机前请预习以下内容，并在空白处填写相应的步骤或命令。 1.熟悉SQL SERVER 2000 的运行环境，练习服务器基本操作：打开、停止、关闭。 2.使用SQL SERVER 2000 中的企业管理器完成以下任务。 数据库名称：STC 表：STU（sno char(9), sname varchar(50), ssex char(2) , sage int, sdept char(2) ）； COUTSES（cno char(3), cname varchar(50), cpno char(3), credit int ）； SC（sno char(9), cno char(3), grade int ）； 说明：以上为表结构，以sno char（9）为例，说明sno属性设置为字符类型，宽度为9，int指整型数据。 1）建立数据库STC，分别建立以上三张表，并完成数据录入。（表结构及数据参见教材） 建立数据库：数据库→右击鼠标→新建数据库，出现如上图所示的框，然后填上所建数据库的名称。