数据结构实验报告

时间：2021-03-03 18:28:35 来源：蒲公英阅读网 本文已影响人

相关热词搜索：数据结构 实验 报告

数据结构实验报告 本文关键词：数据结构，实验，报告

数据结构实验报告 本文简介：计算机科学与技术学院实验报告课程名称：数据结构专业：计算机科学与技术班级：2011级1班学号：201113137024姓名：镇方权指导老师：邱奕敏20实验一1.实验题目设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到

数据结构实验报告 本文内容：

计算机科学与技术学院

实验报告

课程名称：数据结构

专

业：计算机科学与技术

班

级：2011

级

1

班

学

号：

201113137024

姓

名：

镇方权

指导老师：

邱奕敏

20

实验一

1.

实验题目

设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

2.

程序核心代码

struct

LNode

{

int

data;

struct

LNodenext;

};

typedef

struct

LNodeLinkList;

LinkList

Union(

LinkList

ha,LinkList

hb

)

{

LinkList

head

=

(LNode*)malloc(sizeof(LNode));

head->next

=

ha;

LNode*

pa,*pb,*pTmp;

pa

=

ha->next;

pb

=

hb->next;

pTmp

=

ha;

while

(

pa

pa

=

pa->next;

}

else

if

(

pa->data

>

pb->data

)

{

LNode*

Lr

=

(LNode*)malloc(sizeof(LNode));

Lr->data

=

pb->data;

Lr->next

=

pa;

pTmp->next

=

Lr;

pTmp

=

Lr;

pb

=

pb->next;

}

else

{

pTmp

=

pa;

pa

=

pa->next;

pb

=

pb->next;

}

}

if

(

pa

)

{

pTmp->next

=

pa;

}

else

{

while

(

pb

)

{

LNode*

Lr

=

(LNode*)malloc(sizeof(LNode));

Lr->data

=

pb->data;

pTmp->next

=

Lr;

pTmp

=

Lr;

pb

=

pb->next;

}

pTmp->next

=

NULL;

}

free(head);

return

ha;

}

int

ListInsert(LinkList

L,int

i,int

e)

