专栏首页三木的博客顺序存储线性表的实现

顺序存储线性表的实现

最近复习数据结构,写了一个顺序存储的线性表,代码粘在这里:)

代码下载:git@github.com:Wang-Sen/algorithm.git

/*
 * Simple array implementation.
 */

#include <stdbool.h>

#define MAX_SIZE 50
#define data_t int
#define array_length_t int

#define ERR_OUT_OF_RANGE -1
#define ERR_EMPTY_ARRAY -2
#define ERR_INVALID_ARGS -3

typedef struct {
    data_t data[MAX_SIZE];
    array_length_t length;
} array;

static inline void array_init(array *arr)
{
    for (int i = 0; i < MAX_SIZE; i++) {
        arr->data[i] = 0;
    }
    arr->length = 0;
}

static inline void show_array(array *arr)
{
    for (int i=0; i < arr->length; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
}

static inline bool is_array_empty(array *arr)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    return !arr->length;
}

static inline array_length_t len(array *arr) {
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    return arr->length;
}

static inline int locate_entry(array *arr, data_t entry) {
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    int ret = -1;
    for (int i = 0; i < MAX_SIZE; i++) {
        if (arr->data[i] == entry) {
            ret = i;
            return ret;
        }
    }
    return ret;
}

static inline int array_push(array *arr, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if ((arr->length + 1) > MAX_SIZE) {
        return ERR_OUT_OF_RANGE;
    }
    arr->data[arr->length] = entry;
    (arr->length)++;
    return 0;
}

static inline int array_pop(array *arr, data_t *p_entry)
{
    if (arr->length <= 0) {
        return ERR_EMPTY_ARRAY;
    }
    if (!p_entry || !arr) {
        return ERR_INVALID_ARGS;
    }

    *p_entry = arr->data[arr->length - 1];
    (arr->length)--;

    return 0;
}

static inline int array_insert(array *arr, int loc, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if ((arr->length + 1) > MAX_SIZE || loc < 0 || loc >= MAX_SIZE) {
        return ERR_OUT_OF_RANGE;
    }
    for (int i = arr->length; i > loc; i--) {
        arr->data[i] = arr->data[i - 1];
    }
    arr->data[loc] = entry;
    (arr->length)++;
    return 0;
}

static inline int array_delete(array *arr, int loc, data_t *entry)
{
    if (!arr || !entry) {
        return ERR_INVALID_ARGS;
    }
    if (loc < 0 || loc >= arr->length) {
        return ERR_OUT_OF_RANGE;
    }

    *entry = arr->data[loc];
    for (int i = loc; i < (arr->length) - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }
    (arr->length)--;
    return 0;
}

static inline int array_update(array *arr, int loc, data_t entry)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }
    if (!arr->length) {
        return ERR_EMPTY_ARRAY;
    }
    if (loc < 0 || loc >= arr->length) {
        return ERR_OUT_OF_RANGE;
    }
    arr->data[loc] = entry;
    return 0;
}

static inline int array_reverse(array *arr)
{
    if (!arr) {
        return ERR_INVALID_ARGS;
    }

    int i, j, tmp;
    for (i = 0, j = (arr->length - 1); j - i > 0; i++, j--) {
        if (arr->data[i] == arr->data[j]) {
            tmp = arr->data[i];
            arr->data[i] = arr->data[j];
            arr->data[j] = tmp;
        } else {
            arr->data[i] ^= arr->data[j];
            arr->data[j] ^= arr->data[i];
            arr->data[i] ^= arr->data[j];
        }
    }

    return 0;
}

测试代码:

#include <stdio.h>
#include <unistd.h>
#include "array.h"

