数据结构教师教学案Word文档格式.docx

数据结构教师教学案Word文档格式.docx

《数据结构教师教学案Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构教师教学案Word文档格式.docx（64页珍藏版）》请在冰点文库上搜索。

1．图书书目自动检索

2．人机对奕

3．交通灯管理

引出《数据结构》的研究内容

计算机系郭猛制

教案中页

1.2数据结构的基本概念和术语

1.数据

2.数据元素、数据项

3.数据对象、数据结构

4.四类基本结构：

集合、线性结构、树形结构、图形结构或网状结构。

5.数据结构一般包括三方面的内容：

逻辑结构

存储结构（物理结构）

数据的运算

算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

6.数据的两种存储结构：

顺序存储结构

链式存储结构

1.3抽象数据类型的表示与实现

类C语言

1.4算法和算法分析

1.4.1算法

算法的定义

算法具有五个重要特性：

有穷性、确定性、可行性、输入、输出

1.4.2算法设计的要求

正确性，可读性，健壮性，高效率低存储

1.4.3算法效率的度量

时间复杂度

1.4.4算法的存储空间需求

空间复杂度

教案末页

教学中遇到的主要问题及解决的方法

主要问题：

学生C语言没有开过，直接学的C++，不过也才学了一学期，这学期还在

继续学习C++

解决方法：

课下参考谭浩强的《C程序设计》

作业批改中发现的问题及教学改进思路

作业及作业要求

课堂练习，了解掌握时间复杂度O（n）的概念和计算。

练习算法的时间复杂度计算

第2--3次

2011年9月1号

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、线性表的动态分配顺序存储结构（用一维数组）

#defineLIST_INIT_SIZE100

#defineLISTINCREAMENT10

typedefstruct{

ElemType*elem;

intlength;

intlistsize;

}SqList;

4、顺序表的运算

顺序表容易实现访问操作，可随机存取元素。

但插入和删除操作主要是移动元素。

⑴初始化操作

⑵插入操作

（3）删除操作

PPT课件中的数组下标，从1开始；

而课本上下标从0开始

提醒学生差数计数的方法。

从周一到周七共几天？

7-1+1

数据结构中大量使用了学生平常C语言中不常用的知识：

宏定义、结构体、联合体定义

Typedef定义类型等等，而这些知识往往是C语言课程中

老师们忽略或者薄弱的环节，因此，在数据结构课程中，尽量

提前讲一些这些预备知识或者作为复习。

静态存储方式和动态存储方式

异同点和优缺点比较。

第3--4次

第3周

2011年9月6

2.3.1节

单链表存储及其运算

掌握单链表存储结构及运算的实现。

建立单链表及实现结点的插入和删除等基本运算

关键：

单链表存储结构定义

难点：

基本运算的实现

2.3线性表的链式表示和实现

2.3.1线性链表

1、线性表的链式存储结构的特点

相关概念：

结点（Node）、数据域、指针域、指针、链、头指针

2、链式存储结构的优点：

插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。

链表的分类

单链表、循环链表和双向链表。

3.单链表：

（1）单链表概念：

链表中的每一个结点中只包含一个指针域的称为单链表或线性链表。

（2）单链表的存储结构定义

