数据结构 - 顺序表

12/27/2020 数据结构C/C++

顺序表的定义

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

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

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

  • 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=1n+1p=\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;            // 退出循环,说明查找失败!
}

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

《数据结构》考研初试中,手写代码可以直接使用 “==”,无论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 Updated: 1/30/2022, 11:35:40 AM