数据结构（C++语言描述）PPT全套完整教学课件VIP

数据结构（C++语言描述）1第一章绪论.pptx2第二章线性表.pptx 3第三章栈和队列.pptx 4第四章树.pptx 5第五章图.pptx 6第六章查找.pptx 7第七章排序.pptx 5.1-静态查找技术.pptx 5.2-动态查找技术.pptx 5.3-二叉查找树的查找.pptx ..........

第一章绪论数据结构算法C++部分概念数据结构数据结构研究内容数据：外界信息进入计算机后，统称为数据。一般分为数值和非数值型。数据元素：是数据处理的最小单位，是一个数据个体。

如处理某窗口前的队列，队列中所有人的信息称数据，每个人的信息称数据元素。什么是数据及数据元素数据结构：有限个、类型相同、相互之间具有一定制约关系的数据元素组成的集合。如某窗口前的队列，有限/类型相同/你先我后关系。几种典型结构：什么是数据结构数据结构研究内容：（以队列为例）

逻辑关系（逻辑结构）+基本操作（关系操作）------来源于生活实践，和计算机无关。存储实现（物理结构）------数据及数据关系在内存中的存储。基本操作的实现------某种存储处理下各种基本操作的实现。典型应用------这种数据结构在生活实践中的典型应用。数据结构研究内容指类型相同的一组元素和元素间的关系。根据关系不同，可分为以下几种：集合关系：不同元素除了同属于一个集合，相互间无其他制约关系。线性关系：元素间呈现你先我后的顺序，是一种一对一的关系。树形关系：元素间呈现一对多的关系。图关系：元素间呈现多对多的关系。逻辑结构

逻辑结构的描述具有某种关系的数据在生活实践中表现出的几种功能相对独立的数据处理（操作）。它和数据的逻辑结构紧密相关，它来源于现实生活中关系自身的特点。无论哪种逻辑结构，基本操作都可分为五大类：构造类、属性类、数据操纵类、遍历类和典型应用类。基本操作(关系操作)构造类：在内存中建立这种数据结构。如一个队列，有存储空间，无或有若干元素。属性类：对元素及元素之间关系的各类查询。属于东瞧瞧、西看看，不影响元素值及元素关系。如在线性结构中查询值为X的元素是否存在，队列中队首是谁。数据操纵类：对元素或元素关系有改变的操作。如插入或删除某个元素，一般修改可以视作在同一位置上先删除一个旧元素后再插入一个新元素，因此不再讨论修改。遍历类：对结构中的每个元素访问且只访问一遍。因其重要且有时又较复杂，常常是其他操作的基础，如遍历树结构、图结构中的元素，所以特意把遍历操作从属性类中单独拿出来研究。典型应用类：每种结构独特的应用。不同结构其典型应用各不相同，如线性结构可以解决队列问题、图结构可以解决两个城市间最短路径问题。数据结构在内存中的表示。数据要得到处理首先必须进入内存。内存中不仅要存储数据元素的值，还要存储元素间的关系。任何一种数据结构基本操作的设计取决于其逻辑结构，但基本操作的实现完全依赖其存储结构。元素及其关系在内存中用什么结构存储适合，原则是存储方式要有利于基本操作的实现。什么是存储结构顺序存储：用一块连续的空间存储数据，借助空间地址上的有序性存储元素间的关系。顺序存储的结构以下称顺序结构。高级语言中，数组是地址连续的空间，有助于实现顺序结构。链式存储：元素可以各自存储在独立的空间中，不要求不同数据存储的内存空间连续，元素间的关系附带存储在数据各自占据的独立空间中。数据结构的链式存储也称链式结构。常见的存储方式存储数据及其关系的目的就是为了处理。基本操作实现方法以存储方法为基础。如果是顺序结构，操作实现就是对数组做各种不同的操作；如果是链式结构，操作实现就是对链表做各种不同的操作。同一种操作虽然在顺序结构和链式结构中具体实现方法不同，但目标都要符合ADT对基本操作定义的条件和结果。如果某种存储方式下，基本操作不易实现，说明存储方式不好，可以考虑放弃这种存储方法。基本操作的实现数据结构算法C++部分概念算法及算法特性算法时间复杂度算法空间复杂度算法具有5个特性：确定性：每一步有确定的含义，没有二义性。有穷性：每一步在有限的时间内完成，整个算法必须在有限步之后完成。可行性：每一步都是经过有限次基本操作可以完成，自身没有复杂的算法。有输入：一个算法可以有零个或者若干个输入作为解决问题的已知条件。有输出：有零个或者若干个输出作为算法运行结果。算法：是解决一个具体问题的方法和步骤。正确性：准确反映并能满足具体问题的要求。可读性：可供人们阅读的容易程度。健壮性：对各种不同的输入都要有相应的反应时间效率：算法的执行时间。空间效率：算法执行期间所需要的最大内存空间。算法的基本要求：比如：选最大桔子问题，体育课排队，5个数字的加法。正确的方式：计算思维，具体从编程语言出发。具体编程语言：输入、输出、赋值、两两比较、算术和逻辑运算，循环、函数（递归）等。

