首页 > 代码库 > 线性表的顺序存储结构

线性表的顺序存储结构

1.顺序表:

线性表占用的存储空间=n*sizeof(ElemType)

n为线性表的长度,ElemType为线性表的元素类型,sizeof(ElemType)为每个元素所占存储空间大小(即字节数)

线性表的顺序存储结构利用数组实现,数组的基本类型是线性表中元素类型,数组大小大于等于线性表的长度。

基本运算实现:

(1)建立顺序表

  void CreateList(SqList *&L,ElemType a[],int n)    //由a中的n个元素建立顺序表
 {  int i;
    L=(SqList *)malloc(sizeof(SqList));    //分配存放线性表的空间
    for (i=0;i<n;i++)       //放置数据元素
      L->data[i]=a[i];      //设置长度
    L->length=n;
 }
(2)初始化线性表InitList

   void InitList(SqList *&L)   //引用型指针
  {

     L=(SqList *)malloc(sizeof(SqList));       //分配存放线性表的空间
     L->length=0;      //置空线性表长度为0
  }

时间复杂度为O(1)。

(3)销毁线性表

   void DestroyList(SqList *&L)
  {
     free(L);
  }

时间复杂度为O(1)。

(4)判断线性表是否为空

   bool ListEmpty(SqList *L)
 {
    return(L->length==0);
 }

时间复杂度为O(1)。

(5)求线性表的长度

    int ListLength(SqList *L)
  {
    return(L->length);
  }

时间复杂度为O(1)。

(6)输出线性表

     void DispList(SqList *L)
  {  

    int i;
    for (i=0;i<L->length;i++)
        printf("%d",L->data[i]);
    printf("\n");
  }

时间复杂度为O(L->length)。
(7)求线性表中的某个数据元素值(按位置查找)

    bool GetElem(SqList *L,int i,ElemType &e)
  {    if (i<1 || i>L->length) 

            return false;     //参数错误是返回false
       e=L->data[i-1];    //取元素值
       return true;   //成功找到元素时返回true
  }

时间复杂度为O(1)。

(8)按元素值查找(按值查找)

    int LocateElem(SqList *L, ElemType e)
  {    int i=0;
    while (i<L->length && L->data[i]!=e)

           i++;      //查找元素e
    if (i>=L->length)  return 0;    //未找到时返回0
    else 

         return i+1;     //找到后返回其逻辑序号
  }

时间复杂度为O(L->length)。
(9)插入数据元素

bool ListInsert(SqList *&L,int i,ElemType e)
{  int j;
   if (i<1 || i>L->length+1)
    return false;    //参数错误时返回false
   i--;            //将顺序表逻辑序号转化为物理序号
   for (j=L->length;j>i;j--)    //将data[i]元素后移一个位置
    L->data[j]=L->data[j-1];
   L->data[i]=e;            //插入元素e
   L->length++;            //顺序表长度增1
   return true;            //成功插入返回true
}

时间复杂度为O(n)。
(10)删除数据元素

bool ListDelete(SqList *&L,int i,ElemType &e)
{  int j;
   if (i<1 || i>L->length)     //参数错误时返回false
    return false;
   i--;        //将顺序表逻辑序号转化为物理序号
   e=L->data[i];
   for (j=i;j<L->length-1;j++)  //将data[i..n-1]元素前移
        L->data[j]=L->data[j+1];
   L->length--;              //顺序表长度减1
   return true;              //成功删除返回true
}
时间复杂度为O(n)。

线性表的顺序存储结构