MENU

数据结构 - 顺序表

February 7, 2021 • Read: 301 • 数据结构

顺序表的定义

顺序表:用顺序存储的方式来实现线性表

顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。

如何知道一个数据元素的大小?

  • C语言:sizeof(ElemType)

sizeof(int) = 4B

顺序表的实现方式

静态分配

#define MaxSize 10     // 定义最大长度
typedef struct{                
    ElemType data[MaxSize];// 用静态的“数组”存放数据元素
    int length;// 顺序表的当前长度
}SqList;// 顺序表的类型定义(静态分配的方式)

当定义了数组的长度就无法改变

Q:如果“数组”中数据存满了怎么办?

A:可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的)

Q:如果刚开始就声明一个很大的内存空间呢?

A:会存在很浪费的问题

#include <stdio.h> 
#define MaxSize 10 // 定义最大长度
typedef struct{
    int data[MaxSize]; // 用静态的“数组”存放数据元素
    int length; // 顺序表的当前长度
}SqList;        // 顺序表的类型定义

// 基本操作 - 初始化一个顺序表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++){
        L.data[i] = 0; // 将所有数据元素设置为默认初始值
    }
    L.length = 0;      // 顺序表的初始长度为0
}

int main(){
    SqList L;     // 声明一个顺序表
    InitList(L);// 初始化顺序表
    // ... 未完待续,后续操作
    return 0;
}

动态分配

#define InitSize 10  //顺序表的初始长度
typedef struct{    //指示动态分配数组的指针
    ELemType *data; //顺序表的最大容量
    int MaxSize;  // 顺序表的当前长度
    int length;  // 顺序表的类型定义(动态分配的方式)
} SqList;
  • C语言中 分别使用 --mallocfree函数。

malloc函数返回一个指针需要强制转型为你定义的数据元素的类型指针

