数据结构教案C语言.docx

《数据结构教案C语言.docx》由会员分享，可在线阅读，更多相关《数据结构教案C语言.docx（33页珍藏版）》请在三一办公上搜索。

1、数据结构教案C语言 课程教案 课程名称： 数据结构 授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 数据结构是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、

2、课程教学内容 第一章 绪论 教学内容： 1） 什么是数据结构 2） 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3） 数据结构的抽象层次 4） 算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章 线性表 教学内容： 1） 线性表的定义和特点 2） 线性表的顺序存储及查找、插入和删除操作 3） 线性表的链式存储及查找、插入和删除操作 4

3、） 使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 第三章 栈和队列 教学内容： 1） 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示 2） 队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 3） 队列的应用举例 教学要求： 熟练掌握：栈的定义及实现 熟练掌握：队列的定义及实现 掌握：能运用栈和队列解决简单实际问题 第四章 串 教学:内容： 1) 字符串的抽象数据类型 2) 字符串操作的实现 3) 字符串的模式匹配 教学

4、要求： 熟练掌握：字符串的定义方式 熟练掌握：字符串的各种操作的实现 了解：字符串的模式匹配算法 第五章 数组和广义表 教学:内容： 1) 数组的定义和初始化 2) 作为抽象数据类型的数组的顺序存储方式 教学要求： 了解：作为抽象数据类型的数组的定义 熟练掌握：顺序表的数组定义方式及实现 第六章 树和二叉树 教学内容： 1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念 2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 3) 二叉树的表示：数组表示；链表存储表示 4) 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法 5

5、) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化 6) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历 7) 二叉树的计数 8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码 教学要求： 了解：树和森林的概念 掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法 掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握：树和森林的实现及遍历方法 掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握：霍夫曼树的实现方法及霍夫曼编码的概念 第七章 图 教学内容： 1）图的基本概念：图的基本概念；图的抽象数据类型 2）图的存储表示：邻接矩阵；邻

6、接表；邻接多重表 3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量 4）最小生成树：克鲁斯卡尔算法；普里姆算法 教学要求： 掌握：图的基本概念和图的存储表示 熟练掌握：图的两种遍历方法与求解连通性问题的方法 掌握：构造最小生成树的Prim和Kruskal方法 第九章 查找 教学内容： 1) 静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找 2) 二叉排序树：二叉排序树上的搜索、插入和删除 教学要求： 熟练掌握：静态搜索表的顺序搜索和折半搜索方法 熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 第十章 内部排序 教学内容： 1) 概述 2) 插入排序：直接插入

7、排序；对分插入排序；链表插入排序；希尔排序 3) 选择排序：直接选择排序；堆排序 教学要求： 掌握：排序的基本概念和性能分析方法 掌握：插入排序、选择排序、等内排序的方法及性能分析方法 单元名称：第 一 讲：绪论 一、教学目标 1.了解数据结构课程的体系结构 2.掌握本章介绍的各种基本概念和术语 3.了解数据结构的二元组表示 4.掌握逻辑结构与物理结构之间的映像关系。 二、重点与难点 重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。 难点：逻辑结构与物理结构之间的映像关系。 三、教学内容与教学过程 介绍本学期课程的内容及安排 本课程是计算机专业的重要专业课之一，主要介绍常用的数据结

8、构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。 成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占 30%，平时成绩为：作业成绩+出勤率+上机成绩。 讲授新课 1.1 什么是数据结构 讲解： 从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。 讲解： 例1-1图书馆的书目检索系统自动化问题。 1-2计算机和人机对奕问题 1-3多叉路口交通灯的管理问题 总结： 从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而 是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数

9、据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 介绍数据结构课程的发展以及与其他课程之间的关系。 1.2基本概念和术语 基本概念：数据、数据元素、数据项、数据对象、数据结构、结构 常见基本结构：集合、线性结构、树形结构、图状结构或网状结构 数据结构的形式定义： 数据结构一般用一个二元组来表示： Data_Structure=(D,S) 其中：D是数据元素的有限集，S是D上的关系的有限集 DS表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中： K=Ki|0in,n0是数据元素的有限集合，n为DS中数据元素的个数。

10、R=Rj|0jm,m0的取值为1。 是K上关系的有限集合，m为K上关系的个数，通常情况下mK上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶，称x为第一个元素，y为第二个元素。 数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。 举例讲解： 例 数据结构line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。 例数据结构tree=K，R，其中K=01，02，03，04，05，06，07，0

