数据结构试验报告一海龟作图(样例5)

时间:2019-05-15 09:38:17下载本文作者:会员上传
简介:写写帮文库小编为你整理了多篇相关的《数据结构试验报告一海龟作图》,但愿对你工作学习有帮助,当然你在写写帮文库还可以找到更多《数据结构试验报告一海龟作图》。

第一篇:数据结构试验报告一海龟作图

实验报告:海龟作图

题目:设计一个能够实现海龟抽象数据类型Turtle。

海龟作图的抽象数据类型的定义为:

ADT Turtle{ 数据对象:D={ai |ai∈CharSet,i=1,2,3,…,n n>=0} 数据关系:R1={|ai-1,ai∈D,ai-1

void StartTurtleGraphics(char name ,int num1,int num2)

操作结果:显示作图窗口并在窗口内写出本人的姓名name、上机号num1,实习题号num2 void StartTurtle(new Turtle &raphael,aPoint startPos)

操作结果:初始化了一个新海龟,定位在startPos,并置画笔状态为落笔、龟头朝向为0,步进的尺寸因子为1。

void PenUp(newturtle &raphael)

初始条件:海龟已存在。

操作结果:设置画笔状态为抬笔。从此时起,海龟在屏幕上移动时将不在屏幕上作图。

void PenDown(newturtle &raphael)

初始条件:海龟已存在。

操作结果:设置画笔状态为落笔。从此时起,海龟在屏幕上移动时将在屏幕上作图。int TurtleHeading(newturtle &raphael,int single)

初始条件:海龟已存在。

操作结果:返回海龟头当前朝向放角度single。aPoint * TurtlePos(newturtle &raphael)

初始条件:海龟已存在。

操作结果:返回海龟头当前位置。

void Move(newturtle &raphael,float steps)

初始条件:海龟已存在。

操作结果:依照海龟头的当前朝向,向前移动steps步。void Turn(newturtle &raphael,float size)

初始条件:海龟已存在。

操作结果:改变海龟头的当前朝向,逆时针旋转size度。void ScaleTurtle(newturtle &raphael,float scaleFactor)

初始条件:海龟已存在。

操作结果:改变海龟移动的步进尺寸SizeFactor,扩大scaleFactor倍 viod MoveTTo(newturtle &raphael,aPoint newPos)

初始条件:海龟已存在。

操作结果:将海龟移动到新位置newPos,newPos是屏幕窗口的一个“点”。void TurnTTo(newturtle &raphael,float angle)初始条件:海龟已存在。

操作结果:改变海龟头的当前朝向从正东方向起的angle度。viod SetTurtleColor(newturtle &raphael,int color)

初始条件:海龟已存在。

操作结果:设置海龟笔的当前颜色为color。

void SetTurtleBackColor(newturtle &raphael,int backcolor)

初始条件:海龟已存在。

操作结果:设置海龟作图的背景的颜色为backcolor。}

第二篇:数据结构试验报告

实验一:ADT的类C描述向C程序的转换实验(2学时)

实验目的:

(1)复习C语言的基本用法;

(2)学会用类C的语言对算法进行描述的方法,将类C算法转换成C源程序的方法和过程;

(3)抽象数据类型的定义和表示、实现;

(4)加深对数据的逻辑结构和物理结构之间关系的理解;(5)初步建立起时间复杂度和空间复杂度的概念。实验内容:(类C算法的程序实现)(1)输入一组数据存入数组中,并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值,并通过函数参数返回所求结果; 实验准备:

1)计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分析与代码设计与分析准备。实验步骤:

1.安装TC并设置好环境,如果已安装好,可以跳过此步; 2.录入程序代码并进行调试和算法分析;

对实验内容(1)的操作步骤:1)用类C语言描述算法过程;2)用C语言环境实现该算法。

对实验内容(2)的操作步骤:1)完成算法的C实现;2)分析其时间复杂度和空间复杂度。

3.编写实验报告。

实验结果:// 动态分配数组空间 #include #include

int size,i;int *pArray;int *p;void malloc_size(){ pArray=(int *)malloc(size*(sizeof(int)));}

int input_size(){ printf(“please input the size:n”);printf(“size= ”);scanf(“%d”,&size);return 0;}

int input_data(){ printf(“please input the value:n”);for(i=0;i

printf(“pArray[%d]= ”,i);

scanf(“%d”,&pArray[i]);} return *pArray;}

int Compare(){ int x,y,i;x=y=p[0];for(i=0;i

if(x>=p[i])x=p[i];

if(y<=p[i])y=p[i];} printf(“min= %dt

max=%dn”,x,y);return 0;}

int Output_data(){ p=pArray;printf(“before ofpaixu :n”);for(i=0;i

printf(“%dt”,*pArray);

pArray++;} printf(“n”);return *pArray;}

void paixu(){ int x=0;int i,j;printf(“later of paixu:n”);for(i=0;i

for(j=i+1;j

{

if(p[i]>=p[j])

{

x=p[i];p[i]=p[j];p[j]=x;

}

}

printf(“%dt”,p[i]);} printf(“n”);}

void main(){ clrscr();input_size();malloc_size();input_data();Output_data();Compare();paixu();}

实验结果:

实验二

线性表及其基本操作实验(2学时)实验目的:

(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构;(2)以线性表的基本操作为基础实现相应的程序;

(3)掌握线性表的顺序存储结构和动态存储结构之区分。

实验内容:(类C算法的程序实现,任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做,其它选做);(2)有序表的合并;(3)集合的并、交、补运算; 实验准备:

1)计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分析与代码设计与分析准备。实验步骤:

1.录入程序代码并进行调试和算法分析; 2.编写实验报告。实验结果://线性链表

#include #include #define M 6

typedef struct node { int data;struct node *next;}*Sqlist;

void Initlialize(Sqlist &L){ L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;}

int Getlength(Sqlist L){ int i=0;Sqlist p=L->next;while(p!=NULL){

i++;

p=p->next;}

return i;}

int Getelem(Sqlist L,int i){

int j=1,e;Sqlist p=L->next;while(j

p=p->next;

j++;}

e=p->data;printf(“第 %d 个元素是:%dn”,i,e);return 1;}

int Locatelem(Sqlist L,int x){

int i=0;Sqlist p=L->next;while(p!=NULL&&p->data!=x){

p=p->next;

i++;} if(p==NULL)

return 0;else

{

printf(“%d 是第 %d 个元素n”,x,i);return i;} }

void CreatlistF(Sqlist &L,int a[ ],int n){ Sqlist s;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

} }