如冒泡排序，选择排序的设计思想设计算法的误区：从以往生活的经验出发，找解决问题的方法算法的执行时间是指依据算法编制的程序运行时所消耗的时间。度量方法有运行后度量和运行前分析。运行后度量：指根据不同算法事先编制好的程序和同样的测试数据，在程序运行时借助机器的计时功能进行计时。当不同程序运行结束时，分别记录实际的运行时间并进行比较。运行前分析：指在算法设计后，在实现程序运行前，根据几个方面的影响因素对算法的执行时间进行分析。算法的时间复杂度机器的运算速度：根据主频和字长。编译后代码的质量：因编译优化策略不同书写程序所用的语言：语言越高级，运行效率低，编程效率高。问题的规模和数据的分布：规模大，分布特殊则处理方法可不同。算法采用的策略和方法：如用迭代或递归就不同。算法设计主要关注5，算法的策略和方法。运行前分析的依据用算法中标准操作即基本语句的执行次数来度量运行时间。基本语句执行次数越多，时间花费越多，执行次数称时间频度。时间频度和处理的数据规模n有关，可表示为n的函数T(n)。s=0;for(i=0;i<n;i++)

s=s+i;算法运行时间的度量---时间频度s=0执行1次，i=0执行1次，i<n执行n+1次，i++执行n次，s=s+i执行n次，共计执行标准操作3n+3次。故算法的时间频度为T(n)=3n+3。循环语句---需要计算实际运行的次数，不是看语句书写的次数。分支语句---按照执行语句多的那个分支计算。如：if(n>0){for(i=0;i<n;i++)cout<<i;}else

cout<<"n<=0!";算法运行时间的度量原则n>0时，为3n+3次；n<=0时，为1次。时间频度为3n+3。

算法的时间复杂度

算法的时间复杂度

算法的时间复杂度

算法的时间复杂度找算法中和数据规模n有关的循环语句，计算循环体的执行次数获得时间频度函数。观察时间频度函数中关于n的最高次项，去掉其系数，即是时间复杂度的大O表示。特殊地：如果算法中无执行次数和数据规模n的相关语句，即时间频度函数是一个常量，则时间复杂度为O(1)。总结时间复杂度的计算方法：