11、8，09，10，R=r，r=，。 例 数据结构graph=K，R，其中K=01，02，03，04，05，R=r，r=，。 介绍常见数据结构具体表示方式 (2) 逻辑结构 上述数据结构的定义是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。 (3) 物理结构 数据结构在计算机中的表示称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：

12、顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。 数据结构一般包括三方面内容： 数据的逻辑结构、数据的存储结构、数据的运算 小结： 总结本讲的主要内容 四、作业布置 见习题集 单元名称：第 二 讲：线性表的类型定义，线性表的顺序存储一、教学目标 掌握线性表

13、的顺序表示和实现 二、重点与难点 线性表的顺序表示和实现。 三、教学过程的具体安排 讲授新课 2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表等。 例如线性表，称ai-1是ai的直接前驱元素， ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。 线性表的长度：线性表中元素的个数，n=0为空表。 线性表中数据元素的位序。 抽象数据类型线性表的定义： 讲解定义中的数据对象，数据关系以及基本操作，重点讲解常用的

14、基本操作含义。 通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。 2.2 线性表的顺序表示和实现 线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。 顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a i)之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。 顺序表及其

15、特点, 顺序储存结构是一种随机存取的存储结构。 线性表的动态分配顺序存储结构。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType *elem; int length; int listsize; SqList; (1) 基于顺序存储结构的基本操作的实现 主要介绍下面的基本操作并且分析时间复杂度。 InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e); ListDelete_Sq(SqList &L, int i,

16、ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType);MergeList_Sq(SqList La,SqList Lb, SqList &Lc); 重点讲解： 顺序存储结构上实现线性表的插入操作 12i-1ii+1n，为了保证线性表的有序性，当在位设线性表置i(1in+1)之前插入一个新的数据元素x时，需要将第i个到第n个数据元A=(a,a,L,a,a,a,L,a)素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表的长度。 Status ListInsert

17、_Sq(SqList &L, int i, ElemType e) / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListlength_Sq(L)+1 if (i L.length+1) return ERROR; / 插入位置不合法 if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.e

18、lem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 q = &(L.elemi-1); / q指示插入位置 for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; / ListInsert_Sq 平均时间复杂度分析：f(n)=(0+1+2+L+n)/(n+1)=n/2=O(n) 顺序存储结构上实现线性表的删除操作 12i-1ii+1n ，设线性表为了保证线性表的有

19、序性,当删除第i(1in)个位置上的元素后，需要将第i+1个到第n个数据元素均向前移动A=(a,a,L,a,a,a,L,a)一个位置并改变线性表的长度。 Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L) if (i L.length) return ERROR; / 删除位置不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.elem+L.length-1; /

