乐趣区

关于数据结构:线性表的顺序表示顺序表

jiezi

1、程序表的定义

​ 程序表是用一组地址间断的存储单元顺次存储线性表中的数据元素。把逻辑上相邻的元素存储在物理地位上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。顺序存储构造如下图所示：

留神：线性表中的位序是从 1 开始的，而数组元素的下标是从 0 开始的。

2、程序表的实现

2.1 动态调配 

#define MaxSize 10  // 定义最大长度
typedef int ElemType;
typedef struct {ElemType data[MaxSize];  // 用动态数组存放数据元素
    int length;              // 程序表的以后长度
} SqList;                    // 程序表的类型定义

/**
 * 基本操作 - 初始化一个程序表
 * @param L
 */
void InitList(SqList &L) {for (int i = 0; i < MaxSize; ++i) {L.data[i] = 0;  // 将所有数据设为默认初始值, 否则会有脏数据
    }
    L.length = 0;  // 程序表初始长度为 0
}

​ 在动态调配时，数组的大小和空间是固定的，无奈更改，一旦空间占满，再退出新的数据就会产生溢出，进而导致程序解体。

思考：如果一开始就申请很大的内存空间呢？？？会存在什么问题？？？ 节约！!

2.2 动态分配 

#define InitSize 10  // 默认的最大长度
typedef int ElemType;
typedef struct {
    ElemType *data;    // 批示动态分配数组的指针
    int MaxSize;  // 程序表的最大容量
    int length;   // 程序表的以后长度
} SeqList;

void InitList(SeqList &L) {
    // 用 malloc 函数申请一片间断的内存空间
    L.data = (int *) malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

用 malloc 函数申请一片间断的存储空间。malloc 函数返回一个指针，须要强制转型为你定义的数据元素类型指针。

减少数组空间的办法：

/**
 * 扩容
 * @param L
 * @param len
 */
void IncreaseSize(SeqList &L, int len) {
    int *p = L.data;
    L.data = (int *) malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {L.data[i] = p[i];         // 将数据复制到新区域
    }
    L.MaxSize = L.MaxSize + len;  // 程序表最大长度减少 len, 事件开销大
    free(p);                      // 开释原来的内存空间
}

留神：动态分配并不是链式存储，它同样属于顺序存储构造，物理构造没有变动，仍然是随机存取形式，只是调配的空间大小能够在运行时动静决定。

3、程序表的特点

① 随机拜访 ，即能够通过首地址和元素序号在 O(1) 工夫内找到第 i 个元素；

②存储密度高，每个节点只存储数据元素；

③逻辑上相邻的元素物理上也相邻，扩容、插入、删除操作不不便。

4、程序表上基本操作的实现 (以动态调配的程序表为例)

4.1 插入操作

在程序表的第 i 个地位插入新元素，要将第 i 个及其后的所有元素往后挪动一个地位，腾出一个空位插入新的元素

逻辑构造：

代码实现：

/**
 * 插入的代码，能解决异常情况
 * @param L
 * @param i
 * @param e
 * @return
 */
bool ListInsert(SeqList &L, int i, int e) {if (i < 1) {  // 判断 i 的范畴是否无效
        return false;
    }
    if (L.length >= L.MaxSize) {       // 以后存储空间已满，要扩容
        IncreaseSize(L, 1);
    }
    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;
}

工夫复杂度：

最好状况：新元素插入到表尾，不须要挪动元素，i = n + 1，循环 0 次，O(1)

最坏状况：新元素插入到表头，须要挪动全副元素，i = 1，循环 n 次，O(n)

均匀状况：假如新元素插入到任何一个地位的概率雷同，即 i = 1,2,3,4……length+ 1 的概率都是 1/(n+1)，均匀工夫 复杂度 O(n)

4.2 删除操作

删除第 i 个元素，须要将第 i + 1 个元素及其前面的所有元素往前挪动一个地位

逻辑构造：

代码实现：

/**
 * 删除数据
 * @param L 要操作的列表
 * @param i 删除第 i 个元素，从 1 开始计数
 * @param e 保留删除的元素
 * @return
 */
bool ListDelete(SeqList &L, int i, int &e) {if (i < 1 || i > L.length) {  // 判断 i 的范畴是否无效
        return false;
    }
    e = L.data[i - 1];           // 将被删除的元素赋值给 e
    for (int j = i; j < L.length; j++) {  // 将第 i 个地位后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--;                // 线性表长度减 1
    return true;
}

工夫复杂度：

最好状况：删除表尾元素，不须要挪动其余元素，i = n，循环 0 次，O(1)

最坏状况：删除表头元素，须要将后续的 n + 1 个元素全副向前挪动，i = 1，循环 n – 1 次，O(n)

均匀状况：假如删除任何一个元素的概率雷同，即 i = 1,2,3,4……length+ 1 的概率都是 1/n，均匀工夫复杂度 O(n)

4.3 按位查找

获取表中第 i 个地位的元素值 

ElemType GetElem(SqList L, int i) {return L.data[i - 1];
}

工夫复杂度 O(1)

4.4 按值查找

在表中查找元素值等于指定值的元素，并返回其位序 

/**
 * 按值查找
 * @param L
 * @param e
 * @return
 */
int LocateElem(SqList L, int e) {for (int i = 0; i < L.length; ++i) {if (L.data[i] == e) {return i + 1;}
    }
    return 0;
}

工夫复杂度：

最好状况：指标元素在表头，循环 1 次，O(1)

最坏状况：指标元素在表尾，循环 n 次，O(n)

均匀状况：假如指标元素呈现在任何一个地位的概率雷同，都是 1/n，均匀工夫复杂度 O(n)

退出移动版