常见算法的时间复杂度：求和定理、求积定理求和定理：假定T1(n)、T2(n)是程序P1、P2的运行时间，并且T1(n)是O(f(n))的，而T2(n)是O(g(n))的。那么，先运行P1、再运行P2的总的运行时间是：T1(n)＋T2(n)＝O(MAX(f(n)，g(n))。for(i=0;i<n;i++)a[i]=0;//第一段for(i=0;i<n;i++)//第二段 for(j=0;j<n;j++)a[i]=i+j;按照求和定理为O(max(n,n2))=O(n2）计算时间复杂度的简化工具：两个定理求和定理、求积定理求积定理：如果T1(n)和T2(n)分别是O(f(n))和O(g(n))的，那么T1(n)×T2(n)是O(f(n)×g(n))的。for(i=0;i<n;i++) for(j=0;j<n;j++) {s=s+i+j;cout<<s;}按照求积定理，为O(n*n)=O(n2)计算时间复杂度的简化工具：两个定理通常考虑三个方面：最好情况的时间复杂度、最坏情况的时间复杂度和平均情况的时间复杂度。大O表示法中，O是数量级order的首字母。O(f(n))并不描述运行时间的精确值，只给出一个数量级。它表示：当问题规模很大时，算法运行时间的增长受限于哪一个数量级的函数，简称为量阶。算法的时间复杂度算法的空间消耗包括三个方面：实现算法的程序本身需要占据存储空间待处理的数据需要在内存中存储，占据一定的空间处理数据的过程中需要一些额外的辅助空间。通常一和二是不可避免的，在设计算法时主要关注额外的辅助空间。渐进空间复杂度也称空间复杂度：是当数据规模n趋于无穷时使用辅助空间的量阶，计为S(n)=O(f(n))。算法的空间复杂度inta[10]={1,6,2,5,8,9,5,4,3,12};intt,i;for(i=0;i<5;i++){ t=a[i]; a[i]=a[10-i-1]; a[10-i-1]=t;}一个数据序列逆置的示例：为完成n=10个元素的逆置，将a[0]和a[9]交换、a[1]和a[8]交换，最后直到a[4]和a[5]交换。使用的辅助空间为一个变量t，辅助空间数量和元素个数没有关系，故其空间复杂度为O(1)。inta[10]={1,6,2,5,8,9,5,4,3,12},b[10];inti;for(i=0;i<10;i++) b[i]=a[10-i-1];for(i=0;i<10;i++) a[i]=b[i];一个数据序列逆置的示例：使用了具有n个元素空间的数组b作为辅助空间，空间复杂度为O(n)。在内存足够大的情况下，算法更加注重时间效率，忽略空间复杂度的计算。或者仅当算法的时间复杂度一致的情况下才可能比较空间复杂度的优劣。说明：数据结构算法

C++部分概念面向对象泛型机制const机制异常处理面向对象方法将数据和对数据的基本操作处理函数都封装在一个类中，分别成为一个类的属性和成员函数。整个类相当于定义了一个新的数据类型，然后根据具体问题建立该类的对象（即变量），通过对象调用合适的函数来解决实际问题。面向对象任务：将1-20之间的奇数存入内存，之后在这组数中查找用户输入的任意一个整数并报告查找结果。面向过程VS面向对象：voidsetValue(intb[],intn);voidfind(intb[],intn,intx);//查找x

intmain(){intdata[10],a;

setValue(data,10);

cout<<"a=";cin>>a;

find(data,10,a);return0;}面向过程：voidsetValue(intb[],intn){for(inti=0;i<n;i++)b[i]=2*i+1;}

voidfind(intb[],intn,intx){inti;for(i=0;i<n;i++)

if(b[i]==x)break;

if(i==n)

cout<<x<<"doesn'texistinthearray!";

else

cout<<x<<"existsinthearray!";cout<<endl;}classarr{private:int*a;intmaxSize,count;public:arr(intsize);voidappend(intx);voidfind(intx);~arr(){delete[]a;};};面向对象：arr::arr(intsize){a=newint[size];maxSize=size;count=0;}

voidarr::append(intx){if(count==maxSize)return;a[count]=x;count++;}voidarr::find(intx){inti;for(i=0;i<count;i++)if(a[i]==x)break;if(i==count)cout<<x<<"doesn'texistinthearray!";elsecout<<x<<"existsinthearray!";cout<<endl;}面向对象：intmain(){arrobj(10);inta;

for(inti=0;i<10;i++)

//将几个奇数放入对象obj.append(2*i+1);

cout<<"a=";cin>>a;

obj.find(a);return0;}数据结构研究的是具有一定关系，且类型相同的一组元素。元素类型不特指某种具体类型，如整型、字符型或者复杂的结构类型。元素无论何种类型，它们在关系、基本操作处理方法上是一样的。因此在数据类型上使用泛型机制：函数模板、类模板泛型机制函数模板定义template<classT>Tmax(Tx,Ty){if(x>y)returnx;elsereturny;}函数模板的使用intmain{count<<max(3,5)<<max(‘a’,’h’)<<endl;}//自动检测类型，编译时产生模板函数函数模板类模板的定义template<classelemType>classarr{private:elemType*a;intmaxSize,count;public:arr(intsize);

类模板//参数前加const，保护参数在函数执行中不得修改voidappend(constelemType&x);

//参数表后加const,保护调用函数的对象的值不得修改voidfind(constelemType&x)const;~arr(){delete[]a;};};

template<classelemType>//类模板中成员函数自动为函数模板arr<elemType>::arr(intsize){a=newelemType[size];maxSize=size;count=0;}类模板

template<classelemType>voidarr<elemType>::append(constelemType&x){if(count==maxSize)return;a[count]=x;count++;}template<classelemType>voidarr<elemType>::find(constelemType&x)const{inti;for(i=0;i<count;i++)

if(a[i]==x)break;类模板

if(i==count)cout<<x<<"doesn'texistinthearray!";

elsecout<<x<<"existsinthearray!";cout<<endl;}类模板的使用intmain(){arr<int>obj1(10);

//<int>使得类模板实例化为一个模板类

constarr<int>obj2(20);

inta;

constintb=100;

类模板

for(inti=0;i<10;i++)obj1.append(2*i+1);cout<<"a=";cin>>a;cout<<"Inobj1:";obj1.find(a);cout<<"Inobj1:";obj1.find(b);cout<<"Inobj2:";obj2.find(a);return0;}用const修饰变量，变量将变为常量。常量一般有初值，在常量的生命周期中，终生不得改变其值。C++中const最普通的用法：constdoublePI=3.14;const机制函数voidfind(constelemType&x)const中修饰参数x的const和&组合。const修饰：变量x前加const，表明在函数的实现过程中参数x的值不需要改变。如函数voidf(constintx)，参数加了const后，编译器会在程序编译阶段帮助程序检查函数实现代码中是否含有修改x值的语句，如果有就报错。所以，如果确认函数实现中不准备改变x的值，请养成加const的习惯。类定义时常见的两种const用法：函数voidfind(constelemType&x)const中修饰参数x的const和&组合。const和&组合修饰：函数find的原型中，x前带&符号，说明形参x不分配空间，是将来调用时实参的别名。如对它的调用obj1.find(a);形参x不分空间，和实参a共用空间。一般来说，如果一个函数只是使用实参a的值，并不想改变实参a的值，这个&就没有必要用，只要加const便可。类定义时常见的两种const用法：函数voidfind(constelemType&x)const中修饰参数x的const和&组合。const和&组合修饰：因为参数类型elemType是一种泛型类型，调用find函数时实参可能是复杂的结构类型，加了&符号就有了明显的好处：形参x不分空间，节省了空间消耗。没有空间分配，在实参和形参打交道时，就不涉及拷贝构造函数的执行。

提高了运行效率。故泛型类型参数前尽量加&符号，如果函数又不需要改变这个参数，请养成const加&组合的习惯。类定义时常见的两种const用法：2.函数voidfind(constelemType&x)const中参数表后const的用法。

参数表后的const是保护调用它的对象的值不能被改变。

语句obj1.find(a)，这个const就是保护对象obj1的值。

一个成员函数不准备改变调用它的对象的值，请养成在参数表后加const的习惯。如果没有函数参数表后带const的支持，常对象obj2是不能调用这个函数的。常对象obj2只能调用参数表后带const的成员函数，加const就为常对象调用它开一扇窗。constarrobj2;obj2.find(10);类定义时常见的两种const用法：template<classelemType>elemTypearr<elemType>::fetch(inti)const{if((i<0)||(i>=count)){cout<<"indexisoutofbound!"<<endl;exit(1);}elsereturna[i];}异常处理在数组类模板中的函数fetch读取并返回下标为i的元素考虑问题：当i越界时返回什么合适？调用exit函数？throw，try，catch异常处理机制classtooSmall{};classtooBig{};异常处理template<classelemType>elemTypearr<elemType>::fetch(inti)const{if(i<0)throwtooSmall();if(i>=count)throwtooBig();elsereturna[i];}intmain(){arr<int>obj1(10);constarr<int>obj2(20);inti;

try{for(i=0;i<10;i++)obj1.append(2*i+1);

异常处理

while(cin>>i)

cout<<i<<":"<<obj1.fetch(i)<<endl;}catch(tooSmall){cout<<"indexistoosmall!"<<endl;}catch(tooBig){cout<<"indexistoobig!"<<endl;}

cout<<"Returntomain,itisOver!"<<endl;return0;}数据元素及元素间关系称作数据结构。数据结构研究具有某种制约关系的一组元素及元素间关系在内存中如何存储、在各种存储方式下关系操作如何实现，以及各种数据结构的典型应用。具体研究分逻辑结构及基本操作、物理结构、基本操作实现、典型应用四个方面。在分析逻辑结构和基本操作时，要完全脱离计算机而仅仅依赖现实生活中的元素特征来分析元素、元素关系及基本操作，最后给出用伪代码描述的抽象数据类型。小结在物理结构分析阶段，讨论元素及元素关系在内存中如何存储。存储可以分顺序存储和链式存储，顺序存储使用一块连续的空间存储元素和元素之间的关系；链式存储使用各自独立的空间存储每个元素，并在每个独立的空间中附加字段以存储元素之间关系。在基本操作实现分析阶段，研究在各种存储方式下基本操作的实现方法和步骤即算法。对于算法提出了时间复杂度和空间复杂度的概念及计算方法，并以此为依据，对不同算法进行性能比较。在典型应用阶段，给出所研究的数据结构最适合的实际应用问题。小结第二章线性表张同珍线性表

顺序表及实现链表及实现一元多项式字符串稀疏矩阵一组特征相同且数量有限的元素构成的集合。该集合可以为空，也可以不为空。当不为空时，有唯一一个元素被称为首元素，有唯一一个元素被称为尾元素。除了尾元素，每个元素有且仅有一个直接后继元素；除了首元素，每个元素有且仅有一个直接前驱元素。

线性结构定义：线性表(List)、时间有序表(ChronologicalOrderedList)、排序表(SortedList)、频率有序表(FrequencyOrderedList)等。线性表：通过元素之间的相对位置来确定它们之间相互关系。时间有序表：按元素到达结构的时间先后，确定元素之间的关系。栈/队列排序表：据元素的关键字值来确定其间的关系。频率有序表：按元素的使用频率确定它们之间的相互关系。常见的几种线性结构：一种仅由元素的相互位置确定它们之间相互关系的线性结构，元素之间呈现出你先我后的关系。

线性表的规模或长度是指线性表中元素的个数。特别地：当元素的个数为零时，该线性表称为空表。线性表Data:{xi|xi

ElemSet,i=1,2,3,……n,n>0}或Φ;ElemSet为元素集合。Relation:{<xi,xi+1>|xi,xi+1

ElemSet,i=1,2,3,……n-1},

x1为首元素，xn为尾元素。Operations:initialize

前提: 无或指定List的规模。结果: 分配相应空间及初始化。isEmpty

前提：无

结果：表List为空返回true，否则返回false。isFull前提：无

结果：表List为满返回true，否则返回false。线性表List的ADT：描述关系和关系操作length

前提：无

结果：返回表List中的元素个数。get

前提：已知元素序号。

结果：

如果该序号元素存在，则返回相应元素的数据值。find

前提：已知元素的数据值。

结果：

查找成功，返回元素的序号，否则返回查找失败标志。insert前提：已知待插入的元素及插入位置。

结果：如果插入位置合理，在指定位置插入该元素。线性表List的ADT：描述关系和关系操作remove前提：已知被删元素的值。

结果：首先按值查找相应元素，查找成功则删除该元素。clear

前提:

无

结果：删除表List中的所有元素。常见的基本操作来源于生活中对这种结构的了解。基本操作可以分为几大类型：结构类、属性类、数据操纵类、遍历类和典型应用类，线性表List的ADT：描述关系和关系操作熟练C++面向对象的编程方法、C++语法、书写完整程序的技巧。接触并逐步熟悉研究一种数据结构的角度和方法。掌握顺序结构的基本功。掌握链式操作的基本功。掌握数据结构工具的建造和工具使用的不同。掌握最基本且简单的线性结构-线性表结构线性表这章的任务和目标：

线性表

顺序表及实现链表及实现一元多项式字符串稀疏矩阵元素存放在内存中一块连续的空间里。借助存储空间物理上的连续性，元素可以按照其逻辑顺序依次存放，即元素存放的物理顺序和它的逻辑顺序是一致的。顺序存储的线性表称顺序表。在高级语言的固有数据类型中，数组在存储器中就表现为一块连续的空间，因此用数组实现顺序表非常合适。数组中各元素位置由其下标来表示，它同时也是相应元素的位置序号。顺序结构顺序表的存储映像图elem为数组名字，数组存储线性表。maxSize为len的上界；initSize为最大的存储空间数，maxSize=initSize-1elem[0]用于其它特殊用途，如果不用于特殊用途maxSize=initSizelen为元素个数，即顺序表长度；#include<iostream>#defineINITSIZE100usingnamespacestd;

//用于异常处理中识别错误类别classillegalSize{};classoutOfBound{};顺序表seqList及操作的定义（seqList.h）template<classelemType>classseqList{private:elemType*elem;//顺序表存储数组，存放实际的数据元素。

intlen;//顺序表中的元素个数，亦称表的长度。

intmaxSize;//顺序表的的最大可能的长度。

voiddoubleSpace();//私有函数，做内部工具顺序表seqList及操作的定义（seqList.h）

public:seqList(intsize=INITSIZE);//初始化顺序表

//表为空返回true,否则返回false。boolisEmpty()const{return(len==0);}

//表为满返回true，否则返回false。boolisFull()const{return(len==maxSize);}intlength()const{returnlen;}//表的长度，即实际存储元素的个数。

顺序表seqList及操作的定义（seqList.h）注意各处：const和const&的用法

elemTypeget(inti)const;//返回第i个元素的值//返回值等于e的元素的序号，无则返回0.intfind(constelemType&e)const;

//在第i个位置上插入新的元素（值为e），//使原来的第i个元素成为第i+1个元素。voidinsert(inti,constelemType&e);//若第i个元素存在，删除并将其值放入e指向的空间。顺序表seqList及操作的定义（seqList.h）

voidremove(inti,elemType&e);

voidclear(){len=0;};//清除顺序表，使得其成为空表~seqList(){delete[]elem;};//释放表占用的动态数组};顺序表seqList及操作的定义（seqList.h）顺序表基本操作的实现代码（seqList.h）//属性赋初值，注意模板函数用法：帽子和胡须template<classelemType>seqList<elemType>::seqList(intsize)//初始化顺序表{elem=newelemType[size];//申请动态数组

if(!elem)throwillegalSize();maxSize=size-1;//0下标位置用于查找时做哨兵位。

len=0;}顺序表基本操作的实现代码template<classelemType>voidseqList<elemType>::doubleSpace(){inti;elemType*tmp=newelemType[2*maxSize];if(!tmp)throwillegalSize();

for(i=1;i<=len;i++)tmp[i]=elem[i];

delete[]elem;elem=tmp;maxSize=2*maxSize-1;}查找操作：待查元素放哨兵位，从后往前比较

