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

1南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述讲授题目第2章线性表教学目的（1）理解线性表ADT（2）掌握线性表的顺序和链接表示方法，（3）熟练掌握线性表插入、删除和查找元素的算法（4）掌握使用大O记号表示线性表运算的渐近时间复杂度的方法（5）掌握使用线性表求解一元多项式的算术运算问题的方法重点及难点重点：（1）线性表的顺序和链接表示（2）在顺序表和单链表上实现线性表运算（3）顺序和链接表示的优缺点难点：（1）多项式的算术运算主要教学方法（1）课内讲授，课外作业、答疑（2）上机实验（3）课外复习：面向对象程序设计方法（4）课外自学：第12章实习指导教学手段（1）多媒体课件（2）《数据结构》网站的网络资源教学过程学时分配教学内容32.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示22.4多项式的算术运算2南京邮电大学计算机学院教案用纸课程：数据结构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的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。ADT2.1线性表抽象数据类型ADTLinearList{Data:零个或多个元素的有序集合。Operations:Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。Find(i,x)：在x中返回表中下标为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)：把表送至输出流。}掌握线性表的顺序和链接表示方法，若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。线性表的链接存储表示法(1)单链表(2)带表头结点的链表(3)循环链表(4)双向链表3南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述熟练掌握线性表插入、删除和查找元素的算法1）查找下标为i的元素aitemplateclassTboolSeqListT::Find(inti,T&x)const{if(i0||in-1){coutOutofBoundsendl;returnfalse;}x=elements[i];returntrue;}渐近时间复杂度：O(1)查找元素ai的算法templateclassTboolSingleListT::Find(inti,T&x)const{if(i0||in-1){coutOutOfBounds;returnfalse;}NodeT*p=first;for(intj=0;ji;j++)p=p-link;x=p-element;returntrue;}渐近时间复杂度：O(n)（2）插入操作Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；插入操作算法：templateclassTboolSeqListT::Insert(inti,Tx){if(i-1||in-1){coutOutOfBoundsendl;returnfalse;}4南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述if(n==maxLength){coutOverFlowendl;returnfalse;}for(intj=n-1;ji;j--)elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为，渐近时间复杂度：O(n)templateclassTboolSingleListT::Insert(inti,Tx){if(i-1||in-1){coutOutOfBounds;returnfalse;}NodeT*q=newNodeT;q-element=x;//生成新结点qNodeT*p=first;for(intj=0;ji;j++)p=p-link;if(i-1){q-link=p-link；p-link=q;//在p之后插入q}else{q-link=first；first=q;//插字第一个元素之前}n++;returntrue;}渐近时间复杂度：O(n)112)1(11niininnE5南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述删除操作Delete(i)：删除元素ai。删除操作算法：templateclassTboolSeqListT::Delete(inti){if(!n){coutUnderFlowendl;returnfalse;}if(i0||in-1){coutOutOfBoundsendl;returnfalse;}for(intj=i+1;jn;j++)elements[j-1]=elements[j];n--;returntrue;}分析:设顺序表长度为n,则删除元素ai（i=0,…,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为，渐近时间复杂度：O(n)templateclassTboolSingleListT::Delete(inti){if(!n){coutUnderFlowendl;returnfalse;}if(i0||in-1){coutOutOfBoundsendl;returnfalse；}NodeT*p=first,*q=first;for(intj=0;ji-1;j++)q=q-link;1021)1(1nidninnE6南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述if(i==0)first=first-link;else{p=q-link;q-link=p-link;}deletep;n--;returntrue;}渐近时间复杂度：O(n)使用线性表求解一元多项式的算术运算问题的方法下面讨论一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选择，如何描述和实现算法。一元整系数多项式p(x)=3x14-8x8+6x2+2要求:(1)按降幂排列(2)做q(x)q(x)+p(x)每一项就是一个要处理的数据元素，即(coef,exp)。一元整系数多项式可以视为线性表。存储表示q(x)=2exp10+4exp8-6exp6，p(x)=3exp14-8exp8+6exp2+2做q(x)+p(x)q(x)，结果为：q(x)=3exp14+2exp10-4exp8+2(2,10)(4,8)(-6,2)(3,14)(-8,8)(6,2)(2,0)(3,14)(2,10)(-4,8)(2,0)7南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述程序2.6多项式项结点的C++类classPolynominal；classTerm{public:Term(intc,inte);Term(intc,inte,Term*nxt);Term*InsertAfter(intc,inte);//在this指//针指示的项后插入新项private:intcoef;intexp;Term*link;friendostream&operator(ostream&,constTerm&);//输出项friendclassPolynominal;};1.多项式类的成员函数(1)AddTerms函数:通过输入流in，输入多项式的各项(c,e)构造一个多项式。(2)Output函数:将多项式的每一项按降幂方式送输出流。(3)PolyAdd函数:实现将多项式r加到指针this指示的多项式上。程序2.7多项式的C++类classPolynominal{public:Polynominal();~Polynominal();voidAddTerms(istream&in）；voidOutput(ostream&out)const；voidPolyAdd(Polynominal&r）；private:Term*theList;friendostream&operator(ostream&,constPolynominal&);friendistream&operator(istream&,Polynominal&);friendPolynominaloperator+(Polynominal&,Polynominal&);};8南京邮电大学计算机学院教案用纸课程：数据结构B主讲教师：邹志强教材：数据结构——使用C++语言描述一元整系数多项式相加voidPolynominal::PolyAdd(Polynominal&r)//将多项式r加到多项式this上{Term*q,*q1=theList,*p;//q1指向表头结点p=r.theList-link;//p指向第一个要处理的结点q=q1-link;//q1是q的前驱，p和q就指向两个当前进行比较的项while(p-exp=0)//对r的单循环链表遍历,直到全部结点都处理完{while(p-expq-exp)//跳过q-exp大的项{q1=q;q=q-link;}if(p-exp==q-exp)//当指数相等时，系数相加{q-coef=q-coef+p-coef;if(q-coef==0)//若相加后系数为0{q1-link=q-link;delete(q);//则删除q,释放q之空间q=q1-link;//重置q指针}else{q1=q;q=q-link;}//若相加后系数不为0，则移动q1和q}else//p-expq-exp的情况。以p的系数和指数生成新结点，插入q1后q1=q1-InsertAfter(p-coef,p-exp);p=p-link;}}