线性表

一、线性表定义

　　线性表（List）:由零个或多个数据元素组成的有限序列。（类似生活中排队）

关键点：

（1）序列：元素之间先来后到，有顺序（2）若元素多个，第一个元素无前驱，最后一个无后继，其他元素都有且只有一个前驱和后继（3）线性表强调有限的

　例：a1,...,ai-1,ai.ai+1,...an，表中ai-1是ai的直接前取元素，ai+1是ai的直接后继元素。

线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

二、抽象数据类型

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。对已有的数据类型进行抽象，就有了抽象数据类型。

抽象数据类型（Abstract Date Type,ADT）是指一个数据模型及定义在该模型上的一组操作。取决于一组逻辑特性，而与其在计算机内部如何表示和实现无关。

ADT 抽象数据类型名
Data 
     数据元素之间逻辑关系的定义
Operation
    操作
endADT

Operation:

InitList(*L)//初始化操作，建立一个空的线性表
ListEmpty(L)//判断线性表是否为空表，若线性表为空，返回true，否则返回false
ClearList(*L)//将线性表清空
GetElem(L,i,*e)//将线性表L中的第i个位置元素值返回给e
LocateElem(L,e)//在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0返回表示失败。
ListInsert(*L.i,e)//在线性表L中第i个位置插入新元素e
ListDelete(*L,i,*e)//删除线性表L中第i个位置元素，并用e返回其值。
ListLength(L)//返回线性表L的元素个数。

三、线性表的存储结构（顺序存储结构和链式存储结构）

顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。（数组）

/*线性表顺序存储结构代码*/
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
      ElemType data[MAXSIZE];
      int length;//线性表当前长度
}SqList;   
数组的长度一般初始化后不变，而线性表的当前长度是线性表中元素的个数，是会变化的。

注意：数组地址计算从0开始，线性表从1开始的。

地址计算方法：

线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是：LOC(ai+1)=LOC(ai)+c

进一步得：LOC(ai)=LOC(a1)+(i-1)*c (a1对应的下标0)，存储时间性能O（1）,称为随机存储结构。

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操做结果：用e返回L中第i个数据元素的值
getElem.c

typedef int Status;
Status GetElem(sqList L,int i,ElemType *e)
{
      if(L.length==0 || i<1 || i>L.length)
      {
            return  ERROR;
      }
      *e = L.data[i-1];
     return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length == MAXSIZE) //顺序线性表已经满了
    {
        return ERROR;
    }
    if(i<1 || i>L->length+1)  //当i不在范围内
    {
        return  ERROR;
    }
    if(i<=L->length)   //若插入数据位置不在表尾
    {
        //将要插入位置后数据元素向后移动一位
        for(k=L->length-1;k>=i-1;k--)
        {
            L->data[k+1]=L->data[k];   
        }
    }
    L->data[i-1] = e;  //将新元素插入
    L->length++;
    return OK;
}

Status ListDelete(SqList *L,int i, ElemType *e)
{
    int k;
    if ( L->length == 0 )
    {
        return ERROR;     
    }  
    if( i<1 || i>L->length)
   {
        return ERROR;
   }
   *e = L->data[i-1];
    
   if(i< L->length)
  {
       for(k=i;k<L->length;k++)
      {
          L->data[k-1] = L->data[k];   
      }
   }
  L->length--;
  return OK;
}

插入和删除的时间复杂度：

最好情况：最后一个位置，不需要移动任何元素，O(1)

最坏情况：第一个元素，O(n)

平均情况：取中间值O((n-1)/2) 简化后还是O(n)