void CreatlistR(Sqlist &L,int a[],int n){

Sqlist s,r;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;r=L;for(i=0;i

s=(Sqlist)malloc(sizeof(Sqlist));

s->data =a[i];

s->next=NULL;

r->next =s;r =s;} }

int Inselem(Sqlist &L,int i,int x){ int j=1;Sqlist s,p=L->next;s=(Sqlist)malloc(sizeof(Sqlist));s->data =x;s->next =NULL;if(i<1||i>Getlength(L))

return 0;while(j

p=p->next;j++;} printf(“在第 %d 个位置插入数据:%dn”,i,x);s->next =p->next;

p->next =s;return 1;}

int Delelem(Sqlist &L,int i){

int j=1;

Sqlist p,q;

p=L;

if(i<1||i>Getlength(L))

return 0;s->data =a[i];

s->next =L->next;L->next =s;

while(j

{

p=p->next;

j++;

}

q=p->next;

p->next =q->next;

free(q);

return 1;}

void Displist(Sqlist L){ Sqlist p=L->next;

while(p!=NULL)

{

printf(“%dt”,p->data);

p=p->next;

}

printf(“n”);}

void input(int *pArray,int n){

printf(“请输入数组数据(共含 %d 个元):n”,n);

for(int i=0;i

Scanf(“%d”,&pArray[i]);

}

int main(int argc, char* argv[]){ Sqlist L;

int Array[M],Select;initlialize(L);do{

printf(“请输入选择方法(1表示头插法,2表示尾插法,0表示结束):n”);

scanf(“%d”,&Select);

switch(Select)

{

case 1: printf(“按头插法建立线性表:n”);

input(Array,M);

creatlistF(L,Array,M);

break;case 2: printf(“按尾插法建立线性表:n”);

input(Array,M);

creatlistR(L,Array,M);

break;

}

printf(“原线性表数据为:n”);Displist(L);

Getelem(L,3);

Locatelem(L,2);

Inselem(L,5,5);

printf(“修改后的线性表数据为:n”);

Delelem(L,4);

Displist(L);}while(Select!=0);return 0;} 运行结果:

实验三

栈和队列实验(6学时)实验目的:

(1)熟练掌握栈和队列的抽象数据类型及其结构特点;(2)实现基本的栈和队列的基本操作算法程序。实验内容:(类C算法的程序实现,任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作(如堆栈的PUSH、POP等操作)(必做);

(2)以表达式计算为例,完成一个可以进行算术表达式计算功能的算法设计与实现(选做); 实验准备:

1)计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分析与代码设计与分析准备。实验步骤:

1.录入程序代码并进行调试和算法分析; 2.编写实验报告。实验结果://队列存储 #include #define QueueSize 10 typedef int status;

typedef struct sqqueue { char data[QueueSize];int front,rear;}SqQueue;

void InitQueue(SqQueue &qu){ qu.front =qu.rear =0;}

status EnQueue(SqQueue &qu,char x){

if((qu.rear +1)%QueueSize==qu.front)

return 0;qu.rear =(qu.rear+1)%QueueSize;qu.data[qu.rear]=x;return 1;}

status DeQueue(SqQueue &qu,char &x){ if(qu.rear==qu.front)

return 0;qu.front =(qu.front +1)%QueueSize;x=qu.data[qu.front];return 1;}

status GetHead(SqQueue qu,char &x){ if(qu.rear ==qu.front)

return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;}

status QueueEmpty(SqQueue qu){ if(qu.rear==qu.front)

return 1;else

return 0;}

void main(){ SqQueue qu;char e;InitQueue(qu);printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”));

printf(“inser an”);

EnQueue(qu,'a');

printf(“inser bn”);

EnQueue(qu,'b');

printf(“inser cn”);

EnQueue(qu,'c');

printf(“inser dn”);

EnQueue(qu,'d');

printf(“Queue %sn”,(QueueEmpty(qu)==1?“Empty”:“Not Empty”));

GetHead(qu,e);

printf(“Queue of top elem is: %cn”,e);

printf(“show of Queue:n”);

while(!QueueEmpty(qu)){

DeQueue(qu,e);

printf(“%ct”,e);}

printf(“n”);} 实验结果:

(2)//用栈实现对表达式的求值运算

#include #include #include

#define TRUE 1 #define FALSE 0 #define OK #define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 #define STACK_INIT_SIZE

#define STACKINCREMENT 10

typedef int Status;typedef char ElemType;

typedef ElemType OperandType;

typedef char OperatorType;

typedef struct {

ElemType *base;

ElemType *top;

int stacksize;}SqStack;

Status InitStack(SqStack &S){

S.base =(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));

if(!S.base)exit(OVERFLOW);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;}

Status GetTop(SqStack S){

ElemType e;

if(S.top == S.base)return ERROR;

e = *(S.top-1);

return e;}

Status Push(SqStack &S,ElemType e)

