数据结构教案C语言版

1、.课程教案课程名称： 数据结构 授课教师：学习对象：任课时间：一、学生情况分析数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了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) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历7)

5、二叉树的计数8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码教学要求：了解：树和森林的概念掌握：二叉树的概念、性质及二叉树的表示熟练掌握：二叉树的遍历方法掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：树和森林的实现及遍历方法掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法及霍夫曼编码的概念第七章 图教学内容：1）图的基本概念：图的基本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量4）最小生成树：克鲁斯卡尔算法；普里姆算法教学要求：掌握：图的基本概念和图的存储表示熟练掌握

6、：图的两种遍历方法与求解连通性问题的方法掌握：构造最小生成树的Prim和Kruskal方法第九章 查找教学内容：1) 静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找2) 二叉排序树：二叉排序树上的搜索、插入和删除教学要求：熟练掌握：静态搜索表的顺序搜索和折半搜索方法熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法第十章 内部排序 教学内容：1) 概述2) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3) 选择排序：直接选择排序；堆排序教学要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、选择排序、等内排序的方法及性能分析方法单元名称：第 一 讲：

7、绪论 一、教学目标 1.了解数据结构课程的体系结构2.掌握本章介绍的各种基本概念和术语3.了解数据结构的二元组表示4.掌握逻辑结构与物理结构之间的映像关系。二、重点与难点重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。难点：逻辑结构与物理结构之间的映像关系。三、教学内容与教学过程介绍本学期课程的内容及安排本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占30%，平时成绩为：作业成绩+出勤率+上机成绩。讲授新课1.1 什

8、么是数据结构 讲解：（数据结构课程的研究背景）从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。讲解：（数据结构课程的研究对象）例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题1-3多叉路口交通灯的管理问题总结：从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。介绍数据结构课程的发展以及与其他课程之间的关系。1.2基本概念和术语基本概念：数据、数据元素、数据项、数

9、据对象、数据结构、结构（1）常见基本结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构数据结构的形式定义： 数据结构一般用一个二元组来表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：是数据元素的有限集合，n为中数据元素的个数。是K上关系的有限集合，m为K上关系的个数，通常情况下m的取值为1。K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶（x，yK），称x为第一个元素（或y的前驱），y为第二个元素（或x的后继）。数据结构中的数据元素和数据元素

10、之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例 数据结构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，08，09，10，R=r，r=，。例 数据结构graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式(2) 逻辑结构上述数据结构的定义是对

11、操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。(3) 物理结构数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

12、非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。（4）数据结构一般包括三方面内容： 数据的逻辑结构、数据的存储结构、数据的运算 （举例讲解）小结：总结本讲的主要内容四、作业布置见习题集 单元名称：第 二 讲：线性表的类型定义，线性表的顺序存储一、教学目标 掌握线性表的顺序表示和实现二、重点与难点线性表的顺序表示和实现。三、教学过程的具体安排讲授新课2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的

13、具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表（图2.1）等。 例如线性表（a1,ai-1,ai,ai+1,an），称ai-1是ai的直接前驱元素， ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。线性表的长度：线性表中元素的个数（n0），n=0为空表。 线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以及基本操作（教材P19），重点讲解常用的基本操作含义。通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。2.2

