复习结构体

//此声明声明了拥有3个成员的结构体,分别为整型的a,字符型的b和双精度的c
//同时又声明了结构体变量s1
//这个结构体并没有标明其标签
struct 
{
    int a;
    char b;
    double c;
} s1;
 
//此声明声明了拥有3个成员的结构体,分别为整型的a,字符型的b和双精度的c
//结构体的标签被命名为SIMPLE,没有声明变量
struct SIMPLE
{
    int a;
    char b;
    double c;
};
//用SIMPLE标签的结构体,另外声明了变量t1、t2、t3
struct SIMPLE t1, t2[20], *t3;
 
//也可以用typedef创建新类型
typedef struct
{
    int a;
    char b;
    double c; 
} Simple2;
//现在可以用Simple2作为类型声明新的结构体变量
Simple2 u1, u2[20], *u3;

值得强调一点的是 struct SIMPLE t1, t2[20], *t3;
这样去命名实在太麻烦了,我们可以使用 typedef <数据类型> <别名> 简化一下名字,就如同上面最后一个方法,无需再写 struct了

线性表

基本概念

  • 定义:线性表,具有相同数据类型的n(n>=0)个数据元素的有限序列

  • 其中n 为表长,n=0时,线性表为空表。如果使用L命令线性表,那么L=(a1,a2,a3...,an)

  • 线性表中的元素从1开始,位序也就是指在第几个位置

  • 除第一个元素,其余元素都有一个直接前驱

  • 除最后一个元素,其余元素都有一个直接后继

基本操作

创销,增删改查

  • InitList(&L):初始化表,构造一个线性表,分配内存空间
  • DestroyList(&L):销毁操作,销毁一个线性表,释放所占的内存空间
  • ListInsert(&L,i,e),插入,在表的第i个位置上插入元素e
  • ListDelete(&L,i,&e):删除,删除表上第i个位置上的元素e
  • LocateElem(L,e):按值查找
  • GetElem(L,i):按位查找
  • Length(L),求表长
  • PrintList(L),输出
  • Empty(L),判断是否为空表

线性表的物理结构之一 --- 顺序表

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

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

顺序表实现---静态分配

定义:
#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];//开辟空间
    int length;//顺序表当前长度
} SqList;
SqList L;//定义顺序表

为了后续说明方便,我们统一规定,下标从1开始,并不是从0开始,也就意味着data数组下标会比实际下标小 1

初始化:

void InitList(SqList &L) //此处L为引用
{
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;//
    L.length = 0;//长度初始化
}

顺序表实现---动态分配

静态分配的大小一但定义下来的,大小就没办法改变了。

c语言就动态分配内存用的是 malloc()和free(),C++使用的就是 new 和delete.

malloc

需要引入库文件include <stdlib.h>

简单介绍一下malloc 函数 void *malloc(size_t size) 分配所需的内存空间,并返回一个指向它的指针。 ,

如果我们要开辟10个int大小的空间,int * data = (int *)malloc(InitSize * sizeof(int));,我们还需要把void*转换成 int*
如果申请失败,返回NULL

定义:

#define InitSize 10
// 动态分配
typedef struct
{
    int *data;   //顺序表动态分配的指针
    int maxSize; //顺序表最大容量
    int lenght;  // 顺序表当前长度
} SeqList;

初始化函数:

bool InitList(SeqList &L)
{
    L.data = (int *)malloc(InitSize * sizeof(int));
 //开辟内存空间
if(!L.data) return false;
    L.lenght = 0;                                   //当前长度为0
    L.maxSize = InitSize;                           //最大的长度为 initseize
return true;
}

动态顺序表增加长度

动态就体现在可以变换长度

void IncreateSize(SeqList &L, int len)
{
    int *p = L.data;                                        //保持原来数据的地址
    L.data = (int *)malloc((InitSize + len) * sizeof(int)); //开辟新的内存空间
    // 把原来的数据拷贝过来
    for (int i = 0; i < L.lenght; i++)
        L.data[i] = p[i];
    L.maxSize = L.maxSize + len; //重新定义最大长度
    free(p);                     //释放内存空间
}

malloc的亲戚 calloc 和 realloc

  1. calloc
    void* calloc(size_t numElements, size_t sizeOfElement);
    与malloc相似,参数sizeOfElement为单位元素长度(例如:
    sizeof(int)),numElements为元素个数,即在内存中申请numElements *
    sizeOfElement字节大小的连续内存空间。
  2. realloc
    void* realloc(void* ptr, unsigned newsize);
    功能为修改 malloc 和 calloc 分配的空间
    ptr为修改空间的首地址,此时有4种情况
  • 如果ptr为NULL,则函数相当于malloc(new_size)
  • 如果 ptr 所占的空间比 newsize 小 增加ptr空间到newsize 并且把数据也拷贝过去
  • 如果 ptr 所占的空间比 newsize 大 减小ptr的空间到newsize 只保留到newsize内的数据
  • 如果 ptr 所占的空间比 newsize 相等 啥都不做