L.data = (ElemType *) malloc (sizeof(ElemType*) * InitSize);

    • ElemType *表示你要申请的内存的数据类型
    • sizeof(ElemType*) * InitSize表示的是申请的内存空间大小
    • C++中使用newdelete关键字
    #include <stdlib.h>
    #define InitSize 10 //默认的最大长度
    typedef struct{
        int *data;         // 指示动态分配数组的指针
        int MaxSize;    // 顺序表的最大容量
        int length;        // 顺序表的当前长度
    }SeqList;
    
    void InitList(SeqList &L){
        // 用malloc函数申请一片连续的存储空间
        L.data=(int *) malloc(InitSize * sizeof(int));
        L.length =0;
        L.MaxSize =InitSize;
    }
    
    // 增加动态数组的长度
    void IncreaseSize(SeqList &L,int len){
        int *p=L.data;
        L.data=(int *)malloc ((L.MaxSize+len)*sizeof(int));
        // 上面的malloc返回一个指针,需要强制转换
        for(int i=0;i<L.length;i++){
            L.data[i]=p[i]; // 复制到新的空间
        }
        L.MaxSize=L.MaxSize+len;
        free(p); // 释放空间 
    }
    
    int main(){
        SeqList L; // 声明一个顺序表
        InitList(L); // 初始化顺序表
        // ……往顺序表中随便插入几个元素
        IncreaseSize(L,5);
        return 0;
    }

    顺序表的特点

    • 随机访问:即可以在O(1)时间内找到第i个元素。
    • 存储密度高:每个节点只存储数据元素
    • 拓展容量不方便(即采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
    • 插入、删除操作不方便,需要移动大量的元素

    顺序表的插入

    ListInsert(&L,e):插入操作。在表L中第i个位置上插入指定元素e。

    以下代码是基于静态分配实现的顺序表,在动态分配实现上也雷同

    #define MaxSize 10 // 定义最大长度
    typedef struct{
        int data[MaxSize]; // 用静态的“数组”存放数据元素
        int length;        // 顺序表的当前长度
    }SqList;     // 顺序表的类型定义
    
    void ListInsert(SqList &L,int i,int e){
        for(int j=L.length;j>i;i--){
            L.data[j]=L.data[j-1];
        }
        L.data[i-1]=e;// 在位置i处放入e  注意位序、数组下标的关系,并从后面的元素依次移动
       // 这里的i为数组的位序,是从1开始的
        L.length++; // 长度加1
    }
    
    int main(){
        SqList L;    // 声明一个顺序表
        InitList(L); // 初始化顺序表
        ListInsert(L,2,3);
        return 0;
    }

    当调用以上的代码是,避免调用者的不规范时使用,比如:i 的范围应该在【1~length+1】,所以我们可以如下的完善相关的代码逻辑,重新编写插入函数如下:

    bool ListInsert(SqList &L,int i,int e){
        if(int < 1 || i > L.length + 1){
            return false; // 判断i的范围是否有误
        }
        if(L.length >= MaxSize){
            return false; // 当前的存储空间已满,不能插入
        }
        for(int j=L.length;j>i;j--){
            L.data[j]=L.data[j-1]; // 将第i个元素及以后的元素后移
        }
        L.data[i-1] =e; // 将第i个元素及之后的元素后移
        L.length ++;  // 长度加1
        return true;

    好的算法,应该具有“健壮性”,能够很好的处理异常情况,并给使用者反馈!

    • 插入操作的时间复杂度:

    问题规模:n = length(表长)

    • 最好情况:新元素插入到表尾,不需要移动元素

      i = n + 1,循环0次;最好时间复杂度 = O(1)

    • 最坏情况:新元素插入到表头,需要将原有的n个元素全都向后移动

      i = 1,循环n次;最坏时间复杂度 = O(n)

    • 平均情况:假设新元素插入到任何一个位置的概率相同,即$ i =1,2,3...,length+1$的概率是$$p=\frac {1} {n+1}$$

      i = 1,循环n次;

      i = 2,循环n-次;

      ...

      i = n+1,循环0次

      平均循环次数 = $$np + (n+1)p +(n-2)p +...+1·p = \frac {n(n+1)}{2}\frac {1}{n+1}=\frac {n}{2}$$ ⇨平均时间复杂度 = O(n)

    顺序表的删除

    ListDelete(&L,i,&e):删除操作。删除表L中的第i个位置的元素,并用e返回删除元素的值。

    bool ListDelete(SqList &L,int i,int &e){
        if(i<1||i>L.length){
            return false;      // 判读i的范围是否有效
        }
        e=L.data[i-1]        // 将要被删除的元素赋值给e
        for(int j=i<j<L.length;j++){
            L.data[j-1]=L.data[j];
        }
        L.length--;         // 顺序表的长度减1
        return true;
    }
    
    int main(){
        SqList L;        //声明一个顺序表
        InitList(L);     //初始化一个顺序表
        // ...此处省略一些代码,插入几个元素
        int e = -1;        //用变量e把删除的元素“带回来”
        if(ListDelete(L,3,e)){
            printf("已删除第3个元素,删除的元素值为=%d\n",e);
        }else{
            printf("位序i不合法,删除失败\n");
        }
        return 0;
    }
    • 删除操作的时间复杂度

      • 最好情况:删除表尾元素,不需要移动其他元素

      i = n,循环0次;最好时间复杂度 = O(1)

      • 最坏情况:删除时表头元素,需要将后续的n-1元素全都向前移动

      i = 1,循环n-1次;最坏时间复杂度 = O(n)

      • 平均情况:假设删除任何一个元素的概率相同,即 i = 1,2,3,… 的概率都是$$p = \frac {1} {n}$$

      i = 1,循环n-1次;

      i = 2,循环n-2次;

      i = 3,循环n-3次;

      ……

      i = n,循环0次

      平均循环次数 = $$(n-1)p + (n-2)p + ... +1·p = \frac {n(n+1)}{2}\frac {1}{n} =\frac{n-1}{2}$$⇨平均时间复杂度 = O(n)

    顺序表的查找

    按位查找

    GetElem(L,i):按位查找操作。获取表中第i个位置的元素的值。

    • 静态分配实现:
    #define MaxSize 10             // 定义最大的长度
    typedef struct {
        ElemType data[MaxSize]; // 用静态的“数组”存放数据元素
        int length;                // 顺序表的当前长度
    }SqList;                    // 顺序表的类型定义(静态分配的方式)
    
    ElemType GetElem(SqList L,int i){
        return L.data[i-1];     // 因为这里传入的是查找的位序,所以是i-1
    }
    • 动态分配实现:
    #define InitSize  10     // 顺序表的初始长度
    typedef struct{
        ElemType *data;        // 指示动态分配数组的指针
        int MaxSize;        // 顺序表的最大容量
        int length;            // 顺序表的长度
    }SeqList;                // 顺序表的类型定义(动态分配方式)
    
    ElemType GetElem(SeqList L,int i){
        return L.data[i-1];
    }

    时间复杂度:O(1)

    由于顺序表的各个元素在内存中连续存放,因此可以根据起始位置和数据元素大小立即找到第i个元素 -- “随机存取”特性

    按值查找

    LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值得元素。

    #define InitSize  10     // 顺序表的初始长度
    typedef struct{
        ElemType *data;        // 指示动态分配数组的指针
        int MaxSize;        // 顺序表的最大容量
        int length;            // 顺序表的长度
    }SeqList;                // 顺序表的类型定义(动态分配方式)
    
    // 在顺序表L中查找第一个元素值等于e的元素,并返回其位序
    int LocateElem(SeqList L,ELemType e){
        for(int i = 0; i<L.length;i++){
            if(L.data[i]==e){
                return i+1;  // 数组下标为i的元素值等于e,返回其位序i+1
            }
        }
        return 0;            // 退出循环,说明查找失败!
    }

    当查找的元素为`结构体类型或复杂类型不能使用==来比较!

    Tips:

    《数据结构》考研初试中,手写代码可以直接使用 “==”,无论ElemType是基本数据类型还是结构类型!

    时间复杂度:

    问题规模:n = L.length(表长)

    • 最好情况:目标元素在表头

    循环1次;最好时间复杂度 = O(1)

    • 最坏情况:目标元素在表尾

    循环n次;最坏情况复杂度 = O(n)

    • 平均情况:假设目标元素出现在任何一个位置的概率相同,都是$$\frac{1}{n}$$

    目标元素在第1位,循环1次

    目标元素在第2位,循环2次

    ……

    目标元素在第n位,循环n次

    平均循环次数 = $$1·\frac{1}{n} + 2·\frac{1}{n} +……+n·\frac{1}{n} =\frac{n(n+1)}{2}\frac{1}{n} = \frac{n+1}{2}$$ ⇨平均时间复杂度 = O(n)

    版权声明:文章转载请注明来源,如有侵权请联系删除!

    Last Modified: April 12, 2021
    Archives QR Code Tip
    QR Code for this page
    Tipping QR Code