顺序表基本操作的实现分析分析时间效率：查找成功情况：查找每个位置元素等概率1/n平均：(1+2+…+n)1/n=（n+1)/2时间复杂度：O(n)查找不成功情况：每次查找从尾部到哨兵位，比较n+1次时间复杂度：O(n)摆龙门阵：顺序表基本操作的实现代码template<classelemType>//注意各处const,const+&组合的用法intseqList<elemType>::find(constelemType&e)const//返回值等于e的元素的序号，无则返回0.{inti;elem[0]=e;//哨兵位先置为待查元素for(i=len;i>=0;i--)if(elem[i]==e)break;returni;}插入操作：新元素欲插在下标为i的位置，i可能的取值为n+1,n,…,2,1。顺序表基本操作的实现分析特别注意：是从后往前至i位置逐个元素后移一位。分析时间效率：插入每个位置等概率1/（n+1）移动的次数分别为0,1,2,…,n平均：(1+2+…+n)/(n+1)=n/2时间复杂度：O(n)摆龙门阵：顺序表基本操作的实现代码如何写出一个完成的程序？“五步口诀法”：参数检查空间是否支持核心操作对其他属性的影响正确返回顺序表基本操作的实现代码template<classelemType>voidseqList<elemType>::insert(inti,constelemType&e){intk;if((i<1)||(i>len+1))return;//插入位置越界if(len==maxSize)doubleSpace();//空间满了，无法插入元素