{

if(S.top1 < n){

merge(r, r1, i, i+length-1, i + 2*length1 < n-1)

merge(r, r1, i, i+length-1, n-1);

else

for(j = i;j < n;j++)r1[j] = r[j];}

void MergeSort(SortObject * pvector){

RecordNode record[MAXNUM];

int length = 1;

while(length < pvector->n){

mergePass(pvector->record, record, pvector->n, length);

length *= 2;

mergePass(record, pvector->record, pvector->n, length);

length *= 2;

} }

SortObject vector = {8, 49,38,65,97,76,13,27,49};

int main(){

int i;printf(“排序前序列为:”);

for(i = 0;i < 8;i++)

printf(“%d ”, vector.record[i]);printf(“n”);

MergeSort(&vector);printf(“采用归并排序为:”);

for(i = 0;i < 8;i++)

printf(“%d ”, vector.record[i]);

getchar();

return 0;}

实验结果:

实验十

查找实验(2学时)* 实验目的:

(1)熟练掌握各种静态查找表方法(顺序查找、折半查找、索引顺序表等);(2)熟练掌握二叉排序树的构造方法和查找算法;

(3)了解和掌握其它查找方法。

实验内容:(类C算法的程序实现,除顺序查找算法之外,任选一个)(1)顺序查找算法的实现(必做);(2)折半查找算法的实现(选做); 实验结果://查找实验

1、顺序查找:

#include #define LENGTH 20

void SequenceSearch(int *fp,int Length){

int data;

printf(“开始使用顺序查询.请输入你想要查找的数据: ”);

scanf(“%d”,&data);

for(int i=0;i

if(fp[i]==data)

{

printf(“数据%d 是第 %d 个数据n”,data,i+1);

return;

}

printf(“未能查找到数据%d.n”,i,data);}

void main(){

int count;

int arr[LENGTH];

printf(“请输入你的数据的个数:”);

scanf(“%d”,&count);

printf(“请输入 %d 个数据:”,count);

for(int i=0;i

scanf(“%d”,&arr[i]);

SequenceSearch(arr,count);}

实验结果:

2、折半查找:

#include #include #define M 10

typedef struct { char *elem;

int length;

}SStable;

void Create(char **t)

{ int i;static char a[M+1];*t=a;for(i=1;i<=M;i++){

printf(“A[%d] is:”,i);

scanf(“%c”,&a[i]);

if(a[i]!= 'n')getchar();} }

int Searth(char *t,char k){ int i;for(i=M;i>=0 && t[i]!=k;i--);

Return i;}

void output(char *t){ int i;for(i=1;i<=M;i++)

printf(“n

A[%d] is %c”,i,t[i]);}

void px(char *t)

{ char s;int i,j;for(i=1;i<=M;i++)

for(j=i+1;j<=M;j++)

{

if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;}

} }

int Search_bin(char *t,char k){ int low=1,high=M,mid;while(low<=high){

mid=(low+high)/2;

if(k==t[mid])return mid;

else if(k

else low=mid+1;} return 0;}

void main(){ char *t,k;int s;Create(&t);output(t);printf(“nplease input you search char:”);k=getchar();s=Searth(t,k);if(s>=0)printf(“1: use search find is A[%d]n”,s);else printf(“1:can not find itn”);px(t);output(t);s=Search_bin(t,k);if(s==0)printf(“n1:can not find it n”);else printf(“n2:use Search_bin find is A[%d]n”,s);getchar();}

实验结果:

第三篇:数据结构线性表试验报告

线性表上机实习

1、实验目的

(1)熟悉将算法转换为程序代码的过程。

(2)了解顺序表的逻辑结构特性,熟练掌握顺序表存储结构的C语言描述方法。

(3)熟练掌握顺序表的基本运算:查找、插入、删除等,掌握顺序表的随机存取特性。(4)了解线性表的链式存储结构,熟练掌握线性表的链式存储结构的C语言描述方法。(5)熟练掌握线性链表(单链表)的基本运算:查找、插入、删除等,能在实际应用中灵活选择适当的链表结构。

2、实验要求

(1)熟悉顺序表的插入、删除和查找。(2)熟悉单链表的插入、删除和查找。

3、实验内容: ① 顺序表

(1)抽象数据类型定义

typedef struct {

TypeData data[maxsize];

//容量为maxsize的静态顺手表

int n;

//顺序表中的实际元素个数

}SeqList;

//静态顺序表的定义

在本次实验中,首先建立一个空的静态顺序表,然后键盘输入数据存入表中,然后进入菜单选择界面,通过不同的数字输入,实现对顺序表,删除,插入,查找,显示等操作。

(2)存储结构定义及算法思想

在顺序表结构体的定义中,typedef int TypeData 为整型,存储结构如下:

for(n=0;n

cout<<“请输入线性表数据”<

cin>>L.data[n];

//顺序将数据存入顺序表

}

//其他存储与此类似,都是直接赋值与数组的某一位

插入版块子函数:

void insert(SeqList &L)

//插入数据 {

int a,b,c,k;

cout<<“请输入插入的数及其插入的位置”<

cin>>a>>b;

if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<

k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1;

while(c>b){

L.data[c]=L.data[c-1];c--;

//通过循环,实现插入位置后的数据挨个往后移动一位

}

L.data[b]=k;} 顺序表的插入与删除操作类似,在插入与删除后,都要循环调整后面数组的每一位元素,同时记录数据元素的长度的标示符也要跟着改变。显示操作是通过循环实现表中第一个元素到最后一个元素的输出,查找操作是直接取数组中的查找位输出。

(3)实验结果与分析

② 单链表

(1)抽象数据类型定义

typedef struct node{ DataType data;

//链表的数据类型

struct node *link;

//链表的结点指针

}linknode,*linklist;

//定义了结构体linklode和结构体指针linklist

在本次实验中,首先程序自己建立一个空的头结点,通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中,有“添加链数据”,“插入链表数据”,“删除链表数据”,“查找链表数据”和“显示链表数据”功能,选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。

(2)存储结构定义及算法思想

在单链表中,typedef int DataType;DataType data;定义链表存储数据位整型。存储结构如下:

while(p->link!=NULL){ p=p->link;

k++;

//首先找到单链表的最后结点(如果是只有头结点

} 的单链表则直接跳过),以便后面接着输入数据

for(int i=0;i

{ cout<<“请输入数据”<

//开辟新的结点空间并转化为linklist指针型

cin>>q->data;

q->link=p->link;

//将前面一个结点的指向(及NULL)赋给新开辟的结点的指向

p->link=q;

//将插入点前面一个结点指向新开辟的的结点

p=q;

//将指明的最后一个一个结点向后移1位到最后一位,以便后面接着输入

}

删除结点子函数:

void delate(linklist &l){

//删除单链表数据

linklist p;int m,n,i=0;

cout<<“请输入想要删除的结点位置”<

cin>>m;

p=l;

//将头结点赋给转移指针p

while(p&&i

//查找删除结点的位置

p=p->link;

//当在单链表中间已查到删除结点或p=NULL时跳出循环

i++;

} if(p==NULL){

//当p=NULL跳出循环时,表明链表中没有该结点

cout<<“该结点不存在,删除错误”<

}

n=p->link->data;//找到删除接结点将数据取出并显示出来(找结点时是找的前一个结点)

cout<<“被删除的结点元素为: ”<

p->link=p->link->link;

//将删除结点的前后结点链接起来

}

链表的删除,插入操作是类似的,要考虑到加入或减少一个结点后,前后结点的链接关系,以及删除或插入的是最后一个结点时,新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能,显示功能也是从链表的头结点遍历至最后一个,依次输出。

(4)实验结果与分析

③ 心得体会

本次数据结构实习我收获颇丰,以前学过c语言与c++也有经常上机,但以往都是偏向于程序整体的算法设计,没有像这次的实习这样是着重在线性表,链表结构的算法设计上面。这次上机实习,让我更加熟练了结构体及结构体指针的用法,线性表的设计等等,同时在这次实习中,引用,指针,地址这三个的用法曾一度让我混淆,在查阅书籍后才得以解决,也希望老师在课堂上有时间时给我们详细讲解一下,指针,地址,引用三者的使用。

附录:

顺序表源代码: #include using namespace std;#define maxsize 50 typedef int TypeData;typedef struct { TypeData data[maxsize];int n;}SeqList;

void makeSeq(SeqList &L)// 据 { int m,n,k;cout<<“请输入线性表长度”<>m;for(n=0;n>L.data[n];} L.n=m;cout<<“您输入的线性表为:”<

输入线性表数输出线性表数据

void insert(SeqList &L)//插入数据 { int a,b,c,k;cout<<“请输入插入的数及其插入的位置”<>a>>b;if(b<=0||b>(L.n+1)){cout<<“不能在该位置插入”<b){ L.data[c]=L.data[c-1];c--;} L.data[b]=k;} void delate(SeqList &L)//删除数据 { int wei;cout<<“请输入想要删除数据的位置”<>wei;if(wei<1||wei>L.n){ cout<<“不能在该位置删除”<>a;if(a<=0||a>(L.n)){cout<<“不能在该位置插入”<

cout<<“删除 2”<>xuanze;switch(xuanze){ case 1: insert(L);break;case 2: delate(L);break;case 3: find(L);break;case 4: showSeq(L);break;default :break;} } }

