完整版数据结构教案.docx

完整版数据结构教案.docx

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

完整版数据结构教案

湖南涉外经济学院

教案

学院信息科学与工程学院

系/教研室软件工程系

课程名称数据结构

主讲教师邹竞

湖南涉外经济学院

教案

讲授章节

第1讲绪论

授课时数

2

教学目的：

1.了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；

2.掌握数据结构的基本概念；

3.理解算法描述和简单的算法分析。

教学内容（讲授提纲）

1.从后序课（数据库、操作系统、编译原理、人工智能）的需要和考研两方面介绍数据结构课程的重要性。

2.通过三个例子讲解数据结构研究的内容。

3.介绍基本概念：

数据的三个层次，数据结构的三个要素，数据结构的分类，四种存储结构，抽象数据类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复杂度和空间复杂度。

4.从“百钱买百鸡”（“一百元钱买一百支笔”）的算法例子说明选择算法的重要性：

方案1：

for（i=0;i<=100;i++）

for（j=0;j<=100;j++）

for（k=0;k<=100;k++）

if（i+j+k==100&&3*i+2*j+0.5*k==100）

printf（“i=%d，j=%d，k=%d”,i,j,k）

方案2：

for（i=0;i<=20;i++）

for（j=0;j<=34-i;j++）

if（3*i+2*j+（100-i-j）*0.5==100）

printf（“i=%d,j=%d,k=%d”,i,j,100-i-j）;

方案1内层循环超过100万次，在某机器上运行了50分钟；方案2的if语句执行525次，运行了2秒钟，相差1500倍。

5.算法分析举例

（1）常量阶：

时间复杂度为O

（1）

++x;

s=0;

语句频度为1，时间复杂度为O

（1）。

for（j=1;j<=10000;++j）

{++x;s+=x;}

语句频度为10000，时间复杂度为O

（1）。

（2）对数阶：

时间复杂度为O（logn）

s=0;

for（j=1;j<=n;j*=2）

s++;

语句频度为logn，所以时间复杂度为O（logn）。

（3）线性阶：

时间复杂度为O（logn）

S=0;

for（j=1;j<=n;++j）

s++;

语句频度为n，所以时间复杂度为O（n）。

（4）时间复杂度为O（nlogn）

s=0;

for（j=1;j<=n;j*=2）

for（k=1;k<=n;++k）

s++;

时间复杂度为O（nlogn）

（5）平方阶：

时间复杂度为O（logn）

s=0;

for（j=1;j<=n;++j）

for（k=1;k<=n;++k）

s++;

语句频度为n2，所以时间复杂度为O（n2）。

s=0;

for（j=1;j<=n;j++）

for（k=1;k<=j;++k）

s++;

语句频度为n（n+1）/2，所以时间复杂度仍为O（n2）。

（6）立方阶：

时间复杂度为O（n3）

例：

矩阵乘法：

nxn

for（i=0;i

for（j=0;j

{c[i][j]=0；//n2

for（k=0;k

c[i][j]=c[i][j]+a[i][k]*b[k][j];//n3

}

说明：

各语句行后的数字是该语句重复执行的次数;

本算法时间复杂度为O（n3）

6.空间复杂度

算法原地（就地）工作：

若所用额外存储空间相对于输入数据量来说是常数，则称此算法为原地（就地）工作。

本章节的教学重点、难点：

1.重点是数据结构的基本概念

2.难点是时间复杂度分析

教学方法、教学手段：

1.介绍到算法概念（45分钟）

2.算法分析和举例（45分钟）

使用教具：

计算机和投影仪

♦作业、讨论题、思考题：

♦编写最优算法，从小到大依次输出顺序读入的三个整数。

♦要求：

♦最佳情况：

比较2次，无移动；

♦最差情况：

比较3次，7次移动

参考资料：

1．陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3．严蔚敏等著《数据结构C语言版》清华大学出版社2005

4．D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

教案

讲授章节

第2讲线性表――顺序表

授课时数

2

教学目的：

1.理解非空线性结构的四个特征。

2.线性表是重要的线性结构，要掌握线性表的定义。

3.掌握线性表的操作在顺序表中的实现。

教学内容（讲授提纲）

1.非空线性结构的四个特征。

2.线性表的定义

3.给定线性表的逻辑结构就可以设计算法：

（1）遍历线性表L

