《数据结构》教案

更新时间:2023-06-09 19:11:01 阅读量: 实用文档 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

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





《数据结构》教案







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


  课程名称:数据结构任 课 教 师总课序授 课
时 间撰写(修改)讲 课 内 容 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、 顺序表的运算
  顺序表容易实现访问操作,可随机存取元素。但插入和删除操作主要是移动元素。
  ⑴初始化操作
  ⑵插入操作
 

 (3)删除操作


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


(2)单链表的存储结构定义
typedef struc LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
(3)单链表的操作:
* 访问:
算法思想:单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中,所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点,然后,让该指针变量逐一向后指向,直到第i个元素。
* 插入操作:要在数据元素a和b 之间插入元素x。
算法思想:决定a和b之间的相邻关系是由a 的指针决定的。若要实现插入,生成x结点,然后让a 的指针指向x 且x 的指针指向b。实现三个元a、x和b的逻辑关系。
设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 分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小,将小的元素链接到合并表中,即,让合
并表的当前指针指向该元素,然后,修改指针。在归并两个链表为一个链表时,不需要另建新表的结点空间,而只需将原来两个链表中结点之间的关系解除,重新建立关系。




  课程名称:数据结构任 课 教 师总课序授 课
时 间撰写(修改)讲 课 内 容2.

3.2-2.3.3课 型
(教法)多媒体讲授课 题循环链表、双向链表、静态链表教 具
准 备教 学
目 的掌握循环链表、双链表及静态链表存储结构及其运算实现教 学
重 点循环链表及双链表存储结构及其运算实现教 学
难 点
与关键循环链表、双向链表的相关运算
教学内容纲要:

2.3.2 循环链表
1、循环链表:
特点:表中最后一个结点的指针域指向头结点,整个链表形成一个环。
循环链表可分为单链和多链的。
2、循环链表的操作:
和线性链表基本一致,差别仅在于循环条件判定是否为空改为是否为头指针。
2.3.3 双向链表
1、双向链表:
特点:在双向链表的结点中有两个指针域,分别指向前驱和后继。
双向链表也可以有循环链表。




2、双向链表存储结构定义:
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinklist;
3、双向链表的操作:
双指针使得链表的双向查找更为方便、快捷。NextElem和PriorElem的执行时间为O(1)。
仅需涉及一个方向的指针的操作和线性链表的操作相同。
插入和删除需同时修改两个方向的指针。
4、双向链表的插入操作
1)p-->next = q
2)p-->prior =q-->prior
3)q-->prior-->next = p
4)q-->prior =p
2.3.4 静态单链表
1.特点:
用数组描述的链表称为静态链表。
2.存储结构定义:
#define MAXSIZE 1000
typedef struct{
ElemType data;
int cur;
}component, SLinklist[MAXSIZE];
3.运算实现
静态链表的操作和动态链表相似。以整型游标代替动态指针。


  课程名称:数据结构任 课 教 师总课序授 课
时 间撰写(修改)讲 课 内 容实验1课 型
(教法)多媒体讲授课 题 单链表的建立及相关操作教 具
准 备教 学
目 的 掌握c上机调试的基本方法。
了解单链表的结构特点及相关概念,
掌握单链表结点链接等相关知识。教 学
重 点 单链表的建立及相关操作教 学
难 点
与关键 单链表的建立教学内容纲要:

[实验要求]
  1、建立一个单
链表。
  2、并在指定的位置完成插入、删除运算。
  3、并方向输出插入、删除结点后的单链表。
  



1



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

本文来源:https://www.bwwdw.com/article/l7v1.html

Top