数据结构与算法学习笔记六--数组和广义表(C语言)

目录

前言

1.数组

1.定义

2.初始化

3.销毁

4.取值

5.设置值

6.完整代码

---

前言

        这篇博客主要介绍数据结构中的数组和广义表的用法。

1.数组

        在数据结构中，数组是一种线性数据结构，它由一组连续的相同类型的元素组成，每个元素都有一个唯一的索引或者下标来标识其在数组中的位置。

        数字的常用操作除了初始化和销毁之外，只有存取元素和修改元素值的操作。

1.定义

        我们一般使用顺序结构来定义数组。

#define MAX_ARRAY_DIM 8 // 设置数组维数的最大值为8
typedef struct {int *base;      // 数组元素基址,由initArray分配int dim;        // 数组维数int *bounds;    // 数组维界基址,由initArray分配int *constants; // 数组影像函数常量基址,由initArray分配
} Array;

2.初始化

//初始化
int initArray(Array *array, int dim, ...) {if (dim < 1 || dim > MAX_ARRAY_DIM) return 0;array->dim = dim;array->bounds = (int *)malloc(dim * sizeof(int));if (!array->bounds) return 0;int total = 1;va_list ap;va_start(ap, dim);for (int i = 0; i < dim; ++i) {array->bounds[i] = va_arg(ap, int);if (array->bounds[i] < 0) return 0;total *= array->bounds[i];}va_end(ap);array->base = (int *)malloc(total * sizeof(int));if (!array->base) return 0;array->constants = (int *)malloc(dim * sizeof(int));if (!array->constants) return 0;array->constants[dim - 1] = 1;for (int i = dim - 2; i >= 0; --i)array->constants[i] = array->bounds[i + 1] * array->constants[i + 1];return 1;
}

3.销毁

int destroyArray(Array *array) {if (!array->base) return 0;free(array->base);array->base = NULL;if (!array->bounds) return 0;free(array->bounds);array->bounds = NULL;if (!array->constants) return 0;free(array->constants);array->constants = NULL;return 1;
}

4.取值

int getValue(Array *array, ...) {va_list ap;va_start(ap, array);int index = 0;for (int i = 0; i < array->dim; ++i) {int subscript = va_arg(ap, int);if (subscript < 0 || subscript >= array->bounds[i]) {va_end(ap);return 0;}index += array->constants[i] * subscript;}va_end(ap);return array->base[index];
}

5.设置值

int setValue(Array *array, int value, ...) {va_list ap;va_start(ap, value);int index = 0;for (int i = 0; i < array->dim; ++i) {int subscript = va_arg(ap, int);if (subscript < 0 || subscript >= array->bounds[i]) {va_end(ap);return 0;}index += array->constants[i] * subscript;}va_end(ap);array->base[index] = value;return 1;
}

6.完整代码

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>#define MAX_ARRAY_DIM 8 // 设置数组维数的最大值为8
typedef struct {int *base;      // 数组元素基址,由initArray分配int dim;        // 数组维数int *bounds;    // 数组维界基址,由initArray分配int *constants; // 数组影像函数常量基址,由initArray分配
} Array;// 基本操作的函数原型说明
int initArray(Array *array, int dim, ...);
int destroyArray(Array *array);
int getValue(Array *array, ...);
int setValue(Array *array, int value, ...);
void testArrayOperations(void);//初始化
int initArray(Array *array, int dim, ...) {if (dim < 1 || dim > MAX_ARRAY_DIM) return 0;array->dim = dim;array->bounds = (int *)malloc(dim * sizeof(int));if (!array->bounds) return 0;int total = 1;va_list ap;va_start(ap, dim);for (int i = 0; i < dim; ++i) {array->bounds[i] = va_arg(ap, int);if (array->bounds[i] < 0) return 0;total *= array->bounds[i];}va_end(ap);array->base = (int *)malloc(total * sizeof(int));if (!array->base) return 0;array->constants = (int *)malloc(dim * sizeof(int));if (!array->constants) return 0;array->constants[dim - 1] = 1;for (int i = dim - 2; i >= 0; --i)array->constants[i] = array->bounds[i + 1] * array->constants[i + 1];return 1;
}int destroyArray(Array *array) {if (!array->base) return 0;free(array->base);array->base = NULL;if (!array->bounds) return 0;free(array->bounds);array->bounds = NULL;if (!array->constants) return 0;free(array->constants);array->constants = NULL;return 1;
}int getValue(Array *array, ...) {va_list ap;va_start(ap, array);int index = 0;for (int i = 0; i < array->dim; ++i) {int subscript = va_arg(ap, int);if (subscript < 0 || subscript >= array->bounds[i]) {va_end(ap);return 0;}index += array->constants[i] * subscript;}va_end(ap);return array->base[index];
}int setValue(Array *array, int value, ...) {va_list ap;va_start(ap, value);int index = 0;for (int i = 0; i < array->dim; ++i) {int subscript = va_arg(ap, int);if (subscript < 0 || subscript >= array->bounds[i]) {va_end(ap);return 0;}index += array->constants[i] * subscript;}va_end(ap);array->base[index] = value;return 1;
}void testArrayOperations(void) {Array array;if (initArray(&array, 2, 3, 4)) {printf("Array initialized successfully.\n");printf("Setting values...\n");for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {if (setValue(&array, i * 10 + j, i, j)) {printf("Value set at (%d, %d).\n", i, j);} else {printf("Failed to set value at (%d, %d).\n", i, j);}}}printf("Getting values...\n");for (int i = 0; i < 3; ++i) {for (int j = 0; j < 4; ++j) {int value;if (getValue(&array, i, j, &value)) {printf("Value at (%d, %d): %d\n", i, j, value);} else {printf("Failed to get value at (%d, %d).\n", i, j);}}}printf("Destroying array...\n");if (destroyArray(&array)) {printf("Array destroyed successfully.\n");} else {printf("Failed to destroy array.\n");}} else {printf("Failed to initialize array.\n");}
}
int main(int argc, const char *argv[]) {testArrayOperations();return 0;
}