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

山东轻工业学院 教师授课教案 课程名称： 数据结构（计科） 课程代码： 0301306 学 分： 4.5 课程类别： 必修 开课单位: 信息科学与技术学院 授课班级： 授课教师： 杨春花 山东轻工业学院教务处制 授课时间 年 月 日 星期 第 节 年 月 日 星期 第 节 年 月 日 星期 第 节 授课内容概要 第二章 线性表 第一节 线性表的类型定义 线性表的逻辑结构定义和抽象数据类型定义。 第二节 线性表的顺序表示和实现 顺序表的类型定义、查找、插入和删除。 第三节 线性表的链式表示和实现 线性链表循环链表循环链表双向链表基本：了解线性表的逻辑结构和基本操作；循环链表和双向链表的概念和基本线性表的顺序存储结构线性表的链式存储结构实现顺序表的；单链表的循环链表循环链表单链表双向链表的单链表的单链表 线性结构的特点： 在数据元素的非空有限集中 存在唯一的一个被称做“第一个”的数据元素； 存在唯一的一个被称做“最后一个”的数据元素； 除第一个之外，每个元素都只有一个前驱； 除最后一个之外，每个元素都只有一个后继。 2.1 线性表的逻辑结构 线性表是一种最简单的数据结构，它是一种线性结构。 线性表是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)线性表的复杂操作可通过基本操作实现； 2.2 线性表的顺序存储和实现 线性表的顺序存储结构: 指的是用一组地址连续的存储单元依次存储线性表的数据元素，用物理上的相邻表示逻辑上的相邻。 说明： 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来； 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai+1 ) = Loc( ai )+ t Loc(ai ) = Loc(a1 )+ ( i – 1) t 顺序表特点：可随机存取 一、顺序表的类型定义： 几种方法： 1) # define ListSize 100 typedef int ElemType; ElemType List[ListSize]; int length; 2) # define ListSize 100 typedef int ElemType; ElemType List[ListSize]; int length; 3) # define ListSize 100 typedef int ElemType; typedef struct{ ElemType data[ListSize]; int length; }SqList; 4) #define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10 typedef struct{ ElemType *elem; int length; int listsize; }SqList 二、顺序表上的基本操作 插入 功能：在顺序表v 中的第 i ( 1=i=n+1)个