完整版数据结构教案.docx

完整版数据结构教案.docx

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

完整版数据结构教案

湖南涉外经济学院

教案

学院信息科学与工程学院

系/教研室软件工程系

课程名称数据结构

主讲教师邹竞

湖南涉外经济学院

讲授章节第讲绪论

授课时数2

教学目的：

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

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

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

教学内容（讲授提纲）

S++；

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

（3）线性阶：

时间复杂度为O（logn）

S=0;

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

s++;

语句频度为n,所以时间复杂度为0（n）。

（4）时间复杂度为0（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，所以时间复杂度为0（n2）。

s=0;

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

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

s++;

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

（6）立方阶：

时间复杂度为0（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

}

说明：

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

本算法时间复杂度为0（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的数据元素。

（0

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

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

试设计一个在时间和空间两方面

都尽可能高效的算法，将R中保存的序列循环左移P（0

中的数据由（X0,X1,…,Xn-1）变换为（Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1）。

要求：

（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）算法执行了两趟逆置，时间复杂度为0（n）;用了一个辅助变量空间，空间复杂度为0

（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为头指针

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

〃输入元素值

returnL;

}

（2）尾插法

LinkedListLinkedListCreat2（）

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

LinkedListL;

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

L->next=NULL;r=L;

scanf（&x）;

{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（“％”,->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;

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

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

Ds->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•陈守孔等著《算法与数据结构考研试题精析》

3•严蔚敏等著《数据结构C语言版》

4.D.E.Knuth著《计算机程序设计技巧》第

讲授章节

第5讲线性表的算法设计举例

授课时数

2

教学目的：

1.以线性表为具体例子深刻理解线性结构。

2.加深对算法设计的理解。

教学内容（讲授提纲）

1.先介绍线性表的应用：

一兀n次多项式的表示。

2.选择题6——14

3.五个算法设计例子

（1）链表的逆置

（2）循环链表的分解

已知L为无头结点单链表中第一个结点的指针，每个结点数据域存放一个字符，该字

符可能是央文子母子符或数子子符或其它子符，编与算法构造一个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。

（要求用最少的时间和最少的空间）

（3）删除有序链表中的重复元素

在一个非递减有序的线性表中，有数值相冋的元素存在。

若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。

分析算法的时间复杂度。

（4）按序输出链表中各元素

设head是带头结点的单链表的头指针，试写出算法，按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。

要求不允许使用数组作辅助空间。

（5）链表的分解

将单链表L1拆成二个链表，其中以L1为头的链表保持原来向后的链接，另一个链表

的表头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的结点，L2包含原链表

的偶数序号的结点。

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

1•链表是本章重点。

2.难点是链表的算法设计。

教学方法、教学手段：

1.基本概念和算法（30分钟）

2.算法设计（60分钟）

使用教具：

计算机和投影仪

作业、讨论题、思考题：

完成本章所留习题

参考资料：

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

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

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

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

讲授章节

第6讲栈

授课时数

2

教学目的：

1理解栈和队列仍属于线性结构，其操作是线性表操作的子集，是操作受限的线性表。

但从数据类型的角度看，它们是和线性表大