数据结构授课教案-第2章.doc

山东轻工业学院教师授课教案课程名称:数据结构(计科)课程代码:学分::必修开课单位:信息科学与技术学院授课班级:授课教师:杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第二章线性表第一节线性表的类型定义线性表的逻辑结构定义和抽象数据类型定义。第二节线性表的顺序表示和实现顺序表的类型定义、查找、插入和删除。第三节线性表的链式表示和实现线性链表(单链表)的结构、类型定义、查找、插入和删除;带头结点的单链表;循环链表的结构,循环链表与单链表操作的区别;双向链表的结构、类型定义、插入和删除。目的要求目的:理解线性表的定义和实现。基本要求:了解线性表的逻辑结构和基本操作;理解循环链表和双向链表的概念和基本算法;掌握线性表的顺序存储结构及基本操作的实现、线性表的链式存储结构及基本操作的实现。重点顺序表的定义、查找、插入和删除;单链表的定义、查找、插入和删除,头结点的作用;循环链表的定义,循环链表的操作和单链表操作的区别;双向链表的定义、插入和删除。难点单链表的定义、插入和删除;带头结点和不带头结点的单链表的基本操作的区别。(C语言版),严蔚敏,清华大学出版社,2002。、算法与应用-C++语言描述,(美)SartajSahni著,汪诗林等译,***出版社,2002。课型理论课学时分配复****分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共8学时,包括2学时的****题课。注:课型一栏填写理论课、实验课****题课等授课内容备注第二章线性表线性结构的特点:在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素;存在唯一的一个被称做“最后一个”的数据元素;除第一个之外,每个元素都只有一个前驱;除最后一个之外,每个元素都只有一个后继。,它是一种线性结构。线性表是n(n>=0)个数据元素的有限序列,通常记为: (a1,a2,…ai-1,ai,ai+1,…an) 其中:同一线性表中的数据元素必须具有相同数据类型,ai是线性表的第i个元素,称i为数据元素ai的序号相邻数据元素间存在序偶关系:将ai-1称为ai的直接前趋,ai+1称为ai的直接后继。a1是表中第一个元素,它没有前趋;an是最后一个元素无后继;其余有且仅有一个直接前趋,有且仅有一个直接后继n为表长,n=0时称为空表()。线性表的数据元素,或者叫结点,或者叫记录,是独立的信息。它可以是一个数:例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为:(6,17,28,50,92,188)或一个符号,如英文字母表(A,B,…,Z);也可以由若干个数据项组成:如:学生健康情况登记表如下:线性表的其他表示方式:1)二元组表示L=<D,S>, 其中:D={a1,a2,a3,...an};S={R}R={<a1,a2>,<a2,a3>,<a3,a4>…<an-1,an>}2)图示表示线性表的基本操作:表的初始化存取操作:存、取线性表中第i个数据元素查找操作:在线性表中查找满足条件元素插入操作:在线性表的第i个元素之前插入删除操作:删除线性表的第i个元素遍历求表长说明: 1)上面列出的操作,只是线性表的一些常用的基本操作;2)线性表的复杂操作可通过基本操作实现;:指的是用一组地址连续的存储单元依次存储线性表的数据元素,用物理上的相邻表示逻辑上的相邻。说明:在顺序存储结构下,线性表元素之间的逻辑关系,通过元素的存储顺序反映(表示)出来;假设线性表中每个数据元素占用t个存储单元,那么,在顺序存储结构中,线性表的第i个元素的存储位置与第1个元素的存储位置的关系是: Loc(ai+1)=Loc(ai)+t Loc(ai)=Loc(a1)+(i–1)t顺序表特点:可随机存取一、顺序表的类型定义:几种方法:1)#defineListSize100typedefintElemType;ElemTypeList[ListSize];intlength;2)#defineListSize100typedefintElemType;ElemTypeList[ListSize];intlength;3)#defineListSize100typedefintElemType;typedefstruct{ ElemTypedata[ListSize]; intlength;}SqList;4)#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typedefstruct{ ElemType*elem; intleng