数据结构课程设计

课程设计任务书。

目录。1 需求分析1

2 概要设计。

2.1 设计思想1

2.2 设计说明2

2.3 算法流程图2

3 详细设计。

3.1源**4

3.2实验结果7

4 调试分析9

5 课设总结9

6 参考文献10

1.需求分析。

1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树t的链式存储结构，即建立二叉链表。可采用先序序列递归建立二叉树，建立如下图所示的二叉树。

应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值：”之后，采用以下字符序列：abc@@de@g@@f@@@以@替代空格）作为建立二叉树t的输入字符序列并回车，窗口出现：

二叉树的链式存储结构建立完成！

2、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“2” 并回车，在程序运行窗口中提示信息“输入要求路径的结点值：”输入“g” 并回车，会得到结果为：

→a→b→d→e→g如果输入“i” 并回车，会得到结果为：没有要求的结点！

2 .概要设计。

2.1 设计思想。

在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树t，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。

2.2设计说明。

为实现上述的设计思想，首先要定义二叉树的链式存储结构，采用二叉链表的方式，相应的类型说明为：

typedef char datatype;

typedef struct node

return ok;

void nodepath(bintree bt,bintnode *ch)

//求二叉树根结点到给定结点*p的路径。

typedef enum boolean;

bintnode *stack[num]; 定义栈。

int tag[num];

int i,top;

boolean find;

bintnode *s;

find=false;

top=0;

s=bt;do

if(top>0)

while(!find &&top!=0);

void findbt(bintree bt,datatype x)

if((bt!=null) &found)else

bintnode *findx(bintree bt,datatype x)

//按给定值查找结点。

int found=0; /用found来作为是否查找到的标志。

bintree p=null; /置空指针。

findbt(bt,x);

return(p);

void main()

bintree bt;

char ch1;

int xz=1;

while(xz)

printf("建立二叉树并求指定结点路径");

printf(" 欢迎光临");

printfn");

printf("1.建立二叉树的存储结构 ");

printf("");

printf("2.求二叉树指定结点的路径 ");

printf("");

printf("0. 退出系统 ");

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了