前言

在学习完C语言的所有语法之后,会发现C语言的数组的功能其实没有那么强大,它仅仅能够存储特定类型特定数量的元素,不能够扩容,也不能够插入或者删除某一个元素,所以这样的数据结构其实并不够强大,如果能够实现一个能够完成这几个操作的数据结构就好了。本篇博客将会把数组衍生,使用结构体指针等知识,构建一个顺序表

顺序表的定义

线性表是由同一类型的数据元素构成的有序序列的线性结构。线性表中元素的个数就是线性表的长度,表的起始位置称为表头,表的结束位置称为表尾,当一个线性表中没有元素时,称为空表

线性表一般具有的功能

  • 初始化: 我们可以初始化从而得到一个线性表。
  • 获取指定位置上的元素: 直接获取线性表指定位置上的元素。
  • 获取元素的位置: 获取某个元素在线性表上的位置。
  • 插入元素: 在指定位置上插入一个元素。
  • 删除元素: 删除指定位置上的一个元素。
  • 获取长度: 返回线性表的长度。

定义一个新的数据结构体

由于我们需要设计一个新的数据结构,所以我们提前定义一个该数据结构的结构体。假设该结构体存储的类型是int,把int型起个别名E,如果以后需要存别的类型,就把这个E修改就可以了。

typedef int E;

struct List
{
    E array[10];
    int capacity;
};

这里通过struct声明了一个结构体,其中包括一个E类型的数组,capacity表示该数组的容量

通过该结构体,我们可以编写一个函数用于初始化数组,当我们声明一个List类型的变量的时候,把变量本身作为参数传入初始化函数就能够对其初始化:

void initList(struct List list)
{
    list.capacity = 10;
}

但是我们会发现,这样的函数传进来的变量只是一个局部变量,当函数结束之后内存就会被销毁,所以这样子的初始化函数是有问题的。

最好的方法应该是传入一个List类型变量的指针,然后通过指针初始化变量的值,我们可以把List类型变量的指针改个名:

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->capacity = 10;
}

然后通过指针传参,这样就能成功初始化了。

#include <stdio.h>


typedef int E;

struct List
{
    E array[10];
    int capacity;
};

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->capacity = 10;
}

int main()
{
    struct List list;

    printf("初始化前:%d\n",list.capacity);//初始化前:0

    initList(&list);

    printf("初始化后:%d\n",list.capacity);//初始化后:10

    return 0;
}

代码到此,我们定义了一个线性表类型,并让该类型默认拥有10个长度的数组和一个capacity属性,并且编写了一个初始化函数用于初始化该类型中的数据。(好想说属性,学面向对象学的…)

现在想想,把里面数组的长度写死为10不太好,不够自由,我们可以使用malloc函数指定该数组使用多少内存空间,如果要这样写的话,List结构体中就不能直接声明数组了,而是声明一个指向数组的指针。

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

typedef int E;

struct List
{
    E * array;
    int capacity;
};

typedef struct List * ArrayList;

void initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    list->capacity = 10;
}

储存线性表的元素个数

我们一般在结构体中定义一个size来储存元素个数,默认初始化为0,同时我们再完善一下初始化函数,如果申请内存空间失败,则返回0(false)。

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;
    
    list->capacity = 10;
    list->size = 0;
    
    return 1;
}

当我们执行初始化操作的时候,可以用if判断是否初始化成功:

	struct List list;
    if (initList(&list)){
        ...
    } else
    {
        printf("初始化线性表失败!");
    }

实现插入元素的操作

首先定义一个函数,用于实现对线性表的插入操作。

该函数需要传入表的地址需要插入的元素,还有插入的位置

void insertList(ArrayList list,E element,int index)

注意:index和索引不一样,index没有0,从1开始

插入操作大概可以分为三部分

  • 找到需要插入的位置,从该位置开始,将之后的元素全部往后移动一个单位
  • 在需要插入的位置,修改为指定的元素
  • 插入完毕后,增加size的值
void insertList(ArrayList list,E element,int index)
{
    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;
}

可以写一个打印表的函数来测试一下效果:

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

typedef int E;

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;

    list->capacity = 10;
    list->size = 0;

    return 1;
}

void insertList(ArrayList list,E element,int index)
{
    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int main()
{
    struct List list;

    if (initList(&list)){
        insertList(&list, 111, 1);
        printList(&list);
        insertList(&list, 222, 1);
        printList(&list);
        insertList(&list, 333, 2);
        printList(&list);
    } else
    {
        printf("初始化线性表失败!");
    }
    
    return 0;
}

输出结果为:

111
222 111
222 333 111

说明,表的插入操作成功。

但在上述代码中,没有考虑到别的情况,比如说如果插入一个非法的位置 如-1,表中没有这个位置便会插入失败;比如,如果插入的元素过多,多到了超过了先前定义的40个字节的内存大小,程序的内存就会不安全,所以做扩容的操作也是有必要的。

解决插入到非法位置的问题

解决这个问题可以通过size属性判断,如果要插入的位置在[0,size+1]的区间内,就可以插入,如果不在则不能返回,在函数中便返回0;只需要在循环之前加一个判断。

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 0;
    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;
    
    return -1;
}

