2.1数据结构基本概念数据结构（datastructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为：数据的逻辑结构独立于计算机，是数据本身所固有的存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。数据结构基本类型数据结构中常用的存贮结构算法（algorithm）1．时间复杂度一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来衡量。例如：for(i=1;i<=n;i++)for(j=1;j<=i;j++)d[i][j]=data[i][j]+1;2．空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。2.2线性数据结构顺序表顺序表类型描述顺序表的主要算法（2）在表中第i个位置插入新元素x算法实现的主要步骤是：①判断插入位置的合理性以及表是否已满。②从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第i个元素为止。③向空出的第i个位置存入新元素x。④最后还要将线性表长度加一。voidInsert(SeqList*L,inti,ElemTypex){if(i<1||i>L->length+1||L->length==L->maxsize)cout<<"插入位置错误或表满";else{for(intj=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];//元素依次后移L->data[i-1]=x;//向第i个位置存入新元素xL->length++;//表长度加一}}（3）在表中删除第i个元素算法实现的主要步骤是：①判断删除位置的合理性。②从第i+1个元素开始，依次向后直到最后一个元素为止，将每个元素向前移动一个位置。这时第i个元素已经被覆盖删除。③最后还要将线性表长度减一。voidDelete(SeqList*L,inti){if(i<1||i>L->length)cout<<"表中没有第"<<i<<"个元素";else{for(intj=i;j<=L->length-1;j++)L->data[j-1]=L->data[j];L->length--;}}（4）在表中查找某个元素下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，算法返回元素的实际位置。intFind(SeqList*L,ElemTypex){for(inti=0;i<L->length;i++){//查找成功，返回元素位置if(L->data[i]==x)returni+1;}return0;//查找失败，返回0}顺序表应用举例用顺序表L1和L2存放需要相加的两个多项式L1(x)和L2(x)，用顺序表L3来存放结果。多项式相加算法可按照下列步骤实现：①设定两个位置变量i和j指向顺序表L1和L2的第一个元素，设定位置变量k表示L3的插入位置，插入位置从1开始。本例中i、j和k初值均为1。②比较i和j两个位置数据元素的指数项，如果L1中第i项指数较小，则将此项数据元素复制到L3的位置k中，并将位置变量i和k后移；如果L2中第j项指数较小，则同样是将此项复制到L3中，并将位置变量j和k后移；如果两项指数项相等，则合并同类项后再将结果复制到L3中，并将位置变量i、j和k同时后移。③当L1或L2中的一个顺序表已经处理完毕，则将另一个顺序表的剩余部分复制到L3中。参照程序[例2-1]