typedefstrucLNode{

ElemTypedata;

structLNode*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分别用来指向两个有序链表和合并表的当前元素。

比较两个表的当前元素的大小，将小的元素链接到合并表中，即，让合并表的当前指针指向该元素，然后，修改指针。

在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。

Malloc（），relloc（），free（）的用法学生一头雾水

先把动态分配和静态分配的各自原理给学生说清楚

Malloc分配的空间不够用，用Relloc重新分配，如果

这部分空间不用了，必须用free释放

上机作业：

两个链表的合并算法和测试。

第5次

2011年9月8

2.3.2—2.3.3

循环链表、双向链表、静态链表

掌握循环链表、双链表及静态链表存储结构及其运算实现

循环链表及双链表存储结构及其运算实现

循环链表、双向链表的相关运算

2.3.2循环链表

1、循环链表：

特点：

表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环链表可分为单链和多链的。

2、循环链表的操作：

和线性链表基本一致，差别仅在于循环条件判定是否为空改为是否为头指针。

2.3.3双向链表

1、双向链表：

在双向链表的结点中有两个指针域，分别指向前驱和后继。

双向链表也可以有循环链表。

2、双向链表存储结构定义：

typedefstructDuLNode{

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLinklist;

3、双向链表的操作：

双指针使得链表的双向查找更为方便、快捷。

NextElem和PriorElem的执行时间为O

（1）。

仅需涉及一个方向的指针的操作和线性链表的操作相同。

插入和删除需同时修改两个方向的指针。

4、双向链表的插入操作

1）pnext=q

2）pprior=qprior

3）qpriornext=p

4）qprior=p

2.3.4静态单链表

1．特点：

用数组描述的链表称为静态链表。

2．存储结构定义：

#defineMAXSIZE1000

ElemTypedata;

intcur;

}component,SLinklist[MAXSIZE];

3.运算实现

静态链表的操作和动态链表相似。

以整型游标代替动态指针。

提醒学生，链表的表头指针和头结点是不是一回事？

表头可以作为链表的名称，是个指针，指向头结点。

设计算法：

1．线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写算法删除线性表中值介于a与b（a≤b）之间的元素。

2．某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。

现出库（销售）m台价格为h的电视机，试编写算法修改原链表。

第6-7次

2011年9月13

上机（从10.1之后，单周周二固定上机）

单链表的建立及相关操作

掌握c上机调试的基本方法。

了解单链表的结构特点及相关概念，

掌握单链表结点链接等相关知识。

单链表的建立

[实验要求]

1、建立一个单链表。

2、并在指定的位置完成插入、删除运算。

3、并方向输出插入、删除结点后的单链表。

VisualC++6.0上机环境学生不熟悉

看教学视频，或者XX搜索

根据实验手册实验1

完成实验报告

郭猛

第8次

2011年9月15

3.1节

栈的定义表示及应用

掌握栈的逻辑结构，存储结构及各种存储结构之上基本运算

栈的顺序存储及基本运算的实现

顺序栈基本运算的实现

第3章栈和队列

3．1栈

3．1．1栈的定义

限定仅在表尾进行插入或删除的线性表

栈顶：

表尾

栈底：

表头

3．1．2栈的表示和实现

1．顺序栈

（1）类型说明：

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

SElemType*base,*top;

intstacksize;

}SqStack;

（2）重要算法的实现：

●入栈操作

●取栈顶元素操作

取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针top的位置，而取栈顶元素操作不改

●出栈操作

●判栈空操作

2．链栈

一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。

栈、队列都是特殊的线性表

栈是FILO，队列是FIFO

设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。

答案：

第9次

第4周

2011年9月20日

3.4节

队列的定义表示及实现

掌握队列的逻辑结构，存储结构及各种存储结构之上基本运算的实现

队列的逻辑结构，存储结构及各种存储结构之上基本运算的实现

循环队列

3．4队列

3．4．1抽象数据类型队列的定义

允许在线性表的一端插入,另一端进行删除操作的线性表称为队列.

队尾,队头,双向队列

3．4．2链队列

1、单链队列—队列的链式存储结构：

typedefstructQNode

{QElemtypedata;

structQNode*next;

}Qnode,*QueuePtr;

{QueuePtr*front,*rear;

}LinkQueue;

2、链队列的算法：

算法一：

构造一个空队列

算法二：

销毁一个队列

算法三：

判队列是否为空：

算法四：

入队列

算法五：

出队列

3．4．3循环队列

1．存储结构

#defineMAXQSIZE100

QelemType*base;

intfront；