14、 线性表的顺序表示和实现（1）线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。（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)为线性表的基地址。（3）顺序表及其特点, 顺序储存结构是一种随机存取的存储结构。（4）线性表的动态分配顺序存储结

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, ElemType &e);LocateElem_Sq(SqList L, ElemTy

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

17、L)+1if (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.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = &(L.elemi-1); / q指示插入位置for (

18、p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增1return OK; / ListInsert_Sq平均时间复杂度分析： 顺序存储结构上实现线性表的删除操作设线性表 ，为了保证线性表的有序性,当删除第个位置上的元素后，需要将第i+1个到第n个数据元素均向前移动一个位置并改变线性表的长度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回其值。/ i的合法值为1i

19、ListLength_Sq(L)if (i L.length) return ERROR; / 删除位置不合法p = &(L.elemi-1); / p为被删除元素的位置e = *p; / 被删除元素的值赋给eq = L.elem+L.length-1; / 表尾元素的位置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; / 插入

20、到表头 / CreateList_L注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。(2) 建立单链表（要求从尾部插入）void CreateList_L(LinkList &L, int n) /正位序输入n个元素的值，建立带表头结点的单链线性表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); / 输入元素值

21、p-next=r-next; r-next=p; r = p; / 插入到表尾 / CreateList_L (3) 在带头结点的单链表中插入结点分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的情况。Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结头的单链表L中第i位置之前插入元素ep = L; j = 0;while (p & j next; +j; / 寻找第i-1个结点if (!p | j i-1) return ERROR; / i小于1或者大于表长s = (LinkList) malloc

22、 ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; / 插入L中p-next = s;return OK; / LinstInsert_L(4) 在带头结点的单链表中删除结点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;

23、/ 删除并释放结点e = q-data; free(q);return OK; / ListDelete_L注：上述两个算法的时间复杂度均为O(n)。单链表的优点：它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间插入、删除操作方便单链表的缺点：指针占用额外存储空间不能随机存取，查找速度慢小结：本讲主要介绍了单链表的存储结构，以及的基本操作（建立、插入和删除）的实现。四、作业布置见习题集实验作业见实验指导。 第四讲 循环链表，双向链表，链表应用一、教学目标 1了解循环链表和的基本概念；2掌握双向链表的插入和删除操作；3掌握一元多项式的表示及加法在链式存储结构上的实现。二、重点与难点双

24、向链表的存储结构和基本操作实现。三、教学内容与教学过程讲授新课单向循环链表设指针p指向单向链表中最后一个结点，则p-next的值是0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最后一个结点，则p-next的值不是0而是等于指向循环链表中的第一个结点head的值。双向链表如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下：typedef struct DuLNode ElemT

25、ype data; / 数据域struct DuLNode *prior; / 指向前驱的指针域struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;设指针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) 双向链表的删除操

26、作设指针变量p指向双向链表中被删除的结点X，则删除结点X的操作序列为：(1) p-prior-next=p-next； (2) p-next-prior=p-prior； (3) free(p)；注：在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指针域的操作次序，以免丢失链域信息而造成链表中断的错误。链式存储结构的应用：一元多项式的表示及相加一元多项式可按升幂写成：它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示：每项系数i隐含在系数的序号里。若为一个一元多项式，同样用线性表Q表示：这两个多项式可以相加，结果为，其中设，则用线性表表示R为：我们可以采用顺序存

27、储结构存放P、Q和R，使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如S(x)=1+3x10001+2x20000的多项式时，要用长度为20001的线性表来表示。如果对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成：因此上式S(x)可表示成(1, 0 ),(3, 1001), (2, 20000 )。显然这样的线性表应采用链式存储结构。课本 P41 图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x8+5x11和一元多项式B(x)=8x+22x7-9x8，由这

28、两个多项式得到的和多项式如图课本 P412.18所示。用链表表示多项式时，链表中的数据类型描述成：typedef struct polynomialfloat coef;int expn ; struct polynomial *next;ElemType;根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项则分别抄到和多项式中去。第一步：分别从A表和B表的表头开始，根据比较pa-expn和pb-expn的比较结果分三种情况讨论，直到A表或B表全部处理完。(1) pa-expn=pb-ex

29、pn：则相加此两项的系数，如果相加后该项系数不等于0，则在C表中生成一个新结点存放该项，修改pa和pb使其指向各自的下一个结点。(2) pa-expn pb-expn：则复制A表中pa所指向的结点到C表中，修改pa使其指向下一个结点。(3) pa-expn expn：则复制B表中pb所指向的结点到C表中，修改pb使其指向下一个结点。第二步：若B表没有处理完，将B表中剩余结点复制到C表中；反之则将A表中剩余结点复制到C表中。void create_item(LinkList &pc,float coef,int expn)p=(LinkList)malloc(sizeof(LNode);p-co

30、ef=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(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-

31、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(pc,pb-coef,pb-expn); pb=pb-next;pc-next=0; pc=pch; pch=pch-next; free(pc); /* 释放c链中的头结点 */小结：本讲主要介绍了循环链表和双向链表的基本概念，双向链

32、表的插入和删除操作，一元多项式的表示及相加在链式存储结构上的实现。四、作业布置见习题集实验作业见实验指导。单元名称：第 五 讲：栈一、教学目标 1了解栈的基本概念和基本操作；2掌握栈的基本操作在两种存储结构上的实现。二、重点与难点栈的基本操作在两种存储结构上实现。三、教学内容与教学过程首先复习线性表的知识，引入限定性的数据结构栈和队列。讲授新课3.1 栈3.1.1 抽象数据类型栈的定义栈：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈。通过教材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。栈的抽象数据类型定义：ADT Stack 数据对象：D ai |

33、ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e) Push(&S, e)Pop(&S, &e) ADT Stack3.1.2 栈的表示和实现顺序栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。 栈的顺序存储表示： #define STACK_INIT_SIZE 100; #define STACKINCREM

34、ENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;顺序栈的基本操作的算法描述：初始化，返回栈顶元素，入栈，出栈。(a) 栈空栈满条件栈空条件：top=base栈满条件：base-top=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(

35、SElemType);if(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e;return OK; (c) 出栈操作Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR;e=*-S.top;return OK;链栈：栈的链式存储结构。栈顶指针就是链表的头指针栈的链式存储结构类似单链表的存储结构，链表中第一个结点表示栈顶，最后一个结点表示栈底。由于链表的长度可以动态增长，因此进行入栈操

36、作时无需考虑栈的上溢，但进行出栈操作时，必需考虑栈的下溢，下溢的条件是top的值为0。链式栈的入栈操作Status Push(LinkList &top, ElemType x)p=(LinkList *)malloc(sizeof(LNode); p-data=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;小结；本讲主要介绍了栈的基本概

37、念，栈的基本运算，栈在顺序存储结构和链式存储结构上实现基本操作。四、作业布置 见习题集实验作业见实验指导。单元名称：第 六 讲：队列一、教学目标 1了解栈的基本概念和基本操作；2掌握栈的基本操作在两种存储结构上的实现。二、重点与难点栈的基本操作在两种存储结构上实现。三、教学内容与教学过程讲授新课队列的基本概念队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另一端进行的特殊线性表。允许插入（入队）操作的一端称为队尾，允许删除（出队）操作的一端称为队头。设队列为，则是队头元素，是队尾元素。队列中的元素按照的顺序进入队列的，退出队列也只能按照这个次序依次退出，即只有在都退出队

38、列后，才能退出队列。因此队列也称为先进先出（FIFO）的线性表。2、队列的基本操作InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)EnQueue(&Q, e)DeQueue(&Q, &e)3、队列的顺序存储结构和循环队列在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针front和rear。为了在C语言中描述方便起见，在此我们约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每

39、当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。讨论：将数据10，20，30，40，50，60按照入队列、入队列、入队列、出队列、出队列、入队列、入队列、入队列、出队列和出队列的顺序，观察队列中队头和队尾指针的变化状态。假设当前为队列分配的最大空间为6，则不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破环，然而，此时又不宜如顺序栈那样进行存储再分配扩大数组空间，因为队列的实际可用空间并末占满。解决这个问题的巧妙方法是将顺序队列的存储空间想象成一个逻辑上首尾相连的环状空间，这种存储结构称为循环队列。分析课本

40、P64图3.14可知，Q.front=Q.rear无法判断队列空间是“满”还是“空”。解决这个问题有两种方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的下一个位置上作为队列“满”的标志。因此，判断队列空的条件为Q.front=Q.rear；判断队列满的条件为Q.front = (Q.rear+1) % MAXQSIZE。(a) 顺序循环队列的类型描述typedef struct QElemType *base; int front; int rear; SqQueue; (b) 顺序循环队列的入队列操作status EnQueue(Sq

41、Queue&Q, QelemType e)if (Q.rear+1)%MAXSIZE=Q.front) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;(c) 顺序循环队列的出队列操作status DeQueue(SqQueue &Q, QelemType &e) if (Q.rear=Q.front) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1)%MAXSIZE;return OK;4、队列的链式存储结构队列的链式存储结构实际上是一个同时带有头指针和尾指

42、针的单向链表，头指针指向队头元素，尾指针指向队尾元素。为了操作方便起见，给链式队列添加一个头结点。空的链式队列的判断条件为头指针和尾指针都指向头结点。(a) 链式循环队列的类型描述typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; / 队头指针QueuePtr rear; / 队尾指针 LinkQueue;(b) 链式队列的入队列操作stutus EnQueue(LinkQueue &Q, QelemType e)p=(QueuePtr)

43、malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;(c) 链式队列的出队列操作。status DeQueue (LinkQueue &Q, QelemType &e) if(Q.front=Q.rear returnERROR;p=Q.front-next; e=p-data; Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front; free(p);return OK;注意：当队列中最后一个元素被删除后，队

44、列尾指针也丢失了，因此需要对队尾指针重新赋值。小结：主讲主要介绍了队列的基本概念和基本操作，以及队列的基本操作在顺序存储结构和链式存储结构上的实现。四、作业布置 见习题集实验作业见实验指导。单元名称：第 七 讲：串一、教学目标 1.熟悉串的定义以及基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆分配存储结构以及在其上实现串操作的基本方法。4.了解串的块链存储结构二、重点与难点串的存储结构以及基本操作的实现。三、教学内容与教学过程讲授新课4.1 串类型的定义（1）基本概念：串（string）：由零个或多个

45、字符组成的有限序列，也称字符串。记为：S = a1a2a3an (n0) 如：A= BEIJING， B= JING串的长度：串中字符的数目n 。空串：不含任何字符的串，串长度为0，空格串：仅由一个或多个空格组成的串，长度为串中空格字符的个数。如： ， C= BEI JING 子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A= BEIJING B= JING 字符在串中的位置：字符在序列中的序号。子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。如：A= BEIJING ，B= JING ，B在A中的位置为4。串相等：当且仅当两个串的值相等。也就是说，只有两个串的

46、长度相等且各个对应位置的字符都相等时才相等。（2）串的抽象数据类型定义：ADT String 数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n 基本操作：（见教材P71） ADT String 通过基本操作可以实现更复杂的操作。如通过判等、求串长和求子串等操作可以实现定位函数Index。 4.2 串的表示和实现4.2.1 定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define MA

47、XSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char SStringMAXSTRLEN + 1; / 0号单元存放串的长度特点：串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”（通过串联接和求子串来讲解）。4.2.2 堆分配存储表示以一组地址连续的存储单元存储串值的字符序列，存储空间在程序执行过程中动态分配。 C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。串堆分配存储表示：typedef struct char *ch; / 若是非空串，则按串长分配存储区,否则ch为NULLint length; / 串长度 HString;这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制（以串的复制操作为例）。讲解串堆分配的表示与实现 （P76，77）4.2.3 块链存储表示 以链表存储串值，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的传存储结构为块链结构。#defin