数据结构实验报告二.doc

精品学习资料范文
数据结构实验报告二
篇一：数据结构实验报告实验二
数据结构实验报告
1.实验序号 实验名称
实验二 二叉树的操作算法
2.班级、姓名、学号、实验日期
3.实验目的
实现二叉树的常用操作算法：包括二叉树的建立、遍历、求高度、线索化等操作
4.概要设计
为了条理清晰，分为2个程序分别实现二叉树的建立、遍历、求高度，线索化功能
(1)实现二叉树的建立、先中后序遍历、求高度
(2)实现线索化功能
5.详细设计
实现二叉树的建立、遍历、求高度
#include stdio.h
#include malloc.h
#define maxsize 66
typedef int datatype;
typedef struct node
{
datatype data ;
struct node *lchild,*rchild;
} bitree;
bitree *Q[maxsize];
bitree *creatree()
{
char ch;
int front,rear;
bitree *root,*s;
root=NULL;
front=1;rear=0;
ch=getchar();
while (ch!= # )
{
s=NULL;
if(ch!= @ )
{
s=(bitree*)malloc(sizeof(bitree));
s- data=ch;
s- lchild=NULL;
s- rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if (s Q[front])
if(rear%2==0)
Q[front]- lchild=s;
else
Q[front]- rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void preorder(bitree *t)
{
if (t)
{
printf( %c ,t- data);
preorder(t- lchild);
preorder(t- rchild);
}
}
void inorder(bitree *t)
{
if (t)
{
inorder(t- lchild);
printf( %c ,t- data);
inorder(t- rchild);
}
}
void postorder(bitree *t)
{
if (t)
{ //先//中 //后
postorder(t- lchild);
postorder(t- rchild);
printf( %c ,t- data);
}
}
int height(bitree *t) //求高度 {
int hl,hr;
if(!t) return 0;
else
{
hl=height(t- lchild);
hr=height(t- rchild);
return ((hl hr?hl:hr)+1);
}
}
main()
{
bitree *t;
int x,y;
printf( 请输入数据，以#做结尾:\n
t=creatree();
printf( \n前序:\t preorder(t);
printf( \n中序:\t inorder(t);
printf( \n后序:\t postorder(t);
x=height(t);
printf( \n高度:%d ,x);
printf( \n
}
实现线索化功能
#include stdio.h
#include malloc.h
#define maxsize 40
typedef struct node{
char data;
struct node *lchild,*rchild;
int ltag,rtag;
} bitree;
bitree *Q[maxsize]; /*队列*/
bitree *pre=NULL;
bitree *creatree()
{char ch;
int front,rear;//队头、队尾 bitree *root,*s;
root=NULL;//空树
front=1; rear=0;//空队
ch=getchar();
while(ch!= # )
{s=NULL;
if(ch!= @ )//建立新结点{s=(bitree *)malloc(sizeof(bitree)); s- data=ch;
s- lchild=s- rchild=NULL;
s- ltag=s- rtag=0;
}
rear++;
Q[rear]=s;//入队
if(rear==1) root=s;
else
{if(s Q[front]) //孩子、双亲均非空 if(rear%2==0) Q[front]- lchild=s; else Q[front]- rchild=s; if(rear%2==1) front++; //出队}
ch=getchar();
}
return root;
}
void inorder(bitree *t)
{if(t)
{inorder(t- lchild);
printf( %c ,t- data);
inorder(t- rchild);
}
}
void INTHREAD(bitree *p)
{if(p!=NULL)
{INTHREAD(p- lchild);
if(p- lchild==NULL) p- ltag=1;
if(p- rchild==NULL) p- rtag=1; if(pre!=NULL)
{ if(pre- rtag==1) pre- rchild=p;
if(p- ltag==1) p- lchild=pre; } pre=p;
INTHREAD(p- rchild);
}
}
bitree * inordernext (bitree *p)
{
bitree *q;
if(p- rtag==1) return p- rchild;
else
{ q=p- rchild;
while(q- ltag==0) q=q- lchild;return q;
}
}
void traverseinthread(bitree *p)
{
if(p!=NULL)
{while (p- ltag==0 )
p=p- lchild;
do {printf( %c ,p- data);
p=inordernext(p);
}while(p!=NULL);
}
}
int main()
{bitree *t;
t=creatree();
printf( 中序遍历结果是:\n:
inorder(t);
printf( \n
INTHREAD(t);
printf( 线索化中序遍历的结果是：\n printf( \n
traverseinthread(t);
printf( \n
}
篇二：数据结构实验报告2
数据结构实验报告
实验1.汉诺塔的实现
一．需求分析
题目：假设有三个命名为X，Y，Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,……，n的圆盘。现按照要求将X轴上的n个圆盘移至塔座Z上，并仍按同样顺序叠排，圆盘移动时必须遵守以下规则：1，每次只能移动一个；2，圆盘
可以插在XYZ中的任一塔座上；3，任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
需要输入的值：圆盘的个数。
输出：从X塔座上移至Z塔座上的顺序。
测试数据：3，输出结果预测：x?y,x?z,y?z,x?y,z?y,z?x,y?x,y?z,x?y,x?z,y?z（箭头符号表示圆盘移动的次序）移动结束。
二．概要设计：
本实验主要运用递归的思想，先把上面的n-1个拿到Y盘，把最下面的一个Z盘，然后剩下的n-1个也用这样的思路，用递归调用的算法实现圆盘的移动。
三．详细设计：
四．调试分析：
遇到的问题：移动时，步骤编号不变。解决方法：用static使其成为静态变量。
时间复杂度：o(n);
经验体会：递归可以把问题简单化，是个很好的方法。
五．使用说明：
输入盘子的数目即可。
六．测试结果：
七．源代码：
#include stdio.h
#include string.h
void move(char a,int i,char b){
static int c=0;
printf( %i.move disk %i. from %c to %c\n ,++c,i,a,b);
}//移动
void hanoi(int n,char x,char y,char z){
if(n==1) move(x,1,z);
else{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}//递归
int main(){
char x,y,z;
int n;
scanf( %d ,
x=&#(转载自：www.BdfQy.Com 千 叶帆 文摘:数据结构实验报告二)39;x
y= y
z= z
hanoi(n,x,y,z);//调用
return 0;
}
实验2.字符串匹配。
一．需求分析：
输入一母串，另输入一字符串，判断该字符串是不是母串的字串，若是字串，则返回母串中字串的起始位置，否则输出不是字串。
输入：两串字符；
输出：返回值或0。
测试数据：abcdefgijk efg 预测结果：4
二．概要设计：
用查找的方法，如果遇到第一个相同的字母，则字串母串同时往后移一个。
三．详细设计：
int substring(string s1,string s2)//s1是字串
{
int a=0,b,j=1,i;
for(b=0;b s2.length();b++){
i=b;
for(;a s1.length();a++)
{
if(s1[a]!=s2[i]) {j=0;continue;}//若s1的字母和s2的字母有一个不同则进行下一个的比较
else i++;
j++;
if(j==s2.length()) return a-s2.length()+1;//如果匹配，则返回母串中与字串开始匹配的位置
}
}
return 0;
}
四．调试分析：
遇到的问题：跳出循环时没有考虑到如果字串与母串相匹配则字串的字母也要向后移动一个。解决方法：字串同时后移一个如果前一个相匹配。
时间复杂度：o(n);
经验体会：设计算法时，即使是很简单的算法，也不能掉以轻心。
五．用户使用说明：
输入一字符串，换行，再输入一字符串，再换行，在换行，即可。
六．运算结果：
七．源代码：
#include iostream
#include string
using namespace std;
int substring(string s1,string s2)//s1是字串
{
int a=0,b,j=1,i;
for(b=0;b s2.length();b++){
i=b;
for(;a s1.length();a++)
{
if(s1[a]!=s2[i]) {j=0;continue;}//若s1的字母和s2的字母有一个不同则进行下一个的比较
else i++;
j++;
if(j==s2.length()) return a-s2.length()+1;//如果匹配，则返回母串中与字串开始匹配的位置
}
}
return 0;
}
int main(){
string s1,s2;
getline(cin,s1);//输入母串
getline(cin,s2);//输入字串
cout substring(s1,s2) endl;
return 0;
}
实验3.停车场管理。
篇三：数据结构实验报告(2)
数据结构实验报告
姓名：班级：
学号：
日期：2015年9月27日
上机环境：win7系统，mircosoft visual++
1．实验名称：线性表
2． 实验题目
编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）并在此基础上设计一个主程序完成如下功能：
(1) 初始化顺序表L；
(2) 依次采用尾插入法插入a,b,c,d,e元素；
(3) 输出顺序表L；
(4) 输出顺序表L的长度；
(5) 判断顺序表L是否为空；
(6) 输出顺序表L的第3个元素；
(7) 输出元素a的位置；
(8) 在第4个元素位置上插入f元素；
(9) 输出顺序表L；
(10) 删除L的第3个元素；
(11) 输出顺序表L；
(12) 释放顺序表。
3． 实验程序
#include stdio.h
#include malloc.h
#define MaxSize 50
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList * L)
{
L= (SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L- length=0; //置空线性表长度为0
}
void DestroyList(SqList *L)
{
free(L);
}
bool ListEmpty(SqList *L)
{
return(L- length==0);
int ListLength(SqList *L)
{
return(L- length);
}
void DispList(SqList *L)
{
int i;
if(ListEmpty(L))
return;
for(i=0;i L- length;i++)
printf( %c ,L- data[i]);
printf( \n
}
bool GetElem(SqList *L,int i,ElemType e)
{
if(i 1||i L- length)
return false;
e=L- data[i-1];
return true;
}
int LocateElem(SqList *L,ElemType e)
{
int i=0;
while(i L- length L- data[i]!=e)
i++;
if(i L- length)
return 0;
else
return i+1;
}
bool ListInsert(SqList *L,int i,ElemType e)
{
int j;
if(i 1||i L- length+1)
return false;
i--;
for(j=L- length;j j--)
L- data[j]=L- data[j-1];
L- data[i]=e;
L- length++;
return true;
}
bool ListDelete(SqList * L,int i,ElemType e)
int j;
if(i 1||i L- length)
return false;
i--;
e=L- data[i];
for(j=i;j L- length-1;j++)
L- data[j]=L- data[j+1];
L- length--;
return true;
}
extern void InitList(SqList *
extern void DestroyList(SqList *L);
extern bool ListEmpty(SqList *L);
extern int ListLength(SqList *L);
extern void DispList(SqList *L);
extern bool GetElem(SqList *L,int i,ElemType extern int LocateElem(SqList *L,ElemType e);
extern bool ListInsert(SqList *L,int i,ElemType e);
extern bool ListDelete(SqList * L,int i,ElemType void main()
{
SqList *L;
ElemType e;
printf( 顺序表的基本运算如下：\n
printf( (1)初始化顺序表L\n
InitList(L);
printf( (2)依次采用尾插法插入a,b,c,d,e元素\n ListInsert(L,1, a
ListInsert(L,2, b
ListInsert(L,3, c
ListInsert(L,4, d
ListInsert(L,1, e
printf( (3)输出顺序表L:
DispList(L);
printf( (4)顺序表L的长度= % d\n ,ListLength(L));
printf( (5)顺序表L为 %s\n ,(ListEmpty(L)? 空 : 非空 )); GetElem(L,3,e);
printf( (6)顺序表L的第3个元素 = % c\n ,e);printf( (7)元素a的位置 = %d\n ,LocateElem(L, a printf( (8)在第4个元素位置上插入f元素\n ListInsert(L,4, f
printf( (9)输出顺序表L:
DispList(L);
printf( (10)删除L的第3个元素\n ListDelete(L,3,e);
printf( (11)输出顺序表L： DispList(L);
printf( (12)释放顺序表L\n DestroyList(L);
}
4． 实验结果