浅谈数据结构中的线性表

浅谈数据结构中的线性表

0内容结构的特性数据结构是计算机专业课程体系中的一门重要的综合专业课程。其后续课程有操作系统、编译原理、数据库原理、软件工程等。因此,学好这门课程,对计算机专业学生极为重要。但是,数据结构是一门十分难学的课程。该课程内容多,逻辑性强,而且许多内容较抽象。学生普遍认为这门课程理论性太强、太枯燥、不好学。其中,C++语言掌握不够扎实,是学生学习数据结构的主要障碍之一。线性表是数据结构的最基本结构。一方面,在线性表的实现及应用实例中,几乎涉及到了所有C++语言语法知识,这些内容足够支持数据结构课程的学习。详细的讲解线性表无疑是对C++语言的最好复习,也是C++语言知识的一个综合应用。另外一方面,内存中的数据结构不外乎就是顺序结构和链式结构。线性表的彻底掌握,在数据结构中栈、队列、图和算法等后续内容的学习中,无疑将是事半功倍。该文以链表为侧重点,探讨了线性表的教学方式。包括了链表概念的引入,链表代码的实现,链表的实例应用等环节。1运用数字水明的运用,有助于激发学生兴趣,加深认链表虽然是数据结构中最基本的结构,但对于C++语言的初学者来说,学习掌握仍然较为困难。所以采用生活中有趣生动的例子,有助于提高学生的兴趣和加深印象。如:一个链表,可以比喻成一列“数据火车”,火车上装载的是各种类型的数据而非货物。如图1所示。通过“数据火车”中车厢的增加和卸载,来理解链表结点的插入和删除。同时也可以启发性的提问学生,“车厢之间的挂钩用C++的什么去实现?”大部分同学都能想到可以用指针来模拟车厢间的挂钩,实现结点的连接。2知其然,知其所以然共实现了6个主要的链表版本,每一个新的版本都是上一个版本的演变,同时将新的C++语法知识点引进,让学生既掌握语法知识点本身,也能理解新的语法知识点的引进使得原有版本代码得到了哪些改善。知其然,而知其所以然。增强了学习效果。限于篇幅,以下代码中只包含类型定义及函数原型,没有实现部分。另外为了讲解一些语法知识点,在6个主要版本之间,还可以一些更小的版本。2.1体、针、动态内存分配的定义在这个版本中,可以复习巩固C语言的基础知识,及结构体、指针、动态内存分配、typedef类型定义等内容。其结构体类型定义及函数原型如下:以上的实现中,将指针类型类型,改成相应的应用类型,可是的代码更简洁些。2.2生成网络地理函数将版本1改写成版本2,用类来表示链表。可以体会到类和封装,构造函数,析构函数,常函数等带给程序设计的好处。如构造函数可以自动调用,避免了程序员定义对象时,忘记初始化的错误;析构函数可以自动调用,以避免资源的不合理占用;函数的原型,命名也更简单。类类型定义如下所示:2.3学生运算符存出合理的表达在链表结点负载的数据是用户自定义类型时,如Student类。此时可以实现流插入运算符和赋值运算符的重载。同时可以让学生体会到运算符重载带来的好处。如在链表插入操作中,可以对链表负载的数据直接进行赋值。在链表输出函数中,可以用形如out<<data的来输出链表每个结点的信息。这样的形式既适用于基本类型,也适用于用户定义类型,增强了函数的通用性。在链表类中,也可以使用运算符重载,输出整个链表。Student类型定义如下:2.4学生模板版本链表本身是一个与数据类型无关的数据结构,很自然的就可以使用上模板。此版本可以让学生体会到模板带来的泛型设计的好处。泛型的链表类定义如下:2.5异常的附设应用在链表的插入操作insert(intI,Tdata)中可以增加异常的处理。当参数i位置不合法时,抛出异常。在此场景下,可以让学生学习try,catch,throw,异常抛出列表等异常的基本知识,体会到异常带给程序设计的好处,如:正常处理代码和错误处理代码的分离;异常的传递等;2.6c++语法特征的链表版本由于顺序表SeqenceList和链表LinkList都是线性表的实现,尽管实现完全不一样,但它们具有共同的操作接口,宜抽象出一个共同的抽象父类List,规范两者的操作。这样,有利于客户代码方便的在顺序表和链表之间选择替换。其关系如图2所示。在这个版本中,学习可以学习继承,多态等面向对象的特征,虚函数的使用。体会这些语法特征带给程序设计的好处。在以上链表的各个版本的设计实现过程中,采用课堂演示的教学方式。由教师和学生共同探讨和设计,在VC6.0环境下逐步的写出完整的代码。过程中,可以提出很多问题,来启发学生思考,进行互动。这样的方式不仅使学生知其然,而且知其所以然。因为,C++面向对象的语法特征,的的确确给写程序带来了好处。顺序表的讲解可以参考链表的过程,补充了链表中没有涉及到的数组,动态数组等方面的语言知识。3顺序表和链表之间的组合为了加强学生的实践应用能力,链表的应用举例是整个环节中必不可少的部分。线性表应用的例子有用集合的运算、一元多项式运算、简单学生信息关系系统等。以上的应用中,既可以使用顺序表,也可以使用链表。精讲其中一个例子能够很好的巩固线性表的知识。如:在简单学生信息管理系统中,用链表完成程序的实现后。要改成顺序表实现。只需要将ListstuList=newLinkList()改成ListstuList=newSeqenceList()即可。因为,两者均按照同一接口实现,顺序表和链表之间可以方便的替换,而不需要修改其它代码。加深了学生对面向对象特型在软件复用方面的支持的理解。4注重线性表的应用,提高了学生学习的积极性该文从链表概念的引入,链表的各个版本的演进式实现,及链表的应用举例。介绍了笔者在独立学院数据结构中线性表的教学方式。该方式的采用,较传统的教学方式多使用2-4学时,但这个时间是值得的。通过精讲线性表,渐进式的C++知识的展开,循序渐进,综合应用了C++语言的知识,学生对C++语言有了一个