//头指针，若队列不空，指向队列头元素

intrear;

//尾指针，若队列不空，指向队列尾元素的下一个位置

}SqQueue;

3．循环队列的重要算法：

队列长度

intQueueLength（SqQueueQ）

{return（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;

}

算法三、循环队列的入队列：

队列满条件：

（Q.rear+1）%MAXQSIZE==Q.front

算法四、循环队列出队列：

循环队列的判空和判满

循环队列为空：

front=rear。

循环队列满：

（rear+1）%MAX_QUEUE_SIZE=front。

栈、循环队列，学生不了解学着有什么用。

可以各讲一个实际应用的例子。

Q是一个循环队列，请写出插入和删除一个元素的算法。

循环队列定义

#defineMAXSIZE100//最大队列长度

QElemType*base;

intfront,rear;

}SqQueue;

intEnCQueue（CyclicQueue&

Q,ElemTypex）

{//Q是一个循环队列，若队列不满，则将x插入并返回1；

否则返回0

……}

intDelCQueue（CyclicQueue&

Q,ElemType&

x）

{//Q是一个循环队列，若队列不空，则删除队头元素并由x带回，且返回1；

否则//返回0

……}

第10次

第5周

2011年9月22

3.2,3.5

栈和队列的应用

掌握栈和队列的应用

栈的应用

3．2栈的应用

数据转换

递归

3．5队列的应用

银行排队

找舞伴

栈、队列在计算机中广泛应用。

不必多讲，讲几个典型的：

栈的应用：

递归、表达式求值、走迷宫

队列的应用：

操作系统wait进程排队

上机练习：

汉诺塔问题。

迷宫问题。

表达式求值。

第12次

2011年9月29日

4.1—4.2

串的基本概念、存储及算法实现

掌握串的类型定义及不同存储结构之上基本运算的实现

串不同存储方式下的运算

字符串的运算

第4章串

4．1串类型的定义

1．串的概念

由零个或多个字符组成的有限序列。

一般记作s=‘c0c1c2…cn-1（n≥0）

2．串的基本运算

（1）求字符串的长度的运算strlen（str）

（2）字符串拷贝（赋值）strcpy（str1,str2）：

（3）字符串的联接strcat（str1,str2）：

（4）子串的查询strstr（str1,str2）：

（5）字符串的比较strcmp（str1,str2）：

（6）求子串substr（str1,str2,m,n）：

（7）字符串的删除delstr（str,m,n）：

（8）字符串的插入Insstr（str1,m,str2）：

（9）字符串的替换replacestr（str1,i,j,str2）

4．2串的表示和实现

4．2．1定长顺序存储表示

#defineMAXSTRLEN255

typedefunsignedcharSString[MAXSTRLEN+1]；

//0号单元存放串的长度

串的实际长度可在这预定义长度范围内随意，超过预定义长度的串值则被“截断”

串联接Concat（&

T,S1,S2）

算法二:

求子串SubString（&

Sub,S,pos,len）

4．2．2.堆分配存储表示

typedefstruct{

{char*ch

intlength;

}HString

4．2．3串的块链存储表示

定义：

#defineCHUNKSIZE80

typedefstructChunk{

{charch[CHUNKSIZE];

structChunk*next;

}Chunk;

Chunk*head,*tail;

intcurlen;

}LString;

存储密度=串值所占的存储位/实际分配的存储位

数据结构这章讲的是“串”的数据结构，而不是C语言中的字符数组“串”

参考C程序中的string.h，看看C语言中“串”的常见操作

上机题：

编写串操作中的Replace函数。

第14次

第7周

2011年10月13

4.3—4.4

串的应用

学会串运算的算法

串的模式匹配算法实现

串的模式匹配算法

算法1、字符串的插入操作insstr（str1,i,str2）

算法2、字符串的删除delstr（str,i,j）

算法3、求子字符串算法

算法4、串的模式匹配算法