解决内存扩容的问题

如果要解决这个问题,需要在插入数组之前进行一次判断,如果表中的元素个数等于表的容量,则把该表之前申请的内存空间大小进行增加,生成新的内存,生成新内存之后,还要把历史元素重新添加进新申请的内存中。

在C语言中,可以不用这么麻烦,我们可以使用realloc函数轻松完成这个任务。

realloc函数可以做到控制动态内存开辟的大小,重新申请的内存空间大小就是我们指定的新的大小,并且原有的数据也会放到新申请的空间中,所以非常方便。当然如果因为内存不足之类的原因导致内存空间申请失败,那么会返回NULL,所以别忘了进行判断。

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 0;

    if (list->size == list->capacity)
    {
        int newCapacity = list->capacity *= 2;// 更新新的容量
        E * newArray = realloc(list->array,sizeof (E) * newCapacity);// 内存扩容
        if (newCapacity == NULL) return 0;
        list->array = newArray;
        list->capacity = newCapacity;
    }

    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;

    return -1;
}

这样就完善了表的插入操作,我们可以测试一下:

int main()
{
    struct List list;
    if(initList(&list)){
        for (int i = 0; i < 30; ++i)
            insertList(&list, i, i+1);
        printList(&list);
    } else{
        printf("顺序表初始化失败,无法启动程序!");
    }

    return 0;
}

输出结果:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

实现删除元素的操作

实现这个过程,思路和插入差不多,只不过需要删除的位置的区间在[1,size]内。

int deleteList(ArrayList list, int index)

删除元素分为两步:

  • 找到需要删除元素的位置将该位置往后的所有元素往前移
  • 将表的size减1

实现获取长度、按位置获取元素、查找元素

int sizeList(ArrayList list) // 获取表长度
{
    return list->size;
}

E * getList(ArrayList list, int index) // 按位置获取元素地址
{
    if (index < 1 || index > list->size) return NULL;
    return &(list->array[index-1]);
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int findList(ArrayList list,E element) // 查找元素
{
    for (int i = 0;i < list->size;i++)
    {
        if (list->array[i] == element) return i + 1;
    }
    
    return -1;
}

实现完成

代码写到此,以数组为基底,构建一个线性表就结束了,一下是全部代码:

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

/*
* 初始化: 我们可以初始化从而得到一个全新的线性表。
* 获取指定位置上的元素: 直接获取线性表指定位置上的元素。
* 获取元素的位置: 获取某个元素在线性表上的位置。
* 插入元素: 在指定位置上插入一个元素。
* 删除元素: 删除指定位置上的一个元素。
* 获取长度: 返回线性表的长度。
 */
typedef int E;

struct List
{
    E * array;
    int capacity;
    int size;
};

typedef struct List * ArrayList;

int initList(ArrayList list)
{
    list->array = malloc(sizeof (E) * 10);
    if (list->array == NULL) return 0;

    list->capacity = 10;
    list->size = 0;

    return 1;
}

int insertList(ArrayList list,E element,int index)
{
    if (index < 0 || index > list->size+1) return 0;

    if (list->size == list->capacity)
    {
        int newCapacity = list->capacity *= 2;// 更新新的容量
        E * newArray = realloc(list->array,sizeof (E) * newCapacity);// 内存扩容
        if (newCapacity == NULL) return 0;
        list->array = newArray;
        list->capacity = newCapacity;
    }

    for (int i = list->size;i > index-1;i--)
    {
        list->array[i] = list->array[i-1];
    }

    list->array[index-1] = element;
    list->size++;

    return -1;
}

int deleteList(ArrayList list, int index)
{
    if (index < 1 || index > list->size) return 0;
    for (int i = index-1;i < list->size - 1;i++)
    {
        list->array[i] = list->array[i+1];
    }
    list->size--;

    return 1;
}

int sizeList(ArrayList list) // 获取表长度
{
    return list->size;
}

E * getList(ArrayList list, int index) // 按位置获取元素地址
{
    if (index < 1 || index > list->size) return NULL;
    return &(list->array[index-1]);
}

void printList(ArrayList list){
    for (int i = 0; i < list->size; ++i)
        printf("%d ", list->array[i]);
    printf("\n");
}

int findList(ArrayList list,E element) // 查找元素
{
    for (int i = 0;i < list->size;i++)
    {
        if (list->array[i] == element) return i + 1;
    }

    return -1;
}

int main()
{
    struct List list;
    if(initList(&list)){
        for (int i = 0; i < 30; ++i)
            insertList(&list, i, i+1);
        printList(&list);
    } else{
        printf("顺序表初始化失败,无法启动程序!");
    }

    return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部