（2）合并线性表1:

设La和Lb是元素属于同一数据对象且非递减有序的两个线性表，现要求将两个线性表合并成一个新的非递减有序的线性表Lc。

（3）合并线性表2:

设La和Lb是元素属于同一数据对象的两个线性表，试将线性表Lb合并到线性表La中。

要求Lb中元素和La中元素相同的不再合并。

要分析为什么

（2）和（3）的时间复杂度分别是O（m*n）和O（m+n）。

4.线性表的顺序表示和实现

#defineMAXSIZE100∥顺序表的最大容量

typedefstruct

{ElemTypedata[MAXSIZE];∥存放线性表的数组

intlast;∥last是线性表的长度

}SeqList;

5.线性表的操作在顺序表中的实现。

（1）定义的线性表的10个操作在顺序表中的实现。

（2）分析在插入和删除操作中的时间复杂度。

6.几个算法举例：

（1）顺序结构线性表LA与LB的结点关键字为整数。

LA与LB的元素按非递减有序，线性表空间足够大。

试给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。

高效指最大限度的避免移动元素。

（2）请写一个算法将顺序表（a1,...,an）逆置为（an,...,a1）。

（3）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0（n）、空间复杂度为0

（1）的算法，该算法删除线性表中所有值为item的数据元素。

（O

（1）表示算法的辅助空间为常量）。

♦（4）设将n（n>1）个整数存放到一维数组R中。

试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P（0

要求：

♦

（1）给出算法的基本设计思想。

♦

（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

解答：

（1）算法设计思想：

按照下标0到p-1、p到n-1、0到n-1的顺序，将这三段分别逆置，最后的结果即为所求。

（2）voidleftshift（intR[],intp,intn）

//将有n个元素的一维数组R的序列循环左移p（0

{elemtypet;//t和数组R中的元素具有相同类型

for（i=0;i

{t=R[i];R[i]=R[p-1-i];R[p-1-i]=t;}

for（i=p;i<（n+p）/2;i++）//逆置p..n-1段

{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}

for（i=0;i

{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}

}//算法初始调用:

leftshift（R,p,n），各参数意义如上。

（3）算法执行了两趟逆置，时间复杂度为O（n）;用了一个辅助变量空间，空间复杂度为O

（1）。

讨论：

若采用直接左移p位，空间复杂度仍为O

（1），但时间复杂度为O（np）。

本章节的教学重点、难点：

重点是顺序表的定义，基本操作的实现。

难点是高效算法设计，例如国家2010年硕士研究生入学考试算法题就有5种解法

教学方法、教学手段：

1.开始到顺序表中各种操作实现（45分钟）

2.顺序表算法举例（45分钟）

使用教具：

计算机和投影仪

作业、讨论题、思考题：

2.3分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。

原2.16顺序表la与lb非递减有序，顺序表空间足够大。

试设计一种高效算法，将lb中元素合到la中，使新的la的元素仍保持非递减有序。

高效指最大限度地避免移动元素。

改为2.16顺序表la非递减有序，lb非递增有序，顺序表空间足够大。

试设计一种高效算法，将lb中元素合到la中，使新的la的元素仍保持非递减有序。

高效指最大限度地避免移动元素。

参考资料：

1．陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3．严蔚敏等著《数据结构C语言版》清华大学出版社2005

4．D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

教案

讲授章节

第3讲单链表

授课时数

2

教学目的：

1从顺序存储结构的优缺点，引出链表的必要性。

2.掌握链表的类型定义。

3.掌握线性表的操作在单链表中的实现。

4.掌握单链表的建立方法，特别是头插法和尾插法。

5.了解单链表的应用。

教学内容（讲授提纲）

1顺序存储结构的缺点：

插入和删除必须大量移动元素；必须预先确定空间；表空间不易扩充。

2.链表的类型定义。

typedefstructNode

{ElemTypedata;

structNode*next;

}LNode，*LinkedList；

几个概念：

结点，首元结点，第一元素结点，头结点，指针，头指针

3.掌握线性表的操作在单链表中的实现。

ListInit（L）；

ListLength（L）；

ListGet（L,i）;

ListLocate（L,x）;

ListClear（L）;

ListEmpty（L）；

ListPrior（L,e）；

ListNext（L,e）；

ListInsert（L,i,e）;

ListDelete（L,i）;

