数据结构教案C语言版

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

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

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

4、数组的定义和初始化2) 作为抽象数据类型的数组的顺序存储方式 教学要求：了解：作为抽象数据类型的数组的定义熟练掌握：顺序表的数组定义方式及实现 第六章树和二叉树教学内容：1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3) 二叉树的表示：数组表示；链表存储表示4) 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例; 叉树的中序非递归算法5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历7) 二叉树的计数8) 霍夫曼

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

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

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

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

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

10、（或 x的后继）。数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的 每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序 偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例 数据结构 line=K，R，其中 K=01，02, 03, 04, 05，06, 07, 08, 09，10，R=r， r=<01 , 02>, <02, 03>, <03, 04>,<04, 05>, <05, 06> , <06 , 07> , <07 , 08> , <

11、;08 , 09> , <09, 10>。例数据结构 tree=K , R,其中 K=01 , 02 , 03 , 04 , 05 , 06 , 07 , 08 , 09 , 10 , R=r, r=<01 , 02> , <01, 03> , <01, 04> , <02 , 05> , <02 , 06> , <04 , 07> , <04 , 08>, <06 , 09> , <06, 10>。例数据结构 graph=K , R,其中 K=01 , 02 , 03

12、 , 04 , 05 , R=r , r=<01 , 02>, <02 , 01>, <01, 04>, <04, 01>, <01, 03>, <03, 01>, <02, 04>, <04, 02>, <03, 05>, <05, 03>。介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式（2）逻辑结构上述数据结构的定义是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的 关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。

13、根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构 和图型结构。（3）物理结构数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉及到数 据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同 的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式 将数据的物理结构划分为顺序结构和链式结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非 顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。注意：数据的逻辑结构和物理结构是密切相关的两个方面，任

14、何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。（4）数据结构一般包括三方面内容：数据的逻辑结构、数据的存储结构、数据的运算（举例讲解）小结：总结本讲的主要内容四、作业布置见习题集单元名称：第 二讲：线性表的类型定义，线性表的顺序存储 '、教学目标掌握线性表的顺序表示和实现、重点与难点线性表的顺序表示和实现。三、教学过程的具体安排讲授新课2.1线性表的类型定义线性表的定义：一个线性表是n个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数 据对象。例如：26个英文字母表；学生健康情况

15、登记表(图 2.1)等。例如线性表(ai,a/,ai,ai+i,an)，称ai-i是ai的直接前驱元素，a+i是ai的直接后继。引导学生自己总结线性结构的特点。线性表的长度：线性表中元素的个数(n > 0),n=0为空表。 线性表中数据元素的位序(如数据元素ai在线性表中的位序为i)。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以及基本操作(教材P19 ),重点讲解 常用的基本操作含义。通过示例2-1 , 2-2讲解更复杂的基本操作，并分析时间复杂度。2.2线性表的顺序表示和实现(1 )线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数 据元素。(2 )顺序储存的地

16、址关系：假设线性表的每个元素需占用I个存储单元， 并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1 个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a i)之间满 足下列关系：LOC(a i+1)=LOC(a i)+l线性表的第i个数据元素ai的存储位置为：LOC(a i)=LOC(a 1)+(i-1)*l,其中 LOC(a 1)为线性表的基地址。(3) 顺序表及其特点，顺序储存结构是一种随机存取的存储结构。(4) 线性表的动态分配顺序存储结构。#define LIST_INIT_SIZE100#defi ne LISTINCREMENT10

17、Typedef struct ElemType *elem; intlen gth;intlistsize;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, ElemType e, Status (*compare)(ElemType, Ele

18、mType);MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重点讲解：顺序存储结构上实现线性表的插入操作设线性表A 知去，目仆耳印仆，an，为了保证线性表的有序性，当在位 置i1 i n 1之前插入一个新的数据元素X时，需要将第i个到第n个数据元素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表 的长度。Status Listl nsert_Sq(SqList & L, int i, ElemType e) /在顺序线性表L的第i个元素之前插入新的元素e,/ i 的合法值为 1 < i w Listlengt