for(k=len+1;k>i;k--)elem[k]=elem[k-1];elem[i]=e;len++;}循环注意：左右边界的检查删除操作：待删元素在下标为i的位置，i可能的取值为n,…,2,1。顺序表基本操作的实现分析特别注意：是自i+1位置开始，从前往后逐个元素前移一位。分析时间效率：删除每个位置等概率1/n移动的次数分别为0,1,2,…,n-1平均：(1+2+…+n-1)/n=（n-1）/2时间复杂度：O(n)摆龙门阵：顺序表基本操作的实现代码template<classelemType>//注意五步口诀法voidseqList<elemType>::remove(inti,elemType&e){intk;if((i<1)||(i>len))return;e=elem[i];

for(k=i;k<len;k++)elem[k]=elem[k+1];len--;}顺序表基本操作的实现代码template<classelemType>elemTypeseqList<elemType>::get(inti)const//返回第i个元素的值{if((i<1)||(i>len))throwoutOfBound();returnelem[i];}

顺序表基本操作的实现代码常见错误：混淆len和maxSize的含义，前者是实际元素的个数，后者是存储空间的大小，也是最多能存多少元素的限制。seqList对象作为函数形参，直接用对象形式而不用引用形式,这样即浪费空间又引起seqList类的复制构造函数的执行，降低运行效率。insert函数实现中忘记检查位置i的合理性、忘了检查表中是否有空间可以支持插入一个新的元素等，造成算法不完整。可以试着使用分析参数、空间检查、核心操作、对其他属性的影响、正确返回的“五步口诀法”，就可以设计出一个相对完整的程序。顺序表应用---基本操作的测试main.cpp#include<iostream>#include"seqlist.h"usingnamespacestd;