bool IncreateSize_SqList(SqList& L, int len)
{
    if (len < 0)
        return false;
    int* new_base = (int*)realloc(L.data, (L.SqListSize + len) * sizeof(int));
    if (!new_base) //如果分配空间失败
    {
        return false;
    }
    L.data = new_base;
    L.SqListSize += len;
    return true; 
}

顺序表的特点

  • 随机访问,即可以在O(1) 时间内找到第i个元素。
  • 存储密度高,每个节点仅仅存储 数据元素
  • 拓展容量很麻烦,即使使用动态分配的方法,拓展长度的时间复杂度还是比较高
  • 插入,删除操作,不方便,需要移动大量元素。

顺序表的实现 ---- 插入,删除

下面的都是基于静态分配顺序表

在第i插入位置上插入数据

我们要在第i的位置上插入指定元素e,那么就需要把第i个位置后面数据向后移动(从最后一个开始移动)。
注意for循环时把先把插入点数据向后移动一位,注意我们顺序表的编号时从0开始的,所以最后一个元素的数组下标是 Lenght-1 ,被插入点的元素数组下标是i-1

void ListInsert(SqList &L, int e, int i)
{
        // 先把插入点数据向后移动一位
        for (int j = L.length-1; j >= i-1; j--)
        {
            L.data[j+1] = L.data[j];//后移元素一个位置
        }
        //  在把给插入点赋值
        L.data[i-1] = e;
        L.length++;
}

当然,这个我们更加希望我们能够知道是否插入成功,所以最好加一个返回值。

插入失败的情况有:

  1. 插入点 i 不合理, i>L.length+1;||i<1
  2. 顺序表已满 , L.length>=MaxSize;
bool ListInsert(SqList &L, int e, int i)
{
    if (i > = L.length || i < 1)
        return false;
    if (L.length> =MaxSize)
        return false;
    // 先把插入点数据向后移动一位
    for (int j = L.length-1; j > =i-1; j--)
    {
        L.data[j+1] = L.data[j];
    }
    //  在把给插入点赋值
    L.data[i-1] = e;
    L.length++;
return true;
}

当然 这是对静态顺序表来说的,动态顺序表如果存储空间不够了,应该自动增加存储空间。

// 插入元素
bool Insert_SqList(SqList& L, int i, int e)
{
    if (i < 0 || i>L.Lenght)
        return false;
    //当顺序表满时 增加空间
    if (L.Lenght == L.SqListSize)
        if(!IncreateSize_SqList(L, AddSize))//如果分配失败返回 false
            return false;
    //插入元素
    int* q=L.data+i-1;   //q为插入的位置
    //开始将插入点和后面的元素向后移动一位
    for (int* p = L.data + L.Lenght - 1; p >= q; p--) //从最后一个元素 向后移动一个位置 直到插入点元素
        *(p + 1) = *p;
    *q = e;
    L.Lenght++;
    return true;
}

这里主要使用的指针,练习自己的对指针的熟悉程度。

我们现在分析一下时间复杂度

根据第一章的知识,我们只需要关注最深层次的循环即可。

问题规模:L.length

  • 最好的情况就是,j=i-1,也就是 i =length+1,循环一次就好了。即最好时间复杂度为O(1);

  • 最坏的的情况就是,i=1;要循环n次,即最坏时间复杂度为O(n);

  • 平均的情况就是每一次的几率相等,也就是 1,2,3.....length+1 每一次出现的概率为 1/n+1;

    那么也就说 平均循环次数: (n+1)n/2*1/(n+1)=n/2 ,也就是 T(n)为O(n);

删除第i个位置元素 并返回删除元素

用传入参数 &e 带回删除的元素。
值得强调的是删除第i个元素需要移动第i个元素后面的所有元素(从数组下标i开始)提前一个位置(直到 表尾元素序号length结束)。