单链表源代码:

#include using namespace std;typedef int DataType;typedef struct node{ DataType data;struct node *link;}linknode,*linklist;

linklist chushihua(){ linklist L;L=(linklist)malloc(sizeof(linknode));L->link=NULL;cout<<“开辟空间成功,头结点建立”<>a;linklist p,q;

p=l;while(p->link!=NULL){ p=p->link;k++;} for(int i=0;i>q->data;q->link=p->link;p->link=q;p=q;} } void show(linklist l){ cout<<“链表数据为:”<link;while(p!=NULL){ cout<

data<<“ ”;p=p->link;} cout<>m;linklist p;p=l->link;while(p&&ilink;i++;} if(!p){ cout<<“链表没有这么长,查找错误”<data<

{ linklist p,q;int m,n,i=0;

cout<<“请输入您要插入的结点位置及插入的数据”<>m>>n;p=l;while(p&&ilink;i++;} if(p==NULL){ cout<<“不能在该位置插入,插入错误”<

q=(linklist)malloc(sizeof(linknode));q->data=n;q->link=p->link;p->link=q;}

void delate(linklist &l){ linklist p;int m,n,i=0;cout<<“请输入想要删除的结点位置”<>m;p=l;while(p&&ilink;i++;} if(p==NULL){ cout<<“该结点不存在,删除错误”<link->data;cout<<“被删除的结点元素为: ”<link=p->link->link;} void main(){ linklist L;int select;

L=chushihua();

while(1){ cout<<“请选择功能”<>select;switch(select){

case 1: shuru(L);break;case 2: insert(L);break;case 3: delate(L);break;case 4: find(L);break;case 5: show(L);break;default :break;} } }

第四篇:北京科技大学数据结构试验报告(附录含代码)

一、1)功能描述

输入数据(设为整型)建立单链表,并求相邻两节点data值之和为最大的第一节点。2)详细设计

遵循链表建立的基本思想,建立一个新的链表,H为表头,r为新节点,p为表尾节点指针,没存入一个新的数据则申请一个新的节点,知道没有数据输入,利用循环和打擂台法,比较和的大小,并输出。3)测试分析

程序调试完成后,选取两组数据进行测试,都得出了正确结果(数据以0为结束符,若有相同和,则取第一组)结果截图

4)心得体会