//求两个正整数集合的交集，用线性表处理集合问题。intmain(){seqList<int>list1(20),list2(20),list3(20);//实例化对象inti,j,x;

intlen1,len3;

//输入第一个整数集合中的元素，输入零结束：i=1;cout<<"输入第一个正整数集合，以零为结束标志：";cin>>x;

while(x!=0){list1.insert(i,x);i++;cin>>x;}//输入第二个整数集合中的元素，输入零结束：i=1;cout<<"输入第一个正整数集合，以零为结束标志：";cin>>x;

while(x!=0){list2.insert(i,x);i++;cin>>x;}

//求list1,list2的交集，结果存入list3len1=list1.length();j=1;for(i=1;i<=len1;i++){x=list1.get(i);if(list2.find(x)!=0)

{

list3.insert(j,x);j++;}}

//显示list3中的元素cout<<"两个集合的交集元素为：";len3=list3.length();for(i=1;i<=len3;i++){x=list3.get(i);cout<<x<<"";}cout<<endl;return0;}

线性表

顺序表及实现

链表及实现一元多项式字符串稀疏矩阵顺序表插入、删除时间代价的分析，可以看出其时间复杂度是线性阶的，而且会引起大量已存储元素的位置移动。改进方法：链式结构各个元素的物理存放位置在存储器中是任意的，不一定连续。每个元素放在一个独立的存储单元中，元素间的逻辑关系依靠存储单元中附加指针来完成。采用链式存储结构存储的线性表，称为链表。链式结构链表的存储映像图为了清晰看出逻辑关系，以后链表用图(b)来表示。(a)(b)结构体和指针的挑战！结构类型，结构变量，结构指针93classdateT{public:

intyear;

intmonth;

intday;};

dateTd,*p;d.year=2020;d.month=3;d.day=11;p=&d;cout<<p->year<<endl;cout<<p->month<<endl;cout<<p->day<<endl;dp类，对象，指针structdateT{intyear;intmonth;intday;};dp94classdateT{public:

intyear;

intmonth;

intday;};dateTd,*p;

p=newdataT;

p->year=1010;

p->month=1;

d->day=1;deletep;

p->year=2021;//非法

p=&d;//合法structdateT{intyear;intmonth;intday;};dp无名氏结点和链表：结点：datanext链表：头指针head指向了头结点。头结点并不是线性表中的一部分，它的指针字段next给出了首结点的地址。线性表中最后一个结点的指针字段next的值为NULL。顺着头指针head，可以很方便地逐个访问单链表中的所有结点。单链表特点：它的任何一个结点包含了一个存储元素数据值的字段和一个存储该结点的直接后继结点地址的指针字段。提供一个单链表只需要给出头结点的地址即头指针。单链表结点类定义、单链表类定义单链表类：单链表结点类：（linkList.h）classoutOfBound{};template<classelemType>classlinkList;//类的前向说明template<classelemType>classnode{friendclasslinkList<elemType>;private:elemTypedata;node*next;单链表结点类：