{

int

j=0;

LinkList

p=L,s;

while(p

j++;

}

if(!p||j>i-1)

return

0;

s=(LinkList)malloc(sizeof(struct

LNode));

/*

生成新结点/

s->data=e;

/*

插入L中/

s->next=p->next;

p->next=s;

return

1;

}

int

main()

{

LinkList

ha,hb;

int

n,i;

int

data;

InitList(

printf(“请输入ha中数据的个数：

“);

scanf(“%d“,printf(“请依次输入ha中的数据：/n“);

for(int

i

=

1;i

next;

while(p)

{

printf(“%d

“,p->data);

p

=

p->next;

}

printf(“/n“);

InitList(

printf(“请输入hb中数据的个数：

“);

scanf(“%d“,printf(“请依次输入hb中的数据：/n“);

for(i

=

1;i

next;

while(p)

{

printf(“%d

“,p->data);

p

=

p->next;

}

printf(“/n“);

printf(“hb归并到ha后，新的ha=“);

p

=

Union(ha,hb)->next;

while(p)

{

printf(“%d

“,p->data);

p

=

p->next;

}

printf(“/n“);

system(“pause“);

return

0;

}

3.

运行结果

4.实验总结

要注意归并时若ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

实验二

1.

实验题目

结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。

2.

程序核心代码

typedef

struct

LNode{

int

data;

//存储系数

int

flag;

//存储对应幂数

struct

LNodenext;

}LNode;

//建立带头结点的单链表，n项多项式

void

CreateList(LNode*L,int

n)

{

LNodep;

int

i

=

0;L

=

(LNode)

malloc

(sizeof(LNode));

(*L)->next

=

NULL;

for

(i

=

0;

idata),p->next

=

(*L)->next;

(*L)->next

=

p;

//插入链表

}

}

//多项式L1与L2对应项相加得到新的L2

void

PolyoAdd(LNode*L1,LNode*L2)

{

int

ck;

LNodep,*q;

p

=

NULL;

q

=

NULL;

q

=

(*L1)->next;

while(q)

{

ck

=

0;

p

=

(*L2)->next;

while(p)

{

if

(q->flag

==

p->flag){

ck

=

1;

break;

}

p

=

p->next;

}

if

(ck

==

1)

//同类项合并

{

p->data

+=

q->data;

q

=

q->next;

}

else

//否则，直接将非同类项插到L2最前面

{

(*L1)->next

=

q->next;

q->next

=

(*L2)->next;

(*L2)->next

=

q;

q

=

(*L1)->next;

}

}

}

int

main()

{

int

m=0;

LNodep1,*p2;

p1

=

NULL;

p2

=

NULL;

printf(“设定多项式A的项数：/n“);

scanf(“%d“,printf(“请输入多项式A的系数及对应位幂次：/n“);

CreateList(

printf(“A“);

PolyoPrint(

printf(“设定多项式B的项数：/n“);

scanf(“%d“,printf(“请输入多项式B的系数及对应位幂次：/n“);

CreateList(

printf(“B“);

PolyoPrint(

PolyoAdd(

printf(“相加后的“);

PolyoPrint(

system(“pause“);

return

0;

}

3.

运行结果

4.

实验总结

合并多项式是指相同指数的项的系数相加，比较两个链表的节点的指数的大小，作为指针移动的条件，同事合并的过程中应消除系数项为零的节点。

实验三

1.

实验题目

二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild

下标

data

lchild

rchild

1

A

2

6

2

B

3

4

3

C

0

0

4

D

5

0

5

E

0

0

6

F

0

7

7

G

0

0

和rchild的类型为bitree。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild

为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，二叉树的静态二叉链表如上图所示。编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。

2.

程序核心代码

typedef

struct

BiTNode

{

char

data;

struct

BiTNodelchild,*rchild;

}BiTNode,*BiTree;

typedef

struct

Node

//静态链表结点结构

{

char

data;

//结点数据

int

row,lchild,rchild

;

//下标，左右孩子

}Node;

Nodest;

//st容量足够大

static

int

length=0;

static

int

num=0;

void

createBiTree(BiTree

scanf(“%c“,if

(ch==

#

)

T

=

NULL;

else

{

if

(!(T

=

(BiTNode)malloc(sizeof(BiTNode))))

printf(“error“);

T->data

=

ch;

//

生成根结点

createBiTree(T->lchild);

//

构造左子树

createBiTree(T->rchild);

//

构造右子树

}

}

void

PreOrder(BiTree

bt)

//

先序遍历二叉树，填写静态链表的“下标”和data域

{

if

(bt)

{

st[++num].data=bt->data;

st[num].row=num;

PreOrder(bt->lchild);

PreOrder(bt->rchild);

}

}

int

Locate(char

x)

{

//在静态链表中查二叉树结点的下标

int

i;

{

for

(i=1;idata

==

x)

return

p;

if(p->lchild)

queue[rear++]

=

p->lchild;

if(p->rchild)

queue[rear++]

=

p->rchild;

}

}

}

void

DynaToST

(BiTree

t){

int

i;

BiTree

p;

PreOrder(t);

for(i

=

1;i

lchild)

st[i].lchild

=

Locate(p->lchild->data);

else

st[i].lchild=0;//无左孩子，其lchild域填0

if(p->rchild)

st[i].rchild

=

Locate(p->rchild->data);

else

st[i].rchild=0;//无右孩子，其rchild域填0

}

}

int

main(){

BiTree

t;

printf(“请输入二叉树各结点的值:/n“);

createBiTree(t);

nodeNum(t);

st

=

(Node*)malloc(sizeof(struct

Node)*length);

DynaToST(t);

show(st);

return

0;

}

3.

运行结果

4.

实验体会

二叉树的建立是按照先序遍历的方式递归的建立的，因此在输入二叉树的节点中的值时，要注意#字符的个数。

实验四

1.

实验题目

设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接表本身所占空间之外只用O（1）辅助空间。

2.

程序核心代码

struct

edgenode//表结点

{int

endver;

edgenode*

edgenext;

};

struct

vexnode//头结点

{

char

vertex;

edgenode

edgelink;

};

struct

Graph//无向图

{

vexnode

adjlists[Max_Ver_Num];

int

vexnum,arcnum;

};

void

CreatAdjList(Graph*

G)

{

int

i,j,k;

edgenode

p1;

edgenode

p2;

cout>G->vexnum>>G->arcnum;

coutvexnum;i++)

{

cin>>G->adjlists[i].vertex;

G->adjlists[i].edgelink=NULL;

}

coutarcnum;k++)

{

cout对应的顶点序号:“;

cin>>i>>j;

coutendver=j;

p1->edgenext=G->adjlists[i].edgelink;

//将结点始终插到表结点后

G->adjlists[i].edgelink=p1;

p2=new

edgenode;

p2->endver=i;

p2->edgenext=G->adjlists[j].edgelink;

G->adjlists[j].edgelink=p2;

}

}

void

DFS(GraphG,int

i,int

visited[])

{

coutadjlists[i].vertexadjlists[i].edgelink;

if(G->adjlists[i].edgelink

}

}

void

DFStraversal(GraphG,char

c)

{

coutvexnum;

i++)

{

visited[i]=0;

}

for

(int

i=1;ivexnum;i++)

{

if

(G->adjlists[i].vertex==c)

{

DFS(G,i,visited);

break;

}

}

for(int

i=1;ivexnum;i++)

{

if(visited[i]==0)

DFS(G,i,visited);

}

cout>Vi;

DFStraversal(G,Vi);

coutdata=number;

p->lchild

=p->rchild=NULL;

if(head==NULL)

{

return

p;

}

else

{

if(p->data

data)

head->lchild=createBST(head->lchild,number);

else

head->rchild=createBST(head->rchild,number);

return

head;

}

}

//求p的双亲

BiTree

searchParent(BiTree

head,BiTree

p)

{

if(head->lchild==p||head->rchild==p||head==p||head==NULL)

return

head;

else

{

if(p->data

data)

return

searchParent(head->lchild,p);

else

return

searchParent(head->rchild,p);

}

}

//删除二叉排序树中结点p

bool

Delete(BiTree

p){

BiTree

q,s;

q=(BiTree)malloc(sizeof(BiTNode));

s=(BiTree)malloc(sizeof(BiTNode));

if(!p->rchild

if(q->lchild==p)

q->lchild=NULL;

else

q->rchild=NULL;

}

else

if(!p->rchild){

//左子树不为空，右子树为空

searchParent(head,p)->lchild

=

p->lchild;

free(p);

}

else

if(!p->lchild){

//右子树不为空，左子树为空

searchParent(head,p)->rchild

=

p->rchild;

free(p);

}

else

{

//左右子树都不为空

q=p;

s=p->lchild;

while(s->rchild){

q=s;

s=s->rchild;

}

p->data=s->data;

if(q!=p)

q->rchild=s->lchild;

else

q->lchild=s->lchild;

delete

s;

}

return

true;

}

bool

deleteBST(BiTree

Head,int

number){

if(!Head)

return

false;

else{

if(Head->data

==

number)

return

Delete(Head);

else

if(number

data)

return

deleteBST(Head->lchild,number);

else

return

deleteBST(Head->rchild,number);

}

}

//主程序

int

main(){

BiTree

Head;

printf(“建立一棵二叉排序树,请输入你要建树的所有数(以-1

作为结束标志!):

/n“);

Head=NULL;

int

number,n;

scanf(“%d“,while(number!=-1)

{

Head=createBST(Head,number);

scanf(“%d“,}

head=Head;

printf(“中序遍历二叉排序树为：

/n“);

printBST(Head);

printf(“/n“);

printf(“请输入要删除的结点:

“);

scanf(“%d“,if(deleteBST(Head,n))

printf(“删除成功！/n“);

else

printf(“删除失败！/n“);

printf(“删除之后的二叉排序树中序遍历为：/n“);

printBST(Head);

printf(“/n“);

return

0;

}

3.

运行结果

4.

实验体会

二叉排序树的删除要注意分类讨论，删除的节点p为叶子节点时，不能简单的直接删除p，而要找到p的双亲节点，令双亲节点指向p的指针为NULL即可。

篇2：数据结构实习报告——国际象棋中马及遍历

数据结构实习报告——国际象棋中马及遍历 本文关键词：遍历，国际象棋，数据结构，实习报告

数据结构实习报告——国际象棋中马及遍历 本文简介：数据结构与VC编程实习实习报告学生姓名：学号：专业班级：指导教师：2012年7月14日实习题目在国际象棋棋盘上实现马的遍历一、任务描述及要求国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可

数据结构实习报告——国际象棋中马及遍历 本文内容：

数据结构与VC编程实习

实习报告

学生姓名：

学

号：

专业班级：

指导教师：

2012年7月14日

实习题目

在国际象棋棋盘上实现马的遍历

一、任务描述及要求

国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可以跳到（x±1，y±2）或（x±2，y±1）（所有的“±”之间没有相关性）。一般来说它下一步可以有八种跳法，但是它不能跳出这64个格子。

设计算法使它不管从哪出发都可以跳遍所有的格子（每个格子只能路过一次）最后回到起点。

1.基本要求：

合理设计界面，自行设计国际象棋棋盘，用鼠标选择马的起始位置，起始位置选定后，按“开始”按钮演示马的每一步行走路线。棋盘和马的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。

2.扩展要求：

对算法进行优化，根据j.c.Warnsdorff规则设计算法，该规则是在所有可跳的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数为最少；如果可跳的方格数相等,则从当前位置看,方格序号小的优先。

二、概要设计

1．抽象数据类型

本次实习中，我主要采用图的深度遍历知识和贪心算法来解决在国际象棋棋盘上实现马的遍历问题。棋盘上将64个格子视为64个点，将马从一个格子跳到另一个格子视为一条边，则共有168条边，那么可以将棋盘视为一个无向图，马在棋盘上按c.Warnsdorff规则跳动可视为图的深度遍历过程中的一步。

为了实现图的存储，需要建立顶点顺序表和邻接表，这个过程是在图的构造函数里实现的。图的操作主要包括：给出顶点vertex在表中的位置，给出顶点位置为

v

的第一个邻接顶点的位置，给出顶点v的邻接顶点w的下一个邻接顶点的位置，给出顶点位置为

v

的最优邻接顶点的位置。图的遍历算法是在视图类里面实现的。

图的抽象数据类型为：

ADT

Graph{

数据：顶点顺序表

关系:

邻接表表示了顶点之间的邻接关系

操作：①

给出顶点vertex在表中的位置

②

给出顶点位置为

v

的第一个邻接顶点的位置

③

给出顶点v的邻接顶点w的下一个邻接顶点的位置

④

给出顶点位置为

v

的最优邻接顶点的位置

}

由于贪心算法有时不能得到整体最优解，所以我设计了另一种遍历算法。由于要求遍历完所有点后要回到起点，则这是一条哈密顿回路，故可以事先找出这样的一种遍历序列并将其用点数组记录下来，以后在每次遍历时不论从哪个点出发都走这条路线，则一定能回到起点。此种遍历易于理解，下面不再详细介绍。

2．整个程序包含功能模块及模块间的调用关系

⑴

整个程序包含的主要功能模块：更换棋盘颜色，遍历起点的定位（鼠标定位、坐标定位和默认起点），在窗口的状态栏右边可以显示鼠标当前所处的坐标值以协助顶点的定位，棋盘上遍历过程的动态显示（图片（可更换）或路线），遍历顶点序列的打印，两种遍历方式（规则遍历（基于c.Warnsdorff规则的图的深度遍历）和固定遍历（按固定的路线遍历）），重新遍历。

⑵

模块间的调用关系：每次开始遍历之前可以更换棋盘的颜色、选择遍历过程的动态显示方式和遍历起点，然后选择规则遍历或固定遍历。开始遍历之后可以动态显示遍历过程，并打印遍历的顶点序列。在下一次遍历之前要选择重新遍历，并重新选择起点和遍历方式。实际上整个遍历是在开始动态显示遍历过程之前完成的，在遍历时将遍历序列用一维数组记录下来，遍历完之后利用此数组记录的序列来控制遍历过程的动态显示和遍历顶点序列的打印。

三、详细设计

1．虚拟实现（即数据结构的C++语言描述）

⑴

规则遍历中图的抽象数据类型的C++类定义为：

class

Edge

{

//边结点的定义

public:

int

dest;

//边的另一顶点位置，即下标

Edgelink;

//下一条边结点的指针

public:

Edge

(int

num=-1,Edgeptr=NULL):

dest

(num),link

(ptr)

{

}

//构造函数

};

struct

Vertex

{

//顶点的定义

E

data;

//顶点的名字

int

numEdge;

//此顶点当前关联的可走边数

bool

ver;

//标记此顶点是否被访问过

Edgeadj;

//边链表的头指针

};

class

Graph

{

//图的类定义

public:

VertexNodeTable;

//顶点顺序表

(各边链表的头结点)

int

numVertices;

//顶点个数

public:

Graph

();

//构造函数

~Graph();//析构函数

int

getVertexPos

(const

E

vertx);//给出顶点vertex在表中的位置

int

getFirstNeighbor

(int

v);

//给出顶点位置为

v

的第一个邻接顶点的位置

int

getNextNeighbor

(int

v,int

w);//给出顶点v的邻接顶点w的下一个邻接//顶点的位置

int

GetPriNeighbor(int

v);

//给出顶点位置为

v

的最优邻接顶点的位置

};

⑵

固定遍历中存储点的数组的定义：

CPoint

arr[64];

//存储马的固定行走回路路径，共64步

2．抽象数据类型中定义的操作算法实现（用伪代码描述）

此处只介绍求顶点位置为

v

的最优邻接顶点的位置的函数和图的深度遍历算法的伪代码：

⑴

int

GetPriNeighbor(int

v)的伪代码：

①若v存在则执行以下操作,否则返回-1；

②令min=9,w2=-1，w2记录最优邻接点；

③令w1为v的第一个邻接顶点的位置；

④当邻接顶点w1存在时执行以下操作:

⑤若

w1未被访问，则转到⑥，否则转到⑦；

⑥若min大于w1当前关联的可走边数numEdge则令min=

numEdge，令w2=w1；若min等于w1当前关联的可走边数numEdge，如果w2>w1则令w2=w1；

⑦令w1为v的邻接顶点w1的下一个邻接顶点的位置，转到④；

⑧

返回w2；

具体实现代码如下：

int

Graph::GetPriNeighbor(int

v)

{//给出顶点位置为

v

的最优邻接顶点的位置,如果找不到,则函数返回-1

if

(v

!=

-1)//顶点v存在

{

int

min=9,w2=-1;

//w2记录最优邻接点

int

w1

=

getFirstNeighbor

(v);

//获取第一个邻接顶点的位置

while

(w1

!=

-1)

//若邻接顶点w存在

{

if

(

!NodeTable[w1].ver

)

//w1未被访问

{

if(min>NodeTable[w1].numEdge)

{

min=NodeTable[w1].numEdge;//记录v的最优邻接顶点的当前关联的边数

w2=w1;

//从该方格出发,马能跳的方格数为最少

}

else

if(min==NodeTable[w1].numEdge)

{if(w2>w1)

w2=w1;

}

//如果可跳的方格数相等,则从当前位置看,方格序号小的优先

else

{}

}

w1

=

getNextNeighbor

(v,w1);

//获取下一个邻接顶点

}

return

w2;

}

return

-1;

}

⑵

void

DFS(Graph

//标记序号,存储下标

G.NodeTable[v].numEdge--;

//起始点被访问过则将其边数减1

if(k==64)

G.NodeTable[m].ver=false;

//k=64时将起始点标记为未被遍历,以便回到起始点

int

w

=

G.getFirstNeighbor

(v);

//获取第一个邻接顶点的位置

while

(w

!=

-1)

//若邻接顶点w存在

{

//if

(

!G.NodeTable[w].ver

)

//w未被访问

G.NodeTable[w].numEdge--;

//顶点各邻接点的边数都应减1

w

=

G.getNextNeighbor

(v,w);

//获取下一个邻接顶点

}

int

pw=G.GetPriNeighbor(v);

//给出顶点位置为

v

的最优邻接顶点的位置,如果找不到,则函数返回-1

if(pw!=-1)

dfs(G,pw,m);

//若最优邻接顶点存在,递归访问顶点pw

}

}

3．函数之间的调用关系

⑴

运行程序后调用视图类的OnDraw()函数在窗口中绘制棋盘。

⑵

在菜单栏的“操作”中点击“黄绿相间”

、“黑白相间”

、“恢复默认”菜单后分别调用视图类的OnMenuitemby()、OnMenuitembw()、OnSyschMenuitem()函数，在此函数中调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。

⑶

点击“图片”

、“路线”菜单后分别调用视图类的OnMaMenuitem()、OnRouteMenuitem()函数。

⑷

点击“更换图片”菜单调用视图类的OnDialog3()函数以弹出对话框，在对话框上点击单选按钮选择图片后，若点击“确定”按钮调用Dialog3类的OnOk3Button()函数，若点击“缺省设置”按钮则调用Dialog3类的OnPicsysButton()函数。

⑸

点击“鼠标定位”、“坐标定位”菜单后分别调用视图类的OnMouselocation()、OnMenuitemsys()函数，点击“坐标定位”

后弹出OnDialog2()对话框，设置起点后，若点击对话框上的“确定”“按钮后调用OnDialog2()类的OnOk2Button()

函数，在此函数中调用了UpdateData(TRUE)函数以刷新控件的值到对应的变量，若点击“缺省值”按钮则调用OnDialog2()类的OnSysButton()函数

关闭对话框后调用视图类的OnDialog2()函数。

⑹

点击“规则遍历”菜单或工具栏中的“J”图标后调用视图类的OnMenuitemstart()函数，此函数中调用了Graph类的构造函数Graph

()来建立图，也调用了视图类的图的深度遍历函数DFS()和显示图片或路线和遍历序列listnumber()函数。在DFS()中调用了Graph类的getVertexPos()和视图类的dfs

()函数，在dfs

()中又调用了Graph类的getFirstNeighbor()、getNextNeighbor

()、GetPriNeighbor()函数，也调用了它本身来形成深度遍历，也用到了遍历序列存储数组h[65]。在listnumber()中调用了视图类的picture()和route()函数和延时函数Sleep()，用以动态显示遍历过程，之后打印顶点的遍历序列并提示遍历成功与否。

⑺

点击“固定遍历”菜单或工具栏中的“S”图标后调用视图类的OnSolidMenuitem()和listnumber()函数,也用到了存储固定路径的点数组arr[64]和遍历序列存储数组h[65]。

⑻

点击“重新遍历”菜单或工具栏中的“T”图标后视图类的OnStopMenuitem()函数，在此函数中对遍历序列存储数组h[65]和全局变量进行了初始化，也调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。

四、调试分析

1．程序在调试过程中出现的问题及解决方法

我个人认为我在写程序之前时考虑得比较仔细，所以需要调试的地方比较少。以下是我在调试过程中出现的问题及解决方法：

⑴

实习期间的前几天我一直认为利用c.Warnsdorff规则设计出的图的深度遍历算法自己设计出算法后，通过窗口右侧显示的遍历序列发现算法不正确。为了解决这个问题，我先仔细得把程序读了几遍，觉得算法设计得不缜密，尤其是对当前遍历点和其邻接点的边数减少问题的考虑和对获取最优邻接点的函数的设计。经过改进后，还是不能得到理想的结果。于是我认为还是算法设计得有问题，所以我对程序进行了调试。经过反复地调试和改进，我觉得算法没有问题了，可是对于某些起始点遍历结果还是不正确。于是我开始怀疑利用c.Warnsdorff规则设计出的算法是不是一定能遍历到所有点并回到起点。在网上查询资料并与老师交流后发现自己前期的想法是错误的，实际上利用c.Warnsdorff规则在大多数情况下能够实现遍历，但并不能确保成功。经过再次深究自己设计的算法，我认为算法是正确的。

⑵

与老师探讨自己设计的算法后，老师要求我重新设计一种算法使得从任何一个点出发都可以遍历到所有点并回到起点，即利用事先已知的固定路线来遍历。在这个算法的设计过程中，也出现了遍历序列不正确的问题，序列的前一部分正确，后一部分错误。经过调试，发现在存储遍历序列的过程中用来控制点数组元素从arr[63]转到arr[0]的变量出了问题，修改之后，问题顺利解决。

2．算法的时间复杂度分析

⑴

图的深度遍历算法的时间复杂度分析：

设第i（1<=i<=64）个点的邻接点个数为Di,图的边数为e。则遍历算法第i个点的各邻接点的边数都减1的循环的时间代价是Di，获取最优邻接顶点的函数的时间代价也是Di，故深度遍历算法的总时间代价为2(D1+D2+…+D63+D64+Dj)=2

O(e)+2Dj，其中Dj是起点的邻接点个数。

⑵

固定路线遍历算法的时间复杂度分析：

设数组元素个数为n,则遍历算法中for循环、while循环和listnumber()函数的时间复杂度都为O(n),故固定路线遍历算法的时间复杂度为O(n)。

五、测试结果

根据一组提供的测试数据得到什么样的结果？

⑴

图的深度遍历算法的测试数据为：坐标值（7，8）

遍历序列：63，48，31，16，6，12，2，17，11，1，18，3，9，26，41，58，52，62，56，46，40，55，61，51，57，42，25，10，4，14，8，23，13，7，24，39，29，19，34，49，59，44，27，33，50，35，20，5，15，21，36，30，45，60，54，64，47，32，22，37，43，28，38，53，63

遍历结果正确！

⑵

固定路线遍历算法的测试数据为：坐标值（1，4）

遍历序列：25，10，4，14，8，23，6，16，31，48，63，53，59，49，34，17，2，12，29，19，9，3，13，7，24，39，56，62，47，64，54，60，50，33，18，1，11，5，15，32，22，28，38，21，27，44，61，55，40，46，52，37，43，58，41，26，20，35，45，30，36，51，57，42，25

遍历结果正确！

六、心得体会

为期九天的数据结构实习，感觉比平常的一个月都要漫长。这不仅仅是因为在考完试后的这九天中我依然早起晚睡，每天的工作量不亚于考前复习每天的工作量，每天对着电脑思考一些复杂的问题，更重要的是因为这九天我坚持下来了，学到了很多知识，锤炼了自己多方面的能力，增强了自己的毅力和信心，为以后的学习和工作奠定了很好的基础。

实习前我并没有做充分的准备，实习开始时老师只说了相关事项，并没有说怎么去做。所以，一切工作都得靠自己，自己利用网络和书籍去解决编程中遇到的问题，请教老师和同学也是很好的一种解决问题的方式，此时我才体会到了“书到用时方恨少”的含义。实习前期主要是对题目加以分析，设计实习作品的预期效果，查找资料并学习相关知识。由于缺乏独立解决问题的经验，以前接触的很少，所以这个阶段感觉比较费力。由于时间有限，所以实习中期知识基本上都是现学现用，而且还得自己设计算法解决相关问题。然而自己设计的算法并不一定正确，需要反复改进并反复测试，经过多次修改后结果还不正确时，自己会感到很失望，并且会动摇自己的信心，甚至想放弃。更令人头疼的是编程过程中会遇到很多错误，有时需要查阅相关资料，有时需要调试程序，所以这个阶段感觉相当费力，当然这个阶段多与老师和同学沟通是非常有必要的，在沟通中常常会有意想不到的收获。但当每一个问题得到解决时，都会令自己信心大增，都会展现出最灿烂的笑容，吃饭都觉得胃口好，睡觉也睡得安稳，于是更加坚定地接着做下去。实习后期主要是对程序进行优化，添加一些功能，验收程序并撰写实习报告。

实习期间一次次的失望对自己是一个很大的考验，但一次次的看到希望对自己则是莫大的肯定。当自己独立完成整个作品时，再回首整个实习期间遇到的问题和经受的苦难，感觉那也不算什么，并且觉得自己的付出是非常值得的，因为这是大学期间乃至整个人生中的一笔宝贵的财富。

指导教师评语及成绩

姓名

学号

评价项目

评

价

内

容

得

分

（百分制）

平时表现

(30%)

学习、工作态度(30%)

纪律性(30%)

综合运用知识能力(40%)

实习成果

(70%)

开题报告书写水平(15%)

实习总结报告书写水平(15%)

成果(70%)

总分

评语：

指导教师（签名）：*年*月*日

篇3：数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序

数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文关键词：数据结构，算数，表达式，运算，演示

数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文简介：实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）

数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序 本文内容：

实习报告

题目：设计一个演示用运算优先法对算数表达式求值过程的程序。

班级：

姓名：

学号：

完成日期：

一、

需求分析

1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.

2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。

3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。

4测试数据见原题。

5程序执行的命令包括：

（1）

建立算数表达式；

（2）

得到运算表达式的值；

（3）

演示运算过程。

二、

概要设计

1.

设定栈的抽象数据类型定义：

ADT

Stack{

数据对象

D＝{

ai

|

ai

∈charSet,i=1,2,.,n,n≥0

}

数据关系：

R1＝{

|

ai-1,ai∈D,i=2,.,n

}

（约定an

端为栈顶，a1

端为栈底）

基本操作：

InitStack（

inttop;

int

stacksize;

}SqStack1;//操作数栈

typedef

struct{

charbase;

chartop;

int

stacksize;

}SqStack2;//操作符栈

2、

栈类型

typedef

struct{

charbase;

chartop;

int

stacksize;

}Stack;

//栈类型

栈的基本操作设置如下：

void

InitStack(Stack

S.top=p;

S.size++;

Return

TRUE;

}

else

return

FALSE;

}

Status

Pop(Stack

else{

p=S.top;S.top=S.top->next;

e=p->:data;S.size--;

return

TRUE;

}

}

3、运算代码

int

Operate(int

a,char

theta,int

b)

//计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值

{

int

c;

if(theta==

+

)

c=a+b;

else

if(theta==

-

)

c=a-b;

else

if(theta==

)

c=a*b;

else

c=a/b;

return

c;

}//Operate

int

result(SqStack1OPND,SqStack2OPTR)

//求值

{

char

a=0;

char

theta;

int

b,c,number=0;

IntInitStack(OPND);

CharInitStack(OPTR);

CharPush(OPTR,#

);

a=getchar();

while(a!=

#

||

CharGetTop(OPTR)!=

#

)

{

printf(“输入字符：%c

“,a);

if(!In(a))//不是运算符则进栈

{

number=0;

while(!In(a))

{

number

=

number*10

+(a-48);//处理多位整数z=10*x+y

a

=

getchar();

}

IntPush(OPND,number);

printf(“主要操作：Push(OPND,%d)

“,number);

}

else

switch(Precede(a,CharGetTop(OPTR)))

{

case

:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作：Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈：%d

OPTR栈：%c/n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“The

result

is

%d./n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

4.主函数和其他函数的代码

void

main()

//主函数，使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“Please

enter

an

expression

with

a

end

of

#

./n“);

printf(“The

Expression:“);

result(OPND,OPTR);

}

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,#include

#include

#include

#define

STACK_INIT_SIZE

100

#define

STACKINCREMENT

10

#define

ERROR

0

#define

OK

1

//********************************************栈模块

typedef

struct

SqStack1//运算数栈

{

intbase;

inttop;

int

stacksize;

}SqStack1;

typedef

struct

SqStack2//运算符栈

{

charbase;

chartop;

int

stacksize;

}SqStack2;

void

IntInitStack(SqStack1S)

{

S->base=(int)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

void

CharInitStack(SqStack2S)

{

S->base=(char)malloc(STACK_INIT_SIZE*sizeof(char));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

int

IntGetTop(SqStack1S)

//取栈顶元素

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

char

CharGetTop(SqStack2S)

//取栈顶元素

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

int

IntPush(SqStack1S,int

e)

{(*S).top++=e;

return

OK;

}

int

CharPush(SqStack2S,char

e)

{(*S).top++=e;

return

OK;

}

int

IntPop(SqStack1S)

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

int

CharPop(SqStack2S)

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

//——————————————————*******************运算模块

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作：Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈：%d

OPTR栈：%c/n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“/n结果:%d./n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

//————————————————————————主程序模块

void

main()

//主函数，使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“请输入算数表达式并以

#

结尾./n“);

printf(“算数表达式:“);

result(OPND,OPTR);

}