线性表详细教案

教案

学科名称：计算机导论 课题：数据结构基础（新课）

教学目标：让学生了解数据结构在信息技术中的重要性，为让学生通

过学习数据结构基础，能过更好的学习算法和程序设计。

教学内容：向学生阐述数据结构的运用和几种典型的数据结构（线性

表、堆栈、队列）及其定义和特征。

教学重点：了解什么是数据结构，数据结构的类型的表现和实现。 教学难点：熟悉几种典型数据结构（线性表、堆栈、队列）的运算及

其存储方式。

教学策略：讲授法，演示法，和操练法。举一些典型的例子，演示数

据结构的存储和区别，主要以幻灯片的方式来演示。

教学过程：

一数据结构含义

(提问：什么是数据结构？)

所谓数据结构是带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系。（这里所说的“数据”，是指描述客观事物的数、字符以及所有能输入到计算机并且被计算机处理的符号的集合。因此，在计算机科学技术中，“数据”的含义是十分广泛的，它不仅可以是数值，其他如字符、图形、图像、乃至声音等信息都可以视为数据。数据集合中每一个个体称为数据元素，它是数据的基本单位。）

（1） 不同角度看数据结构

学科角度：数据结构是计算机科学技术的一个分支，它主要研究数据的逻辑结构（即数据元素之间的逻辑关系）和物理结构（即数据在计算机中是如何表示的）以及它们之间的关系。

课程角度：数据结构是计算机科学技术的一门重要的专业基础课，其中系统介绍线性表、堆栈、队列、串、数组和广义表、树、图等基本类型的数据结构及其相应的运算的实现算法。

二、几种典型的数据结构 1、线性表

（1）线性表的定义（提问：看到线性表会联想到什么？｛数轴｝、坐标）

线性表是一种简单且最常用的数据结构。一个线性表是n个数据元素的有序列，每一个数据元素根据不同的情况可以是一个数、一个符号或者一个记录等信息。例如：英文字母表（A,B,C,D,E,„，Z）就是一个线性表，其中的数据元素就是单个的字母。

数据元素、数据项

数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：

（课堂解释：其中，数据元素是由每一个学生部分课程成绩组成的记录，记录由学号、姓名以及各门课程名等数据项组成，这些数据项称为字段）

不同的线性表中的数据元素可以是各种各样的，但是同一个线性表中的数据元素必须具有相同的特性。 （2）、线性表的运算

设L为一个线性表，则对L可以进行以下一些基本运算。 ① 置空表SETNULL(L)。该运算用来线性表L置为空表。 ② 求线性表长度LENGTH(L)。该运算用来求线性表L的长度（即L中数据元素的个数）作为其函数值。

③ 取表元素GET(L,i)。该运算取得线性表L的第i个数据元素（或第i个数据元素的地址）作为其函数值。

④ 在表中定位查找元素Locate (L,e):该运算用来在线性表L中查找指定的数据元素e。如果线性表L存在值为e的数据元素，则执返回该数据元素的位置i作为其函数值；若这样的元素不存在,则返回值为0

⑤ 插入数据元素Insert(L,i,e)。该运算的功能是将指定的数据元素e，

插入到线性表L的第i个元素的前面。如果线性表L原来有n个数据元素，则执行该运算后其数据元素个数：n+1.

⑥ 删除数据元素Delete(L,i):该运算的功能是将线性表L的第i个数据元素删除。如果线性表L原来有n个数据元素，则执行该运算 后其数据元素个数为n-1。 （3）、线性表的存储结构

在计算机中线性表通常可以采用顺序存储和链式存储两种结构。 （给学生分析：顺序和链式存储结构是难点，应详细讲清楚，画图事例）

① 顺序存储结构

顺序存储结构是使用一批地址连续的存储单元来依次存放线性表的数据元素。如果线性表共有n个数据元素，每一个数据元素占用m个存储单元，则存储该线性表共计需要m*n个存储单元。采用这种存储结构实现对线性表的某些运算比较简单，例如计算机线性表的长度。但是实现插入或删除表元素运算，则因为需要移动大量相关的运算而花费较多时间。

下标位置

线性表存储空间

LOC(A)+(MaxSize-1)*sizeof(ElemType) LOC(A)+(n-1)*sizeof(ElemType) LOC(A)+(i-1)*sizeof(ElemType) 存储地址 LOC(A)

LOC(A)+sizeof(ElemType)

② 链式存储结构

