顺序表

顺序表的定义

• 线性表的顺序存储又称顺序表
• 它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻

线性表的顺序存储类型描述

• 静态分配

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize]; // 顺序表的元素
    int length;             // 顺序表的实际长度
} SqList;                   // 顺序表类型的定义

• 动态分配

#define InitSize 100
typedef struct {
    ElemType * data;
    int MaxSize,length;     //最大容量和当前size
} SqList; 

// C的初始动态分配语句
L.data = (ElemType *)malloc(sizeof(SqList) * InitSize);

// C++的初始动态分配语句
L.data = new ElemType[InitSize];

顺序表上基本操作实现以及事件复杂度分析

• 插入操作

/**
 *  方法名:ListInsert
 *  参数1:SqList &L     顺序表
 *  参数2:int i         插入位置
 *  参数3:ElemType e    插入内容
 *  要求在 i (1 <= i <= L.length + 1) 个位置插入新元素e
 */
 bool ListInsert(SqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1)              // 判断 i的范围是否有效
        return false;
    if(L.length >= MaxSize)                    // 存储空间已满，不能插入
        return false;
    for(int j = L.length; j >= i; j --) {      // 将第 i个元素之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;                         // 在位置 i处放入e
    L.length++;                                // 线性表长度加1
    return true;
}

时间复杂度分析:
最好情况: 表尾插入，没有元素移动时间复杂度为O(1)
最坏情况: 表头插入，所有元素都移动，时间复杂度为O(n)
平均情况: O(n)
分析：
插入到哪个位置就把从那个位置之后所有的值都往后移动一位；
平均移动次数 = 总次数 / 移动情况个数；
移动情况个数: 表的长度为n，由于表头和表尾都可以插入，所以插入的情况有(n + 1)种；
总次数: 在表尾插入移动的次数为0次，在表头插入移动的次数为n次，一共有(n + 1)次种情况可以插入，所以首项为(n + 1)，末项为0，项数为(n + 1)，所以总次数为(n + 1)(n + 0) / 2；
平均移动次数 = ((n + 1)(n + 0) / 2) / (n + 1) = n / 2

• 删除操作

/**
 *  方法名:ListDelete
 *  参数1:SqList &L     顺序表
 *  参数2:int i         删除位置
 *  参数3:ElemType &e   被删除内容用引用变量e返回
 *  要求删除在 i (1 <= i <= L.length) 个位置元素
 */
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)              // 判断范围是否有效
        return false;
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++) {     // 把所有元素往前移动
        L.data[j - 1] = L.data[j]; 
    }
    L.length --;                            // 线性表长减1
    return true;
}

时间复杂度分析:
最好情况: 表尾删除，没有元素移动时间复杂度为O(1)
最坏情况: 表头插入，所有元素都移动，时间复杂度为O(n)
平均情况: O(n)
分析:
删除哪个元素就把那个元素后面所有的值往前移一位；
平均移动次数 = 总次数 / 移动情况个数；
移动情况个数: 表的长度为n，可以删除的情况有n种
总次数: 在表尾删除移动的次数为0次，在表头删除移动的次数为n - 1次，一共有n种删除的情况，所以首项为(n - 1)，末项为0，项数为n，所以总次数为(n - 1)n / 2；
平均移动次数 = （(n - 1)n / 2）/ n = (n - 1) / 2

• 查找元素

/**
 *  方法名:LocateElem
 *  参数1:SqList L      顺序表
 *  参数3:ElemType e    需要查找的内容
 */
 int LocateElem(SqList L, ElemType e) {
    int i = 0;
    for(i = 0;i < L.length; i++) {  
        if(L.data[i] == e) 
            return i + 1;   // 返回位置
    }
    return 0;
 }

时间复杂度分析:
最好情况: 查找表头元素，时间复杂度为O(1)
最坏情况: 查找表尾元素，需要把所有元素都遍历一遍，时间复杂度为O(n)
平均情况: O(n)
分析:
平均查找次数 = 总次数 / 查找的情况个数
移动情况个数: 顺序表长度为n，查找情况一共有n种，
总次数: 如果需要查找的元素在表头需要查找1次，如果需要查找的元素在表尾需要查找n次，所以首项为n，末项为1，一共有n项，总次数为(n + 1)n / 2，
所以平均查找次数 = ((n + 1)n / 2) / n = (n + 1) / 2