bool ListDelete(SqList &L, int i,int &e)
{
    if (i >= L.length || i < 1)
        return false;
    // 把删除点后面的数据向前移动一格
    e=L.data[i-1];
    for (int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

时间复杂度,和前面差不多,

  • 最好的情况 :删除表位的元素,不需要移动元素 T(n)=0=O(1)

  • 最坏的情况:删除表头的元素,需要把后续的n-1个元素都移动

    循环n-1; T(n)=O(n)

  • 平均的情况: 循环 0,1,2,3.....n-1次的概率都是为 1/n,平均循环次数为 n(n-1)/2n =(n-1)/2

    T(n)=O(n)

查找

按位查找
int GetElem(SqList L, int i)
{
    if (i < 1 || i > L.length + 1)
        return 0;
    return L.data[i];
}

最好最坏都一样,所以平均复杂度等于他们等于 O(1)

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

时间复杂度,其实和插入的情况一致的,不再赘述了。

顺序表简答实现

分享 我自己简单使用c语言实现了一下动态顺序表,

#include <stdio.h>
#include <stdlib.h>

/*** 动态顺序表  下标从1 开始***/

// 动态顺序表
#define InitSize 20 // 顺序表初始空间分配大小
#define AddSize 5   // 顺序表存储空间分配增量

//顺序表的定义
typedef struct
{
    int* data;      //存储空间的基地址
	int Lenght;     //顺序表的长度
    int SqListSize; //当前顺序表的存储容量
} SqList;

bool Init_SqList(SqList& L);                  //初始化顺序表
bool IncreateSize_SqList(SqList& L, int len); //增加顺序表的存储空间大小len
bool Insert_SqList(SqList& L, int i, int e);  //在第i个位置上插入元素e
bool Delete_SqList(SqList& L, int i, int& e); //删除第i个元素,并用e返回删除元素
bool GetElem_SqList(SqList L,int i,int& e);         //获取第i个位置上的元素
bool Empty_SqList(SqList L);                  //判断顺序表是否为空
bool Destory_SqList(SqList& L);               //销毁顺序表

//简单测试一下
void test()
{
    SqList L;
    int e;
    Init_SqList(L);
    printf("L初始化完成 ^_^\n");
    for (int i = 1; i <= 25; i++)
    {
        Insert_SqList(L, i, i);
    }
    printf("添加数据完成,L.lenght :%d\n",L.Lenght);
    for (int i = 1; i <= L.Lenght; i++)
    {
        GetElem_SqList(L, i, e);
        printf(" 在第%3d个位置上数据为        %3d   \n", i, e);
    }
    
    Delete_SqList(L, 5, e);
    printf("完成删除第5个数据 \n \n");
    for (int i = 1; i <= L.Lenght; i++)
    {
        GetElem_SqList(L, i, e);
        printf(" 在第%3d个位置上数据为        %3d   \n", i, e);
    }
    Destory_SqList(L);
}
int main()
{
    test();
    getchar();
    return 0;
}

//初始化
bool Init_SqList(SqList& L)
{
    //分配空间失败则返回false
    L.data = (int*)malloc(InitSize * sizeof(int));
    if (L.data == NULL)
        return false;
    L.Lenght = 0;
    L.SqListSize = InitSize;
    return true;
}
// 增加顺序表的长度
bool IncreateSize_SqList(SqList& L, int len)
{
    if (len < 0)
        return false;
    int* new_base = (int*)realloc(L.data, (L.SqListSize + len) * sizeof(int));
    if (!new_base) //如果分配空间失败
    {
        return false;
    }
    L.data = new_base;
    L.SqListSize += len;
    return true; 
}
// 判空
bool Empty_SqList(SqList L)
{
    if (L.Lenght == 0)
        return true;
    return false;
}

// 插入元素
bool Insert_SqList(SqList& L, int i, int e)
{
    if (i < 1)
        return false;
    //当顺序表满时 增加空间
    if (L.Lenght >= L.SqListSize)
        if(!IncreateSize_SqList(L, AddSize))//如果分配失败返回 false
            return false;
    //插入元素
    int* q=L.data+i-1;   //q为插入的位置
    //开始将插入点和后面的元素向后移动一位
    for (int* p = L.data + L.Lenght - 1; p >= q; p--) //从最后一个元素 向后移动一个位置 直到插入点元素
        *(p + 1) = *p;
    *q = e;
    L.Lenght++;
    return true;
}

bool Delete_SqList(SqList& L, int i, int& e)
{
    if (i<1 || i>L.Lenght)
		return false;
    int * q = L.data + i - 1;//删除元素的位置
    e = *q;
    int* p = L.data + L.Lenght - 1;
    for (q++; q <= p; q++)// 将删除点后面的元素向前移动一位 直到最后一位;
        *(q - 1) = *q;
    L.Lenght--;
    return false;
}

bool GetElem_SqList(SqList L, int i, int& e)
{
    if (i<1 || i>L.Lenght)
        return false;
    e = *(L.data + i - 1);
    return false;
}

bool Destory_SqList(SqList& L)
{
    if (!(L.data||L.data==0))//如果L.data 已经被销毁了 
        return false;
    free(L.data);
    L.data = NULL;
    L.Lenght = 0;
    L.SqListSize = 0;
    return true;
}

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://blog.yxqin.top/2021/02/04/sqlist
最后更新于:  210  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