《《数据结构B》教案第02章.doc》由会员分享，可在线阅读，更多相关《《数据结构B》教案第02章.doc（8页珍藏版）》请在金锄头文库上搜索。
1、南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述 讲授题目第2章 线性表教学目的（1） 理解线性表ADT（2） 掌握线性表的顺序和链接表示方法，（3） 熟练掌握线性表插入、删除和查找元素的算法（4） 掌握使用大O记号表示线性表运算的渐近时间复杂度的方法（5） 掌握使用线性表求解一元多项式的算术运算问题的方法重点及难点重点：（1） 线性表的顺序和链接表示（2） 在顺序表和单链表上实现线性表运算（3） 顺序和链接表示的优缺点 难点：（1） 多项式的算术运算主要教学方法（1） 课内讲授，课外作业、答疑（2） 上机实验（3） 课外复习：面向对象程序设计
2、方法 （4） 课外自学：第12章 实习指导教学手段（1）多媒体课件（2）数据结构网站的网络资源教学过程学时分配教 学 内 容32.1 线性表ADT 2.2 线性表的顺序表示 2.3 线性表的链接表示 22.4 多项式的算术运算 南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述理解线性表AD线性表是n(0)个元素a0，a1，an-1 的有序集合，记为（a0，a1，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0 时称为空表。设ai是线性表（a0，a1，an-1）中第i个元素，i=0, 1,n-1，则称 ai 是ai+1的直接前驱元
3、素，ai+1是ai的直接后继元素。 线性表是动态数据结构，它的表长可以改变。 ADT 2.1 线性表抽象数据类型ADT LinearList Data:零个或多个元素的有序集合。 Operations: Create()： 创建一个空线性表。 Destroy()： 撤消一个线性表。 IsEmpty()：若线性表空，则返回true；否则返回false。 Length()：返回表中元素个数。 Find(i,x)：在x中返回表中下标为i的元素ai(即表中第i+1个元素)。 如果不存在，则返回false，否则返回true。 Search(x)：返回x在表中的下标；若x不在表中，则返回-1。 Inser
4、t(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。 插入成功返回true，否则返回false。 Delete(i)：删除元素ai。删除成功返回true，否则返回false。 Update(i,x)：将元素ai的值修改为x。修改成功返回true，否则返回 false。 Output(out)：把表送至输出流。掌握线性表的顺序和链接表示方法，若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0) ，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k 只要给定loc(a0)和k，就可以确定
5、线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。 线性表的链接存储表示法 (1) 单链表 (2) 带表头结点的链表 (3) 循环链表 (4) 双向链表6南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述熟练掌握线性表插入、删除和查找元素的算法1） 查找下标为i的元素aitemplatebool SeqList:Find(int i,T& x) const if (in-1) coutOut of Boundsendl; return false; x=elementsi; return true;渐近时间复杂度：O(1) 查找
6、元素ai的算法 templatebool SingleList:Find(int i,T& x)const if (in-1 ) cout Out Of Bounds; return false; Node *p=first; for (int j=0; jlink; x=p-element; return true;渐近时间复杂度：O(n)（2）插入操作 Insert(i,x)： 在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true； 插入操作算法：templatebool SeqList:Insert(int i,T x) if (in-1) co
7、utOut Of Boundsendl; return false;南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述 if (n=maxLength ) coutOverFlowi;j-) elementsj+1=elementsj; elementsi+1=x; n+; return true;设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为，渐近时间复杂度：O(n)templatebool SingleList:Insert(int i,T x) i
8、f ( in-1 ) cout Out Of Bounds; return false; Node *q=new Node; q-element=x; /生成新结点q Node *p=first; for (int j=0; jlink; if(i-1) q-link=p-link；p-link=q; /在p之后插入qelse q-link=first；first=q; /插字第一个元素之前 n+; return true;渐近时间复杂度：O(n)南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述删除操作 Delete(i)： 删除元素ai。删除
9、操作算法：template bool SeqList:Delete(int i) if ( !n ) coutUnderFlowendl; return false; if ( in-1 ) coutOut Of Boundsendl; return false; for (int j=i+1;jn;j+) elementsj-1=elementsj; n-; return true;分析: 设顺序表长度为n,则删除元素ai（i=0,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为，渐近时间复杂度：O(n)te
10、mplatebool SingleList:Delete(int i) if ( !n ) coutUnderFlowendl;return false;if ( in-1 ) cout Out Of Boundsendl;return false； Node *p=first,*q=first; for (int j=0; jlink;南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述 if (i=0) first=first-link; else p=q-link; q-link=p-link; delete p; n-; return tr
11、ue;渐近时间复杂度：O(n) 使用线性表求解一元多项式的算术运算问题的方法下面讨论一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选择，如何描述和实现算法。一元整系数多项式 p(x)=3x14-8x8+6x2+2 要求:(1)按降幂排列 (2)做q(x)q(x)+p(x) 每一项就是一个要处理的数据元素，即 (coef,exp) 。一元整系数多项式可以视为线性表。存储表示q(x)=2 exp 10+4 exp 8-6 exp 6，p(x)=3 exp 14-8 exp 8+6 exp 2+2 做q(x)+p(x)q(x)， 结果为：q(x)= 3 ex
12、p 14+2 exp 10-4 exp 8+2 (2,10) (4,8) (-6,2)(3,14) (-8,8) (6,2) (2,0)(3,14) (2,10)(-4,8) (2,0)南京邮电大学计算机学院教案用纸课程： 数据结构B 主讲教师：邹志强 教材：数据结构使用C+语言描述程序2.6 多项式项结点的C+类class Polynominal；class Term public: Term(int c,int e);Term(int c,int e,Term* nxt);Term *InsertAfter(int c,int e);/在this指 /针指示的项后插入新项 private:int coef;int exp;Term *link;friend ostream & operator(ostream &,