链式存储结构的特点是使用不一定连续的存储单元来存放线性表。为了表示某一元素与其后继元素的位置关系，除了存放数据元素本身之外，还需要存储一个指示其直接后继元素的指针。这样线性表每一个元素的存储空间包括两部分：数据域和指针域。整个线性表的各个数据元素的存储区域之间通过指针连接成为一个链式的结构，因此称为链表。采用链式存储结构可以充分利用零星的存储单元来存放元素，可以高效地实现插入、删除等运算。但是，由于对于每一个数据元素都需要额外增加一个指针域，这会增加存储空间。

（应讲清楚顺序和链表的区别，并提问：顺序和链式存储的区别及其好处） 2堆栈 (1) 堆栈的定义

堆栈（stack）简称为栈。它是一种受限的线性表，即在堆栈中规定只能够在表的一端（表尾）进行插入和删除操作，该表尾称为栈顶（TOP）。设栈S=（a1,a2, „,an），a1是最先进栈的元素，an是最后进栈的元素，则称a1是栈底元素，an是栈顶元素。进栈和

退栈是按照“后进先出”的原则进行的。 进栈和退栈操作：如图：

进栈 出栈

栈顶

栈底

栈示意图

（2） 堆栈的运算

设S为一个堆栈，则对S可以进行以下一些基本运算。 ① 置空栈SETNULL(S)。该运算是把堆栈置为空栈。

② 进栈PUSH(S,x)。该运算是在堆栈S的栈顶压入一个新的元素x。 ③ 退栈POP(S).该运算是删除堆栈S的栈顶元素。

④ 取栈顶元素TOP(S)。该运算取得堆栈S的栈顶元素作为其函数值。

⑤ 判断堆栈是否为空EMPTY(S)。该运算用来判断堆栈S

是否为

空。它是一个布尔函数。如果S为空栈，则返回真；否则，返回假。

（3） 堆栈的存储结构

对于堆栈一般采用顺序存储结构，即使用一个连续的存储区域来存放栈元素，并设置一个top指针，用来指向栈顶的位置。

4 3 2 1 0

MaxSize=5

4 3 2 1 0

4 3 2 1 0

4 3 2 1 0

(a)空栈 (b)元素a入栈 (c)元素b、c、d入栈 (d)元素d出栈

top=-1 top=0 top=3

top=2

（注意：空栈时，top为-1，top是指向栈顶的位置，不是元素个数） 3、队列

（1）队列的定义

队列也是一种受限的线性表。与堆栈不同的是，在队列中规定只能够在表的一端插入，在表的另一端进行删除操作。允许插入的元素的一端为

队尾 (rear).允许删除的一端称为对首(front).设队列Q=（a1,a2, „,an），其中,a2, „,a

n顺序进入，而退出对列的第一个元素是对首元素a1。即进入队列和退出队列操作是按照“先进先出”的原则进行的。

4 3 2 1 0

(a)空队

4 3 2 1 0

4 3 2 1 0

4 3 2 1 0

(b)a,b,c,d,e入队

(c)出队一次 (d)出队4次

（2） 队列的运算

队列的运算与堆栈的运算类似，所不同的是队列中删除运算在队首进行，插入运算在队尾进行。队列的基本运算：

① 置空队列SETNULL(Q).该运算把队列置为空队列。 ② 进入队列

ADDQUEUE(Q,x)。该运算在队列Q中的尾插入一个新元素x。

③ 退出队列DELQUEUE(Q)。该运算是删除队列Q的队首元素。 ④ 取队首元素

FRONTQUE（Q）。该运算取得队列Q的队首元素作为其函数值。

⑤ 判断队列是否为空EMPTY(Q)。该运算用来判断队列Q是否为空。它是一个布尔函数。如果Q为空队列，则返回真值；否则，返回假。 （

3）、队列的存储结构

由于队列中的数据元素变动较大，如果使用顺序存储结构其中的

数据要频繁地进行移动。因此，队列同采用链式存储结构。用链表表示的队列为链队列。一个链队列需要设置两个指针，一个为队首指针，另一个为队尾指针，分别指向队列的头于尾。 如下图：

q

q (b)入队3个元素 (a)链队初态

q (c)出队1个元素

三、给学生思考(也是作业和下节课要简单复述的内容) 1、什么是数据结构？

2、什么是线性表？线性表有哪些运算？线性表怎样存储？ 3、什么是堆栈？堆栈有哪些运算？堆栈怎样存储？ 4、什么是队列？队列哟扑哪些运算？队列怎样存储？ 5、要区分好堆栈和队列的进退的原则。 四、总结：

这节知识要点比较多，学生容易混淆堆栈和队列的存储方式。对线性的两种存储结构不容易理解，在以后讲课中要经常复述来巩固这些知

识点。