李凤荣 刘嘉洋

摘 要 数据结构是研究计算机科学和工程的基础，数据结构课程是计算机科学与专业技术专业及相关专业的核心课程之一，学好该课程不仅对后续课程的学习有很大帮助，而且对开发有效利用计算机资源的程序极为有益。

关键词 数据结构 二叉树 算法

中图分类号：G424文献标识码：A

计算机是进行数据处理的工具，数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算算法的实现，它不仅为用计算机语言进行程序设计提供了方法性的理论指导，还在更高的层次上总结了程序设计的常用方法和常用技巧。

1教学目标剖析

1.1课程性质

数据结构是一门承上启下的课程，前期课程：计算机基础，C语言，后期课程：算法设计与分析、操作系统、编译原理、数据库原理、软件工程……。

1.2教学目标剖析

数据结构课程是研究各种数据模型在内存中的存储方法及实现方法，只要是程序，无不是以数据结构为基础。通过学习数据结构课程获得经典数据结构和经典算法的思想、方法、技术。学习过程就像思维体操，潜移默化中提高程序设计和计算思维能力。所以，理解并掌握基本的数据结构和经典的算法，培养算法设计和分析能力，培养计算思维能力，培养数据结构和算法的运用能力是这门课的教学目标。

1.3教学内容设计

在教学设计上紧扣大纲，涵盖全部知识点（考研、面试）;强调基础提炼基础性内容，让学生在这门课程涉及的相关领域内，打下终身学习的知识基础、技术基础和思维基礎;因材施教对人的公平以及对人才的公平，对某些知识点进行适当的扩充和提高，可用于选讲，可用于部分同学的讲授，也可用于学生自学或课外阅读;抽象分层兼顾概念层和实现层，既强调数据结构的基本概念和原理方法，又注重数据结构的程序实现和实际运用;呈上启下抓住关键点。

1.4课程结构设计

我们将课程分成两条线让学生更好的理解：第一条线从线性表→栈→队列→串→数组→树→二叉树→图;第二条线从逻辑结构→映射计算机中的表示→存储结构→运算实现→算法设计。只有掌握了数据的存储结构表示方法，才能在此之上设计更有效的算法。

2数据表示的重要性及讲授方法

数据结构 + 算法 = 程序，程序设计的关键是数据表示和数据处理。将现实世界的问题进行抽象变成模型化数据模型，表示高级语言层（常量变量、数据类型）进行翻译到机器层（内存0、1编码）。将问题（抽象模型+基本思路）的想法（数据表示+数据处理）编程算法（程序语言+编程环境）用程序实现。

数据表示的重要性及讲授方法，没有数据表示，数据处理是空中楼阁（顶层算法）。存储（映像）到内存中，由机外表示转换为机内表示。

2.1变量表示数据的理解

通过顺序表的插入实现体会数据表示的含义，计算的本质就是符号变换，形式化的计算机仅有语法，没有语义，如数据的插入程序

for （int j = L->length-1; j > i; j--）

L->data[j+1] = L->data[j];

2.2从实际问题抽象的数据模型

例如求解两个动物之间通信的最少翻译问题，来掌握广度优先遍历在求解实际问题中的应用。假设动物A可以与动物B进行通信（通信是双向的），但它不能与动物C通信，动物C只能与动物B通信，所以动物A、C之间通信需要动物B来当翻译。则两个动物之间相互通信最少需要多少翻译。通过输入样本得出输出结果。

2.3算法的执行结果

哈夫曼树具体的构造方法，如何实现使用频率越高的字符采用越短的编码。理解在数据通信中文字怎样转换成二进制字符0和1的。

3运行实例方法在教学中的运用

3.1运行实例，理解基本思想

二叉树的顺序存储结构就是用一组地址连续的存储单元来存放二叉树的数据元素，因此必须确定好树中各元素的存放次序，使得各数据元素在这个存放次序中的相互位置能反映出数据元素之间的逻辑关系。

3.2运行实例，设计存储结构

3.2.1二叉树顺序存储结构（不用下标为0的元素）

typedef  ElemType  SqBTree[MaxSize];

SqBTree bt="#ABD#C#E######F";

其特点：对于完全二叉树来说，其顺序存储是十分合适的;对于一般的二叉树，特别是对于那些单分支结点较多的二叉树来说是很不合适的，因为可能只有少数存储单元被利用，特别是对退化的二叉树（即每个分支结点都是单分支的），空间浪费更是惊人。在顺序存储结构中，找一个结点的双亲和孩子都很容易。

3.2.2二叉树的链式存储结构：

二叉树的链式存储结构，每个结点用链表中的结点来存储。

typedef struct node

{   ElemType data;

struct node *lchild， *rchild;

} BTNode;

其特点：除了指针外，二叉链比较节省存储空间。占用的存储空间与树形没有关系，只与树中结点个数有关;在二叉链中，找一个结点的孩子很容易，但找其双亲不方便。

3.3运行实例，解决算法的关键问题

二叉树的基本运算包括创建二叉树、查找结点、求高度、输出等。

void CreateBTNode（BTNode * &b，char *str）

{      //由str 二叉链b

BTNode *St[MaxSize]， *p;

int top=-1，  k ， j=0;

char ch;

b=NULL;//建立的二叉链初始时为空

ch=str[j];

while （ch！='＼0'）  //str未扫描完时循环

{     switch（ch）

{

case '（'： top++; St[top]=p; k=1; break;//可能有左孩子结点，进栈

case '）'： top--;  break;

case '，'： k=2;  break; //后面为右孩子结点

……

4数据结构中的计算思维

任何一种思维的形成，都肯定有一定的模式（套路），都需要大量的练习， 在潜移默化中逐渐形成。思维培养是一个综合性的系统工程，把计算思维的培养构建一个教学体系，需要思考计算思维的特征和表现是什么？计算思维有哪些组成？各组成部分在哪些课程中讲授？如何将其贯彻到具体课程的知识单元中？程序设计的过程训练就像一种思维体操，能够使思维得到锻炼，引导思维过程，在潜移默化中使思维变得更清晰、更有逻辑，程序设计关注的是从实际问题到抽象出解决问题的算法，直至编写程序解决问题的整个思维过程，这个过程正是计算思维的运用过程。使学生对数据结构理解得到升华。

5结语

数据结构是一门应用实践性非常强的课程，学生在掌握各种数据结构（特别是存储结构）的基础上一定要尽可能地多上机实习，通过较多的实验把难以理解的抽象概念转化为实实在在的能够在计算机上执行的程序，这样才能将所学知识和实际应用结合起来，吸取算法的设计思想和精髓，提高运用这些知识解决实际问题的能力。