20、表尾元素的位置 for (+p; p next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点 scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入到表头 / CreateList_L 注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。 (2) 建立单链表 void CreateList_L(LinkList &L, int n) /正位序输入n个元素的值，建立带表头结点的单链线性表

21、L。 L = (LinkList) malloc (sizeof (LNode); r = L; L-next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点 scanf(&p-data); / 输入元素值 p-next=r-next; r-next=p; r = p; / 插入到表尾 / CreateList_L (3) 在带头结点的单链表中插入结点 分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的情况。 Status Lis

22、tInsert_L(LinkList L, int i, ElemType e) / 在带头结头的单链表L中第i位置之前插入元素e p = L; j = 0; while (p & j next; +j; / 寻找第i-1个结点 if (!p | j i-1) return ERROR; / i小于1或者大于表长 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_L (4) 在带头结点的单链表中删除结点

23、Status ListDelete_L(LinkList L, int i, ElemType &e) p = L; j = 0; while (p-next & j next; +j; /寻找第i个结点并令p指向其前趋 if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK; / ListDelete_L 注：上述两个算法的时间复杂度均为O(n)。 单链表的优点： 它是一种动态结构，整个存储空间为多个链表共用 不需预

24、先分配空间 插入、删除操作方便 单链表的缺点： 指针占用额外存储空间 不能随机存取，查找速度慢 小结：本讲主要介绍了单链表的存储结构，以及的基本操作的实现。 四、作业布置 见习题集 实验作业见实验指导。 第四讲 循环链表，双向链表，链表应用 一、教学目标 1了解循环链表和的基本概念； 2掌握双向链表的插入和删除操作； 3掌握一元多项式的表示及加法在链式存储结构上的实现。 二、重点与难点 双向链表的存储结构和基本操作实现。 三、教学内容与教学过程 讲授新课 单向循环链表 设指针p指向单向链表中最后一个结点，则p-next的值是0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点

25、的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最后一个结点，则p-next的值不是0而是等于指向循环链表中的第一个结点head的值。 双向链表 如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下： typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLi

26、nkList; 设指针p指向双向链表中的某个结点，则显然有以下的结论： p-prior-next=p=p-next-prior (1) 双向链表的插入操作 设指针变量p指向双向链表中的结点A，指针变量q指向被插入的新结点B，则在结点A的后面插入结点B的操作序列为： (1) q-next=p-next； (2) p-next-prior=q； (3) p-next=q； (4) q-prior=p； (2) 双向链表的删除操作 设指针变量p指向双向链表中被删除的结点X，则删除结点X的操作序列为： (1) p-prior-next=p-next； (2) p-next-prior=p-prior；

27、 (3) free(p)； 注：在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指针域的操作次序，以免丢失链域信息而造成链表中断的错误。 链式存储结构的应用：一元多项式的表示及相加 一元多项式Pn(x)可按升幂写成： 2n Pn(x)=P0+Px1+P2x+L+Pnx它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示： P=(P0,P1,P2,L,Pn) 每项系数i隐含在系数Pi的序号里。 若Qm(x)为一个一元多项式，同样用线性表Q表示： Q=(Q0,Q1,Q2,L,Qm) 这两个多项式可以相加，结果为Rn(x)=Pn(x)+Qm(x)，其中设nm，则用线性表

28、表示R为： R=(P0+Q0,P1+Q1,P2+Q2,L,Pm+Qm,Pm+1,L,Pn) 我们可以采用顺序存储结构存放P、Q和R，使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如S(x)=1+3x10001+2x20000的多项式时，要用长度为20001的线性表来表示。如果对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成： P=(P0,e0),(P1,e1),(P2,e2),L,(Pn,en) 因此上式S(x)可表示成(1, 0 ),(3, 1001), (2, 20000

29、 )。显然这样的线性表应采用链式存储结构。课本 P41 图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x8+5x11和一元多项式B(x)=8x+22x7-9x8，由这两个多项式得到的和多项式如图课本 P412.18所示。 用链表表示多项式时，链表中的数据类型描述成： typedef struct polynomial float coef; int expn ; struct polynomial *next; ElemType; 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指

30、数不相同的项则分别抄到和多项式中去。 第一步：分别从A表和B表的表头开始，根据比较pa-expn和pb-expn的比较结果分三种情况讨论，直到A表或B表全部处理完。 (1) pa-expn=pb-expn：则相加此两项的系数，如果相加后该项系数不等于0，则在C表中生成一个新结点存放该项，修改pa和pb使其指向各自的下一个结点。 (2) pa-expn pb-expn：则复制A表中pa所指向的结点到C表中，修改pa使其指向下一个结点。 (3) pa-expn expn：则复制B表中pb所指向的结点到C表中，修改pb使其指向下一个结点。 第二步：若B表没有处理完，将B表中剩余结点复制到C表中；反之

31、则将A表中剩余结点复制到C表中。 void create_item(LinkList &pc,float coef,int expn) p=(LinkList)malloc(sizeof(LNode); p-coef=coef; p-expn=expn; pc-next=p; pc=p; void ploy_add(LinkList pah,LinkList pbh,LinkList &pch) pa = pah; pb = pbh; pc = pch=(LinkList *)malloc(sizeof(LNode); / 为c链表添加一个头结点 while(pa!=0 & pb!=0) if

32、(pa-expn=pb-expn) x=pa-coef+pb-coef; if(x!=0) create_item(pc,x,pa-expn); pa=pa-next; pb=pb-next; else if(pa-expnpb-expn) create_item(pc,pa-coef,pa-expn); pa=pa-next; else create_item(pc,pb-coef,pb-expn); pb=pb-next; while (pa!=0) create_item(pc,pa-coef,pa-expn); pa=pa-next; while (pb!=0) create_item

33、(pc,pb-coef,pb-expn); pb=pb-next; pc-next=0; pc=pch; pch=pch-next; free(pc); /* 释放c链中的头结点 */ 小结：本讲主要介绍了循环链表和双向链表的基本概念，双向链表的插入和删除操作，一元多项式的表示及相加在链式存储结构上的实现。 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第 五 讲：栈 一、教学目标 1了解栈的基本概念和基本操作； 2掌握栈的基本操作在两种存储结构上的实现。 二、重点与难点 栈的基本操作在两种存储结构上实现。 三、教学内容与教学过程 首先复习线性表的知识，引入限定性的数据结构栈和队列。

34、 讲授新课 3.1 栈 3.1.1 抽象数据类型栈的定义 栈：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈。 通过教材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。 栈的抽象数据类型定义： ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶， a1 端为栈底。 基本操作： InitStack(&S) StackEmpty(S) Push(&S, e) DestroyStack(&S) StackLength(S) ClearStac

35、k(&S) GetTop(S, &e) Pop(&S, &e) ADT Stack 3.1.2 栈的表示和实现 顺序栈 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 栈的顺序存储表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 顺序栈的基本操作的算法描述： 初始化，返回栈顶元素，入栈，出栈。 (a) 栈空栈满条件 栈空条件：top=base 栈满条件：base-top

36、=stacksize (b) 入栈操作 Status Push (SqStack &S, SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base ) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+ = e; return OK; (c) 出栈操作 Status Pop (S

37、qStack &S, SElemType &e) if (S.top=S.base) return ERROR; e=*-S.top; return OK; 链栈：栈的链式存储结构。栈顶指针就是链表的头指针 栈的链式存储结构类似单链表的存储结构，链表中第一个结点表示栈顶，最后一个结点表示栈底。由于链表的长度可以动态增长，因此进行入栈操作时无需考虑栈的上溢，但进行出栈操作时，必需考虑栈的下溢，下溢的条件是top的值为0。 链式栈的入栈操作 Status Push(LinkList &top, ElemType x) p=(LinkList *)malloc(sizeof(LNode); p-da

38、ta=x; p-next=top; top=p; return OK; (2) 链式栈的出栈操作 Status Pop(LinkStack &top, ElemTye &y) if (top=0) return ERROR; p=top; y=p-data; top=p-next; free(p); return OK; 小结；本讲主要介绍了栈的基本概念，栈的基本运算，栈在顺序存储结构和链式存储结构上实现基本操作。 四、作业布置 见习题集 实验作业见实验指导。 单元名称：第 六 讲：队列 一、教学目标 1了解栈的基本概念和基本操作； 2掌握栈的基本操作在两种存储结构上的实现。 二、重点与难点

39、栈的基本操作在两种存储结构上实现。 三、教学内容与教学过程 讲授新课 队列的基本概念 队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另一端进行的特殊线性表。允许插入操作的一端称为队尾，允许删除操作的一端称为队头。 设队列为q=(a1,a2,L,an)，则a1是队头元素，an是队尾元素。队列中的元素按照a1,a2,L,an的顺序进入队列的，退出队列也只能按照这个次序依次退出，即只有在 a1,a2,L,an-1都退出队列后，an才能退出队列。因此队列也称为先进先出的线性表。2、队列的基本操作 InitQueue(&Q) QueueEmpty(Q) DestroyQueue

40、(&Q) ClearQueue(&Q) QueueLength(Q) GetHead(Q, &e) EnQueue(&Q, e) DeQueue(&Q, &e) 3、队列的顺序存储结构和循环队列 在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针front和rear。为了在C语言中描述方便起见，在此我们约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。 讨论：将数据10，

41、20，30，40，50，60按照入队列、入队列、入队列、出队列、出队列、入队列、入队列、入队列、出队列和出队列的顺序，观察队列中队头和队尾指针的变化状态。 假设当前为队列分配的最大空间为6，则不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破环，然而，此时又不宜如顺序栈那样进行存储再分配扩大数组空间，因为队列的实际可用空间并末占满。解决这个问题的巧妙方法是将顺序队列的存储空间想象成一个逻辑上首尾相连的环状空间，这种存储结构称为循环队列。 分析课本P64图3.14可知，Q.front=Q.rear无法判断队列空间是“满”还是“空”。解决这个问题有两种方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的下一个位置上作为队列“满”的标