数据结构教案C语言版.doc
课程教案 课程名称 数据结构 授课教师 学习对象 任课时间 一、 学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了 C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、 课程教学目标 数据结构是计算机 学科 中一门 核心 专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地 理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章 绪论 教学内容 1) 什么是数据结构 2) 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3) 数据结构的抽象层次 4) 算法定义 5)性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求 了解数据结构基本概念及数据结构的抽象层次 了解抽象数据类型概念 了解算法的定义及算法特性 掌握算法的性能分析与度量方法 第二章 线性表 教学内容 1) 线性表的定义和特点 2) 线性表的顺序存储及查找、插入和删除操作 3) 线性表的链式存储及查找、插入和删除操作 4) 使用线性表的实例 教学要求 了解线性表的定义和特点 熟练掌握线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握单链表、循环链表及双向链表的定义及实现 掌握熟练掌握单链表的应用方法 第三章 栈和队列 教学内容 1) 栈栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表 示 2) 队列队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 3) 队列的应用举例 教学要求 熟练掌握栈的定义及实现 熟练掌握队列的定义及实现 掌握能运用栈和队列解决简单实际问题 第四章 串 教学 内容 1 字符串的抽象数据类型 2 字符串操作的实现 3 字符串的模式匹配 教学要求 熟练掌握字符串的定义方式 熟练掌握字符串的各种操作的实现 了解字符串的模式匹配算法 第五章 数组和广义表 教学 内容 1 数组的定义和初始化 2 作为抽象数据类型的数组的顺序存储方式 教学要求 了解作为抽象数据类型的数组的定义 熟练掌握 顺序表的数组定义方式及实现 第六章 树和二叉树 教学内容 1 树和森林的概念树的定义；树的术语；树的抽象数据类型；森林的概念 2 二叉树二叉树的定义；二叉树的性质；二叉树的抽象数据类型 3 二叉树的表示数组表示；链表存储表示 4 二叉树的遍历中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法 5 线索化二叉树线索；中序线索化二叉树；前序与后序的线索化 6 树与森林树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历 7 二叉树的计数 8 霍夫曼树路径长度；霍夫曼树；霍夫曼树编码 教学要求 了解树和森林 的概念 掌握二叉树的概念、性质及二叉树的表示 熟练掌握二叉树的遍历方法 掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握树和森林的实现及遍历方法 掌握二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握霍夫曼树的实现方法及霍夫曼编码的概念 第七章 图 教学内容 1)图的基本概念图的基本概念；图的抽象数据类型 2)图的存储表示邻接矩阵；邻接表；邻接多重表 3)图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量 4)最小生成树克鲁斯卡尔算法；普里姆算法 教学要求 掌握图的基本概 念和图的存储表示 熟练掌握图的两种遍历方法与求解连通性问题的方法 掌握构造最小生成树的 Prim 和 Kruskal 方法 第 九 章 查找 教学内容 1 静态查找表顺序表的查找；有序表的查找；索引顺序表的查找 2 二叉排序树二叉排序树上的搜索、插入和删除 教学要求 熟练掌握静态搜索表的顺序搜索和折半搜索方法 熟练掌握二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 第十章 内部排序 教学内容 1 概述 2 插入排序直接插入排序；对分插入排序；链表插入排序；希尔排序 3 选择排序直接选择排序；堆排序 教学要求 掌握排序的基本概念和性能分析方法 掌握插入排序、选择排序、等内排序的方法及性能分析方法 单元名称第 一 讲绪论 一、教学目标 1.了解数据结构课程的体系结构 2.掌握 本章介绍的各种基本概念和术语 3.了解数据结构的二元组表示 4.掌握 逻辑结构与物理结构之间的映像关系。 二 、重点与难点 重点数据结构的基本概念；逻辑结构与物理结构之间的映像关系。 难点逻辑结构与物理结构之间的映像关系。 三 、 教学内容与 教学过程 介绍本学期课程的内容及安排 本课程是计算 机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。 成绩考核方式为期末成绩 平时成绩，其中期末成绩占 70，平时成绩占 30，平时成绩为作业成绩 出勤率 上机成绩。 讲授新课 1.1 什么是数据结构 讲解( 数据结构课程的研究背景 ) 从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。 讲解( 数据结构课程的研究对象 ) 例 1-1 图书馆的书目检索系统自动化问题。 1-2 计算机和人机对奕问题 1-3 多叉路口交通灯的管理 问题 总结 从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而 是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 介绍数据结构课程的 发展以及 与其他课程之间的关系。 1.2 基本概念和术语 基本概念数据、数据元素、数据项、数据对象、数据结构、结构 ( 1)常见基本结构(逻辑结构)集合、线性结构、树形结构、图状结构或网状结构 数据结构的形式定义 数据 结构一般用一个二元组来表示 Data_StructureD,S 其中 D 是数据元素的有限集， S 是 D 上的关系的有限集 DS 表示一种数据结构，它由数据元素集合 K 和在 K 上定义的一种二元关系的集合 R 所组成。其中 0,0| nniKK i 是数据元素的有限集合， n 为 DS 中数据元素的个数。 0,0| mmjRR j 是 K 上关系的有限集合， m 为 K 上关系的个数，通常情况下 m的取值为 1。 K 上 任何一个二元关系 Rj 是序偶的集合。对于 Rj 中的任一序偶 ( x， yK)，称 x为第一个元素(或 y 的前驱)， y 为第二个元素(或 x 的后继)。 数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。 举例讲解 例 数据结构 lineK， R，其中 K01， 02， 03， 04， 05， 06， 07， 08， 09， 10， Rr，r， ， ,， ， ， ， ，。 例数据结构 treeK， R，其中 K01， 02， 03， 04， 05， 06， 07， 08， 09， 10， Rr，r， ， ， ， ， ， ， ，。 例 数据结构 graphK， R，其中 K01， 02， 03， 04， 05， Rr， r， ， ， ， ， ， ， ， ， 。 介绍常见数据结构(集合、 线性结构、 树 型结构 、图 型结构 )具体表示方式 2 逻辑结构 上述数据结构的定义是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的 “关系 ”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和 图型结构。 3 物理结构 数据结构在计算机中的表示(存储映象)称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 注意 数据的逻辑结构和物理结构是密切相关的两个方面，任 何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。 ( 4)数据结构一般包括三方面内容 数据的逻辑结构、数据的存储结构、数据的运算 (举例讲解) 小结 总结本讲的主要内容 四 、作业布置 见习题集 单元名称第 二 讲 线性表的类型定义，线性表的顺序 存储 一、教学目标 掌握 线性表的顺序表示和实现 二 、重点与难点 线性表的顺序表示和实现。 三 、教学过程的具体安排 讲授新课 2.1 线性表的 类型定义 线性表的定义一个线性表是 n 个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如 26 个英文字母表；学生健康情况登记表(图 2.1)等。 例如线性表( a1, ,ai-1,ai,ai1, ,an)，称 ai-1 是 ai的直接前驱元素， ai1 是 ai的直接后继。 引导学生自己总结线性结构的特点。 线性表的长度线性表中元素的个数( n 0)， n0 为空表。 线性表中数据元素的位序(如数据元素 ai在线性表中的位 序为 i)。 抽象数据类型线性表的定义 讲解定义中的数据对象，数据关系以及基本操作(教材 P19)，重点讲解常用的基本操作含义。 通过示例 2-1， 2-2 讲解更复杂的基本操作，并分析时间复杂度。 2.2 线性表的顺序表示和实现 ( 1)线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。 ( 2)顺序储存的地址关系假设线性表的每个元素需占用 l 个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 i1个数据元素的存储位置 LOC a i 1和第 i 个数据元素的存储位置 LOCa i之间满足下列关系 LOCa i 1LOCa il 线性表的第 i 个数据元素 ai 的存储位置为 LOCa iLOCa 1i-1*l，其中 LOCa1为线性表的基地址。 ( 3)顺序表及其特点 , 顺序储存结构是一种随机存取的存储结构。 ( 4)线性表的动态分配顺序存储结构。 define LIST_INIT_SIZE 100 define LISTINCREMENT 10 Typedef struct ElemType *elem; int length; int listsize; SqList; 1 基于顺序存储结构的基本操作的实现 主要介绍下面的基本操作并且分析时间复杂度。 InitList_SqSqList ListInsert_SqSqList ListDelete_SqSqList LocateElem_SqSqList L, ElemType e, Status *compareElemType, ElemType;MergeList_SqSqList La,SqList Lb, SqList 重点讲解 顺序存储结构上实现线性表的插入操作 设线性表 niii aaaaaaA , 1121 ，为了保证线性表的有序性，当在位置 i 11 ni 之前插入一个新的数据元素 x 时，需要将第 i 个到第 n 个数据元素均向后移动一个位置，然后将数据元素 x 存储到第 i 个位置上并改变线性表的长度。 Status ListInsert_SqSqList 插入位置不合法 if L.length L.listsize 当前存储空间已满，增加分配 newbase ElemType *reallocL.elem, L.listsizeLISTINCREMENT*sizeof ElemType; if newbase exitOVERFLOW; 存储分配失败 L.elem newbase; 新基址 L.listsize LISTINCREMENT; 增加存储容量 q q 指示插入位置 for p p q; p *p1 *p; 插入位置及之后的元素右移 *q e; 插入 e L.length; 表长 增 1 return OK; ListInsert_Sq 平均时间复杂度分析 2/1/210 nOnnnnf 顺序存储结构上实现线性表的删除操作 设线性表 niii aaaaaaA , 1121 ，为了保证线性表的有序性 ,当删除第 1 nii 个位置上的元素后，需要将第 i1 个到第 n 个数据元素均向前移动一个位置并改变线性表的长度。 Status ListDelete_SqSqList 删除位置不合法 p p 为被删除元素的位置 e *p; 被删除元素的值赋给 e q L.elemL.length-1; 表尾元素的位置 for p; p next NULL; 先建立一个带头结点的单链表 for i n; i 0; i p LinkList malloc sizeof LNode; 生成新结点 scanf 输入元素值 p-next L-next; L-next p; 插入到表头 CreateList_L 注 从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。 2 建立单链表(要求从尾部插入) void CreateList_LLinkList r L; L-next NULL; 先建立一个带头结点的单链表 for i n; i 0; i p LinkList malloc sizeof LNode; 生成新结点 scanf 输入元素值 p-nextr-next; r-nextp; r p; 插入到表尾 CreateList_L 3 在带头结点的单链表中插入结点 分析设在结点 a 和结点 b 之间插入数据为 x 的结点， 通过图来分析 则插入前和插入后的情况。 Status ListInsert_LLinkList L, int i, ElemType e 在带头结头的单链表 L 中第 i 位置之前插入元素 e p L; j 0; while p 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 在带头结点的单链表中删除结点 Status ListDelete_LLinkList L, int i, ElemType j 0; while p-next j; 寻找第 i 个结点并令 p 指向其前趋 if p-next j i-1 return ERROR; 删除位置不合理 q p-next; p-next q-next; 删除并释放结点 e q-data; freeq; return OK; ListDelete_L 注 上述两个算法的时间复杂度均为 On。 单链表的优点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 插入、删除操作方便 单链表的缺点 指针占用额外存储空间 不能随机存取，查找速度慢 小结 本讲主要介绍了 单 链 表的 存储结构，以及的基本操作(建立、插入和删除) 的实现。 四 、作业布置 见习题集 实验作业见实验指导。 第 四 讲 循环链表，双向链表， 链表应用 一、教学目标 1了解循环链表和的基本概念； 2掌握双向链表的插入和删除操作； 3掌握一元多项式的表示及加法在链式存储结构上的实 现。 二 、重点与难点 双向链表的存储结构和基本操作实现 。 三 、 教学内容与 教学过程 讲授新课 单向循环链表 设指针 p 指向单向链表中最后一个结点，则 p-next 的值是 0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线 性链表为单向循环链表。设 p 指向单向循环链表中的最后一个结点，则 p-next 的值不是 0 而是等于指向循环链表中的第一个结点 head的值。 双向链表 如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下 typedef struct DuLNode ElemType data; 数据域 struct DuLNode *prior; 指向前驱的指针域 struct DuLNode *next; 指向后继 的指针域 DuLNode, *DuLinkList; 设指针 p 指向双向链表中的某个结点，则显然有以下的结论 p-prior-nextpp-next-prior 1 双向链表的插入操作 设指针变量 p 指向双向链表中的结点 A，指针变量 q 指向被插入的新结点 B，则在结点 A的后面插入结点 B 的操作序列为 1 q-nextp-next； 2 p-next-priorq； 3 p-nextq； 4 q-priorp； 2 双向链表的删除操作 设指针变量 p 指向双向链表中被删除的结点 X，则删除结点 X 的操作序列为 1 p-prior-nextp-next； 2 p-next-priorp-prior； 3 freep； 注 在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指针域的操作次序，以免丢失链域信息而造成链表中断的错误。 链式存储结构的应用 一元多项式的表示及相加 一元多项式 nPx可按升幂写成 20 1 2 nnnP x P P x P x P x 它由 n1 个系数唯一确定。在计算机中，可用一个线性表 P 来表示 0 1 2 , , , , nP P P P P 每项系数 i 隐含在系数 iP 的序号里。 若 mQx为一个一元多项式，同样用线性表 Q 表示 0 1 2 , , , , mQ Q Q Q Q 这两个多项式可以相加，结果为 n n mR x P x Q x，其中设 nm ，则用 线性表表示 R 为 0 0 1 1 2 2 1 , , , , , , , m m m nR P Q P Q P Q P Q P P 我们可以采用顺序存储结构存放 P、 Q 和 R，使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如 Sx13x100012x20000 的多项式时，要用长度为 20001 的线性表来表示。如果 对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成 0 0 1 1 2 2 , , , , , , , , nnP P e P e P e P e 因此上式 Sx可表示成 1, 0 ,3, 1001, 2, 20000 。显然这样的线性表应采用链式存储结构。课本 P41 图 2.17 中两个线性链表分别表示一元多项式 Ax73x9x85x11 和一元 多项式Bx8x22x7-9x8，由这两个多项式得到的和多项式如图课本 P412.18 所示。 用链表表示多项式时，链表中的数据类型描述成 typedef struct polynomial float coef; int expn ; struct polynomial *next; ElemType; 根据一元多项式相加的运算规则对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项则分别抄到和多项式中去。 第一步 分别从 A 表和 B 表的表头开始，根据比较 pa-expn 和 pb-expn 的比较结果分三种情况讨论，直到 A 表或 B 表全部处理完。 1 pa-expnpb-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 表中；反之则将 A 表中剩余结点复制到 C 表中。 void create_itemLinkList p-coefcoef; p-expnexpn; pc-nextp; pcp; void ploy_addLinkList pah,LinkList pbh,LinkList pb pbh; pc pchLinkList *mallocsizeofLNode; 为 c 链表添加一个头结点 whilepa0 ifx0 create_itempc,x,pa-expn; papa-next; pbpb-next; else ifpa-expnpb-expn create_itempc,pa-coef,pa-expn; papa-next; else create_itempc,pb-coef,pb-expn; pbpb-next; while pa0 create_itempc,pa-coef,pa-expn; papa-next; while pb0 create_itempc,pb-coef,pb-expn; pbpb-next; pc-next0; pcpch; pchpch-next; freepc; /* 释放 c 链中的头结点 */ 小结 本讲主要介绍了循环链表和双向链表的基本概念，双向链表的插入和删除操作， 一元多项式的表示及相加在链式存储结构上的实现 。 四 、作业布置 见习题集 实验作业见实验指导。 单元名称第 五 讲栈 一、教学目标 1 了解栈的基本概念和基本操作； 2掌握栈的基本操作在两种存 储结构上的实现。 二、重点与难点 栈的基本操作在两种存储结构上实现 。 三、教学内容与教学过程 首先复习线性表的知识，引入限定性的数据结构栈和队列。 讲授新课 3.1 栈 3.1.1 抽象数据类型栈的定义 栈限定仅在表尾进行插入或删除操作的线性表，表尾 栈顶，表头 栈底，不含元素的空表称空栈。 通过教材 P44 的图 3.1 讲解栈顶，栈底以及栈后进先出的特点。 栈的抽象数据类型定义 ADT Stack 数据对象 D ai | ai ElemSet, i1,2,.,n, n 0 数据关系 R1 | ai-1, ai D, i2,.,n 约定 an 端为栈顶，a1 端为栈底。 基本操作 InitStack define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 顺序栈的基本操作的算法描述 初始化，返回栈顶元素，入栈，出栈。 a 栈空栈满条件 栈空条件 topbase 栈满条件 base-topstacksize b 入栈操作 Status Push SqStack ifS.base exitOVERFLOW; S.topS.baseS.stacksize; S.stacksizeSTACKINCREMENT; *S.top e; return OK; c 出栈操作 Status Pop SqStack e*S.top; return OK; 链栈栈的链式存储结构。栈顶指针就是链表的头指针 栈的链式存储结构类似单链表的存储结构，链表中第一个结点表示栈顶，最后一个结点表示栈底。由于链表的长度可以动态增长，因此进行入栈操作时无需考虑栈的上溢，但进行出栈操作时，必需考虑栈的 下溢，下溢的条件是 top 的值为 0。 链式栈的入栈操作 Status PushLinkList p-datax; p-nexttop; topp; return OK; 2 链式栈的出栈操作 Status PopLinkStack ptop; yp-data; topp-next; freep; return OK; 小结； 本讲主要介绍了栈的基本概念，栈的基本运算，栈在顺序存储结构和链式存储结构上实现基本操作。 四、作业布置 见习题集 实验作业见实验指导。 单元名称第 六 讲队列 一、教学目标 1 了解栈的基本概念和基本操作； 2掌握栈的基本操作在两种存储结构上的实现。 二、重点与难点 栈的基本操作在两种存储结构上实现 。 三、教学内容与教学过程 讲授新课 队列的基本概念 队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另 一端进行的特殊线性表。允许插入(入队)操作的一端称为 队尾 ，允许删除(出队)操作的一端称为 队头 。 设队列为 12 , , , nq a a a ，则 1a 是队头元素， na 是队尾元素。队列中的元素按照12, , , na a a 的顺序进入队列的，退出队列也只能按照这个次序依次退出，即只有在1 2 1, , , na a a 都退出队列后， na 才能退出队列。因此队列也称为先进先出( FIFO)的线性表。 2、队列的基本操作 InitQueue int front; int rear; SqQueue; b 顺序循环队列的入队列操作 status EnQueueSqQueue Q.baseQ.reare; Q.rearQ.rear1MAXSIZE; return OK; c 顺序循环队列的出队列操作 status DeQueueSqQueue e Q.baseQ.front; Q.front Q.front1MAXSIZE; return OK; 4、队列的链式存储结构 队列的链式存储结构实际上是一个同时带有头指针和尾指针的单向链表，头指针指向队头元 素，尾指针指向队尾元素。为了操作方便起见，给链式队列添加一个头结点。空的链式队列的判断条件为头指针和尾指针都指向头结点。 a 链式循环队列的类型描述 typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; 队头指针 QueuePtr rear; 队尾指针 LinkQueue; b 链式队列的入队列操作 stutus EnQueueLinkQueue ifpexitOVERFLOW; p-datae; p-nextNULL; Q.rear-nextp; Q.rearp; return OK; c 链式队列的出队列操作。 status DeQueue LinkQueue pQ.front-next; ep-data; Q.front-nextp-next; ifQ.rearpQ.rearQ.front; freep; return OK; 注意 当 队列中最后一个元素被删除后，队列尾指针也丢失了，因此需要对队尾指针重新赋值。 小结 主讲主要介绍了队列的基本概念和基本操作，以及队列的基本操作在顺序存储结构和链式存储结构上的实现。 四、作业布置 见习题集 实验作业见实验指导。 单元名称第 七 讲串 一、教学目标 1.熟悉串的定义以及基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。 2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3.掌握串的堆分配存储结构以及在其上实现串操作的基本方法。 4.了解串的块链存储结构 二、重点与难点 串的存储结构以及基本操作的实现。 三、教学内容与教学过程 讲授新课 4.1 串类型的定义 ( 1)基本概念 串( string)由零个或多个字符组成的有限序列，也称字符串。记为 S a1a2a3an n 0 如 A BEIJING， B JING 串的长度串中字符的数目 n 。 空串不含任何字符的串，串长度为 0， 空格串仅由一个或多个空格组成的串，长度为串中空格字符的个数。 如 ， C BEI JING 子串由串中任意个连续的字符组成的子序列。 主串包含子串的串。如 A BEIJING B JING 字符在串中的位置字符在序列中的序号。 子串在主串中的位置以子串的第一个字符在主串中的位置来表示。 如 A BEIJING ， B JING ， B 在 A 中的位置为 4。 串相等当且仅当两个串的值相等。也就是说，只有两个串的长度相等且各个对应位置的字符都相等时才相等。 ( 2)串的抽象数据类型定义 ADT String 数据对象 D ai |ai CharacterSet, i1,2,.,n, n 0 数据关系 R1 | ai-1, ai D, i2,.,n 基本操作(见教材 P71) ADT String 通过基本操作可以实现更复杂的操作。 如通过判等、求串长和求子串等操作可以实现定位函数 Index。 4.2 串的表示和实现 4.2.1 定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出 define MAXSTRLEN 255 用户可在 255 以内定义最大串长 typedef unsigned char SStringMAXSTRLEN 1; 0 号单元存放串的长度 特 点 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为 “截断 ” 。 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制 ”(通过串联接和求子串来讲解)。 4.2.2 堆分配存储表示 以一组地址连续的存储单元存储串值的字符序列，存储空间在程序执行过程中动态分配。 C 语言中提供的串类型就是以这种存储方式实现的。系统利用函数 malloc和 free 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为 “堆 ”。 C 语言中 的串以一个空字符为结束符，串长是一个隐含值。 串堆分配存储表示 typedef struct char *ch; 若是非空串，则按串长分配存储区 ,否则 ch 为 NULL int length; 串长度 HString; 这类串操作实现的算法为先为新生成的串分配一个存储空间，然后进行串值的复制(以串的复制操作为例)。 讲解串堆分配的表示与实现 ( P76， 77) 4.2.3 块链存储表示 以链表存储串值，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长 度。称如此定义的传存储结构为块链结构。 define CHUNKSIZE 80 可由用户定义的块大小 typedef struct Chunk 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct 串的链表结构 Chunk *head, *tail; 串的头和尾指针 int curlen; 串的当前长度 LString; 讲解块链存储表 示在串处理系统中的应用。 小结 总结本讲的主要内容 四、作业布置 见习题集 实验作业见实验指导。 单元名称第九讲 数 组 一、教学目标 1.熟悉数组的定义。 2.掌握数组的顺序表示和基本操作的实现。 3.掌握特殊矩阵的压缩存储和稀疏矩阵三元组顺序表存储。 4.了解稀疏矩阵的行逻辑链接的顺序表和十字链表表示储存 二、重点与难点 数组的压缩存储。 三、教学内容与教学过程 讲授新课 5.1 数组的定义 数组的抽象数据类型定义 ADT Array 数据对象 数据关系 基本 操作 ADT Array 数组 是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组 可以看成是线性表的线性表。 举例 对于数组的操作一般只有两类(与线性表对比讲解) ( 1)获得特定位置的元素值； ( 2)修改特定位置的元素值。 5.2 数组的顺序表示和实现 对于数组 A，一旦给定其维数 n 及各维长度 bi( 1 i n)，则该数组中元素的个数是固 定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。 数组的顺序存储结构有两种一种是按行序存储， 如高级语言 BASIC、COBOL 和 PASCAL 语言都是以行序为主。另一种是按列序存储，如高级语言中的FORTRAN 语言就是以列序为主。 以二维数组为例，假设每个元素只占 L 个存储单元， “以行为主 ”存放数组，下标从 0 开始，首元素 a00 的地址为 Loc0,0