19、h_Sq(L)+1if (i < 1 | i > L.length+1) return ERROR; /插入位置不合法if (L.length >= L.listsize) /当前存储空间已满，增加 分配n ewbase = (ElemType *)realloc(L.elem,(ElemType);存储分配失败增加存储容量(Listsize+LISTINCREMENT)*sizeof if (!n ewbase) exit(OVERFLOW); / L.elem = n ewbase; /新基址L.listsize += LISTINCREMENT; /q = &(

20、L.elemi-1); / q指示插入位置for (p = & (L.elemL.le ngth-1); p >= q; -p) *(p+1) = *p;/插入位置及之后的元素右移*q = e; / 插入 e+L.le ngth; / 表长增 1return OK; / ListI nsert_Sq平均时间复杂度分析：f(n) (° 1 2n”(n 1) n/2 0(n)顺序存储结构上实现线性表的删除操作设线性表A 知" 8 1,a，ai “ ，an ，为了保证线性表的有序性，当删除 第i(1 i n)个位置上的元素后，需要将第i+1个到第n个数据元素均向前移

21、动 一个位置并改变线性表的长度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) /在顺序线性表L中删除第i个元素，并用e返回其值。/ i 的合法值为 1 w i w ListLength_Sq(L)if (i < 1) | (i > L.le ngth) return ERROR;/ 删除位置不合法p = &(L.elemi-1);/ p为被删除元素的位置e = *p;/被删除元素的值赋给eq = L.elem+L.length-1;/ 表尾元素 的位置for (+p; p <= q; +p) *

22、(p-1) = *p;/被删除元素之后的元素左移-L.le ngth; / 表长减 1return OK; / ListDelete_Sq平均时间复杂度分析：f(n)(°12 (n 1)/n n 1/20(n)总结： 顺序存储结构的优缺点顺序结构的优点是结构简单，对数据元素既可以实现顺序访问，又可以实 现随机访问；缺点是插入和删除操作需要移动大量的数据元素。小结：本讲主要介绍了线性表的逻辑结构定义和基本运算，线性表的插入和删除操作在 顺序存储结构上的实现。小结：总结本讲的主要内容四、作业布置见习题集实验作业见实验指导单元名称：第三讲：线性表链式存储、教学目标掌握单链表的表示和实现、重

23、点与难点单链表的存储结构和基本操作实现。三、教学内容与教学过程复习线性表的顺序存储结构的特点引入另一种表示方法链式存储结构。 讲授新课2.3.1线性链表（1）线性链表线性链表：用一组任意的存储单元存储线性表的数据元素（这组存储单元 可以是连续的，也可以是不连续的）。线性链表的存储结构：以元素（数据元素的映象）+指针（指示后继元素存储位置）=结点（表示数据元 素 或 数据元素的映象），其中指针域只有一个。举例讲解：教材图2.5线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头 指针。有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结 点的指针为链表的头指针。线性表为空

24、时，头结点的指针域为空。举例如图2.7.线性表的单链表存储结构的C语言描述：typedef struc LNode ElemType struct LNodeLNode, *Li nkList ； 单链表操作的实现：/定义单链表结点data;GetElem(L, i, e)ListInsert(&L, i, e)/取第i个数据元素/插入数据元素ListDele CreateList (&L, n)/生成含n个数据元素的链表CreateList (&L, n)/生成含n个数据元素的链表MergeList (&La,&Lb,&Lc) /合并两个有序链

25、表*next ；/指向后继的指针域欢迎下载13（1）建立单链表（要求从头部插入）void CreateList_L（Li nkList & L, i nt n）/逆位序输入n个元素的值，建立带表头结点的单链线性表L。L = (Lin kList) malloc (sizeof (LNode);L-> next = NULL; /先建立一个带头结点的单链表for (i = n; i > 0; -i ) p = (Li nkList) malloc (sizeof (LNode); / 生成新结点scanf(&p->data); / 输入元素值p->next

26、 = L->n ext; L->n ext = p; /插入到表头 / CreateList_L注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。（2）建立单链表（要求从尾部插入）void CreateList_L（Li nkList & L, i nt n）L。/正位序输入n个元素的值，建立带表头结点的单链线性表L = (Lin kList) malloc (sizeof (LNode);r = L;L-> next = NULL; /先建立一个带头结点的单链表for (i = n; i > 0; -i ) p = (Li nkList) mal

27、loc (sizeof (LNode); / 生成新结点scanf(&p->data); / 输入元素值p->n ext=r- >n ext; r->n ext=p; r = p; /插入至 U表尾 / CreateList_L(3) 在带头结点的单链表中插入结点分析：设在结点a和结点b之间插入数据为 x的结点，通过图来分析则插入前和插入后的 情况。Status List In sert_L(L in kList L, int i, ElemType e) /在带头结头的单链表L中第i位置之前插入元素ep = L; j = 0;while (p &&am

28、p; j < i-1) p = p->next; +j; / 寻找第 i-1 个结点if (!p | j > i-1) return ERROR; / i 小于 1 或者大于表长s = (L in kList) malloc ( sizeof (LNode); /生成新结点s->data = e; s->next = p->next; / 插入 L 中p_>next = s;return OK; / Li nstl nsert_L(4) 在带头结点的单链表中删除结点Status ListDelete_L(L in kList L, i nt i, El

29、emType &e)p = L; j = 0;while (p->next && j < i-1) p = p_>n ext; +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注：上述两个算法的时间复杂度均为0( n)。单链表的优点：它是一种动态结构，整个

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

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

32、, *DuLi nkList;设指针p指向双向链表中的某个结点，则显然有以下的结论：p->prior- >n ext=p=p->n ext->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-

33、>prior->next=p->next ；(2) p_>next->prior=p->prior ；(3) free(p)；注：在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指 针域的操作次序，以免丢失链域信息而造成链表中断的错误。链式存储结构的应用：一元多项式的表示及相加一元多项式Pn(x)可按升幕写成：Pn(x)F0Rx F2x2 LPnXn它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示：P(P0,P,P2 丄，R)每项系数i隐含在系数P的序号里。若Qm(x)为一个一元多项式，同样用线性表 Q表示：欢迎下载15Q

34、(Q0,Q1,Q2,L ,Qm)这两个多项式可以相加，结果为R/x)巳(x) Qm(x)，其中设n m，则用线性表表示R为：R(P0Q0,PQ1,P2Q2丄，PmQmHml'L ,P!)我们可以采用顺序存储结构存放P、Q和R,使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如 S(x)=1+3x 10001+2x20000的多项式时，要用长度为20001的线性表来表示。如果对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表 示成：P (F0,eo),( Pe),(卩2,良)丄

35、，(Pn©)因此上式S(x)可表示成(1,0 ),(3, 1001), (2, 20000 )。显然这样的线性表应采用链式存储结 构。课本P41图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x 8+5x"和一元多项式B(x)=8x+22x 7-9x8，由这两个多项式得到的和多项式如图课本P412.18所示。用链表表示多项式时，链表中的数据类型描述成：typedef struct polyno mialfloat coef;int exp n ;struct polyno mial *n ext;ElemType;根据一元多项式相加的运算规则：对于两个一元多

36、项式中所有指数相同的项，对应系数 相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的 项则分别抄到和多项式中去。第一步：分别从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使其指向下 一个结

37、点。(3) pa->expn < pb->expn :则复制B表中pb所指向的结点到 C表中，修改pb使其指向 下一个结点。第二步：若B表没有处理完，将 B表中剩余结点复制到C表中；反之则将 A表中剩余结点复制到C表中。void create_item(L in kList &pc,float coef,i nt exp n)p=(L in kList)malloc(sizeof(LNode);p->coef=coef; p->exp n=exp n;pc->n ext=p;pc=p;void ploy_add(L in kList pah,L in

38、 kList pbh,L in kList &pch)pa = pah; pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode);/ 为 c 链表添加一个头结点while(pa!=0 && pb!=0)if(pa->exp n=pb_>exp n)x=pa->coef+pb->coef;if(x!=0) create_item(pc,x,pa->exp n);pa=pa->n ext; pb=pb->n ext;else if(pa->exp n>pb->exp n

39、)create_item(pc,pa->coef,pa->exp n);pa=pa->n ext;else create_item(pc,pb->coef,pb->exp n); pb=pb->n ext;while (pa!=0) create_item(pc,pa->coef,pa->exp n);pa=pa->n ext;while (pb!=0) create_item(pc,pb->coef,pb->exp n);pb=pb->n ext;pc->next=0; pc=pch; pch=pch->ne

40、xt; free(pc); /* 释放 c链中的头结点*/小结：本讲主要介绍了循环链表和双向链表的基本概念，双向链表的插入和删除操作，一元 多项式的表示及相加在链式存储结构上的实现。四、作业布置见习题集实验作业见实验指导。单元名称：第五讲：栈一、教学目标1 .了解栈的基本概念和基本操作；2. 掌握栈的基本操作在两种存储结构上的实现。二、重点与难点栈的基本操作在两种存储结构上实现。三、教学内容与教学过程首先复习线性表的知识，引入限定性的数据结构栈和队列。讲授新课3.1栈3.1.1抽象数据类型栈的定义栈：限定仅在表尾进行插入或删除操作的线性表，表尾一栈顶，表头一栈 底，不含元素的空表称空栈。通过教

41、材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。栈的抽象数据类型定义：ADT Stack 数据对象：D = ai | ai ElemSet, i=1,2,.,n,n > 0 ADT Stack3.1.2 栈的表示和实现 顺序栈类似于线性表的顺序映象实现， 栈的顺序存储表示：#defi neSTACK_INIT_SIZE#defi neSTACKINCREMENTtypedef struct SElemType*base;SElemType*top;int stacksize; SqStack;顺序栈的基本操作的算法描述： 初始化，返回栈顶元素，入栈， 栈空栈满条件栈空条件：top=

42、base栈满 条件：base-top=stacksize(b)入栈操作指向表尾的指针可以作为栈顶指针。100;10;数据关系：R1 = <ai-1, ai >| ai-1, ai D, i=2,.,n 约定an端为栈顶，a1端为栈底。基本操作：Ini tStack(&S)DestroyStack (&S)ClearStack(&S)StackEmpty(S)StackLe ngth(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)Status Push (SqStack &S, SElemTy

43、pe e) if(S.top-S.base>=S.stacksize) S.base=(SEIemType*)realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType); if(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;欢迎下载18*S.top+ = e;return OK;(c)出栈操作Status Pop (SqStack &S, SEIemType &e) if (S.top=S.base

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

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

46、与教学过程讲授新课队列的基本概念队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另端进行的特殊线性表。允许插入(入队)操作的一端称为队尾，允许删除(出队)操作的一端称为队头。设队列为q (aa2,L ,an)，则ai是队头元素，务是队尾元素。队列中的元素按照ai,a2丄,an的顺序进入队 列的，退出队列也只能按照这个次序依次退出，即只有在 ai,a2,L ,务1都退出队列后，a.才能退出队列。因此队列也称为先进先出(FIFO)的线性表。2、队列的基本操作Ini tQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)Que

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

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

49、有两种方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的 下一个位置上作为队列“满”的标志。因此，判断队列空的条件为Q.front=Q.rear ；判断队列满的条件为 Q.front = (Q.rear+1) % MAXQSIZE(a) 顺序循环队列的类型描述typedef struct QElemType *base; int front; int rear; SqQueue;(b) 顺序循环队列的入队列操作status En Queue(SqQueue&Q, QelemType e)if (Q.rear+1)%MAXSIZE=

50、Q.fro nt) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;欢迎下载20return OK;(c) 顺序循环队列的出队列操作status DeQueue(SqQueue &Q, QelemType &e) if (Q.rear=Q.fro nt) return ERROR;e = Q.baseQ.fr on t;Q.fro nt = (Q.fro nt+1)%MAXSIZE;return OK;4、队列的链式存储结构队列的链式存储结构实际上是一个同时带有头指针和尾指针的单向链表， 头指针指向队头元素，尾指针指向

51、队尾元素。为了操作方便起见，给链式队列 添加一个头结点。空的链式队列的判断条件为头指针和尾指针都指向头结点。(a) 链式循环队列的类型描述typedef struct QNode QElemType data;struct QNode *n ext; QNode, *QueuePtr;typedef struct QueuePtr front; /队 头指针QueuePtr rear; /队尾指针 Lin kQueue;(b) 链式队列的入队列操作stutus En Queue(L in kQueue &Q, QelemType e)p=(QueuePtr)malloc(sizeof(

52、Q no de);if(!p)exit(OVERFLOW);p->data=e; p->n ext=NULL; Q.rear- >n ext=p; Q.rear=p;return OK;(c) 链式队列的出队列操作。status DeQueue (Lin kQueue &Q, QelemType &e) if(Q.fro nt=Q.rear returnERROR;p=Q.fr ont->n ext; e=p->data; Q.front->n ext=p->n ext;if(Q.rear=p)Q.rear=Q.fr ont;free(

53、p);return OK;注意：当队列中最后一个元素被删除后，队列尾指针也丢失了，因此需要对 队尾指针重新赋值。小结：主讲主要介绍了队列的基本概念和基本操作，以及队列的基本操作在顺 序存储结构和链式存储结构上的实现。四、作业布置见习题集实验作业见实验指导。欢迎下载26教学目标单兀名称：第七讲：串1. 熟悉串的定义以及基本操作的定义，并能利用这些基本操作来实现串的 其它各种操作的方法。2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3掌握串的堆分配存储结构以及在其上实现串操作的基本方法。4. 了解串的块链存储结构二、重点与难点串的存储结构以及基本操作的实现。三、教学内容与教学过程讲

54、授新课4.1串类型的定义（1）基本概念：串（string ）:由零个或多个字符组成的有限序列，也称字符串。记为：S =' a1a2a3 an' （in 0）女口： A= ' BEIJING B= ' JING '串的长度：串中字符的数目n 。空串：不含任何字符的串，串长度为0,空格串：仅由一个或多个空格组成的串，长度为串中空格字符的个数。女口：' , C= ' BEI JING '子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A= ' BEIJING ' B= ' JING '字

55、符在串中的位置：字符在序列中的序号。子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。女口： A= ' BEIJING B= ' JING B 在 A 中的 位置为 4。串相等：当且仅当两个串的值相等。也就是说，只有两个串的长度相等 且各个对应位置的字符都相等时才相等。（2 ）串的抽象数据类型定义：ADT Stri ng 数据对象：D = ai |ai CharacterSet, i=1,2,.,n, nn 0 数据关系：R1 = < ai-1, ai > | ai-1, ai D, i=2,.,n 基本操作：（见教材P71 ） ADT Stri ng通过

56、基本操作可以实现更复杂的操作。如通过判等、求串长和求子串等操 作可以实现定位函数Index。4.2 串的表示和实现4.2.1 定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存 储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的 上界预先给出：#define MAXSTRLEN 255用 户可在255以内定义最大串长typedef unsigned charSStringMAXSTRLEN + 1;/ 0 号单元存放串的长度特点：串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的 串值则被舍去，称之为截断”。按这种串的表示方法实现的串的运算时，其基本操作为字符序列的复制” （通过串联接和求子串来讲解）422 堆分配存储表示以一组地址连续的存储单元存储串值的字符序列，存储空间在程序执行过 程中动态分配。C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc() 和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称 串值共享的存储空间为堆”C语言中的串以一个