《数据结构》教案

艺术的大道上荆棘丛生，这也是好事，常人望而却步，只有意志坚强的人例外。——雨果





《数据结构》教案







广西民族大学数学与计算机学院


　　课程名称：数据结构任 课 教 师总课序授 课
时 间撰写（修改）讲 课 内 容　2.1-2.2课 型
（教法）多媒体讲授课 题线性表的逻辑结构及运算
线性表的顺序存储及其运算实现教 具
准 备教 学
目 的掌握线性表的逻辑结构及运算，线性表的顺序存储结构及其运算的实现教 学
重 点线性表的逻辑结构及运算
线性表的顺序存储结构及其运算的实现教 学
难 点
与关键线性表的顺序存储结构及其运算
教学内容纲要：

　　第2章 线 性 表
线性结构的特点
2.1 线性表的类型定义
1. 线性表的定义
（a1,...,ai-1,ai,ai+1,...an）
2. 定义在逻辑结构上的运算
表的初始化、求表长、取表中的结点、查找结点、插入结点和删除结点等
3. 抽象数据类型线性表的定义


　　
　　例1：扩大线性表LA，将存在于线性表LB中而不在LA中的数据元素加入到线性表LA中。
　　算法思想：逐一取出LB中的元素，判断是否在LA中，若不在，则插之。
　　例2： 线性表LA和LB是非递减的，将两表合并成新的线性表LC，且LC也是非递减的。
　　2.2 线性表的顺序表示和实现
　　1、线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。用物理位置来表示逻辑结构。
　　LOC(ai+1)=LOC(ai)+l
　　LOC(ai)=LOC(a1)+(i-1)*l
　　2、顺序表的特点：随机存取
　　3、线性表的动态分配顺序存储结构（用一维数组）
　　#define LIST_INIT_SIZE 100
　　#define LISTINCREAMENT 10
　　typedef struct{
　　ElemType *elem;
　　int length;
　　int listsize;
　　}SqList;
　　4、 顺序表的运算
　　顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。
　　⑴初始化操作
　　⑵插入操作