public:node():next(NULL){};node(constelemType&e,node*N=NULL){data=e;next=N;};};单链表类：（linkList.h）template<classelemType>classlinkList{private:node<elemType>*head;public:linkList();//构造函数，建立一个空表boolisEmpty()const;//表为空返回true,否则返回false。boolisFull()const{returnfalse;};//表为满返回true,否则返回false。intlength()const;//表的长度单链表类：

elemTypeget(inti)const;//返回第i个元素的值//返回值等于e的元素的序号，从第1个开始，无则返回0.intfind(constelemType&e)const;//在第i个位置上插入新的元素（值为e）。voidinsert(inti,constelemType&e);//若第i个元素存在，删除并将其值放入e指向的空间。voidremove(inti,elemType&e);voidreverse()const;//元素就地逆置voidclear();//清空表，使其为空表~linkList();};链表基本操作的实现代码（linkList.h）//属性赋初值，模板函数用法template<classelemType>linkList<elemType>::linkList()//构造函数，建立一个空表{head=newnode<elemType>();}template<classelemType>boollinkList<elemType>::isEmpty()const//表为空返回true,否则返回false。{if(head->next==NULL)returntrue;returnfalse;}插入操作：将元素x插入在P指针所指结点之后链表基本操作的实现分析摆龙门阵！找核心操作插入总结：遵循“先武装自己，再融入队伍”在内存中创建新结点。武装新结点：将x写入新结点的data字段，p指针所指结点的下一结点地址写入新结点的next字段，使p所指结点的下一结点成为新结点的直接后继结点。将新结点地址写入p的next字段，使新结点成为p所指结点的直接后继结点。链表基本操作的实现分析插入具体语句：tmp=newnode<elemType>();tmp->data=e;tmp->next=p->next;p->next=tmp;或者：tmp=newnode<elemType>(e,p->next);p->next=tmp;链表基本操作的实现分析时间复杂度分析：当P已经指向了插入位置的前一个结点时，插入操作和结点个数无关，时间复杂度为O(1)。或者：一个四合一语句p->next=newnode<elemType>(e,p->next);链表基本操作的实现代码template<classelemType>voidlinkList<elemType>::insert(inti,constelemType&e)//在第i个位置上插入新的元素（值为e）。{if(i<1)return;//参数i越界intj=0;node<elemType>*p=head;

while(p&&j<i-1){j++;p=p->next;}

if(!p)return;//参数i越界p->next=newnode<elemType>(e,p->next);}五步口诀法!删除操作：删除P指针所指结点之后的那个结点链表基本操作的实现分析摆龙门阵！找核心操作删除总结：记住待删除结点地址。将值为x的结点旁路掉。回收原本存储x的结点占用的空间。具体语句：node*q=p->next;p->next=q->next;deleteq;链表基本操作的实现分析时间复杂度分析：当P已经指向了待删除结点的前一个结点时，删除操作和结点个数无关，时间复杂度为O(1)。链表基本操作的实现分析查找操作：找值为x的结点，顺首结点逐个向后检查、匹配。

单链表和顺序表中，时间复杂度都是O(n)。

找第k个结点，顺序表O(1），链表O(n)。其他基本操作：

isFull：因每次只申请一个结点空间，故总为false。clear：除了头结点删除并释放整个单链表中结点，回到初始化后的状态。链表基本操作的实现代码template<classelemType>intlinkList<elemType>::length()const//表的长度{intcount=0;node<elemType>*p;p=head->next;while(p)

{count++;p=p->next;}returncount;}链表基本操作的实现代码template<classelemType>//注意：五步口诀法elemTypelinkList<elemType>::get(inti)const//返回第i个元素的值,首元素为第1个元素{if(i<1)throwoutOfBound();intj=1;node<elemType>*p=head->next;while(p&&j<i){p=p->next;j++;}if(p)returnp->data;throwoutOfBound();}

链表基本操作的实现代码template<classelemType>intlinkList<elemType>::find(constelemType&e)const//返回值等于e的元素的序号，从第1个开始，无则返回0.{inti=1;node<elemType>*p=head->next;

while(p)

{if(p->data==e)break;i++;p=p->next;}if(p)returni;return0;}两种常用技巧：兄弟协同法、首席插入法template<classelemType>//P、Q兄弟协同法voidlinkList<elemType>::clear()//清空表，使其为空表{node<elemType>*p,*q;

p=head->next;head->next=NULL;

while(p)

{q=p->next;deletep;p=q;}}heo…∧head头结点pq最速插入位置—脖子//首席插入法template<classelemType>voidlinkList<elemType>::insert(constelemTypea[],intn){node*tmp,for(inti=0;i<n;i++){tmp=newnode(a[i],head->next);head->next=tmp;}}114a[5]={1,3,5,7,9}971…∧head头结点首结点练习：对一个单链表进行就地逆置---摆龙门阵115heo…∧head头结点首结点存储映像图：olh…∧head头结点首结点helloolleh116heo…∧head头结点heo…∧head头结点pqpqeho…∧head头结点pq“兄弟协同法”+“首席插入法”实现单链表的就地逆置template<classelemType>voidlinkList<elemType>::reverse(){node<elemType>*p,*q;//兄弟俩协同p=head->next;head->next=NULL;while(p){q=p->next;p->next=head->next;head->next=p;//首席插入p=q;}}常见错误：指针p未被初始化或者为空，读取其指向的字段如p->data，如循环检查p所指的结点中值是否x，可用while(p&&p->data!=x)p=p->next。p原本指向了一个结点，但其指向的结点空间已经释放，仍要读取其所指结点的字段。如p=head;deletep;p=p->next;p->next非法访问了不能访问的内存空间。末结点的next不再指向空，而是指向头结点。单循环链表空单向循环链表，只有头结点。优点：从表中任何一个结点出发，都可以顺next指针访问到所有结点。为了循环方便，不带头结点的单循环链表居多，head直接指向首结点。不带头结点的单循环链表空单向循环链表，head指向空。每个结点有prior和next两个指针，分别指向直接前驱和直接后继结点双向链表空双向链表，只有头、尾结点。优点：根据待查元素在前或后半段，决定自head向后还是自tail向前。不带头、尾结点的双向循环链表双向循环链表空双向链表双向链表node*tmp=newnode()//（1）tmp->data=x;//（2）tmp->prior=p;tmp->next=p->next;tmp->prior->next=tmp;//（3）tmp->next->prior=tmp;//（4）插入：将元素x插入到p指针所指结点之后。如果新结点插入在首结点位置，操作又有不同，请课后练习。

