【408数据结构复习记录】顺序表

顺序表属于线性表
线性表的核心功能一般有：
InitList(&L) ：
Length(L) ：
LocateElem(L,e)：
GetElem(L,i)：
ListInsert(&L,i,e)：
ListDelete(&L,i,&e)：
PrintList(L)：
Empty(L)：
DestroyList(&L)：

• 顺序表实现
• 知识点
• 代码实现

顺序表
物理结构：顺序存储
特点：
随机访问，可以在O(1)时间内找到第i个元素
存储密度高，每个节点只存数据元素
拓展容量不方便（即便是采用动态分配的方式，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量元素。

代码如下：

#include 

using namespace std;

//静态分配
#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int length;
}SSqlist;

//初始化一个顺序表，主要是给他赋初值，防止内存中有遗留脏数据。
void SInitList(SSqlist &L){
    for(int i=0;i
        L.data[i]=0;
    }
    L.length=0;
}

//往第i个位置插入数据e，也就是说要把第i位后面的元素向后移
bool SListInsert(SSqlist &L,int i,int e){
//    要考虑好健壮性
    if(i<1||i>L.length+1){
        return false;
    }
    if(L.length>=MaxSize){
        return false;
    }
    for(int j=L.length;j>=i;j--){
        L.data[j]=L.data[j-1];//其平均时间复杂度为O(n)
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}
//删除后要把该元素后面的元素向前移动
bool ListDelete(SSqlist &L,int i,int&e){
    if(i<1||i>L.length){
        return false;
    }
    e=L.data[i-1];
    for(int j=i-1;j
        L.data[j]=L.data[j+1];
    }
    L.length--;
    return true;
}

//按位查找
int GetElem(SSqlist L,int i){
    return L.data[i-1];
}

int locateElem(SSqlist L,int e){
    for(int i=0;i
        if(L.data[i]==e){
            return i-1;
        }
    }
    return 0;
}

//动态分配
#define InitSize 10
typedef struct{
    int *data;
    int MSize;
    int length;
}SqList;

void Initlist(SqList &L){
    L.data=new int[InitSize];
    L.length=0;
    L.MSize=InitSize;
}

void IncreaseSize(SqList &L,int len){
    int *p=L.data;
    L.data=new int[InitSize+len];//这里其实是给data另外开了一个容量为[InitSize+len]的空间。
    for(int i=0;i
        L.data[i]=p[i];
    }
    L.MSize=L.MSize+len;
    delete p;
}

bool ListInsert(SqList &L,int i,int e){
//    要考虑好健壮性
    if(i<1||i>L.length+1){
        return false;
    }
    if(L.length>=MaxSize){
        return false;
    }
    for(int j=L.length;j>=i;j--){
        L.data[j]=L.data[j-1];//其平均时间复杂度为O(n)
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

int main()
{
    SqList L1;
    Initlist(L1);
    L1.data[0]=3;
    L1.data[1]=4;
    IncreaseSize(L1,10);
    return 0;
}