数据结构笔记1 线性表-顺序表示_!l.elem什么意思

预定义：

一、线性表的顺序表示

一些操作：

1. 线性表的初始化（参数为引用）

//下列：函数返回类型  函数名称初始化线性表  参数表（参数类型 引用参数）
Status InitList_Sq(SqList &L) {    
//构造一个空的线性表
    L.elem = New ElemType[MAXSIZE];      //动态分配L.elem的内存，类型为ElemType，个数为MAXSIZE
    //也可以写：
    //L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE];
 
    if(!L.elem)                          //如果分配的地址值为空，则意味着分配失败
        exit(OVERFLOW);                  //exit(x)（x不为0）都表示异常退出，此时为-2 具体见链接
    //异常处理        
 
    L.length = 0；                       //初始化的线性表长度为0
 
    return OK;                           //成功，返回1
}

C语言中的exit()函数_春卷同学的博客-CSDN博客_c语言exithttps://blog.csdn.net/Rex_WUST/article/details/88372481

2.销毁线性表（参数为引用）

void DestroyList(SqList &L){
    if(L.elem) delete  L.elem;   //释放存储空间。要先判断是否存在。
    //delete: C++的语法。
    //C:free(L.elem);
}

3.清空线性表

Status ClearList(SqList &L){
    L.length = 0;             //将线性表长度置0
}      

4.求线性表的长度

Status GetLength(SqList L){    // 这里并不需要对L进行修改
    return(L.length);
}      

5.判断线性表长度

int IsEmpty(SqList L){
    if(L.length == 0) return 1;
    else return 0;
}

6.顺序表的取值（随机存取），根据位置i获取相应位置数据元素的内容

int GetElem(int i,SqList L,int &e){
    if(i<1 || i>L.length) return ERROR;
    //异常处理，判断i是否合理
    e = L.elem[i-1];         //第i个元素对应下标i-1（第i-1的单元存储着第i个数据）
    return OK;
}

  其算法复杂度是常量阶O(1)，只执行一次。

7.按值查找元素

int LocateElem(SqList L,ElemType e){
//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）
    for(int i=0; i<L.length; i++)
        if(L.elem[i] == e) return i+1;  //查找成功，返回序号
    return 0;       //查找失败，返回0
}
 
 
//用while语句实现
int LocateElem(SqList L,ElemType e){
//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）
    int i=0;
    while(i<L.length && L.elem[i] != e)  i++;
    if(i<L.length) return i+1;
    return 0;       //查找失败，返回0
}

时间复杂度：

基本操作：L.elem[i] == e，比较次数不定，取决于要查找的值 

平均查找长度ASL：

 ∴T(n)=O(n)

 8.顺序表的插入

算法思想：

Status ListInsert_Sq(SqList &L, ElemType e, int i) {
    if (i<1 || i>L.length )  return ERROR;  //i值不合法
    if (L.length == MAXSIZE) return ERROR;  //当前存储空间已满
    for(int j = L.length-1; j>=i-1; j--)    //j是数组下标
        L.elem[j+1] = L.elme[j];            //插入位置以及之后的元素后移
    L.elem[i-1] = e;                        //放入新元素，第i个下标为i-1
    L.length++;                             //表长加一
    return OK;
}

复杂度O（n）

9.顺序表的删除

 

Status ListDelete_Sq(Sq List &L, Elem Type &e,int i){
    if (i<1 || i>L.length) return ERROR;            //i不合法    
    e = L.elem[i-1];
    for(int j = i; j<=L.length-1; j++)              //被删除的元素之后的元素前移
        L.elem[j-1] = L.elem[j];
    L.length--;                                     //表长减一
    return OK;
}