线性表

顺序表及实现链表及实现一元多项式字符串稀疏矩阵在数学上，一元多项式一般表示为如下形式：pn(x)=p0+p1x+p2x2+…+pnxn在计算机内实现时，可以用线性表来表示:p=(p0，p1，p2，…，

pi

…，pn)，其中结点pi(0≤i≤n)表示幂为i项的系数。一元多项式一种方法是：为了表示系数和项的对应关系。i次幂项的系数pi存放在下标为i的数组结点中，即便pi为0，相应的数组分量也不能挪作它用。另外一种处理方法是：只存储系数不为0的项，每一项除了存储它的系数，还要存储它的幂。

两个多项式的加法处理起来比第一种方法复杂。

用数组时，要预估一个多项式的规模，分配足够的空间。一元多项式存储方法每个结点存放一元多项式中的一项的信息。信息包括该项的系数和幂，零系数项不予存储。链式存储的好处是多项式的项数可以动态地增长，不存在溢出问题。用单链表表示一元多项式。在存储实现时，按照幂由小到大的原则进行，这样该单链表便成为幂有序的单链表。链表中的结点，包含两个部分：数据部分和指针部分。数据部分又包含了系数coef和幂exp二个字段。一元多项式的链式存储一元多项式的链式存储多项式如： A=7+3x+9x8+5x17 B=8x+22x7-9x8两个一元多项式相加对pa和pb所指结点，反复执行如下操作，直至其中一个单链表中的结点全部读取完毕。幂指数相等：如果这二个结点的系数之和为零，和式中不增加项，否则按照相加后的系数、相应幂指数创建一个新结点，作为和式单链表C的末结点，pa、pb后移。指针pa幂指数小：按pa指向的结点的系数、幂指数创建一个新结点作为单链表C的末结点，pa后移，pb不变。指针pb幂指数小：按pb指向的结点的系数、幂指数创建一个新结点作为单链表C的末结点，pb后移，pa不变。两个一元多项式相加将非空多项式单链表(可能是A的单链表，也可能是B的单链表)中的剩余结点，按序逐个创建新结点插入在单链表C的尾部多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）#ifndefPOLYNOMIAL_H_INCLUDED#definePOLYNOMIAL_H_INCLUDED#include"linklist.h"usingnamespacestd;多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）structType{intcoef;//系数intexp;//幂指数}template<classelemType>structNode{elemTypedata;Node*next;};分开定义结点的好处多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）template<classelemType>structPolynomial{private:Node<elemType>*head;elemTypestop_flag;//用于判断多项式输入结束。public://从用户处获取结束标志并初始化多项式Polynomial(constelemType&stop);voidgetPoly();//读入一个多项式。多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）voidaddPoly(constPolynomial&L1,constPolynomial&L2);

//L3=L1+l2。voiddispPloy();//显示一个多项式voidclear();//释放多项式空间~Polynomial(){clear();deletehead;};};多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）//getStop为外部函数，即非类成员函数template<classelemType>voidgetStop(elemType&stopFlag)//从用户处获取结束标志{intc,e;cout<<"请输入系数、指数对作为结束标志,如(0,0):";cin>>c>>e;stopFlag.coef=c;stopFlag.exp=e;}多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）template<classelemType>Polynomial<elemType>::Polynomial(constelemType&stop)

//初始化多项式{head=newNode<elemType>();stop_flag.coef=stop.coef;stop_flag.exp=stop.exp;}

template<classelemType>voidPolynomial<elemType>::getPoly()//读入一个多项式{Node<elemType>*p,*tmp;elemTypee;多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）p=head;cout<<“请按照指数从小到大输入系数、指数对，”

<<最后输入结束标志对结束：\n";cin>>e.coef>>e.exp;

while(true){if((e.coef==stop_flag.coef)&&(e.exp==stop_flag.exp))break;多项式Polynomial及其部分基本操作的声明、定义（polynomial.h）

tmp=newNode<elemType>();tmp->data.coef=e.coef;tmp->data.exp=e.exp;tmp->next=NULL;p->next=tmp;p=tmp;

cin>>e.coef