通过做第一题,学习到链表的建立以及链表里指针的使用,并且复习了比较法里面的打擂台法。

二、1)功能描述

实现算术表达式求值程序(栈的运用),输入中缀表达式,可将其转换成后缀表达式 2)详细设计

本题目的程序是根据课本上的程序改进之后得出的,课本上有完整的程序,但是有bug,按照课本上的程序,结果会出现“烫烫烫烫烫”,原因是对于优先级的比较没有处理好,因此加了两行代码,将优先级的比较处理好,即现在的程序。3)测试分析

程序调试完成后,选取题目所给的式子进行测试,得出了正确后缀表达式结果 结果截图

4)心得体会

通过做第二题,对于课本上的知识表示得出“实践出真知”的真理,即使书上的东西也不一定就是正确的,尤其是代码,最好是个人自己真正实践一下。

三、1)功能描述

实现链式队列运算程序(队列的运用)2)详细设计

本题目是队列相关应用,队列和栈是相反的,队列是先进的先出,因此输入12345,先出的是1,本着队列的这一特性,根据课本所学的队列的算法,设计了如下程序。3)测试分析

程序调试完成后,选取12345进行测试,后缀加0,则一个字符出队,只输入0,则继续出队,输入@,则打印剩余全部元素。结果截图

4)心得体会

通过做第三题,对于队列的特点有了更加深刻的认识,尤其区分队列与栈的不同点,需要特别注意。

四、1)功能描述

①构造关于F的Huffman树;

②求出并打印D总各字符的Huffman编码。2)详细设计

本题目是Huffman树的应用以及Huffman编码的应用,参照课本上关于Huffman树的建立以及Huffman编码的应用的实现,将所给数据依权值最小原则建立Huffman树,并实现Huffman编码。3)测试分析

程序调试完成后,给出数据abcdefgh,相应频率为12345678,运行代码得出结果如图。同时选取另一组数据测试也得出了正确结论

结果截图

4)心得体会

通过做第四题,对于Huffman树有了更加深刻的体会,同时练习也使得对课本知识进行实践,有助于更好的理解Huffman树的算法。

五、1)功能描述

设英文句子:“everyone round you can hear you when you speak.”(1)依次读入句中各单词,构造一棵二叉排序树;(2)按LDR遍历此二叉排序树。

LDR: can everyone hear round speak when you(有序)

2)详细设计

本题目是有关二叉树的建立和中序遍历的,二叉树作为数据存储一个很重要的结构,它的建立也是很重要的。本题目代码设计上采用课本上的对于二叉树建立的方法,将所给单词以二叉树形式建立并存储,然后中序遍历的到字典顺序。3)测试分析

程序调试完成后,给出单词串everyone round you can hear you when you speak,运行代码得出中序遍历结果如图。结果截图

4)心得体会

通过做第五题,练习运用二叉树模型解决了一些实际问题如现实中字典的编排问题,在熟悉算法的基础上,同时得出结论,好的算法可以应用与实际生活生产,使之更为便捷。

附录 程序代码 实验一:

#include“stdio.h” #include“malloc.h” typedef struct node {

int data;

struct node *next;}list,*List;List Creatlist()

//建立链表函数 { List H,p,r;

//H为表头,r为新节点,p为表尾节点指针

H=(List)malloc(sizeof(list));

//建立头节点

r=H;

p=(List)malloc(sizeof(list));

//申请新节点

while(scanf(“%d”,p)&&p->data!=0)//输入数据,直到为零(结束标志)

{

r->next=p;//新节点链入表尾

r=p;

p=(List)malloc(sizeof(list));

} r->next=NULL;//将尾节点的指针域置空

return H;

//返回已创建的头节点 } List Adjmax(List H)//比较相邻两数之和

{

//返回相邻两数之和最大的第一个数指针

List p,r,q;int sum=0;p=H->next;if(H->next ==NULL)//判断是否为空

{

printf(“Empty List!”);

q=(List)malloc(sizeof(list));

q->data =0;}

while(p!=NULL)//比较相邻两数之和

{

r=p->next;

if(p&&r)

if(r->data+p->data>sum)

{

q=p;

sum=r->data +p->data;}//不断赋给sum新的最大值

else;

p=p->next;} return q;} int main(){ char ch;printf(“/// 请输入整形数据,以空格隔开,0结束。/// n”);printf(“Ready? nY/N(enter 'y' or 'Y' to continue)n”);while(scanf(“%c”,&ch)&&(ch=='Y'||ch=='y'))

{

List H,pmax;

H=Creatlist();

pmax=Adjmax(H);

printf(“相邻两数之和最大的第一个数为:%dnContinue?

Y/N

free(H);

scanf(”%c“,&ch);} return 0;}

”,pmax->data);实验二:

#include #include #include typedef struct node //栈节点类型 { char data;//存储一个栈元素

struct node *next;//后继指针 }snode,*slink;int Emptystack(slink S)//检测栈空 { if(S==NULL)return(1);else return(0);} char Pop(slink*top)//出栈 { char e;slink p;if(Emptystack(*top))return(-1);//栈空返回

else {

e=(*top)->data;//取栈顶元素

p=*top;*top=(*top)->next;//重置栈顶指针

free(p);return(e);} } void Push(slink*top,char e)//进栈 { slink p;p=(slink)malloc(sizeof(snode));//生成进栈p节点

p->data=e;//存入元素e p->next=*top;//p节点作为新的栈顶链入

*top=p;} void Clearstack(slink*top)//置空栈 { slink p;while(*top!=NULL){

p=(*top)->next;

Pop(top);//依次弹出节点直到栈空

*top=p;} *top=NULL;} char Getstop(slink S)//取栈顶 { if(S!=NULL)return(S->data);return(0);} //符号优先级比较

int Precede(char x,char y)//比较x是否“大于”y { switch(x){