4.掌握单链表的建立方法，特别是头插法和尾插法。

（1）头插法

LinkedListLinkedListCreat1（）

{//用头插法建立带头结点的单链表

LinkedListL;

L=（LNode*）malloc（sizeof（LNode））;//申请结点

L->next=NULL;//初始化一个空链表，L为头指针

scanf（&x）;//x是和链表元素具有相同类型的变量

while（x!

=flag）//flag为结束输入的标志

{p=（LNode*）malloc（sizeof（LNode））;

p->data=x;//输入元素值

p->next=L->next;//链接到表中

L->next=p;//插入到表头

scanf（&x）;//读入下一个元素的值

}

returnL;

}

（2）尾插法

LinkedListLinkedListCreat2（）

{//用尾插法建立带头结点的单链表

LinkedListL;

L=（LNode*）malloc（sizeof（LNode））;

L->next=NULL;r=L;

scanf（&x）;

while（x!

=flag）//设置结束标志

{p=（LNode*）malloc（sizeof（LNode）;

p->data=x;//赋值元素值

r->next=p;//在尾部插入新结点

r=p;//r指向新的尾结点

scanf（&x）;

}

r->next=NULL;//最后结点的指针域放空指针

returnL;

}

（3）单链表的遍历

voidprint（LinkedListla）//非递归

{LinkedListp=la->next;

while（p）

{printf（“%c，”,p->data）;//正序输出

p=p->next;

}

}

voidout（LinkedListp）//递归

{if（p）

{out（p->next）;

printf（“%c，”,p->data）;//逆序输出

}//若将以上两个语句位置调换，则正序输出

}

5.了解单链表的应用。

举例1.：

LinkedListUnion（LinkedListla，LinkedListlb）