int main(int argc, char **argv) {
    int ret = 0, i;
    array list;
    array_init(&list);

    /* test is_empty_array */
    printf("Empty array: %d\n", is_array_empty(&list));
    list.data[0] = 2400;
    list.length += 1;
    printf("Empty array: %d\n", is_array_empty(&list));
    /* end test is_empty_array */

    /* test push */
    for (i = list.length; i < MAX_SIZE; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }

    show_array(&list);

    if ((ret = array_push(&list, 20))) {
        printf("Err: %d\n", ret);
        printf("length: %d\n", list.length);
        printf("Entry: %d\n", 20);
    }
    /* end test push */

    /* test insert */
    array_init(&list);
    for (i = list.length; i < MAX_SIZE-1; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    array_insert(&list, 3, 5);
    show_array(&list);

    array_insert(&list, 3, 6);
    show_array(&list);

    array_init(&list);
    for (i = list.length; i < MAX_SIZE-1; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    array_insert(&list, MAX_SIZE, 5);
    show_array(&list);
    /* end test insert */

    /* test locate_entry */
    array_init(&list);
    for (i = list.length; i < MAX_SIZE; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    printf("location of 5 is: %d\n", locate_entry(&list, 5));
    printf("location of 10 is: %d\n", locate_entry(&list, 10));
    printf("location of 100 is: %d\n", locate_entry(&list, 100));
    printf("location of -100 is: %d\n", locate_entry(&list, -100));
    /* end test locate_entry */

    /* test len*/
    array_init(&list);
    for (i = 0; i < 38; i++) {
        if ((ret = array_push(&list, i))) {
            printf("Err: %d\n", ret);
            printf("length: %d\n", list.length);
            printf("Entry: %d\n", i);
        }
    }
    printf("len : %d\n", len(&list));
    /* end test len */

    /* test pop */
    array_init(&list);
    int j = 0;
    for (i = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 27; i++) {
        array_pop(&list, &j);
        printf("Pop Entry: %d\n", j);
        show_array(&list);
    }
    /* end test pop */

    /* test delete*/
    array_init(&list);
    for (i = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 27; i++) {
        if (array_delete(&list, i, &j) != 0) {
            printf("Delete %dth entry error!\n", i);
            break;
        }
        printf("Deleted Entry: %d\n", j);
        show_array(&list);
    }
    /* end test delete */

    /* test update*/
    array_init(&list);
    for (i = 0, j = 0; i < 26; i++) {
        array_push(&list, j);
        j += 2;
    }
    show_array(&list);
    for (i = 0; i < 28; i++) {
        if (array_update(&list, i, 99) != 0) {
            printf("Update %dth entry error!\n", i);
            break;
        }
        printf("Updated %dth Entry: %d\n", i, j);
        show_array(&list);
    }
    /* end test update */

    /* test reverse*/
    array_init(&list);
    for (i = 0; i < MAX_SIZE; i++) {
        array_push(&list, i);
    }
    show_array(&list);
    array_reverse(&list);
    show_array(&list);
    /* end test reverse */
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python中的正则表达式

    正则表达式特殊符号表 ? ? ? Python处理正则表达式的方法 ? ?

    用户1214695
  • Linux shell 程序设计1——安装及入门

    1、什么是shell? shell是linux内核的“壳”,是用户和内核的桥梁。它类似于windows下的命令提示符,将用户输入的命令解释给内核执行,并返回给用...

    用户1214695
  • 在fedora下使用搜狗拼音输入法

    Linux下的拼音输入法实在是不敢恭维,还好有人把搜狗拼音输入法制作成了RPM包.安装此rpm包就可以在Linux下面使用搜狗拼音输入法及其字库了. 第一步,下...

    用户1214695
  • PHP 排序算法实现讲解

    所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

    wangxl
  • python 游戏(数字推理游戏Bage

    实现功能:玩家猜测三位不一样的数字,猜错了有提示,提示分别为(位置错误数字正确),(位置和数字正确),(数字和位置都不正确)

    py3study
  • 新手指南OpenStack:Nova的基础知识

    [第二部分基础知识] OpenStack 新手指南 #Nova? 它是OpenStack提供云计算服务的IaaS的主要架构控制器。在美国国家航空航天局(NA...

    天空
  • 【面试题】CSS知识点整理(附答案)

    css引入伪类和伪元素概念是为了格式化文档树以外的信息。伪类和伪元素是用来修饰不在文档树中的部分。

    木子星兮
  • [Servlet] 初识Servlet

    什么是Servlet? 定义 Servlet的全称是 Server Applet,顾名思义,就是用 Java 编写的服务器端程序。 Servlet 是一个 Ja...

    静默虚空
  • 封装数组之包含、搜索和删除元素

    前言:在上一小节中我们已经会了如何获取和如何修改数组中的元素,在本小节中我们将继续学习如何判断某个元素是否在数组中存在、查询出某个元素在数组中的位置、以及删除数...

    wfaceboss
  • JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

    笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便以后复习。

    夜尽天明

扫码关注云+社区

领取腾讯云代金券