case '(':x=0;break;case '+': case '-':x=1;break;case '*': case '/':x=2;break;default: x=-1;} switch(y){ case '+': case '-':y=1;break;case '*': case '/':y=2;break;case '(':y=3;break;default: y=100;} if(x>=y)return(1);else return(0);} //中后序转换

void mid_post(char post[],char mid[])//中缀表达式mid到后缀表达式post的转换的算法 { int i=0,j=0;char x;

slink S=NULL;//置空栈 Push(&S,'#');//结束符入栈 do { x=mid[i++];//扫描当前表达式分量x switch(x){ case '#':

{ while(!Emptystack(S))

post[j++]=Pop(&S);

}

}break;case ')':

{ while(Getstop(S)!='(')

post[j++]=Pop(&S);//反复出栈直至遇到'('

Pop(&S);//退掉'('

}break;case '+': case '-': case '*': case '/': case '(':

{ while(Precede(Getstop(S),x))//栈顶运算符(Q1)与x比较

post[j++]=Pop(&S);//Q1>=x时,输出栈顶符并退栈

Push(&S,x);//Q1

}break;default:post[j++]=x;//操作数直接输出

} }while(x!='#');post[j]='';//后缀表达式求值

int postcount(char post[])//后缀表达式post求值的算法 { int i=0;char x;float z,a,b;slink S=NULL;//置栈空

while(post[i]!='#'){ x=post[i];//扫描每一个字符送x

switch(x)

{case '+':b=Pop(&S);a=Pop(&S);z=a+b;Push(&S,z);break;

case '-':b=Pop(&S);a=Pop(&S);z=a-b;Push(&S,z);break;

case '*':b=Pop(&S);a=Pop(&S);z=a*b;Push(&S,z);break;

case '/':b=Pop(&S);a=Pop(&S);z=a/b;Push(&S,z);break;//执行相应运算结果进栈

default:x=post[i]-'0';Push(&S,x);//操作数直接进栈

} i++;} if(!Emptystack(S))return(Getstop(S));//返回结果 } void main(){ char post[255],mid[255]=“";printf(”请输入要处理的中缀表达式:n“);

} scanf(”%s“,mid);printf(”相应的后缀表达式为:n“);mid_post(post,mid);printf(”%sn“,post);printf(”表达式的值为:%dn“,postcount(post));getch();实验三:

#include”stdio.h“ #include”malloc.h“ #define max 1000

typedef struct node { char ch[max];int front,rear;}squeue,*sq;void Clearqueue(sq Q){

Q->front=Q->rear;} int Emptyqueue(sq Q){ if(Q->rear==Q->front)

return 1;else

return 0;} void Enqueue(sq Q,char ch){ if(Q->rear>=max){

printf(”FULL QUEUE!“);} else {

Q->ch [Q->rear]=ch;

Q->rear ++;}} void Dequeue(sq Q){ if(Emptyqueue(Q)){

printf(”Empty QUEUE!n“);} else {

printf(”出队:%cn“,Q->ch[Q->front]);

Q->front ++;} } void Printqueue(sq Q){ if(Emptyqueue(Q))

;

else {

printf(”队列中全部元素:n“);

while(Q->front!=Q->rear-1)

{

printf(”%c“,Q->ch[Q->front]);

Q->front++;

}

printf(”n“);} } int main(){

sq Queue;

char f;

printf(”*******************************************n“);

printf(”请输入字符XnX ≠'@'并且 X ≠'@'字符入队;n“);

printf(”X='0',字符出队;n“);

printf(”X='@',打印队列中各元素。n“);

printf(”*******************************************n“);

Queue=(sq)malloc(sizeof(squeue));

Queue->front =Queue->rear=0;

while(scanf(”%c“,&f)&&f!='@')

{

if(f!='0')

Enqueue(Queue,f);

else

Dequeue(Queue);

}

if(f=='@')

Printqueue(Queue);

else;return 0;} 实验四:

#include”stdio.h“ #include”malloc.h“ #define N 8 #define MAX 100 #define M 2*N-1 typedef struct { char letter;int w;int parent,lchild,rchild;}Huffm;typedef struct { char bits[N+1];int start;char ch;}ctype;void inputHT(Huffm HT[M+1]){ int i;

for(i=1;i<=M;i++){

HT[i].w=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;}

printf(”请输入电文字符集:“);for(i=1;i<=N;i++){

scanf(”%c“,&HT[i].letter);

}