{∥将非递减有序的单链表la和lb合并成新的非递减有序单链表lc，并要求利用原表空间

举例2：

已知一个带有表头结点的单链表，结点结构为（data,link），假设该链表只给出了头指针list。

在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求：

⑴描述算法的基本设计思想；

⑵描述算法的详细实现步骤；

⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。

【2009年全国硕士研究生入学计算机学科专业基础综合试题】

intSearchInvK（LinkedListla ,intk）

{//在单链表la上查找倒数第k个结点

p=list->link;//p指向当前待处理元素

q=list;//若成功,q指向倒数第k个元素

i=1;

while（p&&i

{i++;p=p->link;}

if（p==null）

{printf（“不存在\n”）;return0;}

while（p）

{q=q->link;p=p->link;}

return1;

}//end

本章节的教学重点、难点：

1．动态存储（单链表）的概念。

2．单链表的算法设计。

教学方法、教学手段：

1．链表的定义和基本操作的实现（45分钟）

2．链表生成和链表应用的算法设计（45分钟）

使用教具：

计算机和投影仪

作业、讨论题、思考题：

2.1试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作用。

2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。

2.4为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂度如何？

2.5在单链表、双链表、单循环链表中，若知道指针p指向某结点，能否删除该结点，时间复杂度如何？

2.6下面算法的功能是什么？

LinkedListUnknown（LinkedListla）

{LNode*q，*p;

if（la&&la->next）

{q=la;la=la->next;p=la;

while（p->next）p=p->next;

p->next=q;q->next=null;

}

returnla;

}

2.7选择题：

在循环双链表的*p结点之后插入*s结点的操作是（）

A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B、p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C、s->prior=p;s->next=p->next;p->next:

=s;p->next->prior=s;

D、s->prior=p;s>next=p>next;p>next->prior=s;p->next=s;

原：

2.9设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链表合并成一个非递增有序的单链表。

要求使用原链表空间，表中无重复数据。

改：

2.9设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链表合并成一个非递减有序的单链表。

要求使用原链表空间，表中无重复数据。

参考资料：

1．陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3．严蔚敏等著《数据结构C语言版》清华大学出版社2005

4．D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社

教案

讲授章节

第4讲循环链表双链表

授课时数

2

教学目的：

1.掌握循环链表引入的背景：

从任一结点开始可以访问链表中的全部结点。

2.掌握循环链表（单循环链表，双循环链表）和双链表。

教学内容（讲授提纲）

1．比较顺序表和单链表操作的优缺点，使用范围。

2．介绍单循环链表。

指出：

单循环链表往往只设尾指针。

3.讲解两个只设尾指针的单循环链表合并成一个单循环链表的例子。

4．双链表的定义：

typedefstructDLNode

{ElemTypedata;

structDLNode*prior,*next;

}DLNode,*DLinkedList;

5.双链表和双循环链表是两种链表。

6.线性表的操作在双链表中的实现

凡涉及一个方向的指针时，如求长度，取元素，元素定位等，其算法描述和单链表基本相同。

但是在插入或删除结点时，一个结点就要修改两个指针域，所以要比单链表复杂。

由于双链表有两个指针域，求前驱和后继都很方便。

6.算法设计举例：

（1）将单循环链表改为双循环链表

假设一个单循环链表，其结点含有三个域pre、data、next。

其中data为数据域；pre为指针域，它的值为空指针（null）；next为指针域，它指向后继结点。

请设计算法，将此表改成双向循环链表。

voidSToDouble（LinkedListla）

{while（la->next->pre==null）

{la->next->pre=la;//将结点la后继的pre指针指向la

la=la->next；//la指针后移

}

}//算法结束

（2）已知一双向循环链表，从第二个结点至表尾递增有序，（设a1

试编写算法，将第一个结点删除并插入表中适当位置，使整个链表递增有序

voidDInsert（DLinkedListL）

{s=L；∥s暂存第一结点的指针

p=L->next；∥将第一结点从链表上摘下

p->prior=L->prior；p->prior->next=p；

while（p->data

p=p->next；∥查插入位置

s->next=p；∥插入原第一结点s

s->prior=p->prior；

p->prior->next=s；

p->prior=s；

}∥算法结束

（3）链表的匹配逆置

L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。

设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。

LinkedListPatternInvert（LinkedListL1,LinkedListL2）

{p=L1；∥p是每趟匹配时L1中的起始结点前驱的指针

q=L1->next；∥q是L1中的工作指针。

s=L2->next；∥s是L2中的工作指针。

while（p!

=null&&s!

=null）

if（q->data==s->data）

{q=q->next;s=s->next;}∥对应字母相等，指针后移。

else//失配时L1起始结点后移，L2从首结点开始。

{p=p->next；q=p->next；s=L2->next；}

if（s==NULL）∥匹配成功，这时p为L1中与L2中首字母结点相同数据域结点//的前驱，q为L1中与L2最后一个结点相同数据域结点的后继。

{r=p->next;∥r为L1的工作指针，初始指向匹配的首字母结点。

p->next=q；∥将p与q结点的链接。

while（r!

=q）；∥逐结点倒置。

{s=r->next；∥暂存r的后继。

r->next=p->next；∥将r所指结点倒置。

p->next=r；

r=s；∥恢复r为当前结点。

}

}

elseprintf（“L2并未在L1中出现”）；

}∥算法结束

本章节的教学重点、难点：

1.循环链表和双链表的概念。

2.难点是循环链表和双链表的应用算法设计。

教学方法、教学手段：

1．循环链表和双链表（45分钟）

2．算法设计（45分钟）

使用教具：

计算机和投影仪

作业、讨论题、思考题：

2.10设la是一个双向循环链表，其表中元素递增有序。

试写一算法插入元素x，使表中元素依然递增有序。

改为：

设la是一个双向循环链表，其表中元素递减有序。

试写一算法插入元素x，使表中元素依然递减有序。

2.12设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空间来构造这两个链表。

设循环链表表示的多项式的结点结构为：

typedefstructnode

{intpower;∥幂

floatcoef;∥系数

ElemTypeother;∥其他信息

structnode*next;∥指向后继的指针

}PNode,*PolyLinkedList;

2.18设la是带头结点的非循环双向链表的指针，其结点中除有prior，data和next外，还有一访问频度域freq，其值在链表初始使用时为0。

当在链表中进行ListLocate（la，x）运算时，若查找失败，则在表尾插入值为x的结点；若查找成功，值为x的结点的freq值增1，并要求链表按freq域值非增（递减）的顺序排列，且最近访问的结点排在频度相同的结点的后面，使频繁访问的结点总是靠近表头。

试编写符合上述要求的ListLocate（la，x）运算的算法，返回找到结点的指针。

参考资料：

1．陈守孔等著《算法与数据结构C语言版》机械工业出版社2007

2．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社2008

3．严蔚敏等著《数据结构