《数据结构b》教案第02章

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

1、南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述讲授题目第2章线性表教学目的（1）理解线性表ADT（2）掌握线性表的顺序和链接表示方法，（3）熟练掌握线性表插入、删除和查找元素的算法（4）掌握使用大O记号表示线性表运算的渐近时间复杂度的方法（5）掌握使用线性表求解一元多项式的算术运算问题的方法重点及难点重点：（1）线性表的顺序和链接表示（2）在顺序表和单链表上实现线性表运算（3）顺序和链接表示的优缺点难点：（1）多项式的算术运算主要教学方法（1）课内讲授，课外作业

2、、答疑（2）上机实验（3）课外复习：面向对象程序设计方法（4）课外自学：第12章实习指导教学手段（1）多媒体课件（2）《数据结构》网站的网络资源教学过程学时分配教学内容32.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示22.4多项式的算术运算8南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述理解线性表AD线性表是n(³0)个元素a0，a1，…，an-1的有序集合，记为（a0，a1，…，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0时

3、称为空表。设ai是线性表（a0，a1，…，an-1）中第i个元素，i=0,1,…,n-1，则称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。ADT2.1线性表抽象数据类型ADTLinearList{Data:零个或多个元素的有序集合。Operations:Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。Find(i,x)：在x中返回表

4、中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。Search(x)：返回x在表中的下标；若x不在表中，则返回-1。Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。插入成功返回true，否则返回false。Delete(i)：删除元素ai。删除成功返回true，否则返回false。Update(i,x)：将元素ai的值修改为x。修改成功返回true，否则返回false。Output(out)：把表送至输出流。}　　　　　　　　　　　　

5、　　　　　掌握线性表的顺序和链接表示方法，若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。线性表的链接存储表示法(1)单链表(2)带表头结点的链表(3)循环链表(4)双向链表8南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++

6、语言描述熟练掌握线性表插入、删除和查找元素的算法1）查找下标为i的元素aitemplateboolSeqList::Find(inti,T&x)const{if(i<0

7、

8、i>n-1){cout<<"OutofBounds"<boolSingleList::Find(inti,T&x)const{if(i<0

9、

10、i>n-1)

11、{cout<<"OutOfBounds";returnfalse;}Node*p=first;for(intj=0;jlink;x=p->element;returntrue;}渐近时间复杂度：O(n)（2）插入操作Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；插入操作算法：templateboolSeqList::Insert(inti,Tx){if(i<-1

12、

13、i>n-1){cout<

14、<"OutOfBounds"<i;j--)elements[j+1]=elements[j];ele