printf(”请输入字符出现的频率:“);for(i=1;i<=N;i++){

scanf(”%d“,&HT[i].w);} } void CreatHT(Huffm HT[M+1]){ int i,j,min1,min2;int tag1,tag2;

//权值最小两个点标号;

for(i=N+1;i<=M;i++){

tag1=tag2=0;

min1=min2=MAX;

for(j=1;j<=i-1;j++)

{

if(HT[j].parent ==0)

if(HT[j].w

{ min2=min1;

min1=HT[j].w;

tag2=tag1;

tag1=j;

}

else

if(HT[j].w

{

min2=HT[j].w;

tag2=j;

}

}

HT[tag1].parent =HT[tag2].parent =i;

HT[i].lchild =tag1;

HT[i].rchild =tag2;

HT[i].w =HT[tag1].w +HT[tag2].w;

} } void Huffmcode(Huffm HT[M+1])// Huffm编码函数

{ int i,j,p,tag;

ctype mcode,code[N+1];for(i=1;i<=N;i++){

code[i].ch=HT[i].letter;

} for(i=1;i<=N;i++){

mcode.ch =code[i].ch;

mcode.start=N+1;

tag=i;

p=HT[i].parent;

for(j=0;j<=N;j++)

mcode.bits [j]=' ';

while(p!=0)

{

mcode.start--;

if(HT[p].lchild ==tag)

mcode.bits[mcode.start ]='0';

else

mcode.bits [mcode.start ]='1';

tag=p;p=HT[p].parent;

}

code[i]=mcode;

} for(i=1;i<=N;i++){

printf(” '%c'的Huffm编码为:“,code[i].ch);

for(j=0;j<=N;j++)

printf(”%c“,code[i].bits [j]);

printf(”n“);} } int main(){ char ch;

printf(”******************************************************n“);printf(”电文字符集含8个字符,连续输入,不同频率之间以空格隔开 n“);

printf(”******************************************************n“);

ch='y';while(ch=='y'){

Huffm HT[M+1];

inputHT(HT);

CreatHT(HT);

Huffmcode(HT);

printf(”Continue? Y/N “);

fflush(stdin);

scanf(”%c“,&ch);

fflush(stdin);} }

实验五:

#include”stdio.h“ #include”malloc.h“ #include”string.h“ typedef struct bsnode { char word[20];struct bsnode *lchild,*rchild;}BStree,*BST;BST BSTinsert(BST T,BST s){ BST f,p;if(T==NULL)

return s;p=T;f=NULL;while(p){

f=p;

if(strcmp(s->word,p->word)==0)

{

free(s);

return T;

}

if(strcmp(s->word,p->word)<0)

p=p->lchild;

else

p=p->rchild;} if(strcmp(s->word ,f->word)<0)

f->lchild=s;else

f->rchild=s;return T;} BST CreatBst(){ BST T,s;char keyword[20];T=NULL;gets(keyword);while(keyword[0]!='0'){

s=(BST)malloc(sizeof(BStree));

strcpy(s->word,keyword);

s->lchild=s->rchild=NULL;

T=BSTinsert(T,s);

gets(keyword);} return T;} void Inorder(BST T){ if(T){

Inorder(T->lchild);

printf(”%s “,T->word);

Inorder(T->rchild);} } int main(){ char ch;BST T;printf(”************************************************************n“);printf(”请输入英文句子,每输入一个单词以回车结束,句子结束以'0'结束。n“);

printf(”************************************************************n“);ch='y';while(ch=='Y'||ch=='y'){ T=CreatBst();

printf(”按LDR遍历此二叉排序树(字典顺序):n“);Inorder(T);free(T);printf(”nContinue? Y/N

“);scanf(”%c",&ch);}}

第五篇:数据结构 实验一 图[推荐]

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称: 实验二——图 学生姓名: 佘晨阳 班

级: 2014211117 班内序号: 20 学

号: 2014210491 日

期: 2015年12月05日

1.实验要求

根据图的抽象数据类型的定义,使用邻接矩阵或邻接表实现一个图。图的基本功能:

1、图的建立

2、图的销毁

3、深度优先遍历图

4、广度优先遍历图

5、使用普里姆算法生成最小生成树

6、使用克鲁斯卡尔算法生成最小生成树

7、求指定顶点到其他各顶点的最短路径

8、其他:比如连通性判断等自定义操作

编写测试main()函数测试图的正确性

2.程序分析

本实验要求掌握图基本操作的实现方法,了解最小生成树的思想和相关概念,了解最短路径的思想和相关概念,学习使用图解决实际问题的能力。

2.1 存储结构

存储结构:1.不带权值的无向图邻接矩阵

2.带权值的无向图邻接矩阵

3.带权值的有向图邻接矩阵

1.不带权值的无向图邻接矩阵

第1页 北京邮电大学信息与通信工程学院

2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵

[备注]:

1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式

2.2 关键算法分析

第2页 北京邮电大学信息与通信工程学院

一.图的邻接矩阵构造函数:

1.关键算法: template Graph::Graph(f a[], int n, int e)

//带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}

//初始化顶点

for(k = 0;k

for(i = 0;i < n;i++)

{

arc[k][i] =-1;

if(i == k)arc[k][i] = 0;

//初始化权值的大小

}

visited[k] = 0;} cout << endl;for(k = 0;k

//初始化边

{

cout << “请输入线性链接节点:”;

cin >> s1 >> s2 >> height;

arc[convert(s1)][convert(s2)] = height;

arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵

} cout << endl;cout << “所得邻接矩阵为:” << endl;

for(k = 0;k

for(i = 0;i < n;i++)

{

if(arc[k][i] ==-1)

cout << “∞” << “ ”;

else cout << arc[k][i] << “ ”;

//打印邻接矩阵的格式

}

cout << endl;

} cout << endl 2.算法的时间复杂度

第3页 北京邮电大学信息与通信工程学院

有构造可知,初始化时其时间复杂度:O(n2)

二.深度优先便利DFS:

1.关键算法

①从某顶点v出发并访问

②访问v的第一个未访问的邻接点w,访问w的第一个未访问的邻接点u,……

③若当前顶点的所有邻接点都被访问过,则回溯,从上一级顶点的下一个未访问过的顶点开始深度优先遍历

④直到所有和v路径相通的顶点都被访问到; 2.代码图解:

深度优先遍历示意图 3.代码详解:

template void Graph::DFS(int v){ cout << vertex[v];visited[v] = 1;

for(int j = 0;j < vnum;j++)

//连通图

if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时,则连通深一层遍历

} 4.时间复杂度

时间复杂度:O(n2)

空间复杂度:栈的深度O(n)

辅助空间O(n)

第4页 北京邮电大学信息与通信工程学院

三.广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3…

③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③,直到所有和v路径相通的顶点都被访问到;

2.代码图解

3.代码详解

1.初始化队列Q

2.访问顶点v,visited[v]=1

3.while(队列非空)

3.1 v=队头元素出队

3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度

时间复杂度:O(n2)

空间复杂度:辅助空间O(n)

四.最小生成树——普里姆算法

1,关键思路

一般情况下,假设n个顶点分成两个集合:U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点),则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构:

邻接矩阵 辅助数据结构:

int

adjvex[MAXSIZE];// U集中的顶点序号

第5页 北京邮电大学信息与通信工程学院

int

lowcost[MAXSIZE];

// U(V-U)的最小权值边

2.代码图解

第6页 北京邮电大学信息与通信工程学院

第7页 北京邮电大学信息与通信工程学院

3;代码详解

template void Graph::Prim(){ for(int i = 0;i < vnum;i++)

//辅助数组存储所有到的V0边

{

adjvex[i] = 0;lowcost[i] = arc[0][i];

} lowcost[0] = 0;for(int j = 1;j < vnum;j++)

//循环n-1次

{

int k = Mininum(lowcost);

//求下一个顶点

cout << vertex[adjvex[k]] << “->” << vertex[k] << endl;

lowcost[k] = 0;

//U=U+{Vk}

for(int j = 0;j < vnum;j++)

//设置辅助数组

{

if((lowcost[j]!= 0 && arc[k][j] < lowcost[j]))

{

lowcost[j] = arc[k][j];

adjvex[j] = k;

}

}

第8页 北京邮电大学信息与通信工程学院

} } 4,时间复杂度:

时间复杂度O(n2),适合稠密图

五.最小生成树----克鲁斯卡尔算法

1,关键思路

先构造一个只含n个顶点的子图SG,然后从权值最小的边开始,若它的添加不使SG中产生回路,则在SG上加上这条边,如此重复,直至加上n-1条边为止。2.代码图解:

3.代码详解

template void Graph::Kruskal()

//最小生成树—kruskal算法

{ cout<<“Krusal算法结果为:”<

int k = 0, j = 0;

while(k < vnum-1){

int m = vedgelist[j].fromv, n = vedgelist[j].endv;

int sn1 = vset[m];

int sn2 = vset[n];

//两个顶点分属

第9页 北京邮电大学信息与通信工程学院

不同的集合 if(sn1!= sn2)

{

cout << vertex[m] << “->” << vertex[n] << endl;

k++;

for(int i = 0;i < vnum;i++)

{

if(vset[i] == sn2)

vset[i] = sn1;

//集合sn2全部改成sn1

}

}

j++;} } 4.时间复杂度

时间复杂度O(nlogn),适合稀疏图

六.最短路径——Dijkstra算法 1.关键代码

• 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点,• 2)初始状态:s=源点v • 3)叠代算法:

• 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的,加入s

……

2.代码图解

第10页 北京邮电大学信息与通信工程学院

3.代码详解

emplate void Graph::ShotPath(f x)

//关于最短路径的初始化 { int v=convert(x);

for(int i = 0;i < vnum;i++)

//初始化路径和点

{

s[i]=0;

disk[i] = arc[v][i];

if(disk[i]!= maxs)path[i] = v;

else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++)

//反复经过从该点到其他点的路径

{

if((v = FindMin())==-1)continue;

s[v] = 1;

for(int j = 0;j < vnum;j++)

if(!s[j] &&(disk[j]>arc[v][j] + disk[v]))

{

第11页 北京邮电大学信息与通信工程学院

disk[j] = arc[v][j] + disk[v];

path[j] = v;

} } Print();

//打印路径长度和遍历

} 4.时间复杂度

时间复杂度为:n^2

七.判断连通图算法

template bool Graph::judgegraph(){ DFS(convert(vertex[0]));if(count==vnum)

{

cout<<“该图为连通图!*******输入成功!”<

return false;

} else {

cout<<“该图不为连通图!*******请重新输入”<

return true;

} }

时间复杂度:n^2

3.程序运行结果

1.测试主函数流程:

第12页 北京邮电大学信息与通信工程学院

函数流程图:

1.输入图的连接边并打印

构造下面所示图的邻接矩阵:

第13页 北京邮电大学信息与通信工程学院

2.判断图连通是否成功

3.BFS DFS PRIM算法的实现

第14页 北京邮电大学信息与通信工程学院

4.克鲁斯卡尔算法实现过程

4.有向图邻接矩阵的构建

第15页 北京邮电大学信息与通信工程学院

插入V0位置后打印距离并开始回溯

总结

1.调试时出现的问题及解决的方法

问题一:prim算法中

解决方法:调整循环条件,修正函数体注意有无Next的区别

第16页 北京邮电大学信息与通信工程学院

问题二:BFS和DFS同时在一个类里作用时会输出错误

解决方案:每次BFS/DFS使用时都把visited数组初始化一遍

问题三:在最短路径,经常出现了停止输入的情况

解决方法:改return为continue,并修改打印算法 2.心得体会

通过本次实验,基本熟练掌握了c++基本语句,尤其对图的结构及应用有了较深了解;调试代码时尽量做到完成一个代码段调试一次,可以最快检测出错误所在;类的封装和调用,类的共有成员和私有成员的设置。

3.下一步的改进

第一,设置增加图节点和边的函数

第二,实现图形化输出图的路径的功能

第三,主函数设计简单,不要过于累赘

4.程序中出现的亮点

1)利用dfs算法衍生生成判断是否为连通图的连通算法

2)采用graph类实现所有图的所有算法,所需的数据类型均在私有成员内,封装 3)利用convert函数采取象意输入,采用ABCD的节点输入方式而并非转化成01234再输入。

4)BFS中采用c++标准库的。

5)打印邻接矩阵时,打印出非链接的∞符号和与自身路径的0距离 6)判断图为非连通图后,提示输入错误,重新输入图元素

第17页

下载数据结构试验报告一海龟作图(样例5)word格式文档
下载数据结构试验报告一海龟作图(样例5).doc
将本文档下载到自己电脑,方便修改和收藏,请勿使用迅雷等下载。
点此处下载文档

文档为doc格式


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:645879355@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。

相关范文推荐