《数据结构》教案15929

《《数据结构》教案15929》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》教案15929读过一本好书，像交了一个益友。——藏克家《数据结构》教案广西民族大学数学与计算机学院　　课程名称：数据结构任课教师总课序授课时间撰写（修改）讲课内容　2.1-2.2课型（教法）多媒体讲授课题线性表的逻辑结构及运算线性表的顺序存储及其运算实现教具准备教学目的掌握线性表的逻辑结构及运算，线性表的顺序存储结构及其运算的实现教学重点线性表的逻辑结构及运算线性表的顺序存储结构及其运算的实现教学难点与关键线性表的顺序存储结构及其运算教学内容纲要：　　第2章线性表线性结构的特点2.1线性表的类型定义1.线性表的定义（a1,...,ai-1,ai,ai+1,

2、...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(a

3、i)=LOC(a1)+(i-1)*l　　2、顺序表的特点：随机存取　　3、线性表的动态分配顺序存储结构（用一维数组）　　#defineLIST_INIT_SIZE100　　#defineLISTINCREAMENT10　　typedefstruct{　　ElemType*elem;　　intlength;　　intlistsize;　　}SqList;　　4、顺序表的运算　　顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。　　⑴初始化操作　　⑵插入操作　　(3)删除操作　　课程名称：数据结构任课教师总课序授课时间撰写（修改）讲课内容2.3.1节

4、课型（教法）多媒体讲授课题单链表存储及其运算教具准备教学目的　掌握单链表存储结构及运算的实现。教学重点　建立单链表及实现结点的插入和删除等基本运算教学难点与关键　关键：单链表存储结构定义　难点：基本运算的实现教学内容纲要：2.3线性表的链式表示和实现2.3.1线性链表1、线性表的链式存储结构的特点相关概念：结点（Node）、数据域、指针域、指针、链、头指针2、链式存储结构的优点：插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。链表的分类单链表、循环链表和双向链表。3.单链表：(1)单链表概念：链表中的每一个结点中只包含一个指针域的称为单链表或线

5、性链表。(2)单链表的存储结构定义typedefstrucLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;(3)单链表的操作：*访问：算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。*插入操作：要在数据元素a和b之间插入元素x。算法思想：决定a和b之间的相邻关系是由a的指针决定的。若要实现插入，生成x结点，然后让a的指针指向x且x的指针指向b。实现三个元a、x和b

6、的逻辑关系。设p为指向结点a的指针，s为指向结点x的指针，则修改s、a的指针：s→next=p→next；p→next=s；*删除操作：在单链表数据元素a、b、c三个相邻的元素中删除b，算法思想：就是要让a的指针直接指向c，使b从链表中脱离。即，p→next=p→next→next*单链表的合并：读过一本好书，像交了一个益友。——藏克家例：将两个有序链表合并为一个有序链表。设立三个指针pa、pb和pc分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到合并表中，即，让合并表的当前指针指向该元素，然后，修改指针。在归并两个链表为一个链

7、表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。　　课程名称：数据结构任课教师总课序授课时间撰写（修改）讲课内容2.3.2-2.3.3课型（教法）多媒体讲授课题循环链表、双向链表、静态链表教具准备教学目的掌握循环链表、双链表及静态链表存储结构及其运算实现教学重点循环链表及双链表存储结构及其运算实现教学难点与关键循环链表、双向链表的相关运算教学内容纲要：2.3.2循环链表1、循环链表：特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表可分为单链和多链的。2、循环链表的操作：和线性链表基本一致，